An Improved Genetic Programming Hyper-Heuristic for the Uncertain Capacitated Arc Routing Problem
Created by W.Langdon from
gp-bibliography.bib Revision:1.7970
- @InProceedings{mac:2018:AJCAI,
-
author = "Jordan MacLachlan and Yi Mei and Juergen Branke and
Mengjie Zhang",
-
title = "An Improved Genetic Programming Hyper-Heuristic for
the Uncertain Capacitated Arc Routing Problem",
-
booktitle = "Australasian Joint Conference on Artificial
Intelligence",
-
year = "2018",
-
editor = "Tanja Mitrovic and Bing Xue and Xiaodong Li",
-
volume = "11320",
-
series = "LNCS",
-
address = "Wellington, New Zealand",
-
month = dec # " 11-14",
-
publisher = "Springer",
-
keywords = "genetic algorithms, genetic programming, Arc routing,
Hyper-heuristic",
-
isbn13 = "978-3-030-03990-5",
-
URL = "http://link.springer.com/chapter/10.1007/978-3-030-03991-2_40",
-
DOI = "doi:10.1007/978-3-030-03991-2_40",
-
size = "13 pages",
-
abstract = "This paper uses a Genetic Programming Hyper-Heuristic
(GPHH) to evolve routing policies for the Uncertain
Capacitated Arc Routing Problem (UCARP). Given a UCARP
instance, the GPHH evolves feasible solutions in the
form of decision making policies which decide the next
task to serve whenever a vehicle completes its current
service. Existing GPHH approaches have two drawbacks.
First, they tend to generate small routes by routing
through the depot and refilling prior to the vehicle
being fully loaded. This usually increases the total
cost of the solution. Second, existing GPHH approaches
cannot control the extra repair cost incurred by a
route failure, which may result in higher total cost.
To address these issues, this paper proposes a new GPHH
algorithm with a new No-Early-Refill filter to prevent
generating small routes, and a novel Flood Fill
terminal to better handle route failures. Experimental
studies show that the newly proposed GPHH algorithm
significantly outperforms the existing GPHH approaches
on the Ugdb and Uval benchmark datasets. Further
analysis has verified the effectiveness of both the new
filter and terminal.",
- }
Genetic Programming entries for
Jordan MacLachlan
Yi Mei
Jurgen Branke
Mengjie Zhang
Citations