【修改ing】基于pyscipopt库求解带时间窗车辆路径问题VRPTW

本文主要是介绍【修改ing】基于pyscipopt库求解带时间窗车辆路径问题VRPTW，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

1. 问题定义
2. VRPTW 数学模型
- 2.1 决策变量
- 2.2 约束条件
- 2.3 目标函数

本文章启发于南军Opt 的相关文章，模型引自 Guy Desaulniers 等人的《Column Generation》，具体将会对已有模型和程序进行详细介绍和扩展。

1. 问题定义

前面我们介绍了带容量限制的车辆路径问题（Capacitated vehicle routing problem, CVRP），在CVRP的基础上，限制车辆到达各个客户点的时间范围，即客户点的时间窗，它限制了车辆到达该客户点的最早和最晚时间，称为带时间窗的车辆路径问题（Vehicle routing with time windows, VRPTW），该时间维度上的约束条件使得车辆的运输方案要考虑在途时间和到达时间之间的关系，极大地增加了模型的复杂性，该约束是VRP问题的典型约束。

处理时间窗的方式很简单，但都需要定义车辆到达客户点的时间变量，通过约束该时间变量的范围，实现时间窗约束，而车辆到达每个客户点的时间具有相互依赖关系，在同一车辆路线上的前后节点的到达时间相距时间不小于节点间的转运时间。时间窗约束的常见分类有两种：

硬时间窗：即车辆到达客户点的时间必须在指定的时间窗内，提前到达则在客户点处等待，而晚于时间窗到达则不被允许（方案不可行）；
软时间窗：即车辆到达客户点的时间应尽量在指定时间窗范围内，如果不在指定时间窗范围内则会进行一定的惩罚，一般而言，晚于时间窗到达会有一个较大的惩罚系数，而早于时间窗到达是否惩罚则需要进行一定的声明。

2. VRPTW 数学模型

VRPTW 模型常常建立为多商品网络流模型（multi-commodity network ﬂow model）的形式，在一定目标下考虑商品流量在网络结构中的流动。具体到 VRPTW 问题的数学模型，则引用参考教材《Column Generation》的第三章节，其中的时间窗约束为硬约束。

2.1 决策变量

根据 VRPTW 问题的描述可知，我们需要直接决策的变量是派那一辆车去配送哪一段的路线，而简介的变量则是车辆到达某个客户点的到达时间，需要限制在一定范围内。变量以及参数如下：

模型决策变量：
1. $x_{ijk}$ 布尔变量，车辆 $k$ 是否负责节点 $i$ 和节点 $j$ 之间的直接配送，若是则取值为 $1$ ，否则取值为 $0$ ；
2. $s_{ik}$ 连续型变量，表示车辆 $k$ 到达节点 $i$ 的时间。由于这里出现了相当于车辆分配的问题，即节点 $i$ 是否是由车辆 $k$ 配送，在优化结果出来之前并不知道，因此有个关键问题是，既然我们要对所有的节点和车辆对建立变量，那如果节点 $i^{'}$ 不是由车辆 $k^{'}$ 配送的， $s_{i'k'}$ 的值应该取什么？不同的约束写法是否会对目标有影响？这个问题后文会进行解答。

这个问题具体得结合目标函数考虑（一般情况下，不同的约束形式只要不影响最终目标值，则认为模型是等价的）。

The inequalities (3.7) establish the relationship between the vehicle departure time from a customer and its immediate successor.
不等式(3.7)建立了车辆从顾客出发时间与其直接后继车辆出发时间之间的关系。
Finally constraints (3.8) affirm that the time windows are observed, and (3.9) are the integrality constraints.
最后，约束(3.8)确认时间窗被观察到，(3.9)是完整性约束。
Note that an unused vehicle is modeled by driving the “empty” route (0, n +1).
请注意，未使用的车辆通过行驶“空”路线(0,n +1)来建模。

2.2 约束条件

The constraints (3.2) ensure that each customer is visited exactly once, and (3.3) state that a vehicle can only be loaded up to it’s capacity.
约束条件(3.2)确保每个客户只访问一次，并且(3.3)规定车辆只能装载到其容量。
Next, equations (3.4), (3.5) and (3.6) indicate that each vehicle must leave the depot O;
由式(3.4)、(3.5)和式(3.6)可知，每辆车必须离开O站;
after a vehicle arrives at a customer it has to leave for another destination;
车辆到达客户处后，必须离开前往另一个目的地;
and finally, all vehicles must arrive at the depot n +1.
最后，所有车辆必须到达仓库n +1。