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

Binhui Chen, Rong Qu, Ruibin Bai, Wasakorn Laesanklang

Research output: Journal PublicationArticlepeer-review

10 Citations (Scopus)

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.

Original languageEnglish
Pages (from-to)1467-1494
Number of pages28
JournalRAIRO - Operations Research
Volume54
Issue number5
DOIs
Publication statusPublished - 1 Sep 2020

Keywords

  • Adaptive operator selection
  • Metaheuristics
  • Periodic vehicle routing problem with time windows and open routes
  • Variable neighbourhood search

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science Applications
  • Management Science and Operations Research

Fingerprint

Dive into the research topics of 'A variable neighborhood search algorithm with reinforcement learning for a real-life periodic vehicle routing problem with time windows and open routes'. Together they form a unique fingerprint.

Cite this