Abstract: The problem of dynamic planning of visitor itineraries based on real-time information is fit for actual scenarios of service systems such as tourist itinerary planning of urban attractions, tourist itinerary planning of theme park attractions, and tourist route planning of museums. In this paper, the re-planning method is used to transform the problem into a number of static programming sub-problems in discrete time segments. The corresponding mixed integer linear programming model is established and the NP-hard property of the problem is proved. A branch-and-bound algorithm is proposed to solve the optimization model of a static sub-problem, and a variable neighborhood search algorithm is designed to solve the corresponding large-scale problem. The proposed mathematical model and algorithms are verified by numerical experiments and the parameter calibration of the algorithms and algorithm comparison analysis are carried out. The results of numerical experiments show that the computational performance of the proposed branch-and-bound algorithm and the variable neighborhood search algorithm are better than those of the existing literature. The proposed model and algorithms can be embedded in the management information systems, which have practical significance for improving the work efficiency of the service system, reducing the waiting time of customers, and optimizing the resource allocation of the service system.

Key words: dynamic planning; itinerary planning; orienteering problem; branch & bound; neighborhood search