In this paper we address a Pickup and Delivery Vehicle Routing Problem where the demands of both pickup and delivery nodes can be split between several vehicles. We investigate a new formulation where the route of each vehicle is decomposed into a sequence of simpler substructures called clusters, mitigating the combinatorial explosion of feasible solutions. We implement a branch-and-price algorithm exploiting column generation procedures that dynamically generates clusters to obtain improved dual bounds, and ad hoc branching strategies to achieve integrality.

A branch and price approach for the Split Pickup and Split Delivery VRP / M. Casazza, A. Ceselli, R. Wolfler Calvo. - In: ELECTRONIC NOTES IN DISCRETE MATHEMATICS. - ISSN 1571-0653. - 69:(2018), pp. 189-196. ((Intervento presentato al convegno EURO-ALIO tenutosi a Bologna nel 2018 [10.1016/j.endm.2018.07.025].

A branch and price approach for the Split Pickup and Split Delivery VRP

M. Casazza;A. Ceselli;
2018

Abstract

In this paper we address a Pickup and Delivery Vehicle Routing Problem where the demands of both pickup and delivery nodes can be split between several vehicles. We investigate a new formulation where the route of each vehicle is decomposed into a sequence of simpler substructures called clusters, mitigating the combinatorial explosion of feasible solutions. We implement a branch-and-price algorithm exploiting column generation procedures that dynamically generates clusters to obtain improved dual bounds, and ad hoc branching strategies to achieve integrality.
bike sharing; split delivery; split pickup; vehicle routing problem; Discrete Mathematics and Combinatorics; Applied Mathematics
Settore INF/01 - Informatica
Settore MAT/09 - Ricerca Operativa
Article (author)
File in questo prodotto:
File Dimensione Formato  
2018_ENDM_Casazza_Ceselli_Wolfler_SPSDVRP.pdf

accesso riservato

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

Caricamento 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: http://hdl.handle.net/2434/633708
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 7
  • ???jsp.display-item.citation.isi??? ND
social impact