Prediction of travel time using deep learning algorithms to solve TDVRPTW
Loading...
Date
2023-08-04
Authors
Ejabati Emanab, Zahra
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Vehicle routing problem (VRP) is a well-known optimization problem in logistics and operations research. This problem aims to find the optimal routes to meet customers' demands in different locations with a specific number of vehicles. Time-dependent vehicle routing problem with time window (TDVRPTW) is a type of traditional VRP that incorporates the consideration of urban traffic conditions. Classic VRP plans routes without considering the dynamic nature of travel times, assuming that the roads are free-flowing, and travel times are constant. However, in real-world scenarios, many factors can affect the travel time like traffic congestion and varying travel speeds. To overcome this limitation, TDVRPTW introduces the concept of time-dependent travel times. In TDVRPTW, travel times can vary based on the time of day, traffic congestion, road conditions, and other factors. Moreover, TDVRPTW considers time windows, which are specific time intervals during which customers must be serviced.
The accuracy of travel time estimation plays a crucial role in the performance of TDVRPTW solutions. There are different ways to predict the travel time between two locations, including model-based and data-driven methods. Data-driven methods are classified into three groups: statistical methods, basic machine learning methods, and deep learning methods. In this project, we apply deep learning algorithms to predict travel time accurately. By leveraging the power of Convolutional Neural Networks (CNN), Long Short-Term Memory (LSTM), and Temporal Convolutional Networks (TCN) architectures, our proposed algorithm demonstrated superior performance compared to existing methods. We achieved a significant improvement of 2.9% in travel time prediction accuracy.
In addition to utilizing deep learning algorithms to predict travel time, this thesis explores the use of genetic algorithms, local search, and large neighborhood search to solve TDVRPTW. Genetic algorithms are inspired by natural selection and iteratively evolve a population of potential solutions using genetic operators, to enhance the quality of the solutions over generations. To effectively manage the intensification (exploitation) and diversification (exploration) aspects in metaheuristics, local search, and large neighborhood search techniques are utilized.
In conclusion, this thesis aims to address the challenges posed by realistic and dynamic transportation systems by combining deep learning algorithms for travel time prediction and metaheuristic algorithms, in the context of the time-dependent vehicle routing problem with time windows (TDVRPTW). By integrating these techniques, we propose a comprehensive and effective approach to optimize route planning and meet customer demands efficiently.
Description
Keywords
Time Dependent Vehicle Routing Problem with Time Window (TDVRPTW), Vehicle Routing Problem (VRP), Deep learning, Travel Time estimation, Long Short Term Memory (LSTM), Convolutional Neural Network (CNN), Metaheuristic algorithm, Optimization, LSTM, CNN, TCN, Traffic management