A novel cost-palatability bi-objective approach to the menu planning problem with an innovative similarity metric using a path relinking algorithm

Bad eating habits are considered with low exercise, tobacco, and alcohol use, among the greatest health risk factors in high-income countries. Here, the spread of non-communicable diseases related to diet contrasts with the increasing availability of diet guidelines and health information. We are all left wondering, why are we not eating healthier? Palatability and cost appear as the two most important barriers to adherence to any prescribed diet. This work aims to generate high-adherence healthy menus attending to Mediterranean standards, modelling and solving a cost palatability bi-objective optimisation problem. Although the latter is implicitly considered in most current models, its use as a quantifiable objective is novel. For this, a novel Similarity Function is introduced, which evaluates the proximity of two different menus and returns a similarity metric between 0 and 1. A multi-criteria optimisation method is used to design nutritious menu plans and analyse the trade-off between the cost and palatability of menus. A Path Relinking algorithm is later applied to improve the objective values, with specific considerations to palatability, designing healthy menus that can beat those adherence barriers.