具有时间窗的取送货问题建模和大邻域搜索算法

程 谦，张大力，侯立文

(1. 上海交通大学 中美物流研究院，上海200030；2. 上海交通大学 安泰经济与管理学院，上海200030)



具有时间窗的取送货问题建模和大邻域搜索算法

程 谦1，张大力1，侯立文2

(1. 上海交通大学 中美物流研究院，上海200030；2. 上海交通大学 安泰经济与管理学院，上海200030)

针对新型物流业态中出现的路径优化问题，建立了一类具有不同起点和不同终点的带时间窗取送货问题模型. 根据模型特点，设计了一类大邻域搜索算法对大规模问题进行求解. 该算法引入了匹配度的概念和时差插入法，以提高搜索效率. 通过设计一类与精确求解工具进行比较的方案，验证了算法的有效性.

取送货问题；时间窗；大邻域搜索算法

具有时间窗约束的取送货问题(pickup and delivery problem with time windows, PDPTW)是一类特殊的具有时间窗的车辆路径规划问题(VRPTW). 在PDPTW问题中，车辆被安排前往不同的地点取货并将货物送往相应目的地，车辆到达每个取货点或目的地的时间均有约束.

PDPTW的相关文献最早可追溯到1980年，Psarafis[1]采用动态规划的方法求解了需求少于10个的算例. 随后出现的精确算法包括分支定价法[2]和分支剪切法[3].而更多文献专注于设计启发式算法以增大可求解的PDPTW规模. Nanry等[4]最早采用了禁忌搜索算法进行求解，并创建了一组基准算例来检测算法的效果，每个算例最多包含50个需求. 此后Li等[5]提出了一种整合模拟退火和禁忌搜索的算法，并进一步扩大了算例的规模至100个需求. Lau[6]等提出了禁忌搜索算法中几种构建路径的方法. Bent等[7]采用了两阶段混合算法，第一阶段用模拟退火算法减少车辆数，第二阶段用大邻域搜索算法(Large Neighborhood Search, LNS)最小化路径长度. Ropke等[8]在此基础上提出了自适应大邻域搜索算法. 据我们了解，目前国内对PDPTW的研究有限，最近的结果主要为潘立军[9]提出的一类时差插入法，以及以该插入法为基础的遗传算法.国外最近的研究进展主要集中于具有特殊结构的PDPTW. 例如需求可拆分的PDPTW[10]和具有后进先出的装载约束的PDPTW[11].

PDPTW的传统应用领域包括车辆调度、航空调度、校车路线规划等. 伴随着新型业态的出现，PDPTW的一般形式已经不能满足实用性的要求. 例如，在传统PDPTW中所有车辆具有同一出发点和终点，且所有需求都要被满足. 而在拼车平台中，车辆通常有事先确定的起点和终点，且并不是所有需求都能匹配到合适的运输车辆.

基于以上实用性要求，本文对于PDPTW模型进行了进一步拓展：首先放松了以往PDPTW中对于所有车辆必须从同一地点出发和到达同一地点的假设，并增加了车辆起点和终点的时间窗约束，同时放松了所有需求都要被满足的要求. 在算法方面，本文设计了一类大邻域搜索算法，通过计算需求与路径的匹配度，提升算法中的路径重构效率.

1 模型建立

本文考虑了一类具有若干运输车辆和多个运输需求的PDPTW模型. 运输车辆事先都有一个预定的运输任务，即给定了起点、终点和初始载货量，不同车辆的起点、终点各不相同. 车辆在完成预定任务的过程中，可以选择接受其他运输需求以提高运营效率. 这些运输需求的取货点、送货点和运输货量也各不相同. 模型中的所有节点(包括车辆起点和终点)都存在时间窗约束，车辆不能晚于时间窗结束时间到达，但可以早于时间窗开始时间到达，并等候至时间窗开始时间再进行装卸货. 模型的目标是把运输需求(不要求全部满足)分配给运输车辆并安排其访问路线，在满足时间窗和载货上限等约束条件下，使得系统运营利润最大.为简化模型，这里假设装卸货时间忽略不计. 同时各点之间的距离和行驶时间对称.

模型定义在全连通图G= (N,A)上. 其中点集N: ={1,2,…,2m+2n}，弧集A: ={:i,j∈N,i≠j}. 模型中共有m个的服务车辆和n个运输需求，我们定义车辆k的起点为k，终点为k+m+n，，需求i的取货点为m+i，送货点为2m+n+i. 集合Om:={1,2,…,m}和Dm:={m+n+1,m+n+2,…,2m+n}分别代表车辆的起点集合和终点集合. 集合On:={m+1,m+2,…,m+n}和Dn:={2m+n+1, 2m+n+2,…, 2m+2n}分别代表需求的取货点集合和送货点集合. 此外图中不存在其他节点，也即N: =Om∪On∪Dm∪Dn. 图中每个节点i都对应一个货量参数qi，当qi为正时代表取货点，当qi为负时代表送货点，有qi=-qm+n+i. 同时每个节点i都对应一个时间窗[ai,bi]. 车辆在i点开始装卸货的时间必须晚于ai且早于bi.A中每条弧 都对应一个距离参数dij和行驶时间参数tij. 集合V表示车队.V中每辆车的载货上限都为c.

本文模型的数学表达式如下：

(1)

(2)

(3)

(4)

(5)

∀k∈V

(6)

(7)

(8)

(9)

(10)

(11)

(12)

(13)

目标函数(1)是整个系统的运营利润，其中收益是货运周转量乘以收费费率u；货运的成本是行驶距离乘以单位距离运费v. 因此系统总利润为：

上式等价于

这里我们考虑一下σ的含义. 令目标函数等于0，即系统保持盈亏平衡时，有

其中:分子为所有被服务的需求产生的总周转量；分母为各车辆行驶总距离乘以其载货上限c的总和. 所以σ的含义为保持盈亏平衡的平均装载率.在下文的实验中，将分别选取不同的σ进行计算，并比较结果.

2 算法设计

大邻域搜索算法(Large Neighborhood Search, LNS)最早由Shaw于1997年提出，其搜索机制包括拆解-重构两个步骤，本文的拆解步骤即为移除路径中的部分需求，重构步骤为将剩余需求插入路径. LNS与传统的邻域搜索算法的主要区别在于每次迭代搜索的范围更大，所得的局部最优解的质量更好，当然每次迭代耗时也更长. 针对约束偏多的问题，LNS算法较容易产生可行的邻域解，同时便于以取货点-送货点对作为基本操作单位，非常适合用于本文模型的求解. 以下是本文所设计的LNS算法框架：

首先，生成初始解x，取当前最优解xoptimal=x；(见2.1节)

While 终止条件(连续Num次迭代后都没有产生新的最优解)不满足：

随机移除当前解x所形成的路径中的若干需求；(见2.2节)

将未被当前解x选中的需求按匹配度依概率分配到各个车辆的路径中；(见2.3节)

对分配给各车辆的需求重新进行随机排列(增加插入顺序的随机性，扩大搜索范围)；

将重排后的需求按顺序依次尝试插入对应的路径，得到新解x′； (见2.4节)

If目标函数值f(x′)满足接受条件(见2.5节)

x=x′；

End if

If目标函数值f(x′)>f(xoptimal)

xoptimal=x’；

End if

End while

输出最优解xoptimal.

2.1 生成初始解

本文采用平行插入的方法构造初始解. 首先生成m条只包含车辆起点和终点的路径，再将剩余需求依次插入路径中的最佳位置(插入方法见2.4)，直到目标函数不再增大为止. 由于生成的初始解由需求插入的顺序决定，这里采用以下方法来选择每一次插入的需求：

假设Δfir表示将需求i插入路径r后目标函数的最大增量，当需求i无法插入r或插入后增量为负时取Δfir=0. 如果把各条路径按Δfir值从大到小排列，ril表示排名第l的路径，l=1,2,…,m. 则每次插入选择的需求i为：

上式可以看作如果不把i插入当前最优路径将可能造成的损失，每次插入时应避免造成最大的损失.

2.2 需求移除

本文采取的移除方法为等概率随机移除各路径上的N个需求，其中N为一随机正整数，取值范围为1，2，…，Nmove，其中Nmove为N能取到的最大值，各数值的选取概率为1/Nmove.

2.3 需求的重新分配

在路径重构过程中，未被选中的需求(包括本次移除和上次重构时未被插入的需求)将被分配到各条路径以待插入. 本文采用了随机分配的方式以保证搜索范围足够大，并设计了一种评价机制，称为匹配度，以使需求以更大概率与合适的路径相匹配，增加搜索效率.

假设需求i的取货点为i，送货点为i′, 需求j的取货点为j，送货点为j′.rij为连接i，i′，j，j′四个点且满足时间窗、货量约束的路径中最短的一条，该路径总距离为drij,dii′为i与i’之间的距离，djj′为j与j′之间的距离. 则需求i与j的匹配度为：

其中:φij的取值范围为0到1，φij的值越大，需求i与j的匹配度越高，也就是说越适合放入同一条路径. 如图1，图1(A)中的φij值更大，接近1，则匹配度也更高.

图1 不同匹配度下两个需求的位置关系示意图

需求与车辆之间的匹配度定义与需求之间的匹配度类似. 假设需求i的取货点为i，送货点为i′，车辆k的起点为k，终点为k′. 由于路径的起点和终点已经确定，所以只存在一条访问路径rik. 需求i与路径k的匹配度为:

如果上述rij或rik不存在，也即不存在符合约束条件的路径. 则规定φij或φik为负无穷大.

接下来，需求与某路径之间的匹配度即为需求与该路径上各需求/车辆之间的匹配度的平均值. 假设路径r={k,j1,j2,…jn}，即路径r中包含了车辆k以及需求,j1,j2,…,jn. 则需求i与路径r的匹配度为：

如需求i与路径r中的某个需求j或车辆k之间的匹配度为负无穷大，则表明不存在满足约束条件的路径能同时访问这4个点. 所以需求i不可能成功插入路径r. 此时φir=0. 根据需求与路径之间的匹配度，即可将需求以轮盘赌的方式分配到路径中去. 假设共有m条路径r1,r2,…rm，则将需求i分配到路径ri的概率为：

2.4 最佳插入位置

在计算将某节点插入某路径的最佳位置时，本文参考了潘立军等[9]的时差插入法以提高检验时间窗和载货量约束的速度. 不同之处在于本文的算法得到的是最优解，而不是较优解.

首先对于路径上的节点i，定义下列参数：

Ei为车辆在i点开始装卸的最早时间;Li为车辆在i点开始装卸的最晚时间;Qi为车辆在i点作业后的装载量.

对于路径的起点k和终点k+m+n，有：

Ek=ak

Lk+m+n=bk+m+n

Qk=qk

Ei，Li和qi的值可以由正向或逆向递推得到，假设车辆先后访问了节点i和j，则有：

Ej=max{Ei+tij,aj}

Li=min{Lj-tij,bi}

Qj=Qi+qj

将节点p插入路径上相邻两点i与j时，判断其满足时间窗和载货量约束的充要条件为同时满足：

min{Lj-tpj,bp}≥max{Ei+tip,ap}

(15)

Lj-Ei≥tip+tpj

(16)

Qp≤c

(17)

假设需求的取货点和送货点分别为p和p′，则最优插入位置的算法具体步骤如下：

1)计算当前路径上各点的Ei，Li和Qi.

2)从路径起点之后的位置到路径终点之前的位置依次尝试插入p点，根据式(15)～(17)判断插入是否满足约束. 如果满足，将该点插入路径，继续执行下面p′的插入步骤，然后尝试下一个插入位置；否则跳过p′的插入，直接尝试下一个位置.

3)更新路径上各点的Ei，Li和Qi.

4)将p点后的位置设为p′插入的初始位置Istart. 计算初始位置后路径上各点的Qi值，若所有Qi值都小于c，则将路径终点前的位置记为终止位置Iend. 若存在Qi值大于，则将第一个出现该情况的点之前的位置记为终止位置Iend.

5)从Istart到Iend依次尝试插入p′，根据式(15)、(16)判断其是否满足时间窗约束. 如果满足，计算插入后目标函数的增量，执行步骤6，再尝试下一个插入位置. 如果不满足，跳过下面的步骤，直接移至下一个位置.

6)将步骤5计算的目标函数增量与当前最优方案比较. 如果大于当前最大的目标函数增量，则更新该数值，并记当前插入方案为最优方案.

在搜索迭代过程中，算出最佳插入位置和目标函数的增量后，还需判断是否接受该插入方案，具体的判断方法见2.5节.

2.5 邻域解接受条件

在判断是否接受新产生的邻域解时，本文采用了模拟退火作为接受条件，以避免陷入局部最优. 假设当前解为x，新产生的邻域解为x′则接受x′作为新的当前解的概率为min{ef(x′)-f(x)/T，1}. 其中为目标函数值，T为淬火温度，T的值会随着迭代的进行逐步减小，使接受条件越来越苛刻. 每次迭代后取T=T·γ，其中γ为冷却率，有0<γ<1. 每当有新的最优解产生后，将T恢复为初始值Tstart. 这里把Tstart设置为以50%的概率接受比当前解小α%的邻域解，则有.

Tstart=-α%·|f(x)|/ln0.5

对于2.4节中需求插入路径的过程，本文同样采用了模拟退火算法来判断是否接受插入，这样可以避免多个需求同时插入后可增大目标函数而单个插入不被接受的情况. 由于单个需求插入引起的改变量相对较小，这里取温度T′=T/m.

3 算法测试与比较

传统的PDPTW的求解目标为最小化车辆数和车辆行驶距离，不具备与本文模型的直接可比性. 因此本文采用了精确求解软件Cplex作为对照. 受计算机计算能力的影响，Cplex可求解的问题规模有限. 这里首先用Cplex尝试精确求解小规模算例，测试本文算法求解的精确度，具体内容见3.1节. 对于大规模问题，本文以Cplex为基础设计了一种分组求解的方法，与启发式算法进行比较，具体内容见3.2节.

本文的LNS算法采用MatlabR2014a编程实现. 算例改编自Ropke[8]的算例.

3.1 精确求解的算例结果对比

精确求解的算例结果比较见表1. 各算例均运行于酷睿I3处理器，4G内存的PC. 表中算例编号的前两位表示节点数量. 在参数方面，取迭代次数Num为3 000，需求移除数量上限Nmove为5，接受条件参数取0.05，冷却率γ取0.998 7.

表1 精确求解的算例结果对比

算例编号σCplexLNS目标函数值CPU时间/s目标函数值CPU时间/s目标函数值误差/%40A0.135521233552113040B0.219185111918517040C0.3-53993-539915040D0.4-134303-1343012040E0.5-371416-3714112040F0.6-352532-3525311040G0.7-565562-5655613050A0.137176249836471191.9050B0.222903159022833180.3150C0.3-22014-220111050D0.4-2456312-2456312050E0.5-378543-3785410050F0.6-496493-4964911050G0.7-447642-4476410060A0.1——5104326—60B0.21707100170720060C0.3——185618060D0.4-1307717-1307717060E0.5-3570410-3570434060F0.6-277445-2774419060G0.7-646075-6460718070A0.1——3556926—70B0.2——1759824—70C0.3——-926420—70D0.4-228829-2288221070E0.5-437894-4378924070F0.6-570676-5706723070G0.7-725806-72580370

从表1中可以看出，本文设计的LNS算法在绝大部分情况下都可以得到最优解，且计算时间相对稳定. 而用Cplex求解时部分算例无法求出最优解. 出现误差的两个算例的σ值都很小，分别为0.1、0.2，意味着车辆选择需求的条件较宽松，或者说对匹配度的要求不高. 这也与本文的算法特点相吻合，说明本文算法更适用于σ较大的情况.

3.2 大规模算例结果对比

对于大规模算例，用Cplex常常无法求解. 本文先将其分组为多个可精确求解的算例(每组算例包含数量不等的车辆和需求)，再分别用Cplex求解，这样就得到了一个可行解. 由于不能保证分组的结果为最优，所以用该方法求出的目标函数值是最优值的下界.

分组方法为：首先用K-means聚类法把车辆分为t组，聚类的评价指标为车辆起点、终点的坐标和时间窗共8个参数. 再对需求进行分组，本文采用了类似于根据匹配度分配需求的方式. 假设需求i的取货点为i，送货点为i′,车辆k的起点为k，终点为k′. 则有

当聚类个数t越小，每组的分到的节点数越多，而Cplex无法求出最优解的可能性越大. 因此，先把t设为一个较大的数，再逐步减小t值，尝试分组计算，直到Cplex无法求解为止. 为了防止分组不均导致个别组求解困难，这里规定每组节点数上限不能超过每组平均节点数的1.3倍.

本算例包含50个车辆，250个需求，共600个节点，运行于酷睿I7处理器，8G内存的PC. 在参数方面，平均装载率σ取0.3，迭代次数Num取10 000，移除数量上限Nmove为5，接受条件参数α取0.05，冷却率γ取0.998 7. 计算结果的对比见表2和图2，可以看出，LNS算法求解具有很大优势.

表2 大规模算例结果对比

求解方法分组数量t目标函数值CPU时间/sCplex分组求解19467381121848152135174298828316514856811552718177614648033218LNS求解—861831503

图2 Cplex分组求解结果趋势图

4 结 语

由于传统PDPTW已不能满足新型物流业态中出现的实用性要求，本文建立了车辆从不同起点出发到达不同终点，且车辆起点和终点具有时间窗约束的PDPTW模型. 针对该模型特征，本文设计了大邻域搜索算法，并通过引入匹配度的概念以及时差插入法，提升算法的运算效率. 算例测试的结果显示，该算法具有良好的求解速度和质量.

[1] PSARAFTIS H N. A dynamic programming solution to the single vehicle many-to-many immediate request dial-a-ride problem [J]. Transportation Science, 1980, 14(2): 130-154.

[2] DUMAS Y, DESROSIERS J, SOUMIS F. The pickup and delivery problem with time windows [J]. European Journal of Operational Research, 1991, 54(1): 7-22.

[3] ROPKE S, CORDEAU J F, LAPORTE G. Models and a branch-and-cut algorithm for pickup and delivery problems with time windows [J]. Networks, 2007, 49(4): 258-272.

[4] NANRY W P, BARNES J W. Solving the pickup and delivery problem with time windows using reactive tabu search [J]. Transportation Research Part B: Methodological, 2000, 34(2): 107-121.

[5] LI H, LIM A. A metaheuristic for the pickup and delivery problem with time windows [J]. International Journal on Artificial Intelligence Tools, 2003, 12(02): 173-186.

[6] LAU H C, LIANG Z. Pickup and delivery with time windows: Algorithms and test case generation [J]. International Journal on Artificial Intelligence Tools, 2002, 11(03): 455-472.

[7] BENT R, HENTENRYCK PV. A two-stage hybrid algorithm for pickup and delivery vehicle routing problems with time windows [J]. Computers & Operations Research, 2006, 33(4): 875-893.

[8] ROPKE S, PISINGER D. An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows [J]. Transportation science, 2006, 40(4): 455-472.

[9] 潘立军, 符 卓. 求解带时间窗取送货问题的遗传算法[J]. 系统工程理论与实践, 2012, 32(1):120-126 [10] AHIN M, AVUSLAR G, ONCAN T,etal. An efficient heuristic for the multi-vehicle one-to-one pickup and delivery problem with split loads [J]. Transportation Research Part C: Emerging Technologies, 2013, 27: 169-188. [11] CHERKESLY M, DESAULNIERS G, LAPORTE G. A population-based metaheuristic for the pickup and delivery problem with time windows and lifo loading [J]. Computers & Operations Research, 2015, 62: 23-35.

Study on model for pickup and delivery problem with time windows and large neighborhood search algorithm

CHENG Qian1, ZHANG Da-li1, HOU Li-wen2

(1.Sino-US Global Logistics Institute, Shanghai Jiaotong University, Shanghai 200030,China; 2. Antai Economic and Management School of Shanghai Jiaotong University, Shanghai 200030, China)

In order to solve the newly emerged route optimization problem in logistics industry, a model of pickup and delivery problem with time windows was built in this paper, in which vehicles were assigned with different originations and destinations. Time windows for drivers are also taken into account. According to the characteristic of this model, a large neighborhood search algorithm was proposed, in which matching rate is introduced to increase search efficiency. Finally, a comparative test was conducted between the algorithm and exact solver. The effectiveness of the algorithm was verified.

pickup and delivery problem; time window; large neighborhood search algorithm

2016-01-07.

国家自然科学基金资助项目(71372108)

程 谦(1989-)，男，硕士，研究方向：物流系统优化.

F252

A

1672-0946(2016)06-0734-06