Skip to main content

Research Repository

Advanced Search

A variable neighborhood search algorithm with reinforcement learning for a real-life periodic vehicle routing problem with time windows and open routes

Chen, Binhui; Qu, Rong; Bai, Ruibin; Laesanklang, Wasakorn

Authors

Binhui Chen

Rong Qu

Ruibin Bai

Wasakorn Laesanklang



Abstract

Based on a real-life container transport problem, a model of Open Periodic Vehicle Routing Problem with Time Windows (OPVRPTW) is proposed in this paper. In a wide planning horizon, which is divided into a number of shifts, a fixed number of trucks are scheduled to complete container transportation tasks between terminals subject to time constraints. In this problem, the routes traveled by trucks are open, as returning to the starting depot is not required in every single shift but every two shifts.

Our study shows that it is unrealistic to address this large scale and nonlinearly constrained problem with exact search methods. A Reinforcement Learning Based Variable Neighbourhood Search algorithm (VNSRLS) is developed for OPVRPTW. The initial solution is constructed with an urgency level-based insertion heuristic, while different insertion selection strategies are compared. In the local search phase of VNS-RLS, reinforcement learning is used to guide the search, adjusting the probabilities of operators being invoked adaptively according to the change of generated solutions’ feasibility and quality. In addition, the impact of sampling neighbourhood space in single solution-based algorithms is also investigated. Three indicators are designed in the proposed Sampling module to set the starting configuration of local search.

Experiment results on different sizes of real and artificial benchmark instances show that, the proposed Sampling scheme and feasibility indicator decrease the infeasible rate during the search. However, Sampling’s contribution to solution quality improvement is not significant in this single solution-based algorithm. Comparing to the exact search and two state-of-the-art algorithms, VNS-RLS produces promising results

Journal Article Type Article
Publication Date Aug 30, 2019
Print ISSN 0399-0559
Electronic ISSN 1290-3868
Publisher EDP Open
Peer Reviewed Peer Reviewed
APA6 Citation Chen, B., Qu, R., Bai, R., & Laesanklang, W. (2019). A variable neighborhood search algorithm with reinforcement learning for a real-life periodic vehicle routing problem with time windows and open routes. RAIRO: Operations Research, https://doi.org/10.1051/ro/2019080
DOI https://doi.org/10.1051/ro/2019080
Keywords Open Periodic Vehicle Routing Problem with Time Windows, Adaptive Operator Selection, Metaheuristics, Variable Neighbourhood Search
Publisher URL https://www.rairo-ro.org/component/article?access=doi&doi=10.1051/ro/2019080
Additional Information The original publication is available at www.rairo-ro.org. Copyright / Published by: EDP Sciences

Files





You might also like



Downloadable Citations

;