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

来源：上海理工大学学报杂志2017年第6期北京时间：

作者：张惠珍

单位：上海理工大学 管理学院, 上海 200093,国网上海市电力公司物资公司, 上海 200002

摘要：研究了配送车辆载重量和工作时间有限，考虑货物装卸时间的多车次同时送货和取货的车辆路径问题（multi-trip vehicle routing problem with simultaneous deliveries and pickups，MTVRPSDP），建立了以配送车辆启动成本和车辆行驶成本之和最小为目标的线性整数规划模型.将量子计算和基本蚁群算法相结合提出了求解MTVRPSDP的量子蚁群算法，该算法应用量子比特启发式因子改进了人工蚂蚁的转移概率，从而提高了算法的全局搜索能力和稳定性，有效改进了算法陷入局部最优的缺陷.算例分析表明：MTVRPSDP的线性整数规划模型在实际应用中是可行和有效的，而且相比于基本蚁群算法和文献中所给其他算法的计算结果，利用量子蚁群算法和MTVRPSDP的线性整数规划模型能够得到较好的满意解，安排的车辆配送路线更加经济合理.

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

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