Groupe d’études et de recherche en analyse des décisions

Efficient heuristic pricing for vehicle routing problems

Rafael Martinelli Pontifícia Universidade Católica do Rio de Janeiro, Brésil

We consider the problem of finding columns of negative reduced costs within a column generation solver for Vehicle Routing Problems (VRPs). We propose efficient local search evaluators to handle the several features needed, including cycle-elimination constraints and limited-memory subset-row inequalities, in addition to classical structural constraints of most vehicle routing applications such as vehicle capacity and time windows. We embed these operators within a multi-start iterated local search heuristic and solve instances derived from two classical VRPs, namely the Capacitated VRP (CVRP) and the VRP with time windows (VRPTW).

Entrée gratuite.
Bienvenue à tous!