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

Christian Tilk, Nicola Bianchessi, Michael Drexl, Stefan Irnich, Frank Meisel

Research output: Contribution to JournalArticleAcademicpeer-review

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 flexible 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 first 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 different transport tasks necessary to fulfill 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 first 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.
Original languageEnglish
Pages (from-to)300-319
Number of pages20
JournalTransportation Science
Volume52
Issue number2
DOIs
Publication statusPublished - Apr 2018
Externally publishedYes

Bibliographical note

Published Online:21 Jun 2017

Keywords

  • Branch-And-price
  • Linear vertex costs
  • Synchronization
  • Vehicle-routing

Fingerprint Dive into the research topics of 'Branch-and-Price-and-Cut for the Active-Passive Vehicle-Routing Problem'. Together they form a unique fingerprint.

  • Cite this

    Tilk, C., Bianchessi, N., Drexl, M., Irnich, S., & Meisel, F. (2018). Branch-and-Price-and-Cut for the Active-Passive Vehicle-Routing Problem. Transportation Science, 52(2), 300-319. https://doi.org/10.1287/trsc.2016.0730