Computer-based dietary menu planning

In this paper, we introduce a computer-based method for menu planning, which applies evolutionary computation. First, we formalize the n-day menu-planning problem, decomposing it into several sub-problems at the daily-menu and meal-planning level. We reduce the problem to a multi-dimensional knapsack problem. Then, we define an evolutionary algorithm that quickly finds a diverse set of feasible solutions (i.e. optimal menus) with the optimum objective functions’ values, without examining all the possibilities. As the problem is constrained, infeasible solutions need to be repaired in order to direct the “evolution” towards the feasible regions. We present greedy repairing methods that slightly differ at the global level and the sub-problems’ levels. At the meal-planning level, we couple repairing with linear programming to balance infeasible meals. We conclude the paper with the presentation of empirical results, which showed that the evolutionary method may outperform a human. A computer was able to find the Pareto-optimal front of 21-day menus with respect to a dietary advice in equal or less time than a human professional, who designed a daily menu. However, the human factor is still important in the last stage, when a solution has to be selected from the Pareto front.