托盘装载约束下带时间窗的配送车辆路径优化研究

刘永，岳志城，王勇

(重庆交通大学，a.经济与管理学院；b.智能物流网络重庆市重点实验室，重庆 400074)

0 引言

随着全球电子商务的快速发展，快递配送问题经常被推上新闻，货物堆积如山，码放不规整造成快递配送效率低，装卸不灵活，货损率高的问题，影响着快递服务质量。三维装载方案作为一种车辆空间规划的方法，可以提高车厢容积的利用率，降低不合理运输。而配送车辆路径优化可以优化配送线路，降低配送成本。在上述背景下，采用三维装载约束下带时间窗的配送车辆路径问题(Three-Dimensional Loading Constrain with Vehicle Routing Problem,3LCVRP)显得日益重要。

三维装箱问题(Three-Dimensional Bin Packing Problem,3DBPP)是在三维空间内，对内部货物进行规则和有序的排列与堆积，以求得最佳摆放方式提高空间内的利用率。三维装箱属于NP 难题，国内外学者对此展开许多由浅及深，由单一变复杂的一系列研究。其中，GEORGE等[1]最早提出一种基于“层”或“墙”的高装载率装箱方案，求得集装箱内空间的充分利用。随后，崔会芬等[2]和EL 等[3]考虑装载容积和货物放置方向等约束，提高装载过程的合理性。李俊等[4]使用贝内排箱的方式，将货物堆积的不同块再进行块堆积，进一步提高集装箱装载率。在容器选择中，GZARA等[5]提出采用层级理论结合搜索树算法，基于层的列生成方法解决了将货物码放到托盘中的问题，却没有继续完成车辆装载部分。杨玉冰等[6]将包装半成品装入集装箱的两阶段二次装箱问题，为二维切割和装箱组合问题的求解提供了有效途径。三维装箱的相关理论研究已取得较为丰富的研究成果，但在三维模型与方法的实际操作便利性和需求客户点的货物高效区分等实际应用方面还存在一些待完善的问题。为此，在GZARA等[5]和杨玉冰等[6]研究的基础上，本文提出采用托盘进行两阶段二次装箱的思路，以解决货物装卸灵活性问题。

在三维装载与路径优化结合考虑的问题上，GENDREAU 等[7]提出3LCVRP模型。根据GENDREAU等使用的示例，CHEN等[8]设计禁忌搜索算法，综合考虑客户对服务时间的要求，最终产生了更为高质量的解决方案。BORTFELDT等[9]建立混合整数规划模型，考虑三维装箱约束和车辆的分配使用，并改进遗传算法进行求解，该研究对三维装载车辆调度问题的推进具有推动作用。杜博文等[10]针对少量的货物类型，提供一种带三维装载的一对一配送路径优化。王勇等[11]对三维装载约束下4种货物类型求解车辆路径优化方案，并与经典的启发式算法结果进行对比。但三维装载与路径结合考虑的难度较大，目前，研究仅考虑了较少的货物类型，现实快递行业中存在着诸多不同大小的包装。

综上所述，快递配送过程中采用三维装箱可提高货物装卸效率和车辆装载率，且配送路径优化也可节约时间成本和缩短运输距离。为此，充分考虑快递货物在配送装箱过程中因货箱种类众多带来的装卸作业复杂和不灵活等问题，本文引入可伸缩高度的托盘作为货物码放载体，扩展了货物类型，探索托盘三维装载方案对配送成本的影响，并结合“砌墙”理论构建基于托盘三维装载约束下带时间窗的配送车辆路径问题3DPP-VRP (Three Dimensional Packing of Pallet-Vehicle Routing Problem)模型，依照货物体积生成三维装载初始解，通过时空聚类生成路径初始解，结合启发式求解方法完成对托盘装载、车辆装载和配送路径的求解过程。

1 问题描述

本文引入可伸缩支撑结构托盘作为快递货物装卸载体，并设计三维装载规则集中码放各个配送站点的货物，这种统一有序的操作既有利于提高站点的装卸速度，节约货物配送时间，又能保证货物在配送过程中规整有序，提高物流服务质量。

托盘可调节高度的支撑结构有利于根据货物量灵活调整高度并进行堆叠规则码放，利用三维装载约束算法也可进一步优化托盘与车辆的空间利用率，如图1 所示。具体做法是，根据不同客户点用托盘进行区分，当货物过多导致码放高度超过最大高度限制(即车厢高度)时，采用下一个托盘进行货物装载，直至该客户点的货物码放完成。

图1 可伸缩立体式托盘Fig.1 Diagram of retractable three-dimensional pallet

为充分发挥物流资源的利用效率，提高车辆装载率，对配送车辆装载的三维空间进行优化设计调整，本文引入托盘三维装载和客户服务时间窗等约束，构建配送车辆装载率最大和物流运营总成本最小的双目标车辆路径优化模型。传统三维装载方案与本文方案对比如图2所示。

图2 传统方案与托盘方案对比Fig.2 Comparison between traditional scheme and pallet scheme

图2 中，优化前为传统三维装载方案，该方案以容积装载率最大为优化目标，在实际配送过程中存在区分货物困难的情况，以及卸载货物效率低下的问题。通过使用托盘三维装载方案优化后，货物通过三维装载算法装载入托盘，根据实际货物量确定托盘高度，再将不同高度托盘视作长宽相同，高度不同的长方体装载入车厢。

托盘三维装载约束下配送车辆路径优化方案如图3所示。首先，将不同高度的托盘通过三维装载优化装入车厢，得到该车厢内所有托盘的客户点编号、位置信息及服务时间窗等；其次，依据该车辆服务的客户点，进行配送路径优化；最终，得到托盘三维装载下的配送方案最优解。在整个配送过程中，由于托盘的使用，可以以托盘为单位进行装卸工作，提高装卸效率，降低因装卸过程导致的时间成本。

图3 托盘三维装载下的配送方案Fig.3 Distribution scheme under three-dimensional pallet loading

2 模型建立

2.1 研究假设

为便于研究，本文基于如下假设：

(1) 快递货物包装均为形状规则的长方体盒状，本文不考虑袋装货物的装载情形。

(2)对于货物重心稳定与包装支撑方面暂不考虑，本文仅计算装载率部分。

(3)车厢内货物的质量和路线中的坡度等不影响单位距离配送成本。

(4)传统三维装载方案因在每个客户点需要区分货物归属，默认每个客户点卸载过程需要至少0.5 h的时间。

(5)每辆配送车辆负责一条配送线路，任意两辆配送车辆不进行相同的路线配送。

2.2 装载设计

在托盘与车厢的装载设计上，本文采用“砌墙法”进行三维装载设计，如图4所示，具体步骤如下。

图4 “砌墙”装载方式Fig.4 Wall loading method

Step 1 将被装载货物的三维按照l ＞w ＞h的顺序进行重新排序。

Step 2 对货物体积按照由大到小的顺序进行排序生成初始遍历序列。

Step 3 车厢高度为托盘的最大高度，以托盘最左方、下方及后方的点作为坐标原点，检测货物的三维是否满足lkmn≤Lkm,wkmn≤Wkm,hkmn≤Hkm。

Step 4 对于没有超出托盘约束的货物首先检测ykmn+wkmn≤Wkm。若超出，则检测下一个货物；没有超出托盘约束，则检测xkmn+lkmn≤Lkm。若超出，则更新y坐标，即向前一层进行装载；没有超出，便继续检测货物的高是否能放入当前z轴，即zkmn+hkmn≤Hkm。若超出，更新x坐标，向右进行装载；若不超出，便在当前位置放入货物并重新更新x轴、y轴及z轴的坐标。例如，在空托盘内放入第一个货物，检测均未超出托盘三维后，其新的检测点更新为z1=z0+h1，x1=x0，y1=y0。

2.3 符号定义

本文涉及的相关变量和含义如表1 所示。

表1 符号定义Table 1 Symbol definitions

2.4 模型构建

本文以配送中心的物流运营总成本和车辆平均装载率作为目标，为求得总成本最低和车辆装载率最高，建立基于托盘三维装载下车辆路径优化模型。

双目标为

对于带有百分比的最大值和常数的最小值的多目标最优值问题，本文采用多目标线性加权法将多目标优化模型式(1)和式(2)转换成单目标优化模型，其数值越大，表示方案越优，将双目标转化后形成的目标函数为

式中：S为车辆总数；β为成本转化权重系数，0 ≤β≤1，其比重通过熵值法确定，本文取0.5，即装载率和总成本同等重要。

约束条件为

式(5)～式(10)表示摆放第n个货物时，不能超出托盘的三维限制；式(11)～式(13)表示任意两个货物之间不发生空间上的重叠；式(14)～式(16)表示任意两个托盘之间不发生空间上的重叠；式(17)表示每条运输线路只派一辆车进行配送；式(18)是消除路线规划中的子回路；式(19)表示车内货物重量之和不得超过运输车辆的最大载重量；式(20)～式(22)是决策变量约束。

计量模型中每个主要解释变量间有可能隐含多重共线性问题，本文采用Pearson方法逐次计算了每个主要解释变量的相关系数，所有主要解释变量的相关系数均小于0.4，可知每个主要解释变量间不具有严重的多重共线性问题。

3 算法设计

3.1 算法总体设计

本文在混合模拟退火-遗传算法的基础上设计3DRP算法进行求解，首先，对空间内各个物流节点的位置进行时空聚类并更新聚类中心，得到较好的聚类结果；随后，将该聚类中心中各个结点的货物进行三维装载，其中，包括生成初始序列，对初始序列的货箱进行检验，得到初始解，计算适应度；随后，随机生成旋转后的货物信息，通过模拟退火-遗传算法的交叉、变异及选择等操作生成新的序列，并进行检验得到新的解，在不断的退火迭代过程中选择最高的适应度对应的解，对于没有装载的货物打包成新的待装载货物装入下一个托盘，终止条件中ΔC表示迭代前后适应度函数的增量，Te表示当前退火温度；然后，根据聚类结果进行车厢装载，针对车厢内的客户进行路径优化，产生最优方案；最后，得出总路程、装载率、总成本以及装卸时间等结果，算法流程如图5所示。

图5 算法流程Fig.5 Algorithm flow chart

3.2 时空聚类

为便于进行路径优化，减少算法的运行时间，本文结合各物流配送点的空间位置对物流点进行时空聚类[12]，首先确定聚类中心，在聚类中心周围内分类不同的时间范围和空间范围，理论上是基于余弦距离以及欧几里得距离进行客户点规划，本文所用k-means时空聚类公式为

式中：Dob为时空距离；t1和t2为时间窗前后时间；δ为距离与时间的转换系数。客户聚类是获得更好的物流网络配置和确保高效配送的方法。

3.3 编码设计

编码过程主要包括三维装载的编码和配送车辆路径优化的编码，其编码结构采用元胞数组的形式。三维装载的编码表示为cargo[o,k,m]，即在第o个客户聚类中，第k辆车的第m个托盘内货物的三维装载状态。其中，该客户点的货物若在该托盘内，则货物状态为1；否则，为0。三维装载结果依据货物长、宽及高等大小判断，采用“砌墙”法进行三维码放判断，得到货物在托盘中码放的三维空间布局状态。三维装载编码的结构如图6 所示。对于路径优化的编码部分，客户点编码采用自然数编码，每辆车的行驶路线被存在元胞数组route[o,k]，即第o个客户聚类中，第k辆车的行驶路径被存在route 中的第o行，第k列中。路径解在元胞数组route中的结构如图7所示。route[o,2]表示在聚类o中，配送车辆2从配送中心0出发，首先到达客户点4，随后，依序到达客户点2，5，1，最后，返回配送中心0，该解在算法中呈现在元胞数组内的第o行，第2列中，其内容是[0,4,2,5,1,0]。

图6 三维装载解货物编码的结构Fig.6 Structure diagram of cargo

图7 路径解编码的结构Fig.7 Structure diagram of path solution

3.4 货物旋转

为充分利用车内空间，本文算法在迭代之前对货物的摆放形态进行预处理，即货物的旋转。算法中将货物的6 种旋转给予相同的比重，利用函数int[r and(·)×6]+1 得以实现，分别实现1～6的6种选择，对应旋转方式分别为货物未旋转、绕x轴旋转、绕y轴旋转、绕z轴旋转、绕z轴旋转后绕y轴旋转及绕x轴旋转后绕y轴旋转。具体展示如图8所示。

3.5 遗传操作

(1)选择操作

通常而言，父代染色体适应度高低会影响算法结果的好坏，选择质量较优的染色体适应度函数就会越高，被保存下来的概率也就越大。本文父代以货箱体积由大到小排列，可以提高算法效果。

(2)交叉操作

在交叉操作过程中，由于配送中心是配送路径的出发点和结束点，所以，为避免交叉操作过程中丢失配送中心，本文在进行交叉操作之前先将染色体前后剔除配送中心基因0，然后，再进行交叉操作。交叉采用局部映射的方法，首先，对随机产生的片段进行两两互换；然后，进行重复基因的替换，两部分的交叉操作是相互独立的。交叉操作如图9所示，具体步骤如下。

图9 交叉操作Fig.9 Cross operation

Step 1 随机选择两个父代染色体命名为Z1和Z2，从范围[1,n]选取两个随机数，选择随机数区间[Fbegin,Fend] 对应染色体中的第Fbegin到第Fend个基因的片段进行两两交叉互换。

Step 2 删除新染色体片段中与原片段重复的基因，保留没有重复的基因片段。

Step 3 对被删除的基因片段补充未重复的基因，新补充的基因前后顺序随机排列。

Step 4 返回新的子代。

(3)变异操作

变异操作是在选择和交叉操作产生的染色体后，随机选择某个或者是多个基因产生突变，如图10所示。首先，给予一定的概率Pm作为突变概率选择一条染色体产生突变；其次，随机选择染色体中的两个基因进行互换，产生新的子代，变异互换基因的过程中不考虑产生重复基因，因此，不需要进行重复基因的删除和补充的操作。

图10 变异操作Fig.10 Mutation operation

3.6 终止条件

设退火算法的初始温度为T0，算法的终止温度为Tend。退火时降温的速度满足Te+1=ωTe，ω为[0.8,1.0]内的温度系数，该系数随机产生。当温度小于等于终止温度或迭代次数达到100次，便终止循环。货物量存在较多的情况时，需要第2个甚至第3个托盘进行装载，根据以上货物装载的编码方式会得到装载好的货物编码为1，因此，要将未装载的货物(编码为0 的货物)进行打包，生成初始解进行下一托盘的装载。

3.7 算法检验

由于缺少3LCVRP相关问题的标准数据集，为验证算法的有效性，本文将LOH 和NEE 的三维装载经典算例LN 算例[13]作为测试对象，并与NGOI等[14]与BISCHOFF 等[15]实验结果进行对比，具体如表2所示。

表2 算法结果对比Table 2 Comparison of algorithm results

通过对比可以看出，在平均容积装载率为68.2%情况下，本算法与其他算法求解差异不大，3 种算法求解装载率结果均在68%～69%，但本文算法拥有更少的平均未装载货物量，在快递行业是尤为重要的，因为这意味着更少的延误订单产生以及更少的申诉量，因此，可以认为本算法在装载方面是有效性的。

4 实例分析

4.1 实例概况

本文以重庆市某快递公司配送中心向周围203个客户点配送为例进行实例分析。对传统的三维装载方案和托盘三维装载方案的求解结果进行比较。车厢规格为6 m×2 m×2 m，车辆行驶速度为15 km·h-1，其中，货车载重量15 t，租赁费和维修费用每次100元，运输过程中违反客户服务时间窗的惩罚成本为100 元·h-1，运输成本为5 元·km-1，每次卸载托盘耗用5 min。

其物流配送节点分布在配送中心0的周围，由于每个配送中心向同一站点配送的频率通常是每天两次，因此，物流结点的需求都是以0.5 d作为一次统计，本文以每个结点的最早时间窗为8:00，最晚时间窗互有不同。快递行业包装没有具体规格标准，因此，本文采用大小不一的6 种常用规格的货物作为研究，具体如表3 所示，各个配送点对货物的需求量也有所不同。

表3 货物规格Table 3 Cargo specifications

由表3中可以看出，货物序号是按照货长大小要求从大到小排列，这有利于“砌墙”理论产生更高的装载率。货物1～货物3属于中型货物，货物4属于中小型货物，货物5和货物6属于小型货物。

4.2 结果与分析

4.2.1 托盘结果分析

该算例所设计的3DRP 算法基于改进的混合模拟退火-遗传算法进行改进，其中，初始温度T0=100，终止温度Tend=1，种群规模为150。本文将货物装入长1 m，宽1.2 m的托盘，限制托盘装载最高的高度为2.0 m，算法运行环境为Matlab R2018a,Windows10 Intel(R) Core(TM) i7-7660U CPU@2.50 GHz。

部分客户点因需求量不同而产生的不同高度的托盘展示如图11 所示。由于货物需求量的不同，客户点的托盘高度也不相同，托盘最低高度为0.4 m，最高高度为2.0 m，当需求量超过这个限制时，会增加装载托盘的使用。因此，部分需求量较大的客户点托盘数会超过1个，经过算法装载得到所有客户点托盘平均装载率为86.44%，能够充分利用装载容器的空间。

图11 不同高度部分托盘装载展示Fig.11 Display of partial pallet loading at different heights

4.2.2 车厢结果分析

完成托盘装载后需要进行托盘入车的规划，本例中将客户点分为三个聚类，分别为R1、R2、R3。图12 表示R3 聚类中，通过3DRP 算法求解后得到的车厢内托盘摆放示意图。其中，每个长方体被视作一个待装载的托盘，图示编号为托盘卸货结点的编号与托盘高度，同一指引线的上下托盘表示码放关系。例如，在图12中，R3聚类的车辆1服务编号108 客户点的托盘高为0.4 m，107 客户点的托盘为1.5 m，并且该托盘被压在客户点108托盘之下。

图12 R3聚类中部分车厢内托盘三维装载Fig.12 Three-dimensional loading diagram of pallets in some R3 cars

经过算法得出方案最终解如表4所示。其中，R1、R2 及R3 聚类分别得到7 条、7 条及5 条配送线路，平均装载率分别为81.23%，84.04%，83.6%。所有线路平均每辆车配送成本为606.84元，平均装载率为83.02%，且车辆的平均里程均未超过100 km。

本文所使用的托盘装载配送方案与传统未使用托盘的三维装载配送方案在本例R3中的优化结果对比如表5所示。可知，以R3聚类区域的配送方案结果为例，本文提出的托盘三维装载方案在总配送成本、时间成本及配送车辆运输距离等指标方面要远优于传统三维装载方案，仅车辆装载率指标要略低于传统三维装载方案。传统三维装载方案是以最大车辆装载率为优化目标，较少考虑货物区分与装卸便利性，其车内货物区分与装卸效率较低，由此导致的平均配送时间成本剧增，达到了7738.37 元。然而，本文提出的托盘三维装载方案的平均时间成本为193.68元，仅为传统三维转载方案的2.5%，相当于节约了97.5%的时间惩罚成本。此外，传统三维装载方案因仅考虑车辆的最大装载率目标，其配送车辆多频次重复访问客户点，造成运输距离剧增，也是该方案成本较高的主要原因之一。综上所述，采用托盘三维转载方案可以兼顾车辆高装载率，并有效节约物流运营成本，提高车辆利用率。

表5 R3聚类中优化前后方案对比Table 5 Comparison of schemes before and after optimization

5 结论

本文针对快递行业中存在的配送效率低和易发生爆仓等问题，在三维装载方案的基础上提出以可调节支撑结构高度的托盘为中间载体的托盘三维装载方案，建立托盘三维装载下车辆装载率最高和配送总成本最低的双目标模型，设计3DRP 算法进行求解，得到结论如下。

(1)使用托盘作为中间载体的两阶段装载模型可以兼顾高装载率与高的配送效率。当卸货时间被作为时间成本考虑在多目标优化模型中时，托盘三维装载方案相比单纯只考虑装载率方案，可以兼顾车辆高装载率，并节约97.5%的时间惩罚成本。相比传统方案来说，托盘三维装载方案下的车辆配送路径优化更加高效，车辆利用率更高。

(2)配送效益与各成本构成因素成反比，但与车辆装载率成正比。在车辆配送过程中，车厢容积装载率不作为配送成本的一部分，却影响着配送成本，在3 个聚类范围内的装载率分别为81.23%，84.04%，83.60%，对应的成本分别为5381.02，3086.20，3062.97元。为提高3LCVRP模型的性能，一方面可以降低各类成本因素，同时，也需要提高配送车辆的装载率。