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

Heuristics for Rich VRP Models

Geir Hasle

In basic and applied research in transportation optimization, there is now a trend towards formulating and solving richer models. This trend partly originates from external requirements of tool vendors and end users, but also from forces within the scientific community. Idealized models of hard OR problems (e.g. the CVRP) that have been studied extensively over the past 4-5 decades are, despite their computational complexity, regarded as solved from a pragmatic point of view. This fact, together with recent methodological advances and the general increase in computing power, has motivated a shift to novel, scientifically often more challenging, and industrially more adequate problem formulations.

The talk will focus on a specific, generic VRP solver, but also touch upon some general issues, and relate to work by others. The underlying conceptual VRP model will be presented. A heuristic framework based on Variable Neighborhood Search, Large Neighborhood Search, and the Guided Local Search meta-heuristic will be described. Ongoing work on improvement of heuristics for rich VRPs will be presented, including:

  • informed construction of initial solutions;
  • definition of focused neighborhoods;
  • filtering techniques;
  • simple learning techniques.

Preliminary computational results on standard benchmarks will be presented.