GRASP/VND and multi-start evolutionary local search for the single truck and trailer routing problem with satellite depots

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

1 LOSI - Laboratoire d'Optimisation des Systèmes Industriels
2 COPA - Centro de Optimización y Probabilidad Aplicada, Departamento de Ingeniería Industrial
3 UdeA - Departamento de Ingeniería Industrial

In the single truck and trailer routing problem with satellite depots (STTRPSD) a vehicle composed of a truck with a detachable trailer serves the demand of a set of customers reachable only by the truck without the trailer. This accessibility constraint implies the selection of locations to park the trailer before performing the trips to the customers. We propose two metaheuristics based on greedy randomized adaptive search procedures (GRASP), variable neighborhood descent (VND) and evolutionary local search (ELS) to solve this problem. To evaluate these metaheuristics we test them on a set of 32 randomly generated problems. The computational experiment shows that a multi-start evolutionary local search outperforms a GRASP/VND. Moreover, it obtains competitive results when applied to the multi-depot vehicle routing problem (MDVRP), that can be seen as a special case of the STTRPSD.

Keywords: Truck and trailer routing problem (TTRP); Multi-depot vehicle routing problem (MDVRP); Greedy randomized adaptive search procedures (GRASP); Evolutionary local search (ELS); Variable neighborhood descent (VND); Iterated local search (ILS)

Domains: Computer Science [cs]; Operations Research [cs.RO]

Juan Villegas, Christian Prins, Caroline Prodhon, Andrés Medaglia, Nubia Velasco. GRASP/VND and multi-start evolutionary local search for the single truck and trailer routing problem with satellite depots. Engineering Applications of Artificial Intelligence, 2010, 23 (5), pp.780-794. ⟨10.1016/j.engappai.2010.01.013⟩. ⟨hal-02493914⟩