Track: Operations Research

Abstract

Japanese school lunches are said to be more nutritionally balanced than those of other countries. This is due to the fact that school lunch menus are prepared in consideration of various items such as food categories and coloring of dishes. As a specific example, Japanese school lunches include not only meat-based dishes, but also rice and side dishes as part of the daily menu. In Japan, there is a style of cooking called Washoku. It is an expression of the Japanese people's respect for nature, and has been selected as an intangible cultural heritage because it is a traditional social practice that has been passed down from generation to generation.

In the field of school lunch, there is a need for a system to support nutrition teachers in menu planning. There are many restrictions to be considered in menu preparation, such as nutritional intake standards, ingredient costs, and cooking time, and it takes a lot of time and effort to complete a menu. In Japan, the intake of 13 nutrients is determined according to the School Meal Intake Standards established by the Ministry of Education, Culture, Sports, Science and Technology (MEXT). Therefore, when preparing menus, it is necessary to keep within the upper and lower limits of the standard's intake.

Previous research has proposed a menu planning model using a mathematical optimization solver that takes into account about 70 different constraints. However, the model has two problems: First, it does not adequately take into account the frequency with which food items and dishes are served. Second, the solution time is too long (about 6,000 seconds). The second reason for this is the number of decision variables and constraints in a month, which are enormous: approximately 200,000 and 10,000, respectively. On the other hand, another previous studies using genetic algorithms (hereafter referred to as GAs) have produced menus in a relatively short time. However, the number of constraints considered is quite small (six), and the frequency of serving ingredients and dishes is not taken into account. In general, in GA, as the number of constraints increases, the solution generated by crossing becomes infeasible in many cases, and it is time-consuming to change to a feasible solution.

In this study, we formulate an automatic menu creation model that takes into account the frequency of serving ingredients and dishes as a mathematical optimization problem. Using the tabu search method, we propose a heuristic solution method that can find a good solution in practical time when the number of constraints is large. The solution corresponds to a menu, which is a combination of dishes for a day. By exchanging dishes in the menu, a better solution is searched. In this study, a taboo list is provided to prevent the user from re-selecting a dish once it has been selected. Numerical experiments using real data of school lunch menus show that the proposed method reduces the solution time better than the conventional method.