A global repair operator for capacitated arc routing problem.

Area of Science:

• Operations Research
• Combinatorial Optimization

Background:

• The Capacitated Arc Routing Problem (CARP) is a significant challenge in logistics and operations research due to its real-world applicability.
• Exact methods for CARP are computationally infeasible for large instances, necessitating the use of heuristic and metaheuristic approaches.

Purpose of the Study:

• To address a key limitation in traditional search algorithms for CARP.
• To introduce a novel Global Repair Operator (GRO) designed to enhance CARP solution methodologies.
• To evaluate the effectiveness of integrating GRO into a Tabu Search Algorithm (TSA).

Main Methods:

• Development and implementation of a novel Global Repair Operator (GRO).
• Integration of GRO into a Tabu Search Algorithm (TSA) to create a Repair-based Tabu Search (RTS) algorithm.
• Empirical evaluation of the RTS algorithm on five benchmark CARP test sets.

Main Results:

• The RTS algorithm demonstrated superior solution quality compared to the original TSA.
• RTS exhibited faster convergence rates in solving CARP instances.
• The performance of RTS was found to be competitive with existing state-of-the-art CARP algorithms.
• The efficacy of the GRO was empirically validated.

Conclusions:

• The proposed Global Repair Operator (GRO) significantly enhances the performance of metaheuristic algorithms for the Capacitated Arc Routing Problem (CARP).
• The Repair-based Tabu Search (RTS) algorithm offers improved solution quality and faster convergence.
• GRO is a versatile tool with the potential to benefit various existing CARP solution methods that utilize similar solution representations.