论文部分内容阅读
车辆路径问题(VRP)是近年来交通运输、管理科学、运筹学、图论、网络分析等学科研究的热点问题之一,在现实中有着广泛的应用,例如公交线路、物流配送、网络路由等等。研究此类问题具有很强的现实意义。本文着重研究带时间窗的车辆路径问题(VRPTW)。VRPTW是在基本VRP上添加时间窗约束条件后的一种变化形式,是更为复杂和特殊的问题。VRPTW已被证明是NP-hard组合优化问题,当问题规模较大时,很难得到问题的精确解。如何设计有效的算法,从而在较短的计算时间快速获得较好的解,成为现阶段研究的重点。
蚁群算法是受自然界中蚂蚁觅食行为的启发而发展起来的一种元启发式优化算法,是一种本质并行的算法,全局搜索能力强。蚂蚁之间通过信息交流加速了进化过程,利用了正反馈原理和学习机制,具有较强的搜索较优解的能力。在基本蚁群算法的基础上,又逐渐发展出来许多新的改进算法,并在二次分配(QAP)、网络路由、车间调度(JSP)、车辆路径(VRP)等组合优化问题的求解中取得了很好的效果。
本文基于蚁群算法对VRPTW问题进行系统研究。主要工作如下:
首先,介绍VRP问题的各种约束条件和分类标准。分析VRPTW问题的特性以及构造VRPTW问题的模型时须考虑的各种因素如目标函数、约束条件、变量等等,给出VRPTW问题的数学模型。对求解VRPTW问题的精确算法、传统启发式算法和元启发式算法进行介绍。接下来介绍蚁群算法的基本原理、发展变化以及在VRP领域的应用。
然后,基于对VRPTW问题的研究,结合物流配送中的实际情况,提出车辆可重复利用的VRPTW问题(VRPTWRV),建立相应的多目标数学规划模型。并在蚁群系统(Ant ColonySystem)的基础上,按照优先访问服务开始时间较早、服务所需时间较短以及关窗时间较早的客户的原则,设计相应的启发式因子和蚂蚁的状态转移规则;结合最大最小蚂蚁系统(MMAS)、基于排序的蚂蚁系统(ASRank)的优点,并引入自适应机制,动态调整信息素的挥发系数,设计相应的信息素更新策略,既加强对每次迭代最优解的利用,又避免过早陷入局优,从而兼顾算法的收敛速度和全局性。根据客户服务结束时间较早优先的原则构造较好的初始解。使用候选表来加快搜索速度。在算法中加入局部搜索阶段,在所有蚂蚁都构造完解之后信息素全局更新之前,使用在求解VRPTW问题上非常有效的几种局部搜索方法如2-opt*、or-opt、CROSS-exchange等,并在or-opt中结合GENI-exchange算子的思想,来对蚂蚁构造的解进行改进,将元启发式算法和局部搜索方法的优点结合起来,设计出求解VRPTWRV问题的混合蚁群算法(HACO-VRPTWRV)。最后,进行大量的数据仿真实验。研究在不同的参数组合下HACO-VRPTWRV算法性能的变化,确定较好的参数组合和取值范围。比较不同的初始解生成策略对算法性能的影响。研究解的多样性。对比加入局部搜索过程前后算法的收敛速度和求得的解的质量,以及车辆可重复利用和不可重复利用下使用的车辆数和总运行时间、等待时间、行驶时间等等。实验结果表明,本文所设计的算法是有效的,具有较快的收敛速度,解的全局性也较好。