EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

3205. On the Separation of Rank-1 Cuts in the VRPSolver Framework

Invited abstract in session MC-58: Column Generation for Vehicle Routing, stream VeRoLog - Vehicle Routing and Logistics.

Monday, 12:30-14:00
Room: S07 (building: 101)

Authors (first author is the speaker)

1. Eduardo Queiroga
Universidade Federal da Paraíba
2. Teobaldo Bulhões
Universidade Federal da Paraíba
3. Anand Subramanian
Universidade Federal da Paraíba
4. Eduardo Uchoa
Engenharia de Producao, UFF

Abstract

As one of the most extensively studied problems in operations research, the Vehicle Routing Problem (VRP) attracts considerable academic and practical interest. The state-of-the-art exact approaches for VRPs rely on the integration of cut and column generation within Branch-Cut-and-Price (BCP) algorithms. A critical component of modern BCP algorithms is the separation of non-robust cuts, such as rank-1 cuts with limited memory, which are considered strong but affect the structure of the pricing subproblem. In this research, we investigate algorithms for separating rank-1 cuts aimed at being both effective and efficient. The study involved implementing these algorithms within the VRPSolver BCP framework and comparing its performance against the existing local search-based separation method. Preliminary results of this study for the classic Capacitated Vehicle Routing Problem (CVRP) will be presented.

Keywords

Status: accepted

Back to the list of papers