Research On Tourism Itinerary Planning Considering The Service Capacity Of POI

Tourism has become one of the fastest growing pillar industries in China’s service industry.However,many attractions are seriously congested,which not only increases the difficulty of on-site management and security risks,but also affects tourist satisfaction and experience.There are many reasons for the problem of tourism congestion,one of the important reasons is that the intelligent management means of scenic spots still need to be improved and there is a lack of scientific methods to formulate scientific tourism itinerary planning for tourists.In view of the realistic problem scenario in the tourism industry,in order to provide tourists with a reasonable itinerary planning scheme from the perspective of the service system,this paper studies the tourism itinerary planning problem considering the service capacity of scenic spots.This problem has been abstracted into Multi Agent Orienteering Problem with Capacity Constraints(MAOPCC)by literature.The application of MAOPCC in the real world includes the itinerary planning of tourist attractions,the itinerary planning of attractions in theme parks,and the route planning of museums.The main research work of this paper is summarized as follows:(1)For the Multi Agent Orienteering Problem with Capacity Constraints(MAOPCC),by considering the single tourist path constraints and capacity occupancy constraints among different tourists in the tourist path planning,the corresponding linear integer programming model is established for the first time,and its NP Hard characteristics are proved.Compared with the nonlinear model of the problem in the existing literature,the linear model established in this paper has obvious advantages.It can be solved directly by using mature business planning solvers(such as ILOG CPLEX),and is conducive to the development of accurate algorithms.(2)Based on the proposed linear integer programming model,a branch and bound algorithm is designed for small-scale problems.Each scenic spot is used as a branch node to calculate the upper bound of each branch and the cutting process is based on this bound.The acceleration steps are used to speed up the calculation process.For large-scale problems,an intelligent optimization algorithm with variable neighborhood search is proposed,an initialization algorithm based on neighborhood reward is designed to quickly construct the initial solution,and four neighborhood structures are proposed for algorithm optimization.The experimental results of the numerical experiment show that the average improvement rate of the proposed branch and bound algorithm is 83.53% and 30.79%,respectively,compared with the accurate algorithm in the existing literature,indicating that the proposed algorithm has good performance;The variable neighborhood search algorithm designed in this paper is significantly superior to the intelligent optimization algorithm in the existing literature,both in terms of solution quality and computing time.(3)For the first time,the multi customer travel path planning problem with dynamic environment is abstracted as Dynamic Multi Agent Orienteering Problem with Capacity Constraints(DMAOPCC).The problem is transformed into a dynamic subproblem in each time period by using the reoptimization method of dynamic optimization,and the mathematical planning model of the subproblem is established.The proposed branch and bound algorithm and variable neighborhood search algorithm are applied to solve the sub problem model.The experimental results show that the proposed branch and bound algorithm and variable neighborhood search algorithm are also significantly superior to the algorithms in the existing literature for solving DMAOPCC problem.