基于社会化库存的多回程物流配送问题的拉格朗日松弛算法

谭志龙，王 征，薛桂琴，王 新

(1.大连海事大学 交通运输工程学院，辽宁 大连 116026;2.大连海事大学 航运经济与管理学院，辽宁 大连 116026)

0 引言

随着零售业的不断发展，网购商品的可选范围得到了极大的拓展，除传统的需要多天配送的服装鞋帽、家电数码等商品外，线上线下相融合的本地商家进行生鲜果蔬、日用百货等生活快消品的配送也成为了网购的一股新力量。这种配送方式依托地理上分散分布的多个商店实现库存的社会化，通过运力的合理调度，在顾客规定的时间内完成从商家取货并向顾客配送的物流任务。这种社会化的库存对运力的优化调度提出了新要求，物流配送呈现出时间紧迫、取送一体化等特点。因此，如何在满足顾客需求的前提下，以较低的成本完成社会化库存的配送服务，是第三方物流公司必须解决的关键问题。理论上，这类问题可归结为一类特殊的多回程混合取送车辆路径问题，是车辆路径问题(Vehicle Routing Problem，VRP)的一类变形，仍具有NP-hard复杂性。

多回程VRP是指配送车辆可在供货点与顾客点之间往返多次，从而完成每个顾客的配送服务。该类问题的代表性研究成果包括Hernandez等[1]的分支定价法、Nguyen等[2]的禁忌搜索算法、Cattaruzza等[3]的遗传算法、Golden等[4]的适应性记忆算法、Chbichib等[5]的构建启发式、Battarra等[6]的适应性监督算法、Azi等[7]的大邻域搜索算法、以及国内学者唐加福等[8]的精确算法、王征等[9]基于路径池的算法等。然而，这些关于多回程VRP的研究通常只考虑一个供货点，而在本文问题中，货物仓储被分散在了大量商店中，每个商店都是供货点。这种分散的社会化库存为车辆带来了更多的路径选择，比现有研究中单供货点、多回程的车辆调度问题具有更多的路线选择，因而解的搜索空间和复杂性显著提升。

混合取送VRP是指配送车辆在配送时既可以取货、又可以送货，是一类取送一体化的VRP拓展问题。其代表性成果包括Dumas等[10]的列生成方法、Nagy等[11]的基于强弱可行性的混合启发式、Wassan等[12]的响应式禁忌搜索、Zachariadis等[13]的基于适应性记忆的方法、Subramanian等[14]的分支裁剪法、Zhang等[15]的分散搜索算法、Paraphantakul等[16]的蚁群算法、及Wang等[17]的混合启发式等。上述文献基本可以分为两类问题:①取货点和送货点一对一的问题;②从中央仓库统一取货送至顾客、同时又从各个顾客回收废品再送至中央仓库的一对多对一的取送问题。不同于上述两类问题，社会化库存配送中的取货点和送货点属于“多对多”的关系，每个商店可为多个顾客供货，每个顾客也可以从多个商店购货，现有研究中的混合取送问题并不具备上述特征。

拉格朗日松弛算法是将增加计算复杂度的约束添加到目标函数中，是一种较好的求解组合优化问题的精确解算法[18]。传统拉格朗日松弛算法的主要工作是求出问题的下界，在有限时间内所得结果虽与最优解的目标值相近，但一般为不可行解[19]。目前，拉格朗日松弛算法的应用主要分为两部分:①利用次梯度优化不断增长问题下界，直至找到问题最优解[20];②将传统拉格朗日算法与启发式算法相结合，在传统拉格朗日松弛算法所得结果的基础上，运用一些启发式规则使其可行化[21]。两者各有优劣，前者虽然可以确定所得结果为问题最优解，但求解时间过长;后者虽然可以得到问题可行解，但在运用启发式规则时充满了不确定性，无法确保可行解的有效性，求解效率难以保证。

基于前人的研究，本文将研究基于社会化库存的带时间窗多回程混合取送车辆路径问题(Multiple Trip Pickup and Delivery Vehicle Routing Problem with Time Windows，MTPDVRPTW)，并对传统拉格朗日松弛算法进行改进，在保留其原有求解问题下界优势的基础上，为其注入了问题上界求解的可行方法，通过不断逼近问题上下界，实现了对MTPDVRPTW 的有效求解。

1 问题描述与模型构建

1.1 问题描述

在MTPDVRPTW 中，每个商店可为多个顾客提供商品，商店可被访问多次，每次访问都可能发生在不同时间，如何表达出商店被不同车辆、在不同时间的多次访问是建模的难点。一种建模的思路是根据时间将商店拷贝多次，同一商店拷贝后的每个点虽然具有相同的位置信息，但所代表的到达时间不同，车辆对同一点的多次访问可以被关联到不同的拷贝点上[22]。建模示例如图1所示，商店s1为顾客b1、b2供货，顾客b2的最晚到达时间为20min时，每隔5min将车场、商店s1、顾客b1、b2复制一份，复制后的位置信息不变，但每点分别代表了不同的时间点，如点s11代表车辆在5分钟时是否位于商店s1。在时间跨度较长时，运用该种建模思路复制后的点数量庞大，求解效率无法得到保证。另一种建模思路是根据商品数量，将商店与顾客进行拷贝，拷贝后的商店点地理位置不变，复制后的商店只完成一个“顾客、订单”对的服务[23]，建模示例如图2所示，商店s1为顾客b1、b2供货，在建模中不易表示到达顾客点时车辆的装载情况，因此将商店s1根据所要服务的顾客点数量进行拷贝，拷贝后商店点s11为顾客点b1提供货物，商店s12为顾客点b2服务。复制后点的地理位置及其他信息不变，商店与顾客属于一一映射关系，每个商店仅服务一个顾客，每个顾客也只需要一个商店的商品。假设现有n个顾客需求m个商店的货物，顾客点的最晚到达时间为60min，顾客最多订购了3家商店的商品。在第一种建模思路下，每隔5min将顾客点与商店点拷贝一份，拷贝后的点数为12(m+n)。而在第二种建模思路下，复制后的商店与顾客总数不超过6max(m，n)，问题规模远小于第一种建模思路，因此本文采用第二种建模思路对问题进行抽象化。

经过抽象后，本文研究的问题可用图G=(N，A)表示。其中N为所有节点的集合，包括车场o，复制过后的商店点集合Ns，顾客点集合Nc;A为所有节点相互连接形成的弧的集合，使用cij表示两节点之间的配送成本，用两点间直线距离来表示。本文模型所用到的主要符号定义如下:xijk表示车辆k是否从点i行驶到点j，行驶则xijk=1，不行驶则;车场的自有车辆集合用K表示，自有车辆总数用V表示，车辆额定装载量为Q，某时刻要完成n个顾客订单的配送服务，配送车辆需从车场o出发，并最终返回车场;订单i所对应的取货点用si表示，商品重量为qi，到达时间为ai，访问i点后的车辆装载为li;顾客订单需求已知，服务时间窗为[ETi，LTi]，其中:ETi表示顾客订单i的时间窗下界，到达时间早于ETi需等待;LTi表示顾客点i的时间窗上界，不允许出现晚于LTi的访问。

现实操作中，配送公司会对当天订单量进行预测，并以此来分配车辆和骑手，一旦制定分配计划，自有车辆在一般情况下都将被使用。若自有车辆无法完成全部顾客点的配送服务，需要利用第三方物流对未被访问的顾客点进行配送，此时每单的配送成本固定为P，顾客点是否进行第三方配送用0-1变量yj表示。问题的目标是成本最小化，成本由自有车辆的行驶成本和第三方物流配送所产生的成本两部分组成。

1.2 模型构建

基于以上问题描述，建立了以成本最小化的多回程混合取送车辆路径问题模型MTPDVRPTW。建模过程中，对商店点进行复制，车辆可以多次返回同一商店点，因此模型具备多回程的特性;且车辆同时具备取送货能力，在商店点取货后，再完成对应顾客点的配送，模型具备取送一体化的特性。

其中:目标函数(1)表示成本最小化，由自有车辆的行驶成本和第三方物流配送的成本构成;约束(2)表示商店点与顾客点的访问次数限制;约束(3)表示商店点与顾客点是否需要第三方物流配送;约束(4)表示车辆需从车场出发，在完成配送服务后返回车场;约束(5)为车辆流约束，确保车辆在进入节点(非车场节点)后一定从该节点离开;约束(6)和(7)确保顾客点与所对应的取货点必须被同一辆车访问，且仅在完成取货点访问后才可访问顾客点;约束(8)为节点到达时间的计算，其中M为一充分大的正数;约束(9)为顾客点的访问时间限制;约束(10)为到达节点时的装载量约束;约束(11)为确保车辆的装载容量约束;约束(12)保证决策变量为0-1变量。

2 改进的拉格朗日松弛算法

2.1 拉格朗日松弛算法

VRP求解算法主要分为启发式算法和精确算法两类。其中启发式算法采用一定的规则在问题可行域进行随机搜索，容易陷入局部最优，无法确保所得结果的有效性，多用于大规模问题的求解;精确算法的求解时间随问题规模的增长而快速增长，一般用于求解中小规模问题，拉格朗日松弛是其中的代表性成果，是求解组合优化NP-hard问题的有效工具。

由于组合优化问题NP难的特性，求解最优目标值非常困难，解决该难点的有效方法就是计算问题下界，通过比较所得可行解与问题下界的差值来评价算法的有效性，而拉格朗日松弛算法是一种有效求解问题下界的方法。拉格朗日松弛算法的优点在于通过松弛某些约束，从而使得松弛问题可被分解为多个相同的子问题，仅需对子问题求解一次即可得到原问题下界，大大提高了下界的求解效率。在实际求解中，问题由于某些原因很难直接求得最优解，或者求解效率较差;而如果放松原问题的一些约束，其求解难度将大大降低，从而在可接受的时间内完成求解。这些导致求解难度增大的约束通常被称为难约束。在本文模型中，难约束为约束(2)，即商店点与顾客点的访问次数限制，引入拉格朗日乘子λj对其进行松弛，由于始终为非负值，松弛过后的拉格朗日松弛模型目标如式(13)所示，满足约束(3)～约束(12):

拉格朗日乘子λj反映了服务顾客的成本，且在一般情况下为正数。因此，对于任意给定的λ=(λ1，λ2，...，λn)T，拉格朗日函数值都是原问题的下界，因而构建拉格朗日对偶问题max(ZLR(λ))，得到拉格朗日松弛模型的最大值ZLD，即可以求得原问题一个较优的下界。

为方便表示，令

显然，式(16)为线性分段的凹函数，且并不可微。而次梯度优化方法是求解不可微凹函数的极大化问题的较好方法。次梯度是指针对x*，对于∀x∈Rn，使得不等式f(x)≤f(x*+dT(x-x*))成立的向量d。换言之，对于凹函数而言，在点x*的次梯度为通过此点，并且始终位于凹函数之下的直线的斜率。在本文问题中，集合U={uj|j=1，2，…，m}即为拉格朗日乘子为λ时的一个次梯度。本文建立的总体算法流程如下:

步骤1将拉格朗日对偶问题分解为相同的车辆数个子问题;对拉格朗日乘子λ，原问题上界Zub，下界Zlb进行初始化。

步骤2求解子问题，计算此时的拉格朗日函数值ZLR(λk+1)，更新原问题下界Zlb。

步骤3根据所求子问题最优解计算次梯度，更新拉格朗日乘子若原问题下界在β1代内未得到更新，β的值减半。

步骤4以γ的概率基于次短路的优化思想求解子问题，搜索原问题可行解，并更新原问题上界Zub;

步骤5若原问题上界与下界的差值小于范围β2或者达到最大迭代次数，停止迭代，将现有最优可行解视为原问题最优解。反之，重复步骤2～步骤4。

2.2 基于次短路的子问题求解算法

拉格朗日松弛模型的目标函数整理后可得:

本文基于动态规划的思想，采用改进的标号法求解子问题。传统算法的思想对每个点进行标号，用以表示从车场起始点到该点的路径，记为π。π由(m，t，l，s，c)5部分构成，其中:m表示此路径访问的上一个点;t表示到达点i并做好装卸货准备的时间;l表示完成点i后的车辆装载量;根据在完成点i访问后车辆的现有装载情况，s表示车辆后续必须访问的顾客点集合;c表示访问完此点的路径成本。假设π与π'为同一点的不同标号，若满足条件式(19)，则认为π支配π'，使用≻符号表示支配。

但该标号方法只能得到子问题的最优解，由于车辆是同质的，所有子问题的求解结果相同。这种情况下，所得子问题求得的访问路径一般无法覆盖所有顾客点，即无法得到原问题的可行解。而且由于覆盖点较少，直接通过启发式方法将其进行可行化的效率并不高，无法实现问题上下界的快速逼近，求解效率差。针对传统标号法的上述缺点，本文在子问题求解过程中引入了次短路的优化思想，在对商店与顾客点进行标号时，接受劣于最优标号一定范围内的次优标号，从而实现了问题上界的有效求解，加快了问题上下界的逼近速度，具有较好的求解性能。

定理1随着次梯度的更新，各点间的成本定价不断减小，原问题最优解中的每条访问路径的reduce cost会不断减小，且各路径成本的最大reduce cost差在不断下降，并逐渐逼近于此时子问题的最短路径。

证明为方便表示，假设最优解由R条路径组合而成，用表示第k代r条路径的reduce cost。由于在最优解中每点被访问且仅被访问一次，若在第k代求得的最短路径为ri，则除第i条路径访问点之外的点均未被访问，根据次梯度的更新法则，点与未访问点之间的成本定价会减小。此时，未访问路径的reduce cost将减小，直至发现比成本更低的路径，以此实现最优解中每条路径的reduce cost的不断缩小。此外，在更新次梯度时，由于更新的步长不断减小，reducecost的降低速度一直在减缓，故最优解中的各路径成本差将逐渐缩小。

因此，在问题求解过程中，以一定的概率采取次短路的优化思想，接受劣于最短路径一定范围内的路径，即使无法覆盖原问题最优解中的所有路径，所得的路径也会包含原问题最优解的一部分，访问的顾客点也比较多，对其进行可行化的效率也较高。综上所述，本文在求解子问题时，以一定的概率采用式(20)的标号支配法则，使用≻符号表示支配。

在这种支配法则下，可以求得成本劣于最优路径一定范围内的路径。在算法运行中，应根据求取目标选择支配法则，按照下述动态规划算法流程进行求解:

步骤1从车场出发，为所有商店点进行标号，并将除车场以外的点加入集合E中。

步骤2从E中选取一点i，将其从E中删除，对其余点进行标号，若标号满足车辆载重约束、顾客时间窗约束、取货后才能送货的约束，且访问后已装载商品至少有一可行配送方案，转至步骤3。

步骤3将标号与已存标号进行比较，若存在可支配标号，删除此标号;若此标号可支配已存标号，进行取代，并将此点加入集合E中;若此标号与已存标号不存在支配关系，将其加入此点的标号集合，并将此点加入集合E。

步骤4当标号中的载重量为0时，对车场o'进行标号。若采用的为次短路策略，接受劣于最短路径一定范围内的路径。

步骤5重复步骤2～步骤4，直至集合E为空集，选取车场的标号，此时得到子问题的解。

上述方法使用传统标号法求取子问题的最短路，保留了传统拉格朗日算法求取问题下界的优势，并以一定概率采用次短路的优化思想寻求问题上界的有效求取，根据问题上下界进行拉格朗日乘子的更新，具有较快的收敛速度。这种次短路的优化思想为传统的拉格朗日松弛算法注入了获得可行解上界的能力，使得该算法在求取下界的同时能够快速得到高质量的上界，从而实现了问题上下界的并行求解，为快速求得问题最优解或高质量可行解提供了途径。

3 实验结果与分析

为验证本文模型的合理性及改进拉格朗日算法的有效性，基于标准Solomon算例构建了顾客订单数不同的算例，采用MATLAB 2014a编程平台对设计的改进朗格朗日松弛算法进行编码实现，并将算法求解结果与CPLEX求解器及利用次梯度优化的传统拉格朗日松弛算法进行了对比。本文所有实验均在i5CPU、8 GB内存的计算机上运行。

3.1 算例与参数

MTPDVRPTW 不同于传统的带时间窗的车辆路径问题，因此将该领域标准的Solomon算例进行了改进，使其适用于本文的问题，算例选取与具体改进工作如下:

(1)选用的算例类型 商店一般存在配送范围的限制，且配送范围不会太大，一般为相邻的人口集聚地。这是由于配送费用与配送范围相关，配送范围越大，配送费用越高，而顾客与商店对于配送费用敏感性较高。这种情况下，商店和顾客往往是成簇出现的，这与Solomon算例中的C 类算例非常相似。本文以C类算例为基础进行了改进，在Solomon算例中选取了V个顾客簇，从这些顾客簇中随机选取了商店点与顾客点，并生成了两者的对应关系。

(2)时间窗设置 同城物流配送公司一般为顾客提供的送达时间为时间点的形式，但在实际情况中，在早于或晚于送达时间点一定范围的时间窗内送达均不会引起顾客满意度的大幅下降，从而也不会出现退货的情况。物流配送公司偏好时间跨度大的时间窗，这有利于配送者根据实际情况对配送路线进行调整，而顾客偏好时间跨度小的时间窗，从而确保送达时间的可靠性。综合考虑两者，本文随机生成了顾客点的送达时间，并根据顾客点的时间窗跨度设置顾客点的时间窗范围，确保物流配送公司既可以对配送路线进行小范围调动，又确保了顾客的满意度。

(3)车辆装载容量的设置 现有同城配送主要由电动车与摩托车完成，装载能力十分有限，另外顾客订购生活快消品通常是为了满足未来一段时间内的消耗，订购的数量较多。综上考虑，设置车辆额定装载量Q=30，并在[7，12]的区间内随机生成了各顾客订单所需要的商品重量。

此外，在参数设置上，本文拉格朗日松弛算法的参数设置为α=1.2，γ=0.2，β1=5，终止条件为问题上下界误差率β2 不超过5%。

3.2 算例求解及分析

为验证算法的有效性，本文分别构建了顾客订单数为15、20、25、30、35、40的算例，相同订单数的算例平均运行时间如图3所示。由图3可知，顾客订单数的规模对于问题求解时间的影响极大，在订单数逐渐增加时，Cplex和本文算法的求解时间都会上升，但本文算法求解时间的上升幅度明显低于Cplex，问题规模越大，两种方法求解时间的差距越大。这是由拉格朗日松弛算法自身的特性决定的，由于本文在利用拉格朗日松弛算法求得下界的同时，也会得到问题的高质量的上界，这十分有利于问题上下界差距的缩小，从而极大地减少了问题的求解时间。

因为MTPDVRPTW 的NP难特性，Cplex求解器很难在有限的时间内求得最优解，所以针对每个算例设置了两个终止条件:①问题上下界误差小于5%;②达到所设置的最大运行时间。满足两者之一即终止，输出当前得到的最优可行解。改进的拉格朗日松弛算法和Cplex的求解结果如表1所示。可以发现，改进算法所求得的上下界仍存在一定的误差，但与CPLEX 求解器的求解结果进行对比，本文算法的求解速度和求解质量均优于CPLEX求解器，体现了本文算法较好的性能。

由于传统的拉格朗日松弛算法在可接受时间内并不能得到问题的可行解，无法提供原问题上界。而本文算法不仅保留了传统算法求取下界的优势，还提供了一种较好的求取问题上界的方法。为了进一步观察在算例计算过程中问题上下界的变化趋势，本文针对上述算例在算法执行过程中的每一次迭代中都记录了上界和下界，如图4所示为算例4的上下界逼近图，其他算例的上下界变化趋势与图4基本一致。如图4可见，在本文算法的执行过程中，问题的上下界不断逼近，最终得到了高质量的上界，即问题的可行解。

表1 改进算法与CPLEX求解结果表

为了确定参数设置的有效性，在α=1.2的前提下，使得γ在区间[0.1，1.0]选取了不同的数值，随机选取了算例4与算例7进行求解，不同γ值时的求解时间如图5所示。可以发现，当γ=0.2时，求解时间最短(分别为75 s，186 s)，说明了本文参数设置的有效性。另外，随着γ的增加，求解时间总体呈上升的趋势，这是由于本文的次短路方法虽然可以较好地构建原问题上界，但在子问题求解过程中，由于接受了更多的标号点，导致子问题求解时间比传统算法稍慢，若仅采用次短路的方法进行问题求解，下界提升较慢。本文采用了一定的概率使用次短路方法构建问题上界，既可以较快地找到可行解，又保证了问题下界的更新速度，因而具有较好的性能。另一方面，从图4也可以看出，如果不采用次短路的方法(γ=0)，传统拉格朗日松弛算法在1000 s内均无法得到可行解，消耗的时间将远远超过本文改进的拉格朗日松弛算法。

4 结束语

本文针对带有社会化库存特征的带时间窗多回程混合取送同城物流配送问题，建立了混合整数模型，并针对传统拉格朗日松弛算法无法有效求解问题上界的缺陷，采用次短路的优化思想构建了原问题上界。该思想为传统的拉格朗日松弛算法注入了获取可行解上界的能力，使得该算法在求取下界的同时能够快速得到高质量的上界，从而实现上下界的并行求解，为快速求得问题最优解或高质量可行解提供了途径。计算实验表明，本文算法的求解速度和求解质量均优于CPLEX 求解器，从而体现了本文算法较好的性能，也证明了模型的合理性和算法的有效性。

本文研究中的模型是针对确定性问题而建立，未考虑配送服务当中的一些不确定因素影响，如服务时间的不确定性、行驶时间不确定性等。随着即时配送市场规模的不断扩大，物流配送中的不确定性对于现有调度方式将是一个巨大的挑战，这些问题将在未来的研究中予以深入考虑。