Multi-depot multi-trip vehicle routing problem with time windows: a perishable good case study.

Abstract

The Multi-Depot Multi-Trip Vehicle Routing Problem with Time Windows (MDMTVRPTW) stems from the problem faced by a bakery. First, it is necessary to analyze one of its components, namely, the vehicle routing problem with release dates. The vehicle routing problem with release dates (VRP-Rd) is a variant of the classic vehicle routing problem in which each customers order has a release date indicating the earliest time when the order is available at the depot for delivery. Hence, customers orders are loaded into vehicles after their release dates, denoting a quite common problem that arises in city logistics and last-mile distribution. In this work, we present a novel two-index compact formulation and lifted inequalities for VRP-Rd. The proposed formulation are compared, with and without lifted inequalities, against two existing compact formulations and a state-of-the-art algorithm reported in the literature, over a set of well-known benchmark instances. The results demonstrate that both variations of the proposed model outperform existing formulations, and they are competitive in terms of solutions quality with those obtained by the state-of-the-art algorithm. Additionally, a deep analysis is carried out to accelerate the optimization and improvement schemes are tested. Finally, it is worthy of highlighting that the resulting lifted formulation can be solved efficiently by commercial software without complicated algorithmic implementations.