VRP's Math Model

• General VRP
• VRP Model Demo
  • 1. Notions
    • 1.1 Origin Notions
    • 1.2 New Notions
  • 2. Objections
    • 2.1 Origin Objections
    • 2.2 New Objections
  • 3. Constraints
    • 3.1 Origin Constraints
    • 3.2 New Constraints
    • 3.3 Accessible Condition
  • 4. Todo
  • 5. Some pics
• VRPTW

General VRP

VRP Model Demo

1. Notions

1.1 Origin Notions

• 节点

$i,j\in\{0,1,2,...,N\}$

• 车辆

$k\in\{1,2,3,...,K\}$

• 决策变量

$x_{ijk}\in\{0,1\}$

决策变量满足：

\begin{align*} x_{iik}=0 , \quad &\forall i\in\{0,1,2,...,N\} \\ &\forall k\in\{1,2,3,...,K\} \end{align*}

• 车辆载货量

$Cap$

• 团长节点的需求量 (向量形式)

$d=[d_1,d_2,d_3,...,d_N]^T$

• 节点间 【距离/路线成本/时间】

$C=\{c_{ij}\}$

节点间【距离/路线成本/时间】满足：（使用【导航距离】时第一个式子不考虑）

\begin{align*} c_{ij} &= c_{ji}, \\ c_{ii} &= 0 ,\quad \forall i,j\in\{0,1,2,...,N\} \end{align*}

1.2 New Notions

• 每条路线的最大节点数，不包括仓库节点

$n$

• 每个团长节点的时间窗

$[b_i, e_i],\quad i\in\{1,2,...,N\}$

• 仓库节点的最早取货时间与最晚返库时间

$[b_0, e_0]$

• 每个节点的服务时间

$s_i,\quad i\in\{0,1,2,...,N\}$

• 第 $k$ 辆车在 $i$ 节点开始服务的时间戳

  若不经过则为 $0$

$S_{ik}$

• 尾节点集合 $H$
  • 暂时只有一个地方用到

若要求车一定不会返回仓库:

$\sum_{k=1}^K\sum_{j=0}^N x_{hjk}=0, \quad \forall h\in H$

若要求车一定返回仓库：

• 还可进一步定义每个尾节点$h_i$对应的车$k_i$

\begin{align*} \sum_{k=1}^Kx_{h0k}=1, \quad \forall h\in H \\ \end{align*}

2. Objections

2.1 Origin Objections

• 最少车辆数

\begin{align*} \min K=\min \sum_{k=1}^K\sum_{j=1}^N x_{0jk} \end{align*}

若要求车一定返回仓库，则可换成

\begin{align*} \min K=\min \sum_{k=1}^K\sum_{j=1}^N x_{0jk}=\min \sum_{k=1}^K\sum_{j=1}^N x_{j0k} \end{align*}

• 最少【距离/路线成本/时间】

若车返不返回仓库都可以

$\min \sum_{k=1}^K \sum_{i=0}^N \sum_{j=1}^N c_{ij}x_{ijk}$

若要求车一定返回仓库

$\min \sum_{k=1}^K \sum_{i=0}^N \sum_{j=0}^N c_{ij}x_{ijk}$

2.2 New Objections

• 总成本定义为【每辆车的固定价格】和【按距离成正比增长的路程价格】

  还可以加上【时间窗约束的违反成本】。【和节点订单数成正比的服务时间的价格】是固定的，可能与车联动时需要考虑

$\min \Bigl( \alpha K+\beta \sum_{k=1}^K \sum_{i=0}^N \sum_{j=0}^N c_{ij}x_{ijk} \Bigr)$

3. Constraints

3.1 Origin Constraints

• 每辆车最多负责一条线路

$\sum_{j=1}^N x_{0jk}=1 ,\quad \forall k\in\{1,2,3,...,K\}$

若要求车一定不会返回仓库

$\sum_{i=1}^N x_{i0k}=0 \quad \forall k\in\{1,2,3,...,K\}$

若要求车一定返回仓库

$\sum_{i=1}^N x_{i0k}=1 \quad \forall k\in\{1,2,3,...,K\}$

• 从 $i$ 节点到 $j$ 节点，最多一辆车从中经过

$\sum_{k=1}^K x_{ijk}\leq 1 ,\quad \forall i,j\in\{1,2,...,N\}$

• 每个节点有且仅有一辆车为其服务

• $j$ 下标不可在第一个位置。for OVRP，若$j\in H$，则和为 $0$
• $j$ 下标不可取 $0$。for VRP，则和为 $K$；for OVRP，则和为 $0$

$\sum_{k=1}^K\sum_{i=0}^N x_{ijk}=1, \quad \forall j\in\{1,2,...,N\}$

• 流量平衡的连通原则

若要求车一定不会返回仓库

\begin{align*} 1=\sum_{k=1}^K \sum_{i=0}^N x_{ijk}=\sum_{k=1}^K \sum_{i=0}^N x_{jik} \quad &\forall j \notin \{0\} \cup H \\ \end{align*}

若要求车一定返回仓库

\begin{align*} 1= \sum_{k=1}^K \sum_{i=0}^N x_{ijk}=\sum_{k=1}^K \sum_{i=0}^N x_{jik} \quad &\forall j\in\{0,1,2,...,N\} \\ \end{align*}

• 每辆车负责配送的货物不超过其载货量

$\sum_{i=0}^N\sum_{j=1}^N d_j x_{ijk} \leq Cap, \quad \forall k\in\{1,2,3,...,K\}$

• 防止出现孤立子环

  计算复杂度太高，实际约束中不考虑，仅作为解可行性的测试条件

$\sum_{k=1}^K\sum_{i\in S}\sum_{j\in S} x_{ijk}\leq |S|-1, \quad \forall S\subseteq \{1,2,...,N\}$

• 车辆数 $K$ 值的下界

$K \geq \max \{\frac {\sum_{i=1}^N d_i} {Cap} , \frac {N}{n}\}$

3.2 New Constraints

• 限制每条路线的节点数

若要求车一定不返回仓库：

$\sum_{i=0}^N\sum_{j=1}^N x_{ijk} \leq n, \quad \forall k\in\{1,2,3,...,K\}$

若要求车一定返回仓库：

$\sum_{i=0}^N\sum_{j=0}^N x_{ijk} \leq n+1, \quad \forall k\in\{1,2,3,...,K\}$

• 每辆车在其路径上的每个节点都满足其节点的时间窗约束：

\begin{align*} b_j \sum_{i=1}^K x_{ijk} \leq S_{jk} \leq e_j \sum_{i=1}^K x_{ijk} , \quad &\forall k\in\{1,2,3,...,K\} \\ &\forall j\in\{1,2,3,...,N\}\\ \end{align*} \begin{align*} S_{ik}+s_i+c_{ij}-S_{jk} \leq 0 , \quad &\forall x_{ijk}=1 \end{align*}

3.3 Accessible Condition

• 从仓库到第一个团长节点的服务时间结束之前

$b_0 \leq \min (e_{j}- c_{0j}) ,\quad \forall j\in\{1,2,3,...,N\}$

若要求车一定返回仓库

• 从最后一个团长节点到仓库

$e_0 \geq \min (b_{i}+ s_i+ c_{i0}) ,\quad \forall i\in\{1,2,3,...,N\}$

4. Todo

1. 考虑司机起始位置到仓库的时间

• 司机起始节点 1~k
• 将其加入目标即可，无约束

1. 去掉不满足以下约束的弧，令 相应的x为0且不可变 即可

• 时间约束：

$b_{i}+s_i+c_{ij} \leq b_j$

• 载货量约束

$d_i+d_j \leq Cap$

5. Some pics

VRPTW