基于改进蚁群算法降低电商物流多仓库车辆路径调度成本问题

Reducing the Routing Cost of Multi-Warehouse Vehicles in E-Commerce Logistics Based on Improved Ant Colony Algorithm

摘要: 本文针对带有时间窗约束的多仓库开放型车辆路径问题，提出了一种梯形模糊数方法对时间窗进行模糊化处理。在用户满意度函数和时间惩罚成本函数的基础上，建立了更加贴近实际场景的优化模型。为降低电商物流成本，本文假设系统允许存在一个或多个虚拟配送中心，并设计了一种改进的蚁群优化算法以求解系统的最小成本问题。通过在不同规模的实验数据集上进行测试，结果表明该算法在总成本方面具有显著优势：相较于基本蚁群算法降低了10%，相较于随机生成方法降低了29%。因此，本文所提出的数学模型具有合理性和有效性，特别适用于多中心、多需求点和开放型系统背景下的电商物流成本优化场景。

Abstract: In this paper, a trapezoidal fuzzy number method is proposed to blur the time window for multi-warehouse open vehicle routing problem with time window constraint. On the basis of user satisfaction function and time penalty cost function, an optimization model which is closer to the actual scenario is established. In order to reduce the cost of e-commerce logistics, this paper assumes that the system allows one or more virtual distribution centers, and designs an improved ant colony optimization algorithm to solve the minimum cost problem of the system. When tested on experimental datasets of different sizes, the results show that the algorithm has a significant advantage in terms of total cost: 10% lower than the basic ant colony algorithm and 29% lower than the random generation method. Therefore, the mathematical model proposed in this paper is reasonable and effective, especially applicable to the scenario of e-commerce logistics cost optimization under the background of multi-center, multi-demand point and open system.

1. 引言

在现代电商物流与供应链管理中，车辆路径问题(Vehicle Routing Problem, VRP) [1]是一类重要的优化问题，旨在通过合理规划车辆的运输路径，最大化运输效率、降低运输成本，且满足客户需求。随着电商物流网络的扩展与客户需求的个性化日益显著，传统的车辆路径问题已经难以满足现实的复杂应用需求[2]。为此，学术界对VRP的研究逐渐从经典的单仓库、确定性时间窗等简单情境，拓展到包含多仓库[3]、模糊时间窗以及开放型路线的复杂情况，以更好地模拟实际的物流需求与约束条件[4]。

随着全球经济一体化的不断推进，电商物流行业的迅猛发展使得高效的配送系统成为企业竞争力的关键因素[5]。在实际场景中，由于客户需求的波动以及环境的不确定性，客户往往难以提供精确的到达时间限制，从而形成了模糊时间窗需求[6]。而多仓库结构广泛存在于供应链管理中，能够有效分散库存压力、缩短配送路径，提高响应速度[7]。然而，由于多仓库调度涉及多个配送中心之间的协同，进一步增加了路径优化的难度。此外，开放型车辆路径问题(Open Vehicle Routing Problem, OVRP) [8]中，车辆不再需要返回出发仓库，而是可以在服务完最后一个客户后就地结束任务[9]。这一设置不仅降低了总路径长度，也更符合当今分布式物流网络的应用场景。

为解决上述复杂的VRP问题，蚁群算法(Ant Colony Optimization, ACO) [10]作为一种基于仿生智能的全局优化算法，凭借其自组织性和分布式并行计算特性，已被广泛应用于VRP的求解。传统的蚁群算法模拟蚂蚁在觅食过程中通过信息素来传递信息、构建路径的过程，具有强大的路径搜索与优化能力[11]。然而，经典蚁群算法在面临复杂路径问题时易出现收敛速度慢、陷入局部最优等问题，难以有效求解具有模糊时间窗、多仓库和开放型路径的复杂VRP [12]。

近年来，改进型蚁群算法已逐渐成为解决复杂优化问题的一种有效方法。通过引入动态信息素调整机制、精英蚂蚁策略、路径交叉与变异操作等改进措施，可以显著提高算法的全局搜索能力和收敛速度，使其更适用于求解高复杂度的VRP。

本文基于改进的蚁群优化算法，结合梯形模糊数方法对时间窗进行模糊化处理，构建了一个更加贴近实际场景的优化模型。通过引入虚拟配送中心的假设与设计高效的算法流程，本文旨在以最小化物流总成本为目标，为电商物流多仓库车辆路径调度问题提供一种高效可行的解决方案。同时，实验验证了所提出方法在不同规模测试集中均具有显著的优化效果。这项研究不仅具有理论意义，也为实际应用场景提供了可行的技术参考。

2. 问题描述和数学模型

2.1. MDOVRP描述

MDOVRP通过引入开放系统概念放宽了对车辆行驶路径的限制。具体的图形表述如下图1。车辆可以多次往返于配送中心和客户之间，只要它们的载货空间允许。在完成一次配送任务后，车辆无需返回起始的配送中心，而是可以选择前往最近的配送中心进行再次装载。这样的安排允许车辆灵活地根据剩余容量继续服务客户，而不是每次配送后都必须回到起点，也就是说起点和终点配送中心可能不一致。它代表了一种更具适应性和现实的建模方法，适用于各种现实世界的物流情况。假设一家快递公司在一个城市中有三个配送中心(A、B、C)和多个客户。每个配送中心可以根据实际情况调配车辆，而客户的订单会在一天内不断变化。在这种情况下，快递公司需要高效地安排车辆的配送路线，以便在满足客户需求的同时，尽量减少运输成本和时间。MDOVRP (多仓库开放型车辆路径问题)为电商物流提供了一种更

Figure 1. Simple diagram of MDOVRP

图1. MDOVRP简单示意图

加灵活高效的配送方案，能够适应现代复杂的供应链需求。通过优化多个配送中心和车辆的服务路径，该方法显著提高了整体配送效率，并在动态和不确定的市场环境中表现出强大的适应性。在电商物流中，MDOVRP的应用尤为重要，它不仅能帮助企业更好地应对多点分布、时效性强的订单需求，还能有效降低物流成本，提升用户满意度，从而增强企业在激烈市场竞争中的核心竞争力。

2.2. 符号说明

本节为该文章中算法所用到的符号和公式表述，具体见下表1。

Table 1. Description of the symbols used in the algorithm

表1. 算法中使用的符号说明

符号	说明
$V$	表示所有顶点的集合
$C$	表示需求点的集合
$D$	表示配送中心的集合
$E$	表示边缘集合
$v$	表示车辆的行驶速度
$K$	为交付车辆的集合
$d$	表示边距离
$M$	为车辆时间惩罚成本
$Q$	为车辆重量容量限制
$TW$	为车辆总行驶时间限制
$S_1$	单位距离运输成本
$S_2$	单位车辆调度成本
$S_3$	车辆早到成本
$S_4$	车辆迟到成本
${\alpha }_i$	顾客满意度水平
$x_i$	节点横坐标
$y_i$	节点纵坐标
$S_k$	为车辆出发时间，其中，$k\in K$
$t_{ik}$	表示车辆k在需求点i的使用时间
$q_i$	表示需求量
$Z_m$	表示实际使用的车辆数量
$X_{ijk}$	二元变量；如果车辆k直接从i到j则为1，否则为0

2.3. 模糊时间窗

在本文中，时间窗采用梯形模糊数表示，记为$\left[EET,ET,LT,ELT\right]$ 。这个表示法扩展了原始时间窗约束，使其更具灵活性和适应性。具体描述如下，$EET$ ：时间窗的上限扩展值(Earliest Expected Time)，表示允许的最大到达时间。$ET$ ：时间窗的期望到达时间(Expected Time)，表示最理想的到达时间。$LT$ ：时间窗的最迟到达时间(Latest Time)，表示允许的最迟到达时间。$ELT$ ：时间窗的下限扩展值(Earliest Latest Time)，表示允许的最小到达时间。如果车辆的到达时间超出最大公差限制，则视为硬时间窗约束，使得该解决方案不可行。这种约束确保了在特定情况下必须严格遵守的时间限制。这种梯形模糊数表示法为时间窗的处理引入了灵活性，使得在面对实际配送中的不确定性时，可以更好地反映客户的需求和服务质量，同时通过满意度和惩罚成本的机制来优化车辆调度与路径选择。从而达到降低电商物流有关车辆调度方面的运行成本。

2.4. 数学模型

基于上文描述，本文相应的数学模型如下：

$MiniZ=S_1\cdot {\displaystyle {\sum }_{i\in V}{\displaystyle {\sum }_{j\in V}{\displaystyle {\sum }_{k\in K}{X}_{ijk}{d}_{ij}}}}+S_2\cdot Z_m+S_3\cdot {\displaystyle {\sum }_{i\in V}{\displaystyle {\sum }_{j\in C}{\displaystyle {\sum }_{k\in K}{X}_{ijk}Max\left\{\left(E{T}_i-T_{ik}\right),0\right\}}}}$ (1)

Subject⋅to

${\displaystyle \sum _{i\in V}{\displaystyle \sum _{k\in K}{X}_{ijk}=1,j\in C}}$ (2)

${\displaystyle \sum _{i\in V}{\displaystyle \sum _{k\in K}{X}_{jik}=1,j\in C}}$ (3)

${\displaystyle \sum _{i\in D}{\displaystyle \sum _{j\in C}{X}_{ijk}\le 1,k\in K}}$ (4)

${\displaystyle \sum _{i\in D}{\displaystyle \sum _{j\in C}{X}_{jik}\le 1,k\in K}}$ (5)

${\displaystyle \sum _{i\in D}{\displaystyle \sum _{j\in C}{X}_{ijk}={\displaystyle \sum _{i\in D}{\displaystyle \sum _{j\in C}{X}_{jik},k\in K}}}}$ (6)

${\displaystyle \sum _{k\in K}{\displaystyle \sum _{i\in V}{X}_{ijk}={\displaystyle \sum _{k\in K}{\displaystyle \sum _{i\in V}{X}_{jik},j\in C}}}}$ (7)

${\displaystyle \sum _{i\in V}{\displaystyle \sum _{j\in C}{X}_{ijk}{q}_i\le Q,k\in K}}$ (8)

$\beta \left(T_{ik}\right)\ge {\alpha }_i$ (9)

${\displaystyle \sum _{i\in V}{\displaystyle \sum _{j\in V}{X}_{ijk}\left(t_{ik}+\frac{d_{ij}}{V}\right)+S_k\le TW,k\in K}}$ (10)

$Z_m={\displaystyle \sum _{i\in D}{\displaystyle \sum _{j\in C}{\displaystyle \sum _{k\in K}{X}_{ijk}}}}$ (11)

$X_{ijk}\in \left\{0,1\right\},\forall i,j\in V,\forall k\in K$ (12)

在上述模型中，式(1)为最小化总成本的目标函数。其又具体包括三个方面的成本，如车辆配送过程中的运输成本、根据顾客需求而产生的车辆之间的调度成本和梯形模糊时间窗约束下的时间惩罚成本。式(2)以及式(3)则确保了每个需求点仅由从特定的配送中心派出的一辆车进行服务。式(4)、(5)、(6)则保证车辆集中的车可以不被强制选择，也可以从某个实际配送中心出发，完成待定服务任务之后再返回最近的配送中心。式(7)为确保输入–输出保持平衡的约束条件。式(8)为每辆车的自重负重极限。式(9)保证了每个顾客满意度水平均在某一水平之上。式(10)为服务车辆的总行驶时间限制条件。式(11)表示实际使用的车辆数量计算方法。式(12)则是表达了决策变量$X_{ijk}$ 的性质。

3. 改进蚁群算法

本文提出了一种改进的蚁群算法，用于解决多配送中心的车辆路径问题(MDOVRP)。该算法在搜索效率和时间复杂度方面表现优异。研究方法基于整体思路，在模型设定中，车辆起始于一个概念上的配送中心(虚拟配送中心)，然后前往实体的配送中心(实际配送中心)，接着从那里出发去满足客户的需求(客户需求点)。完成配送任务后，车辆会返回到实际配送中心，最后再回到虚拟配送中心。为了简化模型，我们假设虚拟配送中心和实际配送中心之间的移动不产生任何成本、距离和时间消耗。这种建模方式具有实际意义。例如，如果某车辆在完成任务后返回实际配送中心2，即使它理论上需返回到虚拟配送中心1，实际上它将从当前位置(即实际配送中心2)开始下一任务。这种处理方式大大简化了路径规划过程，同时保证了效率。

改进的蚁群算法设计具体步骤如下图2：

Figure 2. Improved ant colony algorithm flow chart

图2. 改进蚁群算法流程图

4. 实验设计

数据来自MDOVRP的公共数据集，包括2个虚拟配送中心和3个实际配送中心以及48 (18, 78)个客户需求点。每个需求点的服务时间在区间(0, 1)内随机生成。最大公差上下限均为120分钟，即各需求点的时间窗口范围在标准时间的基础上延伸了120分钟。需求点时间窗口的满意度设定为${\alpha }_i=0.1$ 。所有车辆总行驶时间为12小时，车辆从早上7点开始工作，要求在晚上7点之前必须返回配送中心。运输速度$v=60$ km/h。单位距离运输成本$S_1=10$ 。单位车辆调度成本$S_2=20$ 。时间窗惩罚成本$S_3=10$ 。具体实验数据如下表2。

Table 2. Distribution center specific data

表2. 配送中心具体数据

序号	配送中心节点	坐标位置
		X	Y
1	虚拟配送中心1 (起点)	0	0
2	实际配送中心2 (实际起点)	6.234	11.992
3	实际配送中心3	18.886	16.363
4	实际配送中心4	−33.326	50.069
5	虚拟配送中心5	−30	0.3

表3~表5分别给出了本文改进的蚁群算法与基本的蚁群算法和随机生成算法的小、中、大测试集的各五次实验数据对比。改进之后的蚁群算法均表现出更优的解结果，小测试集最优成本为362.7739，路径总距离为335.0127；中测试集最优成本为748.0483，路径总距离为477.9749；大测试集最优成本为1213.6，路径总距离为634.8670。运行时间也在设置范围之内，且最佳与最差解决问题的错误率均在4%以下，表明改进之后的蚁群算法在求解具有代表性的模糊时间窗的MDOVRP时始终收敛到相当好的解结果。

Table 3. Comparison of experimental results of the small test set use case repeated solving for 5 times (18 customer requests)

表3. 小测试集用例重复求解5次的实验结果对比(18个顾客需求)

	随机生成算法	基本蚁群算法	改进蚁群算法
总成本(小)	401.1423	413.3159	374.8801
	444.2021	391.1634	400.0743
	415.7476	398.9466	363.5716
	448.4708	423.5392	378.5982
	417.8561	416.6050	362.7739
路径总距离(小)	412.7250	342.7933	284.5820
	349.2602	289.3463	327.5285
	446.9802	349.7012	275.2629
	417.9396	385.2011	379.0343
	269.6394	441.8589	335.0127

Table 4. Comparison of experimental results of repeated solution of medium test set use cases for 5 times (48 customer requests)

表4. 中测试集用例重复求解5次的实验结果对比(48个顾客需求)

	随机生成算法	基本蚁群算法	改进蚁群算法
总成本(中)	1283.1	846.1314	795.3737
	1227.8	885.5766	797.0633
	1266.2	916.6246	824.3350
	1307.9	888.6971	748.0483
	1197.7	959.7224	799.4753
路径总距离(中)	1301.4	579.2356	493.2465
	1145.2	511.6891	536.2735
	1176.2	543.5473	577.1289
	1250.6	637.1886	477.9749
	1361	524.3733	548.9996

Table 5. Comparison of experimental results of repeated solution of large test set use cases for 5 times (78 customer requests)

表5. 大测试集用例重复求解5次的实验结果对比(78个顾客需求)

	随机生成算法	基本蚁群算法	改进蚁群算法
总成本(大)	2174.3	1352.1	1240.8
	2161.4	1360.5	1293.4
	2124.6	1376.2	1213.6
	2100.9	1344	1260.5
	2110.8	1364.7	1243.5
路径总距离(大)	2172.2	746.3343	699.3018
	2161.8	765.6081	725.1567
	2206.8	700.1401	634.8670
	2107.3	717.5727	650.6449
	2364.8	780.3733	628.4431

图3~图5分别显示了小、中、大三种测试集下改进蚁群算法与普通蚁群算法的最优总成本迭代对比图。可以看出小中测试集在第120次迭代内收敛到最优值，大测试集则在410次迭代内收敛到最优值，表明该改进算法收敛速度较快，能够快速发现并搜索到满意的解结果。

表6给出了更加具体的各种算法的对比数据，包括最佳总成本和最佳总路径距离的平均值、最小值以及最大值。改进蚁群算法比随机生成法的最优总成本平均提升了29%，比基本蚁群算法平均提升了9.29%。同时最优路径总距离分别提升45.38%和9.08%。这些结果说明，本文所改进的蚁群算法在搜索性能和整体有效性以及合理性方面都优于普通的蚁群算法和随机生成法。

Figure 3. Cost iteration diagram of optimal solution (small test set, 18 requirements)

图3. 最优解成本迭代图(小测试集，18个需求)

Figure 4. Cost iteration diagram of optimal solution (medium test set, 48 requirements)

图4. 最优解成本迭代图(中测试集，48个需求)

Figure 5. Cost iteration diagram of optimal solution (large test set, 78 requirements)

图5. 最优解成本迭代图(大测试集，78个需求)

Table 6. Comparison of experimental data of the three algorithms including average, minimum and maximum data (small, medium, and large test sets)

表6. 三种算法包括平均值、最小值、最大值的实验数据对比(小、中、大测试集)

		最佳总成本			最佳路径总距离
		小	中	大	小	中	大
随机生成算法	平均值	425.48	1256.54	2134.40	379.31	1246.88	2202.58
	最小值	401.14	1197.70	2100.90	269.64	1145.20	2107.30
	最大值	448.47	1307.90	2174.30	446.98	1361.00	2364.80
基本蚁群算法	平均值	408.71	899.35	1359.50	361.78	559.21	741.61
	最小值	391.16	846.13	1344.00	289.35	511.69	700.14
	最大值	423.54	959.72	1376.20	441.86	637.19	780.37
改进蚁群算法	平均值	375.98 (11.63%) (8.01%)	792.86 (36.90%) (11.84%)	1250.36 (41.41%) (8.03%)	320.28 (15.56%) (11.47%)	526.72 (58.3%) (5.8%)	667.68 (62.3%) (9.96%)
	最小值	362.77	748.05	1213.60	275.26	477.97	628.44
	最大值	400.07	824.33	1293.40	379.03	577.13	725.16

图6、图7显示通过10次实验得到最优解结果下的最优车辆调度方案图。本文提出的算法在寻求最优解的过程中，展现了与配送中心服务模式和客户需求点的空间分布相适应的特性，确保了对所有客户的需求点都能进行有效的服务覆盖，并满足了时间上的同步需求。关键的配送优化特点包括：1. 邻近服务：靠近配送中心的需求点会根据各自的需求量获得服务，以实现服务的接近性。2. 成本效益中心服务算法：该算法能够高效地确定两个配送中心交叉服务区域的需求点，以确保配送车辆的运行成本效益最大化。

Figure 6. Middle test set optimal vehicle scheduling scheme diagram

图6. 中测试集最优车辆调度方案图

Figure 7. Large test set optimal vehicle scheduling scheme diagram

图7. 大测试集最优车辆调度方案图

5. 结论

本文针对电商物流场景下带有模糊时间窗的多车场开放车辆路径问题，提出了一种结合梯形模糊数的时间窗处理方法，构建了包含顾客满意度函数和时间惩罚成本函数的优化模型，并设计了基于虚拟配送中心的改进蚁群优化算法。研究结果表明，该方法在优化电商物流配送网络方面表现出显著优势，如成本优化显著：在实验测试中，无论是小规模、中规模还是大规模数据集，改进蚁群算法均显著降低了总配送成本，与未改进蚁群算法相比平均下降近10%，与随机生成方法相比成本减少约30%。同时，最优总路径距离也节约了9%，进一步提升了配送效率。适应不确定性需求：通过模糊时间窗方法处理时间约束，模型能够在动态和不确定的市场环境下有效平衡顾客满意度与物流成本，展现出强大的适应性和实用性。对电商场景的适配性：本文提出的优化模型和算法特别适用于电商物流中的多仓库、多订单点配送系统，能够有效应对复杂供应链需求，实现高效的资源配置和路径规划。理论与实践贡献：研究为电商物流车辆路径问题(VRP)的优化提供了理论支持，同时也为物流企业在动态环境中降低成本、提升服务质量提供了实践参考。本文提出的模型与算法为解决具有时间窗约束的多车场开放型车辆路径问题提供了一种高效的解决方案，对于优化电商物流配送效率、降低物流成本具有重要意义，并为未来更复杂的VRP研究奠定了基础。