基于一种新型分支定价算法的电动车支线镇际快递配送路径规划研究*

师欣欣，陈树国，马 弘，邓明荣

(1.浙江大学管理学院，浙江 杭州 310058；2．国网浙江省电力有限公司，浙江 杭州 310007;3.浙江大学工程师学院，浙江 杭州 310015)

1 引言

伴随着互联网经济的蓬勃发展，网上购物成为人们消费活动的重要组成部分，国内对快递的配送需求也呈现爆发式增长态势。2019年，中国快递服务企业业务量累计完成630亿余件，其中农村快递增速比城市高近10个百分点[1]。支线镇际的快递配送是影响配送整体效率和服务水平的重要环节，快递的大规模和高时效性特点为支线镇际配送问题提出新的要求和挑战。与此同时，随着新能源汽车在续航、充电时间等方面的表现日益提升，将电动汽车引入支线镇际快递配送成为可能，并将有助于物流行业绿色经济的发展。本文主要对电动汽车在城镇快递配送中的路径规划进行研究，并提出与之相适应的分支定价算法求解该问题。

本文以支线镇际快递配送系统为研究对象，给定运营周期内城镇之间的快递配送需求，要求结合电动车辆自身属性，决策车辆的行驶路径和充电地点及时长，在满足所有运输需求的前提下，最小化总运输成本。由于Kerivin等[2]证明了SPDPR问题(the Splittable Pickup and Delivery Problem with Reloads)的复杂度为NP-hard，本文的研究问题较SPDPR问题附加考虑了多种车型以及电动车辆的相关特性，使得SPDPR问题成为了本文研究问题的一个特例，因而本文研究问题的复杂度亦为NP-hard。

已有的与城际、镇际快递配送应用相关的研究，大多围绕启发式算法和智能优化算法展开。Smilowitz等[3]在运输模型中将航空配送系统的剩余运力纳入考虑之中，利用割平面法计算问题下界，并提出一个高效的线性规划取整算法获得问题可行解。Li等[4]则在有资源管理约束的服务网络设计中考虑到异车型的问题。该研究将原问题分解为2个子问题，并利用禁忌搜索不断指导和调整2个子问题的求解。在精确求解算法方面，Andersen等[5]针对铁路运输系统设计与之对应的分支定价算法，对小规模和中等规模问题实现了高效求解。但是，由于研究对象为铁路运输系统，模型并未涉及多车型、仓储管理、充电桩管理等本文研究所必须要考虑的问题。

分支定价作为精确求解整数规划问题中的经典算法，已经被广泛应用于车辆路径规划、网络设计和背包问题等各个研究领域中[6 - 8]。在本文的研究问题中，分支定价算法的应用要求对电动车辆建立基于路径的数学模型，和经典的基于边构建的模型相比，该模型提供了更优的问题下界，同时规避了车辆之间建模对称性所带来的困扰，有利于问题的高效求解。针对不同的应用场景，分支定价算法框架中的分支策略、子问题求解策略、割平面策略和强化策略等部分都需要完成有针对性的算法设计。基于上述研究，本文针对电动汽车在镇际快递配送的路径规划这一问题提出相应的分支定价算法，给出有利于平衡搜索树的分支策略，结合割平面策略，用Java语言进行了实现。在实验部分，将分支定价算法与求解器和经典的启发式算法进行比较，实验结果验证了本文算法的可行性和有效性。

2 问题描述与模型建立

在镇际快递配送系统中，某2个城镇中转站之间每隔一段时间会产生一批新的快递运输需求，即需要将一定数量快递包裹在规定的时间窗内从城镇中转站1送达城镇中转站2。在运输车辆资源有限的情况下，为进一步节约运输成本，降低车辆空驶率，本文规定该配送系统支持以下2种运输规则：

(1)同一批货物可以以任意数量被分装在不同的车辆上进行运输。

(2)每个城镇中转站配有仓库，可以临时存放货物，货物在中转站可以选择更换运输车辆。

在时间维度，与文献[5]相同，本文假设快递运输需求和车辆路径都具有周期性重复的特点。所有快递运输需求的时间窗长度不超过一个运营周期，每辆运输车的配送路径要求在一个运营周期形成环路。通过图1中的运输方案来说明该假设。在该实例中，运营周期为10 h。表1列举了5批待完成运输需求的信息，其中需求D1的货物数量为30，需要从城镇中转站2运往城镇中转站3，在某个配送周期内，最早取货时刻为1，要在当前配送周期的时刻5之前送达。注意到需求D3、D4和D5的最晚送达时刻小于或等于最早取货时刻，此时最晚送达时刻所在周期指相对于最早取货时刻所在周期的下一个运营周期，即允许需求的时间窗跨越周期。在图1中，2辆电动汽车完成了D1到D5的运输需求。载重量为50的车辆1在1时刻从城镇2出发，途径城镇3、城镇4，到达城镇中转站4后在其充电桩充电1 h并空闲等待3 h后从城镇4出发返回城镇2。载重量为20的车辆2在1时刻从城镇5出发，途径城镇3、城镇1、城镇2、城镇1,在一个周期后返回城镇5。需求D3被拆分成2批(数量为10和20)进行运输，数量为10的货物首先由车辆2运送至城镇中转站2的仓库存放4 h后由车辆1运往目的地城镇3。

为了更好地描述问题，与文献[9]类似，本文选择在时空网络(Time-Space Network)上构建模型。在时空网络中，原配送网络中的每一个城镇中转站以及每一条边在每一个时刻均有一个备份，使得时空网络中的每个点和边既定位空间也定位时间。如图2所示，网络中共包含2类边，运输边和等候边。运输边代表快递包裹或电动汽车实际的空间位置转移，等候边代表快递包裹在仓库存放等候或者电动汽车在某中转站充电或者等候。注意到由于问题具有周期性，在周期末尾的边会循环指向周期开始，代表进入下一个新的运营周期。

Table 1 Delivery demand example

Figure 1 An example of transportation solution

Figure 2 Time-space network

2.1 符号说明

记G(N,A)代表时空网络。假设每一个城镇中转站配有固定数量的充电桩。N代表时空网络中点的集合，A代表时空网络中的边集，包括运输边集E和等候边集H，记为A=E∪H。将整个时间周期划分为离散的时刻T={1,2,…,Tmax}，对于实际的物理中转站集合L，有N=L×T={lt|l∈L,t∈T}，其中lt代表t时刻的中转站l。定义s(o,d)∈S为一个运输服务，它包含了时空网络中从中转站o到中转站d的所有时刻的运输边的集合。

2.2 模型构建

Table 2 Notation list

(1)

(2)

(3)

(4)

(5)

(6)

(7)

zτ∈N,∀τ∈θ

(8)

约束(2)保证所有运输需求都在规定的时间窗内被满足。约束(3)限制在所有的运输边上，货物总量不得超过车辆的总载重量。约束(4)代表每个中转站l最多派出车型为p的汽车数量为ubpl。约束(5)保证了每个中转站的仓库在各时刻容纳的快递货物量不超出其容量限制。所以，对于时空网络中的每一个点lt∈N，将从该点出发的等候边上的所有非终点货物流相加，计为存放在当前仓库的总货物量。dk为需求k的实际目的城镇。这里，为了简化模型中可能涉及的仓库存储成本，本文假设当快递被送达目的城镇的中转站时，它即刻从该中转站分拨至快递货物目的地具体地址附近，而不再占用中转站的仓储资源。约束(6)限制每个中转站同时充电的最大车辆数。

3 分支定价算法设计

为了获得更高质量的LP松弛值，并且消除基于车辆构建模型中车辆同质所引起的对称性问题[10]，本文选择基于路径构建模型。这相当于对经典的基于边构建的模型进行Dantizg-Wolfe分解[11]，模型中会包含大量车辆路径决策变量。对于该模型，列生成算法有助于求解其LP松弛问题(zτ松弛为实数变量)。算法主要在受限主问题RMP(Restricted Master Problem)和子问题之间协调计算。为了检查RMP中的解对于主问题MP(Master Problem)是否已经最优，子问题将被求解。在本文算法中，每一个中转站l和每一种车型p均对应于其中一个子问题。将列生成算法应用在分支定界搜索树中的每个节点，即为分支定价算法，算法流程如图3所示。

Figure 3 Flow chart of the branch and price algorithm

3.1 受限主问题RMP

3.2 分支策略

在分支定价算法中，本文采用了3种分支策略，分别是服务分支策略、子问题服务分支策略和运输边分支策略。3种分支策略的执行优先权依次递减。当得到某LP实数解时，首先考虑是否可以执行服务分支策略，如果不满足条件，则继续检查是否可以执行子问题服务分支策略，最后检查运输边分支策略。运输边分支策略可以保证最终得到可行解。

3.2.1 服务分支策略

服务分支策略针对所有子问题的某一服务s(o,d)∈S来进行分支，即所有电动车辆提供服务s(o,d)的数量之和需要为整数。服务s(o,d)为包含了时空网络中所有时刻从中转站o到d的运输边集合。本文通过向RMP中加入以下相对应的约束来进行分支操作。

(9)

(10)

3.2.2 子问题服务分支策略

同服务分支策略类似，子问题服务分支策略针对某一子问题的某一服务s(o,d)∈S来进行分支，即从某中转站l∈L出发，第p∈P种电动车辆提供服务s(o,d)的数量之和需要为整数。RMP中对应的分支约束如下所示：

(11)

(12)

3.2.3 运输边分支策略

在运输边分支策略中，检查每个子问题中电动车辆走过某一运输边的数量和是否为整数，若存在非整数，同样选取小数部分最接近预先设点值的一条运输边a∈E进行分支。该分支对应于RMP中的约束(13)和(14)。运输边分支策略可以保证最终的解为可行解，但它往往会造成搜索树2个分支的不平衡，本文将它放在分支策略中的最后来保证解的可行性。

(13)

(14)

3.3 割平面策略

在该问题中，本文还使用了普遍应用于服务网络设计问题的强限制约束(Strong Forcing Constraint)。由于该强制约束数量众多，本文将其作为割平面策略，只在适当的时候采用并将其加入到RMP中。由式(15)可看出，每一条运输边和每一批运输需求均对应于一个强限制约束。

(15)

3.4 子问题

物流配送中电动汽车在很多方面具有与传统汽车不同的特征[12]。本文假设电动汽车通过在中转站的充电桩充电来进行能量供给，且采用部分充电模式，充电的最小时间单位同时空网络。假设充电时间和充电可供行驶里程成线性关系，单位时间充电可供电动汽车行驶里程为g。为方便起见，将电动汽车的电池容量同样用行驶里程来衡量，假设所有车辆的电池容量为Power。

(16)

(17)

(18)

(19)

(2)当考虑在点i充电时，对于以点i为首的等候边(i,j)∈H，生成下列新标签：

(20)

(21)

(22)

其中，chargeMark表示该路径处有充电行为。

在本文的列生成算法中，针对特定子问题中的每个出发时刻，求出其最短路径，若机会成本为负则将该最短路径变量加入RMP中进行下一轮求解。

3.5 强化策略

在本文提出的分支定价算法中，每隔一定数目节点的LP问题被求解后，会使用一次强化策略。首先统计出2个变量，cycleSet和lpColumnCount,其中，cycleSet代表当前列生成算法产生过的所有路径变量构成的集合，lpColumnCount代表上述路径变量对在所有节点LP最优解中的值的和。接下来以lpColumnCount为依据对cycleSet中的路径变量进行筛选，识别cycleSet中的关键路径变量并将其加入求解器，有利于强化策略在短时间获得更高质量的可行解。

(23)

至此，计算出所有组组内路径变量之间的距离并将其存储在cyclePairList中。在图4所示算法(其中包含了本文提出的路径变量筛选算法)中，我们设置targetSize为将路径变量集合筛选后的目标集合大小。路径变量筛选算法根据lpCoumnCount提供的信息筛选出对问题求解关键的路径变量集合并输出该集合。

Figure 4 Flow chart of the intensification strategy

4 数值实验与分析

本节中的数值实验在安装了CentOS Linux 7，配置了Intel Pentium 3.5 GHz处理器与16 GB内存的PC机上完成。使用Java 1.8实现了分支定价算法，并使用IBM ILOG CPLEX 12.6.1求解LP与MIP问题。源代码已上传至github网站(https://github.com/JAIMX/ESNDRC/tree/dev/paper)。在实验部分，首先针对小规模算例将分支定价算法同直接用求解器求解做对比，以探究分支定价算法在精确求解小规模算例方面的性能。其次针对中等规模用例，使用分支定价算法和基于列生成的启发式算法来求解并进行比较，以探究分支定价算法对中等规模问题的求解效果。

4.1 算例说明

从文献[5]的实验数据中挑选了数据集1～12，其中5组小规模数据集构成测试算例1～5，其允许在有限时间内枚举出所有可能的路径τ并将其对应变量加入求解器中求解。7组中等规模数据集中，每组又加入了2个随机生成的数据集以构成测试算例6～12。

将各算例的规模总结如表3所示。数据生成时，对于每一个中转站，保证车辆固定使用成本随着车辆容量增大而增加。根据每组算例的具体规模，在保证有可行解的前提下，相关参数的区间取值如表4所示。

Table 3 Problem instance sizes

Table 4 Parameters values

4.2 小规模数据求解

针对小规模算例1～算例5，本文将所有可能的路径变量枚举出加入求解器CPLEX进行求解，并将其结果和分支定价算法的结果作对比。2种算法的求解时间限制均设置为2 h。分支定价算法中，按照节点的下界大小进行节点选择，优先搜索下界最低的节点，有助于更快地找到小规模算例的最优解。割平面策略只应用在父节点进行分支操作后下界没有提升的节点中，并且相应的约束会保留在当前节点。强化策略中，设置每求解10个节点使用一次强化策略，targetSize设置为1 000。表5展示了分支定价算法和求解器对小规模算例求解的结果。

在表5中，|θ|列表示所有可能路径变量的数量，本文将该数量的路径变量全部加入到求解器CPLEX中直接求解原MIP问题。由表5可看出，分支定价算法在5组算例中的4组找到最优解并证明了是全局最优。求解器CPLEX则在算例1和算例5中找到了最优解，然而对所有小规模算例都无法证明最优性。尽管在其他相关研究[4]中，求解器在提升下界方面有很好的表现，但在该问题中，相比于求解器，分支定价算法总是具有更佳的提升下界的表现。总体来说，在精确求解小规模问题方面，相比于求解器直接求解，分支定价算法在寻找可行解和提升下界方面都具有更好的表现。

Table 5 Comparison of results on small instances of the branch and price algorithm and the CPLEX MIP solver

4.3 中等规模数据求解

在求解中等规模算例时，如果使用不加强化策略的分支定价算法，绝大多数算例甚至无法在2 h内找到任何一个可行解，该实验事实表明了强化策略的必要性。为了进一步验证分支定价算法结合强化策略的高效性，本文将其与效果表现良好的常用算法——基于列生成的启发式算法进行比较。

使用分支定价算法和基于列生成的启发式算法对算例6～12中共14组中等规模数据进行了测试，求解时间均为2 h。基于列生成的启发式算法的主要思路是使用列生成算法对原问题对应的LP问题进行求解，并将求解过程中生成的所有路径变量加入求解器，求解仅包含该部分列变量的MIP问题。在分支定价算法中，由于本文的求解目标不再是全局最优，有限时间内的最优解往往由强化策略搜索得到。强化策略中，本文设置每求解2个节点使用一次强化策略，targetSize设置为1 000。表6显示了2种算法对中等规模数据的测试结果。

在表6中，强化策略|θ|表示获得最优解时加入求解器中的路径变量数。 基于列生成的启发式算法中的|θ|列表示加入求解器中路径变量数。在14组测试结果中，分支定价算法在12组数据上的表现都要优于基于列生成的启发式算法。注意到由于算例10运营周期为50，2个算法在2 h之内无法对原问题的LP问题求得最优解，所以未显示下界和最优间隔，仅对2个算法的最优解进行比较。另一方面，不同测试用例之间的最优间隔百分比的值相差较大，这主要和各部分成本之间的比例构成有关。由表6结果可以看出，相比于经典的基于列生成的启发式算法，分支定价算法在中等规模问题上具有更好的表现，可以有效解决该规模的问题。

Table 6 Comparison of results on medium instances of the branch and price algorithm and the CG-based heuristic algorithm

5 结束语

本文针对电动汽车支持的镇际快递配送系统建立基于路径变量的数学模型。模型构建在具有周期性的时空网络之中，同时考虑到车辆资源、仓储资源和充电桩资源的管理问题。本文针对该模型提出了分支定价算法。分支策略有利于削弱由时间离散化导致的对称性问题，子问题中的标签算法为列生成算法的主问题提供支持部分充电的电动汽车路径变量。分支策略和割平面策略的组合有助于实现对小规模数据的精确求解。强化策略通过筛选路径变量并利用求解器的高效性，帮助算法在求解中等规模问题时找到高质量可行解。实验对比了分支定价算法和CPLEX求解器在精确求解小规模问题上的表现，以及与基于列生成的启发式算法对比了在中等规模问题中的表现，结果表明了分支定价算法在精确求解和启发式求解方面的高效性。因为在时空网络上构建模型，时间离散化会造成问题规模的迅速扩增，加大问题的求解复杂度，后续的研究可以考虑探究上述问题在时空网络的子网络中实现精确求解的可能性[13]，以期扩大问题求解规模。