交通 | 基于分支定价算法框架求解带有时间窗的两级车辆路径优化问题

运筹OR帷幄

1111人浏览 · 2025-06-24 01:41:22

运筹OR帷幄 · 2025-06-24 01:41:22 发布

在这里插入图片描述

摘要：本文研究带时间窗的两层车辆路径优化问题。第一层路径负责将货物从配送中心转运至中间设施（即中转站），第二层路径则需在客户指定时间窗内将货物从中转站配送至最终客户。针对该问题，本研究提出两种基于路径的数学建模方法：（1）第一种模型将两层配送路径整合为统一路径网络；（2）第二种模型对两层配送路径进行解耦处理。基于分支定价算法框架，本研究为两种模型分别开发了求解方法。通过对大量算例的对比测试，本研究首次在学术领域实现了包含5个中转站和100个客户的大规模算例的精确求解，这一求解规模在现有文献中尚属首次突破。

关键词：分枝定价法、列生成、带时间窗的两层车辆路径优化问题

1. 引言

两级车辆路径问题（2E-VRP）在城际物流、电子商务、生鲜配送等领域有广泛应用，尤其是在城市物流中，通过卫星设施（如城市外围的仓库和市内的中转站）实现高效配送，减少大型车辆进入市中心，降低污染。本研究围绕带时间窗的两层级车辆路径问题（2E-VRPTW），即在第一层级从仓库到卫星设施运输货物，第二层级从卫星设施到最终客户，且客户有严格的时间窗限制。现有研究主要集中在无时间窗的2E-VRP，且多采用启发式方法，精确算法较少。本研究的主要贡献是：（1）提出了两种基于路径的数学模型（2E-1P和2E-2P），分别采用整合和分解的策略描述问题；（2）针对每种模型，开发基于分支定价的精确算法，2E-2P模型对应的算法能够求解多达5个卫星点和100个客户的大规模实例，这是文献中首次解决如此大规模的实例。

2. 模型描述

问题描述：

（1）一级网络：同质一级车辆从多个仓库出发，将货物送至卫星点并返回相同仓库。一级车辆到达卫星点时，需进行装卸货操作，这会花费一定的服务时间，装卸完成后便能出发。

（2）二级网络：同质二级车辆装上来自一级车辆的货物后，从卫星点出发，将货物送至客户点并返回相同卫星点；客户有硬时间窗和服务时间，只能被服务一次。

一级车辆和二级车辆的容量和固定成本分别为 $K^{(1)}$ , $K^{(2)}$ , $h^{(1)}$ , $h^{(2)}$ ，其中往往 $K_{(1)} > K_{(2)}$ ，车辆数目无限制；仓库和卫星点没有时间窗；不能将货物从仓库直接送达客户点；一辆二级车辆的货物只来自一辆一级车辆。目标函数是最小化车辆固定成本和运输成本（包括服务时间，等待时间不计成本）。如图1展示了3个仓库、4个卫星点和8个客户的可行解。

2E-1P模型：定义tour-tree为一条一级路径以及它所访问的卫星点所对应的二级路径，图1中有3个tour-tree，分别是 $A − i − ii − A),{(i − 1 − i),(ii − 3 − 2 − ii)}],[(B − ii − iv − B), {(ii − 4 − 5 − ii),(iv − 6 − 7 − iv)}]$ , $C − iv − C), {(iv − 8 − iv)}]$ ，根据该定义可得如下数学模型，其中 $R\mathcal{R}$ 表示所有可行tour-tree的集合， $r$ 表示一条可行tour-tree， $c_r$ 表示路径 $r$ 的成本， $αrz\alpha_{rz}$ 表示路径 $r$ 是否访问客户点 $z$ , $y_r$ 是二元决策变量，表示是否选择路径 $r$ 。

2E-2P模型：将tour-tree解耦为一级路径和二级路径，例如图1中包含3条一级路径 ${(A − i − ii − A), (B − ii − iv − B), (C − iv − C)}$ 和5条二级路径 ${(i − 1 − i),(ii − 3 − 2 − ii),(ii − 4 − 5 − ii),(iv − 6 − 7 − iv),(iv− 8 − iv)}$ ，根据该定义可得如下数学模型，其中 $M\mathcal{M}$ 表示一级路径的集合， $L\mathcal{L}$ 表示二级路径的集合， $m$ 表示一条一级路径， $L_m$ 表示固定路径 $m$ 后可能的所有二级路径， $l$ 表示一条二级路径， $c_m$ 是一级路径的成本， $c_l$ 是二级路径的成本， $ξlz\xi_{lz}$ 表示路径 $l$ 是否访问客户点 $z$ ， $Dl\mathcal{D}_l$ 表示路径 $l$ 的总需求， $Xm\mathcal{X}_m$ 是二元决策变量，表示是否选择路径 $m$ ， $Yl\mathcal{Y}_l$ 是二元决策变量，表示是否选择路径 $l$ 。

3. 算法设计

2E-1P模型：

采用分支定价算法求解这一模型，列生成的子问题设计前向、后向和双向标签算法进行求解。

2E-2P模型：

求解该模型的算法如下图所示。该算法的思路是首先枚举所有可能的一级车辆路径，并将多条路径组合形成一级网络的解（每个解称作一个配置），在固定一个配置的情况下，求解2E-2P模型，其中只考虑部分配置。其中 $M$ 表示一个配置， $θ\theta$ 是算法的参数， $LB_{AG}(M)$ 表示基于聚合的下界， $LB_{AP}(M)$ 表示基于分配的下界， $LB_{AP}(M) > LB_{AG}(M)$ 。1.a行产生所有可行的一级车辆路径，在每次迭代过程中，产生 $θ\theta$ 个最好的配置并将其加入到当前的配置集合 $W$ （1.c行和23行）。 $W$ 重新按照 $LB_{AP}(M)$ 的值由小到大排序。对于每个配置 $M∈WM\in W$ 产生一棵搜索子树，该子树中所有节点的解中都将一级网络的解固定为 $M$ （行2），采用列生成求解该模型的线性松弛问题，其中将 $M\mathcal{M}$ 替换为配置 $M$ ，并固定 $Xm=1,m∈M\mathcal{X}_m=1, m \in M$ （行7-13）。只要下一个配置产生的下界好于当前最优下界，就初始化下一棵子树（行24）。

4. 数值实验

算例产生：

（1）车辆情况：一级车辆容积200，固定成本50；二级车辆容积50，固定成本25

（2）卫星点和客户的服务时间为10

（3）结点组合：depots+satellites有3种组合：2/3；3/5；6/4；customers的数量为15/30/50/100

（4）数据分为Ca,Cb,Cc,Cd四类，每类共有60个算例，其区别在于客户时间窗和需求

实验结果：

2E-1P模型：在15个客户的实例中表现良好，但在更大规模实例中求解时间较长，尤其是时间窗较宽的实例。
2E-2P模型：在15至100个客户的实例中均表现出色，能够高效求解中等规模问题（如5个卫星节点和100个客户节点），且平均求解时间较短。

5. 总结与展望

本文的主要贡献在于提出了两种新的数学模型和高效的分支定价算法，首次实现了对中等规模2E-VRPTW问题的精确求解。未来研究方向包括：设计启发式方法以处理更大规模的实例；扩展模型以考虑更多实际约束，如动态需求或不确定性；进一步优化算法，提升求解效率。本文的研究为城市物流中的路径优化问题提供了重要的理论支持和实用工具。