《城多网点配送车辆调度模型及算法研究》由会员分享，可在线阅读，更多相关《城多网点配送车辆调度模型及算法研究（6页珍藏版）》请在金锄头文库上搜索。
1、城市多网点配送车辆调度模型与算法研究赵鲁华(山东科技大学 资源与环境工程学院 山东 青岛 266510)摘要 ：多网点布局是城市配送中心发展的趋势，而多网点配送的车辆优化调度问题，在具体实施时 更加复杂困难。本文通过对城市多网点车辆调度特点的深入分析和研究，建立了追求总体效益最优 的多网点车辆调度多目标决策模型，并设计了求解该模型有效的启发式算法。关键词 ：城市配送，多网点，车辆调度，时间窗，启发式算法Study on Vehicle Scheduling Model and Algorithm of City Multi-networkPoint DeliveryZHAO Lu-hua( C
2、ollege of Resource and Environment Engineering .SUST Qingdao Shandong China )Abstract : The multi-network point layout is the developing trend of city delivery center, and the vehicle scheduling problems of city multi-network point delivery is more complicated and difficult in practice. The paper se
3、ts up multi-object decision-making model of multi-network point vehicle scheduling in pursuit of the greatest benefits on the whole through thoroughly studying and analyzing on the features of city multi-network point vehicle scheduling, and designs effective heuristic algorithm to solve the problem
4、. Key words: City delivery, Multi-network point, Vehicle scheduling, Time window, Heuristic algorithm 0 引言城市配送中心发展到一定阶段后，必然通过建立多个配送网点的形式来更好地服务客户，以取 得更大的经济效益和社会效益。而针对城市配送的货物品种多、数量少、批次多、交通情况复杂等 特点的多网点车辆调度问题比单配送中心条件下要复杂的多。现在，国内外对车辆调度的研究多集 中在单配送中心问题上。对于多配送中心问题，Wren 、 Holliday 、 Sumichrast 、 Renaud、 Irni
5、ch 1-4等国外学者进行了相关研究，并取得了一定价值的成果。在国内，一些学者只对简单条件下的多车场 车辆调度问题进行了研究，但是，针对城市范围内复杂的配送条件，多网点多优化目标的车辆调度 问题在国内的研究基本上是空白。本文在已有的研究成果基础上，针对城市配送的特点及配送中心 的战略发展目标确立了符合现实情况的优化目标：满足客户要求，配送成本低和出行车辆数少。这 三个目标集中体现了城市货物运输的经济效益和社会效益，并根据此目标建立了追求总体效益最高 的城市配送中心多网点车辆调度多目标决策模型，设计了求解多网点车辆调度问题有效的启发式算 法，对于在城市范围内复杂状况下的多网点车辆调度问题的研究具
6、有一定的现实意义。1 问题描述和模型构建1.1 问题描述城市多网点的车辆调度是一个多约束问题：即考虑货物发送量、车辆容量、容积、货物需求时 间窗约束，多车型约束，城市交通状态等约束条件下，配送中心的多个网点的任务分派问题和车辆 路线选择问题。 具体可描述如下： 城市配送中心共有 M 个配送网点可以向市内的 N 个客户配送货物，各客户需求点的需求量为qi (i=1,2,N)，体积分别是Vi (i = 1, 2,N)。第m个配送中心可以进行货物配送的车辆集合为 am1,am2，a% ，共有Km辆车，配送车的最大载重量分别是Qamk (m=i ,2,M , k=1 , 2,Km),最大容积分别是 V
7、amk(m=1 , 2,M , k=1 , 2,Km)。各个需求点之间及需求点与配送网点之间的距离 dij 已知。配送车辆从配送中心出发 沿着一条行车路线把装载的货物运送到指定位置后 返回配送网点；每个客户对货物到达时间的要求是在某个时间段上；客户 商品种类不止一种。合理分派各个网点配送任务和车辆配送路线，使目标函数得到优化。1.2模型构建以往对含有时间窗约束的车辆调度问题的研究中，成本大多仅包含行驶成本。但事实上，若违 反了顾客的时间窗约束，则势必会产生一定的损失，例如，赔偿顾客的损失；服务质量和信誉的损 失；车辆等候造成人员闲置成本和机会成本的损失，或因停放不当造成城市交通拥挤而产生的社会
8、 成本损失等，本文将这些成本损失综合称为时间效应成本。设定时间效应成本函数如下：nnG(tJ =Max( ETi - s,0 C2 Max(s, - LT, ),0i 二i J其中，【ET ,LT,】为客户要求车辆到达的时间范围，Si为车辆实际到达时间，G表示车辆在任务点处等待单位时间的机会成本，c2表示车辆在要求时间之后到达单位时间所处以的罚值(G和c2的值可根据具体情况由配送中心和客户通过签订合同的形式确定)。综合上述，可建立城市多网点、多品种货物、多车型装配的车辆调度模型如下：M NuM NuM KmM N M KmZ= MinC i (ti ) + Min . J .一 (C0amk
9、C1amkdij )Xijkm + Mi qi yikm mA iA j7 kAm iA kAM N M KmMin二二二Vi yikm(1)m i i k 1约束条件：N M N M M-X ijkm - 1i =1j i m=1k=1,2,，Km(2)N M M一 一 yikmqiim- QamKk=1,2,，Km(3)N M MI二 yikm Vii =1 m- VamKk=1,2,，Km(4)MDm =Nm 二(5)X ijkm = 0 或 1i,j = 1, 2,.,N+M ； k=1, 2,Km(6)yikm = 0 或 1i=1, 2,.,N ； k= 1,2,，Km(7)其中，
10、C0amk是使用第amk辆车的固定费用，即增加一辆车的边际费用；C1amk是第amk辆车运行单位距离的费用；Xijkm表示第m个配送中心的第amk辆车是否从i点开向j点，如果是，Xijkm值为 1,否则为0； yikm表示点i的任务是否由车辆amk完成，如果是yikm的值为1,否则为0。目标函数 第一项表示时间效应成本最低，第二项表示车辆的使用与运行成本最低，第三项和第四项分别表示 能够达到配送车辆的最大载重量和容积利用率，使车辆的空载率最小。约束条件(2)表示每个需求点只有一辆车进行配送；（3）和（4）表示每辆车的装载容量不超过配送车的最大装载能力；（5）式表明每个客户都得到配送服务；（6）
11、和（7）表明了决策变量 Xijkm和yikm的值；另外，对于硬时间窗问题可将Ci和C2取作无穷大的正数 M，这意味着时间窗约束必须满足，否则成本巨大，没有可行解。2算法设计城市多网点配送的车辆调度模型是NP-难题的组合。在实际解决这类问题时，启发式方法对初值要求不严格，能够较快地得到满意解，且易于计算机实现，这对解决NP难题来说有着不可估量的作用。目前，解决城市多网点配送车辆调度模型的启发式算法还在探索阶段，据国内外相关资料 来看，对该问题的研究多集中在单配送中心、单目标（总成本最低）的问题，而针对城市多网点、 多目标问题，特别是以满足客户要求为主要目标，并追求成本最低、车辆空载率最小问题的解
12、决方 法还没有发现。本文结合 sweep扫描启发式算法、Fisher、Jaikumar的分派启发式算法和 C-W节约 法设计了求解城市多网点车辆调度模型的启发式算法。5-6 具体算法过程如下：2.1将任务进行初始分配计算N个客户与M个网点的距离，根据sweep扫描启发式算法，以就近原则将客户点分配给对 应的配送网点。在实际情况中，有的网点可能距此次分配的所有客户的距离都很远，因此分配得到的客户数Dm可能为0。2.2车辆调度路线优化D mDm1、 根据hm= max【（二.qj /Qm ：）+ 1 ,（二Vj /V m ：）+ 1】确定每个配送网点所需的车辆数目hmii（hm畠0）。其中，Qm,
13、 Vm分别为网点m的车辆平均载重量和平均容量；6为弹性系数，取0.71。2、确定并分派根顾客在分派启发式算法中，根顾客是根据一定的原则选出的货物配送任务（客户）。本文根据以下原则确定根顾客：（1）客户距配送中心的距离；（2）货物的性能（即货物的品种、颜色、形状、规格等）；（3）客户的具体要求（如对时间或装车的要求等）。选出根顾客后，则剩余的任务称为顾客。首先根据根顾客货物的重量、体积等特性分别分派给各个与之相适应的配送车辆，再以根顾客为依 据将其他的任务（顾客）进行分派。由根顾客的定义可知，每个网点m的根顾客的数目必须与配送车辆的数目相等。具体步骤如下：第一步，首先找出有特殊要求，必须单独装车
14、的任务A1, A2,Aio作为根顾客；在hm辆配送车中，搜索满足qA, 1/2 3 GBj （ Va1/2 3 Vb； ） （i = 1, 2,io； j = 1, 2, -jo）（8）的车辆B1, B2,Bjo,并将任务 Ai分派到根据（8）式求出的相应配送车 Bj中。此时剩余任务数nn= Dm i0,剩余车辆数 mm= hm j0。若没有需要单独装车的任务，则i0= 0。第二步，在剩余的 nn项任务中，搜索满足qAk -1/2 3GBh（vAk-1/2 3 VBh ）（ k= 1,2,.nn；h= 1,2,.hm）（9）的任务A+1, A+ 2, .A 2+ e0作为根顾客，直到i0+ e
15、0 = hm，即e0= mm为止；将根顾客 A0+e （e=1, 2, . , e0）分派给根据（9）式求出的相应配送车B+h（h=1,2,.hm）中。3、分配顾客根顾客已经分派到相应的配送车上，且根顾客A1, A2 ,Ai0只能单独装车，因此只需把剩余 的（Dm hm）个顾客分派给根顾客 Ai0+ e,具体步骤如下:第一步，以根顾客Ao+e为供应点，以剩余的(Dm hm)个顾客为需求点；根据式aA = 3 GB 0*j0 hgAje ( a =3VBj人Vaoe)计算各个根顾客A。+e的供应量，根据b= q ( b = v )计算各个顾客Cj(j = 1,2,Dm hm)的需求量。第二步，分别计算所有的顾客与各个根顾客Ao +e(e= 1,2，e0)之间的费用节约值s(i0+e,j),令 M = s(i0 e, j)|s(i0 e,j) .0;由节约算法的原理可知， 若以Cj表示车辆从点i行驶到点j的费用，则点i
