Enhancing Q-Learning with Vector Similarity and Tabu Search for Solving the Vehicle Routing Problem

In recent years, addressing the m-Dial-a-Ride variant of the Vehicle Routing Problem (VRP) has become an important research area. This paper presents a novel model that aims to effectively represent this variant by leveraging a combination of well-known techniques and original approaches. The model incorporates Q-learning, embedding vector-based knowledge representation and interpolation, and tabu search to improve the bus shuttle routing problem and reduce waiting times. The implementation of this model yielded satisfactory results, with a significant 27% reduction in the 90<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">th</sup> percentile waiting times for passengers. By comparing it to the optimal solution calculated using brute force in a previous paper for the same real-life dataset, the trained model’s predictions deviate on average by approximately 20% from the optimal. Considering the model was trained with a limited number of iterations and demonstrated the ability to transfer knowledge to new inputs without over-fitting, this performance is commendable. The model effectively captures the dynamics between demand and its impact on waiting times. While the model shows promise, the paper concludes with the limitations and further work that need to be addressed in future research.