资源受限的基本最短路问题

发表于 更新于 分类于

在使用列生成算法求解带时间窗限制的车辆路径规划问题时，定价子问题是一个资源受限的基本最短路问题（Elementary Shortest Path Problem with Resource Constraints，ESSPRC）。在文献中[^1]证明了ESSPRC问题是强NPNP难的，因此针对大规模的问题，使用求解器求解速度较慢。

问题描述

有一辆容量为QQ的货车，从起点oo出发，为途中的客户送货，最后到达终点dd， 货车在配送时需要满足时间和容量的限制。假设有mm个客户，这些客户分布在不同的地点, 客户用集合CC表示，C={1,2,…,m}C = \{1, 2, \ldots, m\}。每个客户ii有不同的服务时间窗[ai,bi][a_i, b_i]和需求量qiq_i。本问题考虑的是硬时间窗，也就是说给客户ii的服务时间必须落在时间窗 [ai,bi][a_i, b_i]内。将起点oo记作0，终点dd设为m+1m+1，则所有的节点用集合VV表示，V={0,1,2,…,m+1}V = \{0, 1, 2, \ldots, m+1\}。从节点ii到节点jj的运输时间为tijt_ij, 运输成本为cijc_ij。问题的目标是，在货车容量不超载，每个客户最多被访问一次且服务开始时刻落在相应的服务时间窗内的情况下，最小化运输总成本。

数学模型

主要参考的是 Column Generation 书[^2]中的第三章，引用 Brian Kallehauge 等人提出的模型：

  • 变量：

    • xij={1,如果最短路径中包含弧 (i,j)∈V×V0,否则x_{ij} = \begin{cases} 1, & \text{如果最短路径中包含弧 } (i,j) \in V \times V \\ 0, & \text{否则} \end{cases}

    • sis_i: 到达点 i∈Vi\in V 的时刻

  • 目标函数：最小化运输总成本

    min⁡∑i∈V∑j∈Vcijxij\min\quad\sum_{i\in V}\sum_{j\in V}c_{ij}x_{ij}

  • 约束条件：
    • 容量约束，规定总运输量不能超过货车容量。

    ∑i∈Cqi∑j∈Vxij≤Q\sum_{i\in C}q_i\sum_{j\in V}x_{ij}\leq Q

    • 从起点出发只能一次。

    ∑j∈Vx0j=1\sum_{j\in V}x_{0j}=1

    • 到达终点只能一次。

    ∑i∈Vxi,m+1=1\sum_{i\in V}x_{i,m+1}=1

    • 客户节点之间的流平衡约束。

    ∑i∈Vxih=∑i∈Vxhj∀h∈C\sum_{i\in V}x_{ih}=\sum_{i\in V}x_{hj}\quad\forall h\in C

    • 硬时间窗约束。

    ai≤si≤bi∀i∈Va_i\leq s_i\leq b_i\quad\forall i\in V

    • 车辆的行驶时间约束，也实现了子回路消除功能。

    si+tij≤sj+Mij(1−xij)∀i∈V,∀j∈Vs_i+t_{ij}\leq s_j+M_{ij}(1-x_{ij})\quad\forall i\in V,\forall j\in V

    • 变量值域。

    xij∈{0,1}∀i∈V,∀j∈Vx_{ij}\in\{0,1\}\quad\forall i\in V,\forall j\in V

    • 任何节点都不能是自己的前继节点或者后继节点。

    xii=0∀i∈Vx_{ii}=0\quad\forall i\in V

补充： MijM_{ij}的取值，满足足够大但是尽量小，可以设为(bi−aj+tij)+ ∀i∈V,∀j∈V(b_i-a_j+t_{ij})^+\:\forall i\in V,\forall j\in V。

ESPPRC的松弛

由于ESPPRC是强NPNP难问题，在求解时通常会松弛问题中的某些约束。其中，应用非常广泛的就是允许路径中存在子回路，即允许客户被多次访问。如此，问题就变成了资源受限最短路问题（SPPRC）。

数学模型

基于前面介绍过的ESPPRC的模型，Brian Kallehauge 等人对SPPRC也给出了如下数学模型：
在模型中定义了一个额外的集合K={1,2,…,∣K∣}K= \{1, 2, \ldots, |K|\}，用来表示路径中弧的顺序。由于每个客户都可以多次访问，所以无法确定最后求得的路径中包含几条弧，但是路径所包含的弧的个数的上限∣K∣|K|是可以确定的。路径中弧的数量受限于容量资源和时间资源，所以∣K∣=min⁡{⌊Qmin⁡i∈V{qi}⌋,⌊bm+1min⁡(i,j)∈V×V{tij}⌋}|K|=\min\{\lfloor\frac{Q}{\min_{i\in V}\{q_i\}}\rfloor,\lfloor\frac{b_{m+1}}{\min_{(i,j)\in V\times V}\{t_{ij}\}}\rfloor\}。
需要注意的是，虽然在SPPRC中，每个客户允许被多次访问，但是，起点和终点在路径中还是只能出现一次。

  • 变量：

    • xijk={1,如果路径中的第 k∈K 条弧是 (i,j)∈V×V0,否则x_{ijk}=\begin{cases}1,&\text{如果路径中的第 }k\in K\text{ 条弧是 }(i,j)\in V\times V\\0,&\text{否则}&\end{cases}

    • siks_{ik}: 第k∈Kk\in K条弧上到达点i∈Vi\in V的时刻

  • 目标函数：最小化运输总成本

min⁡∑i∈V∑j∈V∑k∈Kcijxijk\min\quad\sum_{i\in V}\sum_{j\in V}\sum_{k\in K}c_{ij}x_{ijk}

  • 约束条件：
    • 路径中的弧必须按序连续出现：若第 kk 条弧在路径中（k≥2k \geq 2），则第 k−1k-1 条弧也必在路径中。

    ∑i∈V∑j∈Vxijk≤∑i∈V∑j∈Vxi,j,k−1∀k∈K∖{1}\sum_{i\in V}\sum_{j\in V}x_{ijk}\leq\sum_{i\in V}\sum_{j\in V}x_{i,j,k-1}\quad\forall k\in K\setminus\{1\}

    • 容量约束，规定总运输量不能超过货车容量。

    ∑i∈Cqi∑j∈V∑k∈Kxijk≤Q\sum_{i\in C}q_i\sum_{j\in V}\sum_{k\in K}x_{ijk}\leq Q

    • 从起点出发只能一次。

    ∑j∈V∑k∈Kx0jk=1\sum_{j\in V}\sum_{k\in K}x_{0jk}=1

    • 起始节点为0的弧必须是路径中的第一条弧。

    ∑j∈Vx0j1=1\sum_{j\in V}x_{0j1} = 1

    • 流平衡约束，规定对于每个客户节点来说，在第 (k−1)∈K∖{1}(k-1)\in K\setminus\{1\} 条弧的入度等于在第k∈K∖{1}k\in K\setminus\{1\}条弧上的出度。

    ∑i∈Vxih,k−1=∑j∈Vxhjk∀h∈C,∀k∈K∖{1}\sum_{i\in V}x_{ih,k-1}=\sum_{j\in V}x_{hjk}\quad\forall h\in C,\forall k\in K\setminus\{1\}

    • 到达终点只能一次。

    ∑i∈V∑k∈Kxi,m+1,k=1\sum_{i\in V}\sum_{k\in K}x_{i,m+1,k}=1

    • 硬时间窗约束。

    ai≤sik≤bi∀i∈V,∀k∈Ka_i\leq s_{ik}\leq b_i\quad\forall i\in V,\forall k\in K

    • 车辆的行驶时间约束。

    sik+tij≤sjk+Mij(1−xijk)∀i∈V,∀j∈V,∀k∈Ks_{ik}+t_{ij}\leq s_{jk}+M_{ij}(1-x_{ijk})\quad\forall i\in V,\forall j\in V,\forall k\in K

    • 变量值域。

    xijk∈{0,1}∀i∈V,∀j∈V,∀k∈Kx_{ijk}\in\{0,1\}\quad\forall i\in V,\forall j\in V,\forall k\in K

    • 任何节点都不能是自己的前继或者后继节点。

    xiik=0∀i∈V,∀k∈Kx_{iik}=0\quad\forall i\in V,\forall k\in K

    • 不能存在两条下标（index）一样的弧。

    ∑i∈v∑j∈Vxijk≤1∀k∈K\sum_{i\in v}\sum_{j\in V}x_{ijk}\leq1\quad\forall k\in K

    • 节点m+1m+1不能有后继节点。

    ∑i∈V∑k∈Kxm+1,j,k=0\sum_{i\in V}\sum_{k\in K}x_{m+1,j,k}=0

    • 节点0不能有前继节点。

    ∑i∈V∑k∈Kxi0k=0\sum_{i\in V}\sum_{k\in K}x_{i0k}=0

    • 服务开始时刻必须是单调递增的。

    si,k−1≤sik∀i∈V,∀k∈K∖{1}s_{i,k-1}\leq s_{ik}\quad\forall i\in V,\forall k\in K\setminus\{1\}

[^1]: Desrochers, M., Desrosiers, J., and Solomon, M. (1992). A new optimization algorithm for the vehicle routing problem with time windows. Operations Research, 40:342-354.

[^2]: Desaulniers, Guy, Jacques Desrosiers, and Marius M. Solomon, eds. Column generation. Vol. 5. Springer Science & Business Media, 2006.