A GRASP with evolutionary path relinking for the truck and trailer routing problem

Juan Villegas (1, 2, 3) , Christian Prins (1) , Caroline Prodhon (1) , Andrés L. Medaglia (2) , Nubia Velasco (2)

1 LOSI - Laboratoire d'Optimisation des Systèmes Industriels
2 UNIANDES - Universidad de los Andes [Bogota]
3 Universidad de Antioquia = University of Antioquia [Medellín, Colombia]

In the truck and trailer routing problem (TTRP) a heterogeneous fleet composed of trucks and trailers has to serve a set of customers, some only accessible by truck and others accessible with a truck pulling a trailer. This problem is solved using a route-first, cluster-second procedure embedded within a hybrid metaheuristic based on a greedy randomized adaptive search procedure (GRASP), a variable neighborhood search (VNS) and a path relinking (PR). We test PR as a post-optimization procedure, as an intensification mechanism, and within evolutionary path relinking (EvPR). Numerical experiments show that all the variants of the proposed GRASP with path relinking outperform all previously published methods. Remarkably, GRASP with EvPR obtains average gaps to best-known solutions of less than 1% and provides several new best solutions.

Keywords: Truck and trailer routing problem (TTRP); Greedy randomized adaptive search procedures (GRASP); Variable neighborhood search (VNS); Path relinking; Vehicle routing problem

Domains: Operations Research [cs.RO]

Juan Villegas, Christian Prins, Caroline Prodhon, Andrés L. Medaglia, Nubia Velasco. A GRASP with evolutionary path relinking for the truck and trailer routing problem. Computers and Operations Research, 2011, 38 (9), pp.1319-1334. ⟨10.1016/j.cor.2010.11.011⟩. ⟨hal-02476300⟩