需求可分割的同时送取货车辆路径问题求解

Model and Algorithm for the Simultaneous Pickup and Delivery Vehicle Routing Problem with Split Loads

摘要: 针对企业生产原料调运过程，建立多品种货物且供需未匹配情况下需求可分割的大规模送取货车辆路径问题的数学模型，以运输成本最小化为目标。提出基于车辆运输效率的启发式算法构造初始解，并采用变邻域搜索算法对初始解进行改进。测算结果表明基于运输效率的启发式算法对实际运输费用降低20%左右，加入变邻域搜索算法后对初始解有3%左右的改进。

Abstract: This paper establishes a mathematical model for a large scaled vehicle routing problem with sim-ultaneous pickup and delivery, the objective is to minimize total transportation cost. A heuristic transportation efficiency based algorithm (TEBA) is developed to gain initial feasible solution, and a local search algorithm based on the variable neighborhood search is used to improve the solution. The computational results show that the TEBA could reduce the actual cost about 20%, and an improvement can be achieved about 3% by the variable neighborhood search.

1. 引言

车辆路径调度是物流配送过程中的关键环节，其直接影响客户需求的响应速度、客户对物流环节的满意度及服务商的物流成本。以某烟草工业企业生产原料调运过程为例，该企业拥有多家卷烟厂，分布在不同的城市。原料采购后就近存放到各厂，各厂生产的卷烟品牌多达十几种，通常需要利用其它卷烟厂的原料。运输车辆从原料供应仓库所属卷烟厂的车场出发，根据生产需求将一定的原料运往有需求的卷烟厂原料仓库之后便空车返回所属车场。这种两点往返的单一送货方式带来严重的车辆空载问题，造成了运力浪费。本研究旨在将卷烟制造厂两点往返送货的原料调运过程优化为整个网络中的联合运输，以达到提升车辆利用率、减少调运车辆数、降低调运成本的目标。在联合调运网络中，每个卷烟厂原料仓库可以同时有取货需求和送货需求。每个原料仓库库存有限供应，一个仓库中某种原料的需求可能要由多个供应仓库同时供应才能满足的情况。因此，每个仓库的需求允许分批满足；各仓库之间的供需匹配关系未知。该联合调运问题可称为存在多品种货物且供需未匹配情况下，需求可分割的送取货车辆路径问题(Vehicle Routing Problem with Split Delivery and Split Pickup, VRPSDSP)。

车辆路径问题自1959年被Dantzig和Ramser [1] 提出以来，一直是优化调度研究中的热点，并衍生出诸多分支，需求可分割的车辆路径问题与送取货车辆路径问题是其中很重要的两个分支。需求可分割的送取货车辆路径问题结合了需求可分割的车辆路径问题(Split Delivery Vehicle Routing Problem, SDVRP)与同时送取货车辆路径问题(Vehicle Routing Problem with Simultaneous Delivery and Pickup, VRPSDP)的特征。SDVRP问题由Dror等(1989) [2] 提出，并且证明了在客户需求可分的情况下对客户进行分割运输，总运输距离和派车数量都能得到优化。VRPSDP问题由Min (1989) [3] 首次提出，指客户同时具有送货需求与取货需求，且当车辆服务客户时，必须同时执行送货、取货两种操作从而确保每个客户只被服务一次。在VRPSDSP问题中，客户节点既有送货需求又有取货需求，而且送货量和取货量都可通过多次运送满足。Mitra (2008) [4] 构建了该问题的混合整数线性规划问题模型，并提出两种启发式算法。针对供需已匹配的情况，Nowak等(2008) [5] 把研究问题命名为可分批的送取货问题，用运输网络的边来表示送取货问题之间的关系，且整个运输网络仅由一辆车来完成集配货任务。Nowak等(2009) [6] 研究了在多辆车的情况下，货物大小、种类以及取送货点数量等对分批运输效果的影响。Sahin等(2013) [7] 结合禁忌搜索算法与模拟退火算法求解有多辆车的VRPSDSP问题，实验结果证明在允许分批运输的情况下，车辆运输里程能够得到有效降低。Chen等(2014) [8] 研究了有多品种货物的VRPSDSP问题，考虑原料无限库存，并采用局部搜索算法求解。

本文针对存在多品种货物且供需未匹配情况下需求可分割的送取货车辆路径问题，考虑每种原料的库存量有限，构建数学模型，首先采用嵌入锁定策略的基于车辆运输效率的启发式算法获得初始解，再采用嵌入局部搜索算法的变邻域算法进一步优化初始解，得到最终优化解。

2. MUPVRPSDP问题描述及数学模型

该VRPSDP问题可以定义为一个完全图 $G=\left(N,A\right)$ ，其中 $N=\left\{0,1,2,\cdots ,n,\cdots ,n+m\right\}$ 表示节点集，它由车场集 $O=\left\{0,1,2,\cdots ,n\right\}$ (表示有n个车场)和仓库集 $W=\left\{n+1,\cdots ,n+m\right\}$ (表示有m个仓库)两个子集共同构成，同时W又可分为供应仓库集S与需求仓库集D，即 $N=O\cup W$ ， $W=S\cup D$ ；若网络中的原料种类为 $R=\left\{0,1,2,\cdots ,r\right\}$ (共r种原料)，则 $S=\left\{S_0,S_1,S_2,\cdots ,S_r\right\}$ 、 $D=\left\{D_0,D_1,D_2,\cdots ,D_r\right\}$ ，其中 $S_r$ 表示原料r的供应仓库集合， $D_r$ 表示原料r的需求仓库集合； $A=\left\{\left(i,j\right):i,j\in N,i\ne j\right\}$ 表示弧集。该网络中的每个仓库不但可以供应一种或多种原料，也可以需求一种或多种原料。因此，集合N中的每个节点i都包含多个非负权值属性，这些属性包括对原料r的需求数量 $d_{ir}$ 和可供应数量 $s_{ir}$ 。对于O中的节点i而言，需求数量 $d_{ir}$ 和可供应数量 $s_{ir}$ 均为零，即 $d_{ir}=0$ ， $s_{ir}=0$ 。集合A中的每条弧 $\left(i,j\right)$ 都包含非负属性值 $c_{ij}$ ， $c_{ij}$ 表示节点i与节点j之间的运输距离。 $K=\left\{0,1,2,\cdots ,L\right\}$ (共有L辆车)表示所有的配送车辆集合，集合K中的每辆车k都包含两个非负权值属性，即车辆k的最大载重量 $Q_k$ 和最长行驶时间 $T_k$ 。

假设所有车辆的可工作时间 $T_k$ 相同、行驶速度 $V_k$ 相同、车容量 $Q_k$ 相同，即 $T_k=T,V_k=V,Q_k=Q$ ；每个仓库的装卸时间为0。令 $K_i$ 表示分配给车场i的车辆集合； $L_{ijr}^k$ 表示车辆k在弧 $\left(i,j\right)$ 上运输原料r的数量； $y_{ij}$ 为0~1变量，当 $y_{ij}=1$ 时，表示节点i,j属于同一卷烟厂，由于每个卷烟厂都有唯一的车场，因此，也可认为节点i,j同属一个车场，否则， $y_{ij}=0$ ；同样地， $z_{ok}$ 也是0~1变量，当 $z_{ok}=1$ 时，表示车辆k属于车场o，否则 $z_{ok}=0$ 。最后，引入决策变量 $q_{ir}^k$ 及 $x_{ij}^k$ 。当 $i\in S_r$ 时， $q_{ir}^k$ 表示车辆k在仓库i装载原料r的数量；当 $i\in D_r$ 时， $q_{ir}^k$ 表示车辆k在仓库i卸载原料r的数量。 $x_{ij}^k$ 为如下0~1变量：值为1时，表示车辆k经过弧 $\left(i,j\right)$ ；否则值为0。基于上述约束条件，该VRPSDP问题的数学模型可描述为：

目标函数：

$\min P\underset{k\in K}{{\displaystyle \sum }}\underset{r\in R}{{\displaystyle \sum }}\underset{i\in N}{{\displaystyle \sum }}\underset{j\in N,j\ne i}{{\displaystyle \sum }}{c}_{ij}{L}_{ijr}^k$ (1)

约束条件：

$\underset{j\in S}{{\displaystyle \sum }}{x}_{ij}^k{y}_{ij}{z}_{ik}\le 1\forall i\in O,k\in K$ (2)

$\underset{j\in D}{{\displaystyle \sum }}{x}_{ji}^k{z}_{ik}\le 1\forall i\in O,k\in K$ (3)

$L_{ojr}^k=L_{jor}^k=0\forall o\in O,j\in W,k\in K,r\in R$ (4)

$x_{o_i{o}_j}^k=0\forall o_i,o_j\in O\left(i\ne j\right),k\in K$ (5)

$\underset{i\in O}{{\displaystyle \sum }}{z}_{ik}=1\forall k\in K$ (6)

$\underset{i\in O}{{\displaystyle \sum }}{y}_{ij}=1\forall j\in W$ (7)

$\underset{k\in K}{{\displaystyle \sum }}\underset{j\in W}{{\displaystyle \sum }}{x}_{ij}^k\le \left|K_i\right|\forall i\in O$ (8)

$\underset{i\in N}{{\displaystyle \sum }}{x}_{ii}^k=0\forall k\in K$ (9)

$\underset{i\in W}{{\displaystyle \sum }}{x}_{ij}^k\le 1\forall k\in K,\forall j\in W\left(i\ne j\right)$ (10)

$\underset{k\in K}{{\displaystyle \sum }}{q}_{ir}^k\le s_{ir}\forall i\in S,r\in R$ (11)

$\underset{k\in K}{{\displaystyle \sum }}{q}_{ir}^k=d_{ir}\forall i\in D,r\in R$ (12)

$\underset{r\in R}{{\displaystyle \sum }}{L}_{ijr}^k\le Q{x}_{ij}^k\forall i,j\in N\left(i\ne j\right),k\in K$ (13)

$L_{ijr}^k-x_{ij}^k{q}_{jr}^k=x_{ij}^k{L}_{jpr}^k\underset{p\in N,p\ne j}{{\displaystyle \sum }}{x}_{jp}^k\forall i\in N,j\in D_r\left(i\ne j\right),k\in K,r\in R$ (14)

$L_{ijr}^k+x_{ij}^k{q}_{jr}^k=x_{ij}^k{L}_{jpr}^k\underset{p\in N,p\ne j}{{\displaystyle \sum }}{x}_{jp}^k\forall i\in N,j\in S_r\left(i\ne j\right),k\in K,r\in R$ (15)

$\underset{k\in K}{{\displaystyle \sum }}\underset{i\in S}{{\displaystyle \sum }}{q}_{ir}^k=\underset{k\in K}{{\displaystyle \sum }}\underset{j\in D}{{\displaystyle \sum }}{q}_{jr}^k\forall r\in R$ (16)

$\underset{i\in N}{{\displaystyle \sum }}\underset{j\in N,j\ne i}{{\displaystyle \sum }}{x}_{ij}^k{c}_{ij}/V\le T\forall k\in K$ (17)

$L_{ijr}^k\ge 0\forall i,j\in N\left(i\ne j\right),k\in K,r\in R$ (18)

$q_{ir}^k\ge 0\forall i\in N,k\in K,r\in R$ (19)

在上述模型中，式(1)为目标函数，表示结算运费最小，其中P为结算单价(吨公里)；式(2)~(4)表示所有配送车辆必须空车从所属车场出发，并首先访问属于同一卷烟厂的仓库，访问若干仓库后最终空车回到所属车场；式(5)表示配送车辆不能直接从车场行驶到车场；式(6)表示每一部配送车辆都只属于某一个车场；式(7)表示每个仓库只属于某一个烟厂；式(8)表示每个车场参与配送的车辆数目不能超过其所拥有的车辆总数；式(9)表示任意仓库不能被同一辆车连续访问两次；式(10)表示每个仓库的需求可以不用一次满足，即同一需求仓库可以被不同的车辆访问，但最多只能被同一辆车访问一次；式(11)表示所有配送车辆在某供应仓库装载的某原料数量不得超过该供应仓库对该原料的可供应量；式(12)表示所有需求仓库的需求量都必须得到满足；式(13)表示任一路径中连接两个仓库的任一路段上车辆的装载量都不得超过该配送车辆的最大装载量，同时也表明当 $x_{ij}^k=0$ 时必有 $L_{ijr}^k=0$ ；式(14)、(15)分别表示配送车辆访问需求仓库和供应仓库后，装载量保持平衡；式(16)表示任一原料在其需求仓库的所有卸载量等于其供应仓库的所有装载量；式(17)表示任意车辆的行驶时间不得超过其可工作时间；式(18)、(19)为非负约束。

3. 变邻域搜索算法求解MUPVRPSDP问题

变邻域搜索算法由Mladenović和Hansen [9] 在1997年提出，并被广泛运用于求解大规模车辆路径优化问题。本文首先采用基于车辆运输效率的启发式算法(TEBA)获得当前解(初始解) S，然后通过六类不同的邻域结构从第一个邻域结构开始对当前解S进行扰动以获得邻域解S'，再采用局部搜索获得可行解S。如果S优于S，那么S = S，重新回到第一个邻域结构，即 $\beta =1$ ；否则当前解不变，并随机选择下一个邻域结构继续计算，即 $\beta =rand\left(\right)\%{\beta }_{\max }+1$ ；当 $\beta ={\beta }_{\max }$ 时，再从第一个邻域结构重新开始循环。一旦程序循环次数N = 1000或者当前解连续未改善次数N' = 500停止程序，返回全局最优方案。

3.1. 基于车辆运输效率的算法(TEBA)构造初始路径

某烟草工业企业每月运输成本以吨公里为单位结算，对于相同的运输量，车辆运输里程越短，相应运输成本越低。Chen等(2014) [8] 提出基于车辆运输效率的启发算法(Heuristic Transportation Efficiency Based Algorithm, TEBA)，该算法的核心在于寻找使运输总量与运输距离之间的比值(δ)最大化的解决方案。本研究在运用TEBA之前先锁定各需求仓库需求量最大的原料供需匹配对，确保需求仓库中需求量最大的原料最先由距离最近的仓库供应。锁定操作如下：

步骤1：先将所有仓库按原料需求总量由大到小排序，生成需求仓库序列 $\text{A}=\left\{{\text{D}}_{\text{1}}{\text{,D}}_{\text{2}},\cdots ,{\text{D}}_{\text{n}}\right\}$ ；再将各需求仓库的原料按需求量由大到小排序，生成需求仓库原料序列 $\text{B}\left({\text{D}}_{\text{i}}\right)=\left\{{\text{r}}_{\text{1}}{\text{,r}}_{\text{2}},\cdots ,{\text{r}}_{\text{m}}\right\}$ 。

步骤2：按顺序选择需求仓库，如D₁，针对D₁中需求量最大的原料r₁选择距离最近的可供应仓库标记为S₁，形成S₁-D₁供需匹配对，以此类推，对A中所有需求仓库都按需求最大的原料形成供需匹配对，共n对。

步骤3：根据库存量、需求量和车容量决定所有供需匹配对中的原料配送量，更新库存量、需求量，并计算剩余车容量。如果剩余车容等于0，将匹配与供应仓库所在的车场连接起来形成初始解中的一条路径。如果存在剩余车容量大于0，则步骤4。

步骤4：判断匹配对中是否存在其他原料的供需匹配关系，若存在，重复步骤3，直到无法再分配任何原料。更新库存量、需求量和剩余车容量。

步骤5：锁定步骤4所得的匹配对，即将该匹配对视为一个虚拟仓库，该虚拟仓库的库存及需求由原匹配仓库的库存、需求及车辆剩余车容量共同决定，举例说明见表1、表2。表1为供需仓库的库存及需求，假设剩余车容量为Q，则锁定后的虚拟仓库的库存及需求如表2所示。如此形成虚拟仓库集合C。

Table 1. Examples of inventory and demand in supply and demand matching

表1. 供需匹配中的库存及需求举例

Table 2. Examples of inventory and demand in virtual warehouse

表2. 虚拟仓库库存及需求举例

然后，按照TEBA算法构造初始解，步骤如下：

步骤1：假设初始可行解的目标值无限大：C_TEBA: = 1000000。

步骤2：生成初始子路径sub-route：从虚拟仓库集合中选择一个虚拟仓库点，再任选一个不包含于该虚拟仓库中的其他仓库，所形成的sub-route即o-i-j-o。基于sub-route，通过步骤3~7产生最优的初始解S。

步骤3：从当前线路中第一个原料仓库的第一种原材料开始依次向后面的需求仓库配送原料。然后，计算对应的δ值，选择该值最大的子路线和匹配方案，并把插入当前子路线的仓库从剩余的仓库集合中删除。

步骤4：如果剩余仓库集合中还有仓库可以插入到当前子路线中，执行步骤3；否则，把该子路线作为可行方案中的一条路线，形成新的原料仓库集合(包含虚拟仓库)，执行步骤5；如果整个网络中的所有原材料需求都已满足，则执行步骤6。

步骤5：从新的原料仓库集合中选取一个虚拟仓库、一个其他仓库，形成新的初始子路线。按步骤3中的匹配思路一样分配各种原材料的供需数量，计算δ值。同样计算所有可行子路径的δ值，选择该值最大的子路线，转向步骤3。

步骤6：获得原问题的可行方案，并停止计算。

步骤7：如果C_TEBA > C(S)，则C_TEBA = C(S)，S即为初始路径。

3.2. 邻域结构

由于供需配对关系S-D是决策变量，所以改变其中一条路线访问工厂的顺序，进而会改变其它路线工厂的供需配对关系和访问顺序。在变邻域算法中构造6类不同的邻域结构：随机删除部分S-D组合，删除一条路线内与某个客户相关的部分S-D组合，删除一条路线内与某些种类原料相关的所有S-D组合，删除某些线路内与某一种原料有关的所有S-D组合，删除某些路线内与某个客户相关的所有S-D组合，删除与某个客户有关的所有S-D组合。

3.3. 局部搜索算法

初始解经上述邻域结构扰动生成多个邻域解的同时会产生新的送货需求，为此，需要采用局部搜索算法来改进邻域解，从而满足新需求并获得可行解。局部搜索算法如下：

步骤1：对被删除的S-D组合，更新S-D中需求客户与供应客户的原料需求量和剩余库存量，生成新的需求仓库集合和供应仓库集合。同时，判断是否存在空路径，即该路径只剩下车场和第一个供应仓库，若是，则删除该路径。

步骤2：对于需求仓库集合D中仓库i对于原料r的需求量d_ir，在剩余车容量和最大运输时间限制内，基于供应表可通过如下三种方式满足。

步骤3：如果存在供应仓库能一次满足需求d_ir，那么供应仓库之后为可行插入位置；若存在多个可行插入位置，选择增加成本最小的位置作为插入点。

步骤4：如果某条路径中同时存在多个供应仓库，虽然各供应仓库的库存量都小于需求量，但总量可以满足，则最后一个供应仓库之后为可行插入位置；若存在多条路径存在该可行插入位置，选择增加成本最小的位置为插入点，并且各供应仓库的供应量按照“越近越多”的原则进行分配。

步骤5：如果所有路径中的供应仓库库存量都不能满足需求量，则按照运输成本最小(运输效率最高)的原则重新建立一条新路径。

4. 实验结果

利用某烟草工业企业2016年1~6月每月的实际调运数据测算，对实际调运费用、初始解求解结果、变邻域搜索算法求解结果三者进行比较，结果见表3。其中GAP₁为实际调运费用与基于车辆运输效率

(TEBA)求解的初始解之间的差距， ${\text{GAP}}_{\text{1}}=\left(\text{C}\left({\text{S}}_{\text{init}}\right)-\text{C}\left(实际\right)\right)/\text{C}\left(实际\right)\times 100\%$ 。GAP₂则为初始解与基于变邻域搜索的启发式算法求解的优化解之间的差距， ${\text{GAP}}_{\text{2}}=\left(\text{C}\left({\text{S}}_{\text{init}}\right)-\text{C}\left({\text{S}}_{\text{best}}\right)\right)/\text{C}\left({\text{S}}_{\text{init}}\right)\times 100\%$ 。

Table 3. Comparison of test results

表3. 测试结果对比

由表3可以看出，基于车辆运输效率(TEBA)的方法得到的初始解效果远远优于实际调用费用，平均每个月的费用可以节约20.219%；变邻域搜索算法稍优于基于车辆运输效率(TEBA)方法，其平均每个月的费用在初始解的基础上可以节约3.811%。可见，基于锁定策略的车辆运输效率(TEBA)的方法已经可以取得较好的结果，加入邻域局部搜索算法后，变邻域搜索算法得到的解的质量有了进一步提高。

5. 结论

本文以多生产点卷烟生产企业原料调运现象为背景，研究了大规模、多品种且库存有限情况下需求可分割的同时送取货车辆路径问题。从供应链的整体性出发，考虑各环节之间的相互影响，建立了相应的数学模型，以最小化车辆运输吨公里为目标，使建立的模型符合企业实际情况。设计了变邻域搜索算法，第一阶段，结合车辆路径选择以及路径上的原料供需匹配关系两方面决策目标，构建基于车辆运输效率的启发式算法，获得问题的初始解。第二阶段，借助六种邻域结构，建立基于变邻域搜索的局部搜索算法，改进初始解。实验部分将每月实际运输成本以及优化后的运输成本分别与基于车辆运输效率构建的运输成本相比较，结果证明基于运输效率的启发式算法对实际运输费用有明显改善，加入邻域局部搜索算法后对初始解有一定的改进。本文优化方案要求同一仓库允许被多次访问但仅能被同一车辆最多访问一次，没有考虑同一辆车多次访问同一仓库点的情况，但这类情况在企业实际物流运输中比较常见，需要做更深一步的研究。此外，各仓库节点时间窗等约束也是未来研究考虑的重点。

基金项目

国家自然科学基金地区项目(71862034；71862035；61762088)；云南省教育厅科学研究基金项目 (2017ZZX004)。

NOTES

^*通讯作者。