Skip to content Skip to navigation
University of Warwick
  • Study
  • |
  • Research
  • |
  • Business
  • |
  • Alumni
  • |
  • News
  • |
  • About

University of Warwick
Publications service & WRAP

Highlight your research

  • WRAP
    • Home
    • Search WRAP
    • Browse by Warwick Author
    • Browse WRAP by Year
    • Browse WRAP by Subject
    • Browse WRAP by Department
    • Browse WRAP by Funder
    • Browse Theses by Department
  • Publications Service
    • Home
    • Search Publications Service
    • Browse by Warwick Author
    • Browse Publications service by Year
    • Browse Publications service by Subject
    • Browse Publications service by Department
    • Browse Publications service by Funder
  • Help & Advice
University of Warwick

The Library

  • Login
  • Admin

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

Tools
- Tools
+ Tools

MacLachlan, Jordan, Mei, Yide, Branke, Jürgen and Zhang, Mengjie (2020) Genetic programming hyper-heuristic with vehicle collaboration for uncertain capacitated arc routing problem. Evolutionary Computation, 28 (4). pp. 563-593. doi:10.1162/evco_a_00267

[img]
Preview
PDF
WRAP-Genetic-programming-hyper-heuristics-vehicle-arc-Branke-2019.pdf - Accepted Version - Requires a PDF viewer.

Download (3609Kb) | Preview
Official URL: https://doi.org/10.1162/evco_a_00267

Request Changes to record.

Abstract

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.

Item Type: Journal Article
Subjects: H Social Sciences > HF Commerce
Q Science > QA Mathematics
T Technology > T Technology (General)
Divisions: Faculty of Social Sciences > Warwick Business School
Library of Congress Subject Headings (LCSH): Operations research -- Mathematics, Physical distribution of goods -- Mathematics, Theory of distributions (Functional analysis) , Mathematical optimization
Journal or Publication Title: Evolutionary Computation
Publisher: M I T Press
ISSN: 1063-6560
Book Title: Proceedings of the Genetic and Evolutionary Computation Conference Companion on - GECCO '19
Official Date: 2 December 2020
Dates:
DateEvent
2 December 2020Published
4 November 2019Accepted
Volume: 28
Number: 4
Page Range: pp. 563-593
DOI: 10.1162/evco_a_00267
Status: Peer Reviewed
Publication Status: Published
Publisher Statement: This is the author’s final version, the article has been accepted for publication in Evolutionary Computation
Access rights to Published version: Restricted or Subscription Access
Related URLs:
  • Publisher

Request changes or add full text files to a record

Repository staff actions (login required)

View Item View Item

Downloads

Downloads per month over past year

View more statistics

twitter

Email us: wrap@warwick.ac.uk
Contact Details
About Us