高梦伟，卢 玮 （上海交通大学 中美物流研究院 上海 200030）

0 引言

随着人工智能技术的兴起以及人力成本的逐年增长，“智慧物流”越来越受到人们的关注，其中使用智能配送车配送是“智慧物流”的重要组成部分，菜鸟、阿里、京东、顺丰等企业纷纷推出智能配送车项目来提升最后一公里的配送效率。在实际应用中，京东、唯品会推出智能配送车在大学校园内配送快递，车厢货柜大小不一，采用模块化设计，通过拆卸货柜之间的隔板，可组合成多种型号的货柜。货柜模块化设计可以使智能配送车容纳更多的包裹尺寸，为包裹装车提供更多的可能方案，可以通过优化货柜组合，选择最优的装车方案，以提高智能无人车空间利用率。

智能配送车包裹配送涉及到装载和路径规划两个重要的组成部分，其中装载要求通过合理的箱体设计来提升空间利用率，路径规划通过行驶线路优化减少行驶距离。本文研究带有拼箱设计的智能配送车路径规划问题，同时考虑时间窗约束，以总行驶距离最小为目标，规划装车和路径行驶方案。

装箱问题（bin packing problem）是复杂的离散组合优化问题，根据考虑货物尺寸的维度多少可划分为一维、二维、三维装箱，本文货柜组合装车属于二维装箱问题，即只考虑物品的长和宽。二维装箱比较著名的算法包括BL[1]、BLF[2]、砌墙式启发算法[3]、递归分支定界法[4]等启发式算法。关于车辆路径问题（vehicle routing problem），国内外的研究体系已经非常成熟，主要集中在模型应用创新和算法创新。在车辆路径基本模型上衍生了带时间窗的车辆路径问题[5]、取送货车辆路径问题[6]、多车场车辆路径问题[7]等，本文路径规划属于带时间窗的VRP问题；求解算法主要包括精确算法如分支定界法[8]、切平面法[9]、动态规划法[10]等，以及启发式算法如遗传算法[11]、紧急搜索、蚁群算法[12]等。货物配载和路径优化问题最早由Gebdreua[13]等人提出，用来解决家具配送的问题，目前把两者结合起来的相关研究比较少。在同时考虑货物配载和路径优化时，目前的解决方案主要分两类：一类是先进行路径规划，然后再调用装箱算法，检验每一条路径是否满足装载约束，如满足则为最优解，如不满足则需要重新寻找最优解；另一类是以装箱优化为主，以最优化装载率为目标形成装车方案，然后在此基础上进行路径优化[14]。

现有的关于货物配载和路径规划问题中的装车部分，主要是考虑在整个车厢空间中如何进行物品摆放，很少考虑拼箱设计情况下的装车问题。有学者研究汽车出厂物流的组合装箱问题，考虑商品车和运输工具之间特有的组合方式，不同车位可容纳不同型号的商品车，形成装载组合，是对传统装箱问题的新突破。本文研究的带有拼箱设计的智能配送车装载和路径规划问题，在现有理论基础上加入了智能配送车厢体模块设计，货柜可进行根据货物尺寸进行自由组合，这也是本文的创新之处。

1 问题建模

1.1 问题描述

智能配送车装载和路径规划优化问题可描述为：某封闭园区内使用多辆智能配送车进行包裹的末端配送，包裹按照大小和形状的不同可分为多种尺寸，为容纳各种尺寸不同的包裹，提高智能配送车空间利用率，智能配送车厢体采用模块化设计。

智能配送车厢体模块化设计是指智能配送车货柜之间的可以进行任意的拼装组合形成大小不同的货柜，从而可以装载不同尺寸的货物。整个车厢被挡板划分为多个单元货柜，每个单元货柜可容纳最小尺寸的包裹，货柜之间的挡板可拆卸，拆出挡板可将多个单元货柜组合成大货柜，拆出不同的挡板可形成不同的货柜组合方式，从而满足各类大小货物的装载。如图1，是智能配送车货柜设计简图，货柜之间的挡板可拆卸，使多个小货柜组合成大货柜。图1中A类包裹占用1个货柜，B类包裹占据2个货柜，C类包裹占据4个货柜，D类包裹占据3个货柜，以此类推。

在进行配送时，将每天的配送时间划分为多个时间段，每个时间段智能配送车运行一个班次；对于配送时间有要求的客户可以提前选择配送时间。出发配送前，后台系统需根据智能配送车不同的货柜组合形成装车方案并进行路径规划，在客户预约的时间内将货物送达，最终使得所有车辆总的行驶路径最短。

图1 货柜组合示意图

1.2 模型建立

根据上述问题建立智能配送车装载和配送的数学模型，模型中包含了以下基本假设：（1）物品单向流动，即只送货不取货；（2）智能配送车出发位置和返回位置都在配送中心，且配送中心只有一个；（3）配送中心位置已知，各停靠点之间以及停靠点与配送中心之间的距离已知；（4）每个停靠点的配送任务量已知；（5）智能配送车不得超载；（6）智能配送车货柜组合情况已知，且每种包裹对应的拼箱组合已知；（7）每个车辆只服务一条线路；（8）每个停靠点的客户预约取货时间已知；（9）在客户规定的时间内到达停靠点；（10）适合智能配送车通行的道路已知。

车体模块化设计使得智能配送车装载配送问题不同于经典的车辆装载和路径规划问题，关于车体组合优化问题的研究和相关解决方法较少。针对货柜组合这类特殊问题，本文创新性地引入SR集合，用以表示所有可能组合的情况。每种组合可容纳的货物编号集合为AR。模型中涉及到以下集合、参数和变量：

（1） 集 合

SR= ｛ ｛P1,P2,…,PR｝, ｛PR+1,PR+2,…｝,… ｝：货柜组合集合。集合内每一元素表示一种组合情况，一共有R种组合，R=1,2,3,…。

sr：SR中的任意一个元素，sr∈SR，r=1,2,3,…。表示SR中每种组合的货柜编号。

AR：货柜组合属于SR的对应包裹编号集合，R=1,2,3,…。

O=｛p|p=1,2,3,…,P｝，单个小货柜的编号集合，共P个货柜。

V=｛i|i=1,2,3,…,N ｝，包裹编号集合，共有N个包裹。

D=｛k|k=1,2,3,…,K ｝，车辆编号集合，共有K辆车。

（2） 参 数

cij：服务点i到服务点j的运输成本；

Si：车辆在i点的服务时长；

tij：车辆从i点到j点的行驶时间；

［ai, bi］：客户i的服务时间窗，ai指最早开始服务时间，bi指最晚开始服务时间；

Wik：k车到达i点的时间；

E：配送中心的开始时间；

L：配送中心的结束时间；

M：无穷大的正数。

（3） 变 量

模型构建如下：

上述模型说明如下：式（1）表示模型的目标函数，即总的配送成本最低；式（12）、式（13） 为模型的变量；约束条件可分为两部分：

货柜组合装载约束：约束条件式（2）表示每个包裹只能被安排一次，对于任意包裹，其占用所有单元货柜之和等于相应的体积，防止包裹被多次排班装车；式（3）表示每个单位小货柜最多被占用一次，对于任意单元货柜，不允许被多次组合、多次占用；约束条件式（4）、式（5）是货柜组合约束，式（4）表示每种组合可装载的包裹尺寸，对于任一特定的货柜组合，其对应的单元货柜作为一个整体，即要么同时被占用，要么同时被空置，式（5）表示包裹不可放入其对应组合之外的货柜集合，每个包裹只能被放入其对应特定的货柜集合。

车辆路径约束：约束条件式（6）、式（7）表示到达客户点的车辆的唯一性，即到达和离开某一客户点的为同一辆车；约束条件式（8）为车辆行驶路线约束，即要求每个车辆从配送中心出发，配送完装载的所有货物后再返回配送中心；约束条件式（9）、式（10）、式（11）为配送时间窗的约束，式（9）表示车辆到达下一客户的时间晚于到达上一客户的时间加上服务时间和路径行驶时间，式（10）表示每个客户点的车辆到达时间不得超出该客户点的服务时间窗，式（11）表示每个客户点的服务时间不得超出配送中心的时间窗。

2 模型求解

2.1 算法设计

在进行模型求解时，涉及到装车和路径规划两个部分。在VRP问题中，蚁群算法被普遍应用并且具有良好的求解结果，但考虑到货柜组合拼接对货物装载的特殊约束，其难以同时完成组合装车和路径规划，因此本文采用精确算法和蚁群算法相结合，优先进行装车方案求解，然后再进行路径规划。包裹装车采用精确算法，确定每个包裹对应的装车车辆和货柜位置和组合，对于形成的装车方案作为路径规划的输入，每辆车的途径点已知，运用蚁群算法求解出每辆车的规划路径。

本文的模型求解思路是：模型中货物装载部分是典型的0-1整数线性规划问题，可以利用matlab自带的intlinprog函数求解，以模型中式（2）～式（5）为约束条件，形成货物的装车方案，建立货物和车辆货柜的一一对应关系；然后采用蚁群算法对智能配送车进行车辆路径规划。将每只蚂蚁的行驶路径的长短转化为蚂蚁的信息素浓度。针对部分货物有时间窗的约束，记录每只蚂蚁的到达时间，在计算路径时引入惩罚函数，每次违反时间窗都会增加惩罚成本，并且增加的惩罚成本加到蚂蚁的行驶距离上，从而导致信息素浓度降低，最终促使蚂蚁选择路径较短且不违反时间窗的路径。具体算法流程如图2。

2.2 算法具体步骤

步骤一：输入初始信息；步骤二：求解货物装车方案；步骤三：计算车辆各个收货点的距离矩阵；步骤四：蚁群算法初始化；步骤五：蚂蚁进行路径选择，记录行驶路径、到达时间；步骤六：计算并记录最短行驶路径和行驶距离，更新信息素浓度；步骤七：判断是否满足终止条件，如果满足，进入下一步；如果不满足，回到步骤五；步骤八：判断是否所有车辆完成路径规划，如果满足，进入下一步，否则回到步骤四；步骤九：计算终止，输出货物装车方案、车辆行驶路径、行驶距离及每个节点的到达时间。

3 算例分析

图2 算法流程图

以唯品会无人车为例，在某校园内有3辆智能配送车用于每天的快递包裹配送，车行驶速为1m/s，每辆车共有28个小货柜，货柜组合如图3所示。组合集合为6种组合占用的小货柜个数分别是1,2,2,4,4,3。每种组合对应的订单编号分别为：共有84个订单，每天配送时段为10:00～17:00。部分客户选择预约配送。

图3 货柜组合

蚁群算法参数如下：蚂蚁数量为100，信息素重要程度因子为1，启发函数重要程度因子设置为5，信息素挥发因子为0.4，最大迭代次数1 000，惩罚值1 000。

输入货柜组合对应订单编号、订单位置、客户预约时间窗信息，初始化参数，通过matlab算法求解，可以同时得出装箱和路径规划的方案。

最终求解结果为：当天车辆运行两个班次，图4为第一班次车辆装载方案；图5为第二班次车辆装载方案；表1为车辆配送路径；图6为第一班次车辆行驶路径；图7为第二班次车辆行驶路径。结果如下所示：

图4 第一班次包裹装车组合方案

图5 第二班次包裹装车组合方案

行驶总距离=3.877+3.4757+5.099+3.604+4.5044+4.2956=24.8557（km）。

4 结束语

本文针对智能配送车的货柜组合和包裹配送这一问题建立了数学模型，并针对模型设计了相应的算法，解决了智能配送车在封闭园区内配送的货物装车和路径规划问题，通过算例验证了模型和算法的有效性。但是仍有很多不足，比如没有考虑同一收货人有多个货物的情况；设计算法时没有考虑装载和路径规划之间的相互影响。后面将针对上述问题进行更深入的研究。

表1 车辆配送路径

图6 班次一车辆行驶路径

图7 班次二车辆行驶路径