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

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.