問題描述

給定一個圖，圖上的點代表客戶，邊代表客戶之間的路線，邊的權重代表客戶之間的距離，點上的數(shù)字代表每個用戶的需求量。

數(shù)學符號表示如下：

本文討論的問題背景：

• 用戶需求已知，且被一輛車滿足（不要拆開）；
• 有$m$輛車，且有相同的最大載量$L$；
• 路網(wǎng)絡是對稱的（往返距離一樣，不考慮上下坡之類的問題）；
• 要么取貨要么送貨；
• 1個倉庫，而且車的路線$T$要是閉環(huán)的（最后要回到倉庫）；
• 只考慮1個規(guī)劃周期；
• 目標是最小化車輛的行駛距離；
• 點0代表倉庫。

問題建模

決策變量

數(shù)學建模

疑問：這種建模方式怎么知道每輛車的路線？
會有圖上的哪些邊被選中，形成$m$個環(huán)，就知道啦！

目標函數(shù)：最小化行駛距離

$max{\sum }_{i,j\in V,i\ne j}{x}_{ij}?c_{ij}$

約束1：車輛從每個客戶出發(fā)一次

∑ j ∈ V , i ≠ j x i j = 1 , ? i ∈ V ? { 0 } \sum_{j \in V, i \neq j}x_{ij} = 1, \forall i \in V-\{0\} ∑j∈V,i=j?xij?=1,?i∈V?{0}

約束2：車輛進入每個客戶一次

∑ j ∈ V , i ≠ j x j i = 1 , ? i ∈ V ? { 0 } \sum_{j \in V, i \neq j}x_{ji} = 1, \forall i \in V-\{0\} ∑j∈V,i=j?xji?=1,?i∈V?{0}

約束3：最多用$m$輛車

∑ j ∈ V ? { 0 } x 0 j ≤ m \sum_{j \in V-\{0\}}x_{0j} \leq m ∑j∈V?{0}?x0j?≤m

如果只是上面的模型，可能會出現(xiàn)下圖這種解，右下角這個環(huán)沒有包含倉庫！因此，我們需要一個約束去消除這種不包含倉庫的子環(huán)。此外，上面的約束也沒有約束車輛的容量限制！這也是VRP建模的一個略難的約束。

基于容量的消除子環(huán)的約束 （load-based SECs）

學術上稱為Sub-tour-elimination constraints (SECs)，該約束需要保證：

1. 每個環(huán)路不超過車輛最大容量；
2. 每個環(huán)路都包含倉庫。

新引入一個變量：
$u_i$： 假設我們的問題是車輛去客戶那里取貨，$u_i$表示車輛到達客戶點$i$時的載量，$?i\in V$；

因此有如下約束：

如果我們選擇了$(i,j)$這條連邊，那么車輛到達客戶$i$時的容量，加上用戶$i$寄貨的重量，要為車輛到達客戶$j$時的容量。邏輯上是相等的，但是我理解是為了刻畫這個等式的成立是基于$(i,j)$這條連邊被選擇，所以描述成了下面的$\le$的形式。

$u_i+b_i\le u_j+(1?x_{ij})L,?i,j\in V?0,i\ne j$

但是這個約束并沒有刻畫車輛的容量限制？

應該還要加一個：
$u_i\le L，?i\in V$

CVRP完整的數(shù)學模型

加上時間窗限制的CVRP

假設某些客戶只想在特定時間段被服務，那么在上述問題的基礎上，我們需要引入如下新的常量定義：

同時，我們需要引入一個新的決策變量：
$a_i$：到達客戶$i$時的時間，$?i\in V$

新增的約束包括：

1. 定義到達第一個客戶的時間：

$t_{0j}{x}_{ij}\le a_j,?j\in V$

2. 約束兩個連續(xù)訪問的用戶的時間：訪問用戶$i$的時間+用戶$i$被服務的時間+從$i$到$j$的形式時間 = 訪問用戶$j$的時間

$a_i+s_i+t_{ij}\le a_j+(1?x_{ij})T，?i,j\in V?0，i\ne j$

3. 約束每個用戶被訪問的時間在指定時間窗內(nèi)：
$w_i^s\le a_i,?i\in V?0$
$a_i+s_i\le w_i^e,?j\in V?0$