Genetic programming hyper-heuristic for multi-vehicle uncertain capacitated arc routing problem

Yi Mei, Mengjie Zhang

Abstract

This paper investigates evolving routing policy for general Uncertain Capacitated Arc Routing Problems (UCARP) with any number of vehicles, and for the first time, designs a novel model for online decision making (i.e. meta-algorithm) for multiple vehicles in service simultaneously. Then, we develop a GPHH based on the meta-algorithm. The experimental studies show the GPHH can evolve much better policies than the state-of-the-art manually designed policy. In addition, the reusability of the evolved policies dramatically decreases when the number of vehicles changes, which suggests a retraining process when a new vehicle is brought or an existing vehicle breaks down.
BibTeX
@inproceedings{mei2018genetic,
  author = {Yi Mei and Mengjie Zhang},
  title = {{Genetic programming hyper-heuristic for multi-vehicle uncertain capacitated arc routing problem}},
  booktitle = {GECCO (Companion)},
  year = {2018},
  doi = {10.1145/3205651.3205661},
}

Loading related content...

Figure