## Guangjie Liu , Jinlong Zhu , Qiucheng Sun , Jiaze Hu and Hao Yu## |

Order | O | M | P | [TeX:] $$\left(\mathbf{A}-\mathbf{Y}_{\mathrm{a}}\right) \mathbf{2} / \mathbf{n}$$ | [TeX:] $$\left(\mathbf{B}-\mathbf{Y}_{\mathbf{b}}\right) \mathbf{2} / \mathbf{n}$$ | [TeX:] $$\left(\mathbf{C}-\mathbf{Y}_{\mathbf{c}}\right) \mathbf{2} / \mathbf{n}$$ |
---|---|---|---|---|---|---|

1 | 20 | 50 | 200 | 1.764 | 1.681 | 1.6 |

2 | 30 | 52 | 200 | 3.364 | 0.441 | 1.6 |

3 | 19 | 56 | 190 | 2.704 | 0.361 | 3.6 |

4 | 25 | 54 | 200 | 0.064 | 0.001 | 1.6 |

5 | 30 | 50 | 190 | 3.364 | 1.681 | 3.6 |

6 | 20 | 57 | 200 | 1.764 | 0.841 | 1.6 |

7 | 25 | 53 | 190 | 0.064 | 0.121 | 3.6 |

8 | 23 | 58 | 200 | 0.144 | 1.521 | 1.6 |

9 | 24 | 51 | 200 | 0.004 | 0.961 | 1.6 |

10 | 26 | 60 | 190 | 0.324 | 3.481 | 3.6 |

Y | 24.2 | 54.1 | 196 | - | - | - |

σ | - | - | - | 1.338453 | 0.987611 | 0.979796 |

CV(%) | 5.53 | 1.83 | 0.50 | - | - | - |

[TeX:] $$\mathrm{Y}=\left(\mathrm{X}_{1}+\mathrm{X}_{2}+\ldots \mathrm{X}_{\mathrm{n}}\right) / \mathrm{n}, \mathrm{CV} \text { (coefficient of dispersion) }=\sigma / \mathrm{Y}, \mathrm{CV}<10 \%$$

As shown in Fig. 2, we use the population density and degree of path congestion as the path evaluation indicators. The most important factor is the recommendation score. In this way, we introduce a large number of factors influencing the path selection into the model, which makes the path strategy more valuable. The model considers these factors and uses historical data to evaluate the path-benefit value. This value is then passed to the game theory as an input parameter for choosing the path, as shown in Fig. 2.

The game theory model was used to solve the problem of repetition. The model includes the participants and selection strategies. We used a prisoner game, as shown in Table 2. As can be seen from Table 2, the results of the different strategies chosen by the two prisoners are different from each other. In all strategies, the Nash equilibrium achieves the maximum benefit for both prisoners, allowing them to avoid pleading guilty.

Table 2.

Prisoner B stays silent (cooperates) | Prisoner B betrays (defects) | |
---|---|---|

Prisoner A stays silent (cooperates) | Each serves 1 year | Prisoner A: 3 years |

Prisoner B: goes free | ||

Prisoner A betrays prisoner B (defects) | Prisoner A: goes free | Each serves 2 years |

Prisoner B: 3 years |

In this study, the scenes are hyper-graphed when comparing the two play routes to find the optimal path, and we use the prisoner’s dilemma to choose the path. When choosing multiple paths, we compare two paths pairwise, and finally choose the best path.

In general, the game is defined as G = {R, S, A, U}, where we have the following:

1. Participator: The [TeX:] $$l^{\text {th }}$$ tourist route is defined as [TeX:] $$R_{i}, i \in N, N=\{1,2 \ldots n\}.$$

2. Strategy space: [TeX:] $$R_{i} \text { is } S_{i}, S_{i} \in\left[0, G_{i}\right], i \in N.$$ From [TeX:] $$R_{i},$$ we assume that the largest number of tourists is [TeX:] $$G_{i} . G_{i}$$ is equal to [TeX:] $$p_{i}(x)$$ using the Monte Carlo method.

3. [TeX:] $$U\left(x_{1}, \ldots, x_{n}\right)$$ is the payoff function of the game; more formally, let

where [TeX:] $$r^{\prime} s_{i}^{p}$$ is the recommended score for the [TeX:] $$i^{\mathrm{th}}$$ path, and [TeX:] $$r s_{j}$$ is the recommended score for the [TeX:] $$i^{\text {th }}$$ scenic spot. In addition, n is the number of paths, m is the number of scenic spots, and t is the time spent on the road or at a scenic spot.

The Nash equilibrium obtained by the game theory model is the mapping relationship between all tourist routes, and thus, the optimal route of tourists can be obtained.

According to the pseudo-palace plane structure, the proposed hypergraph model constructs a network topology map, as shown in Fig. 3. We constructed a hypergraph structure consisting of five regional hypergraphs. The nodes of the regional hypergraph are composed of buildings, roads, gates, flower cells, swimming pools, and ponds. The building node is composed of a floor, staircase, door, and basement node. The floor or basement joints are composed of rooms, corridors, stairs, and overpasses. The room is made up of various furniture, decorations, and furnishings.

There are 153,728 nodes in the super graph used to retrieve the nodes and obtain the travel routes. The weight of the edges between the nodes is the distance between two points divided by the walking speed. Our experiment consists of four scenarios: the route of the entire tour, the route of a single architectural tour, the optional tour route, and a custom scene with a high crowd density. Each viewing area contains the following extended attributes: the best viewing time interval, best viewing season, recommended viewing time, precursor spot, succeeding spot, and person threshold (the maximum number of persons accommodated by the best viewing effect at the spot). These factors are used as the basis for the formulation of the play routes and affect the final path results.

**Scenario 1**

We used three testing methods to verify the performance of our algorithm in scenario 1. The number of people was lower than the person threshold at the viewing point. Table 3 shows the comparison data between our method and multi-goal path planning (MGPP) [1] and heuristic algorithm (HA) [15]. The results show that the path generated by our algorithm is the longest because the path given by our method fully considers the best viewing time of a scenic spot, which leads to the shortest path. Our method can provide the recommended viewing time for each scenic spot, whereas other methods do not support this function.

Table 4 shows the strategy of sightseeing paths 9 through 12 under different weather conditions. The business hours of the palace are from 9 a.m. to 6 p.m. Therefore, the deadline of the obtained strategy will be no later than 6 p.m. In addition, it can be seen from Table 4 that the recommended path length is the shortest because outdoor scenes cannot be seen on rainy days. Compared with sunny days, the recommended consumption time of cloudy and rainy days is less because the outdoor play time is reduced. Although the indoor viewing time is increased, the overall time is reduced.

Table 3.

Method | Route length (m) | Recommended consumption time (hr) |
---|---|---|

The proposed method | 15,560 | 5.7 |

MGPP | 14,768 | null |

HA | 14,768 | null |

Table 4.

Time | Sunny day | Cloudy day | Rainy day | |||
---|---|---|---|---|---|---|

Route length (m) | Consumption time (hr) | Route length (m) | Consumption time (hr) | Route length (m) | Consumption time (hr) | |

9 | 15,560 | 5.7 | 15,560 | 5.3 | 10,328 | 4.5 |

10 | 15,560 | 5.7 | 15,560 | 5.3 | 10,328 | 4.5 |

11 | 15,560 | 5.7 | 15,560 | 5.3 | 10,328 | 4.5 |

12 | 15,560 | 5 | 15,560 | 5 | 10,328 | 4.5 |

The data in Table 5 show the comparison data of the tourism path strategies generated at 9 o'clock for 12 months on sunny days. It can be seen from the data that in the case of bad weather during the winter, the path length is the shortest, thus causing the shortest time for tourism consumption. Because winter in Changchun is extremely long, from November to March of the following year, the change in path distance and time can be seen within this range.

Table 5.

Month | Route length (m) | Recommended consumption time (hr) |
---|---|---|

1 | 10,328 | 4.5 |

2 | 10,328 | 4.5 |

3 | 10,328 | 4.5 |

4 | 10,328 | 4.5 |

5 | 15,560 | 5.7 |

6 | 15,560 | 5.7 |

7 | 15,560 | 5.7 |

8 | 15,560 | 5.7 |

9 | 15,560 | 5.7 |

10 | 15,560 | 5.7 |

11 | 10,328 | 4.5 |

12 | 10,328 | 4.5 |

**Scenario 2**

We used two test methods to verify the performance of our algorithm under scenario 2. The number of people was lower than the person threshold at the viewing point. We chose the scenic spot list to test the performance of the path-generating algorithm, as shown in Table 6.

Table 7 shows the strategy of sightseeing paths from 9 to 12 under different weather conditions. The data in the table show that the path length and time are the same in different climates. Because the scenes are indoors, viewing is not affected by the climate.

Table 6.

No. | Scenic spots |
---|---|

1 | Tongde Hall |

2 | Academy of painting and calligraphy |

3 | Gungnaebu |

4 | Changchunxuan |

5 | Zhixiuxuan |

6 | Rising floor |

7 | Zhonghe gate |

8 | Zhonghe gate |

9 | Huaiyuan building |

Table 7.

Time | Sunny day | Cloudy day | Rainy day | |||
---|---|---|---|---|---|---|

Route length (m) | Consumption time (hr) | Route length (m) | Consumption time (hr) | Route length (m) | Consumption time (hr) | |

9 | 7,598 | 2.1 | 7,598 | 2.1 | 7598 | 2.1 |

10 | 7,598 | 2.1 | 7,598 | 2.1 | 7598 | 2.1 |

11 | 7,598 | 2.1 | 7,598 | 2.1 | 7598 | 2.1 |

12 | 7,598 | 2.1 | 7,598 | 2.1 | 7598 | 2.1 |

The data in Table 8 show the comparison data of tourism path strategies generated at 9 o'clock for 12 months on sunny days. Because the scenes are indoor, the viewing is not affected by the season.

Table 8.

Month | Route length (m) | Recommended consumption time (hr) |
---|---|---|

1 | 7,598 | 2.1 |

2 | 7,598 | 2.1 |

3 | 7,598 | 2.1 |

4 | 7,598 | 2.1 |

5 | 7,598 | 2.1 |

6 | 7,598 | 2.1 |

7 | 7,598 | 2.1 |

8 | 7,598 | 2.1 |

9 | 7,598 | 2.1 |

10 | 7,598 | 2.1 |

11 | 7,598 | 2.1 |

12 | 7,598 | 2.1 |

**Scenario 3**

Scenario 3 is the viewing strategy for a single building. The number of people was lower than the person threshold at the viewing point. We chose Tongde Hall as the test scene. Because it is a single scene, we take the order of each viewing point in the building as the test result of the path strategy. The path policy is mainly affected by the attributes of each node, including the code, precursor, successor, and recommended viewing duration. Because Tongde Hall is an indoor scene, the route strategy is unaffected by the season or climate.

We considered the room as the basic node unit of the comparison data. The numbers in Table 9 represent the number of room nodes, and the path column represents the sequence of the path nodes. Compared with methods B and C, method A shows that the order of nodes, i.e., 13, 21, 24, 36, and 39, is different. This is because the precursor and successor of these points affect the node order of the path, as shown in Table 10.

The results of the algorithm-based game theory for optimizing the tourism route strategy combined with the Monte Carlo route evaluation mechanism show that the model can fully consider the precursor, follow-up, best season, and best time factors of the scenic spots. The path strategy guarantees the shortest path under the premise of satisfying the constraints.

Table 9.

Method | Path |
---|---|

Proposed method | 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 13, 15, 16, 18, 17, 19, 20, 22, 23, 21, 25, 26, 24, 27, 28, 30, 31, 29, 36, 32, 33, 34, 35, 37, 38, 40, 39, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52 |

MGPP | 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 18, 17, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 30, 31, 29, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52 |

HA | 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 18, 17, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 30, 31, 29, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52 |

**Scenario 4**

To test the performance of the model, scenario 4 applies a list of test spots under Scenario 2 as a custom viewing point. We chose hot spots as our custom viewing spots, and the attributes of each spot are as listed in Table 11. The person threshold indicates the maximum number of tourists in the scenic spot, and the tourist numbers indicate the actual number of tourists.

Table 11.

No. | Scenic spot name | Person threshold | Tourist numbers |
---|---|---|---|

1 | Tongde Hall | 150 | 60 |

2 | Academy of painting and calligraphy | 124 | 150 |

3 | Gungnaebu | 120 | 100 |

4 | Changchunxuan | 150 | 100 |

5 | Zhixiuxuan | 121 | 20 |

6 | Rising floor | 80 | 130 |

7 | Zhonghe gate | 150 | 120 |

8 | Ground floor | 150 | 100 |

9 | Huaiyuan building | 121 | 150 |

Table 12 shows three different path strategies generated by the three algorithms. From the three path strategies, we can see that our algorithm fully considers the tourist threshold factor. The optimal path generated by our algorithm can give tourists a better experience.

Table 12.

Method | Path |
---|---|

Proposed method | Zhonghe gate, Zhixiuxuan, Changchunxuan, Gungnaebu, Huaiyuan building, Academy of painting and calligraphy, Tongde Hall, The ground floor, Rising floor |

MGPP | Rising floor, Zhonghe gate, Tongde Hall, Academy of painting and calligraphy, Huaiyuan building, Gungnaebu, Changchunxuan, Ground floor, Zhixiuxuan |

HA | Rising floor, Zhonghe gate, Tongde Hall, Academy of painting and calligraphy, Huaiyuan building, Gungnaebu, Changchunxuan, Ground floor, Zhixiuxuan |

The order of visitation of scenic spots is one of the most important factors in the evaluation of a tourism plan. To improve the experience of a particular tour, optimal path planning should be carried out. In this paper, we propose a path strategy optimization algorithm based on game theory combined with the Monte Carlo path evaluation method. The proposed algorithm was developed in two phases. The Monte Carlo method evaluates the path weight as the selection index for path selection during phase I. In the proposed scheme, game theory chooses the optimal path, and the Nash equilibrium is obtained according to the path weight generated by the Monte Carlo evaluation algorithm during phase II. During the process of choosing the path, the model fully considers the attributes of the scenic spots to ensure the best viewing effect. To verify the proposed algorithm, we demonstrated its capability as follows:

In the first set, to verify the proposed method, the algorithm calculates all scenic spots at the pseudo Imperial Palace according to the 12 months of the year and their different weather patterns.

In the second set, to illustrate the influence of climate on the recommended path, a custom list of scenic spots within the experimental environment was tested.

In the third set, to demonstrate the advantage of the proposed method, the performance of the path recommendation model based on the presented algorithm was compared with two conventional approaches from a single scenic spot in an experimental environment.

In the fourth set, to verify the impact of the crowd density on the recommended path, we selected the scenic spots defined for scenario 2 to generate the recommended viewing path strategy under different crowd densities.

The results from these four comparative experiments can be expressed as follows:

In the experiment conducted on the first and second sets, indoor and outdoor scenes affect the recommended path length and travel time during different seasons and under differing climates. The proposed model introduces the influencing factors during the process of generating a recommendation strategy as compared to the other methods.

In the third set of experiments, the order of viewing points was used to test the effect of the influencing factors in a single building. The experiment results show that the proposed method is more efficient for optimal path planning.

In the fourth set of experiments, the sequence of path strategy nodes generated by the three comparative methods shows that the proposed method takes the population density factor more fully into account.

When the tourist density exceeds the threshold, the proposed algorithm can effectively improve the efficiency of the path planning and reduce the time consumption.

This paper is funded by talent introduction scientific research project of Changchun Normal University (No. RC2016009), Natural Science Foundation of Changchun Normal University (No. 2018007), science and technology development project of Jinlin Province (No. 20180201086SF), Education Department of Jilin Province (No. JJKH20181181KJ, JJKH20190499KJ, and JJKH20181165KJ), Research Projects of Jilin Development and Reform Commission (No. 2019C039-1).

He was born in 1984. He received the B.E., M.S., and D.S. degree in Computer Science and Technology from Jilin University, China, in 2007, 2009, and 2016, respectively. He is a lecturer at the Department of Computer Science and Technology, Changchun Norm University, China. His research interest include digital image processing and virtual reality technique. And his research interests include computer algorithms and simulation, evacuation planning, image processing and 3D modelling.

He was born in 1980. He received the B.E. and M.S. degree in Computational Mathe-matics from Jilin University, China, in 2003 and 2006, respectively. He is a professor at the Department of Computer Science and Technology, Changchun Norm University, China. His research interest include digital image processing and machine vision technique. And his research interests include image measurement, camera calibration, image processing and 3D modelling.

He was born in 1989. He is a communication engineer, specializing in information communication and network. His research interest include digital image processing and machine vision technique. And his research interests include image measurement, camera calibration, image processing and 3D modelling.

- 1 K. Hernandez, B. Bacca, B. Posso, "Multi-goal path planning autonomous system for picking up and delivery tasks in mobile robotics,"
*IEEE Latin America Transactions*, vol. 15, no. 2, pp. 232-238, 2017.custom:[[[-]]] - 2 L. Wang, "A two-stage stochastic programming framework for evacuation planning in disaster responses,"
*Computers & Industrial Engineering*, vol. 145, no. 106458, 2020.doi:[[[10.1016/j.cie..106458]]] - 3 Y. Zheng, X. G. Li, B. Jia, R. Jiang, "Simulation of pedestrians’ evacuation dynamics with underground flood spreading based on cellular automaton,"
*Simulation Modelling Practice and Theory*, vol. 94, pp. 149-161, 2019.custom:[[[-]]] - 4 A. Pandey, D. R. Parhi, "MA TLAB simulation for mobile robot navigation with hurdles in cluttered environment using minimum rule based fuzzy logic controller,"
*Procedia Technology*, vol. 14, pp. 28-34, 2014.custom:[[[-]]] - 5 X. Zheng, Y. Cheng, "Conflict game in evacuation process: a study combining cellular automata model,"
*Physica A: Statistical Mechanics and its Applications*, vol. 390, no. 6, pp. 1042-1050, 2011.custom:[[[-]]] - 6 J. Tanimoto, A. Hagishima, Y. Tanaka, "Study of bottleneck effect at an emergency evacuation exit using cellular automata model, mean field approximation analysis, and game theory,"
*Physica A: Statistical Mechanics and its Applications*, vol. 389, no. 24, pp. 5611-5618, 2010.custom:[[[-]]] - 7 D. M. Shi, B. H. Wang, "Evacuation of pedestrians from a single room by using snowdrift game theories,"
*Physical Review E*, vol. 87, no. 2, 2013.doi:[[[10.1103/PhysRevE.87.022802]]] - 8 J. Guan, K. Wang, "Towards pedestrian room evacuation with a spatial game,"
*Applied Mathematics and Computation*, vol. 347, pp. 492-501, 2019.custom:[[[-]]] - 9 M. Mavronicolas, M. Papadoupoulou,
*Algorithmic Game Theory*, Germany: Springer, Heidelberg, 2009.custom:[[[-]]] - 10 G. M. Hua, "Tourism route design and optimization based on heuristic algorithm," in
*Proceedings of 2016 8th International Conference on Measuring Technology and Mechatronics Automation (ICMTMA)*, Macau, China, 2016;pp. 449-452. custom:[[[-]]] - 11 J. Lee, M. P. Kwan, "A combinatorial data model for representing topological relations among 3D geographical features in micro-spatial environments,"
*International Journal of Geographical Information Science*, vol. 19, no. 10, pp. 1039-1056, 2005.doi:[[[10.1080/13658810500399043]]] - 12 Z. Liu, P. Huang, Y. Xu, C. Guo, J. Li, "The quantitative risk assessment of domino effect caused by heat radiation," in
*Proceedings of 2010 5th International Conference on Systems*, Menuires, France, 2010;pp. 120-124. custom:[[[-]]] - 13 D. G. Milledge, S. N. Lane, A. L. Heathwaite, S. M. Reaney, "A Monte Carlo approach to the inverse problem of diffuse pollution risk in agricultural catchments,"
*Science of the Total Environment*, vol. 433, pp. 434-449, 2012.custom:[[[-]]] - 14 Q. Meng, X. Qu, K. T. Yong, Y. H. Wong, "QRA model-based risk impact analysis of traffic flow in urban road tunnels,"
*Risk Analysis: An International Journal*, vol. 31, no. 12, pp. 1872-1882, 2011.doi:[[[10.1111/j.1539-6924.2011.01624.x]]] - 15 Q. Wang, D. M. Kilgour, K. W. Hipel, "Fuzzy real options for risky project evaluation using least squares Monte-Carlo simulation,"
*IEEE Systems Journal*, vol. 5, no. 3, pp. 385-395, 2011.doi:[[[10.1109/JSYST.2011.2158687]]]