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.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
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.