Multi-depot multi-trip vehicle routing problem with time windows: a perishable good case study.
Loading...
Date
2021
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Universidad de Concepción
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.
Description
Tesis presentada para optar al grado de Magíster en Ingeniería Industrial.
Keywords
Problema de Rutas de Vehículos, Programación (Matematicas), Transporte, Itinerario, Industria Innovación e Infraestructura