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

Quantum-Inspired Ant Colony Algorithm for the Multi-Trip Vehicle Routing Problem with Simultaneous Deliveries and Pickups

作　　者：张惠珍[1] 赵玉苹 ZHANG Huizhen;ZHAO Yuping(Business School,University of Shanghai for Science and Technology,Shanghai 200093,China;State Grid Shanghai Procurement Company,Shanghai 200002,China)

机构地区：[1]上海理工大学管理学院,上海200093 [2]国网上海市电力公司物资公司,上海200002

出　　处：《上海理工大学学报》2017年第6期563-570,共8页Journal of University of Shanghai For Science and Technology

基　　金：国家自然科学基金资助项目(71401106);上海市教育委员会科研创新项目(14YZ090);教育部人文社科规划基金资助项目(16YJA630037)

摘　　要：研究了配送车辆载重量和工作时间有限,考虑货物装卸时间的多车次同时送货和取货的车辆路径问题(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.

关 键 词：车辆路径问题 同时送取 多车次 蚁群算法 量子计算 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]