基于实时信息的游客行程动态规划研究

Research on Dynamic Planning of Visitor Itineraries based on Real-time Information

基于实时信息的游客行程动态规划问题可适用于城市景点的游客行程规划、主题公园的游客行程规划、博物馆的游客游览路线规划等服务系统的实际场景。本文采用重规划方法将该问题转化为离散时间段上的静态规划子问题,建立了对应的混合线性整数规划模型,并证明了该问题的NP难性质。提出了一种分支定界算法来求解静态子问题的优化模型,并设计了一种变邻域搜索算法来求解对应的大规模问题。通过数值实验验证了所提的模型和算法,并进行了算法参数标定和算法比较分析。数值实验的结果表明,所提分支定界算法和变邻域搜索算法的计算性能都明显优于已有文献的算法。所提的模型和算法可以嵌入到管理信息系统中,对于提升服务系统的工作效率、降低顾客的等待时间、优化服务系统的资源配置等具有实际意义。

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.