考虑交付失败的快递末端配送路径优化研究

doi:10.12677/mos.2025.1410615

期刊菜单

考虑交付失败的快递末端配送路径优化研究
Research on Optimization of Last-Mile Delivery Routes Considering Delivery Failure

DOI: 10.12677/mos.2025.1410615, PDF, HTML, XML,
作者: 米峰南：上海出版印刷高等专科学校，上海
关键词: 末端配送路径优化；局部搜索策略；鸽群算法；End-of-Line Delivery Route； Optimization Local Search Strategy； Pigeon-Inspired Optimization (PIO) Algorithm

摘要: 针对快递服务网络路径优化问题，因其存在高价值或面交的快递包裹，为了降低顾客投诉率并完成配送服务，需要额外规划二次配送路径。对此，考虑交付失败概率，以车辆固定成本、时间窗惩罚成本、一次配送成本以及二次配送成本之和为目标函数，构建多车型、有时间窗的快递末端配送路径优化模型，结合局部搜索策略对鸽群算法进行改进，并采用该算法进行求解，最终选择2辆车型A和2辆车型B，完成配送任务比基础鸽群算法降低成本约13.7%，验证了模型和算法的可行性，为快递服务网络优化提供参考性建议。

Abstract: Aiming at the express delivery service network route optimization problem, which involves high-value or hand-delivery parcels, additional secondary delivery routes need to be planned to reduce customer complaint rates and ensure successful delivery. Considering the probability of delivery failure, an optimization model for last-mile delivery with multiple vehicle types and time windows is constructed, with the objective function comprising fixed vehicle costs, time window penalty costs, primary delivery costs, and secondary delivery costs. By integrating a local search strategy, an improved Pigeon-Inspired Optimization (IPIO) algorithm is proposed and applied to solve the model. The solution ultimately selects 2 Type A vehicles and 2 Type B vehicles, reducing the total cost by approximately 13.7% compared to the basic PIO algorithm. This validates the feasibility of the model and algorithm, providing valuable insights for optimizing express service networks.

文章引用：米峰南. 考虑交付失败的快递末端配送路径优化研究[J]. 建模与仿真, 2025, 14(10): 168-181. https://doi.org/10.12677/mos.2025.1410615

1. 引言

快递服务网络配送路径优化的研究一般基于车辆路径问题建立混合整数规划模型[1]，而快递交付过程由于快递包裹的差异性和特殊性，即使依靠快递柜、临时代收点等寄存方式，仍有部分快递因为高价值、需要面交的情况，存在交付失败的可能性，因此快递的末端配送往往不是一次就交付成功，而是多次交付完成的。

快递末端配送问题可以归结为车辆路径的研究问题，即车辆路径规划问题(Vehicle Routing Problem, VRP) [2]。Vaziri等考虑多个取件任务和送货服务拆分，以旅行时间最小化、总利润最大化为目标，以减少服务于客户的车辆数量并消除空载回程，应用可变邻域搜索方法以提高初始解质量，在可接受的计算时间内提供了合理的解[3]。Benayed等考虑枢纽节点与非枢纽节点间的服务关系，以运输服务网络运营成本最小为目标函数建立陆运包裹运输网络优化模型，提出一种基于模拟退火算法的启发式方法，有效提高求解速度并缩短运行时间[4]。Li等考虑经济效益和环境影响，研究以最大化收入和最小化成本、时间和排放的多车型绿色车辆路径问题、改进的蚁群优化算法来求解，为末端零售商配送路径规划提供建议[5]。Barnhart考虑枢纽节点处理能力、运输路线的运输能力和包裹运输时限三方面约束，以运输总成本最小为目标函数建立快递包裹运输路线优化模型，求解得出快递运输路线和时刻表[6]。姬杨蓓蓓等以降低企业成本和提高满意度为目标，建立两阶段配送路线优化模型，以申通快递网络为例，基于k-means聚类算法、蚁群算法和扫描算法，设计两阶段优化算法验证模型的有效性[7]。邓学平等以成本最小为目标，建立考虑时间窗的多车型城市快递配送路径优化模型，并使用两点互异和两点交叉改进的遗传算法对模型进行求解[8]。张梦颖等针对快递配送过程中客户需求具有不确定性的特征，提出包含随机客户的选择性旅行商问题。在满足行驶距离限制的条件下，为快递公司提供更具有经济效益的路径，并提出包含精细化局部搜索策略的改进遗传算法求解[9]。周林等引入车辆路径近似连续模型，建立集上门和自提于一体的多容量多车型终端选址–路径集成优化模型，基于模拟退火算法加入一种先“多容量选址–分配”再“多车型路径”的两阶段求解规则[10]。许闯来等针对确定需求下的车辆路径不适合解决需求激增的配送问题，构建基于情景集的鲁棒优化模型，重新分配客户服务时间以实现对车辆的最大利用，发现短时间业务量增加并不会引起利润快速增长[11]。江海等考虑错峰交货，以最小化运输成本为目标的混合整数规划模型，提出以点到点集的距离之和作为邻域搜索优先指标，并设计了基于“路径–车型对”的列生成算法求解模型[12]。Wei等基于地铁设计了一个三级最后一英里快递交付系统，提出“自提 + 地铁站”、“自提 + 商场”、“自提 + 社区”、“上门 + 社区”、“上门 + 写字楼”五种不同的快递交付模式[13]。

本文在构建末端配送路径优化模型时，考虑配有多种车辆型号，以便满足不同配送包裹量的需求，为快递服务网络末端配送资源提供合理优化建议。

2. 问题描述

目前末端配送多数选择上门模式，是指快递企业的物流配送人员根据客户指定的收货地点，利用车载工具将快递包裹当面交给客户的一种模式。由于送货上门的便利性，该模式受到客户的普遍欢迎，成为当前国内外主流的末端配送模式。针对“最后一公里”末端配送的配送时间、地点、方式，尚未形成成熟稳定的末端配送路径分析优化系统。从城市物流末端配送情况看，自营企业末端配送路线较为随机，主要与当日路面的情况及快递员经验、偏好等因素有关。货物约定交付的时间一般精准到日，而没有进一步精准到时、分。而在货物送达后，主要由配送人员采用电话沟通的形式对配送的方式、时间、地点进行约定。快递包裹体量较小，快递员会集中配送某个顾客点的多个订单，但部分订单客户存在投递失败问题，因此为了完成配送任务、降低顾客投诉率，快递员会在一次配送完成后进行二次投递。因而在规划快递末端配送路径时，应考虑交付失败概率造成的二次配送，求解两次配送的路径。

3. 模型假设及符号说明

鉴于模型的复杂度，为保证考虑交付失败概率的末端配送路径优化模型的可行性和有效性，做出以下假设：

1) 车辆从配送中心出发，完成一次配送任务后返回配送中心；考虑存在交付失败概率，在一次交付完成后再进行二次交付服务；

2) 每辆车每次配送至少服务一个顾客点；

3) 每条路径上客户配送需求总和小于车辆的载重能力；

4) 不同类型的车辆载重能力、运输成本和固定成本已知；

5) 车辆运输成本与运输距离有关，与车辆当前载重量无关，单位运输成本已知。

表1为考虑交付失败概率的快递末端配送路径优化模型涉及的集合、参数和变量的符号和定义。

Table 1. Symbols and definitions used in the path optimization model

表1. 路径优化模型中使用的符号及定义

符号	定义
集合
$N$	顾客点集合，索引为 $i$
$M$	车辆类型集合， $M = {1, 2, \cdot \cdot \cdot, r}$
$M_{r}$	车型r车辆集合， $M_{r} = {1, 2, \cdot \cdot \cdot, m_{r}}$
参数
$q_{i}$	顾客点 $i$ 总包裹重量
$θ$	顾客点 $i$ 一次交付失败概率
$f_{r}$	车型 $r$ 的车辆启用的固定成本，包括车辆折旧成本和维修成本等

续表

$C_{r}$	车型 $r$ 单位距离行驶成本
$C_{r}^{'}$	车型 $r$ 二次配送单位距离行驶成本， ${C^{'}}_{r} = γ C_{r}$
$Q_{r}$	车型 $r$ 最大装载量
$r$	转运中心处车辆种类数量
$m_{r}$	车型 $r$ 的车辆数
$t_{i}^{k r}$	车型 $r$ 的车辆k到达顾客点 $i$ 处的时刻
$t_{i j}^{k r}$	车型为 $r$ 的车辆k从顾客点 $i$ 到顾客点j所花费的时间
$s_{i}$	顾客点 $i$ 服务时间
$e_{i}$	顾客点 $i$ 能接受最佳配送服务时间的最早时刻
$l_{i}$	顾客点 $i$ 能接受最佳配送服务时间的最晚时刻
$e_{i i}$	顾客点 $i$ 能接受配送服务的最早时刻
$l_{i i}$	顾客点 $i$ 能接受配送服务的最晚时刻
$e p u$	车辆k早到达顾客点的惩罚系数
$l p u$	车辆k晚到达顾客点的惩罚系数
变量
$X_{i j}^{k r}$	0~1变量，如果从目的地 $i$ 到j由车型为r中的第k辆车到达并服务时，则取值为1，否则取值为0
$Y_{i j}^{k r}$	0~1变量，二次配送过程，如果从目的地 $i$ 到j由车型为r中的第k辆车到达并服务时，则取值为1，否则取值为0
$x_{i}^{k r}$	0~1变量，车型为r车辆中的第k辆车服务目的地 $i$ 时取值为 1；否则取值为0
$y_{i}^{k r}$	0~1变量，二次配送过程，如果顾客点 $i$ 由车辆k服务，则取值为1，否则取值为0

4. 目标函数及约束条件

第一阶段：即车辆自配送中心驶出，依次到达顾客点后并开始配送快递包裹的任务，到回到配送中心的过程产生的成本。主要包括车辆启用成本、时间惩罚成本和一次行驶成本。

1) 车辆启用成本：即派出车辆消耗的固定成本，包括车辆每日在行驶中产生的折旧费用、维修费用和保险费等，其表达式为：

$F 3 = \sum_{i \in N} \sum_{j \in N} \sum_{k \in m} \sum_{r \in R} f_{r} X_{i j}^{k r}$ (1)

2) 时间惩罚成本：指快递员在顾客最期望的时间窗到达，不会产生额外的时间惩罚成本，而快递员在顾客可以接受的时间窗到达，会产生一定的早到惩罚成本或晚到惩罚成本，从而约束快递员尽量在顾客最期望的时间段到达，时间惩罚成本为分段函数，其表达式为：

$F_{4} = {\begin{matrix} e p u \sum_{i \in N} \sum_{k \in m} \sum_{r \in R} (t_{i k r} - e_{i i}), e_{i i} \leq t_{i k r} \leq e_{i} \\ 0, e_{i} \leq t_{i k r} \leq l_{i} \\ l p u \sum_{i \in N} \sum_{k \in m} \sum_{r \in R} (l_{i i} - t_{i k r}), l_{i} \leq t_{i k r} \leq l_{i i} \end{matrix}$ (2)

3) 一次行驶成本：指配送车辆在运输路线上行驶时产生的变动成本，车辆行驶成本会随着车辆的行驶距离增长而提高，其成本和车辆的运输距离成正比，其表达式为：

$F_{5} = \sum_{i \in N} \sum_{j \in N} \sum_{k \in m} \sum_{r \in R} c_{r} d_{i j} X_{ij}^{k r}$ (3)

约束条件：

$\sum_{i = 0} q_{i} x_{i}^{k r} \leq Q_{r}, \forall k \in M, \forall r \in M_{r}$ (4)

约束式(4)表示车型为 $r$ 的车辆 $k$ 配送承担的快递包裹量不超过车辆 $k$ 的最大载重。

$\sum_{k = 1} \sum_{r = 1} x_{i}^{k r} = 1, \forall i \in N$ (5)

约束式(5)表示在车辆行驶路线中，每个顾客点有且只能由某一车辆为其提供配送服务。

$\sum_{i = 0} X_{i j}^{k r} = x_{j}^{k r}, \forall j \in N, \forall r \in M_{r}, \forall k \in M$ (6)

$\sum_{j = 0} X_{i j}^{k r} = x_{i}^{k r}, \forall j \in N, \forall r \in M_{r}, \forall k \in M$ (7)

约束式(6)和约束式(7)表示到达和离开某一目的地(顾客点)的车辆有且仅有一辆。

$\sum_{i = 1} \sum_{k = 1} \sum_{j = 1} X_{i 0}^{k r} = \sum_{i = 1} \sum_{k = 1} \sum_{j = 1} X_{0 j}^{k r}$ (8)

约束式(8)表示车辆都是从配送中心驶出，完成一次配送任务后返回该配送中心。

$\sum_{i = 1} X_{i h}^{k r} - \sum_{j = 1} X_{h j}^{k r} = 0, \forall h \in N, \forall k \in M, \forall r \in M_{r}$ (9)

约束式(9)表示配送车辆在配送完成后必须离开该顾客点。

$\sum_{i = 1} \sum_{j = 1} X_{i j}^{k r} \leq | S | - 1, \forall S \in N, 1 < | S | < n, \forall k \in M, \forall r \in M_{r}$ (10)

约束式(10)表示避免车辆配送过程中产生子回路。

$t_{i} + t_{i j} + s_{i} = t_{j}, \forall i \in N, \forall j \in N$ (11)

约束式(11)表示服务时间限制。

$X_{i j}^{k r}, x_{i}^{k r} \leq 1, \forall i \in N, \forall j \in N, \forall r \in M_{r}, \forall k \in M$ (12)

约束式(12)表示决策变量为0~1决策变量。

第二阶段：指的是即使快递员在时间窗内到达顾客点，但是由于顾客点订单数目多，且订单需求存在差异性，存在一定概率的订单需要当面交付而未成功交付的可能性，因此在完成一次配送后，快递员为完成包裹配送，会就未交付的快递包裹进行二次配送，额外的配送路线上车辆行驶的成本称为二次交付成本，二次交付过程中依旧使用一次配送的车辆，因此不重复计算车辆固定成本。

二次行驶成本：指配送车辆在完成一次配送后，对未交付成功的快递进行二次配送，而二次行驶成本会随着车辆的行驶距离增长而提高，其成本和车辆的运输距离成正比，其表达式为：

$F_{6} = \sum_{i \in N} \sum_{j \in N} \sum_{k \in m} \sum_{r \in R} {c^{'}}_{r} d_{i j} Y_{i j}^{k r}$ (13)

约束条件：

$\sum_{i = 0} q_{i} θ y_{i}^{k r} \leq Q_{r}, \forall k \in M, \forall r \in M_{r}$ (14)

约束式(14)表示车型为 $r$ 的车辆 $k$ 配送承担的快递包裹量不超过车辆 $k$ 的最大载重。

$\sum_{k = 1} \sum_{r = 1} y_{i}^{k r} = 1, \forall i \in N, \forall k \in M$ (15)

约束式(15)表示在车辆行驶路线中，每个顾客点有且只能由一辆货车为其提供配送服务。

$\sum_{i = 0} Y_{i j}^{k r} = y_{j}^{k r}, \forall j \in N, \forall r \in M_{r}, \forall k \in M$ (16)

$\sum_{j = 0} Y_{i j}^{k r} = y_{i}^{k r}, \forall j \in N, \forall r \in M_{r}, \forall k \in M$ (17)

约束式(16)和约束式(17)表示到达和离开某一目的地(顾客点)的车辆有且仅有一辆。

$\sum_{i = 1} \sum_{k = 1} \sum_{j = 1} Y_{i 0}^{k r} = \sum_{i = 1} \sum_{k = 1} \sum_{j = 1} Y_{0 j}^{k r}$ (18)

约束式(18)表示车辆都是从配送中心驶出，完成一次配送任务后返回该配送中心。

$\sum_{i = 1} Y_{i h}^{k r} - \sum_{j = 1} Y_{h j}^{k r} = 0, \forall h \in N, \forall k \in M, \forall r \in M_{r}$ (19)

约束式(19)表示配送车辆在配送完成后必须离开该顾客点。

$\sum_{i = 1} \sum_{j = 1} Y_{i j}^{k r} \leq | S | - 1, \forall S \in N, 1 < | S | < n, \forall k \in M, \forall r \in M_{r}$ (20)

约束式(20)表示避免车辆配送过程中产生子回路。

$Y_{i j}^{k r}, y_{i}^{k r} \leq 1, \forall i \in N, \forall j \in N, \forall r \in M_{r}, \forall k \in M$ (21)

约束式(21)表示决策变量为0~1决策变量。

综上，建立考虑交付失败概率的末端配送路径优化模型，以网络运输成本最小化为目标，主要包括四个部分：车辆启用的固定成本、未按约定时间到达顾客点的时间惩罚成本、车辆由转运中心至末端顾客点一次行驶成本和额外的二次行驶成本：

$\min F F = F_{3} + F_{4} + F_{5} + F_{6}$ (22)

约束条件满足约束式(1)~(12)和约束式(13)~(21)。

5. 算法设计

鸽群优化算法(PIO)是一种智能优化算法，该算法是根据家鸽自主归巢行为而提出的，具有搜索速度快、进化能力强、寻优能力强等特点。

1) 编码与解码

针对多车型带时间窗的末端快递配送路径问题，采用自然数编码的方法设计构造染色体。染色体长度为转运中心服务的顾客点数量 + 车辆数量 − 1，用“0”表示配送中心，用“N”表示所有配送需求点，“0”的个数比车辆数多一个，将“0”作为一条染色体的首尾部分，然后将剩下的“0”插入客户点之间。假设某转运中心有3辆车，其服务范围内有10个顾客点，染色体被表示为“1 5 7 9 0 2 4 8 0 3 10 6”，则表示车辆1在自转运中心出发，依次访问顾客点1、5、7、9后返回转运中心；车辆2自转运中心出发，依次访问顾客点2、4、8后返回转运中心；车辆3自转运中心出发，依次访问顾客点3、10、6后返回转运中心。

2) 初始解的生成

随机生成初始种群能够帮助算法在搜索过程中保持多样性、避免偏见、适应性强、简单高效以及具有全局搜索能力。为了保证基于初始种群求得较为均匀分布的解，本文选用随机生成初始种群的方法，从而在一定程度上避免算法过早陷入局部最优解。

3) 适应度函数的确定

种群的优劣程度主要通过适应度函数来评价，通过适应度的大小来判断算法中某个解是否优异是其最基本的意义，适应度函数是一种用来评估每个个体的适应性，从而进行进化的重要工具。为了方便计算，将末端配送路径的成本作为适应度函数：

$f i t_{3} = F_{3} + F_{4} + F_{5} + F_{6}$ (23)

4) 局部搜索策略

由于初始构造阶段的路径方案不能保证局部最优，因此引入局部搜索策略对基础的鸽群算法进行优化，局部搜索过程主要用大邻域搜索算法对解进行破坏和修复。针对种群的每一个个体都进行局部搜索操作，种群中返回最好的一个作为全局解，然后进行全局解的局部搜索操作，迭代更新全局最优解以改进解的质量。

针对种群的每个个体进行局部搜索操作，检查当前路径集合是否有违反时间窗约束的路径，将违反时间窗最严重的顾客点移除，并将其重新插入到其他路径中。如果没有顾客点被移除(可能是因为所有顾客点都满足时间窗约束)，则随机选择顾客点数量最少的一条路线，对某一个顾客点进行移除和重新插入的操作，计算并比较移除和插入前后的成本。如果新的成本更低，则更新局部最优解。

针对全局最优解进行局部搜索操作，检查当前路径集合是否有违反时间窗约束的路径，将违反时间窗最严重的顾客点移除，并将其重新插入到其他路径中。如果没有顾客点被移除(可能是因为所有顾客点都满足时间窗约束)，则选择相关性较高的顾客点进行移除和插入操作。我们将相关性定义为1/(d + x)，其中d为顾客点间距离，x为0~1变量，若顾客点由同一车辆服务则取值为0，否则取值为1。若两个顾客点距离较近且由同一车辆服务，则顾客点间相关性较高，反之相关性较低。将相关性高的顾客点进行移除和插入操作，计算并比较移除和插入前后的成本。如果新的成本更低，则更新全局最优解。

5) 鸽群算法求解考虑交付失败概率的末端配送路径优化模型流程

加入局部搜索策略后的鸽群算法主要步骤总结如下：

步骤1 初始化参数。随机生成方式构建初始种群，种群中的每个个体代表一种车辆路径方案。计算每个个体的适应度值，选择适应度值最优的个体作为全局最优解。

步骤2 速度和位置更新。根据鸽群算法的原理，更新种群中个体的位置或路径方案。计算更新后种群中每个个体的适应度值。比较所有鸽子的适应度值，找到最佳路径，将所有的个体根据它们的适应度排名。

步骤3 局部搜索阶段。遍历种群中的每个个体。针对每个个体，检查当前路径集合中是否有违反时间窗约束的路径。如果有违反时间窗约束的路径，则找到违反时间窗最严重的顾客点，将其从当前路径中移除。尝试将该顾客点重新插入到其他路径中，并计算新路径的总成本。如果没有顾客点被移除，则随机选择顾客点最少的路线进行移除和重新插入操作。计算并比较移除和插入操作前后的成本，如果新的成本更低，则更新局部最优解。在完成局部搜索后，对全局解进行局部搜索操作。针对全局解，检查当前全局最优路径集合中是否有违反时间窗约束的路径。如果有违反时间窗约束的路径，执行与局部搜索相同的移除和重新插入操作。如果没有顾客点被移除，则选择相关性高的顾客点进行移除和重新插入操作。计算比较操作前后的全局最优解成本，如果新的成本更低，则更新全局最优解。

步骤4 迭代终止。检查是否满足达到最大迭代次数，迭代终止，则输出全局最优解作为最终解。否则，返回步骤2。

6. 上海市同城快递末端配送案例分析

6.1. 数据来源及参数设定

考虑疫情封控等不可抗力因素使得国内外物流系统、快递行业深受影响，为验证模型的有效性和通用性，选取上海市2021年某快递业务作为年同城快递业务量作为参考。根据上海市统计局数据(https://tjj.sh.gov.cn)，第七次人口普查上海市常住人口为2487.09万。根据上海市邮政管理局(https://spb.gov.cn)数据，上海市1~12月累计同城快递业务总量为82632.8万件。一年按照365天计算，得出每日人均的同城快递量为0.09件。

选取上海市主要城区466 km²作为研究区域，选取区域内共计366个居住点作为需求点集合[14]。

采用行业标准并使用部分折算设置参数，具体参数见表2：

Table 2. Parameter settings

表2. 参数设置

符号	定义	取值(单位)
$f_{q}$	辐点固定运营成本	1000元/天
$c_{i l}$	顾客点至辐点单位距离运输成本	1.0元/件次/公里
$g_{i}$	辐点处单位分拣成本	0.65元/件次
$F Q_{i}$	辐点处容量限制	8000件次/日
$f_{k}^{H}$	轴点固定运营成本	5000元/天
$c_{k m}$	轴点间单位距离运输成本	0.04元/件次/公里
$c_{i k}$	辐点至轴点间单位距离运输成本	0.1元/件次/公里
$c_{i j}$	辐点间直接连接的单位距离运输成本	0.5元/件次/公里
$f_{k}$	轴点处单位转运成本	0.51元/件次
$H Q_{k}$	轴点处容量限制	25,000件次/日

通过经纬度距离公式计算网络中任意两点间的实际空间距离，随机选取点 $(W_{1}, J_{1})$ 和 $(W_{2}, J_{2})$ ，其实际空间距离的计算公式为：

$d = 2 R \cdot \arcsin \sqrt{\sin^{2} (\frac{W_{1} - W_{2}}{2}) + \cos W_{1} \cdot \cos W_{2} \cdot \sin^{2} (\frac{J_{1} - J_{2}}{2})}$ (24)

其中， $W$ 表示节点纬度， $J$ 表示节点经度， $R$ 为地球半径系数，取 $R = 6378.137$ 。

配送中心和顾客点坐标信息见表3，顾客点时间窗、服务时间等信息见表4，顾客点交付失败概率由rand (0, 1)随机生成。配送中心共配有三种不同车型：车辆A、车辆B和车辆C。最大载重限制分别为0.8 t、1.0 t、1.2 t，车辆固定启用成本为150元/天、200元/天、250元/天，车辆具体信息见表5。设置早到惩罚系数 $e p u$ 为5元/小时，晚到惩罚系数 $l p u$ 为10元/小时，不同车型车辆早到惩罚系数和晚到惩罚系数相同。不同顾客点之间的实际空间距离通过经纬度距离公式(24)计算。

Table 3. Coordinates information of distribution centers and customer points

表3. 配送中心及顾客点的坐标信息

编号	经度	纬度
FD03 (0)	121.3933	31.2818
1	121.4215	31.2843
2	121.4139	31.3207

续表

3	121.4127	31.2692
4	121.4030	31.2693
5	121.4006	31.3052
6	121.3979	31.3186
7	121.3894	31.2807
8	121.3875	31.2629
9	121.3842	31.3056
10	121.3838	31.2746
11	121.3791	31.2815
12	121.3787	31.2631
13	121.3719	31.2813
14	121.3697	31.2680
15	121.3665	31.3045
16	121.3657	31.2926
17	121.3577	31.2847

Table 4. Customer demand quantities and service time windows

表4. 顾客点的需求量及服务时间窗

编号	$q_{i}$ (kg)	$[e_{i}, l_{i}]$	$[e_{i i}, l_{i i}]$	$θ$	$s_{i}$ (min)
1	252	[11:00~12:00]	[10:30~12:30]	0.12	30
2	144	[10:00~11:00]	[9:30~12:30]	0.08	30
3	240	[12:00~13:00]	[11:00~14:30]	0.16	35
4	124	[10:30~11:30]	[10:00~14:00]	0.26	20
5	542	[14:30~15:30]	[14:30~16:30]	0.40	56
6	152	[15:00~16:00]	[12:30~16:30]	0.55	44
7	150	[10:30~11:30]	[9:00~13:00]	0.41	33
8	246	[13:00~15:00]	[12:00~16:00]	0.38	45
9	96	[10:00~12:00]	[9:00~14:00]	0.34	14
10	286	[12:00~15:00]	[11:30~15:30]	0.16	32
11	126	[13:00~16:00]	[12:00~16:30]	0.20	23
12	216	[14:30~16:00]	[13:00~16:30]	0.19	34
13	144	[12:30~14:30]	[12:00~15:00]	0.23	29
14	224	[12:00~14:00]	[11:00~15:00]	0.28	33
15	188	[10:30~14:30]	[10:00~15:30]	0.30	23
16	122	[14:00~15:30]	[13:00~16:30]	0.31	32
17	154	[9:50~12:50]	[9:00~13:30]	0.35	20

Table 5. Vehicle-related data at the distribution center

表5. 配送中心处车辆相关数据

车型	启用成本	单位配送成本	最大载重	车辆数
车型A	150元/天	1.0元/km	0.8 t	3
车型B	200元/天	1.2元/km	1.0 t	3
车型C	250元/天	1.5元/km	1.2 t	3

6.2. 求解结果

利用MATLAB软件对该模型进行建模，考虑交付失败概率的末端配送路径优化问题，PIO算法参数设置：最大迭代次数200，种群数量80，地图和指南针算子阶段种群数量占比0.75。PIO算法运行20次，记录算法运行最优值和平均值。

1) 改进的鸽群算法求解结果

基础的鸽群求解结果如下：共选择4辆配送车辆，即2辆车型A，2辆车型B，最小配送成本为817.7元，其中，车辆固定启用成本700元，时间惩罚成本8.3元，一次配送成本62.2元，二次配送成本47.2元。具体车辆行驶路线详见表6、图2及图3：

Table 6. Improved pigeon-inspired optimization algorithm for solving delivery routes

表6. 改进的鸽群算法求解配送路线

	序号	配送车型	服务路线
一次配送	1	车型A	0- > 7- > 17- > 13- > 15- >16- > 0
	2	车型B	0- > 8- > 14- > 12- > 6- >11 - > 0
	3	车型A	0- > 10- > 9- > 4- > 3- > 0
	4	车型B	0- > 1- > 2- > 5- > 0
二次配送	1	车型A	0- > 2- > 9- > 15- > 17- > 16- > 5- > 6- > 0
二次配送	2	车型A	0- > 7- > 4- > 1- >3- > 10- > 13- > 14- > 8- > 12- > 11- > 0

Figure 1. Shows an improved pigeon-inspired optimization algorithm for solving a single delivery route

图1. 改进的鸽群算法求解一次配送路线

Figure 2. Shows an improved pigeon-inspired optimization algorithm for solving secondary delivery routes

图2. 改进的鸽群算法求解二次配送路线

2) 基础的鸽群算法求解结果

基础的鸽群求解结果如下：选择4辆配送车辆，即1辆车型A，3辆车型B，最小配送成本为900.7元，其中，车辆固定启用成本750元，时间惩罚成本29元，一次配送成本71.2元，二次配送成本50.5元。具体车辆行驶路线见表、图3及图4：

Figure 3. Shows the basic pigeon-inspired optimization algorithm solving a single delivery route

图3. 基础的鸽群算法求解一次配送路线

Figure 4. Shows the basic pigeon-inspired optimization algorithm solving the secondary delivery route

图4. 基础的鸽群算法求解二次配送路线

Table 7. Basic pigeon-inspired optimization algorithm for solving delivery routes

表7. 基础的鸽群算法求解配送路线

	序号	配送车型	服务路线
一次配送	1	车型A	0- > 14- > 8- > 6- > 16- > 0
	2	车型B	0- > 10- > 13- > 17- > 4- > 12- > 0
	3	车型B	0- > 3- > 1- > 11- > 15- > 9- > 0
	4	车型B	0- > 2- > 7- > 5- > 0
二次配送	1	车型A	0- > 14- > 17- > 16- > 7- > 0
	2	车型A	0- > 4- > 5- > 2- > 9- > 1- > 6- > 0
	3	车型A	0- > 12- > 10- > 11- > 15- > 13- > 8- > 3- > 0

Figure 5. Comparison of pigeon-inspired optimization algorithm before and after improvement

图5. 改进前后鸽群算法对比

Figure 6. Comparison of cost before and after improvement of the pigeon-inspired optimization algorithm

图6. 改进前后鸽群算法成本对比

3) 结果对比

运行算法20次取均值，得到改进前后鸽群算法适应度函数收敛图像。发现：改进前后的鸽群算法均在150次左右收敛，但改进后的鸽群算法适应度函数平均值约821.7，如图5所示。其中，改进的PIO求解车辆固定成本710元，时间惩罚成本8.3元，一次配送成本61.2元，二次配送成本52.2元；基础的鸽群算法适应度函数平均值为952.4，车辆固定成本795元，时间惩罚成本38元，一次配送成本73.5元，二次配送成本45.8元；总成本减少约13.7%，其余成本分别减少10.7%、78.2%、16.7%和7.9%，如图6所示。

6.3. 结论

考虑交付失败概率，以车辆固定成本、时间窗惩罚成本、一次配送成本以及二次配送成本之和为目标函数，构建多车型、有时间窗的、考虑交付失败概率的快递末端配送路径优化模型，并加入局部搜索策略设计鸽群算法，开展仿真实验分析。结果发现，提出的改进PIO算法能够降低成本约13.7%，其中，节省车辆固定成本约10.7%、时间窗惩罚成本78.2%、一次配送成本16.7%以及二次配送成本9.7%，验证了模型和算法的有效性和可行性。

参考文献

[1]	姬杨蓓蓓, 储昊, 成枫. 基于两阶段算法的快递企业末端配送网络优化研究[J]. 系统工程, 2019, 37(2): 100-105.
[2]	Chen, R.M., Shen, Y.M. and Hong, W.Z. (2019) Neural-Like Encoding Particle Swarm Optimization for Periodic Vehicle Routing Problems. Expert Systems with Applications, 138, Article 112833. [Google Scholar] [CrossRef]
[3]	Vaziri, S.H., Etebari, F. and Vahdani, B. (2019) Development and Optimization of a Horizontal Carrier Collaboration Vehicle Routing Model with Multi-Commodity Request Allocation. Journal of Cleaner Production, 224, 492-505. [Google Scholar] [CrossRef]
[4]	Jabalameli, M.S., Barzinpour, F., Saboury, A. and Nasab, N.G. (2012) A Simulated Annealing-Based Heuristic for the Single Allocation Maximal Covering Hub Location Problem. International Journal of Metaheuristics, 2, 15-37. [Google Scholar] [CrossRef]
[5]	Li, Y., Soleimani, H. and Zohal, M. (2019) An Improved Ant Colony Optimization Algorithm for the Multi-Depot Green Vehicle Routing Problem with Multiple Objectives. Journal of Cleaner Production, 227, 1161-1172. [Google Scholar] [CrossRef]
[6]	Kim, D., Barnhart, C., Ware, K., et al. (1999) Multimodal Express Package Delivery: A Service Network Design Application. Transportation Science, 33, 341-428. https://pubsonline.informs.org/doi/abs/10.1287/trsc.33.4.391 [Google Scholar] [CrossRef]
[7]	Hu, W., Dong, J., Yang, K., Hwang, B., Ren, R. and Chen, Z. (2023) Reliable Design of Urban Surface-Underground Integrated Logistics System Network with Stochastic Demand and Social-Environmental Concern. Computers & Industrial Engineering, 181, Article 109331. [Google Scholar] [CrossRef]
[8]	邓学平, 孙芹, 田帅辉. 基于不同车型的城市快递配送车辆路径优化研究[J]. 价值工程, 2020, 39(12): 275-280.
[9]	张梦颖, 秦进, 梁樑. 包含随机客户的选择性旅行商问题建模及求解[J]. 运筹与管理, 2018, 27(5): 8-14.
[10]	周林, 林云, 王旭, 等. 网购城市配送多容量终端选址与多车型路径集成优化[J]. 计算机集成制造系统, 2016, 22(4): 1139-1147.
[11]	许闯来, 胡坚堃, 黄有方. 不确定需求下快递配送网络鲁棒优化[J]. 计算机工程与应用, 2020, 56(3): 272-278.
[12]	江海, 陈峰. 面向快递同城运输的车辆路径问题研究[J]. 工业工程, 2019, 22(4): 58-63.
[13]	Wei, L., Chen, Y., Guo, D., Ji, J., Chen, Z. and Zhuo, C. (2024) A Last-Mile Delivery System for Underground Logistics with “Self-Pickup+” and “Home-Entry+” Modes. Tunnelling and Underground Space Technology, 147, Article 105678. [Google Scholar] [CrossRef]
[14]	Zhao, L., Zhou, J., Li, H., Yang, P. and Zhou, L. (2021) Optimizing the Design of an Intra-City Metro Logistics System Based on a Hub-and-Spoke Network Model. Tunnelling and Underground Space Technology, 116, Article 104086. [Google Scholar] [CrossRef]

为你推荐

友情链接