We propose a meta-heuristic based on GRASP combined with Path Relinking to address the Two-Echelon Vehicle Routing Problem, an extension of the Capacitated Vehicle Routing Problem in which the delivery from a single depot to customers is achieved by routing and consolidating the freight through intermediate depots called satellites. The problem is treated by separating the depot-to-satellite transfer and the satellite-to-customer delivery, and iteratively solving the two resulting routing subproblems, while adjusting the satellite workloads that link them. The meta-heuristic scheme consists of applying a GRASP and a local search procedures in sequence. Then, the resulting solution is linked to an elite solution by means of a Path Relinking procedure. To escape from infeasible solutions, which are quite common in this kind of problem, a feasibility search procedure is applied within Path Relinking. Extensive computational results on instances with up to 50 customers and 5 satellites show that the meta-heuristic is able to improve literature results, both in efficiency and accuracy.

GRASP with Path Relinking for the Two-Echelon Vehicle Routing Problem / Crainic, Teodor; Mancini, Simona; Perboli, Guido; Tadei, Roberto. - STAMPA. - 53:(2013), pp. 113-125. [10.1007/978-1-4614-6322-1_7]

GRASP with Path Relinking for the Two-Echelon Vehicle Routing Problem

CRAINIC, TEODOR;MANCINI, SIMONA;PERBOLI, Guido;TADEI, Roberto
2013

Abstract

We propose a meta-heuristic based on GRASP combined with Path Relinking to address the Two-Echelon Vehicle Routing Problem, an extension of the Capacitated Vehicle Routing Problem in which the delivery from a single depot to customers is achieved by routing and consolidating the freight through intermediate depots called satellites. The problem is treated by separating the depot-to-satellite transfer and the satellite-to-customer delivery, and iteratively solving the two resulting routing subproblems, while adjusting the satellite workloads that link them. The meta-heuristic scheme consists of applying a GRASP and a local search procedures in sequence. Then, the resulting solution is linked to an elite solution by means of a Path Relinking procedure. To escape from infeasible solutions, which are quite common in this kind of problem, a feasibility search procedure is applied within Path Relinking. Extensive computational results on instances with up to 50 customers and 5 satellites show that the meta-heuristic is able to improve literature results, both in efficiency and accuracy.
9781461463214
Advances in Metaheuristics, Operations Research/Computer Science Interfaces Series
File in questo prodotto:
File Dimensione Formato  
MIC2011_CMPT_v4.pdf

non disponibili

Tipologia: 1. Preprint / submitted version [pre- review]
Licenza: Non Pubblico - Accesso privato/ristretto
Dimensione 135.56 kB
Formato Adobe PDF
135.56 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
2428975.pdf

non disponibili

Tipologia: 1. Preprint / submitted version [pre- review]
Licenza: Non Pubblico - Accesso privato/ristretto
Dimensione 121.5 kB
Formato Adobe PDF
121.5 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
Pubblicazioni consigliate

Caricamento 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/2428975
 Attenzione

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