EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

1629. A Matheuristic for the Edge Set Vehicle Routing Problem With Time Windows and Variants

Invited abstract in session WC-64: Heuristics for Vehicle Routing 1, stream VeRoLog - Vehicle Routing and Logistics.

Wednesday, 12:30-14:00
Room: S16 (building: 101)

Authors (first author is the speaker)

1. Rossana Cavagnini
Chair of Computational Logistics, RWTH Aachen University

Abstract

To reduce emissions, traffic, and noise, municipalities and governments are imposing fees and toll schemes to logistic companies for accessing particular roads. Because such measures increase delivery costs, transportation companies have to consider them when planning routes. In this talk, we address the edge set vehicle routing problem with time windows (ESVRPTW) initially introduced by Reinhardt et al. (2016). The ESVRPTW is a generalization of the vehicle routing problem with time windows in which a fixed cost must be paid for accessing a set of edges.

We propose an improved formulation for the ESVRPTW, new variable fixing techniques, and new valid inequalities. We introduce a new variant of the ESVRPTW to represent urban contexts in which waiting at customers for the opening of their time windows is not allowed. To solve these problems, we present a matheuristic, called MS-LBM, that consists of a multi-start local descent framework that uses a local branching scheme.

In addition to its flexibility in solving all ESVRPTW variants addressed in this talk, MS-LBM provides high-quality solutions faster than a commercial optimization solver and finds new best-known solutions. With an extensive computational study, we derive insights into how allowing waiting at customers affects the edge-set activation and routing decisions depending on the type of infrastructure for which fixed costs must be paid.

Keywords

Status: accepted

Back to the list of papers