城市多网点配送车辆调度模型及算法研究

1、城市多网点配送车辆调度模型与算法研究赵鲁华（山东科技大学 资源与环境工程学院 山东 青岛 266510）摘要：多网点布局是城市配送中心发展的趋势，而多网点配送的车辆优化调度问题，在具体实施时更加复杂困难。本文通过对城市多网点车辆调度特点的深入分析和研究，建立了追求总体效益最优的多网点车辆调度多目标决策模型，并设计了求解该模型有效的启发式算法。关键词：城市配送，多网点，车辆调度，时间窗，启发式算法Study on Vehicle Scheduling Model and Algorithm of City Multi-network Point DeliveryZHAO Lu-hua（Colle

2、ge 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 sets up

3、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.Key w

4、ords: City delivery, Multi-network point, Vehicle scheduling, Time window, Heuristic algorithm0 引言城市配送中心发展到一定阶段后，必然通过建立多个配送网点的形式来更好地服务客户，以取得更大的经济效益和社会效益。而针对城市配送的货物品种多、数量少、批次多、交通情况复杂等特点的多网点车辆调度问题比单配送中心条件下要复杂的多。现在，国内外对车辆调度的研究多集中在单配送中心问题上。对于多配送中心问题，Wren、Holliday、Sumichrast、Renaud、Irnich1-4等国外学者进行了相关研究，

5、并取得了一定价值的成果。在国内，一些学者只对简单条件下的多车场车辆调度问题进行了研究，但是，针对城市范围内复杂的配送条件，多网点多优化目标的车辆调度问题在国内的研究基本上是空白。本文在已有的研究成果基础上，针对城市配送的特点及配送中心的战略发展目标确立了符合现实情况的优化目标：满足客户要求，配送成本低和出行车辆数少。这三个目标集中体现了城市货物运输的经济效益和社会效益，并根据此目标建立了追求总体效益最高的城市配送中心多网点车辆调度多目标决策模型，设计了求解多网点车辆调度问题有效的启发式算法，对于在城市范围内复杂状况下的多网点车辆调度问题的研究具有一定的现实意义。1 问题描述和模型构建1.1 问

6、题描述城市多网点的车辆调度是一个多约束问题：即考虑货物发送量、车辆容量、容积、货物需求时间窗约束，多车型约束，城市交通状态等约束条件下，配送中心的多个网点的任务分派问题和车辆路线选择问题。具体可描述如下：城市配送中心共有M个配送网点可以向市内的N个客户配送货物，各客户需求点的需求量为 (i=1,2,N)，体积分别是（i1，2，N）。第m个配送中心可以进行货物配送的车辆集合为，共有辆车，配送车的最大载重量分别是(m=1，2，M，k=1，2，), 最大容积分别是(m=1，2，M，k=1，2，)。各个需求点之间及需求点与配送网点之间的距离已知。配送车辆从配送中心出发，沿着一条行车路线把装载的货物运送

7、到指定位置后，返回配送网点；每个客户对货物到达时间的要求是在某个时间段上；客户商品种类不止一种。合理分派各个网点配送任务和车辆配送路线，使目标函数得到优化。1.2 模型构建以往对含有时间窗约束的车辆调度问题的研究中，成本大多仅包含行驶成本。但事实上，若违反了顾客的时间窗约束，则势必会产生一定的损失，例如，赔偿顾客的损失；服务质量和信誉的损失；车辆等候造成人员闲置成本和机会成本的损失，或因停放不当造成城市交通拥挤而产生的社会成本损失等，本文将这些成本损失综合称为时间效应成本。设定时间效应成本函数如下： 其中，【】为客户要求车辆到达的时间范围，si为车辆实际到达时间，表示车辆在任务点处等待单位时间

8、的机会成本，表示车辆在要求时间之后到达单位时间所处以的罚值（和的值可根据具体情况由配送中心和客户通过签订合同的形式确定）。综合上述，可建立城市多网点、多品种货物、多车型装配的车辆调度模型如下：Z=+ （1）约束条件： k=1，2，Km （2） k=1，2，Km （3） k=1，2，Km （4）=N （5）0或1 i，j1，2，.，N+M；k1，2，Km （6）0或1 i1，2，.，N；k1，2，Km （7）其中，是使用第辆车的固定费用，即增加一辆车的边际费用；是第辆车运行单位距离的费用；表示第m个配送中心的第辆车是否从i点开向j点，如果是，值为1，否则为0；表示点i的任务是否由车辆完成，如果是

9、的值为1，否则为0。目标函数第一项表示时间效应成本最低，第二项表示车辆的使用与运行成本最低，第三项和第四项分别表示能够达到配送车辆的最大载重量和容积利用率，使车辆的空载率最小。约束条件（2）表示每个需求点只有一辆车进行配送；（3）和（4）表示每辆车的装载容量不超过配送车的最大装载能力；(5)式表明每个客户都得到配送服务；（6）和（7）表明了决策变量和的值；另外，对于硬时间窗问题可将和取作无穷大的正数M，这意味着时间窗约束必须满足，否则成本巨大，没有可行解。2 算法设计城市多网点配送的车辆调度模型是NP-难题的组合。在实际解决这类问题时，启发式方法对初值要求不严格，能够较快地得到满意解，且易于计

10、算机实现，这对解决NP难题来说有着不可估量的作用。目前，解决城市多网点配送车辆调度模型的启发式算法还在探索阶段，据国内外相关资料来看，对该问题的研究多集中在单配送中心、单目标（总成本最低）的问题，而针对城市多网点、多目标问题，特别是以满足客户要求为主要目标，并追求成本最低、车辆空载率最小问题的解决方法还没有发现。本文结合sweep扫描启发式算法、Fisher、Jaikumar的分派启发式算法和C-W节约法设计了求解城市多网点车辆调度模型的启发式算法。5-6具体算法过程如下：2.1 将任务进行初始分配计算N个客户与M个网点的距离，根据sweep扫描启发式算法，以就近原则将客户点分配给对应的配送网

11、点。在实际情况中，有的网点可能距此次分配的所有客户的距离都很远，因此分配得到的客户数可能为0。2.2 车辆调度路线优化1、根据hmmax【（/Qm）1，（/Vm）1】确定每个配送网点所需的车辆数目hm（hm0）。其中，Qm，Vm分别为网点m的车辆平均载重量和平均容量；为弹性系数，取0.71。2、确定并分派根顾客在分派启发式算法中，根顾客是根据一定的原则选出的货物配送任务（客户）。本文根据以下原则确定根顾客：（1）客户距配送中心的距离；（2）货物的性能（即货物的品种、颜色、形状、规格等）；（3）客户的具体要求（如对时间或装车的要求等）。选出根顾客后，则剩余的任务称为顾客。首先根据根顾客货物的重量

12、、体积等特性分别分派给各个与之相适应的配送车辆，再以根顾客为依据将其他的任务（顾客）进行分派。7由根顾客的定义可知，每个网点m的根顾客的数目必须与配送车辆的数目相等。具体步骤如下：第一步，首先找出有特殊要求，必须单独装车的任务A1，A2，Ai0作为根顾客；在hm辆配送车中，搜索满足1/2（1/2）（i1，2，i0；j1，2，j0） （8）的车辆B1，B2，Bj0，并将任务Ai分派到根据（8）式求出的相应配送车Bj中。此时剩余任务数nni0，剩余车辆数mmhmj0。若没有需要单独装车的任务，则i00。第二步，在剩余的nn项任务中，搜索满足1/2（1/2）（k1，2，.nn；h1，2，.hm） （

13、9）的任务Ai01，Ai02，.Ai0e0作为根顾客，直到i0e0hm，即e0mm为止； 将根顾客Ai0e（e1，2，.，e0）分派给根据（9）式求出的相应配送车Bj0+h(h=1,2,.hm)中。3、分配顾客根顾客已经分派到相应的配送车上，且根顾客A1，A2，Ai0只能单独装车，因此只需把剩余的(hm)个顾客分派给根顾客Ai0e，具体步骤如下：第一步，以根顾客Ai0e为供应点，以剩余的（hm）个顾客为需求点; 根据式（ ）计算各个根顾客Ai0e的供应量，根据（）计算各个顾客Cj(j=1,2,hm)的需求量。第二步，分别计算所有的顾客与各个根顾客Ai0e（e1，2，.，e0）之间的费用节约值s

14、(i0+e,j)，令M；由节约算法的原理可知，若以表示车辆从点i行驶到点j的费用，则点i和点j连接在一条线路上的费用节约值为，因此，根据本文所建立的城市配送车辆调度模型，节约值应按下式计算： 可得第三步，在M内按s(i0+e,j)从大到小的顺序排列；第四步，若M，则终止，否则按s(i0+e,j)从大到小的顺序，考察相应的（i0+e，j）所对应的：（1） 若0，则转第六步（2） 若 0，则计算，令Ms(i0+e,j)|s(i0+e,j)0； 其中表示连接点i和点j所在线路后，车辆到达j点的时间比原路线上车辆到达j点时间的推迟量， （代表车辆到达i点的时间；代表车辆从i点到j点的时间；代表完成任务

15、i的时间）。显然，0时，到达时间推迟。是由时间原因而对节约值的修正值：（，为连接点i和点j所在线路时，车辆在j后面的任务r处的等待时间；，为任务r开始执行的延迟时间）。第五步，在M内按s(i0+e，j)从大到小的顺序排列，对第一项s(i0+e，j)，考察对应的（i0+e，j），转下一步； 第六步，若（i0+e，j）满足下列条件之一：(1)点i0+e和点j不在已构的线路上（设只有根顾客的线路不算已构成线路）；(2)点i0+e点j在已构成的线路上，但不是线路的内点（即不与车场相连）；(3)点i0+e和点j位于已构成的不同线路上，均不是内点，且一个是起点，一个是终点。则转下一步，否则转第九步；第七步

16、，考察顾客j的需求量 和，若满足，则转下一步，否则转第九步； 第八步，连接点i和点j，计算车辆到达各项任务的新时间，转第九步； 第九步，令M：M，转第四步。8-92.3 优化调整所有任务都得到分派以后，则得到配送车辆的配送路线，此时可恢复车辆的人工容量为实际容量。为使配送车辆调度能够达到整体最优，在根据配送路线进行配送时，可采用人工经验法对配送调度结果从整体上进行检查调整，在组成每个网点的每条配送路线的需求点组中，若有配送点严重偏离该组，则可在不违反时间等约束的情况下进行适当调整，配送中心也可与客户进行沟通看能否在客户允许的范围内进行时间调整，这样可达到配送中心的整体效益和社会效益最高。3 结

17、束语本文针对城市配送的特点，考虑货物品种的复杂性、客户的要求、车辆的装载率等，设计启发式算法来求解多网点的车辆调度问题。首先根据sweep启发式算法将所有任务进行初始分配，分配给最近的配送网点；然后对每个网点的客户组采用Fisher、Jaikumar分派启发式算法以保证最大程度地满足客户的要求，并对C-W节约算法进行修正，在连接点对时，考虑时间约束，来求解较优的车辆调度路线；保证配送中心能够保留并吸引客户的同时降低配送成本；最后进行总体优化调整，以达到整个配送网点车辆调度的全局优化。笔者根据该算法设计并开发了城市配送车辆调度系统，该系统的正常运行表明了该算法能够有效地解决城市多网点配送多目标决

18、策问题。参考文献：1 A. Wren and A. Holliday. Computer scheduling of vehicles from one or more depots to a number of delivery points J. Opns Res. Q. 1972, 23: 333-344.2 Wu T. H. Low C. Bai J.W. Heuristic solutions to multi-depot location-routing problemsJ. Computers & Operations Research, 2002 (29):1393-1415.3 Sumichrast R. T., Markham I. S. A heuristic and lower bound for a multi-depot routing problemJ. Computer Ops Res, 1995,22(10):1047-1056.4Irnich S. A multi-depot pickup and delivery problem with a single hub