The Library
Optimizing agents with genetic programming : an evaluation of hyper-heuristics in dynamic real-time logistics
Tools
van Lon, Rinde R. S., Branke, Jürgen and Holvoet, Tom (2018) Optimizing agents with genetic programming : an evaluation of hyper-heuristics in dynamic real-time logistics. Genetic Programming and Evolvable Machines, 19 (1-2). pp. 93-120. doi:10.1007/s10710-017-9300-5 ISSN 1389-2576.
|
PDF
WRAP-optimising-agents-genetic-programming-logistics-Branke-2017.pdf - Accepted Version - Requires a PDF viewer. Download (781Kb) | Preview |
Official URL: https://doi.org/10.1007/s10710-017-9300-5
Abstract
Dynamic pickup and delivery problems (PDPs) require online algorithms for managing a fleet of vehicles. Generally, vehicles can be managed either centrally or decentrally. A common way to coordinate agents decentrally is to use the contract-net protocol (CNET) that uses auctions to allocate tasks among agents. To participate in an auction, agents require a method that estimates the value of a task. Typically this method is an optimization algorithm. Recently, hyper-heuristics has been proposed for automated design of heuristics. Two properties of automatically designed heuristics are particularly promising: 1) a generated heuristic computes quickly, it is expected therefore that hyper-heuristics heuristics perform especially well for urgent problems, and 2) by using simulationbased evaluation, hyper-heuristics can learn from the past and can therefore create a ‘rule of thumb’ that anticipates situations in the future. In the present paper we empirically evaluate whether hyper-heuristics, more specifically genetic programming (GP), can be used to improve agents decentrally coordinated via CNET. We compare several GP settings and compare the resulting heuristic with existing centralized and decentralized algorithms on a dynamic PDP dataset with varying levels of dynamism, urgency, and scale. The results indicate that the evolved heuristic always outperforms the optimization algorithm in the decentralized MAS and often outperforms the centralized optimization algorithm. Our paper shows that designing MASs using genetic programming is an effective way to obtain competitive performance compared to traditional operational research approaches. These results strengthen the relevance of decentralized agent based approaches in dynamic logistics.
Item Type: | Journal Article | ||||||||
---|---|---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||||||
Divisions: | Faculty of Social Sciences > Warwick Business School > Operational Research & Management Sciences Faculty of Social Sciences > Warwick Business School |
||||||||
Library of Congress Subject Headings (LCSH): | Logistics -- Computer programs, Logistics -- Mathematical models | ||||||||
Journal or Publication Title: | Genetic Programming and Evolvable Machines | ||||||||
Publisher: | Springer New York LLC | ||||||||
ISSN: | 1389-2576 | ||||||||
Official Date: | June 2018 | ||||||||
Dates: |
|
||||||||
Volume: | 19 | ||||||||
Number: | 1-2 | ||||||||
Page Range: | pp. 93-120 | ||||||||
DOI: | 10.1007/s10710-017-9300-5 | ||||||||
Status: | Peer Reviewed | ||||||||
Publication Status: | Published | ||||||||
Access rights to Published version: | Restricted or Subscription Access | ||||||||
Date of first compliant deposit: | 2 March 2017 | ||||||||
Date of first compliant Open Access: | 6 April 2018 | ||||||||
RIOXX Funder/Project Grant: |
|
||||||||
Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year