面向仓配一体化的配送路径优化：多时间窗与可变装载效率下的MILP与启发式求解

一、研究背景与问题提出

1.1 仓配一体化兴起的背景

• 电商驱动：随着电子商务的普及，企业纷纷自建仓储。京东、盒马等开设区域性仓库，用自动化设备处理订单，直接向消费者配送。
• 城市物流挑战：城市配送涉及小件/大批量运输，需结合仓储与配送实现高效一体化，避免中间环节。
• 现实约束：城市道路拥堵和运输高峰，要求配送车辆在预定时间窗口内完成装载和服务，且尽量减少占道等待。
• 研究意义：针对“仓配一体化配送路径问题（WDIRP）”，在多仓库、多时间窗、可变装载效率和半开放路线的复杂环境下，现有研究不足。

1.2 WDIRP问题定义

• 网络构成：节点分为仓库和客户。仓库是车队出发和返回的节点，可异地装载与返回，形成半开放路线。
• 车辆与装载：各仓库配有充足的同型车辆和自动装载机。装载机速度因仓库而异，每台只能同时为一辆车服务。
• 客户需求：每个客户有已知、不可分割的需求，只能由一辆车服务一次。
• 时间窗约束：仓库有单一时间窗；客户拥有多个不重叠的双侧时间窗，车辆必须在规定窗口内到达并完成服务。
• 问题目标：在装载与配送阶段同时考虑装载效率与行驶时间，选择服务仓库并规划路径，使总时间最小。

下图展示了七个客户与三座仓库构成的示例，其中车辆需在客户各自的两个时间窗内完成配送，车辆可从任意仓库发车并返回。

1.3 本研究关注的创新点

• 双侧多时间窗建模：引入两组辅助变量，确保车辆到达时间既不早于最早开窗，又不晚于最晚关窗，从而兼顾早到与迟到惩罚。
• 装载效率异质化：将仓库装载效率纳入目标函数与约束，不同仓库的装载速度影响车辆装载时间与出发时刻。
• 半开放路线：允许车辆从任意仓库出发，完成配送后返回任一仓库，增强灵活性。
• 数据驱动的实例生成：利用 POI、GPS 浮动车数据和手机信令等大数据，构建真实城市道路、需求和时间参数。

二、数学建模：MILP公式与约束

2.1 变量与符号

表1列出了主要符号。关键变量包括：

• ：车辆  是否从节点  行驶至节点 ；
• ：客户  是否由仓库  服务；
• ：车辆  装载并配送仓库  的客户 ；
• ：辅助二元变量，用于双侧时间窗约束；
• ：车辆  在仓库  的装载开始时间、离开时间及在客户  的到达时间。

2.2 目标函数

整体目标是最小化车辆总装载时间与行驶时间之和：

第一部分反映仓库装载时间，受到客户需求  和仓库装载机效率  影响；第二部分是车辆在网络上的旅行时间。

2.3 核心约束

• 路径平衡：每辆车进入仓库的次数等于离开次数；每个客户只能被访问一次。
• 仓库分配：每个客户必须分配给一个仓库。
• 装载与车辆选择：约束(7)-(10)确保只有当车辆从仓库出发并访问了客户时， 才取1。
• 时间衔接：约束(11)-(17)保证仓库装载与客户之间、客户与客户之间的到达时间连续性。
• 双侧时间窗：通过辅助变量  和  判定到达时间是否落在客户第  个时间窗内，再由  决定服务在哪个窗口。该方法比直接对二元变量加约束更高效。
• 车辆容量：每辆车所运载的总需求不得超过车辆容量 。

2.4 其他建模说明

• 半开放路径：模型允许车辆从一座仓库出发，途经多个客户后返回另一座仓库；这通过节点集合与出发/返回时刻变量来实现。
• 可替代约束：文中还提供了不使用辅助变量、直接约束服务时间落在某个时间窗的写法。通过对比实验，两种建模方式的效率差异明显，辅助变量法更高效。

三、两阶段启发式算法设计

为解决大规模 WDIRP，在 MILP 难以求解时，作者提出了两阶段启发式算法，包括多贪婪算法构建初始解和变量邻域搜索（VNS）优化。

3.1 多贪婪初始解构建

多贪婪算法的流程如算法1所示。

1. 仓库分配：为每个客户计算贪婪函数

   其中  为仓库  到客户  的行驶时间， 为需求， 为装载速度。选择  最小的仓库为客户服务。
2. 路线构建：按照客户最早开窗  排序，依次插入到路径中。初始装载开始时间为

   并保证不早于仓库开窗。
3. 时间调整：为满足后续客户时间窗约束，计算每个客户在其第  个时间窗可调整时间 。该最小值即为当前路线的最大调整量 ，用以同步调整装载开始时间，尽可能接纳更多客户。
4. 选择返回仓库：当无法继续插入客户时，根据最短回程时间选择返回仓库。

3.2 变量邻域搜索（VNS）

VNS用于从初始解出发不断改进路径，其结构如算法2所示：

• 邻域设计：包括三大类11个操作：节点重新定位 (Relocation) 、节点插入 (Insertion) 、节点交换 (Exchange) 。操作允许在同仓库(same warehouse, sw)或不同仓库(different warehouse, dw)间移动1–3个节点。
• 摇动与搜索：外层循环随机选择一个邻域进行“摇动”，内层循环结合局部搜索操作寻找改进解。若改进成功则更新当前最优解并重置邻域，否则切换到下一个邻域。
• 停止条件：外层循环迭代次数达到预设值或连续若干轮未改进时停止。作者设置外层迭代上限为1000，内层为30。

下面的图2–图4展示了三类邻域操作示意：

3.3 算法流程

总体流程为：利用多贪婪算法生成初始解；然后对该解施加 VNS 优化，通过摇动和局部搜索反复改进，最终得到优化解。

四、真实数据驱动的实例构建

作者使用重庆市中心及周边为研究区域，结合多源数据生成随机、基准和真实实例。共设计 20 个小规模随机实例、20 个基准实例和 18 个真实实例，还构建了扩展实例以测试算法规模性。

4.1 仓库与客户位置

• 仓库选取：选取沃尔玛、永辉、新世纪、盒马等大型超市作为仓库，利用在线地图 API 获取 POI 位置。下图显示研究区域内各研究单元，如渝北、南坪等。

• 客户位置与数量：利用手机信令基站代表客户位置，并根据基站覆盖的居民人口数估计客户数量。图7呈现了基站分布和人口密度。

4.2 路径与行驶时间

通过路网拓扑数据和 GPS 浮动车数据，采用地图匹配与 Dijkstra 算法评估任意两节点间的实际行驶时间。下图为仓库至客户、客户之间的最短路径示例。

4.3 客户需求预测

采用POI影响、交通绩效指数 (TPI) 和人口密度三指标加权预测客户潜在需求。权重通过AHP确定，最终结果为；以基础需求  kg 计算客户需求

图8展示了 Voronoi 方法划分的客户服务区，图9为需求预测结果。

4.4 其他参数

实际城市配送中，车辆装载速度  介于 1000–1500 kg/h，服务时间  为 0.2 h/客户，车辆容量  为 400–800 kg，客户时间窗数  为 2–4。

五、计算实验与结果分析

作者通过三类实例验证模型和算法的性能，并利用 ArcGIS 进行三维模拟。以下分两部分介绍。

5.1 小规模与基准实例

在 20 个随机小实例中，模型使用 CPLEX 求得最优解；对比传统建模方式，双侧时间窗辅助变量模型在计算时间上平均节约 8.85%，在较难实例中目标值降低 2.19%。采用两阶段启发式算法后，目标值接近最优解，平均偏差不超过 2.8%，证明算法有效。

5.2 真实实例与管理洞见

1. 工作日与非工作日差异：非工作日交通更顺畅，行驶时间更短，因此在同等需求下总时间成本更低。图10显示不同区域在工作日与非工作日的目标值差异。

2. 仓库规模影响：在客户规模相近时，增加参与仓库数量可降低平均单客户时间成本。图11展示了仓库数量与服务质量指标的关系；例如南坪地区，单客户时间随着仓库数增加显著下降。

3. 客户需求变化：通过调整客户需求因子分析发现，需求增加导致总时间成本和车辆数增加，但平均服务效率与单客户时间基本平稳，可为企业进行灵活调度提供参考。图12展示了需求因子对各指标的影响。

4. 车均服务客户与时间成本：图13和图14展示了客户数量扩大时，每辆车服务的客户数量和平均单客户时间的变化趋势；规模经济使得车均客户数增加，而单客户时间略有下降，提示在密集区域适当增加客户整合效率更高。

5. 仓库与车辆利用率：图15、图16统计了各地区参与服务的仓库和车辆数。部分地区仓库利用率低，提示可共享仓库或整合网络。

6. 三维仿真：利用 ArcGIS 构建3D城市模型，模拟车辆在山地城市中的行驶路径，为运营者提供直观决策依据。

六、结论与未来研究

6.1 研究贡献

• 提出仓配一体配送路径问题的新模型，兼顾多仓库、可变装载效率、双侧多时间窗及半开放路线等现实特征。
• 创新的多时间窗建模方法：利用两个辅助变量确定服务窗口，提高了求解效率，优于常用的直接约束方式。
• 设计两阶段启发式算法，通过多贪婪初始化与VNS优化，在大规模实例上取得接近最优的解。
• 首次将POI、手机信令、GPS浮动车数据等融合到仓配问题中，构建真实实例并进行三维仿真。
• 提供了一系列管理洞见，如合理安排工作日与非工作日配送、平衡仓库数量与服务质量、关注规模经济效应等。

6.2 研究局限与展望

• 适用条件：双侧时间窗需获得企业和客户认同，且仓库需配备一定数量的自动装载机。
• 扩展场景：未来可考虑车辆异质化、固定车队规模、车辆重复利用、一对多自动装载等。
• 更复杂交通因素：包括实时拥堵、信号灯控制、禁限行等。
• 算法发展：结合分支定价、Benders分解、拉格朗日松弛以及机器学习等技术，提升模型的精确求解能力和启发式算法的效率。

通过对双侧时间窗和可变装载效率下仓配一体配送问题的深入研究，本篇论文为城市配送运营提供了新的模型和算法，并通过大数据驱动的实例和仿真验证其有效性，为未来城市物流优化提供了参考。

文章须知 

推文编辑：单子叶 

责任编辑：弓仪长

原文链接：https://doi.org/10.1016/j.tre.2025.104343