需求可拆分的节点具有双重需求的车辆路径问题研究进展

，

(中南大学 交通运输工程学院， 湖南 长沙 410075)

一般车辆路径问题(vehicle routing problem，VRP)中各客户点仅具有送货需求或取货需求， 即纯送(取)货车辆路径问题。 随着逆向物流的快速发展及环保政策的切实落实， 实际操作中需要对一部分客户点送货， 对另一部分客户点取货， 于是产生了取送货问题(general pickup and delivery problem，GPDP)。 无论是VRP还是GPDP， 客户更愿意接受以尽可能少的服务访问次数下完成所有需求。 目前大部分的研究都是针对每个客户点的需求只能由一辆车服务， 即需求不可拆分的问题类型， 但是， 在实际运行中，客户需求被拆分运输的情况并不少见，例如不同货物需要不同的运输工具及装卸设备，将客户需求根据货物类型特性分类运输， 可提高作业物流作业效率。 具有集中管理制度的中心物流配送中心可以为需求拆分运输模式提供技术及设备支持。

已有理论研究及事实证明，需求可拆分的运输方式有利于充分利用车辆装载能力和降低车辆行驶成本。Dror等[1-3]首次提出需求可拆分的纯送(取)货车辆路径问题(split delivery vehicle routing problem，SDVRP)，此后越来越多学者致力于需求可拆分问题领域的研究，但是较少有针对GPDP需求可拆分问题类型的研究。2005年，Mitra[4]和Nowak[5]分别就不同类型GPDP考虑需求可拆分的运输模式，开启了需求可拆分的取送货问题(GPDP with split loads，GPDPSL)的研究。本文中提出了适用于各种节点具有双重需求的车辆路径问题(SVRPNDD)的数学模型，分析比较各种问题的特性，并归纳总结各种问题算法的研究进展。

1 GPDP分类

在已有研究中，不同学者从不同角度、不同准则对GPDP进行分类。大部分GPDP中假设所有客户点均只能被访问一次，即需求不可拆分类型。借鉴Parragh等[6-7]提出的分类准则，本文中将GPDP划分为2个不同问题类型。在第1类问题中，所有配送货品必须由单一(或多个)配送中心发送至各收货客户点，且从各具有发货需求的客户点收集的货品必须全部运送回配送中心，此类问题统称为带回程的车辆路径问题(vehicle routing problems with backhauls，VRPB)。需要说明的是，目前大部分VRPB的经典定义是假设运输方式为“先取后送”形式，在Parragh等[6-7]的问题定义及分类中，归类为带聚类回程的车辆路径问题(VRP with all linehauls before backhauls或VRP with clustered backhauls，VRPCB)。在第2类问题中，取送货需求存在于各客户点之间，本文中定义为收发问题(pickup and delivery problem，PDP)。借鉴王科峰等[8-10]的研究，本文中根据客户节点具有的需求类型情况，进一步将VRPB细分为节点具有单一需求的车辆路径问题(VRP with nodes of single demand，VRPNSD)及节点具有双重需求的车辆路径问题(VRP with nodes of double demands，VRPNDD)。VRPNSD中所有客户点只能具有取货或送货中的一种需求，而VRPNDD中客户点可同时具有取货及送货2种需求。PDP根据发、收货客户是否对应分为2个子类，即不对称的PDP及对称的PDP。为了便于理解，将GPDP分类进行归纳，如图1所示。

图1 取送货问题分类

1.1 VRPNSD概述

VRPNSD中的客户被分为配送客户(只具有送货需求)及集取客户(只具有取货需求)。假设所有客户集为N，配送客户集为D，集取客户集合为P，则有N=D∪P且D∩P=○/。若任意车辆只有在访问完路径中的所有配送客户后才能开始对集取客户进行访问，则称此类问题为VRPCB。如果问题对送货服务及取货服务顺序无约束，则为混合取送货车辆路径问题(VRP with mixed linehauls and backhauls，VRPMB)。

1.2 VRPNDD概述

VRPNDD中客户可同时具有取货及送货2种需求，即客户可能既是配送客户，也是集取客户。同时取送货的车辆路径问题(VRP with simultaneous delivery and pickup，VRPSDP)是VRPNDD的代表类型。值得注意的是，VRPSDP假设所有客户需求均不得大于车辆最大装载能力。

Parragh等[6-7]将取送货可分割的车辆路径问题(VRP with divisible delivery and pickup，VRPDDP)列入VRPB中，VRPDDP中同时具有取货及送货需求的客户，允许被访问2次，一次完成取货服务，一次完成送货服务，即客户需求可能被拆分成2次。由于本文中假设GPDP中所有客户不允许被拆分运输，因此将VRPDDP列为VRPNDD类型。

2 GPDPSL的研究现状

针对GPDPSL的研究，Mosheiov[11]于1998年最早提出了单位需求(single-unit demand)的假设。在此假设下，客户的任意需求(取或送)均可以最小计量单位进行拆分，从而由多辆车运输。Nagy等[12]虽然在研究中未直接考虑GPDPSL，但是针对GPDP特别设计了一组算法求解邻域，其中包括“Neck”与“Unneck”一组对偶算子，分别用于对客户需求进行拆分及合并。

GPDPSL研究的正式开端可追溯至2005年，Mitra[4]首次将需求可拆分运输方式引入VRPSDP中， 并在文献[13]中正式定义该类问题为需求可拆分的同时取送货车辆路径问题(vehicle routing problem with split pickups and deliveries，VRPSPDP)。更多学者也致力于GPDPSL领域研究，包括研究其求解难度、问题特性、最优解特性及求解算法等。图2所示为全球在GPDPSL领域研究论文的发表数量。从图中可以看出，该问题在早期的研究成果相对较少，近年来呈增长趋势。

图2 需求可拆分的取送货问题(GPDPSL)研究论文发表情况

已知GPDP分为2个大类，本文中也相应地将GPDPSL分为2类，即需求可拆分的带回程的车辆路径问题(VRPB with split loads，VRPBSL)及需求可拆分的收发车辆路径问题(PDP with split loads，PDPSL)。已有研究中，PDPSL的研究热度略高于VRPBSL的，两者的比例大致为56∶44。

2.1 VRPBSL研究现状

VRPBSL同样可以分为2大类，即需求可拆分的VRPNSD(split VRPNSD，SVRPNSD)及需求可拆分的VRPNDD(split VRPNDD，SVRPNDD)。自Mitra[4]开始VRPSPDP研究以来，随后更多学者聚焦VRPBSL领域研究。Lai等[14]将需求可拆分操作模型引入VRPCB，提出需求可拆分的VRPCB(split VRPCB，SVRPCB)，这也是目前针对SVRPNSD的唯一研究文献。可见，绝大多数的VRPBSL研究均是针对SVRPNDD的，其比例约占95%。本文中分析认为，这是因为SVRPNDD更加贴合实际运输活动的复合型，所以具有更重要的研究意义及更强的实用性。如果假设SVRPNDD中具有双重需求的客户中的某一项需求为0，则SVRPNDD即可转换成SVRPNSD。

2.2 PDPSL研究现状

2005年Nowak[5]首次针对PDPSL进行研究，并在后续几年继续对该领域进行较全面的研究[15-17]。在已有研究中，针对PDPSL的研究大部分是基于实际应用问题的，特别是应用于海上商贸运输，其比例约占60%，其余的32%、8%分别是关于理论及算法和其他应用。近年来，PDPSL研究问题呈现较大的个性化趋势，这里不进行详尽阐述。

3 SVRPNDD研究进展

目前大部分SVRPNDD研究以VRPSPDP问题为主，其比例占到85%，其中Mitra[4,13]为VRPSPDP的研究奠定了基础，王科峰等[8-10]深入研究VRPSPDP问题特性，为该问题研究提供了更加详尽的理论依据。文献[18-19]中在解决现实第三方物流案例时采用VRPSPDP模型，考虑时间窗限制，提出了带时间窗的VRPSPDP(VRPSPDP with time windows，VRPSPDPTW)。Yin等[20]提出一种特殊的VRPSPDP，对各客户点拆分次数进行限制(最多只能被拆分2次)，且行驶路径不能超过最大长度的限制。2017年，Wassan等[21]将VRPDDP以需求可拆分类型问题呈现在学者面前，Nagy等[22]进而就VRPDDP需求可拆分特性进行深入、全面的研究，拓展了研究领域。2005—2017年12月全球SVRPNDD领域研究论文的发表情况如图3所示。

3.1 问题描述与数学模型

SVRPNDD可统一表示为无向图G=(V，E)，其中V={0，1，2，…，n}代表配送中心及客户点的集合，其中0表示配送中心，{1,2,…,n}表示客户点的集合；E表示边集。

SVRPNDD旨在满足下列约束条件的情况下求得最小运输成本(使用最少车辆数使得行驶总路程最短)：

VRPSPDP—需求可拆分的同时取送货车辆路径问题；VRPDDP—取送货可分割的车辆路径问题。

1) 所有车辆离开同一车场， 并最终返回该车场；

2)所有车辆装载能力相同，车辆的实际装载量不得超过该车最大装载能力；

3)各客户点可同时具有收取、发送2种需求，且任意类型需求量可能大于车辆装载能力；

4)客户总需求量可同时被不只一辆车访问，或被同一辆车服务1次以上；

5)任意车辆对客户点取、送服务无顺序要求；

6)无时间窗及最长路径距离限制。

通常认为，多用一辆车所产生的固定费用总是超过总行驶费用减少带来的节省，因此即使存在不进行最小车辆数限制，可能求解得到总行驶距离更短的情况，问题仍然设定最小车辆数K为已知参数。最小车辆数为

式中：「⎤表示向上取整；D为总送货量；P为总取货量；Q为车辆最大装载能力。

大部分考虑带时间窗的问题初始条件并未设定最小车辆数约束，原因是增加时间窗约束会导致问题求解变得更加困难。为了能在接受的时间内得到满意解，允许使用尽可能少而非最少的车辆完成服务，但是，Tang等[18]得出结论是，在一个时间窗内，需要的最小车辆数与非时间窗约束下问题使用的最小车辆数相等，且在一个时间窗内，存在一个可行方案，其所需车辆数为问题最小车辆数。

SVRPNDD数学模型符号说明见表1。

表1 需求可拆分的同时取送货车辆路径问题的数学模型符号及说明

SVRPNDD的数学模型为

(1)

s.t.

(2)

(3)

(4)

(5)

(6)

(7)

(8)

yij,zij≥0

，

(9)

xijk≥0,xijk∈+

，

(10)

式中：i,j∈{0,1,…,n}；k∈{1,2,…,K}。

目标函数(1)为最小化车辆行驶总路程；约束条件(2)—(3)保证所有客户点的需求均被满足；式(4)—(5)确保离开配送中心时，车上没有收集的货物，当车辆返回车场时，车上没有待配送给客户点的货物；约束条件(6)表示车辆访问某点的次数等于离开该点的次数；条件(7)表示每辆车仅离开配送中心1次，并最终返回配送中心；约束条件(8)保证车辆的实际装载量不超过其最大装载能力；式(9)—(10)表示变量约束。

也有学者描述目标函数时，把最小化车辆使用数量作为第1层优化目标，最小化车辆行驶费用作为第2层优化目标，即

(11)

式中P1、P2(P1>>P2)与目标规划中的定义一样，为优先因子，是定性的概念，不赋予具体数值，只表示各目标的优先级。若固定费用和行驶费用都能准确度量，则也可以用统一的费用量纲表示，转化为单目标优化函数，直接进行求和来比较优劣，即

(12)

式中w1、w2分别表示单位车辆使用费和单位行驶距离行驶费用。Mitra[13]在研究VRPSPDP过程中给出一种假设，令w1=100，w2=0.1。Ai等[23]在考虑VRPSDP时，假设w1=100,w2=1。

VRPSPDP中对各客户被拆分的次数无限制，可直接采用SVRPNDD数学模型。因为VRPDDP对客户拆分方式及次数有限制，各客户需求最多只能被拆分2次，所以需要在SVRPNDD模型中修改约束条件(10)为

0≤xijk≤2,xijk∈+,i,j∈{0,1,…,n},k∈{1,2,…,K}。

(13)

又因为VRPDDP中能够被拆分的客户只能是具有双重需求的客户，且被拆分的2次服务中，一次完成全部送货需求，一次满足所有取货需求，所以SVRPNDD模型中的式(7)需要替换为

x0jk∈{0,1},j∈{0,1,…,n},k∈{1,2,…,K}，

(14)

xi0k∈{0,1},i∈{0,1,…,n},k∈{1,2,…,K}。

(15)

3.2 问题特性

纵观已有SVRPNDD研究，主要研究重点为问题的算法求解，针对问题本质特性的专项研究较少。问题特性的主要成果来自于王科峰等[8-10]。文献[9]中指出，SDVRP是SVRPNDD中当客户点送货和取货2种需求之一为0时的特例，因此节点需求的双重性带来的问题结构方面的改变，使得SVRPNDD比只有单一需求的SDVRP在固有性质方面的研究更为困难。在研究SVRPNDD特性时，学者们通常会将其与SDVRP进行比较。

3.2.1 计算复杂度

3.2.2 最优解特性

问题最优解特性是研究SVRPNDD的首要关键所在。虽然SVRPNDD是SDVRP的扩展，但是，在最优解的性质方面两者之间存在着明显的差异。其原因是SVRPNDD中客户点可以同时具有取货及送货2种需求，且2种需求相互制约。王科峰等[10]指出，目前直接研究SVRPNDD与SDVRP最优解性质的差异还存在困难。

已知的SDVRP重要最优解特性见定理1、 2。

定理1[1]若距离矩阵满足三角不等式， 则SDVRP最优解中任意2条线路最多只存在一个公共点。

定理2[1]若距离矩阵满足三角不等式， 则SDVRP最优解中不存在k-拆分循环，k≥2。

定理3[25]若距离矩阵满足三角不等式，则SDVRP最优解中需求拆分点的个数少于路径数。

王科峰等[8-9]研究了SVRPNDD是否具有与SDVRP相同的最优解特性， 论证得出结论， 在SVRPNDD的最优解中， 2条路径间可能存在不止一个公共点， 与定理1不符。 同时VRPSPD中解的一条路径中含有子回路的路径相对于不含子回路的路径可能会使行驶距离更短， 与定理3性质相异。 Nagy等[22]也指出， VRPDDP最优解不符合定理1及定理3， 且实际需求拆分点的个数没有数量上限约束。

对比SDVRP最优解特性，可得出SVRPNDD最优解特性如下：1)若距离矩阵满足三角不等式，则SVRPNDD最优解中任意2条线路可存在多个公共点；2)若距离矩阵满足三角不等式，则SVRPNDD最优解中路径中可能存在子环；3)若距离矩阵满足三角不等式，则SDVRP最优解中需求拆分点的个数无上限约束。

3.2.3 可还原性

王科峰等[8]研究了VRPSPD是否有与Archetti等[24-25]提出的SDVRP可还原性相类似的性质，给出SVRPNDD可简化性定义。

定义2[8]当客户点的取货、送货需求都大于或等于车辆最大装载能力Q时，车辆满载Q单位货物，从车场出发直接到达该客户点，在卸下车场运送来的Q单位货物的同时，装载需要运走的Q单位货物，然后直接返回车场的运输过程，称之为直送(out-and-back)运输操作。

定义3[8]若存在客户点i的集货、送货需求均大于或等于车辆最大装载能力Q，求得SVRPNDD的最优解必须先通过对节点i进行若干直送服务，直到该节点的收货或送货需求其中一个小于Q时直送服务停止。通过这种操作方式将问题简化为求解一个新的SVRPNDD，则称该SVRPNDD是可简化的。

定义3与Archetti等[24-25]提出的SDVRP可还原性的定义方式相同， 王科峰等[8]经论证提出， 如果问题距离矩阵对称且满足三角不等式， 则只有当Q=1时，SVRPNDD是可简化的。

3.2.4 成本节约

Archetti等[26]研究证明了客户平均需求量与车辆装载能力的关系是SDVRP成本节约的最大影响因素。 只有当该因素满足一定条件时， 才能使SDVRP获得较大的成本节约。同时，SDVRP带来的成本节约首先来源于需求可拆分所导致的车辆使用数的减少。虽然SVRPNDD与SDVRP在最优解的性质方面存在明显的差异，但是在问题成本节约情况及特点方面存在许多共同之处。

Dror等[1]通过算例证明，当客户需求量与车辆装载能力差异较小时，SDVRP的解较VRP并没有太大的改进。当平均客户需求量大于车辆装载能力的10%时，需求拆分运输将带来明显成本节约。该结论同样适用于SVRPNDD。

Wang等[27]指出，当平均客户需求量为车辆最大装载能力的50%，且需求量方差较小时，需求拆分运输将带来的最大运输成本节约。该结论与Archetti等[26]的研究结论一致，即SDVRP带来的成本节约情况受客户需求量方差影响。不同的是，Wang等[27]指出SVRPNDD带来的成本节约受客户点的位置分布及聚类情况影响，而Archetti等[26]得到的研究结论与之相异，即SDVRP不受客户点的位置分布影响。

综上所述，SVRPNDD及SDVRP在成本节约方面的结论基本一致，两者的比较如表2所示。

表2 需求可拆分的纯送(取)货车辆路径问题(SDVRP)与需求可拆分的节点具有双重需求的车辆路径问题(SVRPNDD)在成本节约方面的比较

Nagy等[22]通过算例测试及分析发现，当VRPDDP能够得到较大成本节约时，往往发生在客户2种需求量差异较大的情况。同时，文中进一步分析总结得到最优可能被拆分的客户点一般具有如下特点，其中以1)尤其显著： 1)客户点邻近配送中心(车场)； 2)客户点某一需求量明显较大； 3)客户点位于某一较为密集的客户点群中。

同时在文献[22]中研究VRPDDP通过取送、送货拆分运输的操作方式给对应VRPSDP能够得到最大的成本节约，给出定理4，与Archetti等[28]针对SDVRP的研究结论相符。

3.3 求解算法

已知SVRPNDD是NP-难问题，高效的求解算法研究是解决该问题的重要途径。已有研究中，大部分学者采用启发式算法，原因是规模较大的问题中，即使在VRPNDD模型(需求不可拆分的运输方式)中能够轻松求解，相应的SVRPNDD模型也不一定能够求得问题最优解。这是因为各客户点被拆分的次数在SVRPNDD模型中是决策变量，所以会使整数规划模型产生巨大的不完整空隙。

精确算法只能求解小规模的NP-难问题，已有SVRPNDD的求解算法研究均采用启发式算法。早期的算法研究主要以构造启发式算法为主，特别是元启发式算法(metahueristics，也称智能优化算法、超启发式算法、亚启发式算法、通用启发式算法等)及混合启发式算法已成为求解SVRPNDD的主要研究方向。

构造启发式算法的研究主要出现在该领域研究早期(2005—2012年)[4,11,18-19,29-30]，其中主要通过先聚类后路径(cluster-first-route-second)方法求解。在聚类阶段，学者们通过各种贪婪算法生成初始路径方案，再结合最短路及智能算法对解进行优化。

在路径优化阶段，Mitra[13]与杨亚璪等[29]采用的是最短路径法，而大多数学者则是采用智能算法进行优化，其中以禁忌搜索算法的应用居多[20-22,31]。除此外，还包括蚁群算法[32-33]、竞争决策算法[30,34]、模拟退火算法[31]及平行算法[35]等。

4 结语

GPDP的研究对物流配送路径的确定具有重要意义及应用前景，特别是在客户点可能同时具有取货及送货2种需求的情况下，即VRPNDD问题类型。允许对客户需求进行拆分，由多辆车共同运输或由同一辆车多次运输的操作方式，能够在最大程度提高平均车辆装载率，充分利用车辆装载能力的同时，降低车辆行驶成本，带来整体运输成本节约。

近几年关于SVRPNDD的研究得到了一些富有意义的研究成果，但是无论是在理论还是求解算法方面，在深度及广度上仍有较大的研究及拓展空间。主要表现在如下2个方面：

1)相对于SDVRP，SVRPNDD在问题性质研究方面仍有很大的探索空间。目前已有的对SVRPNDD性质的研究结论大部分仍为猜测及推论，需要进一步论证和分析，例如SVRPNDD的最优解特征、成本节约情况等。

2)在实际物流实例中，客户更加倾向于较少的访问次数，或多种类货物多车型混合运输等，若在VRPSPD中考虑客户最大访问次数、多种货物或多车型混合运输等附加约束条件，将增大问题的复杂程度。同时，附加条件将限制可行解的数量，因此需要研究设计性能更好的求解算法。