New compact integer programming formulations for the multi-trip vehicle routing problem with time windows. (June 2020)

• Record Type: Journal Article
• Authors: Neira, Daniel A.; Aguayo, Maichel M.; De la Fuente, Rodrigo; Klapp, Mathias A.
• Is Part Of: Computers & industrial engineering. Volume 144(2020)
• Publication Date: 2020-06
• Subjects: IP -- Vehicle routing -- Multi-trip -- Time windows -- Compact formulations; Engineering -- Data processing -- Periodicals; Industrial engineering -- Periodicals; 620.00285
• DOI: 10.1016/j.cie.2020.106399
• Languages: English
• ISSNs: 0360-8352

Abstract

Highlights: Two-index compact models for the MTVRPTW-SDLT and MTVRPTW-SD are introduced. Compact models outperform existing formulations reported in the literature. Models for the MTVRPTW-SD are competitive with existing branch-and-price approaches. Model can be easily implemented in any available off-the-shelf optimization software. 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.