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

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

TL;DR

This paper introduces a collaborative framework for the Uncertain Capacitated Arc Routing Problem (UCARP), where vehicles "tag-team" tasks to handle unpredictable demands. By using Genetic Programming to automatically evolve routing policies that leverage vehicle collaboration, the researchers achieved state-of-the-art results, particularly on large-scale, complex logistics problems.

What Problem Does This Paper Address?

Imagine a fleet of salt trucks during a winter storm or garbage trucks on a busy route. This is the Capacitated Arc Routing Problem (CARP): you have a set of streets (arcs) that need service, and a fleet of vehicles with limited capacity.

In the real world, things are rarely certain. The amount of trash on a street or the time it takes to travel between blocks fluctuates. This is UCARP. The biggest headache in UCARP is "route failure"—when a vehicle starts servicing a street but runs out of capacity halfway through. Traditionally, that vehicle has to go back to the depot, empty its load, and return to finish that specific street. This is incredibly inefficient.

The authors noticed a major gap: existing solutions treat vehicles as "lone wolves." They don't account for the possibility that a nearby vehicle with spare capacity could finish the job, or that a vehicle heading back to the depot could pick up a few extra tasks along the way.

Methods

The authors propose a two-pronged approach: a new collaborative framework and an AI-driven way to navigate it.

  1. Collaborative Solution Construction Procedure (SCP): This is the "rulebook" for how the fleet operates in real-time. It introduces two collaborative events:
  2. Route Failure Collaboration: If Vehicle A runs out of capacity, the remaining task is put back into a shared pool. Any available vehicle can now step in to finish it.
  3. Refill Collaboration: While a vehicle is driving back to the depot to empty its load, it checks if there are any unserved tasks along its path. If it has a little bit of room left, it services them "on the way," saving other vehicles a trip.
  4. Genetic Programming Hyper-Heuristic (GPHH): Manually writing a "routing policy" (the logic that tells a vehicle which task to do next) for a collaborative fleet is nearly impossible. Instead, the authors use GPHH to evolve these policies. GPHH treats mathematical expressions as "individuals" in a population, breeding and mutating them over generations to find the most efficient decision-making logic.

Datasets

The researchers tested their approach on three classic CARP benchmark datasets, modified to include uncertainty (using normal distributions for demand and cost):

  • gdb: Small instances (up to 55 tasks).
  • val: Medium-sized instances (34 to 97 tasks).
  • egl: Large-scale, real-world road network data from Lancashire, UK (up to 190 tasks).

Key Insights and Ideas

  • Collaboration Scales Better: The "aha moment" was seeing that collaboration becomes exponentially more valuable as the problem gets bigger. In small sets (gdb), the benefits were modest, but in the large egl sets, collaboration was a game-changer.
  • Imperfect Information is Fine: When a task is partially finished, the exact remaining demand might be unknown. The authors tested a version where vehicles "guessed" the remaining demand using a truncated normal distribution. Surprisingly, this statistical guess performed almost as well as having "perfect" knowledge of the remaining demand.
  • Refill Efficiency: The "on the way" servicing (Refill Collaboration) was found to be more effective than the "tag-teaming" (Route Failure Collaboration) for large instances. It significantly reduces the "deadheading" (driving without servicing) that plagues traditional routing.

Key Results

The collaborative GPHH (GPHH-C) was compared against standard GPHH and EDASLS (the previous state-of-the-art).

  • Superior Performance: GPHH-C outperformed the state-of-the-art on the majority of medium and large instances.
  • The egl Breakthrough: On the largest egl dataset, GPHH-C achieved an average total cost of 12,647, significantly lower than EDASLS (13,772) and standard GPHH (13,327).
  • Robustness: The evolved policies proved to be highly generalizable, performing well on unseen test samples that they weren't specifically trained on.

Limitations and Future Work

While the results are impressive, the authors note a few areas for growth:

  • Policy Complexity: The evolved mathematical expressions can become quite "bloated" and difficult for a human to interpret (though they work well for the computer).
  • Multi-Agent Coordination: The current model uses a centralized "operating center" to give instructions. Future work could explore decentralized multi-agent systems where vehicles negotiate with each other directly.
  • Broader Uncertainty: The study focused heavily on demand uncertainty; future versions could look deeper into dynamic edge failures (e.g., road closures) or time-window constraints.

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},
}

Loading related content...

Figure