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

Christian Tilk () and Michael Forbes ()
Additional contact information
Christian Tilk: Johannes Gutenberg University Mainz
Michael Forbes: The University of Queensland St Lucia

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

Abstract: This paper studies the active-passive vehicle-routing problem (APVRP).The APVRP coversarange 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). It supports a flexible coupling and decoupling of active and passive vehicles at customer locations in order to achieve a high utilization of both resources. This flexibility raises the need to synchronize the operations and the movements of active and passive vehicles in time and space. The contribution of the paper is twofold. First, we present a branch-and-cut algorithm for the exact solution of the APVRP that is based on Benders decomposition. Second, our approach can be generalized to deal with other vehicle-routing problems with timing aspects and synchronization constraints. Especially for the more complicated cases in which completion time or duration of routes is part of the objective, we show how stronger optimality cuts can be defined by identifying minimal responsible subset. Computational experiments show that the proposed algorithm outperforms the previousstate-of-the-artfortheAPVRPandcomputeoptimalsolutionsformorethan70previously unsolved benchmark instances.

Keywords: Routing; synchronization; branch-and-cut; Benders decomposition; truck and trailer (search for similar items in EconPapers)
Pages: 24 pages
Date: 2019-12-09
New Economics Papers: this item is included in nep-cmp, nep-tre and nep-ure
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://download.uni-mainz.de/RePEc/pdf/Discussion_Paper_1915.pdf First version, 2019 (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:1915

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