物流系统优化与设计-有时间窗约束非满载车辆调度问题的C-W节约启发式算法.doc

物流系统优化与设计题 目: 有时间窗约束非满载车辆调度问题的 c-w节约启发式算法 姓 名: 宋 静 敏 学 院: 专 业: 物 流 工 程 班 级: 物 流 84 班 学 号: 指导老师： 2011年 6 月 29日有时间窗约束非满载车辆调度问题的c-w节约启发式算法物流工程专业学生 宋静敏摘 要：本文引用了一个实际案例，假设了相应的时间约束与各配送点的任务量，采用c-w节约启发式算法求解和分析了此种带有时间窗约束的非满载车辆优化调度问题，得到了最优路线，从而在一定程度上达到了总运行费用最少的目标，实现了非满载车辆的优化调度。关键词：车辆调度；c-w节约算法；时间窗；非满载；配送路线相对一般的集货或送货非满载vsp来说，对于有时间约束的集货或送货的非满载vsp问题越来越受到人们的关注。本文针对多点配送调度问题，引用了一个实际案例，对旅行商的c-w算法进行修正，采用c-w节约启发式算法对带有时间要求的硬时间窗车辆优化调度问题进行了求解和分析，得到了满足货运需求的费用最小的运输路线，从而在一定程度上实现了非满载车辆的优化调度。1 案例问题描述与情景假设本文以南京浦口区部分苏果超市的实际分布为例，假设了某个物流配送中心在一天时间内的送货任务，并用驾车的最短距离近似地表示点对间的实际行驶距离。具体情景假设为：某物流配送中心正常上班时间为7：30，现有11项送货任务，编号为1，11，各任务的货运量为gi （ 单位：吨)。卸货时间为ti（单位：小时）以及要求每项任务开始执行的时间范围为 eti，lti（单位：时刻）由表1给出。这些任务由配送中心0发出的容量为8吨的车辆来完成，配送中心0与各任务点间和各个任务点之间的距离（单位：公里）由表2给出。表1 任务的特征及要求任务i1234567891011gi(吨)222.5343.51.54.5343ti小时0.30.20.20.150.250.250.30.250.30.350.4eti, lti 0.5,0.80.8,10.7,10.4,0.70.4,0.80.3,0.60.9,1.20.7,10.4,0.70.3,0.70.5,0.9表2 点对之间的距离012345678910110026.135.325.717.419.117.332.32417.117.227.3105.912.111.613.313.13.413.810.412.99.22 06.367.47.33.78.15.37.23.5301.34.439.25.50.92.84403.31.79.42.421.54.3502.111.53.15.32.25.26010.41.73.70.856.57011.37.810.26.8802.80.754.7905.93.41005.6110这里，假设车辆的行驶时间与距离成正比，每辆车的平均行驶速度为40公里/小时，则从点i到j的行驶时间，tij=dij/40就不另列表给出了。又把各点之间的距离作为费用，即cij=dij（i,j=0,1,11）,如何安排车辆的行驶路线，使总运行费用最少。2 优化方法描述2.1 算法原理此算法对旅行商问题的c-w算法进行修正，在连接点对时，考虑时间约束，是一种解决时间窗问题的有效启发式算法。以cij表示车辆从点i到点j的费用，由c-w算法得到点i和点j连接在一条线路上的节约值：s(i,j)=ci0+c0j-cij。上述案例问题描述已经假设eti为任务i的允许最早开始时间，lti为任务i的允许最迟开始时间。以si表示车辆到达点i的时间，tij表示车辆由点i行驶到j的时间，则有下列关系式：s0=0，etisilti。以ef表示连接点i和点j所在的线路后，车辆到达j的时间比原线路上车辆到达j点时间的推迟（或提前量），则efj可表示为：efj=si+ti+tij-sj。显然，efj0时，到达时间推迟。 为说明问题方便，定义参数如下：-j 车辆在线路上j点后面的各任务均不需要等待的j点的到达时间的最大可以提前量；+j 线路上j点后面的任务不违反时间窗约束的j点的到达时间的最大允许推迟量。分别可以按下式计算：-j = minsr-etr +j = minltr-sr rj 当考虑连接点i和点j所在的线路时，需检查是否违反时间窗约束。（1） 当efj0时，若有efj +j ，则j后面的任务的执行不会延迟，否则，要延迟进行。2.2 算法步骤根据前述算法原理，设计具体求解步骤如下：step1:计算s(i,j),令m =s(i,j)|s(i,j)0;step2:在m内按s(i,j)从大到小的顺序排列；step3:若m = ，则终止，否则对第一项s(i,j),考察对应的（i，j）,若满足下述条件之一：（1）点i和点j均不在已构成的线路上；（2）点i或点j在已构成的线路上，但不是线路的内点（即不与配送中心相连）；（3）点i和点j位于已构成的不同线路上，均不是内点，且一个是起点，一个是终点,则转下步，否则转step7。step4:考察点i和点j连接后的线路上总货运量q，若qq,则转下步，否则转step7。step5:计算efj（1） 若efj =0，则转step6;（2） 若efj 0，则计算+j ，当|efj|+j ，则转step6，否则转step7;step6:连接点i和点j,计算车辆到达各任务点的新时间,转step7。step7:令m：= m-s(i,j),转step3。3 优化方案3.1 计算各点之间连接的费用节约值s(i,j)，并按从大到小的顺序示于表3中。表3 点对之间连接的费用节约值(i,j)(2,7)(2,11)(1,2)(1,7)(2，3)(7,11)(2,8)(3,11)(3,7)(2,9)(2,5)s(i,j)63.959.155.55554.752.851.24948.847.147(i,j)(2,4)(8,11)(2,6)(2,10)(7,8)(1,11)(3,8)(3,9)(3,4)(7,9)(5,11)s(i,j)46.746.645.345.34544.244.241.941.841.641.2(i,j)(9,11)(8,10)(3,5)(4,11)(4,7)(3,10)(3,6)(5,8)(5,7)(1，3)(6,8)s(i,j)4140.4540.440.440.340.1404039.939.739.6(i,j)(7,10)(6,7)(4,8)(10,11)(8,9)(6,11)(1,8)(5,6)(5,10)(6,10)(4,5)s(i,j)39.339.23938.938.338.136.334.334.133.6533.2(i,j)(4,10)(4,6)(1,9)(4,9)(1,4)(1,5)(5,9)(6,9)(1,10)(1,6)(9,10)s(i,j)33.13332.832.531.931.930.930.730.430.328.43.2 构造线路初始时，当车辆从车场0开往任务i时，若efit0ilti，取si = t0i,若t0ieti,取si = eti 。表4 点对之间的连接过程1234567i-j两点位置q=giefj=si+ti+tij-sj-j 或 +j连接否sk:=sk+efj(kj)27非线路上点q=g2+g7=3.5 qef7=s2+t2+t27-s7= 0.0275+7= lt7-s7=0.327s7:=s7+ef7=1.175112非线路上点、外点q=g11+g2+g7=6.5 +2不能连接92非线路上点、外点q=g11+g2+g7=6.5 qef2=s9+t9+t9,2-s9= -0.0225-2=mins2-et2, s7-et7=0.0825| ef2| -2927s2:=s2+ef2=0.86s7:=s7+ef2=1.15253.3 求解结果与分析由表4所示，得到最终的线路与运输距离如下表5：表5 最终的线路与运输距离车辆访问次序运输距离行驶时间（小时）装载量101052.21.3052204034.80.87330103045.71.14256.540927058.41.466.550511051.61.29760680431.0758显然，各任务的开始时间均满足时间窗约束。其中，与配送中心单独构成行驶路线的1点、4点可能是到达时间约束以及卸货时间要求造成的。此时，配送中心应该安排6辆车进行这一天的配送任务，并且按照以上路线行驶可以实现总运行费用最少，即总运输距离最短的目标。4 结语本文采用c-w节约启发式算法，分析了带有时间窗的配送车辆调度问题，算法简单，但也存在着某些边缘点难于组合以致于影响整体最优的缺点。同时，可用matlab软件设计出相应的遗传算法，操作简洁。而本文基于人工操作，算法需要改进的地方还很多，需要进一步修正，从而以更优的行驶路线，确定最省运行时间和最适合载重量，使总运行费用最少。参考文献：1 李剑文.带时间窗车辆路径问题的优化控制研究d.黑龙江：哈尔滨工业大学，2007:8-18.2 宋伟刚,张宏霞,佟玲.有时间窗约束非满载车辆调度问题的节约算法j.东北大学学报,2006,27(1):65-68.3 李作秋，王国林.一种有时间窗约束的非满载车辆调度问题中的启发式算法研究j.公路交通科技,2006,23(7):147-150.4 李芳，郑晴，邱俊茹等.带时间窗的某物流配送车辆调度问题的方案优化分析j.数学的实践与认识,2010,40(17):177-180.5 徐哲.基于遗传算法的配送车辆调度优化研究j. 中国产业,2010(12).附录：1 配送中心0与各任务点i（i=1,2,11）表示的实际地点见附录表。附录表编号任务点地址0苏果马群配送中心江苏省南京市栖霞区青马路1号1苏果便利店江苏省南京市浦口区文昌路 西 575 米2苏果便利江苏省南京市浦口区双城路 东北 5.4 公里3苏果便利江苏省南京市浦口区浦东路7-4号 东北 10 公里4苏果便利江苏省南京市浦口区 东北 11 公里