# A Study on Menu Planning Method Considering the Variation in Menu Orders - Application to Daily Foods in a Company Cafeteria

Ruriko Watanabe, Nobutada Fujii, Daisuke Kokuryo, Toshiya Kaihara, Kyohei Irie, Kenji Yanagita, Kenichi Harada

<figure><img src="image_1.png" /></figure>

## ► To cite this version:

Ruriko Watanabe, Nobutada Fujii, Daisuke Kokuryo, Toshiya Kaihara, Kyohei Irie, et al.. A Study on Menu Planning Method Considering the Variation in Menu Orders - Application to Daily Foods in a Company Cafeteria. IFIP International Conference on Advances in Production Management Systems (APMS), Sep 2021, Nantes, France. pp.224-231, 10.1007/978-3-030-85906-0_25 hal-04022126

HAL Id: hal-04022126

https://inria.hal.science/hal-04022126

Submitted on 9 Mar 2023

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
<figure><img src="image_3.png" /></figure>

ifip

International Federation for Information Processing

This document is the original author manuscript of a paper submitted to an IFIP
conference proceedings or other IFIP publication by Springer Nature. As such, there
may be some differences in the official published version of the paper. Such
differences, if any, are usually due to reformatting during preparation for publication or
minor corrections made by the author(s) during final proofreading of the publication
manuscript.
# A Study on Menu Planning Method Considering the Variation in Menu Orders
## - Application to daily foods in a company cafeteria -

Ruriko Watanabe<fnref n="1" />, Nobutada Fujii<fnref n="1" />, Daisuke Kokuryo<fnref n="1" />, Toshiya Kaihara<fnref n="1" />, Kyohei Irie<fnref n="1" />, Kenji Yanagita<fnref n="2" /> and Kenichi Harada<fnref n="2" />

r.watanabe@crystal.kobe-u.ac.jp, nfujii@phoenix.kobe-u.ac.jp, kokuryo@port.kobe-u.ac.jp, kaihara@kobe-u.ac.jp, kenji_yanagita@tte-net.com and kenichi_harada@tte-net.com

**Abstract.** It is a problem that dietitians have a shortage of labor and a large amount of work per person. The work of a dietitian includes menu planning, ordering meals, nutritional guidance, etc. Among them, menu planning is an important work. Menu planning is an advanced work that considers dietitians adjustment, safety and economic efficiency based on basic knowledge such as cooking combination, food combination, appropriate amount for one-person, seasoning ratio, cooking method, etc. It is thought that reducing the burden on menu planning will lead to more efficient work for dietitians. The subjects for which a dietitian makes a menu plan are classified into managed meals such as those provided at hospitals and daily meals provided to healthy people in a company cafeteria. This paper proposes a menu planning method that meets the requirements for menu plans for regular meals in the company cafeteria, which has more constraints than managed meals and is a complicated problem. The menu planning is optimized by a DGA (Distributed Genetic Algorithm) using an evaluation function that expresses the variations in menu orders.

**Keywords:** Genetic Algorithm • Menu Planning • Information Entropy

## 1 Introduction

It is a problem that dietitians have a shortage of labor and a large amount of work per person. The work of a dietitian includes menu planning, ordering meals, nutritional guidance, etc. Among them, menu planning is an important work. Menu planning is an advanced work that considers dietitians adjustment, safety and economic efficiency based on basic knowledge such as cooking combination, food combination, appropriate amount for one-person, seasoning ratio, cooking method, etc. It is regarded as a problem that dietitians have a large amount of work per person due to labor shortage [1]. It is thought that reducing the burden on menu planning will lead to more efficient work for dietitians.

<footnote n="1">¹ Kobe University, 1-1 Rokkodai-cho, Nada, Kobe, Hyogo, 657-8501, Japan</footnote>

<footnote n="2">² TMES Corporation</footnote>
The subjects for which a dietitian makes a menu plan are classified into managed meals [2] such as those provided at hospitals and daily meals [3] provided to healthy people in a company cafeteria. Table 1 shows the requirements for preparing menus for managed meals and daily meals.

<table><caption>**Table 1.** Menu planning requirements for managed meals and daily meals</caption><thead><tr><th></th><th>Managed meals</th><th>Daily meals</th></tr></thead><tbody><tr><td>Diversity of dishes</td><td colspan="2">Considering the variety of dishes and the order of serving so that the eaters will not get bored</td></tr><tr><td>Nutrition</td><td>Adjusted based on dietary intake standards</td><td>Adjusted based on the standards set for each business establishment</td></tr><tr><td>Ingredient cost</td><td>Considering of keeping within a limited budget</td><td>Considering by cost rate</td></tr><tr><td>Menu style</td><td>Considering the combination of one meal</td><td>Considering many kinds of dishes for one meal</td></tr></tbody></table>

This study focuses on menu planning for daily meals in a company cafeteria. As shown in Table 1, menu planning for daily meals is a more complex problem structure with more constraints than managed meals.

Four decades ago, the need for computer-based methods for menu planning was recognized. In 1964, Balintfy[4] applied linear programming techniques to build the first computer-based menu planner, which optimized menus for nutritional adequacy and budgeted food cost. Subsequently, menu planning methods using random sampling techniques [5], interactive [6] and evolutionary computation [7] were proposed. In this research, which has a complex problem structure with many constraints, a menu planning method using GA (Genetic Algorithm) has been proposed [8], which is an algorithm that only requires information to determine the degree of adaptation to a given environment and requires little information about the nature of the problem to be solved, such as a mathematical model. By expanding the method of the previous study [8], the developed menu planning method is suggested that takes into account the variation in the characteristics of dishes in consecutive days, the variation in the characteristics of dishes in the same category provided on the same day, the event menu for each day of the week, and the cost rate.

## 2 Menu planning using genetic algorithm

In this study, menus are planed from a cooking database using a genetic algorithm.
## 2.1 Target problem

The menu is for a company cafeteria where meals are served in a cafeteria style, and the menu is planned for 20 days (4 weeks) only for lunch on weekdays. In addition, the categories of dishes offered per day are main dish A, main dish B, main dish C, bowl, curry, Japanese noodles, Chinese noodles, pasta, small bowl A, small bowl B, small bowl C, salad and dessert.

The total number of dishes registered in the cooking database is 1770. The information that each dish data has is "cooking number", "cooking name", "cost", "characteristic 1", "characteristic 2", and "characteristic 3". Regarding the characteristics of cooking, characteristic 1: main ingredients, characteristic 2: cooking method, and characteristic 3: classification, are held as numerical values of each item. The number of items for each characteristic differs depending on the cooking category.

## 2.2 Distributed Genetic Algorithm

Since the daily meals have more constraints than the case of the managed meals and the search ability is not sufficient in the single-population Genetic Algorithm, Distributed Genetic Algorithm (DGA) [9] having a higher search ability is used. The flow of DGA is shown below.

Step 1. **Generation of early individuals**
Individuals are randomly generated until the default number of individuals is reached.

Step 2. **Fitness calculation**
The fitness of the individual is calculated.

Step 3. **Confirmation of the number of generations**
If generations have not reached the default number, go to step 4. If they reach, the calculation ends.

Step 4. **Selection**
Next-generation individuals are selected according to the evaluation value of each individual. The best individuals of that generation remain in the next generation.

Step 5. **Migration judgement**
If generations have reached the default number, proceed to step 6. If they have not been reached, go to step 7.

Step 6. **Migration**
The number of individuals determined by the migration rate from each sub-population is transferred to another population.

Step 7. **Crossover**
Two individuals are randomly selected and uniformly crossed with a certain probability.

Step 8. **Mutation**
Each individual is mutated with a certain probability, return to step 2.
## 2.3 Gene Coding

The genetic coding is shown in Fig. 1. 20 pieces for each of the 13 cooking categories (main dish A, B, C, bowl, curry, Japanese noodles, Chinese noodles, pasta, small bowls A, B, C, salad and dessert) They are arranged one by one (5 days on weekdays x 4 weeks), and each is arranged according to the menu orders. Each individual holds the dish number of the corresponding category. The information contained dish data, which is not included in the gene, is linked to the dish number.

<figure><img src="image_4.png" /><figcaption>Fig. 1 Cording of individuals</figcaption></figure>

## 2.4 Fitness function

The fitness function F consists of the evaluation value H of the variability of the order of appearance of the features of a dish, the evaluation value S of the variability of the features of the same category of dishes on the same day, and a penalty term p. With reference to the calculation method of the evaluation function in the previous study [10], the entropy H<sub>m,i</sub> for measuring the variation in the appearance order of the characteristics for each dish of each category is calculated as the average of the all intervals, shifting the intervals with the number of items J<sub>|m,i</sub> as one interval. The expressions and the meanings of the characters in the expressions are shown below.

$$ 
\begin{aligned}
F &= \sum_{m=1}^{M} \sum_{i=1}^{I} \frac{H_{m,i}}{H_{m,i}^{*}} + S + p \\
H_{m,i} &= -\frac{1}{T - J_{|m,i} + 1} \sum_{t=1}^{T - J_{|m,i} + 1} \sum_{j_{|m,i}=1}^{J_{|m,i}} P_{j_{|m,i}}(t) \log P_{j_{|m,i}}(t) \\
P_{j_{|m,i}}(t) &= \frac{1}{J_{|m,i}} \sum_{k=0}^{J_{|m,i}-1} \alpha_{j_{|m,i}}(t+k) \\
S &= \frac{1}{MTI} \sum_{m=1}^{M} \sum_{t=1}^{T} \sum_{i=1}^{I} \frac{\beta_{t,j_{m,i}}}{\beta_{t,j_{m,i}}^{*}}
\end{aligned}
$$
- $m = 1,2,..., M$: Cooking category

- $i = 1,2,..., I$: Characteristics of cooking

- $j_{m,i} = 1,2,..., J_{m,i}$: Characteristic $i$ item of dish type $m$

- $t = 1,2,..., T$: Menu ordinal number (for $T$ days)

- $P_{i|m,i}$: Serving frequency ratio in one section from $t$ of dishes with $j_{m,i}$

- $\alpha_{j|m,i}$: 1/0 binary variable representing the serving / non-serving of dishes with the feature $j_{m,i}$ in $t$

- $H_{m,i}$: Average of entropy of characteristic $i$ of all sections of dish type $m$

- $H_{m,i}^*$: Maximum value of $H_{m,i}$

- $\beta_{t,j,m,i}$: Number of types of item $i$ of characteristics of dishes in category $m$ on day $t$

- $\beta_{t,j,m,i}^*$: Maximum value of $\beta_{t,j,m,i}$

- $S$: Evaluation index for variations in the characteristics of dishes of the same category on the same day

- $P$: Penalty term when there is a constraint violation (if any of the constraints described is violated : -10, if not : 0)

$H_{m,i}$ is not considered for curry characteristics 3, Japanese noodles characteristics 1 and 2, small bowl A characteristics 2, salad characteristics 1 and 2, and desserts due to data bias.

## 2.5 Constraints

The restriction that the event menu specified for each day of the week is included in the target day of the week, the menu categorized as "high profit" is included once a week, and the menu categorized as "popular TOP20" is included twice a week. The cost rate is restricted so that the average cost rate falls within a certain range. Since there is a target value for the usage ratio of the main ingredients (characteristic 1) for the main dish and rice bowl dishes, the usage ratio of the main ingredients is set so that the error from the target value is within $\pm$ 5%.

# 3 Computer experiments

These experiments are conducted to create a menu using the proposed method and verify its effectiveness by comparing it with the comparison method (single-population Genetic Algorithm) and the menu prepared by a dietitian.

## 3.1 Experimental conditions

Use the cooking database in which the 1770 kinds of dishes described in Section 2.1 are registered. The number of trials was 10.

The parameters of GA and DGA are shown in Table 2.
<table><caption>**Table 2.** Experimental conditions</caption><thead><tr><th></th><th>GA</th><th>DGA</th></tr></thead><tbody><tr><td>Population</td><td>1000</td><td>1000</td></tr><tr><td>Number of islands</td><td>-</td><td>5</td></tr><tr><td>Number of genetically mated generations</td><td>100,000</td><td>100,000</td></tr><tr><td>Migration interval</td><td>-</td><td>1000</td></tr><tr><td>Migration rate</td><td>-</td><td>0.01</td></tr><tr><td>Target individuals for migration</td><td>-</td><td>Descending order of fitness</td></tr><tr><td>Selection method</td><td>Tournament selection (Tournament size: 2)</td><td>Roulette tournament selection (Tournament size: 2)</td></tr><tr><td>Crossing method</td><td>Uniform crossing (crossing rate: 0.9)</td><td>Uniform crossing (crossing rate: 0.9)</td></tr><tr><td>Mutation rate</td><td>0.1</td><td>0.1</td></tr></tbody></table>

## 3.2 Experimental results

### Comparative experiment between DGA and single-population GA

Table 3 shows the maximum, minimum, average, standard deviation of the evaluation value *F* of the solution obtained in 10 trials and value *F* of menu prepared by a dietitian used in the actual cafeteria.

<table><caption>**Table 3.** Comparison of the degree of fitness</caption><thead><tr><th rowspan="2"></th><th colspan="4">F</th></tr><tr><th>Max.</th><th>Min.</th><th>Ave.</th><th>Std.</th></tr></thead><tbody><tr><td>Proposed method (DGA)</td><td>26.36</td><td>25.69</td><td>26.10</td><td>0.21</td></tr><tr><td>Comparison method (single-population GA)</td><td>25.10</td><td>17.00</td><td>24.12</td><td>2.51</td></tr></tbody></table>

From Table 3, it was confirmed that a solution with higher fitness was obtained using DGA than single-population GA. The minimum value of fitness by single-population GA is extremely low, and it can be confirmed that the search performance of the algorithm is insufficient without getting out of the solution with the constraint violation. On the other hand, the minimum value of fitness by DGA is 25.69, and it can be confirmed that the search performance is improved.

Fig. 2 shows comparison of the diversity of solutions in the population. The horizontal axis represents the number of generations, and the vertical axis represents the type of solution in the population. For the single-population GA, it is confirmed that the diversity of solutions within the population is lost and converges at an early stage.
For the DGA, the diversity of solutions is maintained, so the search performance is improved and a solution with better fitness is obtained.

<figure><img src="image_5.png" /><figcaption>Fig. 2. Comparison of the diversity of solutions in the population</figcaption></figure>

## Comparison with the menu prepared by dietitians

Table 3 shows the fitness of the menu obtained by the proposed method and the menu actually prepared by the dietitian.

<table><caption>Table 3. Comparison of the degree of fitness</caption><thead><tr><th></th><th>Proposed method</th><th>Menu prepared by the dietitian</th></tr></thead><tbody><tr><td><em>F</em></td><td>26.36</td><td>14.29</td></tr><tr><td>Main dish A</td><td>2.32</td><td>1.84</td></tr><tr><td>Main dish B</td><td>2.32</td><td>1.82</td></tr><tr><td>Main dish C</td><td>2.40</td><td>1.98</td></tr><tr><td>Bowl</td><td>2.58</td><td>1.77</td></tr><tr><td>Curry</td><td>1.69</td><td>1.08</td></tr><tr><td>Noodle J</td><td>0.97</td><td>0.54</td></tr><tr><td>Noodle C</td><td>2.32</td><td>1.70</td></tr><tr><td>Pasta</td><td>2.44</td><td>1.32</td></tr><tr><td>Side dish A</td><td>1.90</td><td>0.00</td></tr><tr><td>Side dish B</td><td>2.63</td><td>0.51</td></tr><tr><td>Side dish C</td><td>2.76</td><td>1.09</td></tr><tr><td>Salad</td><td>0.97</td><td>0.00</td></tr><tr><td>Duplication</td><td>0.82</td><td>0.64</td></tr></tbody></table>
The proposed method has a higher fitness. Even when the objective function value is divided into the degree of variation in each cooking category, the proposed method gives a higher value in all cases. It can be confirmed that the fitness is increasing in the proposed method even in the cooking category such as Side dish A, where diversity was not taken into consideration when the dietitian made the menu.

From the discussion with the dietitian, it was suggested that the proposed method would be useful in the real world, as it would be able to create menus with a variety of cooking category that cannot be fully considered by humans.

## 4 Conclusion

This study proposed a menu planning method that considers the menu order so that eaters will not get tired of dishes, targeting the daily meals in the company cafeteria where food is served in a cafeteria format.

As a result of computer experiments, it was confirmed that proposed method could search for the solution while maintaining the diversity of solutions within the population and obtain the solution with a high fitness, compared with the single-population GA. By comparing the menus obtained by the proposed method with the menus prepared by the dietitians, the menus obtained by the proposed method had a more varied order of appearance of the characteristics of the dishes. Although omitted in this paper, it is confirmed that the proposed method can meet the restrictions that the registered dietitian cannot meet.

Future prospects include consideration of the expiration date and inventory of ingredients, and consideration of nutrients by establishing categories such as healthy menus.

## References

1. Hisako Kamata, Miyoko Hasumi and Reiko Aikawa, A Study of Menu Planning Ability on a Dietitian Course: An Analysis of Factors Related to Menu Planning, Journal of the Japanese Society of Food Education, Vol.7, No.4, 2013. (Japanese)

2. Yoshitaka Okamura, Nakamori Yuka, Hamano Atsuko, Higuchi Naoko, Yoshida Mayumi, Okuda Toyoko, Nutritional management for the dietary reference intake in the hospital diet: about nutrients which is apt tp be short, Senri Kinran University Bulletin, pp.1-13, 2007. (Japanese)

3. Yumi Yoshioka, Yukari Kobayashi, Akiko Ogawa and Hatsuko Murasawa, An approach to nutrition education of company cafeteria lunches by industry, government and a college, Journal of Nagano Prefectural College, pp.21-29, No. 69, 2014. (Japanese)

4. J.L. Balintify, Menu planning by computer, Commun. ACM, Vol.7, No.4, pp. 255-259, 1964.

5. Brown, R.M, Automated menu planning, M.S.Thesis. Kansas State University, 1966.

6. T. Hinrichs, Problem Solving in Open Worlds: A Case Study in Design Lawrence Erlbaum Associates, Hillsdale, NJ, 1992.

7. Barbara Korousic Seljak, Computer-based dietary menu planning, Journal of Food Composition and Analysis Vol.22, No.5, pp.414-420, 2009.
8. Kohei Irie, Nobutada Fujii, Daisuke Kokuryo and Toshiya Kaihara, A study on planning method for managed meal – Consideration of the cost of ordering ingredients -, APMS 2020 International Conference Advances in Production Management Systems 679-685, 2020.

9. Tomoko Kajima, Yukiko Orito and Hiroshi Someya, Consecutive Meals Planning on Meals Support System: Verification of Solutions Obtained by Permutation GA, The papers of Technical Meeting on Intelligent Transport Systems, IEE Japan, pp.1-6, 2017. (Japanese)

10. Reiko Tanese, Distributed Genetic Algorithms. Proc,3rd ICGA, pp.434-439, 1989.