MULTIFACTOR MODEL FOR OVERCOMING THE SPARSE REWARD PROBLEM IN THE VEHICLE ROUTING PROBLEM WITH TIME WINDOWS
Keywords:
combinatorial optimization, reinforcement learning, Offline RL, Reward Shaping, ablation study, ALNSAbstract
The sparse reward problem in training Offline RL agents for VRPTW is investigated. Analyzing 12617 ALNS iterations proved the inefficiency of isolated binary signals generating 97% non-informative transitions. A complex Reward Shaping function considering cost changes, fleet size, and penalties is proposed. The ablation study confirmed that the method creates a dense gradient (98% informative iterations), acting as a strict controller of route feasibility.
References
[1] С. В. Островецький, «VRPTW-Search-Trajectories-Dataset», GitHub, 2025. [Електронний ресурс]. Режим доступу: https://github.com/SerganO/VRPTW-Search-Trajectories-Dataset
[2] W. Kool, H. van Hoof, and M. Welling, «Attention, Learn to Solve Routing Problems!», in Proc. 7th Int. Conf. on Learning Representations (ICLR), New Orleans, LA, USA, 2019. [Online]. Available: https://openreview.net/forum?id=ByxBFsRqYm
[3] S. Levine, A. Kumar, G. Tucker, and J. Fu, «Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems», arXiv preprint arXiv:2005.01643, 2020.
[4] M. Nazari, A. Oroojlooy, L. V. Snyder, and M. Takáč, «Reinforcement learning for solving the vehicle routing problem» in Advances in Neural Information Processing Systems 31 (NeurIPS), 2018, 11p.
[5] S. Ropke and D. Pisinger, «An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows», Transportation Science, vol. 40, no. 4, pp. 455-472, 2006. DOI: 10.1287/trsc.1050.0135
[6] R. S. Sutton and A. G. Barto, Reinforcement Learning: An Introduction, 2nd ed. Cambridge, MA, USA: MIT Press, 2018.
Downloads
Published
How to Cite
Issue
Section
License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
