Enhancing vehicle routing problem solutions through deep reinforcement learning and graph neural networks
DOI:
https://doi.org/10.35335/emod.v16i3.64Keywords:
Combinatorial Optimization, Deep Reinforcement Learning (RL), Graph Neural Networks (GNNs), Optimization, Vehicle Routing Problem (VRP)Abstract
The Vehicle Routing Problem (VRP) involves finding optimal routes for a fleet of vehicles to serve a set of clients while minimizing costs or optimizing efficiency. Scalability and uncertainty handling are issues with traditional VRP solutions. This study integrates Deep Reinforcement Learning (RL) with Graph Neural Networks (GNNs) to improve VRP solutions. Deep RL algorithms let agents learn optimal decision-making rules by interacting with the environment, whereas GNNs capture the VRP's graph representation's spatial and structural relationships. This research uses deep RL and GNNs to improve VRP solutions. The project intends to create an agent that can reason about customer, vehicle, and depot interactions and make educated routing decisions depending on the problem state by integrating deep RL agents with GNN models. Formulating the problem, preprocessing the data, constructing state and action representations, defining reward functions, training the deep RL agent and GNN models, and assessing the proposed strategy using benchmark VRP datasets. The merged deep RL-GNN technique improves VRP solutions. Optimized routing reduces travel expenses, improves resource use, and boosts efficiency. This research shows how deep RL and GNNs can overcome the limits of classic optimization methods for vehicle routing optimization. The findings emphasize the need of integrating advanced machine learning techniques into the VRP domain, enabling more effective and scalable real-world vehicle routing systems
References
Bertsimas, D., & Georghiou, A. (2015). Design of near optimal decision rules in multistage adaptive mixed-integer optimization. Operations Research, 63(3), 610–627.
Chen, Tao, Zhang, B., Pourbabak, H., Kavousi-Fard, A., & Su, W. (2016). Optimal routing and charging of an electric vehicle fleet for high-efficiency dynamic transit systems. IEEE Transactions on Smart Grid, 9(4), 3563–3572.
Chen, Tianwen, & Wong, R. C.-W. (2020). Handling information loss of graph neural networks for session-based recommendation. Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, 1172–1180.
Coelho, L. C., Renaud, J., & Laporte, G. (2016). Road-based goods transportation: a survey of real-world logistics applications from 2000 to 2015. INFOR: Information Systems and Operational Research, 54(2), 79–96.
Dixit, A., Mishra, A., & Shukla, A. (2018). Vehicle routing problem with time windows using meta-heuristic algorithms: a survey. In Harmony Search and Nature Inspired Optimization Algorithms: Theory and Applications, ICHSA 2018 (pp. 539–546). Springer.
Dong, H., Dong, H., Ding, Z., Zhang, S., & Chang. (2020). Deep Reinforcement Learning. Springer.
Everett, M., Chen, Y. F., & How, J. P. (2021). Collision avoidance in pedestrian-rich environments with deep reinforcement learning. IEEE Access, 9, 10357–10377.
Everett, M., Chen, Y. F., & How, J. P. (2018). Motion planning among dynamic, decision-making agents with deep reinforcement learning. 2018 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), 3052–3059.
Fellek, G., Gebreyesus, G., Farid, A., Fujimura, S., & Yoshie, O. (2022). Edge Encoded Attention Mechanism to Solve Capacitated Vehicle Routing Problem with Reinforcement Learning. 2022 IEEE International Conference on Industrial Engineering and Engineering Management (IEEM), 576–582.
Ghannadpour, S. F., & Zarrabi, A. (2019). Multi-objective heterogeneous vehicle routing and scheduling problem with energy minimizing. Swarm and Evolutionary Computation, 44, 728–747.
Gupta, V. (2019). Near-optimal Bayesian ambiguity sets for distributionally robust optimization. Management Science, 65(9), 4242–4260.
Joe, W., & Lau, H. C. (2020). Deep reinforcement learning approach to solve dynamic vehicle routing problem with stochastic customers. Proceedings of the International Conference on Automated Planning and Scheduling, 30, 394–402.
Karimi-Mamaghan, M., Mohammadi, M., Meyer, P., Karimi-Mamaghan, A. M., & Talbi, E.-G. (2022). Machine learning at the service of meta-heuristics for solving combinatorial optimization problems: A state-of-the-art. European Journal of Operational Research, 296(2), 393–422.
Keçeci, B., Altıparmak, F., & Kara, I. (2021). A mathematical formulation and heuristic approach for the heterogeneous fixed fleet vehicle routing problem with simultaneous pickup and delivery. Journal of Industrial and Management Optimization, 17(3), 1069–1100.
Konstantakopoulos, G. D., Gayialis, S. P., & Kechagias, E. P. (2020). Vehicle routing problem and related algorithms for logistics distribution: a literature review and classification. Operational Research, 1–30.
Li, K., Zhang, T., Wang, R., Wang, Y., Han, Y., & Wang, L. (2021). Deep reinforcement learning for combinatorial optimization: Covering salesman problems. IEEE Transactions on Cybernetics, 52(12), 13142–13155.
Li, Y., Gao, H., Gao, Y., Guo, J., & Wu, W. (2022). A survey on influence maximization: From an ml-based combinatorial optimization. ACM Transactions on Knowledge Discovery from Data.
Liao, W., Bak-Jensen, B., Pillai, J. R., Wang, Y., & Wang, Y. (2021). A review of graph neural networks and their applications in power systems. Journal of Modern Power Systems and Clean Energy, 10(2), 345–360.
Likmeta, A., Metelli, A. M., Tirinzoni, A., Giol, R., Restelli, M., & Romano, D. (2020). Combining reinforcement learning with rule-based controllers for transparent and general decision-making in autonomous driving. Robotics and Autonomous Systems, 131, 103568.
Mańdziuk, J. (2018). New shades of the vehicle routing problem: Emerging problem formulations and computational intelligence solution methods. IEEE Transactions on Emerging Topics in Computational Intelligence, 3(3), 230–244.
Marinakis, Y., Marinaki, M., & Dounias, G. (2010). A hybrid particle swarm optimization algorithm for the vehicle routing problem. Engineering Applications of Artificial Intelligence, 23(4), 463–472.
Mekrache, A., Bradai, A., Moulay, E., & Dawaliby, S. (2022). Deep reinforcement learning techniques for vehicular networks: Recent advances and future trends towards 6G. Vehicular Communications, 33, 100398.
Nguyen, H., & La, H. (2019). Review of deep reinforcement learning for robot manipulation. 2019 Third IEEE International Conference on Robotic Computing (IRC), 590–595.
Pham, Q. D., Nguyen, T. H., & Bui, Q. T. (2022). Modeling and solving a multi-trip multi-distribution center vehicle routing problem with lower-bound capacity constraints. Computers & Industrial Engineering, 172, 108597.
Poullet, J. (2020). Leveraging machine learning to solve The vehicle Routing Problem with Time Windows. Massachusetts Institute of Technology.
Qi, X., Luo, Y., Wu, G., Boriboonsomsin, K., & Barth, M. (2019). Deep reinforcement learning enabled self-learning control for energy efficient driving. Transportation Research Part C: Emerging Technologies, 99, 67–81.
Razali, N. M. (2015). An efficient genetic algorithm for large scale vehicle routing problem subject to precedence constraints. Procedia-Social and Behavioral Sciences, 195, 1922–1931.
Rougé, C., & Tilmant, A. (2016). Using stochastic dual dynamic programming in problems with multiple near‐optimal solutions. Water Resources Research, 52(5), 4151–4163.
Sangamithra, B., Neelima, P., & Kumar, M. S. (2017). A memetic algorithm for multi objective vehicle routing problem with time windows. 2017 IEEE International Conference on Electrical, Instrumentation and Communication Engineering (ICEICE), 1–8.
Shitole, V., Louis, J., & Tadepalli, P. (2019). Optimizing earth moving operations via reinforcement learning. 2019 Winter Simulation Conference (WSC), 2954–2965.
Sicilia, J. A., Quemada, C., Royo, B., & Escuin, D. (2016). An optimization algorithm for solving the rich vehicle routing problem based on Variable Neighborhood Search and Tabu Search metaheuristics. Journal of Computational and Applied Mathematics, 291, 468–477.
Suárez-Varela Macià, J. R. (2020). Enabling knowledge-defined networks: deep reinforcement learning, graph neural networks and network analytics.
Tahami, H., & Fakhravar, H. (2022). A literature review on combining heuristics and exact algorithms in combinatorial optimization. European Journal of Information Technologies and Computer Science, 2(2), 6–12.
Vesselinova, N., Steinert, R., Perez-Ramirez, D. F., & Boman, M. (2020). Learning combinatorial optimization on graphs: A survey with applications to networking. IEEE Access, 8, 120388–120416.
Wang, H., Liu, N., Zhang, Y., Feng, D., Huang, F., Li, D., & Zhang, Y. (2020). Deep reinforcement learning: a survey. Frontiers of Information Technology & Electronic Engineering, 21(12), 1726–1744.
Wang, Q., & Tang, C. (2021). Deep reinforcement learning for transportation network combinatorial optimization: A survey. Knowledge-Based Systems, 233, 107526.
Wang, Y., & Chen, Z. (2022). A Deep Reinforcement Learning Algorithm Using A New Graph Transformer Model for Routing Problems. Proceedings of SAI Intelligent Systems Conference, 365–379.
Ye, G., Tang, Z., Wang, H., Fang, D., Fang, J., Huang, S., & Wang, Z. (2020). Deep program structure modeling through multi-relational graph-based learning. Proceedings of the ACM International Conference on Parallel Architectures and Compilation Techniques, 111–123.
Zhou, J., Cui, G., Hu, S., Zhang, Z., Yang, C., Liu, Z., Wang, L., Li, C., & Sun, M. (2020). Graph neural networks: A review of methods and applications. AI Open, 1, 57–81.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2022 Zhou Cien Tien, Joe Qi-lee
This work is licensed under a Creative Commons Attribution 4.0 International License.
