Branch-and-Price for the Active-Passive Vehicle-Routing Problem

Christian Tilk (), Nicola Bianchessi (), Michael Drexl (), Stefan Irnich () and Frank Meisel ()
Additional contact information
Christian Tilk: Johannes Gutenberg University Mainz
Nicola Bianchessi: Johannes Gutenberg University Mainz, University of Brescia
Michael Drexl: Johannes Gutenberg University Mainz, Fraunhofer Centre for Applied Research on Supply Chain Services SCS Nuremberg
Stefan Irnich: Johannes Gutenberg University Mainz
Frank Meisel: University Kiel

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

Abstract: This paper presents a branch-and-price algorithm for the exact solution of the active-passive vehicle-routing problem (APVRP). The APVRP covers a range of logistics applications where pickup-and-delivery requests necessitate a joint operation of active vehicles (e.g., trucks) and passive vehicles (e.g., loading devices such as containers or swap bodies). The problem supports a ?exible coupling and decoupling of active and passive vehicles at customer locations in order to achieve a high utilization of both resources. Accordingly, the operations of the vehicles have to be synchronized carefully in the planning. The contribution of the paper is twofold: Firstly, we present an exact branch-and-price algorithm for this class of routing problems with synchronization constraints. To our knowledge, this algorithm is the ?rst such approach that considers explicitly the temporal interdependencies between active and passive vehicles. The algorithm is based on a non-trivial network representation that models the logical relationships between the di?erent transport tasks necessary to ful?ll a request as well as the synchronization of the movements of active and passive vehicles. Secondly, we contribute to the development of branch-and-price methods in general, in that we solve, for the ?rst time, an ng-path relaxation of a pricing problem with linear vertex costs by means of a bidirectional labeling algorithm. Computational experiments show that the proposed algorithm delivers improved bounds and solutions for a number of APVRP benchmark instances. It is able to solve instances with up to 76 tasks, 4 active, and 8 passive vehicles to optimality within two hours of CPU time.

Keywords: Vehicle-routing; Synchronization; Branch-and-price; Linear vertex costs (search for similar items in EconPapers)
Pages: 24 pages
Date: 2015-09-17
New Economics Papers: this item is included in nep-cmp 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_1513.pdf First version, 2015 (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:1513

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 ().