Skip to main content

Research Repository

Advanced Search

Large neighbourhood search with adaptive guided ejection search for the pickup and delivery problem with time windows

Curtois, Timothy; Landa-Silva, Dario; Qu, Yi; Laesanklang, Wasakorn

Authors

Timothy Curtois tim.curtois@nottingham.ac.uk

Yi Qu

Wasakorn Laesanklang



Abstract

© 2018, The Author(s). An effective and fast hybrid metaheuristic is proposed for solving the pickup and delivery problem with time windows. The proposed approach combines local search, large neighbourhood search and guided ejection search in a novel way to exploit the benefits of each method. The local search component uses a novel neighbourhood operator. A streamlined implementation of large neighbourhood search is used to achieve an effective balance between intensification and diversification. The adaptive ejection chain component perturbs the solution and uses increased or decreased computation time according to the progress of the search. While the local search and large neighbourhood search focus on minimising travel distance, the adaptive ejection chain seeks to reduce the number of routes. The proposed algorithm design results in an effective and fast solution method that finds a large number of new best-known solutions on a well-known benchmark dataset. Experiments are also performed to analyse the benefits of the components and heuristics and their combined use to achieve a better understanding of how to better tackle the subject problem.

Citation

Curtois, T., Landa-Silva, D., Qu, Y., & Laesanklang, W. (2018). Large neighbourhood search with adaptive guided ejection search for the pickup and delivery problem with time windows. Euro Journal of Transportation and Logistics, 7(2), 151-192. https://doi.org/10.1007/s13676-017-0115-6

Journal Article Type Article
Acceptance Date Dec 26, 2017
Online Publication Date Jan 12, 2018
Publication Date 2018-06
Deposit Date Jan 9, 2018
Publicly Available Date Jan 12, 2018
Journal EURO Journal on Transportation and Logistics
Electronic ISSN 2192-4384
Publisher Springer Verlag
Peer Reviewed Peer Reviewed
Volume 7
Issue 2
Pages 151-192
DOI https://doi.org/10.1007/s13676-017-0115-6
Public URL http://eprints.nottingham.ac.uk/id/eprint/48978
Publisher URL https://link.springer.com/article/10.1007/s13676-017-0115-6
Copyright Statement Copyright information regarding this work can be found at the following address: http://creativecommons.org/licenses/by/4.0

Files


dls_ejtl2018.pdf (1.6 Mb)
PDF

Copyright Statement
Copyright information regarding this work can be found at the following address: http://creativecommons.org/licenses/by/4.0






You might also like



Downloadable Citations