An Improved Genetic Programming Hyper-Heuristic for the Uncertain Capacitated Arc Routing Problem

Created by W.Langdon from gp-bibliography.bib Revision:1.8051

@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