不确定需求下快递配送网络鲁棒优化

2020-02-19许闯来胡坚堃黄有方

计算机工程与应用 2020年3期

许闯来，胡坚堃，黄有方

上海海事大学物流科学与工程研究院，上海201306

1 引言

随着我国经济的稳步发展，互联网消费环境的日益成熟和企业信息化的完善，进一步推进了互联网消费方式的普及。来自国家邮政局公布的数据[1]显示：2017年“双11”当天，主要电商企业全天共产生快递物流订单8.5亿件，同比增长29.4%；全天各邮政、快递企业共处理3.31亿件，同比增长31.5%。电子商务在不同消费群体中的普及为快递行业带来了巨大的发展商机，同时也要求城市配送活动在服务能力上更高效，低成本、准时性地满足多样化的物流需求。目前我国快递企业发展水平参差不齐，都面临着专业化程度低，资源配置不均等问题[2]。近几年“双十一购物节”所引发的快递“爆仓”事件，使得物流配送系统承载着巨大的压力[3]。快递需求的集中爆发直接表现为快件量的倍数增长，大量快件堆积在分拨中心[4]。为解决这个问题，快递公司为分拨中心招聘了大量外包人员以及部分职能岗位的员工。该方法虽然可以帮助提升分拨中心的装卸效率，但是并不能有效解决货物积压的问题，相反会加剧分拨中心的运作压力。因此合理并有效地规划配送车辆路径是避免“快递变慢递”的根本之法，也是公司控制人力投入成本，确保客户按时收货，提升客户满意度和品牌竞争力的重要保障。

车辆路径问题来源于交通运输，最早是由Dantzig和Ramser[5]于1959年提出。它是指一定数量的客户，各自有不同的货物需求，在一定的约束下，配送中心安排车队并设计一套运输路线，满足货物在客户点的运输[6]。车辆路径优化是一个NP难问题，可选车辆路径随着客户数量的增加而呈现阶乘般的增长。对于一个有15个顶点的VRP问题，其可行解的数目将达到1 012个[7]。现有的快递分拨物流网络设计主要针对确定性需求基础上对分拨网路的构建，容易受到客户点运输需求剧烈变动的影响[8-9]。Baldacci等[10]回顾了有容量约束进行VRP精确算法的发展，并对它们的计算性能进行比较。张涛等[11]将热轧生产批量计划归结为不确定车辆数的车辆路径问题，并用遗传算法和禁忌搜索算法相结合的混合算法对问题进行求解。

在不确定车辆路径问题上，研究人员大多采用随机规划或者模糊规划的方法。戎丽霞[12]针对具有不确定需求的车辆路径问题，建立了基于模糊可信性理论的模糊机会约束规划模型，利用基于模糊模拟的混合遗传算法进行求解。邢占文[13]以启发式算法为基础，提出了勘探搜索算法和基于非精确距离矩阵的共轭优化算法求解呼和浩特市内带有顾客需求不确定性和车速度不确定的车辆路径问题。Chung[14]等运用鲁棒优化方法解决结合交通动态性和需求不确定性的网络设计问题。Yu[15]应用鲁棒优化模型处理随机物流问题，并设计了求解方法。该文建立鲁棒线性规划模型，并通过对比该解与对应确定性模型的解来描述模型的鲁棒性。孙华[16]用鲁棒优化的方法求解了应急管理下需求和旅行时间不确定的车辆路径问题。伍方凌[17]首先建立了确定性带时间窗的班轮支线网络优化模型，并在此基础上提出集装箱班轮支线网络鲁棒优化模型对不确定条件下船舶的运输航线进行优化选择。管峰等[18]采用鲁棒优化模型解决需求不确定的、有容量限制的车辆路径问题，证明虽然鲁棒优化模型的最优目标函数值较大，但能有效保证路径在需求波动下的可行性。2017年，熊瑞琦等[19]针对危险货物配送路径对不确定因素敏感度较高的问题，提出了鲁棒性可调的多配送中心危险货物配送路径鲁棒优化方法。本文通过引入基于情景集的鲁棒优化模型，先对物流分拨网络结构进行经济性分析，并与运输时效优先下的成本进行比较，分析两种选择下的成本和总旅行时间差异；将车辆数，旅行时间和成本最低作为模型的3个因变量，通过改进蚁群算法，并用Matlab求解模型，给出决策方案，减缓由于需求波动而带来的不利影响，为快递企业选择合适的分拨路径提供解决方案。

2 快递配送物流网络鲁棒优化模型的建立

2.1 问题描述

本文不考虑分拨中心的装货时间。快递企业的VRP模型通常考虑一个配送中心同时服务多个需求客户点的情况：每个客户点的位置已知，配送中心有足够可使用的配送车辆，且每辆车的装载容量一定；每个客户只能被服务一次；每条线路上的客户需求不能超过车辆的最大装载容量；客户需求量超出车辆额定容量的限制，得不到运输的部分给予惩罚。完成配送任务的车辆最终返回配送中心。本文模型求解的目标函数是总成本最小，基于确定需求利用鲁棒优化的思想，对物流配送网络进行设计和优化，同时利用不同的情景集来描述需求的不确定性问题。

2.2 模型建立

本文是由一个配送中心向多个客户点进行配送。首先建立确定需求下的以成本最低为目标函数的确定性模型，然后在此基础上建立关于需求量的鲁棒性模型。

设车辆路径网络图为G(V,A)，其中V={v0,v1,…,vn}为顶点集合；集合A={(Vi,Vj):i≠j∧i,j∈V}为弧集合；定义v0为配送中心；v1～n为需求客户点；K为自有同质车辆数目；D为外包同质车辆数目；N={0,1,2,…,n}表示配送中心和客户点集合；QV为车辆的装载容量；gi为各客户点的需求量，且满足gi≤QV；dij为客户点i和j之间的距离；tij为客户点i和j之间的行驶时间；Cf为单位体积燃料成本；Cd为单位装卸成本；C1为自有车辆固定费用；C2为外包车辆固定费用；ρ为配送车辆单位油耗；[ai,bi]为客户点i指定的服务时间窗；Nc为完成一个配送班次所用的自有车辆的数量；Nd为完成一个配送班次所用的外包车辆的数量；Xijk为当车辆K经过客户i到达客户j时为1，否则为0；yk为当车辆K被使用时为1，否则为0。

2.3 需求不确定下的快递配送路径模型

鲁棒优化模型是以确定性需求模型为基础，所以首先建立确定性需求下快递配送物流网络模型。

确定性需求的车辆路径问题模型为：

其中，式（1）为成本最小的目标函数，包括司机工资、燃油费用、装卸成本和车辆固定成本；式（2）表示所有提供服务的车辆都必须从配送中心出发，并最终返回到配送中心；式（3）表示每个客户点有且只有一辆车到达和服务；式（4）表示抵达客户的车同时也是离开客户的车；式（5）约束了车辆的最大载荷；式（6）中，等式左边表示路径中投入使用的车辆总数，是自有车辆数和外包车辆数之和；式（7）表示车辆在两个客户点之间的行驶要保持连续性；式（8）为参数变量的约束值。

为了更好地研究各客户需求量不确定的情况，现将鲁棒优化的思想运用到快递配送网络的设计问题中。假设存在S个需求情景，每个需求情景中含有不确定需求d，每种情景发生的概率对应为ps，对应情景S下客户j的需求量为

基于情景集s下的鲁棒优化模型的目标函数为：

其中，式（9）是基于情景集的鲁棒优化的目标函数原型，第一部分考虑了偏离均值的情况，第二部分通过加入λ倍偏差以体现决策者的风险偏好，第三部分为惩罚函数；约束式（10）～（12）保证了得出的鲁棒最优解能满足所有情景。

现将确定性需求下的快递配送路径模型加入到基于情景集S下的鲁棒优化模型，最终目标函数模型为：

修改和新添加的约束条件：

其中，式（13）表示任意情景S下鲁棒优化的目标函数，即将公式（9）中的ξs替换成公式（1）中的，其余部分保持不变；式（14）松弛了确定性模型中车辆最大载荷量的约束，允许运输需求大于车辆最大载荷量，且两者之间存在偏差zs，即如果客户点i→j实际需求量小于或等于车辆的最大载荷量，则zs=0，否则zs=，表示存在运输量为zs的需求得不到满足，这部分通过式（13）的最后一部分进行惩罚；约束式（15）与基于情景集的鲁棒优化模型中约束式（11）相对应，表示解的鲁棒性，即对任意情景中的参数值，模型的解都“接近”最优；式（16）为对新添加参数变量的约束。

3 算法设计

本文通过构建不确定需求的鲁棒模型，并与确定需求下的模型结果进行比较。蚁群算法适用于求解规模较大的组合优化问题。同时为了避免陷入局部最优，采用2-opt进行局部搜索优化，易于寻找到全局最优解。

采用文献[20]基础建立的蚁群算法，算法步骤如下。

步骤1系统初始化：初始化距离dij，设置迭代次数iter_max=200，Q=20为环境初始残留信息素。

步骤2初始化m只蚂蚁，将n个客户点放入蚂蚁的未访问城市表notVisitk，客户点需求量qk。

步骤3蚂蚁k随机选一个客户点放入蚂蚁路径solutionk，同时从notVisitk将该客户点删除。

步骤4根据公式

计算蚂蚁从客户点i转移到客户点j的转移概率。

步骤5如果notVisitk不为空，则用轮盘赌法随机选择一个客户点放入solutionk，同时从notVisitk将该客户点删除，比较客户点j的需求量和车辆剩余容量的大小，若客户点j的需求量大于车辆剩余容量，则车辆返回配送中心开始新一轮路线寻找，否则重新选择客户点。

步骤6对蚂蚁k构造解路径用2-opt进行局部搜索优化，避免陷入局部最优。

步骤7根据公式τij( t+1)=(1 -ρ)τij(t)+Δτij更新信息素浓度，其中ρe∈( 0 ,1)。

步骤8若迭代次数小于iter_max，则转步骤2；否则程序结束，输出结果。

4 算例分析

假设坐标点1是某快递公司在苏州设立的一个大型分拨中心（本文只考虑配送作业），设其坐标为[12，6]。该快递公司在苏州市区内共有55个网点；配送车辆每天进行5个班次的运输，配送开始时间分别为06：20、08：50、13：10、15：45和18：20，每个配送班次的作业时间为2.5 h；客户坐标在边长为40的矩形中随机产生，需求为随机从[100，300]取整，设为a0，如表1所示；同时表1中的需求数据也将用于计算双十一期间情景S的服务时间，公式10+0.2×ps×(gsj-a0)，此部分数据不再单独列出；非双十一期间各客户点服务时间为10 min；公司现阶段拥有20辆1.5 T自有车辆，装载容量为700件。

燃油成本（元）=单位体积的燃料成本×满载耗油量×客户点之间的距离。总旅行时间（min）=运输时间+服务时间。

设93#汽油价格为7.65元/L[21]；满载耗油量为0.06 L/km；自有车辆固定成本为500元/辆；外包车辆固定成本为1 000元/辆；车辆行驶速度为50 km/h；司机工资为40元/h与1.6元/km；单位装卸成本为2元/件；若存在两条或两条以上运输路径总旅行时间小于时间窗2.5 h，则使用同一辆车进行分次运输，并优先使用自有车辆。

本文假设该分拨中心在双十一期间预测了三种可能存在的需求情景，发生的概率分别是0.3、0.3和0.4，蚂蚁数量为80，信息素残留系数为0.5，信息启发因子为0.1，期望启发式因子为0.5。各情景下客户点的需求量如表2所示。另设定鲁棒模型参数λ为1，ϖ为100，算法迭代200次。

运用Matlab软件分别对确定性模型和鲁棒性模型求解。原确定需求成本为71 372元，总旅行时间为1 944 min，路径图见图1。由于路径1-19-16-1和1-30-28-25-1总旅行时间小于150 min，因此可以使用同一辆车进行分次运输。同理，路径1-9-6-27-1和1-23-22-1、1-31-35-1和1-36-37-33-1、1-49-55-1和1-5-3-1、1-21-17-1和1-50-54-1、1-24-20-42-1和1-13-7-1、1-39-40-1和1-2-4-1、1-46-44-1和1-32-26-1也分别使用一辆自有车辆进行运输，其余路径分别配置一辆自有车辆，共需要自有车辆15辆。其结果如表3所示。

鲁棒优化模型的成本为92 433元，总旅行时间为2 935 min，路径图见图2。其中路径1-16-1和1-27-7-1、1-55-47-1和1-19-23-1、1-31-1和1-43-40-1、1-50-1和1-22-20-1、1-17-29-1和1-18-1、1-39-32-1和1-13-21-1、1-35-34-1和1-26-38-1、1-46-1和1-3-5-1、1-44-1和1-24-6-1分别使用一辆自有车辆进行运输，其余路径分别配置一辆自有车辆，因此共需要自有车辆23辆，外包车辆3辆。结果如表4所示。

表1 客户点坐标及需求件

表2 情景集下客户点的运输需求

图1 原确定需求车辆路径

为了进一步比较鲁棒模型的优势，本文将三种情景集的运输需求分别代入确定性模型计算相应的最优值并与鲁棒优化模型进行比较，同时比较两者在一轮运输班次结束之后所花费的总旅行时间的差异，其结果如表5所示。对比发现：在成本方面，成本最优条件下鲁棒模型的解与原需求的解差距最大，而与所有情景下的成本差距保持在10%左右。一方面是由于需求增加导致成本上涨；另一方面，由于鲁棒模型是综合考虑所有情景条件得到的，因此所有情景都可以接受，故差距稳定，证实了鲁棒模型的抗干扰性和高成本的代价；而两种情况各自对应的总成本之间差距较小，环比的最大值仅为1.90%。在旅行时间方面，一轮行车结束的总旅行时间存在较大差异，最多可节约47 min。由此可见，快递企业可以在成本没有大幅度变动的前提下优先考虑运输时效，以减缓分拨中心压力，保证快件及时送达配送站点。

表3 确定性模型最优解 min

图2 鲁棒模型车辆路径

表4 鲁棒优化模型最优解min

为找出公司规模与业务量和总成本之间的相关性，将需求在[200，700]范围内，间隔50取整，算法运行结果见图3。分析发现：随着公司业务量的增加，且当超出公司自有车辆的规模时，运营成本增长较快；运输费用的上升是导致企业利润增长缓慢的原因之一。

为更加直观地对比算法收敛性能，运用Matlab软件，以原确定需求数据为背景，采用传统蚁群算法和基于2-opt的蚁群算法对确定性模型进行求解，设置迭代次数为500次，结果见图4。可以看出：相较于基本蚁群算法，改进后算法的探索性和收敛性强，求解的目标函数值更优。但由于本文算法添加了2-opt，故问题求解时间略有增加。

5 结论及未来工作

本文在确定性模型的基础上，选用基于情景集下的鲁棒优化方法优化分拨中心的配送网络，为了避免蚁群算法在求解过程中陷入局部最优，采用2-opt进行局部搜索优化。并创新性地通过变化的快件数量，对客户服务时间进行重新分配；通过对每条运输路径的时间计算，若存在两条或两条以上路径的旅行时间之和满足时间窗要求，则使用同一辆车进行配送，以实现对自有车辆的最大利用。提出的模型能够在需求大幅浮动的情况下控制成本，同时保证每个运输班次总旅行时间的合理性，提高了企业的运作效率。