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 T. G.; Mancini S.; Perboli G.; Tadei R.. - STAMPA. - 53:(2013), pp. 113-125. [10.1007/978-1-4614-6322-1_7]
Titolo: | GRASP with Path Relinking for the Two-Echelon Vehicle Routing Problem | |
Autori: | ||
Data di pubblicazione: | 2013 | |
Titolo del libro: | Advances in Metaheuristics, Operations Research/Computer Science Interfaces Series | |
Abstract: | We propose a meta-heuristic based on GRASP combined with Path Relinking to address the Two-Echelo...n 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. | |
ISBN: | 9781461463214 | |
Appare nelle tipologie: | 2.1 Contributo in volume (Capitolo o Saggio) |
File in questo prodotto:
File | Descrizione | Tipologia | Licenza | |
---|---|---|---|---|
MIC2011_CMPT_v4.pdf | 1. Preprint / submitted version [pre- review] | Non Pubblico - Accesso privato/ristretto | Administrator Richiedi una copia | |
2428975.pdf | 1. Preprint / submitted version [pre- review] | Non Pubblico - Accesso privato/ristretto | Administrator Richiedi una copia |
http://hdl.handle.net/11583/2428975