Premium
Effects of update frequencies in a dynamic capacitated arc routing problem
Author(s) -
Padungwech Wasin,
Thompson Jonathan,
Lewis Rhyd
Publication year - 2020
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.21990
Subject(s) - arc routing , computer science , tabu search , mathematical optimization , routing (electronic design automation) , set (abstract data type) , graph , arc (geometry) , vehicle routing problem , algorithm , mathematics , theoretical computer science , computer network , geometry , programming language
The capacitated arc routing problem (CARP) concerns a minimum‐cost set of routes for vehicles that provide service on edges in a given graph while ensuring that the total demand in each route does not exceed the vehicle's capacity. This paper concerns a dynamic variant of the CARP. In particular, it focuses on a problem in which new tasks appear over time. We find that simply increasing the number of iterations of a tabu search algorithm does not always lead to a better solution for a dynamic CARP. This paper investigates how the solution quality can be affected by changing the frequency of updating solutions. Furthermore, we investigate whether or not such effect varies with a method of integrating new tasks into the solution at each update.