EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

3165. A Unified Exact Approach for a Broad Class of Vehicle Routing Problems With Simultaneous Pickup and Delivery

Invited abstract in session WA-58: MILPs for Vehicle Routing 2, stream VeRoLog - Vehicle Routing and Logistics.

Wednesday, 8:30-10:00
Room: S07 (building: 101)

Authors (first author is the speaker)

1. Teobaldo Bulhões
Universidade Federal da Paraíba
2. Rafael Praxedes
Department of Engineering and Architecture, University of Parma
3. Anand Subramanian
Universidade Federal da Paraíba
4. Eduardo Uchoa
Engenharia de Produção, Universidade Federal Fluminense

Abstract

The vehicle routing problem with simultaneous pickup and delivery (VRPSPD) is a well-known combinatorial optimization problem. It involves finding the least-cost set of routes, starting and ending at the depot, while simultaneously satisfying pickup and delivery demands from multiple locations within a single trip without exceeding the capacity of the vehicle. There are many variants of this problem, each one incorporating additional attributes such as a heterogeneous fleet of vehicles, time constraints, route duration, multiple depots, and decisions regarding depot location. In this work, we propose a unified formulation for ten of these variants, which were considered special cases of a generic problem denoted as heterogeneous location routing problem with simultaneous pickup and delivery and time windows (HLRPSPDTW). To solve it, we developed a branch-cut-and-price (BCP) algorithm and validated it through extensive computational experiments on more than 530 benchmark instances. The proposed BCP algorithm successfully found optimal solutions for 44.3% of unsolved problems, attained 92.6% of known optima, and improved lower bounds for 69.9% of the instances that remained unsolved.

Keywords

Status: accepted

Back to the list of papers