混合量子算法在车辆路径问题中应用的研究

物流业已发展成为当代国民经济的重要基础产业之一,而运输成本占物流成本比例过大的现状制约物流业的发展。对作为运输系统关键环节的车辆路径问题(Vehicle Routing Problem,VRP)的研究不再被局限于公路、铁路等陆路交通,还被扩展至航空、水运以及报品送递、班车路线优化等多行业,因此研究如何有效解决VRP具有重要的现实意义和实用价值。 本文对带时间窗车辆路径问题(Vehicle Routing Problem with Time Windows,VRPTW)、不确定需求车辆路径问题(Uncertain Information Vehicle Routing Problem, UIVRP)和有同时集送货需求车辆路径问题(Vehicle Routing Problem with Pickup Delivery, VRPPD)以及现有的解决算法进行了系统研究。 (1)在使用了改进的量子遗传算法和总结了一般量子粒子群算法的基础上,根据优化变量的特征,将量子粒子群分成几个子相粒子群,提出了混合量子粒子群优化算法解决VRPTW.仿真计算结果表明这种算法具有使用更少的参数,运算更简单,在较短时间内能够快速收敛得到全局最优解的优点,而且所提的算法提高了在高维搜索空间的收敛可靠性以及收敛速度。 (2)建立了UIVRP的数学规划模型和目标函数,根据其约束条件的限制提出了将模拟退火算法与量子算法相结合的混合量子优化算法求解UIVRP。仿真分析结果表明所提方法提高了收敛速度和收敛可靠性,是一种解决UIVRP的有效方法。 (3)在深入研究禁忌搜索算法在求解此类问题优势和局限性的基础上,设计了结合精英量子均值和混沌扰动理论的量子进化算法求解VRPPD。算法中引入Lyapunov指数、关联维数和功率谱等混沌运动判断标准,并完成对旋转门旋转角的改进。