ILS Metaheuristic to solve the Periodic Vehicle Routing Problem

  • Angelica Maria tenahua Centro Interdisciplinario de Posgrados, UPAEP
  • Elías Olivares-Benítez Facultad de Ingeniería, Universidad Panamericana
  • Diana Sánchez-Partida Centro Interdisciplinario de Posgrados, UPAEP
  • Santiago Omar Caballero Morales Centro Interdisciplinario de Posgrados, UPAEP
Keywords: Vehicle Routing Problem, Iterated Local Search

Abstract

This article presents a methodology for solving the Periodic Vehicle Routing Problem (PVRP) with an Iterated Local Search Metaheuristic (ILS). The problem is solved in two phases: the first step is to assign days of visit to each customer, and in the second step to determine the routes that each vehicle must perform each day. The heuristic for local improvement in ILS is Clarke & Wright Heuristic, and perturbation is made on the days of visit assigned to some customers. The instances generated by Cordeau for PVRP with 51, 102 and 153 customers are used. The results are compared to the best known solutions. The gap between the results presented by the proposed metaheuristic range from 15% to 5% above the best known solutions. The time to find the solutions with the proposed metaheuristic goes from 6.76 seconds for instances of 51customers, to 172.09 seconds for instances of 153 customers.

Published
2018-06-19
How to Cite
tenahua, A. M., Olivares-Benítez, E., Sánchez-Partida, D., & Caballero Morales, S. O. (2018). ILS Metaheuristic to solve the Periodic Vehicle Routing Problem. International Journal of Combinatorial Optimization Problems and Informatics, 9(3), 55-63. Retrieved from https://ijcopi.org/index.php/ojs/article/view/96
Section
Articles