Aarhus University Seal / Aarhus Universitets segl

A Branch-and-Cut Algorithm for the Capacitated Open Vehicle Routing Problem

Research output: Working paperResearch


  • L 2006 06

    Final published version, 260 KB, PDF document

  • Adam N. Letchford, Lancaster University, United Kingdom
  • Jens Lysgaard
  • Richard W. Eglese, Lancaster University, United Kingdom
  • Department of Business Studies
  • CORAL - Centre for Operations Research Applications in Logistics
In open vehicle routing problems, the vehicles are not required to return to the depot after completing service. In this paper, we present the first exact optimization algorithm for the open version of the well-known capacitated vehicle routing problem (CVRP). The algorithm is based on branch-and-cut. We show that, even though the open CVRP initially looks like a minor variation of the standard CVRP, the integer programming formulation and cutting planes need to be modified in subtle ways. Computational results are given for several standard test instances, which enables us for the first time to assess the quality of existing heuristic methods, and to compare the relative difficulty of open and closed versions of the same problem.
Original languageEnglish
Place of publicationAarhus
PublisherAarhus School of Business, Department of Business Studies
Number of pages24
ISBN (Electronic)8778821231
Publication statusPublished - 2006

    Research areas

  • vehicle routing, branch-and-cut, separation

See relations at Aarhus University Citationformats

Download statistics

No data available

ID: 32345528