A predictive-reactive approach with genetic programming and cooperative co-evolution for uncertain capacitated arc routing problem

Liu, Y., Mei, Y., Zhang, M. and Zhang, Zili 2019, A predictive-reactive approach with genetic programming and cooperative co-evolution for uncertain capacitated arc routing problem, Evolutionary computation, pp. 1-25, doi: 10.1162/evco_a_00256.


Title A predictive-reactive approach with genetic programming and cooperative co-evolution for uncertain capacitated arc routing problem
Author(s) Liu, Y.
Mei, Y.
Zhang, M.
Zhang, ZiliORCID iD for Zhang, Zili orcid.org/0000-0002-8721-9333
Journal name Evolutionary computation
Start page 1
End page 25
Total pages 25
Publisher MIT Press
Place of publication Cambridge, Ma.
Publication date 2019
ISSN 1063-6560
1530-9304
Keyword(s) Capacitated arc routing problem
cooperative co-evolution
genetic programming.
hyper-heuristics
Summary The uncertain capacitated arc routing problem is of great significance for its wide applications in the real world. In uncertain capacitated arc routing problem, variables such as task demands and travel costs are realised in real time. This may cause the predefined solution to become ineffective and/or infeasible. There are two main challenges in solving this problem. One is to obtain a high-quality and robust baseline task sequence, and the other is to design an effective recourse policy to adjust the baseline task sequence when it becomes infeasible and/or ineffective during the execution. Existing studies typically only tackle one challenge (the other being addressed using a naive strategy). No existing work optimises the baseline task sequence and recourse policy simultaneously. To fill this gap, we propose a novel proactive-reactive approach, which represents a solution as a baseline task sequence and a recourse policy. The two components are optimised under a cooperative co-evolution framework, in which the baseline task sequence is evolved by an estimation of distribution algorithm, and the recourse policy is evolved by genetic programming. The experimental results show that the proposed algorithm, called Solution-Policy Co-evolver, significantly outperforms the state-of-the-art algorithms to uncertain capacitated arc routing problem for the ugdb and uval benchmark instances. Through further analysis, we discovered that route failure is not always detrimental. Instead, in certain cases (e.g. when the vehicle is on the way back to the depot) allowing route failure can lead to better solutions.
Notes In Press
Language eng
DOI 10.1162/evco_a_00256
Indigenous content off
Field of Research 01 Mathematical Sciences
08 Information and Computing Sciences
HERDC Research category C1 Refereed article in a scholarly journal
Persistent URL http://hdl.handle.net/10536/DRO/DU:30121964

Connect to link resolver
 
Unless expressly stated otherwise, the copyright for items in DRO is owned by the author, with all rights reserved.

Versions
Version Filter Type
Citation counts: TR Web of Science Citation Count  Cited 0 times in TR Web of Science
Scopus Citation Count Cited 0 times in Scopus
Google Scholar Search Google Scholar
Access Statistics: 64 Abstract Views  -  Detailed Statistics
Created: Mon, 20 May 2019, 10:48:43 EST

Every reasonable effort has been made to ensure that permission has been obtained for items included in DRO. If you believe that your rights have been infringed by this repository, please contact drosupport@deakin.edu.au.