Exact and heuristic solution of the consistent vehicle-routing problem

Dominik Goeke*, Roberto Roberti, Michael Schneider

*Corresponding author for this work

Research output: Contribution to JournalArticleAcademicpeer-review

363 Downloads (Pure)


Providing consistent service by satisfying customer demands with the same driver (driver consistency) at approximately the same time (arrival-time consistency) allows companies in last-mile distribution to stand out among competitors. The consistent vehicle-routing problem (ConVRP) is a multiday problem addressing such consistency requirements along with traditional constraints on vehicle capacity and route duration. The literature offers several heuristics but no exact method for this problem. The state-of-the-art exact technique to solve VRPs-column generation (CG) applied to route-based formulations in which columns are generated via dynamic programming-cannot be successfully extended to the ConVRP because the linear relaxation of route-based formulations is weak. We propose the first exact method for the ConVRP, which can solve medium-sized instances with five days and 30 customers. The method solves, via CG, a formulation in which each variable represents the set of routes assigned to a vehicle over the planning horizon. As an upper bounding procedure, we develop a large neighborhood search (LNS) featuring a repair procedure specifically designed to improve the arrival-time consistency of solutions. Used as stand-alone heuristic, the LNS is able to significantly improve the solution quality on benchmark instances from the literature compared with state-of-the-art heuristics.

Original languageEnglish
Pages (from-to)1023-1042
Number of pages20
JournalTransportation Science
Issue number4
Early online date28 Jun 2019
Publication statusPublished - Jul 2019


  • Column generation
  • Consistent vehicle routing problems
  • Customer service
  • Large neighborhood search


Dive into the research topics of 'Exact and heuristic solution of the consistent vehicle-routing problem'. Together they form a unique fingerprint.

Cite this