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

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