Abstract
The Uncertain Capacitated Arc Routing Problem (UCARP) is a critical optimization challenge with direct applications in post-disaster logistics, meter reading, and refuse collection. While stochastic models more accurately reflect real-world conditions than deterministic ones, existing research often overlooks the potential for vehicle collaboration to mitigate the negative effects of uncertainty. This paper proposes a novel Solution Construction Procedure (SCP) that enables a multi-vehicle collaborative framework. The framework addresses two key scenarios: unexpected capacity depletion (route failure) and the refill process. To navigate this framework, we employ a Genetic Programming Hyper-Heuristic (GPHH) algorithm to evolve effective routing policies. Experimental results demonstrate that this collaborative approach significantly outperforms state-of-the-art algorithms, particularly in large-scale instances with high task and vehicle density.
Introduction
In the Capacitated Arc Routing Problem (CARP), a fleet of vehicles with limited capacity must service a set of required edges (arcs) in a network. In real-world scenarios, however, demand and travel costs are rarely static. This leads to the Uncertain CARP (UCARP), where stochastic variables introduce the risk of "route failure"—a situation where a vehicle's capacity is exhausted before it completes its assigned tasks.
Traditionally, UCARP solutions treat vehicles as independent agents. When a route failure occurs, the vehicle must return to the depot to refill and then return to the exact point of failure to finish the task. This "lone wolf" approach is inherently inefficient. This research introduces a collaborative paradigm where vehicles can assist one another, transforming a fleet of independent units into a coordinated team.
A Collaborative Framework for Routing
The core of this research is a new Solution Construction Procedure (SCP) that incorporates two distinct collaborative mechanisms:
- Route Failure Collaboration: Instead of requiring a failed vehicle to return and finish its own task, the remaining demand of a partially served task is returned to a shared task pool. This allows any available vehicle in the vicinity to pick up the task, reducing redundant travel.
- Refill Collaboration: When a vehicle is forced to return to the depot to empty its load, it evaluates unserved tasks along its return path. If it has residual capacity, it services these tasks "on the way," effectively utilizing what would otherwise be "deadhead" (non-productive) travel time.
Because the exact remaining demand of a failed task is often unknown, the framework utilizes a truncated normal distribution to estimate requirements, allowing the fleet to make informed decisions despite imperfect information.
Evolving Policies via Genetic Programming
Manually designing routing heuristics that account for these collaborative opportunities is complex. To address this, the study utilizes Genetic Programming Hyper-Heuristics (GPHH). GPHH evolves mathematical expressions that serve as priority functions for task selection. By treating these functions as a population that undergoes selection, crossover, and mutation, the algorithm automatically discovers high-performing routing policies tailored for the collaborative environment.
Experimental Evaluation
The proposed GPHH with Collaboration (GPHH-C) was tested against standard GPHH and the previous state-of-the-art algorithm, EDASLS, across three benchmark datasets:
- gdb: Small-scale instances.
- val: Medium-scale instances.
- egl: Large-scale instances based on real-world road networks in Lancashire, UK.
Results and Key Insights
The experiments revealed that the benefits of collaboration scale with the complexity of the problem. While improvements in small gdb instances were modest, the performance gap widened significantly in the larger egl datasets.
On the largest egl instances, GPHH-C achieved an average total cost of 12,647, compared to 13,327 for standard GPHH and 13,772 for EDASLS. This represents a substantial reduction in operational costs. Furthermore, the study found that Refill Collaboration was particularly effective in large-scale scenarios, as it significantly minimized the distance traveled without servicing tasks.
Conclusion
This research demonstrates that vehicle collaboration is a powerful tool for managing uncertainty in arc routing. By integrating collaborative rules into the solution construction process and using Genetic Programming to evolve sophisticated routing policies, the proposed GPHH-C framework sets a new benchmark for UCARP. Future work will explore decentralized coordination models where vehicles can negotiate tasks directly, as well as the impact of dynamic road closures and time-window constraints on collaborative efficiency.
Summary updated