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 in questo prodotto:
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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11583/2679582