基于动态需求的多车型车辆配送路径优化研究

曹炳汝，王 霞

（江南大学商学院，无锡 214122）

0 引言

车辆路径问题[1]（Vehicle Routing Problem，VRP）自1959年Dantzing和Ramser提出以来，备受广大研究者的关注，一直是研究的热点。假定在进行配送路径规划之前，客户所在位置、客户指定的服务时间窗、需要提供配送服务的货物重量、体积、行驶速度、在客户地点服务的时间等都是确定的，在这种情况下，实施的车辆调度方案一般是固定且不会变化的，这类运输问题被称为静态车辆路径优化问题。事实上，在物流配送中可能出现新增客户点、原客户点的需求增多、减少甚至变为零、交通堵塞或天气状况等情况需要重新调整配送路线，这类问题被称为动态车辆路径优化问题（Dynamic Vehicle Routing Problem，DVRP）。动态车辆路径优化问题研究的是动态变化的情况，更加符合实际情况，因而逐渐成为研究的热点。实际上，大多数物流公司通过历史调度经验进行车辆的调度，面对实时变化的客户需求时，即使借助GPS等先进的系统可能也没有办法在短时间内重新规划路径以满足客户需求量和服务时间要求。在客户的动态需求下，如何决策使得运输成本最小化是物流公司亟待解决的问题。

张景玲等[2]为解决如果通过实时调度将动态需求的客户插入到初始配送路线中，考虑到配送中心拥有多种型号的车辆，建立了基于多车型的动态需求模型，提出了混合量子进化算法进行求解。葛显龙[3]根据动态车辆路径问题的产生的原因提出了时间轴概念，根据配送网络的服务状态找到关键点，建立了动态调度问题模型，并提出了云遗传算法。Goodson J C等[4]提出了一种基于固定路径的策略，以此来获得车辆路径问题的动态解。葛显龙等[5]考虑到了配送车辆从多个配送中心出发，建立了多车型动态需求模型，并利用云遗传算法进行求解。Jabali O等[6]提出了一种基于一般局部路径生成的三种下界泛函数，并给出了识别违规割集的精确分离过程。Zhang Q和Yan R[7]在随机研究随机需求车辆路径问题及其模型时，将免疫算法和遗传算法结合，提出了一种混合式的算法。Sarasola B等[8]提出了适用于动态设置的可变邻域搜索算法（VNS），并发现在需求偏差较小的情况下，基于采样的动态VNS方法能获得较好的结果。Zhang J[9]等考虑了带时间窗的需求随机的车辆路径问题，建立了三种概率模型，并提出了预防性再储备策略。Lingkai L等[10]在需求预测和电池数量分析的基础上，建立了基于电池交换站的初始模型和实时调度模型。Hernandez F等[11]根据需求是随机不确定的特点，建立了两阶段模型，第一阶段规划模型，第二阶段执行模型，若在执行过程中由于随机需求的出现，车辆无法满足客户的需求，则需要回配送中心进行补货。Hu C[12]等研究了需求和旅行时间不确定性条件下具有硬时间窗的车辆路径问题，并设计了一种基于改进的自适应可变邻域搜索启发式的两阶段算法。

在多车型车辆调度研究中，葛显龙等[13]在前人的研究基础下提出了多车型车辆路径优化问题的车型分配原则，并将实载率纳入运输成本的考虑范围。杨珍花，平仲，汤洋，et al[14]在冷藏车多车型混合配送调度优化研究中考虑冷链配送货物对时间的要求提出了时间窗外的惩罚成本表达式。Cruz J等[15]在具有时间窗和多乘积的多车型车辆路径问题的研究中，提出了序贯蚁群系统-禁忌搜索算法，引入了两种信息表跟踪策略。Penna P H V等[16]将多仓库、分批交付、站点依赖性、开放路线、时间窗口等属性与多车型相结合，并提出了一种混合元启发式算法进行求解。Zhang D等[17]在研究多车型车辆路径问题时，考虑了二维负载约束，并将人工蜂群算法和人工免疫算法相结合，提出了一种混合式算法，有效避免了出现局部最优解的情况。Farid G S和Abdolhadi Z[18]利用非均匀性的概念，考虑了时间窗和多车型因素，建立了多目标函数，根据客户的优先服务问题，提出了非支配排序遗传算法。Yu Y[19]等考虑多车型车辆可用于减少碳排放的特性，提出了一种改进的支路价格算法求解带有时间窗的异质车队绿色车辆路径优化问题。Bevilaqua A[20]等研究了两级固定车队异质车辆路径问题，提出了一种基于局部搜索的LIN-Kernighan启发式算法。

基于前述研究成本，建立了基于动态需求的多车型车辆路径两阶段优化模型，研究了在出现动态的客户需求时如何合理的安排配送线路使得运输成本最低，考虑了多车型以及时间窗对车辆配送线路的影响，基于问题的HP-hard特性，本文采用了遗传算法进行运算求解配送线路。最后通过JLD公司实际配送案例进行研究，证明模型有效的降低了JLD公司的运输成本并减少了配送车辆数量。

1 问题描述和模型的基本假设

1.1 问题描述

基于动态需求的多车型车辆路径优化问题可以描述为：配送中心存在不同车型的车辆，根据客户的订单需求情况，车辆根据调度指示从配送中心出发，依次为客户需求点提供配送服务，完成配送任务后，需要回到配送中心。车辆为客户配送服务的过程中，客户需求是动态变化的。需要解决的问题是：如何在以运输成本最小为目标的前提下，通过智能调度完满足客户动态变化的需求。

1.2 模型的基本假设

1）物流配送过程是单纯的送货过程，配送的是同一类型的产品，配送车辆在完成任务后需要回到配送中心；

2）客户的需求都是不可拆分的，每个客户的需求只能由一辆车为其服务，不可拆分成两辆及两辆以上的车辆为其服务；

3）假设车辆在行驶过程中匀速行驶，不考虑交通堵塞及天气环境的影响；

4）车辆到达客户点立刻可以对其进行服务，无等待时间。

2 模型构建

基于上述的问题描述和假设条件，对符号定义如下：

N={0，1，2，…，n}：配送中心与n个客户点集合；

0，n+1：配送中心；

dij：任意两个客户点之间的距离；

M：配送中心的车辆数；

K：配送中心的车型数；

Qk：车型为k的车辆容量；

Fk：第k种车型车辆的发车成本（包括折旧费用和司机工资薪酬）；

qi：客户i的需求量；

[ei，li]：客户i要求车辆达到的时间窗，i∈N；

ek1：第k种类型车辆空载时的单位距离油耗成本；

ek2：第k种类型车辆在满载时的单位距离的油耗成本；

pijmk：车型为k的车辆从客户i处到客户j处的实际装载率；

vk：车型为k的车辆行驶速度；

wijmk：车型为k的车辆m从客户i处到客户j处的实际运输量；

si：配送车辆在客户i处的服务时间；

ti：车辆达到节点i的时间点，i∈N；

c（tim）：配送车辆m在客户i需要承担的惩罚成本，ai是配送车辆早于客户点i要求的最早到达时间的单位时间惩罚成本，bi是车辆晚于客户要求的最晚到达时间的单位惩罚时间成本，bi＞＞ai且（其中ai与bi可用来反应客户的重要程度，客户越重要，ai与bi的设置就越大）：

S：支路消去约束集。

2.1 初始送路径规划模型

目标函数如下：

式(4)总配送成本最小，第一项表示车辆发动的固定成本，第二项时是油耗成本，第三项是车辆早到或者晚到的惩罚成本；式(5)表示车型为k的车辆m从客户i到客户j的实际载重率；式(6)表示车型为k的车辆运输货物总量不得大于车辆本身的最大载重量；式(7)客户i只能由某一辆车提供配送服务，不得拆分成两辆或两辆以上的车辆提供配送服务；式(8)、式(9)表示车辆为客户服务结束，必须要从该客户点驶出，保证驶入车辆等于驶出车辆；式(10)表示配送车辆必须从配送中心出发，在完成配送任务之后必须返回配送中心；式(11)表示车型为k的车辆m从客户i处到客户j的运输量要大于客户j的需求量；式(12)表示车型为k的车辆m从客户i处出发，到达客户j的时间；式(13)表示车辆从配送中心出发时是满载状态；式(14)表示支路消除约束，即避免不完整的行驶线路。

2.2 实时优化阶段模型

本文采用定时的批量处理策略，将工作日划分为若干个时间段，每个时间节点设为关键时间点，现假设关键时间点为Th，在这个时间段里总计出现了H个新的新客户需求信息，其中包括了初始客户的需求量增加至超过配送车辆的剩余装载量的部分。此时，设初始阶段已经服务结束h个客户，初始阶段已经派出车辆Mv（Mv≤M），派出的车型数为Ka，由于初始配送已经开始配送服务，调度中心无法直接安排调度，则假设初始配送车辆在关键时间点的位置为虚拟的配送中心。Qkm为派出的车型为k的车辆m的剩余载重量，在Th时刻，未服务的客户数为n-h+H。设还需派出车辆为p辆（m=Mv+1，Mv+2，…，Mv+p），车型总量为Kb。客户编号为：h，h+1，…，n-h+H（Y=n-h+H）。

则实时优化阶段的数学模型如下：

式(15)是表示的是目标函数：总配送成本最低，第一项表示实时阶段车辆从配送中心出发的固定成本，第二项表示实时调度的车辆运输的油耗成本，第三项表示初始配送车辆继续行驶花费的油耗成本，第四项表示车辆延迟或者早到服务点的惩罚成本；式(16)表示车型为k的车辆m从客户i行驶至客户j的实际载重率；式(17)表示各位于配送路中的车辆的剩余装载量可以满足剩余需要配送客户点的需求量之和；式(18)表示客户i的需求只能由一辆车完成，即客户点i的需求不可拆分为两辆或两辆以上车辆配送；式(19)和式(20)表示变量之间的关系，即车辆为客户服务结束，必须从该客户点驶出；式(21)表示在为下一个客户服务之前就可以确定车辆的剩余载重量客户满足这个客户的需求；式(22)表示到达连续服务的两个客户的递推时间；式(23)表示实时派车时车辆从配送中心满载出发状态；式(24)表示支路消去约束，即避免构成不完整线路的行车路线。

3 动态需求路径优化求解算法

由于遗传算法具有在搜索过程中不易陷入局部最优、搜索速度快、运行时间短的优点，故本文采用遗传算法进行运算。在初始阶段，采用遗传算法得到初始配送阶段车辆配送的具体线路；在实时优化阶段，在关键时间点，对动态变化的需求信息进行统计，将其转化为静态的车辆路径问题进行求解，采用遗传算法进行运算，得到实时阶段车辆配送线路。以下是遗传算法的算法设计：

步骤1：染色体编码

运用将已经编号的客户点依次排列的方法，根据车辆的装载约束条件，按照一定顺序将客户点安排到车辆的配送路径中；

步骤2：种群初始化

完成染色体变化后，随机产生若干初始个体的种群；

步骤3：适应度函数

本文模型中的目标函数是运输成本最小，适应度值选取运输成本与超载成本之和，超载成本是装载量违反约束的重量与惩罚系数的乘积，只有当超载成本≤0时，才能得到可行解。运输成本与超载成本之和越小，适应度值就越小。

步骤4：选择操作

本文采用的是轮盘赌规则，计算当前个体的适应度值，通过比较，选择比较优的个体进行下一代。借鉴幂律概率选择[21]的方式，质量越好的个体的概率越大，被选择的机会越大。对适应度值进行排列，选出最差的适应度值，通过式(25)得出种群个体的等级：

其中Xi表示当前种群个体，Xw表示表示最差的适应度值，β表示放大系数，通过放大系数缓解极端情况出现。个体被选择的概率为，适应度值越小，在整个种群中所占的比例就越大，进入下一代的概率就越大。

步骤5：交叉操作

交叉方式包括单点交叉、多点交叉、算数交叉、均匀交叉等，本文采用算术交叉的方法进行交叉操作，即将两个种群个体利用线性组合的方式进行交叉，得到两个新的个体。1）确定个体线性交叉的系数∂；2）根据式(26)进行交叉操作形成两个新的个体。

步骤6：变异操作

在某条染色体上任取几个点，将其所在位置进行逆转，从而得到一个新的染色体；

步骤7：新旧种群合并

采用精英保留策略，即将父代种群与生成的交叉个体和变异个体进行合并。

4 实证分析

以WX市JLD物流公司的配送数据作为案例进行研究，JLD物流公司的运输领域包括航海运输、航空运输和陆地运输，陆运业务包括长途、短驳、城际运输三大模块，本文的研究对象是短驳组的运输情况。目前短驳组最大的问题是在根据客户需求进行了车辆调度的情况下，出现了动态客户需求时，如何实时调度车辆满足客户配送需求的同时达到运输成本最小，故收集了JLD物流公司短驳组2019年某日的需求数据，配送中心的坐标为（120.277757，31.489746），初始客户需求信息如表1所示。JLD公司对客户进行了ABC分类，A类客户是最重要的客户，ai=15元/小时，bi=50元/小时，C类客户是最不重要的客户，ai=5元/小时，bi=30元/小时，B类客户的ai=10，bi=40元/小时，短驳组共有三种类型的车辆，车辆的相关参数如表2所示。JLD配送中心自有车辆共有9辆车，其中有4辆5t型号的车，3辆8t型号的车，2辆20t型号的车。假设车辆在行驶过程中是匀速行驶，不考虑天气和交通堵塞的情况，v=30km/h。车辆每天7点从配送中心出发为客户配送货物。由于配送中心无法预知动态客户的需求信息，因此在制定配送线路时，为了能对动态需求作出快速响应，假设车辆从配送中心出发时是满载状态，用有效装在率来衡量车辆配送路径优化的效果。

表1 初始客户需求信息

表1（续）

表2 配送中心使用的车型参数

以Th=9.5作为关键点，汇总在9.5h之前出现的动态需求信息。新的客户需求信息如表3所示。

表3 新的客户需求信息

利用遗传算法对初始配送路径规划模型进行运算，结果如下：运算时间为103.472647秒，迭代次数为1072时得到最优解，最小运输成本为3956.5062元。具体运输线路如表4所示，算法的进化过程如图1所示，初始配送方案如图2所示。

图1 遗传算法进化过程图

图2 初始配送方案

表4 初始配送路径优化结果

利用遗传算法对实时配送路径规划模型进行运算，结果如下：运算时间为46.740466秒，迭代次数为311次时得到最优解，最小运输成本为4877.393元。优化结果如表5所示，算法的进化过程如图3所示，实时配送方案如图4所示。

表5 实时配送路径优化结果

图3 实时优化阶段遗传算法进化过程图

图4 实时配送方案

由上述结果可以发现：

1）两阶段模型可以快速的对新的客户需求做出响应，在实时优化阶段，增加了一辆5t车辆和一辆8t车辆提供配送服务。5t的车辆为客户36、14、27提供配送服务，有效装载量为4.9t，有效装载率为98%。8t的车辆为新增客户37、35、32、38、33、31提供配送服务，有效装载量为7.85t，有效装载率为98.125%；

2）两阶段模型可以在一定程度上提高有效装载率。车型为8t的车辆5在初始配送阶段的有效转载量为7.7t，在实时优化阶段的有效装载量为7.85t，有效装载率增加了1.875%；车型为20t的车辆8在初始配送阶段的有效装载量为19.003t，在实施优化阶段的有效装载量为19.503t，有效装载率提高了2.5%；

3）两阶段模型可以在一定程度上减少因早于或晚于时间窗到达的惩罚成本。车型为8t的车辆5在实时优化阶段根据新增客户点调整配送线路，惩罚成本从21.5037元减少为0元。总惩罚成本从初始配送阶段的181.8875元减少实时优化阶段至177.6673元，减少了4.2202元。

在实际配送中，JLD采用的是专人专车专线路的原则，每个司机专门负责一辆车，责任到人，根据历史成本数据可以发现专人专车的原则有效的缓解了车辆的损坏率以及减少了车辆的维修成本。采用专线路的原则是因为客户对JLD的配送要求很高，规定了在客户厂区内的行驶线路以及速度等，并且考虑了司机与客户仓库员工熟悉程度会影响到装卸搬运的效率。然而通过分析大量数据，在实际操作过程中，采用专线路原则的必要性不强，同时导致了车辆的装载率非常低，以及自有车辆的使用效率也很低。实际调度过程中JLD派出了9辆自有车辆，同时安排了6辆外包车辆进行了配送。动态需求路径方案与JLD实际配送方案的对比如表6所示。

表6 方案对比

由表6可以发现，利用动态需求的多车型车辆路径优化模型，JLD的9辆自有车辆完全可以满足客户的配送需求，只需要8辆车辆即可满足配送需求，比实际调度结果节约了7辆车，不需要外包车辆进行配送，配送车辆数优化了46.667%，运输成本节约了1853.297元，优化了27.53%。基于动态需求的多车型模型为JLD减少了配送车辆数并降低了运输成本。两阶段模型根据运输成本最小化进行路径优化，改变了JDL公司专线路的原则。

5 结语

论文针对路径优化问题中客户需求是动态变化的、配送中心拥有多种型号的车辆以及客户提出了需在时间窗提供配送服务等特点，展开了一系列研究。首先根据客户的需求是动态变化的特征，建立了两阶段的模型，通过关键点将动态变化的需求转化为静态问题，在初始配送路径阶段，运用了遗传算法进行了求解分析，得出了初始阶段的车辆配送线路；在实时优化阶段，运用了遗传算法进行了分析求解，得出了在出现新的客户需求时的配送路径方案；其次，针对不同车型的车辆在运输过程中油耗成本会不同的特点，考虑了运输成本会与配送车辆的实际装载率、运输距离成本之间的关系，改变以往只以运输距离最小化为目标函数的情况，更加客观全面的描述了不同车型对配送线路的影响；接下来，考虑了时间窗对配送线路的影响，迟到或早到都会产生惩罚成本；最后，通过JLD公司这一实际案例验证模型的优化效果，改变了JLD原有的专线路原则，重新规划运输线路，发现两阶段模型的优越性，可以快速的对动态需求作出高效的响应、提高有效装载率、减少惩罚成本，并将得出的结果与JLD实际配送情况进行对比分析，发现通过建立动态需求的多车型模型解决了JLD短驳组目前最大的配送难题，可以根据动态客户需求信息实时更新配送线路，同时起到了降低运输成本和减少配送车辆数的作用，对长途组、城际配送组的配送也有一定的借鉴意义。未来将结合交通流进行研究，不再假设车辆为匀速行驶，分析交通流对车辆配送线路的影响。