Variable-depth adaptive large neighbourhood search algorithm for open periodic vehicle routing problem with time windows

Chen, Binhui1; Qu, Rong1; Ishibuchi, Hisao2,3

2017

19th International Conference on Harbor, Maritime and Multimodal Logistics Modeling and Simulation, HMS 2017

25-34

Barcelona, Spain

CAL-TEK S.r.l.

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 wellbalanced 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.

其他

EI

University of Nottingham[] ; Ningbo Municipal Bureau of Science and Technology[2014A35006] ; National Graduate School in Computer Science[]

20174804471647

Benchmarking ; Economic and social effects ; Electronic trading ; Routing algorithms ; Vehicles

Computer Software, Data Handling and Applications:723 ; Computer Applications:723.5 ; Social Sciences:971

EV Compendex

1.School of Computer Science, University of Nottingham, United Kingdom
2.Department of Computer Science and Engineering, Southern University of Science and Technology, Shenzhen, China
3.Department of Computer Science and Intelligent Systems, Osaka Prefecture University, Japan

Chen, Binhui,Qu, Rong,Ishibuchi, Hisao. Variable-depth adaptive large neighbourhood search algorithm for open periodic vehicle routing problem with time windows[C]:CAL-TEK S.r.l.,2017:25-34.