多车次同时送取货物车辆路径问题的量子蚁群算法

摘要

研究了配送车辆载重量和工作时间有限,考虑货物装卸时间的多车次同时送货和取货的车辆路径问题(multi-trip vehicle routing problem with simultaneous deliveries and pickups,MTVRPSDP),建立了以配送车辆启动成本和车辆行驶成本之和最小为目标的线性整数规划模型.将量子计算和基本蚁群算法相结合提出了求解MTVRPSDP的量子蚁群算法,该算法应用量子比特启发式因子改进了人工蚂蚁的转移概率,从而提高了算法的全局搜索能力和稳定性,有效改进了算法陷入局部最优的缺陷.算例分析表明:MTVRPSDP的线性整数规划模型在实际应用中是可行和有效的,而且相比于基本蚁群算法和文献中所给其他算法的计算结果,利用量子蚁群算法和MTVRPSDP的线性整数规划模型能够得到较好的满意解,安排的车辆配送路线更加经济合理.%The multi-trip vehicle routing problem with simultaneous deliveries and pickups (MTVRPSDP) was studied in consideration of the loading and discharging time,maximum vehicle transport time and load capacity.A linear integer programming model for the MTVRPSDP was formulated,in which the objective function was to minimize the total distribution costs including vehicle costs and transportation costs.A quantum-inspired ant colony optimization (QACO)algorithm for solving the MTVRPSDP was proposed by combining the quantum computing and basic ant colony optimization (ACO).Owing that the transition probability of artificial ants was improved by using the heuristic factor of quantum bits in the QACO,the global search ability and stability of the algorithm have a better improvement,and its disadvantage of getting into the local optimum is also effectively weakened.The numerical results show that the linear integer programming model for the MTVRPSDP is feasible and effective in real application.The solutions obtained by using the basic ACO,QACO and other state-of-art algorithms presented in literatures were compared,and the conclusion shows that the distribution routes,obtained by using the QACO to solve the linear integer programming model for MTVRPSDP,are better in terms of economic efficiency and reasonability.