The Multi-trip Vehicle Routing Problem with Time Windows (MTVRPTW) generalizes the well-known Capacitated Vehicle Routing Problem (CVRP) in that vehicles can perform more than one trip within a maximum shift length but must comply customer time windows.
The MTVRPTW has recently got the attention of scholars due to its applications to city logistics. A Branch & Price approach is proposed in [1], while [2] tackles a variant with limited trip duration.
We propose a three-index MILP formulation for the MTVRPTW that makes use of base and replenishment arcs. The former model the direct connection between two nodes, while the latter imply a reload operation in between two clients. Base and replenishment arc variables are vehicle-indexed. Replenishment arcs allow to represent a journey as an elementary path and thus to ensure connectivity by separating SECs on a transformation of the graph. Further sets of two-indexed variables allow to impose time windows, shift length, and service-dependent loading time constraints.
The use of classical capacity constraints to enforce the load limit on vehicles leads to a Branch & Cut algorithm. Capacity constraints are then strengthened after branching decisions to exploit some properties of the vehicle index.
Preliminary tests have been conducted, with promising results.
[1] F.Hernandez, D.Feillet, R.Giroudeau, O.Naud, "Branch-and-price algorithms for the solution of the multi-trip vehicle routing problem with time windows." EJOR, 249(2):551-559, 2016.
[2] F.Hernandez, D.Feillet, R.Giroudeau, O.Naud, "A new exact algorithm to solve the multi-trip vehicle routing problem with time windows and limited duration." 4OR, 12:235-259, 2014.
| Subject : | : | Abstracts |
| Topics | : | City Logistics |
| Topics | : | Exact methods |
| Topics | : | Vehicle routing with time windows |
| PDF version | : |  PDF version |
