A Route Clustering and Search Heuristic for Large-Scale Multidepot-Capacitated Arc Routing Problem

Area of Science:

• Operations Research
• Combinatorial Optimization
• Logistics and Transportation

Background:

• The capacitated arc routing problem (CARP) is crucial for practical applications like waste collection and delivery services.
• The large-scale multidepot CARP (LSMDCARP) variant presents significant computational challenges due to its expansive search space.

Purpose of the Study:

• To develop an efficient heuristic for solving the challenging large-scale multidepot capacitated arc routing problem (LSMDCARP).
• To introduce the route clustering and search heuristic (RoCaSH) for improved LSMDCARP solution quality and reduced computation time.

Main Methods:

• Proposed the iterative improvement heuristic, route clustering and search (RoCaSH).
• Employed route cutting off and clustering techniques to decompose LSMDCARP into smaller single-depot CARP subproblems.
• Utilized Ulusoy's split operator and local search to solve individual subproblems iteratively.

Main Results:

• RoCaSH demonstrated superior performance compared to state-of-the-art multidepot CARP algorithms across various instance sizes.
• The heuristic achieved significantly better solutions for large-scale LSMDCARP instances.
• RoCaSH substantially reduced computational time, indicating high efficiency.

Conclusions:

• The proposed RoCaSH heuristic is highly effective for solving large-scale multidepot capacitated arc routing problems.
• Route clustering and iterative subproblem solving enhance search efficiency and solution quality in LSMDCARP.
• RoCaSH offers a promising approach for practical applications requiring efficient routing solutions.