带时间窗的电动车辆路径规划问题

发表于 分类于

带时间窗的电动车辆路径规划问题（Electric Vehicle Routing Problem with Time Windows, EVRPTW）的问题描述如下：区域内存在一个车场或配送中心，一个或多个充电站以及若干个客户，每个客户都有明确的服务需求和服务时间窗口，且服务时间已知。车辆的行驶过程需要保证电量、时间、货物容量上的可行性。配送中心或车场需要派出车队并且为其设计合适的配送方案，使其以最小的总行驶成本完成所有的客户的货物配送需求。

为了简化问题，我们做出了如下假设：

  1. 只考虑一个充电站。
  2. 时间窗为硬时间窗。
  3. 电动车从配送中心出发时为满电量状态。
  4. 电动车的充电速率是线性的， 每次充电都充满。

为便于理解，下图展示了一个EVRPTW的示例，其中包含了3辆电动车，10个客户点以及1个充电站。3辆电动车的行驶路径及其电量状态（State Of Charge, SOC）如下：

  • 电动车1：配送中心(100%) →\rightarrow 4(60%) →\rightarrow (45%)充电站(100%) →\rightarrow 3(90%) →\rightarrow 2(70%) →\rightarrow 1(45%)→\rightarrow配送中心(45%)。
  • 电动车2：配送中心(100%) →\rightarrow 7(55%) →\rightarrow 6(20%) →\rightarrow (5%)充电站(100%) →\rightarrow 5(70%) →\rightarrow 配送中心(35%)。
  • 电动车3：配送中心(100%) →\rightarrow 10(75%) →\rightarrow 9(60%) →\rightarrow 8(40%)→\rightarrow 配送中心(10%)。

EVRPTW示例

符号

给定有向图G=(V,A)\mathcal{G}=(\mathcal{V}, \mathcal{A})，V=C∪{o,d}∪r\mathcal{V}=\mathcal{C}\cup\{o,d\}\cup{r}，是图中的点集，包括了客户点集C\mathcal{C}，配送中心点oo及其复制配送中心点dd，充电站点rr；A={(i,j)∣∀i,j∈V,i≠j}\mathcal{A}=\{(i,j)|\forall i,j\in\mathcal{V}, i\neq j\}, 是图中的边集。客户ii的需求为qiq_i，服务时间为lil_i，服务时间窗为[ai,bi][a_i,b_i]。弧(i,j)(i,j)的行驶时间为TijT_{ij},行驶成本为cijc_{ij}。电动车的充电速率gg是线性的。假设电动车的电量状态为[0[0%,100%]，且其电量消耗是与行驶距离成正比函数。为了刻画不同电动车到达同一个充电站rr的剩余电量和充电时间段的不一致，我们将充电站rr复制多个(每一个的坐标相同，仅编号不一样)，使用R\mathcal{R}来表示所有复制点的点集。将图G\mathcal{G}的点集更新为V=C∪{o,d}∪R\mathcal{V}=\mathcal{C}\cup\{o,d\}\cup{\mathcal{R}}。需要注意的是复制的数量不宜过多，否则会出现对称性，即访问不同得到复制点但是对应的解实际上是一样的。理论上最差是每辆车访问一个客户后就必须充电，需要复制∣C∣∣K∣|\mathcal{C}||\mathcal{K}|个充电站。

问题建模

  • 决策变量：
    • xijx_{ij}表示从客户点ii到客户点jj的行驶路径，取值为0或1，0表示不选择该路径，1表示选择该路径。
    • tit_i表示客户点ii的访问时间。
    • uiu_i表示到达客户点ii的剩余容量。
  • 目标函数：最小化总行驶成本。
    min⁡∑i,j∈Vcijxij\min \sum_{i,j\in\mathcal{V}}c_{ij}x_{ij}
  • 约束条件：
    • 每个客户都必须被一辆车访问一次。
      ∑j∈Vxij=1,∀i∈C\sum_{j\in\mathcal{V}}x_{ij}=1,\forall i\in\mathcal{C}
    • 车辆必须重配送中心出发，最后返回配送中心。
      ∑j∈Vxoj−∑j∈Vxid=0\sum_{j\in\mathcal{V}}x_{oj} - \sum_{j\in\mathcal{V}}x_{id}=0
    • 对于每个客户点离开的车数量必须等于进入的该客户点数量， 即车辆的流平衡约束。
      ∑i∈Vxij−∑j∈Vxji=0,∀j∈C∪R\sum_{i\in\mathcal{V}}x_{ij} - \sum_{j\in\mathcal{V}}x_{ji}=0,\forall j\in\mathcal{C}\cup\mathcal{R}
    • 车辆的容量约束。
      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∈C∪o,j∈Vt_i + l_i + T_{ij} - t_j \leq M(1-x_{ij}), \forall i\in\mathcal{C}\cup{o}, j\in\mathcal{V}
      • 存在充电过程的弧：
        当电动车访问以充电站为起点的弧，表明电动车进行了充电。为了对电动车的电量状态进行建模，需要记录电动车到达客户点的SOC的决策变量。引入非负变量yiy_i表示电动车到达点ii时已消耗的电量，且yi∈[0,1]y_i\in[0,1], 那么到达客户点的剩余电量为1−yi1-y_i。电动车的充电时间约束为：
        ti+gyi+Tij−tj≤M(1−xij),∀i∈R,j∈C∪dt_i + gy_i + T_{ij} - t_j \leq M(1-x_{ij}), \forall i\in\mathcal{R}, j\in\mathcal{C}\cup{d},
        其中gyigy_i表示充满电的时间。
    • 行驶过程中的电量约束：用参数EijE_{ij}表示电动车在弧(i,j)(i,j)行驶过程中的电量消耗。

      • 以配送中心或者充电站点为起点的弧(i,j),i∈{o}∪R,j∈C∪{d}(i,j), i \in \{o\}\cup\mathcal{R}, j \in \mathcal{C}\cup\{d\}, 电动车到达点jj时已消耗的电量为EijE_{ij},那么yj=yi+Eij=0+Eij=Eijy_j = y_i + E_{ij} = 0 + E_{ij} = E_{ij}。

        Eij−yj≤M(1−xij),∀i∈{o}∪R,j∈VE_{ij} - y_j \leq M(1-x_{ij}), \forall i \in \{o\}\cup\mathcal{R}, j \in \mathcal{V}

      • 以客户点为起点的弧(i,j),i∈C,j∈V(i,j), i \in \mathcal{C}, j \in \mathcal{V}, xij=1x_{ij}=1, 那么yj=yi+Eijy_j = y_i + E_{ij}。
        yi+Eij−yj≤M(1−xij),∀i∈C,j∈Vy_i + E_{ij} - y_j \leq M(1-x_{ij}), \forall i \in \mathcal{C}, j \in \mathcal{V}

完整的EVRPTW数学模型如下：

min⁡∑i,j∈Vcijxijs.t.∑j∈Vxij=1,∀i∈C∑j∈Vxoj−∑j∈Vxid=0∑i∈Vxij−∑j∈Vxji=0,∀j∈C∪Rui+qi−uj≤M(1−xij),∀(i,j)∈Ati+li+Tij−tj≤M(1−xij),∀i∈C∪o,j∈Vti+gyi+Tij−tj≤M(1−xij),∀i∈R,j∈C∪dEij−yj≤M(1−xij),∀i∈{o}∪R,j∈Vyi+Eij−yj≤M(1−xij),∀i∈C,j∈Vai≤ti≤bi,∀i∈C0≤ui≤Q,∀i∈V0≤yi≤1,∀i∈Vxij∈{0,1},∀(i,j)∈A\begin{aligned} \min &\sum_{i,j\in\mathcal{V}}c_{ij}x_{ij} \\ \text{s.t.} &\sum_{j\in\mathcal{V}}x_{ij}=1,&\forall i\in\mathcal{C}\\ & \sum_{j\in\mathcal{V}}x_{oj} - \sum_{j\in\mathcal{V}}x_{id}=0\\ &\sum_{i\in\mathcal{V}}x_{ij} - \sum_{j\in\mathcal{V}}x_{ji}=0,&\forall j\in\mathcal{C}\cup\mathcal{R}\\ & u_i+q_i-u_j\leq M(1-x_{ij}), &\forall (i,j)\in\mathcal{A}\\ &t_i + l_i + T_{ij} - t_j \leq M(1-x_{ij}), &\forall i\in\mathcal{C}\cup{o}, j\in\mathcal{V} \\ &t_i + gy_i + T_{ij} - t_j \leq M(1-x_{ij}), &\forall i\in\mathcal{R}, j\in\mathcal{C}\cup{d}\\ &E_{ij} - y_j \leq M(1-x_{ij}), &\forall i \in \{o\}\cup\mathcal{R}, j \in \mathcal{V}\\ &y_i + E_{ij} - y_j \leq M(1-x_{ij}), &\forall i \in \mathcal{C}, j \in \mathcal{V}\\ &a_i \leq t_i \leq b_i, &\forall i \in \mathcal{C}\\ &0 \leq u_i \leq Q, &\forall i \in \mathcal{V}\\ &0\leq y_i \leq 1, &\forall i \in \mathcal{V}\\ &x_{ij} \in \{0,1\}, &\forall (i,j)\in\mathcal{A} \end{aligned}