Genetic Programming Hyper-Heuristics with Vehicle Collaboration for Uncertain Capacitated Arc Routing Problems
Evolutionary Computation · 2020-12 · 28 (4) · 563-593
DOI: 10.1162/evco_a_00267 ↗Kurz gefasst
Fachartikel in der Zeitschrift Evolutionary Computation, 2020-12. Verfasst von Jordan MacLachlan und 3 weiteren Autor:innen. Beteiligte Einrichtung: School of Engineering and Computer Science, Victoria University of Wellington, PO Box 600, Wellington 6140, New Zealand maclacjord@ecs.vuw.ac.nz. Hauptthemen laut MEDLINE: Algorithms, Heuristics, Motor Vehicles. Die Arbeit wurde bisher 44-mal zitiert (Crossref) und nennt 80 Literaturangaben.
Abstract (Originalsprache)
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 article 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 ( 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.
Schlagwörter
MeSH-Schlagwörter (MEDLINE)
Stichwörter der Autor:innen
Autor:innen und Institutionen
- School of Engineering and Computer Science, Victoria University of Wellington, PO Box 600, Wellington 6140, New Zealand maclacjord@ecs.vuw.ac.nz.
- School of Engineering and Computer Science, Victoria University of Wellington yi.mei@ecs.vuw.ac.nz.
- Warwick Business School, Coventry, CV4 7AL, United Kingdom juergen.branke@wbs.ac.uk.
- School of Engineering and Computer Science, Victoria University of Wellington mengjie.zhang@ecs.vuw.ac.nz.
Zitieren
APA
MacLachlan, J., Mei, Y., Branke, J., & Zhang, M. (2020). Genetic Programming Hyper-Heuristics with Vehicle Collaboration for Uncertain Capacitated Arc Routing Problems. Evolutionary Computation, 28(4), 563-593. https://doi.org/10.1162/evco_a_00267
Vancouver
MacLachlan J, Mei Y, Branke J, Zhang M. Genetic Programming Hyper-Heuristics with Vehicle Collaboration for Uncertain Capacitated Arc Routing Problems. Evolutionary Computation. 2020;28(4):563-593. doi:10.1162/evco_a_00267
BibTeX
@article{MacLachlan2020,
author = {MacLachlan, Jordan and Mei, Yi and Branke, Juergen and Zhang, Mengjie},
title = {Genetic Programming Hyper-Heuristics with Vehicle Collaboration for Uncertain Capacitated Arc Routing Problems},
journal = {Evolutionary Computation},
year = {2020},
volume = {28},
number = {4},
pages = {563--593},
doi = {10.1162/evco_a_00267}
}
EUVIMED