New compact integer programming formulations for the multi-trip vehicle routing problem with time windows

Abstract

We study two integer programming (IP) models for the multi-trip vehicle routing problem with time windows, service-dependent loading times, and limited trip duration (MTVRPTW-SDLT). Our first two-index formulation model represents vehicle returns to the depot in a graph with multiple copies of the depot node. The second two-index formulation model has just one depot node per vehicle, but includes a parallel arc for each pair of customer nodes representing an intermediate vehicle return to the depot. We compare these formulations against three-index formulations available in the literature over a set of benchmark instances. Results show that our models outperform existing formulations. We also adapt the proposed formulations for a relaxation of the MTVRPTW-SDLT without trip duration limit (LT). Our computational results also suggest that our models also improve their performance on MTVRPTW-SD instances.