A Predictive-Reactive Approach with Genetic Programming and Cooperative Coevolution for the Uncertain Capacitated Arc...

Area of Science:

• Operations Research
• Computer Science
• Artificial Intelligence

Background:

• The uncertain capacitated arc routing problem (UCARP) involves real-time demand and cost variations, challenging predefined solutions.
• Existing UCARP methods often address either baseline route optimization or recourse policy design, not both simultaneously.
• This leads to suboptimal or infeasible solutions when real-world uncertainties arise.

Purpose of the Study:

• To develop a novel approach that simultaneously optimizes the baseline task sequence and the recourse policy for the UCARP.
• To address the gap in existing research that fails to integrate these two critical components of UCARP solutions.
• To enhance the robustness and effectiveness of solutions for real-world routing problems with uncertainty.

Main Methods:

• A proactive-reactive approach is proposed, representing solutions as a baseline task sequence and a recourse policy.
• A cooperative coevolution framework is employed for simultaneous optimization.
• An estimation of distribution algorithm evolves the baseline task sequence, while genetic programming evolves the recourse policy.

Main Results:

• The proposed algorithm, Solution-Policy Coevolver, significantly outperforms state-of-the-art methods on benchmark instances (ugdb, uval).
• Analysis reveals that route failures are not always detrimental and can sometimes lead to better solutions, particularly when vehicles are returning to the depot.
• The simultaneous optimization of baseline sequences and recourse policies yields superior results compared to methods addressing only one aspect.

Conclusions:

• The cooperative coevolution of baseline task sequences and recourse policies offers a superior strategy for solving the UCARP.
• The findings challenge the conventional view of route failure, suggesting its strategic allowance can improve overall solution efficiency.
• This integrated approach provides a more robust and effective framework for tackling real-world routing problems under uncertainty.