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

Authors

  • Oscar M. González Research Center of Mathematics (CIMAT A.C.)
  • Carlos Segura Research Center of Mathematics (CIMAT A.C.)
  • Sergio I. Valdez Peña Research Center of Mathematics (CIMAT A.C.)

Keywords:

Capacitated Vehicle Routing Problem, memetic algorithm, CVRPTW, Parallel Computing, Solomon’s benchmark

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.

Downloads

Published

2018-01-30

How to Cite

González, O. M., Segura, C., & Valdez Peña, S. I. (2018). A Parallel Memetic Algorithm to Solve the Capacitated Vehicle Routing Problem with Time Windows. International Journal of Combinatorial Optimization Problems and Informatics, 9(1), 35–45. Retrieved from https://ijcopi.org/ojs/article/view/77

Issue

Section

Articles