论文研究-动态规划启发式算法求解时变车辆调度问题.pdf,  时变网络中车辆在任意两节点间的行驶时间不仅与节点间的距离有关, 还与所处的时段有关. 对时变车辆调度问题提出一种满足先入先出准则的跨时段处理方法, 直接推导出跨时段对应的车辆行驶时间. 在此基础上建立了数学模型, 并构造动态规划启发式算法进行求解. 该算法能够通过设置参数H平衡求解质量和运行时间. 通过对10组随机产生的数据进行测
1714 系统工程理论与实践 第32卷 经整理得 乃1+1-Bt BK t;+(1 K+1 因此到达节点y的时刻 B2-ti B1+1- Bu t i=ti+ B t:+|1 Cii.K+1 Ciil 经整理得 ≈cK+t,+BK-1+1B B Cij, K+l (2) C Cijl 车辆到达节点j的时刻t;同样也为从节点i出发时刻t的增函数,满足HHO准则特别地,当K=1 时,∑1=2-16元=0,该式变为跨单时段情形,有t=动nt2+(1-am1)B2+cj2,式(2)变为式(1 若t满足B≤t<Bn+1-c车辆会在p时段内到达节点j不会发生跨时段现象;若t:满足 D+1-cn+∑+1=(B2+1-B1)≤t<B+1,车辆在节点i到节点的行驶过程中会从时段n跨越 到时段p+K.特别地当K=1时∑+F1=(B+1-B1)=0,有Bn+1-cn≤<B+1 3模型建立 在 TDVRE问题中,假设相同类型的M辆车需要去服务N个顾客.每辆车具有相同的装载能力,每个 顾客有一确定的需求量.每辆车从车场出发,并返回到车场.每个顾客只能山一辆车服务.车辆装载量不能 超过车的装载能力.该问题目标为找到一组能服务所有顾客的最短行驶时间车辆路线.假设所有车辆在同一 时刻从车场出发,目标可转换为最小化所有车辆服务完顾客后返回车场的时刻 在模型建立过程中,需要用到如下参数和变量 参数 N:顾客数目 M:车辆数目 0:车场编号 d:顾客讠的需求量; Q:每辆车的装载能力 所有车辆从车场出发的时刻; L:非常大的正数 变量 tN+m:第m辆车返回车场的时刻; t:到达节点j的时刻(不考在顾客处停留,也为从节点j出发的时刻) m:车辆于p时段从节点出发,到达节点j的时刻; 1,若车辆在时段p内从节点出发到节点j, p 否则 1,若第m辆车在任意时段访问节点 0. 否则 1,若第m辆车从节点讠出发到节点j yiin 否贝 第8期 李妍峰,等:动态规划启发式算法求解时变车辆调度问题 1715 TDVRP问题数学模型可表示为 ∑ N+m 1,j=1,2,…,N+M 0,i≠jp P 0、⊥ J p- t;-Lm;p≥Sip-D 0.1 1,2,……,N+M;≠;p=1 c1p+Bn+k-118AA1,2,…,P ti t ci ≤t<Bp+1-cijn,P 1-m+B1= EP (B1+1-B1)≤t<B2 Cijl (8) M ∑zm≤Q ∑m=∑ 0.1.….N 1.2 N+M 20P +M;p=1,2, (12) {0,1} 1,2 2im∈{0,1},i=0,1,…,N;m=1,2.…,M 日标函数(3)为最小化所有车辆访问完所有顾客之后返回车场的时刻.约束(4)保证在任一时段节点j 紧前只有一个节点.约東(5)保证在任一时段节点讠紧后只有一个节点.约束(6)计算到达节点j的时刻 若x=1,约束(7)应取“=”号,此时t=51;若xi=0,约束(7)应取“>”号.约束(7)分别考虑了跨 时段与不跨时段两种情况计算S1p.约束(8)保证每个顾客只能被某一辆车访问,而车场则被所有车辆访问 约束(9)为车的能力约束.约束(10)保证路径的连续性.约束(11)保证车辆到达节点i的时刻非负 4动态规划启发式算法 为了更好地描述动态规划启发式算法,在此先给出求解 TDVRP问题的动态规划精确算法.为了描述方 便,时变处理以考虑跨单时段情形(跨多时段情形叮类推). S表示车辆访问的节点(顾客+车场)集合.若所有车辆从车场出发,访问完所有顾客,并回到车场,则 S可表示为{0,81,0,62,0,…,0,sM,0},其中s1(∈1,M)表示第l辆车访问的全部顾客集合,0的个数为 M+1,因此|S|=N+M+1 阶段数:N+M4+1 状态(S,h):S={0,31,0.,52,0,…,0,1-1,0,w,b}表示目前已安排了-1辆车的路径,且第l(≤M) 辆车访间∫部分顾客集合后到达节点h、h∈{0,1,…,N/(=15;m) 指标函数F(S,h):表示前l-1辆车的总到达时刻与第l辆车访问了部分顾客集合u后到达节点h的 时刻之和最小值 初始条件 S|=1:S={0},S中只有车场 1716 系统工程理论与实践 第32卷 S=2:对第一辆可供使用的车,有 F({0,b},h Bos to B nhm,p=1,2,…,P (15) to+(1 Bp+1+ Coh, p+1, Bp+ ≤to<B2 1.2 P-1 Coh 其中h∈{0, 对S>2,S=(0,。81,0,82,0,…,0,w,g,b},考虑第l辆车访问了节点q后立即访问节点,对所有 h∈{0,1,…,N},有如下递归方程 (S-{h},q)+c ≤F(S-{h},q)-∑f(m)<B2+1-chp,p=1,2,…,P m=1 F(S,h= q∈{0,…N}/{h} ∑fm)+中F(Sy)-∑ f(m)+(1 cgh, P+1Bp+/+cgrp C P Bn+1-cmn≤F(S-{h}q)-∑f(m)<B+1,=1,2 其中,f(m)(m∈[1,l-1)为第m辆车的最早返回车场时刻 最后阶段|S=N+M+1:考虑第M辆车访了顾客q后返凹车场,则所有车辆返车场的总最早 到达时刻为 F(S-{0},q)+c M-1 Bp≤F(S-{0},q)-∑f(m)<Bn+1-cm,P 把1210=0m C02+1)Bn+1+cp (17) gOp M-1 Bp+1 0}p)-∑f(m) 动态规划启发式算法在动态规划精确算法的基础上.每阶段保留前H(或小于H,当每阶段所有的子路 径数目小于H时)个最优子路径,H是一个可被设定的参数.假设在第讠阶段(S|=)得到前H个最优子 路径,则第i+1阶段(S|=i+1),在这H个最优子路径后加上一节点(若为顾客,则之前一定未被访问),同 样在该阶段选择前Ⅰ个最优子路径.特别地,当H=1时,该算法变为 Malandraki和 Daskinltj提出的最近 郐算法,动态规划启发式算法是动态规划精确算法与最近邻算法的折中,在保证满意解的情况下能够较大幅 度地减少运算时间和存储空间.算法步骤如下 Step 1 S-1,$=10f Step 2S +1,若|S|=N+M+1,转Sep6 Step3对正被安排的车通过对上阶段前H(或小于H)个最优子路径加上一个剩余未被访问的顾客 若满足该车能力约束,则计算在当前阶段到达该顾客的时刻,转Step5;否则,转Step4 Seυ4对正被安排的车返回车场,计算返回车场的到达时刻,另安排下一辆车.转Suep5 Step5当前阶段保留前Ⅱ(或小于Ⅰ)个最优子路径 Step6第M辆车对应的前H个最优子路径均返回车场.在H个方案中,找到最早到达车场时刻,并 回溯找到最优路径.算法停止 5实验及算法性能比较 文中用随机产生的10组不同规模数据分别测试动态规划启发式算法和最近邻算法,考虑跨单时段情形. 随机数据包括顾客数、车辆数和在不同时段节点间的车辆行驶时间.所有程序均用C++编写,并在 Pentium ⅣV主频1.6GHz的计算机上进行实验仿真.表1记录了两类算法的实验结果,其中包括了目标函数值(单位: h)和算法运行时间(单位:s) 第8期 李妍峰,等:动态规划启发式算法求解时变车辆调度问题 1717 表1动态规划启发式算法和最近邻算法性能比较 实验 动态规划启发式算法 最近邻算法 规模 H=3 H=1 (顾客数ⅹ车辆数)目标函数值运行时间目标函数值运行时间目豕函数值运行时间 23.48 0.00 23.48 0.00 23.48 0.00 10×3 0.01 36.59 0.02 0.01 20×5 48.41 0.04 60.54 30×6 5982 0.25 54.96 0.34 75.21 0.14 50×8 86.72 0.51 79.28 0.51 104.11 0.36 60×10 1.02 169.28 0.77 100×15 160.92 1.93 143.50 2.64 l89.89 1.20 150×22 259.31 3.75 242.65 4.03 278.34 2.09 200×35 34.92 4.56 321.84 5.02 367.30 3.18 250×40 NA NA 平均值 128.79 1.34 119.97 1.58 144.91 0.86 注:NA表示不能运行计算 从表1,可以得到如下结论: 1)随着 TDVRF问题规模的扩大,即顾客数和车辆数不断增加,两类算法的运行时间随之增加.当顾客 数为250、车辆数为40时,以上两类算法均不能求解. 2)随着H的增加即每阶段选取状态数越多,所得目标函数值越好.H=2对应的目标函数值比H=1对 应的目标函数值改进11%,H=3时目标函数值比H=1时目标函数值改进17% 3)随着H的增加,算法运行时间也随之增加,但增加幅度不大.当H=1时平均运算时问为0.86s,H=2 时平均运算时间为1.34s,H=3时平均运算时间为1.58.在平均运算时间不到2s的情况下,动态规划启发 式算法能较好地改进最近邻算法(H=1)的目标函数值 6结论 木文对①DVRP间题提出一类满足IO准则的垮时段处理方法,建立相应的数学模型,并构造动态规 划启发式算法求解该问题通过设置算法参数H平衡求解质量和算法运行时间,使得算法运用更加灵活.H 越大(小),求解质量更好(差),算法运行时间越长(短).当H设置为每阶段子路径数目时,算法变为动态规 划精确算法;当H=1时,算法变为最近邻算法.文中对10组随机数据进行测试,结果表明,动态规划启发式 算法能在非常短的时间内得到比最近郐算法更好的解.该算法也能在运行时间和存储空间允许的情况下求 解更大规模的问题得到满意解,为实际物流企业配送提供更切实际的决策支持.该方法还可以应用于其他时 变运输问题 参考文献 [1 Malandraki C, Daskin M S. Time dependent vehicle routing problems: Formulations, properties and heuristic algorithms J. Transportation Science, 1992, 26(3): 185-200 2 Malandraki C, Dial B. A restricted dynamic programming heuristic algorithm for the time dependent traveling salesman problem[J]. European Journal of Operational Research, 1996, 90(1):45-55 3 Ahn B H, Shin JY. Vehicle-routing with time windows and time-varying congestionJ. Journal of the Operational Research Society, 1991, 42(5): 393-400 1 Hill A V, Benton W C. Modeling intra-city time-dependent travel speeds for vehicle scheduling problemsJ Journal of the Operational Research Society, 1992, 43 (4):343-351 5 Horn ME T. Efficient modeling of travel in networks with time-varying link speeds[J]. Networks, 2000, 36(2) 8090 6 Ichoua S, Gendreau M, Potvin J Y. Vehicle dispatching with time-dependent travel times J. European Journal of Operational Research, 2003, 144(2):379-396 7 Fleischmann B, Gietz M, Gnutzmann S. Time-varying travel times in vehicle routing J. Transportation Science, 2004,38(2):160-173. 1718 系统工程理论与实践 第32卷 [8 Haghani A, Jung S. A dynamic vehicle routing problem with time-dependent travel times[J. Computer Op- erations Research, 2005, 32(11): 2959-2986 9 Donati A V, Montemanni R, Casagrande N, et al. Time dependent vehicle routing problem with a multi ant colony system[J. European Journal of Operational Research, 2008, 185(3): 1171-1191 10李妍峰,李军,赵达·用动态搜索算法求解吋间依赖型旅行商问题「J.西南交通大学学报:自然科学版,2008,43(2) 187-193. Li Y F, Li J, Zhao D. Dynaseareh algorithms for solving time dependent traveling salesman problemJ Journal of Southwest Jiaotong University, 2008, 43(2): 187 193 1]李妍峰,李军,高自友.时变网络环境下旅行商问题研究!J.系统工程学报.2010,25(5):585591 LiY F, Li. Gao Z Y. Traveling sa lesman problem in time varying net work[ J] Journal of Systems Engineering, 2010,25(5):585-591 12魏航,李军,蒲云.吋变条件下有害物品运输的路径问题硏究「J.系统工程理论与实践,2006·26(10):107-112 Wei H, Li J, Pu Y. Route planning for hazardous materials transportation in time-varying networkJ. Systems Engineering Theory Practice, 2006, 26(10): 107-112 13魏航.种求解时变条件下有宵禁限制最短路的算法[.管理科学学报,2009,12(1):917 Wei H. An approach for time-varying shortest path problem with curfews[J. Journal of Management Science in China,2009,12(1):917 14 Van Woensel T, Kerbache L, Peremans H, et al. A queueing framework for routing problems with time-dependent travel times J. Journal of Mathemalical Modeling and AlgorithIns, 2007, 6(1):151-173 [15 Van Woensel T, Kerbache L, Peremans H, et al. Vehicle routing with dynamic travel times: A queueing h[J. European Journal of Operational Research, 2008, 186(3): 990-1007