This paper presents a branch-And-price-And-cut 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 objective is to minimize aweighted sum of the total distance traveled, the total completion time of the routes, and the number of unserved requests. To this end, the problem supports a flexible coupling and decoupling of active and passive vehicles at customer locations. Accordingly, the operations of the vehicles have to be synchronized carefully in the planning. The contribution of the paper is twofold: First, we present an exact branch-And-price-And-cut 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 nontrivial 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. Second, 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, four active, and eight passive vehicles to optimality within two hours of CPU time.

Branch-and-Price-and-Cut for the Active-Passive Vehicle-Routing Problem / C. Tilk, N. Bianchessi, M. Drexl, S. Irnich, F. Meisel. - In: TRANSPORTATION SCIENCE. - ISSN 0041-1655. - 52:2(2018), pp. 300-319. [10.1287/trsc.2016.0730]

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

N. Bianchessi;
2018

Abstract

This paper presents a branch-And-price-And-cut 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 objective is to minimize aweighted sum of the total distance traveled, the total completion time of the routes, and the number of unserved requests. To this end, the problem supports a flexible coupling and decoupling of active and passive vehicles at customer locations. Accordingly, the operations of the vehicles have to be synchronized carefully in the planning. The contribution of the paper is twofold: First, we present an exact branch-And-price-And-cut 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 nontrivial 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. Second, 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, four active, and eight passive vehicles to optimality within two hours of CPU time.
Vehicle-routing; Synchronization; Branch-And-price; Linear vertex costs;
Settore MAT/09 - Ricerca Operativa
2018
https://pubsonline.informs.org/doi/pdf/10.1287/trsc.2016.0730
Article (author)
File in questo prodotto:
File Dimensione Formato  
TheActivePassiveVehicleRoutingProblem.pdf

accesso aperto

Tipologia: Post-print, accepted manuscript ecc. (versione accettata dall'editore)
Dimensione 522.22 kB
Formato Adobe PDF
522.22 kB Adobe PDF Visualizza/Apri
trsc.2016.0730.pdf

accesso riservato

Tipologia: Publisher's version/PDF
Dimensione 421.04 kB
Formato Adobe PDF
421.04 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2434/609876
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 36
  • ???jsp.display-item.citation.isi??? 30
social impact