时间窗约束下的车辆路径问题多目标优化算法

《时间窗约束下的车辆路径问题多目标优化算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、万方数据第39卷第7I／1数学的实践与认识V01．39No．72009年4月MATHEMATICSINPRACTICEANDTHEORYApril，2009时间窗约束下的车辆路径问题多目标优化算法张毅，申彦杰(河南科技大学车辆与动力工程学院，河南洛阳471003)摘要：讨论了带时间窗约束的车辆路径问题(VRPTW)及其数学模型。分析了以遗传算法求解该类问题时的染色体表示和有关遗传操作，将VRPTW视为一个多目标优化问题．用Pareto评等技术来求解最优解．并以Solomen基准问题为例验证了该方法的有效性．结果表明t该方法与以往文献中

2、的最好结果具有竞争性．关键词：物流配送，时问窗约束的VRP，遗传算法，多目标优化．1引言带时间窗的车辆路径问题(VRPTW)是VRP问题的扩展，已被Savelsbergh证明是一个NP难题。且对于超过100个客户点的问题很难找到最优解．近年来，遗传算法、禁忌搜索算法、模拟退火算法等启发式方法在解决此类问题中发挥了积极的作用．文献[1]中，H．GehringandJ．Homberger研究了基于混合两阶段搜索算法，第一阶段用演化策略使车辆数最小，第二阶段用禁忌搜索法使总距离最小．文献[2]中，J．Y．PotvinandJ．M．Rouss

3、eau研究了两阶段禁忌搜索算法，第一阶段通过改变路径上的客户来减小车辆数，第二阶段客户交换使总费用最小．文献[3]中，w．C．ChiangandR．Russell研究了基于模拟退火和禁忌搜索的混合算法．文献[4]中，S．R．Thangiah，研究了先聚类后考虑路线的模型，并用遗传算法和局部搜索来进行模型求解．文献[5]中，L．M．Gambardella，E．Taillard，andG．Agazzi等通过分层目标函数最小化研究了一类VRPTW的多目标问题，第一个函数使车辆数最小。第二个函数使总时问最小．文献[6]中。B．Ombuki，M

4、．Nakamura，andO．Maeda先用模拟退火算法设置车辆数。再用局部禁忌搜索算法使总运输费用最小．但上述文献中普遍采用两阶段法解决VRPTW问题，即首先最小化车辆数。继而再最小化行驶距离(费用)，其实质是将一个多目标问题转化为一个单目标的优化问题．但笔者以为，车辆数增加固然会使与之相关的车辆使用费和人工费增加，但优先优化最小车辆数(使用较少的车辆长距离行驶)。在理论和实际应用中不仅没有太多的积极意义，相反会增加燃料费用和为客户服务的时间。特别是在车辆和人工费用较低(如使用摩托车快递)的条件下，由于车辆和人员数的重要性相对降低，

5、这种差别就更加显著．因此，无论从能源消耗还是从生态环境保护角度而言，均应将优化车辆数和距离视为同等重要．本文将两者独立考虑，避免优先考虑其中任何一方和试图将其组合．并运用Pareto评等技术的遗传算法获得与以往研究更具竞争性的最优解．2VRPTW问题及其数学模型设V={1，2，⋯．五)表示车辆集合，C={1，2。⋯，挖)表示客户集合，N={O。1，⋯，咒，咒收藕日期：2007—04．19基金项目t河南省教育厅自然科学基金(200510464028)万方数据7期张毅，等：时间窗约柬下的车辆路径问题多目标优化算法125+1}表示一个连通有

6、向图G=(c，以)顶点集合．点0和咒+1表示配送中心，弧集A表示各个顶点间的可能连接(包括表示配送中心的点)．所有弧既不能终止于点0，也不能起始于点卵+1，并且所有的路线都是从点0开始。至点咒+1结束．费用f，』和在弧(i，．f)∈A上的行驶时间为t伊车辆是的容量为qt，客户i的需求量为di，i∈C．每个客户有时间窗[口，，b，]限制．车辆可以在时间窗开始之前到达，而不允许在时间窗之后到达．假定所有路线在时间0开始，则口。=b。=0．另设决策变量z和s．对于弧(i，歹)，其中i≠歹，i≠，l+1，_『≠0I对于车辆志，当它从i点到-『

7、点时。变量z珊=1，否则等于0．5“表示车辆正开始服务的时间。若车辆五不服务i点，则S抽无意义．根据以上问题描述，可建立如下带时间窗约束的车辆路径问题的数学模型．rain∑∑∑qz叫(1)I∈yiEⅣJ∈Ns．t．∑∑z班=1，Vi∈c(2)●∈yJ∈Ⅳ∑d。∑z啦≤q，V五∈V(3)iECJ∈N∑Xoih=1·V五∈V(4)J∈N∑zⅢ一∑z—p=0，Vh∈C，V志∈V(5)iENJ∈Ⅳ∑Xi肿1．·=1，Vk∈V(6)iENs“+tf』一K(1一z。拍)≤跏，Vi∈Ⅳ，V．，∈Ⅳ，V忌∈V(7)of，≤毋，≤ct，，Vi∈N，V志

8、∈V(8)z珊∈{0，1}，Vi∈Ⅳ，歹∈Ⅳ，V志∈V(9)式(1)是目标函数最小化费用。即在完成配送任务的前提下，要求服务客户的车辆总数最少和车辆行驶总里程最短．式(2)确保每位客户只能被一辆车访问一次；式(3)确保每