Research on tourism individualized route management based on intelligent optimization algorithm

Abstract

With the development of China’s economy, living standards of people have been improving day by day, and tourism has become a way for most people to spend their leisure time. In order to make travel more efficient and fun, travel routes need to be properly planned before traveling. There are many intelligent algorithms that can be used to optimize the routes. The Benchmark27, Att48 and kroA100 travel simulation problems were solved by the ant colony algorithm and the improved ant colony algorithm on the Matlab simulation platform. The optimal path search capabilities of two kinds of algorithms were compared, and the path diagram was drawn. The results showed that the optimal path and average path length of the improved ant algorithm of the improved ant colony algorithm were smaller than those of the ant colony algorithm in solving the three simulation problems, and moreover the improved ant colony algorithm had higher iterative convergence speed and smaller optimal solution than the ant colony algorithm.

Keywords

The improved ant colony algorithm tourism routes multiple constraint the optimal solution

1. Introduction

With the development of China’s economy, living standards of people have been continuously improve and the way of life has also changed. More and more people prefer the self-help travel in spare time to a specific tour group. For travelers who choose self-help travel, how to choose the location and route of travel according to their own wishes is really a tedious job [5]. Although there are many websites related to tourism at present, most of them only provide information about scenic spots, but do not provide travel advice. Tourists still need to pay attention to plan, and it is more difficult to arrange properly when they do not know much about the destination. The emergence of intelligent optimization algorithms based on computers and smart phones solves this problem well. Intelligent algorithms used to optimize tourism routes include genetic algorithm, neural network algorithm, ant colony algorithm, etc., among which ant colony algorithm is more commonly used [6]. There are some relevant researches in this aspect. Durisman et al. [3] used ant colony optimization algorithm to determine the shortest route of tourism in Banda Aceh city and Aceh Besar regency. Through the analysis made by using both manual calculation and MATLAB program application test, the shortest route with a minimum distance of 120.85 km was obtained in one trip. Mao [4] took “one-day tour” as an example to study the optimization of tourism routes. The objective function of the tourism route optimization problem was improved by ant colony algorithm and principal component analysis. It selected ant line randomly and dynamically set the parameters of heuristic elements, information dispersion coefficient and so on. Finally, it was proved by the MATLAB experiment that the improved ant colony algorithm has greatly improved the performance of route optimization problem of the “one-day tour”. Liu et al. [5] studied the multi-weights (such as weather, route length, attractions landscape, etc.) in route selection, and then proposed an improved ant colony algorithm based on multi-weights (ACA-MW) which used the multi-weights ant and the genetic variation to search optimal routes. Simulated experiment showed that the ACA-MW had high performance, and the improved algorithm can do well in optimal route selection problem. Ding [6] proposed the branching ant colony with dynamic perturbation (DP) algorithm under the electronic commerce environment. The algorithm introduced dynamic disturbance to select cities. Experiments showed that the algorithm can effectively improve the disadvantages of long search time and easy to fall into local minima in basic ant colony algorithm. This method can help tourists choose the tourism route under the environment of e-commerce more effectively. In this study, the Benchmark27, Att48 and kroA100 tourism simulation problems were solved by ant colony algorithm and the improved ant colony algorithm on the Matlab simulation platform. The optimal path search capabilities of two kinds of algorithms were compared, and the path diagram was drawn, so as to explore the suitable algorithm used in the selection of tourist routes. The final results demonstrated that the improved ant colony algorithm could find out more excellent route planning.

2. Tourism route model

Figure 1.

A simple schematic diagram of tourism route planning.

Developing individualized tourism routes based on personal interests, behaviors and travel demands of tourists is called tourism route planning. Figure 1 is a simple schematic diagram of tourism route planning, from which it can be seen that route planning has multiple constraints, including the selection of vehicle, the cost and time of the play stage, time spent on the road, opening hours of scenic spots, etc. In this study, the shortest tourism route was used to evaluate the quality of the planned route, and its mathematical model [7] is:

$\displaystyle\text{decision variable: }y_{ij}=\left\{{{\begin{array}[]{ll}1&(i% ,j)\text{ on a certain route}\\ 0&\text{otherwise}\\ \end{array}}}\right.,$ (1) $\displaystyle\text{objective function: }\min Y=\sum\limits_{i=1}^{n}\sum% \limits_{i=0}^{m-1}l_{ij}y_{ij},$ (2) $\displaystyle\text{constraint condition: }\sum_{k=0}^{m-1}y_{kj}=\left\{{{% \begin{array}[]{ll}1&j\in\{1,2,\ldots,m-1\}\\ n&j=1\\ \end{array}}}\right.,$ (3) $\displaystyle\sum\limits_{k=0}^{m-1}y_{ik}=\left\{{{\begin{array}[]{ll}1&{j\in% \{{1,2,\ldots,m-1}\}}\\ n&{j=1}\\ \end{array}}}\right.,$ (4) $\displaystyle\sum\limits_{i\in S}^{m-1}\sum\limits_{j\in S}y_{ij}\leqslant m-1% +n,$ (5)

where $Y$ stands for the sum of all travel routes, $y_{ij}$ stands for the variable that determines whether the scenic spot $(i,j)$ is on a certain route, and $l_{ij}$ stands for the distance to $(i,j)$ . Equations (3) and (4) ensure that there is only one route in and out for other scenic spots except the starting point, and there are n routes in and out for the starting point. Equation (5) ensures that there are only $m-1+n$ routes in the entire tourism planning route at most.

3. The improved ant colony algorithm

3.1 Ant colony algorithm

From the above mathematical model, it can be seen that the tourism route planning problem essentially is to find out the shortest route that ensure tourists to visit each scenic spot once. In order to solve this problem, ant colony system model was adopted in this study. Suppose that there were M scenic spots and N ants. The basis for ants to choose the next scenic spot was the transition probability, and its expression [8] is:

$\displaystyle P_{ij}^{r}(u)=\left\{{{\begin{array}[]{ll}{\frac{\omega_{ij}^{% \theta}(u)\eta_{ij}^{\sigma}}{\sum\limits_{j\in M_{j}^{r}}{\omega_{ij}^{\theta% }(u)\eta_{ij}^{\sigma}}}}&{j\notin\textit{tabu}(r)}\\ 0&\text{otherwise}\\ \end{array}}}\right.,$ (6)

where $\omega_{ij}$ stands for the size of pheromone left on the route from scenic spot $i$ to scenic spot $j$ , $\theta$ stands for the importance of pheromone, $\eta_{ij}$ stands for the reciprocal of the route length from scenic spot $i$ to scenic spot $j$ , which is the heuristic factor of the route, $\sigma$ stands for the importance of heuristic factor, $\textit{tabu}(r)$ stands for the tabu table, which is used to store the scenic spots that have been visited, and $P_{ij}^{r}(u)$ stands for the probability that the $r$ -th ant selects scenic spot $j$ at time $t$ in scenic spot $i$ .

3.2 Improvement of ant colony algorithm

3.2.1 Sequence adjustment of scenic spots in tabu table

After “ant” walked through all the scenic spots according to the algorithm, all the scenic spots were added to the tabu table, and then the total distance was calculated according to the tabu table, but the order of the tabu table at this time was not necessarily the shortest order, because the selection probability of the next scenic spot in the algorithm was jointly affected by heuristic factor and pheromone, and the influence of heuristic factor was smaller in the later stage. If the route found at the beginning was not the shortest, then the global optimal solution cannot be found in the later stage because of the influence of the pheromone. In order to solve this problem, the order of the tabu table needs to be adjusted. The adjusted formula [12] is:

$\displaystyle L=\left\{{{\begin{array}[]{ll}{L(i)+L(P(j),P(j+1))}&L(P(i),P(j))% +L(P(j),P(j+1))<\\ &L(P(i),P(j+1))+L(P(j+1),P(j+2))\\ {L(i)+L(P(j+1),P(j+2))}&\text{otherwise}\\ \end{array}}}\right.,$ (7)

where $P$ stands for the tabu table, $L$ stands for the best route for this iteration, $L(i)$ stands for the distance from the starting point to the scenic spot $i$ , and $L(P(i),P(j))$ stands for the distance between the scenic spot $i$ and the scenic spot $j$ in the tabu table.

3.2.2 Improvement of heuristic factors

As mentioned above, the traditional basic ant colony algorithm follows the principle of shortest route when selecting the next node, but when choosing a route more than two steps, the route selected according to the principle is not necessarily the shortest, and the error is constantly accumulated in the iterative process, which leads to the failure of the algorithm to obtain the real optimal solution. In order to solve this problem, this study improved the heuristic factor [11]:

$\displaystyle\eta_{ij}=\frac{1}{l_{i,j}+l_{j,j+1}},$ (8) $\displaystyle j=\left\{{{\begin{array}[]{ll}j&{L(i,j)+L(j,j+1)<L(i,k)+L(k,j+1)% \text{ and }j,k,j+1\notin\textit{tabu}(r)}\\ k&\text{otherwise}\\ \end{array}}}\right.,$ (9)

where $l_{i,j}$ stands for the distance between the scenic spot $i$ and the scenic spot $j$ , $j$ stands for the next scenic spot selected in the scenic spot $i$ , $j+1$ stands for the next scenic spot selected in the scenic spot $j$ , $K$ stands for any scenic spot, and $L()$ stands for the distance between scenic spots.

3.2.3 Pheromone update rules

The updated expression of pheromone [9] is:

$\displaystyle\omega_{ij}(u+m)=\rho\cdot\omega(u)+\sum\limits_{r=1}^{n}\Delta% \omega_{ij}^{r},$ (10)

where $\rho$ stands for the pheromone residual factor, $\rho\in(0,1)$ , and the initial moment is $\Delta\omega_{ij}^{r}=C$ . The later change [10] is:

$\displaystyle\Delta\omega_{ij}^{r}=\left\{{{\begin{array}[]{ll}{\frac{O}{L_{r}% }}&{j\notin\textit{tabu}(r)}\\ 0&\textit{otherwise}\\ \end{array}}}\right.,$ (11)

where $O$ stands for constant, and $L_{r}$ stands for the total distance that ant $r$ has walked in a trip.

Considering that too large pheromone makes the probability of the ant to choose the path larger, too small will cause the ant to ignore the path and easily fall into the local optimal solution, so the threshold value of pheromone was set to avoid the negative effect of too large or too small pheromone on positive feedback.

When the pheromone was updated, the original pheromone and the newly added pheromone in the path should be “volatilized” to avoid excessive increase or decrease. The formula is as follows:

$\displaystyle\omega_{ij}(t+1)=(1-\rho)\omega_{ij}+\rho\Delta\omega_{ij}(t).$ (12)

4. Simulation experiment

4.1 Experimental environment

The experiments in this study were carried out on a laboratory server, which was equipped with Windows7 system, I7 processor, and 16 G memory. Matlab [13] simulation platform was used to write the model algorithm.

4.2 Experimental method

Benchmark27, Att48 and kroA100 problems [14] in TSPLIB was taken as the optimization simulation object of the tourism route, and it was operated using the ant colony algorithm and the improved ant colony algorithm for 10 times respectively. The parameters in the algorithm were: $\theta=$ 1, $\sigma=$ 5, $\rho=$ 0.1, $O=$ 100, and after 250 iterations, the number of ants N was 27. The process of the improved ant colony algorithm [15] is shown in Fig. 2.

4.3 Experimental results

Table 1
The simulation results of three problems

Simulation problem	Ant colony algorithm		The improved ant colony algorithm
	Optimal value	Average value	Optimal value	Average value
Benchmark27	14603	14789	14397	14588
Att48	35703	35448	32115	33299
kroA100	22128	24144	21825	22325

Figure 2.

The process of the improved ant colony algorithm.

The simulation results of Benchmark 27, Att48 and kroA100 problems are shown in Table 1. The optimal path length of Benchmark 27 under the ant colony algorithm was 14603, with an average length of 14798; the optimal path length of Att48 was 35703, with an average length of 35448; and the optimal path length of kroA100 was 22128, with an average length of 24144. Under the improved ant colony algorithm, the optimal path length of Benchmark 27 was 14397, and the average length was 14588; the optimal path length of Att48 was 3215, and the average length was 33299; and the optimal path length of kroA100 was 21825, and the average length was 22325. The comparison of the optimal value and average value between the two algorithms under the same problem suggested that the improved ant colony algorithm was shorter in both the optimal path length and the average length.

Figure 3.

Iterations of the three problems under the two algorithms.

Figure 4.

The optimal route obtained by the ant colony algorithm.

Figure 5.

The optimal route obtained by the improved ant colony algorithm.

As shown in Fig. 3, for the Benchmark 27 problem, the traditional ant colony algorithm achieved the optimal value after 85 iterations, and the improved ant colony algorithm achieved the optimal value after 80 iterations; for the Att48 problem, the traditional ant colony algorithm achieved the optimal value after 80 iterations, and the improved ant colony algorithm achieved the optimal value after 85 iterations; for the kroA100 problem, the traditional ant colony algorithm achieved the optimal value after 87 iterations, and the improved ant colony algorithm achieved the optimal value after 60 iterations. Generally speaking, the improved ant colony algorithm could converge to the optimal value faster. Moreover, it can be seen from Fig. 3 that the optimal value obtained by the improved ant colony algorithm was always smaller and better.

Limited by the length of paper, only the planning of the optimal path of the Benchmark27 problem using the traditional ant colony algorithm and the improved ant colony algorithm was displayed, as shown in Fig. 4.

As shown in Fig. 4, the route distance of the optimal solution to the Benchmark27 problem obtained by the ant colony algorithm was 14603, and the route was 14-7-8-6-10-9-24-11-23-25-22-22-20-19-17-18-27-27-13-3-4-5-2-1-15.

As shown in Fig. 5, the route distance of the optimal solution to the Benchmark27 problem obtained by the improved ant colony algorithm was 14397, and its route was 10-24-23-25-22-22-20-19-19-17-18-16-12-3-4-2-5-6-11-8-7-14-1-15-9.

In conclusion, the improved ant colony algorithm converged faster than the ant colony algorithm in the planning of tourism routes, and the total distance of the optimal solution was the shortest, so the improved ant colony algorithm was more suitable for tourism route management.

5. Conclusion

With the development of social economy, people’s life has gradually become rich, and they begin to have extra time to travel. In order to make their own travel faster and more efficient without losing the fun, tourism route planning before departure is essential. The ant colony algorithm and the improved ant colony algorithm were used to solve tourism simulation problems, Benchmark27, Att48 and kroA100 problems, on the Matlab simulation platform, and the results are as follows:

After 10 operations, the Benchmark 27 problem got an average length of 14798 under the ant colony algorithm and 14588 under the improved ant colony algorithm; the Att48 problem got an average length of 35448 under the improved ant colony algorithm and 33299 under the improved ant colony algorithm; the kroA100 problem got an average length of 24144 under the improved ant colony algorithm and 22325 under the improved ant colony algorithm. By comparing the iteration diagrams of the two algorithms, it was found that the improved ant colony algorithm converged faster than the ant colony algorithm, it converged faster to the optimal solution than the ant colony algorithm in the initial stage of iterations, and its optimal solution was smaller than that of the ant colony algorithm, suggesting a better searching performance.

References

Zhang

Gong

Han

et al., An improved ant colony algorithm for path planning in one scenic area with many spots IEEE Access, (99) (2017), 1–1.

and Zeng

, Ant colony optimization based test case generation method in context-aware applications, Journal of Computational Information Systems 11(10) (2015), 3641–3648.

Durisman

Ramli

and Rusdiana

, Designing application of ant colony system algorithm for the shortest route of Banda Aceh city and Aceh Besar regency tourism by using graphical user interface MATLAB, 17(2) (2017).

Mao

, Study on ant colony optimization algorithm for “one-day tour” traffic line, Cluster Computing (C) (2018), 1–8.

Liu

Y.Z.

H.P.

Huang

et al., A multi-weights ant colony algorithm for solving optimal path in tourism, Advanced Materials Research, 2014, 998–999:789–792.

Ding

, Research on TSP problem in e-commerce tourist based on ant colony algorithm, International Journal of u- and e- Service, Science and Technology, 2014, 7.

Zhao

Pan

and He

, Application of dynamic ant colony algorithm in route planning for UAV, in: Seventh International Conference on Information Science and Technology, 2017, pp. 433–437.

Zhang

X.L.

Chen

Wang

B.J.

et al., Intelligent fault diagnosis of rotating machinery using support vector machine with ant colony algorithm for synchronous feature selection and parameter optimization, Neurocomputing 167(C) (2015), 260–279.

Holzinger

Plass

Holzinger

et al., Towards interactive machine learning (iml): applying ant colony algorithms to solve the traveling salesman problem with the human-in-the-loop approach, in: International Conference on Availability, Reliability, and Security, Springer International Publishing, 2016, pp. 81–95.

10.

Salama

K.M.

and Freitas

A.A.

, Ant colony algorithms for constructing bayesian multi-net classifiers, Intelligent Data Analysis 19(2) (2015).

11.

Liu

C.Y.

Zou

C.M.

and Wu

, A task scheduling algorithm based on genetic algorithm and ant colony optimization in cloud computing, in: International Symposium on Distributed Computing and Applications To Business, Engineering and Science, 2015, pp. 68–72.

12.

Dai

Lou

and Lu

, A task scheduling algorithm based on genetic algorithm and ant colony optimization algorithm with Multi-QoS constraints in cloud computing, in: International Conference on Intelligent Human-Machine Systems and Cybernetics, 2015, pp. 428–431.

13.

Saini

and Anand

, A multi-objective ant colony system algorithm for virtual machine placement, International Journal of Engineering Research & Applications 7(1) (2017), 95–97.

14.

Chen

Cheng

and Wise

, Designing daily patrol routes for policing based on ANT colony algorithm, 2015, II-4/W2:103-109.

15.

Otero

F.E.B.