主管：中国科学院
主办：中国优选法统筹法与经济数学研究会
　　　中国科学院科技战略咨询研究院
中国管理科学

中国管理科学 ›› 2023, Vol. 31 ›› Issue (3): 124-132.doi: 10.16381/j.cnki.issn1003-207x.2022.0383

• 论文 • 上一篇    下一篇

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

刘昕睿1, 雒兴刚1, 姬朋立2, 张忠良1   

  1. 1.杭州电子科技大学数据科学与智能决策实验中心,浙江 杭州310018;2.浙江省人民政府之江实验室,浙江 杭州311100
  • 收稿日期:2020-02-27 修回日期:2022-08-10 出版日期:2023-03-20 发布日期:2023-04-03
  • 通讯作者: 雒兴刚(1971-)，男(汉族)，新疆奇台人，杭州电子科技大学管理学院，教授，研究方向：产品/服务开发、运营管理、质量管理等，Email：xgluo@mail.neu.edu.cn. E-mail:xgluo@mail.neu.edu.cn
  • 基金资助:
    国家自然科学基金资助重点项目(71831006); 国家自然科学基金资助青年项目(72101068)

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

LIU Xin-rui1, LUO Xing-gang1, JI Peng-li2, Zhang Zhong-liang1   

  1. 1. Experimental Center of Data Science and Intelligent Decision, Hangzhou Dianzi University, Hangzhou 310018, China;2. The People’s Government of Zhejiang Province, Zhejiang Lab, Hangzhou 311100, China
  • Received:2020-02-27 Revised:2022-08-10 Online:2023-03-20 Published:2023-04-03
  • Contact: 雒兴刚 E-mail:xgluo@mail.neu.edu.cn

PDF (PC)

987

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

关键词: 动态规划；行程规划；定性问题；分支定界；邻域搜索

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

中图分类号: