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
² School of Computer Scicence, University of Nottingham, Nottingham, UK
³ School of Computer Scicence, The University of Nottingham Ningbo China, Ningbo, P.R. China
⁴ Department of Mathematics, Faculty of Science, Mahidol University, Bangkok, Thailand

^* Corresponding author: psxbc2@nottingham.ac.uk, BinhuiChen@sf-express.com, cbh_fzu@sina.com

Received: 6 April 2018
Accepted: 14 August 2019

Abstract

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.