Volume 54, Number 5, September-October 2020
|1467 - 1494
|23 July 2020
A variable neighborhood search algorithm with reinforcement learning for a real-life periodic vehicle routing problem with time windows and open routes
SF Technology Co. Ltd, Shenzhen, P.R. China
2 School of Computer Scicence, University of Nottingham, Nottingham, UK
3 School of Computer Scicence, The University of Nottingham Ningbo China, Ningbo, P.R. China
4 Department of Mathematics, Faculty of Science, Mahidol University, Bangkok, Thailand
Accepted: 14 August 2019
This paper studies a real-life container transportation problem with a wide planning horizon divided into multiple shifts. The trucks in this problem do not return to depot after every single shift but at the end of every two shifts. The mathematical model of the problem is first established, but it is unrealistic to solve this large scale problem with exact search methods. Thus, a Variable Neighbourhood Search algorithm with Reinforcement Learning (VNS-RLS) is thus developed. An urgency level-based insertion heuristic is proposed to construct the initial solution. Reinforcement learning is then used to guide the search in the local search improvement phase. Our study shows that the Sampling scheme in single solution-based algorithms does not significantly improve the solution quality but can greatly reduce the rate of infeasible solutions explored during the search. Compared to the exact search and the state-of-the-art algorithms, the proposed VNS-RLS produces promising results.
Mathematics Subject Classification: 90B06 / 90B40 / 90C27
Key words: Periodic vehicle routing problem with time windows and open routes / adaptive operator selection / metaheuristics / variable neighbourhood search
© EDP Sciences, ROADEF, SMAI 2020
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.