Route Optimization Algorithm Based on Game Theory for Tourism Routes at Pseudo-Imperial Palace

1. Introduction

An optimization algorithm for determining a scenic tour path aims to ensure that tourists visit each scenic spot using the shortest route and the best time to obtain the most enjoyable experience [1-4]. With an improvement in living conditions, an increasing number of people are choosing to spend their time traveling. The path finding address optimization problem has become extremely popular in the area of tourist planning, which aims to minimize the cost (time, distance, and money) and ensure the best experience. The shortest path problem can be solved using the Dijkstra, Bellman, Floyd, and SPFA algorithms.

In particular, some factors affect the experience of tourists, including the tourist density, viewing time, viewing season, playing time, and journey length. Among them, the population density of scenic spots is an important factor and has attracted the attention of researchers. Many studies have introduced a crowding phenomenon to study the routing optimization problem in a game-theoretic framework. To study the characteristics of crowd movement, Zheng et al. [5] proposed a crowd evacuation model based on a game theory model with crowd cooperation and competition behavior. Tanimoto et al. [6] proposed the Saint and Temptation reciprocity game to analyze a bottleneck in crowd movement. Some scholars [7,8] have also used the game theory model to study crowd movement in complex scenes with multiple exits. During the past decade, the game theory model [9,10] has been used to solve conflict events, and thus it has been widely used in the problem of multi-path selection.

In most travel path optimization algorithms, the dynamic path plan is modeled with respect to the crowd density, time, season, and other factors. In this study, we propose a path strategy optimization algorithm based on game theory combined with the Monte Carlo path evaluation method. The proposed algorithm was developed through two phases. In phase I, the Monte Carlo method is used to evaluate the path weight as the selection index for path selection. In phase II of the proposed scheme, the optimal path is chosen based on game theory, and the Nash equilibrium is obtained according to the path weight generated by the Monte Carlo evaluation algorithm. During the process of choosing the path, the model fully considers the attributes of scenic spots to ensure the best viewing effect. Based on the experiment data from the Puppet Imperial Palace in Changchun, the proposed method can reduce the travel time and degree of congestion.

2. Scene Node Relationship Structure Model

Scenic spots at the Puppet Imperial Palace include 12 palaces, nine guard barracks, two gardens, and a racecourse. Each palace is a multilayer construction that was used for different needs of the emperor. To represent the structure of a scenic spot, we propose a semantic-based scenic modeling method to construct its network structure. The proposed semantic modeling method can find the shortest path between any two scenic spots in the pseudo palace and improve the search efficiency of the shortest path. Each floor of the palace contains many rooms. Each room contains numerous photographs, ornaments, and articles with historical significance. In the process of creating the tour routes, we should fully consider these factors and ensure that the tourists can enjoy all content available.

Lee and Kwan [11] proposed a node relation structure (NRS) to represent the internal structure of a building. To represent the structure of a scene, the model constructs the scene as a graph based on the relationship between the nodes and edges. However, during the process of building a diagram, the fine-grained structure of a building cannot be effectively represented. The model cannot describe the details of the viewing locations in a scenic area.

To solve this problem, we improve the NRS model by adding fine-grained nodes in a hierarchical undirected graph G = (V, E) to fully represent any detailed structure in the scene. The graph includes nodes V and E. A hypergraph can be divided into four types: courtyards, palaces, floors, and rooms. The hypergraph of a courtyard contains nodes such as palaces, roads, bridges, barracks, and gates. The super-map of the palace includes the basement and floor. The hypergraph of the floor consists of rooms, stairs, doors, viewing points, and corridors. The hypergraph of the room includes nodes indicating the layout and ornamental objects in the room. The scene is divided into regions and subgraphs with different intensities according to the scope. The model connects all subgraphs together to form a complete scenic spot map through a hypergraph. This building has two levels of graphs (Fig. 1).

As shown in Fig. 1, the left side of the graph is a two-dimensional plane structure, the right side of the graph is the network topology constructed using the NRS model, and the bottom of the graph is a subgraph of node P5. The building has two floors. Each floor forms a sub-drawing, i.e., F1 and F2, respectively. Between F1 and F2 is a staircase connecting the two floors. Each room and corridor constitute the nodes in each sub-diagram, and the two spaces can be interconnected by edge connections. To effectively express the distance between the two nodes, the corridor node is extended to generate an extension node between each room. In this way, the exact path length can be obtained by determining the shortest path. For example, corridor node P8 is expanded to P81, P82, P83, P84, P85, and P86. The next level of the floor is the room sub-drawing, and the nodes in the room sub-drawing are the objects placed in the room, as shown in the blue node in the figure. Similarly, the space inside the room is transformed into a graph structure.

The relationships are as follows:

G = (N, E),

N = {F1, F2, E8},

F1 = (N, E), N = {P1…P86, E1…E8, S1}, and

P5 = (N, E), N= {C1, C2, R1, R2, R3, B1},

where G is a super-graph set, F is a subgraph of the floor, N is a node set indicating an enclosure, E is an edge set representing the corridor, and S indicates the stairs. In the subgraph of P5, the cabinet (R1, R2) and bed (R3) are formed into nodes (C1, C2, B1), and extended nodes R1, R2, and R3 are generated by our algorithm to form an undirected graph.

3. Quantitative Recommendation Score Assessment

The Monte Carlo method [12-15] is often used for a quantitative risk assessment. According to previous data, it can predict the future data trend or the maximum possible value through a simulation. We propose a Monte Carlo method for a quantitative recommendation score assessment to estimate the score indices for the routes. The Monte Carlo method requires 500 simulation runs during the evaluation process, and therefore too many factors will lead to the consumption of resources and prolong the operation time. We choose the most important factor, i.e., the population density, to express the congestion factor and reduce the computing time. The factors consist of two principal events: the congestion degree dt of the tourist route, and the average congestion degree dl of the ornamental location.

Here,

where [TeX:] $$\text { count }_{i}$$ is the number of people on the tourist route, and [TeX:] $$\text { count }_{c r}$$ is the best number of people for viewing the scenery. In addition, [TeX:] $$d l=\text { countj } / \text { count }_{c l}, \text { count }_{j}$$ is the number of visitors of the scenic spot. Here, [TeX:] $$\text { count }_{c l}$$ is the maximum threshold for the best number of tourists. As a random variable, the crowd density obeys a triangular distribution with the Monte Carlo model.

The recommendation score of the scenic spot estimates the weight based on the scenic attributes. The attributes of the scenic spot mainly include the best viewing time interval, best viewing season, recom¬mended viewing time, precursor spot, succeeding spot, and maximum number of persons accommodated by the best viewing effect at the spot.

There are three extremums in the triangular distribution, i.e., the maximum, minimum, and highest number possible (Table 1). The Monte Carlo algorithm randomly applies 500 simulation results accor¬ding to the three extremums, and then obtains the average value according to the simulation results to obtain the evaluation value by removing the contingency. Here, O is the minimum, P is the maximum, and M is the maximum number possible.

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.

4. Route Optimization Based on Game Theory

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.

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.

5. Performance Analysis

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.

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.

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.

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.

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.

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 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.

6. Conclusion

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.

Acknowledgement

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).