23rd Conference of the International Federation of Operational Research Societies
Abstract Submission

781. A route relaxation based on the spatial aggregation of nodes for the generalized vehicle routing problem

Invited abstract in session TE-29: Last Mile Delivery, cluster Location, Network Design, and Routing.

Tuesday, 16:15-17:45
Room: FENH302

Authors (first author is the speaker)

1. Claudio Contardo
Concordia University
2. Matthieu Gruson
Logistics and Operations Management, HEC Montréal
3. Francois Lamothe
DISC, ISAE-Supaero
4. Rafael Martinelli
Industrial Engineering, Pontifícia Universidade Católica do Rio de Janeiro (PUC-Rio)

Abstract

We consider the generalized vehicle routing problem (GVRP), an extension of the classical capacitated vehicle routing problem (CVRP), where customer nodes are clustered and exactly one node in each cluster must be visited by one vehicle, at minimum total cost, while respecting the vehicle capacities. We consider a route relaxation for the GVRP aggregating nodes belonging to the same cluster, using a spatial criterion in a dynamic way. The relaxation, when embedded within a column generation solver, triggers a decrease in the computational complexity associated with the pricing subproblem. The proposed route relaxation copes well with several other state-of-the-art techniques for the GVRP, such as cutting planes and branching. As a result, problems with dense clusters can now be solved to proven optimality much faster when compared to a classical pricing mechanism.

Keywords

Status: accepted

Back to the list of papers