A benchmark generator for dynamic capacitated arc routing problems

Capacitated arc routing problems (CARPs) are usually modeled as static problems, where information is known in advance and assumed to remain constant during the course of optimization. However, in practice, many factors such as demand, road accessibility, vehicle availability etc. change during the course of a mission and the route of each vehicle must be reconfigured dynamically. This problem is referred to as dynamic capacitated arc routing problem (DCARP) and there have been limited attempts to solve such problems in the past. Lack of standard DCARP benchmarks is one of the key factors limiting research in this direction. This paper introduces a benchmark generator for DCARPs considering interruptions/changes that are likely to occur in realistic scenarios. These benchmarks can be used to evaluate the strengths and the weaknesses of various optimization algorithms attempting to solve realistic DCARP problems.