We introduce new valid inequalities for the two-echelon variant of the Capacitated Vehicle Routing Problem (CVRP)In particular, a first group of inequalities is obtained by extending to 2E-CVRP some of the most effective among the existing CVRP valid inequalities. A second group of inequalities is explicitly derived for the 2E-CVRP and concerns the flow feasibility at customer nodes and the satellitecustomer route connectivity. The inequalities are then introduced in a Branch & Cut algorithm. Computational results show that the proposed algorithm is able both to solve to optimality many open literature instances and significantly reduce the optimality gap for the remaining instances.
New Valid Inequalities for the Two-Echelon Capacitated Vehicle Routing Problem / Perboli, Guido; Tadei, Roberto; Fadda, Edoardo. - In: ELECTRONIC NOTES IN DISCRETE MATHEMATICS. - ISSN 1571-0653. - ELETTRONICO. - 64:(2018), pp. 75-84. [10.1016/j.endm.2018.01.009]
New Valid Inequalities for the Two-Echelon Capacitated Vehicle Routing Problem
PERBOLI, GUIDO;TADEI, Roberto;FADDA, EDOARDO
2018
Abstract
We introduce new valid inequalities for the two-echelon variant of the Capacitated Vehicle Routing Problem (CVRP)In particular, a first group of inequalities is obtained by extending to 2E-CVRP some of the most effective among the existing CVRP valid inequalities. A second group of inequalities is explicitly derived for the 2E-CVRP and concerns the flow feasibility at customer nodes and the satellitecustomer route connectivity. The inequalities are then introduced in a Branch & Cut algorithm. Computational results show that the proposed algorithm is able both to solve to optimality many open literature instances and significantly reduce the optimality gap for the remaining instances.File | Dimensione | Formato | |
---|---|---|---|
inoc2017-ptf.pdf
Open Access dal 23/02/2020
Descrizione: Articolo principale
Tipologia:
2. Post-print / Author's Accepted Manuscript
Licenza:
Creative commons
Dimensione
152.4 kB
Formato
Adobe PDF
|
152.4 kB | Adobe PDF | Visualizza/Apri |
1-s2.0-S157106531830009X-main.pdf
non disponibili
Tipologia:
2a Post-print versione editoriale / Version of Record
Licenza:
Non Pubblico - Accesso privato/ristretto
Dimensione
252.85 kB
Formato
Adobe PDF
|
252.85 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.
https://hdl.handle.net/11583/2679582