Variable-depth adaptive large meighbourhood search algorithm for Open Periodic Vehicle Routing Problem with time windows
The Open Periodic Vehicle Routing Problem with Time Windows (OPVRPTW) is a practical transportation routing and scheduling problem arising from real-world scenarios. It shares some common features with some classic VRP variants. The problem has a tightly constrained large-scale solution space and re...
| Main Authors: | , , |
|---|---|
| Format: | Conference or Workshop Item |
| Published: |
2017
|
| Online Access: | https://eprints.nottingham.ac.uk/48713/ |
| _version_ | 1848797830599147520 |
|---|---|
| author | Chen, Binhui Qu, Rong Ishibuchi, Hisao |
| author_facet | Chen, Binhui Qu, Rong Ishibuchi, Hisao |
| author_sort | Chen, Binhui |
| building | Nottingham Research Data Repository |
| collection | Online Access |
| description | The Open Periodic Vehicle Routing Problem with Time Windows (OPVRPTW) is a practical transportation routing and scheduling problem arising from real-world scenarios. It shares some common features with some classic VRP variants. The problem has a tightly constrained large-scale solution space and requires well balanced diversification and intensification in search. In Variable Depth Neighbourhood Search, large neighbourhood depth prevents the search from trapping into local optima prematurely, while small depth provides thorough exploitation in local areas. Considering the multi-dimensional solution structure and tight constraints in OPVRPTW, a Variable-Depth Adaptive Large Neighbourhood Search (VD-ALNS) algorithm is proposed in this paper. Contributions of four tailored destroy operators and three repair operators at variable depths are investigated. Comparing to existing methods, VD-ALNS makes a good trade-off between exploration and exploitation, and produces promising results on both small and large size benchmark instances. |
| first_indexed | 2025-11-14T20:10:07Z |
| format | Conference or Workshop Item |
| id | nottingham-48713 |
| institution | University of Nottingham Malaysia Campus |
| institution_category | Local University |
| last_indexed | 2025-11-14T20:10:07Z |
| publishDate | 2017 |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | nottingham-487132020-05-04T19:07:28Z https://eprints.nottingham.ac.uk/48713/ Variable-depth adaptive large meighbourhood search algorithm for Open Periodic Vehicle Routing Problem with time windows Chen, Binhui Qu, Rong Ishibuchi, Hisao The Open Periodic Vehicle Routing Problem with Time Windows (OPVRPTW) is a practical transportation routing and scheduling problem arising from real-world scenarios. It shares some common features with some classic VRP variants. The problem has a tightly constrained large-scale solution space and requires well balanced diversification and intensification in search. In Variable Depth Neighbourhood Search, large neighbourhood depth prevents the search from trapping into local optima prematurely, while small depth provides thorough exploitation in local areas. Considering the multi-dimensional solution structure and tight constraints in OPVRPTW, a Variable-Depth Adaptive Large Neighbourhood Search (VD-ALNS) algorithm is proposed in this paper. Contributions of four tailored destroy operators and three repair operators at variable depths are investigated. Comparing to existing methods, VD-ALNS makes a good trade-off between exploration and exploitation, and produces promising results on both small and large size benchmark instances. 2017-09-18 Conference or Workshop Item PeerReviewed Chen, Binhui, Qu, Rong and Ishibuchi, Hisao (2017) Variable-depth adaptive large meighbourhood search algorithm for Open Periodic Vehicle Routing Problem with time windows. In: The 19th International Conference on Harbor, Maritime & Multimodal Logistics Modelling and Simulation, 18-20 September 2017, Barcellona, Spain. http://www.msc-les.org/proceedings/hms/hms2017/hms2017_25.html |
| spellingShingle | Chen, Binhui Qu, Rong Ishibuchi, Hisao Variable-depth adaptive large meighbourhood search algorithm for Open Periodic Vehicle Routing Problem with time windows |
| title | Variable-depth adaptive large meighbourhood search algorithm for Open Periodic Vehicle Routing Problem with time windows |
| title_full | Variable-depth adaptive large meighbourhood search algorithm for Open Periodic Vehicle Routing Problem with time windows |
| title_fullStr | Variable-depth adaptive large meighbourhood search algorithm for Open Periodic Vehicle Routing Problem with time windows |
| title_full_unstemmed | Variable-depth adaptive large meighbourhood search algorithm for Open Periodic Vehicle Routing Problem with time windows |
| title_short | Variable-depth adaptive large meighbourhood search algorithm for Open Periodic Vehicle Routing Problem with time windows |
| title_sort | variable-depth adaptive large meighbourhood search algorithm for open periodic vehicle routing problem with time windows |
| url | https://eprints.nottingham.ac.uk/48713/ https://eprints.nottingham.ac.uk/48713/ |