在复杂约束下的车辆路径优化研究中，一般存在两种模型构建方式：（1）基于vehicle-index 的边流模型 （arc-flow model）；（2）基于route-related variables 的 集合划分模型（route-based model）。这两种建模方式各有其特点与适用场景。

1. 边流模型&集合划分模型之优缺点分析

1.1 边流模型 Arc-flow Model 的优缺点

Arc-flow model 一般构建在物流运输场景下的完全有向图上，以某车辆是否经过有向图上的某一条弧作为主要决策变量，辅以流平衡约束，容量约束以及顾客需求约束等其他特殊约束，从而构建完整的模型。该种模型能够用相对有限的变量构建完整的模型。但是，由于inherent symmtries 导致 search tree 的低效剪支，该种模型在通用的以 branch & bound 为底层算法的商业求解器下的求解效果不佳。

1.2  集合划分模型 Route-based Model 的优缺点

Route-based model 在完全有向图上基于预先产生的feasible routes 设定路径相关的变量（如是否选择某路径的 binary 变量）。该种建模方式通过忽略车辆索引与路径枚举有效避免了inherent symmtries 导致的剪枝低效。但是，若要以该种建模方式构建compact formultaion，通常意味着路径相关变量的指数爆炸。因此，在大多数路径优化领域的研究当时，arc-flow model 一般会作为复杂优化问题的compact formulation，并且可以直接通过通用求解器求解得到算例的精确解。通常会设计Branch-and-price算法来求解route-based model，在分枝定价（Branch-and-price）算法中会用到列生成（colunm generation）法来求解中间节点对应的线性松弛最优解。

既然这两种模型都能够通过一定方式得到精确解，那么哪种模型会表现得相对更好呢？在算法求解上，绝大部分基于 route-based model 的Branch and Price算法效果要显著优于基于求解器求解的 arc-flow model。而本文将从模型根节点（root node）线性松弛最优解（最小化问题是下界，最大化问题是上界）的角度来比较这两种模型的下界或者上界的优劣。我们通过松弛arc-flow model的整数变量，然后直接用数学规划求解器CPLEX求模型的上界或者下界；松弛route-based model的整数变量，然后用列生成（colunm generation）法求模型的上界或者下界。

1.3  实验问题选择

我们选择了两种复杂的车辆路径优化问题来进行实验比较。分别是 the synchronized vehicle routing problem with split delivery, proportional service time and multiple  time windows 以及 the electric vehicle relocation problem in one-way carsharing systems。关于这两个问题的分支定价算法分别发表在期刊TRE与期刊Omega上。感兴趣的读者可以详细阅读这两篇文章：

Qin Hu, Su E, Wang Yilun, Li Jiliu. Branch-and-price-and-cut for the electric vehicle relocation problem in one-way carsharing systems[J]. Omega, 2022, 109: 102609.

Li Jiliu, Qin Hu, Baldacci Roberto, Zhu wenbin. Branch-and-price-and-cut for the synchronized vehicle routing problem with split delivery, proportional service time and multiple time windows[J]. Transportation Research Part E: Logistics and Transportation Review, 2020, 140: 101955.

关于 the electric vehicle relocation problem in one-way carsharing systems 问题的详细介绍可参考推文论文拾萃｜分支定价切割算法精确求解单向汽车共享系统中的E-VReP。我们着重介绍问题：the synchronized vehicle routing problem with split delivery, proportional service time and multiple  time windows 。

2. 问题介绍

2.1 带有拆分送货、比例服务时间和多个时间窗口的同步车辆调度问题

我们先详细介绍一下 the synchronized vehicle routing problem with split delivery, proportional service time and multiple  time windows（SVRP-SPM）问题。该问题定义于如下：

在该问题中，车队需要从仓库出发，满足各个顾客点的需求，其中需求是离散的，允许分拆分送，服务时间与交付的产品单位成正比，并提供多个时间窗口，同时每个顾客的所有需求产品必须在一个时间窗口内交付（该要求称为同步约束）。SVRP-SPM 的一个典型应用出现在家庭服务中。在中国，居民通常雇用小时工（即家政服务人员）来清洁他们的公寓或房屋，并提供多个可用时间段，要求在这些时间段内完成服务。为了方便起见，居民更喜欢服务在一个时间段内开始并结束。家庭服务提供商可以在同一时间段内派遣多名家政服务人员来服务客户（即服务时间可以分割），并且每位家政服务人员分配的服务时间必须是 1 小时的整数倍。在这个应用中，我们可以假设家政服务人员将产品交付给居民，每单位产品的卸货时间为 1 小时。另一个应用场景是交付笨重或危险的产品。通常，从车辆上卸下笨重或危险产品并将其送往客户的存储空间（例如，仓库）是非常耗时的。例如，我们可以假设接收一个笨重的产品，如大冰箱，需要固定的时间。客户可能会订购一定数量的笨重产品，然后制造商安排车辆交付这些产品。每个客户的需求可以由多辆车辆满足，所有笨重产品必须在客户指定的时间窗口之一内交付。

Fig.1. 显示了 SVRP-SPM 的一个示例解决方案，其中两辆车为四个客户提供服务。矩形表示客户，矩形内的方形代表虚拟负载顶点。矩形旁边的三角形表示时间窗，与矩形通过实线箭头连接的三角形是所选择的时间窗。在该图中，有两条路线 0-1-4-5 和 0-1-2-3-5。第一条路线访问客户 1 和 5，交付量分别为 1 和 3 单位；第二条路线访问客户 1、2 和 3，交付量分别为 3、2 和 2 单位。与客户 1 至 4 相关的所选时间窗口分别为 [8:40, 10:20]、[10:30, 14:00]、[16:00, 17:30] 和 [10:00, 13:00]。

2.1.1 边流模型 Arc-flow Model

模型变量定义如下

• : 0-1变量，表示如果车辆k访问弧（u，v），则为1，反之为0；
• : 0-1变量，表示如果车辆k访问装载点u且选择时间窗w则为1，反之为0；
• : 0-1变量，表示如果顾客i选择时间窗w则为1，反之为0；
• : 为表示车k在装载点u的开始服务时间的决策变量。

模型如下：

在约束条件（1-13）中，M 是一个足够大的正数。目标函数（1-1）最小化总旅行成本。约束条件（1-2）确保每个客户的需求得到充分满足。约束条件（1-3）对每个客户施加了最低访问次数的要求。约束条件（1-4）至（1-6）定义了每条可能路线的结构。约束条件（1-7）限制每个客户只能被同一车辆访问最多一次。约束条件（1-8）说明，如果某顶点被车辆kk 访问，则与uu 和kk 相关的决策变量必须设置为 1。约束条件（1-9）是车辆容量约束。约束条件（1-10）至（1-12）是同步约束。约束条件（1-13）至（1-15）确保每个客户选择的时间窗口必须被遵守。最后，关于变量（1-16）至（1-18）给出变量定义。

2.1.2 集合划分模型 Route-based Model

模型变量定义如下

• :可行路径集合 ；
• : 某条路径r的成本；
• : 0-1参数，表示如果路径在时间窗w内包含装载点u则为1，反之为0；
• : 0-1参数，如果路径包含顾客点i为1，反之则为0；
• : 整数变量，路径r被选择的次数；

模型如下：

一条路线是可行的，如果满足以下三个条件：(1) 路线最多访问每个客户一次；(2) 每个客户在该路线中选择其可用时间窗口之一；(3) 路线满足车辆容量约束和持续时间约束。目标函数（2-1）最小化总旅行成本。约束条件（2-2）确保客户需求得到充分满足。约束条件（2-3）限制每个客户的最低访问次数。约束条件（2-4）规定最多可使用KKK 辆车辆。约束条件（2-5）是对决策变量rrr 的整数要求。需要注意的是，我们不能将rrr 定义为二元变量，因为多个车辆可以沿某条特定路线行驶，这与 Desaulniers (2010) 和 Luo et al. (2017) 中的模型不同。

2.2 单向汽车共享系统中的E-VReP问题

论文拾萃｜分支定价切割算法精确求解单向汽车共享系统中的E-VReP 有关于该问题详细的介绍，包括对模型以及算法详细解释，我们在本推文也还是简单介绍一下该问题，需要注意的是该问题是一个最大化问题，因此在之后的下界比较中一定是下界越小的下界越紧凑。

单向汽车共享系统（One-Way Carsharing Systems）是一种创新的共享出行方式，它允许用户在一个地点取车并在不同的地点还车，而不必将车辆归还到原来取车点。这种系统提供了更大的灵活性和便利性，尤其适合城市内短途出行和多地点间的旅行。

E-VReP 定义在有向图 上，其中 是节点集， 是一个弧集。节点 和 称为起始节点和目标节点，分别代表出现在路线 起点 和 终点 的两个虚拟节点。

节点子集 表示需要将电动汽车移至其他停车站的取车请求集合， 表示工作人员交付电动汽车以防止某些停车站车辆耗尽的交付请求集合。

每条距离为 的弧线 分别具有固定的EV行驶时间 和骑行时间 。

工作人员将自行车 放入/取出 后备箱会产生服务时间 ，并且对每个节点 施加一个时间窗口 ，其中 和 表示最早时间和允许服务请求 的最晚时间。

如果早于 ，工人必须在节点 等待，直到到达 ，如果晚于 到达，则不允许他们进行搬迁。以代接节点 为例， 之前的时间表示该EV不可用，而 之后的时间表示该 EV 可以被用户 保留/使用。

为了简单起见，让 ；让 和 ，因此，the planning horizon 等于车辆段时间窗口的长度。对于配送节点 ，令  表示 EV 在时间 时必须具有的最小剩余电池电量。然而，我们允许在 之前交付电池电量低于 的电动汽车，前提是在 时至少达到 ，因为电池在交付后可以充电。对于拾取节点 ， 表示在时间 时 EV 的当前电池电量。

为每个搬迁请求分配相应的收入，我们仅将交付请求 与收入 相关联。这是因为，只有完成电动汽车的交付，才能收钱，系统才能实现盈利。假设有一个由同质工人组成的团队，每个工人都有最长工作时间 和雇佣成本 ，他们可以在不同时间离开仓库以满足不同的请求。工人驾驶电动汽车从取货节点到送货节点，除此之外，他们必须骑自行车在以下路径之间移动：从仓库到取货节点 → 从送货节点到下一个取货节点 → 再从最终的送货节点返回仓库。

上述假设图中，虚线表示从仓库到取货节点 和 从最终的送货节点返回仓库 为 分钟。实线表示从送货节点到下一个取货节点 为 分钟。橘色矩形代表电量 的变化，被取走的电动汽车的电池电量会有可能低于交付的电动汽车所需的电量。在分配给 的路线中， 处的电动汽车的电池电量为 ，而 处所需的最低电池电量为 。电动汽车在 的 交付，电池电量为 ，因为从 到 的电池消耗为 。虽然是这样，在 最晚时间，即 ，电动汽车通过充电可以达到 的电池电量。从 到 （ 分钟），电池电量增加了 ，因为电动汽车在不使用时始终连接到充电底座。

E-VReP 的目标是最大化总利润，这等于所服务的交付请求所获得的总收入减去规划期间雇用工人所产生的总成本。每个工人最多可以执行一条路线，如果这条路线从仓库开始并结束于仓库，且在规定的时间  内完成一系列取货和送货请求，则该路线被认为是可行的。每个请求只能被服务一次，任何时候均不可重复服务同一个请求。

2.2.1 边流模型 Arc-flow Model

目标函数 (14) 旨在最大化总利润，该利润等于所有已服务的配送请求所获得的总收入减去雇用工人的总成本。约束条件 (15) 保证每个请求最多只能被访问一次。考虑到最多有∣𝐾∣名工人可用，约束条件 (16) 和 (18) 确保每个工人只能从配送中心 0 出发一次，并只能在配送中心 𝑛+1 返回一次。约束条件 (17) 是流量守恒约束。约束条件 (19)–(24) 与约束 (1)–(7) 类似。具体而言，约束 (19) 和 (20) 建立了同一工人访问的两个连续节点之间服务开始时间的关系。一个足够大的数 𝑀 确保这些约束的有效性，其中M=。约束条件 (21) 规定了所有请求的时间窗口。约束条件 (22)–(24) 定义了所有 𝑝 - 𝑑 对之间的电池电量约束。约束条件 (22) 确保当前电池电量能够覆盖从取货节点 𝑖 到配送节点 𝑗 的行程。此外，约束条件 (23) 和 (24) 限制到达配送节点时的电池电量不小于在时间 时的 。约束条件 (25) 确保每个工人的工作时长不超过阈值 𝑇。最后，约束条件 (26) 和 (27) 定义了决策变量的取值范围。

2.2.2 集合划分模型 Route-based Model

令 𝑅 表示工人可行路径的集合。对于任意路径 r∈R，其利润 表示为：。其中，是服务配送节点 𝑗 获得的收入， 是路径中是否使用弧 (i,j) 的指示变量，C 表示使用该路径的总成本。我们引入一个0-1决策变量 ，当路径 r 在最优解中被选择时，，否则,此外，我们定义一个二进制参数 ，若路径 r 访问节点 i，则 ,否则为 0。基于以上符号定义，模型如下所示：

目标函数 (28) 最大化所有选定路径的总利润。约束条件 (29) 限制每个请求最多只能被服务一次。约束条件 (30) 确保使用的工人数不超过最大限额∣K∣。约束条件 (31) 定义了决策变量的可行范围。需要注意的是，模型 (28)–(31) 包含指数级数量的决策变量（列）。

3. 下界对比实验

3.1 带有拆分送货、比例服务时间和多个时间窗口的同步车辆调度问题实验

对于带有需求可拆分、比例服务时间和多个时间窗口的同步车辆调度问题，我们选用了四个真实数据算例（HE1,HE2,HE3,HE4）进行对比试验，其中每个算例均包含25个顾客点。得到的两类模型在根节点的下界结果如下表：

该问题为一个最小化问题，因此lower bound数值越大效果越好。由上表可知，route-based model的lower bound在四个真实算例上的表现均优于arc-flow model。

3.2 单向汽车共享系统中的E-VReP问题

对于 the electric vehicle relocation problem in one-way carsharing systems 问题，我们选用了作者在论文中提到的10个中等规模算例进行对比试验，详细算例介绍可参考论文。得到的两类模型在根节点的下界结果如下表：

需要特别注意的是该问题为一个最大化问题，因此upper bound数值越小效果越好。由上表可知，route-based model的upper bound在十个算例上的表现也大幅均优于arc-flow model。

3.3 总结

通过这两类问题算例的对比试验我们可以知道，在这两类问题中，arc-flow model 在根节点所提供的下界远差于 route-based model 在根节点提供的下界。

本文的参考文献如下，感兴趣的读者可以详细阅读这两篇文章。

Qin H, Su E, Wang Y, et al. Branch-and-price-and-cut for the electric vehicle relocation problem in one-way carsharing systems[J]. Omega, 2022, 109: 102609.

Li J, Qin H, Baldacci R, et al. Branch-and-price-and-cut for the synchronized vehicle routing problem with split delivery, proportional service time and multiple time windows[J]. Transportation Research Part E: Logistics and Transportation Review, 2020, 140: 101955.

文案&排版：陆治中（华中科技大学管理学院研究生一年级）

指导老师：秦虎老师（华中科技大学管理学院）

如对文中内容有疑问，欢迎交流。

如有需求，可以联系：

秦虎老师（华中科技大学管理学院，tigerqin1980@qq.com）