Effects of update frequencies in a dynamic capacitated arc routing problem. Issue 4 (16th September 2020)

• Record Type: Journal Article
• Authors: Padungwech, Wasin; Thompson, Jonathan; Lewis, Rhyd
• Is Part Of: Networks. Volume 76:Issue 4(2020)
• Page Start: 522
• Page End: 538
• Publication Date: 2020-09-16
• Subjects: capacitated arc routing -- dynamic -- metaheuristic -- new tasks -- tabu search -- update schedule; Network analysis (Planning) -- Periodicals; 658.4032
• DOI: 10.1002/net.21990
• Languages: English
• ISSNs: 0028-3045

Abstract

Abstract: 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.