A Scalable Approach to Capacitated Arc Routing Problems Based on Hierarchical Decomposition

Area of Science:

• Operations Research
• Computer Science
• Optimization

Background:

• The capacitated arc routing problem (CARP) is a complex optimization challenge with significant real-world applications.
• Existing methods for CARP often struggle with scalability, requiring extensive computation time for large problem instances.

Purpose of the Study:

• To develop an efficient and scalable approach for solving large-scale capacitated arc routing problems.
• To address the limitations of current methods in handling CARP instances with thousands of tasks.

Main Methods:

• A hierarchical decomposition strategy is proposed, breaking down CARP instances into manageable subgroups.
• Subproblems are solved recursively, with outputs treated as virtual tasks for higher-level problem formulation using clustering techniques.
• This recursive decomposition rapidly reduces the number of tasks at each hierarchical layer, ensuring tractability.

Main Results:

• Empirical studies were conducted on CARP instances up to 3584 tasks, significantly larger than those previously investigated.
• The proposed hierarchical approach demonstrated superior scalability compared to existing methods.
• Satisfactory solutions were achieved in significantly reduced computation times for large-scale instances.

Conclusions:

• The developed hierarchical decomposition method offers a highly scalable solution for the capacitated arc routing problem.
• This approach effectively handles large-scale CARP instances, overcoming the limitations of previous methods.
• The methodology shows potential for generalization to other permutation-based optimization problems.