In the commodity-constrained split delivery vehicle routing problem (C-SDVRP), customer demands are composed of sets of different commodities. The C-SDVRP asks for a minimum-distance set of routes such that all customer demands are met and vehicle capacities are respected. Moreover, whenever a commodity is delivered by a vehicle to a customer, the entire amount requested by this customer must be provided. Different commodities demanded by one customer, however, can be delivered by different vehicles. Thus, the C-SDVRP is a relaxation of the capacitated vehicle routing problem and a restriction of the split delivery vehicle routing problem. For its exact solution, we propose a branch-price-and-cut algorithm that employs and tailors stabilization techniques that have been successfully applied to several cutting and packing problems. More precisely, we make use of (deep) dual-optimal inequalities which are particularly suited to reduce the negative effects caused by the inherent symmetry of C-SDVRP instances. One main issue here is the interaction Rc{between} branching and cutting decisions and the different classes of dual inequalities. Extensive computational tests on existing and extended benchmark instances show that all stabilized variants of our branch-price-and-cut are clearly superior to the non-stabilized version. On the existing benchmark, our algorithm is significantly faster than the state-of-the-art algorithm and provides several new optima for instances with up to 60 customers and 180 tasks. Lower bounds are reported for all tested instances with up to 80 customers and 480 tasks, improving the bounds for all unsolved instances and providing first lower bounds for several instances.

Stabilized branch-price-and-cut for the commodity-constrained split delivery vehicle routing problem / T. Gschwind, N. Bianchessi, S. Irnich. - In: EUROPEAN JOURNAL OF OPERATIONAL RESEARCH. - ISSN 0377-2217. - 278:1(2019 Oct), pp. 91-104.

Stabilized branch-price-and-cut for the commodity-constrained split delivery vehicle routing problem

N. Bianchessi;
2019

Abstract

In the commodity-constrained split delivery vehicle routing problem (C-SDVRP), customer demands are composed of sets of different commodities. The C-SDVRP asks for a minimum-distance set of routes such that all customer demands are met and vehicle capacities are respected. Moreover, whenever a commodity is delivered by a vehicle to a customer, the entire amount requested by this customer must be provided. Different commodities demanded by one customer, however, can be delivered by different vehicles. Thus, the C-SDVRP is a relaxation of the capacitated vehicle routing problem and a restriction of the split delivery vehicle routing problem. For its exact solution, we propose a branch-price-and-cut algorithm that employs and tailors stabilization techniques that have been successfully applied to several cutting and packing problems. More precisely, we make use of (deep) dual-optimal inequalities which are particularly suited to reduce the negative effects caused by the inherent symmetry of C-SDVRP instances. One main issue here is the interaction Rc{between} branching and cutting decisions and the different classes of dual inequalities. Extensive computational tests on existing and extended benchmark instances show that all stabilized variants of our branch-price-and-cut are clearly superior to the non-stabilized version. On the existing benchmark, our algorithm is significantly faster than the state-of-the-art algorithm and provides several new optima for instances with up to 60 customers and 180 tasks. Lower bounds are reported for all tested instances with up to 80 customers and 480 tasks, improving the bounds for all unsolved instances and providing first lower bounds for several instances.
routing; vehicle routing; dual-optimal inequalities; column generation; discrete split delivery
Settore MAT/09 - Ricerca Operativa
ott-2019
Article (author)
File in questo prodotto:
File Dimensione Formato  
EJOR-D-18-02358R2-POSTPRINT.pdf

Open Access dal 02/10/2021

Tipologia: Post-print, accepted manuscript ecc. (versione accettata dall'editore)
Dimensione 501.27 kB
Formato Adobe PDF
501.27 kB Adobe PDF Visualizza/Apri
1-s2.0-S0377221719303285-main.pdf

accesso riservato

Tipologia: Publisher's version/PDF
Dimensione 629.96 kB
Formato Adobe PDF
629.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.

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