带时间窗的联盟运输调度问题蚁群算法研究

摘要

联盟运输调度问题(AlliedVehicleRoutingProblem，AVRP)研究的是物流联盟架构下的运输调度最优化。本论文针对几种不同模型的AVRP，分别进行了建模、蚁群算法设计和仿真计算，同时研究了AVRP的并行蚁群算法。所作的主要工作如下： 第一，针对车辆类型相同带时间窗的AVRP，提出了改进的蚁群算法。该算法提出了一种近似解可行化策略，整合了可行解分支的三种类型，并对遗漏客户点做了归属处理，克服了基本蚁群算法在AVRP模型下可能得到非可行解的问题。 第二，针对车辆类型不同带时间窗的AVRP，提出了改进的蚁群算法。该算法首先将选择策略按经验分为三个阶段，在不同的阶段选用相应的转移概率；然后根据信息素浓度与挥发速度的关系自适应调整了信息素挥发因子，较好地克服了基本蚁群算法易陷入局部最优、收敛速度慢的缺点。 第三，针对多车场带时间窗的AVRP，提出了一种结合sweep算法和saving算法将多车场问题化为单车场问题的方法，即通过计算每个客户离车场最近距离与离车场次近距离的比值并按大小排序确定初始分派，继而根据计算节约值确定最终分派，从而便于蚁群算法求解。 第四，提出了AVRP的并行蚁群算法。通过对蚁群算法的算法机理分析，构造了一种基于粗粒度模型的主从式并行蚁群算法，分别为服务器和处理机安排了相应的任务，设计了服务器和处理机各自的算法流程，较好地克服了大规模AVRP难收敛的问题。 最后，对论文进行了总结，对下一步要进行的工作提出了自己的设想。

目录

文摘

英文文摘

第一章绪论

第二章车辆类型相同带时间窗的联盟运输调度问题

第三章车辆类型不同带时间窗的联盟运输调度问题

第四章多车场带时间窗的联盟运输调度问题

第五章联盟运输调度问题的并行蚁群算法

论文总结与展望

参考文献

攻读学位期间发表的论文

攻读学位期间参加的课题

致谢