Genetic Programming Hyper-Heuristics with Vehicle Collaboration for Uncertain Capacitated Arc Routing Problems

Jordan MacLachlan, Yi Mei, Jürgen Branke, Mengjie Zhang

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:

  1. 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.
  2. 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

Abstract

Due to its direct relevance to post-disaster operations, meter reading and civil refuse collection, the Uncertain Capacitated Arc Routing Problem (UCARP) is an important optimisation problem. Stochastic models are critical to study as they more accurately represent the real-world than their deterministic counterparts. Although there have been extensive studies in solving routing problems under uncertainty, very few have considered UCARP, and none consider collaboration between vehicles to handle the negative effects of uncertainty. This paper proposes a novel Solution Construction Procedure (SCP) that generates solutions to UCARP within a collaborative, multi-vehicle framework. It consists of two types of collaborative activities: one when a vehicle unexpectedly expends capacity (\emph{route failure}), and the other during the refill process. Then, we propose a Genetic Programming Hyper-Heuristic (GPHH) algorithm to evolve the routing policy used within the collaborative framework. The experimental studies show that the new heuristic with vehicle collaboration and GP-evolved routing policy significantly outperforms the compared state-of-the-art algorithms on commonly studied test problems. This is shown to be especially true on instances with larger numbers of tasks and vehicles. This clearly shows the advantage of vehicle collaboration in handling the uncertain environment, and the effectiveness of the newly proposed algorithm.
BibTeX
@inproceedings{maclachlan2020genetic,
  author = {Jordan MacLachlan and Yi Mei and Jürgen Branke and Mengjie Zhang},
  title = {{Genetic Programming Hyper-Heuristics with Vehicle Collaboration for Uncertain Capacitated Arc Routing Problems}},
  booktitle = {Evol. Comput},
  year = {2020},
  url = {https://openreview.net/forum?id=O0dq73E7Qh},
}
Figure