书接上回，今天我们来看一个更加复杂的问题，VRP问题【指车辆路径问题（Vehicle Routing Problem）】，通过上面的学习知道了TSP问题是一个人和若干个景点，遍历一遍的最小代价和方案。VRP问题的问题定义是指一定数量的客户，各自有不同数量的货物需求，配送中心向客户提供货物，由一个车队负责分送货物，组织适当的行车路线，目标是使得客户的需求得到满足，并能在一定的约束下，达到诸如路程最短、成本最小、耗费时间最少等目的。
原始的VRP问题的简单抽象如下
一个出发点，N台车，M个终点和需求量，最终找到满足所有配送点需求的运输方案，这个已经很符合生活中的场景啦。

经典VRP问题

经典的VRP问题是一种组合优化问题，涉及在有限数量的车辆和一组客户点之间规划车辆的路线，以最小化车辆行驶的总距离或成本，同时满足客户点的需求和车辆的容量限制。下面详细解释如何使用运筹学建模来描述经典的VRP问题：

参数定义

n：客户点的数量，假设有n个客户点，编号为1到n。
m：车辆的数量，假设有m辆车。
q[i]：表示客户点i的货物需求量。
Q：每辆车的容量限制，即可装载的货物量上限。
c[i][j]：表示从客户点i到客户点j的距离或成本。

决策变量

x[i][j][k]：二进制变量，表示第k辆车是否从客户点i直接到客户点j（1表示经过，0表示不经过）。
y[i][k]：二进制变量，表示第k辆车是否访问客户点i（1表示访问，0表示不访问）。

目标函数

最小化总距离或总成本

$$min\ Σ_{i=0}^{n} Σ_{j=0}^{n} Σ_{k=1}^{m} c[i][j] * x[i][j][k]$$

约束条件

每个客户点必须被访问且只能被访问一次：$Σ_{k=1}^{m} y[j][k] = 1,j \in [1,n]$
车辆路线约束：

$$Σ_{i=1}^{n} x[i][j][k] = 1, j \in [1,n], k \in [1,m]\\ Σ_{j=1}^{n} x[i][j][k] = 1, i \in [1,n],k \in [1,m]$$

排除回路： $x[i][i][k] = 0, i \in [1,n], k \in [1,m]$

以上就是简单的VRP的运筹抽象，也比较好理解的，接下来我们来看VRP问题几种变种，变种以后更加贴合实际应用场景。

Capacitated VRP(CVRP)

CVRP是一种变种VRP，其中固定容量的固定车辆车队必须以最小的运输成本满足客户对来自公共仓库的单个商品的已知需求。也就是说，CVRP就像VRP，但有一个额外的约束条件，即每个车辆必须具有统一的单一商品容量。

相比与经典的VRP问题，也就是添加了如下的约束条件。

每辆车的总载货量不能超过其容量限制： $Σ_{j=1}^{n} q[j] * y[j][k] ≤ Q, k \in [1,m]$
也就是说你送了这个路线，确保你车上的货物是够得。

Multiple Depot VRP(MDVRP)

公司可能有多个仓库，可以从中为客户提供服务。如果客户聚集在仓库附近，则应将分发问题建模为一组独立的VRP。如果客户和仓库混合在一起，则应该解决多仓库车辆路径问题。
MDVRP要求将客户分配到仓库。每个仓库都有一支车队。每辆车都来自一个仓库，为分配给该仓库的客户提供服务，然后返回同一仓库。
问题的目的是为所有客户提供服务，同时最大程度地减少车辆数量和行驶距离。

目标

最大程度地减少车辆数量和行驶时间，并且必须从几个仓库满足商品的总需求。

参数定义

n：客户点的数量，假设有 n 个客户点，编号为 1 到 n。
m：车辆的数量，假设有 m 辆车。
q[i]：表示客户点 i 的货物需求量。
Q：每辆车的容量限制，即可装载的货物量上限。
c[i][j]：表示从客户点 i 到客户点 j 的距离或成本。
p：车辆起始点的数量，假设有 p 个车辆起始点，编号为 1 到 p。

决策变量

x[i][j][k]：二进制变量，表示第 k 辆车是否从客户点 i 直接到客户点 j（1 表示经过，0 表示不经过）。
y[i][k]：二进制变量，表示第 k 辆车是否访问客户点 i（1 表示访问，0 表示不访问）。
z[i][k]：二进制变量，表示第 k 辆车是否从车辆起始点 i 出发（1 表示出发，0 表示不出发）。

目标函数

最小化总距离或总成本。

$$minimize Σ_{i=1}^{n} Σ_{j=0}^{n} Σ_{k=1}^{m} c[i][j] * x[i][j][k]$$

约束条件

每个客户点必须被访问且只能被访问一次： $Σ_{k=1}^{m} y[j][k] = 1, j \in[1,n]$

每辆车的总载货量不能超过其容量限制： $Σ_{j=1}^{n} q[j] * y[j][k] ≤ Q, k \in[1,m]$

车辆路线约束：

$$Σ_{i}^{n} x[i][j][k] = 1, j \in[1,n], k \in[1,m] \\ Σ_{j=1}^{n} x[i][j][k] = 1, i \in[1,n] , k \in [1,m]$$

车辆起始点约束： $Σ_{k=1}^{m} z[i][k] = 1, i \in [1, p]$

车辆和客户点关系约束：$y[i][k] ≤ z[i][k], i \in [1, p], k \in[1,m]$

排除回路： $x[i][i][k] = 0, i \in [1, p], k \in[1,m]$

VRP with Backhauls(VRPB)

带回程的车辆路线问题（VRPB）是一种VRP，客户可以在其中请求或退回一些商品。因此，在VRPPD中，需要考虑到客户退回交付车辆的货物必须适合其中。至关重要的假设是，必须在每条路线上进行所有交付，然后才能进行取货。这是由于以下事实：车辆被重新装载，并且在运送点处的轨道上的载荷的重新布置被认为不经济或不可行。待交付和提取的数量是固定的，并且事先已知。VRPB与VRPPD相似，但有一个限制：就VRPB而言，必须在完成任何取货之前完成每个路线的所有交付。

参数列表

n：客户点的数量，假设有 n 个客户点，编号为 1 到 n。
m：车辆的数量，假设有 m 辆车。
q[i]：表示客户点 i 的货物需求量。
Q：每辆车的容量限制，即可装载的货物量上限。
c[i][j]：表示从客户点 i 到客户点 j 的距离或成本。

决策变量

x[i][j][k]：二进制变量，表示第 k 辆车是否从客户点 i 直接到客户点 j（1 表示经过，0 表示不经过）。
y[i][k]：二进制变量，表示第 k 辆车是否访问客户点 i（1 表示访问，0 表示不访问）。
z[i][k]：二进制变量，表示第 k 辆车是否进行 Backhauls（1 表示进行，0 表示不进行）。

目标函数

最小化总距离或总成本，表示为：minimize Σ_{i=0}^{n} Σ_{j=0}^{n} Σ_{k=1}^{m} c[i][j] * x[i][j][k]

约束条件

每个客户点必须被访问且只能被访问一次： $Σ_{k=1}^{m} = 1, j \in [1,n]$
每辆车的总载货量不能超过其容量限制： $Σ_{j=1}^{n} q[j] * y[j][k] ≤ Q, k \in [1,m]$
车辆路线约束：

$$Σ_{i=1}^{n} x[i][j][k] = 1,j \in [1,n], k \in [1,m] \\ Σ_{j=1}^{n} x[i][j][k] = 1, i \in [1,n] k \in [1,m]$$

Backhauls 约束：$y[i][k] ≤ z[i][k], i \in [1,n] , k \in [1,m]$
排除回路： $x[i][i][k] = 0, i \in [1,n], k \in [1,m]$

VRP with Pick-Up and Delivering(VRPPD)

带提货和运送的车辆路径问题（VRPPD）是一种VRP，其中考虑了客户退还某些商品的可能性。因此，在VRPPD中，需要考虑到客户退回交付车辆的货物必须适合其中。这种限制使规划问题更加困难，并可能导致车辆容量利用率低下，行驶距离增加或需要更多车辆。
因此，通常要考虑有限的情况，即所有交付需求都从仓库开始，所有提货需求都应带回仓库，因此客户之间没有商品互换。另一种选择是放宽所有客户必须被精确访问一次的限制。另一个通常的简化是考虑到每辆车必须在提取任何货物之前交付所有商品。

参数定义

n：客户点的数量，假设有 n 个客户点，编号为 1 到 n。
m：车辆的数量，假设有 m 辆车。
q[i]：表示客户点 i 的货物需求量。
Q：每辆车的容量限制，即可装载的货物量上限。
c[i][j]：表示从客户点 i 到客户点 j 的距离或成本。

决策变量

x[i][j][k]：二进制变量，表示第 k 辆车是否从客户点 i 直接到客户点 j（1 表示经过，0 表示不经过）。
y[i][k]：二进制变量，表示第 k 辆车是否访问客户点 i（1 表示访问，0 表示不访问）。

目标函数

$$minimize\ Σ_{i=0}^{n} Σ_{j=0}^{n} Σ_{k=1}^{m} c[i][j] * x[i][j][k]$$

约束条件

每个客户点必须被访问且只能被访问一次： $Σ_{k=1}^{m} y[j][k] = 1, j \in [1,n]$

每辆车的总载货量不能超过其容量限制： $Σ_{j=1}^{n} q[j] * y[j][k] ≤ Q, k \in [1,m]$

车辆路线约束：

$$Σ_{i=1}^{n} x[i][j][k] = 1,j \in [1,n], k \in [1,m] \\ Σ_{j=1}^{n} x[i][j][k] = 1, i \in [1,n], k \in [1,m]$$

排除回路： $x[i][i][k] = 0, i \in [1,n] k \in [1,m]$

Pick-Up 和 Delivering 约束

对于每个客户点 i，如果车辆访问了该点，它必须同时进行货物的 Pick-Up 和 Delivering。也就是说，如果 y[i][k] = 1，则该车辆必须在客户点 i 进行 Pick-Up 和 Delivering。
这可以表示为以下约束条件： $y[i][k] ≤ x[i][j][k], i \in [1,n],j \in [1,n], k \in [1,m]$

VRP with Time Windows(VRPTW)

VRPTW的问题与VRP相同，其附加限制是客户对货物的送达时间有时间窗口要求。这就不就是外卖吗？

参数定义

n：客户点的数量，假设有 n 个客户点，编号为 1 到 n。
m：车辆的数量，假设有 m 辆车。
q[i]：表示客户点 i 的货物需求量。
Q：每辆车的容量限制，即可装载的货物量上限。
c[i][j]：表示从客户点 i 到客户点 j 的距离或成本。
e[i]：表示客户点 i 的时间窗口的开始时间（最早到达时间）。
l[i]：表示客户点 i 的时间窗口的结束时间（最晚到达时间）。

决策变量

x[i][j][k]：二进制变量，表示第 k 辆车是否从客户点 i 直接到客户点 j（1 表示经过，0 表示不经过）。
y[i][k]：二进制变量，表示第 k 辆车是否访问客户点 i（1 表示访问，0 表示不访问）。
t[i][k]：表示第 k 辆车在客户点 i 的到达时间。

目标函数

最小化总距离或总成本，表示为：

$$minimize Σ_{i=1}^{n} Σ_{j=1}^{n} Σ_{k=1}^{m} c[i][j] * x[i][j][k]$$

约束条件

每个客户点必须被访问且只能被访问一次： $Σ_{k=1}^{m} y[j][k] = 1, j \in [1,n]$

每辆车的总载货量不能超过其容量限制： $Σ_{j=1}^{n} q[j] * y[j][k] ≤ Q, k \in [1,m]$

车辆路线约束：

$$Σ_{i=1}^{n} x[i][j][k] = 1, j \in [1,n], k \in [1,m] Σ_{j=1}^{n}x[i][j][k] = 1, i \in [1,n], k \in [1,m]$$

排除回路：$ x[i][i][k] = 0, i \in [1,n], k \in [1,m]$

时间窗口约束： $e[i] ≤ t[i][k] ≤ l[i] - c[i][j] * x[i][j][k], i \in [1,n], j \in [1,n], k \in [1,m]$
（表示车辆在访问客户点 i 时，必须在其时间窗口范围内到达，t[i][k] 表示第 k 辆车在客户点 i 的到达时间）