Large neighbourhood search with adaptive guided ejection search for the pickup and delivery problem with time windows
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 u...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Published: |
Springer
2018
|
| Online Access: | https://eprints.nottingham.ac.uk/48978/ |
| _version_ | 1848797893818843136 |
|---|---|
| author | Curtois, Timothy Landa-Silva, Dario Qu, Yi Laesanklang, Wasakorn |
| author_facet | Curtois, Timothy Landa-Silva, Dario Qu, Yi Laesanklang, Wasakorn |
| author_sort | Curtois, Timothy |
| building | Nottingham Research Data Repository |
| collection | Online Access |
| description | 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 data set. Experiments are also performed to analyse the benefits of the components and heuristics and their combined use in order to achieve a better understanding of how to better tackle the subject problem. |
| first_indexed | 2025-11-14T20:11:07Z |
| format | Article |
| id | nottingham-48978 |
| institution | University of Nottingham Malaysia Campus |
| institution_category | Local University |
| last_indexed | 2025-11-14T20:11:07Z |
| publishDate | 2018 |
| publisher | Springer |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | nottingham-489782020-05-04T19:43:52Z https://eprints.nottingham.ac.uk/48978/ 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 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 data set. Experiments are also performed to analyse the benefits of the components and heuristics and their combined use in order to achieve a better understanding of how to better tackle the subject problem. Springer 2018-06-30 Article PeerReviewed Curtois, Timothy, Landa-Silva, Dario, Qu, Yi and Laesanklang, Wasakorn (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). pp. 151-192. ISSN 2192-4376 https://link.springer.com/article/10.1007/s13676-017-0115-6 doi:10.1007/s13676-017-0115-6 doi:10.1007/s13676-017-0115-6 |
| spellingShingle | Curtois, Timothy Landa-Silva, Dario Qu, Yi Laesanklang, Wasakorn Large neighbourhood search with adaptive guided ejection search for the pickup and delivery problem with time windows |
| title | Large neighbourhood search with adaptive guided ejection search for the pickup and delivery problem with time windows |
| title_full | Large neighbourhood search with adaptive guided ejection search for the pickup and delivery problem with time windows |
| title_fullStr | Large neighbourhood search with adaptive guided ejection search for the pickup and delivery problem with time windows |
| title_full_unstemmed | Large neighbourhood search with adaptive guided ejection search for the pickup and delivery problem with time windows |
| title_short | Large neighbourhood search with adaptive guided ejection search for the pickup and delivery problem with time windows |
| title_sort | large neighbourhood search with adaptive guided ejection search for the pickup and delivery problem with time windows |
| url | https://eprints.nottingham.ac.uk/48978/ https://eprints.nottingham.ac.uk/48978/ https://eprints.nottingham.ac.uk/48978/ |