A Parallel Memetic Algorithm to Solve the Capacitated Vehicle Routing Problem with Time Windows

Abstract

Nowadays, smart cities management has become an important topic where algorithms are crucial to solving their problems. Some topics related to smart cities can be modeled as combinatorial optimization problems. A common challenge is to find the optimal route, or routes, to attend demands of customers of a store. This challenge is known as the Vehicle Routing Problem (VRP). Evolutionary Algorithms (EAs) have demonstrated a high capacity to approximate optimal solutions in   a relatively small interval of time. In this article, we propose an EA to solve the Capacitated Vehicle Routing Problem with Time Windows (CVRPTW). Our proposal is a memetic algorithm that integrates simulated annealing and novel crossover operators. Although this kind of algorithm obtains higher quality solutions than simple EAs, they require a greater amount of time. Hence, the use of parallel computing is essential to get high-quality solutions in admissible times. Additionally, a novel crossover operator that enhances results of state-of-art schemes is proposed. The proposal is validated using Solomon’s benchmark, by contrasting our results with the best solutions reported in the specialized literature. A new best-known solution for a commonly used instance could be generated.