A Novel Generalized Metaheuristic Framework for Dynamic Capacitated Arc Routing Problems

Tong，Hao1; Minku，Leandro L.1; Menzel，Stefan2; Sendhoff，Bernhard2; Yao，Xin3

10.1145/3583133.3595829

2023-07-15

GECCO 2023 Companion - Proceedings of the 2023 Genetic and Evolutionary Computation Conference Companion

45-46

The capacitated arc routing problem (CARP) aims at scheduling a fleet of vehicles with limited capacities to serve a set of tasks in a graph. The dynamic CARP (DCARP) optimization focuses on updating the vehicles’ service routes when unpredicted dynamic events happen and deteriorate the current service plan. Due to the outside vehicles are still being in their service when dynamic events happen and being located at different positions of the graph with different remaining capacities, the optimization algorithms for static CARP are unsuitable for solving the DCARP instance. However, in the existing literature, almost all proposed algorithms for DCARP were designed only for specific dynamic events instead of generic dynamic events such as the changing of traversing costs, the changing of the task’s demand, and the changing of the task’s number. Moreover, these algorithms are unable to benefit from the wealth of contributions provided by the existing CARP literature. In this work, we proposed a novel generalized meta-heuristic framework which enables all algorithms designed for static CARP to be capable of solving DCARP instances. Our experimental results demonstrated that the proposed framework significantly improves over state-of-the-art dynamic optimization algorithms in terms of the quality of obtained solution within the limited computational time.

Dynamic Capacitated Arc Routing Problem Evolutionary Algorithms Meta-heuristic Algorithms Routing Optimization

其他

英语

EI

20233514658531

Fleet operations ; Graph theory ; Heuristic algorithms ; Optimization ; Routing algorithms ; Vehicle routing ; Vehicles

Computer Software, Data Handling and Applications:723 ; Computer Programming:723.1 ; Combinatorial Mathematics, Includes Graph Theory, Set Theory:921.4 ; Optimization Techniques:921.5

2-s2.0-85169061030

Scopus

1.School of Computer Science University of Birmingham,Birmingham,United Kingdom
2.Honda Research Institute Europe,Offenbach,Germany
3.Department of Computer Science and Engineering,SUSTech Shenzhen,China School of Computer Science University of Birmingham,Birmingham,United Kingdom

Tong，Hao,Minku，Leandro L.,Menzel，Stefan,et al. A Novel Generalized Metaheuristic Framework for Dynamic Capacitated Arc Routing Problems[C],2023:45-46.