In this paper we address the Two-Echelon Vehicle Routing Problem (2E-VRP), an extension of the classical Capacitated VRP, where the delivery from a single depot to the customers is managed by routing and consolidating the freight through intermediate depots called satellites. We present a family of Multi-Start heuristics based on separating the depot-to-satellite transfer and the satellite-to-customer delivery by iteratively solving the two resulting routing subproblems, while adjusting the satellite workloads that link them. The common scheme on which all the heuristics are based consists in, after having found an initial solution, applying a local search phase, followed by a diversification; if the new obtained solutions are feasible, then local search is applied again, otherwise a feasibility search procedure is applied, and if it successful, the local search is applied on the newfound solution. Different diversification strategies and feasibility search rules are proposed. We present computational results on a wide set of instances up to 50 customers and 5 satellites and compare them with results from the literature, showing how the new methods outperform previous existent methods, both in efficiency and accuracy.

Multi-start heuristics for the Two-Echelon Vehicle Routing Problem / T. G., Crainic; Mancini, Simona; Perboli, Guido; Tadei, Roberto. - 6622:(2011), pp. 179-190. (Intervento presentato al convegno 11th European Conference, EvoCOP 2011 tenutosi a Torino (IT) nel April 27-29, 201) [10.1007/978-3-642-20364-0_16].

Multi-start heuristics for the Two-Echelon Vehicle Routing Problem

MANCINI, SIMONA;PERBOLI, Guido;TADEI, Roberto
2011

Abstract

In this paper we address the Two-Echelon Vehicle Routing Problem (2E-VRP), an extension of the classical Capacitated VRP, where the delivery from a single depot to the customers is managed by routing and consolidating the freight through intermediate depots called satellites. We present a family of Multi-Start heuristics based on separating the depot-to-satellite transfer and the satellite-to-customer delivery by iteratively solving the two resulting routing subproblems, while adjusting the satellite workloads that link them. The common scheme on which all the heuristics are based consists in, after having found an initial solution, applying a local search phase, followed by a diversification; if the new obtained solutions are feasible, then local search is applied again, otherwise a feasibility search procedure is applied, and if it successful, the local search is applied on the newfound solution. Different diversification strategies and feasibility search rules are proposed. We present computational results on a wide set of instances up to 50 customers and 5 satellites and compare them with results from the literature, showing how the new methods outperform previous existent methods, both in efficiency and accuracy.
2011
9783642203633
File in questo prodotto:
File Dimensione Formato  
2397454.pdf

accesso aperto

Tipologia: 1. Preprint / submitted version [pre- review]
Licenza: PUBBLICO - Tutti i diritti riservati
Dimensione 324.46 kB
Formato Adobe PDF
324.46 kB Adobe PDF Visualizza/Apri
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/2397454
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo