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

Abstract

© EDP Sciences, ROADEF, SMAI 2020. 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.