带时间窗和货物权重的车辆路径问题的研究

　车辆路径问题(vehicle routing problem,VRP)最早是由Dantzig和Ramser于1959年首次提出的,在公路交通运输、水运、航空和通讯等领域有着广泛的应用.遗传算法(genetic algorithm)是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型,是一种通过模拟自然进化过程搜索最优解的方法,它是由美国Michigan大学J.Holland教授于1975年首先提出来的,J.Holland教授所提出的GA通常为简单遗传算法(SGA).有时间窗并且带货物权重的车辆路径问题(vehicle routing problem withtime window and weight,VRPTWW)是在基本VRP中对每个客户的开始服务时间范围和车辆容量加以约束,与实际情况更加吻合,因此有很强的实用背景.

　目前对该问题的研究主要集中在各种启发式算法上,其中遗传算法是研究得较多的一种方法.目前,国内外对VRPTW的研究多以针对带时间窗或带货物权重来求解,而对两者进行综合的问题涉及较少.本文采用遗传算法,对不确定车辆数的有时间窗和带货物权重车辆路径问题的求解进行研究,通过引入CX交叉算子,提出了一种改进路径划分算法,使遗传算法在VRPTWW问题的计算过程中能自动寻找满足要求的最少费用的路径划分,能有效克服遗传算法的“早熟性收敛”,得到的优化结果也更接近最优解.

　1　问题的描述及模型建立

　1·1　问题描述及假设

　给定一个配送中心,拥有不确定数量的具有相同容量的车辆,车辆从配送中心出发对具有确定数量的客户集进行服务,完成服务后开回配送中心.每个客户具有确定的位置,车辆在配送中心装好客户需要的货物,在客户允许的时间窗口内将客户需要的货物送达,求:如何安排分销路线和车辆,使整个分销过程的费用最小.

　为了表达方便,我们建立如下的符号体系:E为客户集合,客户数量为n=E;O为配送中心;OE=E∪{O};配送中心与零售商两两之间的距离记为di,j(i,j的取值从0到n). qj为客户j的需求量,j=1,2,…,n. k为配送中心需求的车辆数目;[ai,bi]为客户i的时间窗口,这个时间窗口说明车辆必须在bi之前达到客户i,在ai前车辆虽然可以到达客户i,但是必须等待而不能马上为该客户服务,Pd、Pu为惩罚系数. V为车辆容量,每使用一辆车的费用为Fc,行驶单位距离的费用为Fd,运送单位重量货物行驶单位距离的费用为Fw.

　对上述问题描述,假设如下几点成立:

　1)单个客户需求量少于车载量.

　2)任意三点间的距离满足三角不等式.

　3)不考虑天气交通因素对运输的影响.

　4)不考虑卸货对运输时间的影响.

　5)每个客户的服务只能由一辆车一次完成.

　6)有足够的车辆供配送中心调度.

　7)车辆行驶过程速度恒定.