We study the class of one-to-many-to-one single vehicle routing problems with pickups and deliveries, in which a single capacitated vehicle is used to serve a set of customers requiring a delivery, a pickup, or both. These problems have many real-world applications, including beverage distribution, courier service transportation, and reverse logistics. We first concentrate on a well-studied problem in this class, known as the single vehicle routing problem with deliveries and selective pickups (SVRPDSP), in which deliveries are mandatory but pickups are optional and generate a revenue if performed, and customers requiring both a delivery and a pickup (combined demand) can be visited either once or twice. Most exact algorithms in the literature solve SVRPDSP by looking for Elementary tours on an extended network which is obtained by transforming each combined demand customer into two different customers, one requiring only the delivery and the other one only the pickup. Because this can result in a significant loss in performance, in this work we focus instead on the original problem network and present formulations that can yield non-Elementary tours. Through the use of Benders Decomposition, valid inequalities, and tailored optimization techniques based on branch-and-cut frameworks, we develop exact algorithms that outmatch previous results in the literature and obtain proven optimal solutions for all benchmark instances. We then generalize the algorithms to solve several other vehicle routing problems with pickups and deliveries, including the cases of split deliveries, intermediate dropoffs, mandatory pickups, and multiple vehicles.

Non-Elementary Formulations for Single Vehicle Routing Problems with Pickups and Deliveries / Bruck, Bruno; Iori, Manuel. - In: OPERATIONS RESEARCH. - ISSN 1526-5463. - 65:6(2017), pp. 1597-1614. [10.1287/opre.2017.1639]

Non-Elementary Formulations for Single Vehicle Routing Problems with Pickups and Deliveries

IORI, MANUEL
2017

Abstract

We study the class of one-to-many-to-one single vehicle routing problems with pickups and deliveries, in which a single capacitated vehicle is used to serve a set of customers requiring a delivery, a pickup, or both. These problems have many real-world applications, including beverage distribution, courier service transportation, and reverse logistics. We first concentrate on a well-studied problem in this class, known as the single vehicle routing problem with deliveries and selective pickups (SVRPDSP), in which deliveries are mandatory but pickups are optional and generate a revenue if performed, and customers requiring both a delivery and a pickup (combined demand) can be visited either once or twice. Most exact algorithms in the literature solve SVRPDSP by looking for Elementary tours on an extended network which is obtained by transforming each combined demand customer into two different customers, one requiring only the delivery and the other one only the pickup. Because this can result in a significant loss in performance, in this work we focus instead on the original problem network and present formulations that can yield non-Elementary tours. Through the use of Benders Decomposition, valid inequalities, and tailored optimization techniques based on branch-and-cut frameworks, we develop exact algorithms that outmatch previous results in the literature and obtain proven optimal solutions for all benchmark instances. We then generalize the algorithms to solve several other vehicle routing problems with pickups and deliveries, including the cases of split deliveries, intermediate dropoffs, mandatory pickups, and multiple vehicles.
8-set-2017
65
6
1597
1614
Non-Elementary Formulations for Single Vehicle Routing Problems with Pickups and Deliveries / Bruck, Bruno; Iori, Manuel. - In: OPERATIONS RESEARCH. - ISSN 1526-5463. - 65:6(2017), pp. 1597-1614. [10.1287/opre.2017.1639]
Bruck, Bruno; Iori, Manuel
File in questo prodotto:
File Dimensione Formato  
SVRPDSP_MAIN_BODY.pdf

embargo fino al 06/12/2017

Descrizione: Articolo principale
Tipologia: Post-print dell'autore (bozza post referaggio)
Dimensione 550.58 kB
Formato Adobe PDF
550.58 kB Adobe PDF Visualizza/Apri
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

Licenza Creative Commons
I metadati presenti in IRIS UNIMORE sono rilasciati con licenza Creative Commons CC0 1.0 Universal, mentre i file delle pubblicazioni sono rilasciati con licenza Attribuzione 4.0 Internazionale (CC BY 4.0), salvo diversa indicazione.
In caso di violazione di copyright, contattare Supporto Iris

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