Branch-and-Price-and-Cut for the Periodic Vehicle Routing Problem with Flexible Schedule Structures

This paper addresses the periodic vehicle routing problem with time windows (PVRPTW). Therein, customers require one or several visits during a planning horizon of several periods. The possible visiting patterns (schedules) per customer are limited. In the classical PVRPTW, it is common to assume that each customer requires a specific visit frequency and offers all corresponding schedules with regular intervals between the visits. In this paper, the authors permit all kinds of schedule structures and the choice of the service frequency. The authors present an exact branch-and-price-and-cut algorithm for the classical PVRPTW and its variant with flexible schedules. The pricing problems are elementary shortest-path problems with resource constraints. They can be based on one of two new types of networks and solved with a labeling algorithm, which uses several known acceleration techniques, such as the ng-path relaxation and dynamic halfway points within bidirectional labeling. For instances in which schedule sets fulfill a certain symmetry condition, the authors present specialized improvements of the algorithm, such as constraint aggregation and symmetry breaking. Computational tests on benchmark instances for the PVRPTW show the effectiveness of the authors' algorithm. Furthermore, the authors analyze the impact of different schedule structures on run times and objective function values.The online appendix is available at

  • Record URL:
  • Availability:
  • Supplemental Notes:
    • Abstracts reprinted with permission of INFORMS (Institute for Operations Research and the Management Sciences,
  • Authors:
    • Rothenbächer, Ann-Kathrin
  • Publication Date: 2019-5


  • English

Media Info

Subject/Index Terms

Filing Info

  • Accession Number: 01714938
  • Record Type: Publication
  • Files: TRIS
  • Created Date: Jun 17 2019 3:36PM