带时间窗约束的车辆路径规划问题(VRPTW)

发表于 更新于 分类于 阅读次数： 本文字数： 695 阅读时长 ≈ 3 分钟
Mathematical formulation and integer programming approach for the Vehicle Routing Problem with Time Windows

带时间窗约束的VRP问题，即在满足约束条件的情况下，求解最短路径。

问题数学描述

假设有CC个客户点，编号从1到CC，所有的客户用集合C\mathcal{C}来表示。给定有向图G\mathcal{G}=(V,A)(\mathcal{V},\mathcal{A})，其中V=C∪{o,d}\mathcal{V}=\mathcal{C}\cup\{o,d\}为图中点集，包括客户集合C\mathcal{C}和车厂点oo及其复制点dd; A={(i,j)∣∀i,j∈V,i≠j}\mathcal{A}= \{(i, j)|\forall i,j\in\mathcal{V}, i\neq j\}为弧集, 表示图G\mathcal{G}中的所有弧。每一段弧(i,j)(i,j)的行驶成本为cijc_{ij}。每一个客户ii都有一个已知的需求qiq_i，以及时间窗[ai,bi][a_i, b_i]和服务时间lil_i，其中aia_i为客户ii的最早开始的服务时间，bib_i为客户ii的最晚开始的服务时间。除此之外，用TijT_{ij}来表示弧(i,j)(i,j)行驶时间。问题中的车辆均为同质的车辆，车辆的最大容量为QQ。

模型定义

决策变量

  • xij∈{0,1},∀(i,j)∈Ax_{ij}\in\{0, 1\}, \forall (i,j)\in \mathcal{A} 为弧(i,j)(i,j)的决策变量，取值为0或1，表示弧(i,j)(i,j)是否被选中。
  • ti≥0，∀i∈Vt_i\geq 0， \forall i \in \mathcal{V} 表示车辆到达点ii的时间。
  • ui≥0，∀i∈Vu_i\geq 0， \forall i \in \mathcal{V} 表示车辆到达点ii的剩余容量。

目标函数

最小化总的行驶成本：

min⁡∑i,j∈Acijxij \min \sum_{i,j\in\mathcal{A}} c_{ij}x_{ij}

约束

  • 离开客户的车辆数目必须为1：
    ∑j∈Vxij=1,∀i∈C \sum_{j\in\mathcal{V}}x_{ij}=1, \forall i\in\mathcal{C}
  • 进出入车厂的数量必须相等, 车厂的流平衡约束：
    ∑j∈Vxoj−∑i∈Vxid=0 \sum_{j\in\mathcal{V}}x_{oj} - \sum_{i\in\mathcal{V}}x_{id} = 0
  • 进出入客户的车的数量必须相等，客户点的流平衡约束：
    ∑i∈Vxij−∑i∈Vxji=0,∀j∈C\sum_{i\in\mathcal{V}}x_{ij} - \sum_{i\in\mathcal{V}}x_{ji} = 0, \forall j\in\mathcal{C}
  • 车辆的容量约束， (MTZ子回路消除)：
    ui+qi−uj≤M(1−xij),∀(i,j)∈Au_i + q_i - u_j \leq M(1-x_{ij}), \forall (i,j) \in \mathcal{A}
  • 车辆行驶时间约束：
    ti+li+Tij−tj≤M(1−xij),∀(i,j)∈At_i + l_i + T_{ij}- t_j \leq M(1-x_{ij}), \forall (i,j) \in \mathcal{A}
  • 客户时间窗约束：
    ai≤ti≤bi,∀i∈V a_i \leq t_i \leq b_i, \forall i \in \mathcal{V}
  • 车辆容量约束：
    0≤ui≤Q,∀i∈V0\leq u_i \leq Q, \forall i \in \mathcal{V}

    完整的VRPTW的数学优化模型如下：
    min⁡∑(i,j)∈Acijxijs.t.∑j∈Vxij=1,∀i∈C∑j∈Vxoj−∑i∈Vxid=0∑i∈Vxji−∑i∈Vxij=0,∀j∈Cui+qj−uj≤M(1−xij),∀(i,j)∈A, j∈Cti+li+Tij−tj≤M(1−xij),∀(i,j)∈Aai≤ti≤bi,∀i∈V0≤ui≤Q,∀i∈Vxij∈{0,1},∀(i,j)∈A \begin{align} \min & \quad \sum_{(i,j) \in \mathcal{A}} c_{ij} x_{ij} \\ \text{s.t.} & \quad \sum_{j \in \mathcal{V}} x_{ij} = 1, && \forall i \in \mathcal{C} \\ & \quad \sum_{j \in \mathcal{V}} x_{oj} - \sum_{i \in \mathcal{V}} x_{id} = 0 \\ & \quad \sum_{i \in \mathcal{V}} x_{ji} - \sum_{i \in \mathcal{V}} x_{ij} = 0, && \forall j \in \mathcal{C} \\ & \quad u_i + q_j - u_j \leq M(1 - x_{ij}), && \forall (i,j) \in \mathcal{A},\ j \in \mathcal{C} \\ & \quad t_i + l_i + T_{ij} - t_j \leq M(1 - x_{ij}), && \forall (i,j) \in \mathcal{A} \\ & \quad a_i \leq t_i \leq b_i, && \forall i \in \mathcal{V} \\ & \quad 0 \leq u_i \leq Q, && \forall i \in \mathcal{V} \\ & \quad x_{ij} \in \{0,1\}, && \forall (i,j) \in \mathcal{A} \end{align}