【VRP】类型总结和DVRP分析（一）

文章目录

- 1. 物流配送的类型
- 2. DVRP（dynamic VRP）的动态时间类型
- - 2.1 出现新顾客
  - 2.2 老顾客取消
  - 2.3 交通中断
  - 2.4 车辆抛锚
  - 2.5 解决：等价于HOVRP问题
- 3. 解决静态VRP的方法分支
- 4. DVCP的12个特点

1. 物流配送的类型

带距离约束的CVRP(Distance-Constrained VRP, DCVRP)
带时间窗的VRP（VRP with time windonws, VRPTW)
带回程取货的VRP（VRP with backhauls,VRPB）
多车场VRP（mult-depot VRP, MDVRP）
带随机需求的VRP(VRP with stochasitic demand ,VRPSD)
带模糊需求的VRP（VRP with fuzzy demand,VRPFD）
时间依赖性VRP(time-dependent VRP, TDVRP)
开放式VRP(open VRP, OVRP)
多车型车辆路径问题(heterogeneous fleet VRO,HFVRP)
带最后时间期限的车辆路径问题(VRP with times deadlines)

2. DVRP（dynamic VRP）的动态时间类型

在这里插入图片描述

2.1 出现新顾客

在这里插入图片描述等价于求解

$EventTime_i$ :第i次动态时间发生的时刻。 $t_0,t_{end}]$ ,且 $t_0=EventTime_0$
在时刻点 $EventTime_i$ 下出现了3个新顾客，即对应参数为 $n^i_{new}=3$

2.2 老顾客取消

在这里插入图片描述等价于求解

在时刻点 $EventTime_i$ 下2个顾客取消订单，即对应参数为 $n^i_{cancel}=2$

2.3 交通中断

在这里插入图片描述等价于求解为

在时刻点 $EventTime_i$ 下两个顾客见的道路拥堵严重，导致不能通行，即对应点间的距离 $d_{ij}$ 取值修改为足够大的数或为无穷大。

2.4 车辆抛锚

在这里插入图片描述等价于求解为

在时刻点 $EventTime_i$ 下配送车辆Vehicle1出现抛锚，该事件发生后 $V e hi c l e St a t u s [1] = 3$ ，将Vehicle1的服务的顾客集合 $CustomerSet_{i1}$ 中的元素确定为该集合中已服务完成的顾客，未服务顾客提出集合，并且该集合不再更新。

$V e hi c l e St a t u s [j]$ :表示配送车辆 $j$ 的状态数组，取值为0、1、2、3， 0表示未开始执行任务；1表示正在执行任务；2表示执行任务完成任务回到配送中心；3表示配送车辆已经抛锚。 $\leq j \leq NumofVehicle$

$CustomerSet_{ik}$ :表示在时刻点 $EventTime_i$ 下正要到达时，第 $k$ 辆车服务的顾客集合， $1\leq k \leq NumofVehicle$

2.5 解决：等价于HOVRP问题

上述4中情况均有正在执行任务的车辆，因此会等价于求解同一个问题，即多车型的开放车辆路径问题(Heterogeneous Fleet Open VRP, HOVRP)

????原因一：在时刻点 $EventTime_i$ 时刻有两类型车辆

正在执行任务的车辆最大容量有 $Q-Q_{ij}$ ，行驶的最大距离为 $L-L_{ij}$
配送中心的车辆最大容量为Q,行驶最大距离为L.

????原因二：开放车辆路径问题的特点是配送车辆完成任务后不一定回到配送中心，所以车辆的计划路径可能是一条路径，而不是一个简单圈。当前正在执行任务的车辆已离开配送中心，且被要求配送完成后回到配送中心，所以此时这些车辆的配送计划路线必定为一条路径，与HOVRP无异。

????转化方式

将当前正在执行任务的车辆 $j$ 所在位置虚拟为顾客，且需求量为车辆j在时刻点 $EventTime_i$ 下已服务顾客的需求之和 $Q_{ij}$ ,该需求顾客与配送中心的距离设定为车辆j在时刻点 $EventTime_i$ 下已行驶的距离之和 $L_{ij}$ ;
在执行任务的车辆j首先服务该对应的虚拟客户。

3. 解决静态VRP的方法分支