论文部分内容阅读
配送车辆路径优化,是物流系统优化中关键的一环。对配送车辆路线进行优化,可以提高经济效益、实现物流科学化。对配送车辆线路优化的理论与方法进行系统研究是物流集约化发展、构建综合物流系统、建立现代调度指挥系统、发展智能交通运输系统和开展电子商务的基础。蚁群算法是受自然界中真实蚁群觅食行为的启发而提出的一种模拟进化算法,在求解VRP(Vehicle Routing Problem,车辆路径优化)等组合优化问题上取得了很好的效果。本文研究的主要目的,就在于改进已有的蚁群算法,使之适合不同类型的车辆路径优化问题,得到质量更好的解。本文主要完成以下几方面的工作:第一,详细介绍了物流系统中车辆路径优化问题,对VRP问题进行了分类,并说明了各自的涵义、限制条件及应用范围,在吸取现有研究成果的基础上,对有容量限制的车辆路径优化问题(Capacitated Vehicle Routing Problem, CVRP)进行建模,并阐述了用于解决VRP问题的各种优化方法。第二,深入讨论了蚁群算法的基本原理,建立了数学模型,包括转移概率的计算、信息素更新的各种规则、参数的取值范围等。并从解的质量、时间/空间复杂度、实现难度、算法的优点及不足之处等各项指标对蚁群算法进行全面的分析,并以TSP(Travelling Saler Problem,旅行商问题)为例,介绍了蚁群算法在路径优化问题领域的应用。第三,针对有容量限制的车辆路径优化问题CVRP,改进基本蚁群算法,采用确定性选择和随机选择相结合的选择策略,以及基于吸引力的信息素更新规则,大蚂蚁数策略、蚂蚁初始分布均匀策略、近似解可行化策略得到CVRP问题的可行解。第四,针对带时间窗的车辆路径优化问题(VRP with Time Windows, VRPTW),建立其数学模型,并对已有蚂蚁算法加以改进,包括新的路径构造选择策略、信息素局部更新、基于2-opt法的局部优化、信息素全局更新等因素,利用近似解可行化策略,整合了可行解分支的三种类型,并对遗漏客户点做了归属处理,克服了基本蚁群算法在VRPTW模型下可能得到非可行解的问题。