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

Ann-Kathrin Rothenbächer ()
Additional contact information
Ann-Kathrin Rothenbächer: Johannes Gutenberg-University Mainz, Germany

No 1714, Working Papers from Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz

Abstract: 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, we permit all kinds of schedule structures and the choice of the service frequency. We 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 half-way points within bidirectional labeling. For instances whose schedule sets fulfill a certain symmetry condition, we 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 our algorithm. Furthermore, we analyze the impact of different schedule structures on run times and objective function values.

Keywords: Vehicle Routing; Multi Period; Branch-and-Price-and-Cut; Service Choice; Flexible Schedules (search for similar items in EconPapers)
Pages: 20 pages
Date: 2017-08-10
New Economics Papers: this item is included in nep-cmp, nep-mkt and nep-tre
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://download.uni-mainz.de/RePEc/pdf/Discussion_Paper_1714.pdf First version, 2017 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:jgu:wpaper:1714

Access Statistics for this paper

More papers in Working Papers from Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz Contact information at EDIRC.
Bibliographic data for series maintained by Research Unit IPP ().