{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,17]],"date-time":"2026-09-17T05:36:03Z","timestamp":1789623363214,"version":"build-2803163510"},"reference-count":39,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2024,3,28]],"date-time":"2024-03-28T00:00:00Z","timestamp":1711584000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"The National Key Research and Development Program of China","award":["2018YFB1800804"],"award-info":[{"award-number":["2018YFB1800804"]}]},{"DOI":"10.13039\/501100001809","name":"National Nature Science Foundation of China","doi-asserted-by":"crossref","award":["U1936217, 61971267, 61972223, 61941117, 61861136003"],"award-info":[{"award-number":["U1936217, 61971267, 61972223, 61941117, 61861136003"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Beijing Natural Science Foundation","award":["L182038"],"award-info":[{"award-number":["L182038"]}]},{"DOI":"10.13039\/501100017582","name":"Beijing National Research Center for Information Science and Technology","doi-asserted-by":"crossref","award":["20031887521"],"award-info":[{"award-number":["20031887521"]}],"id":[{"id":"10.13039\/501100017582","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Tsinghua University - Tencent Joint Laboratory for Internet Innovation Technology"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Intell. Syst. Technol."],"published-print":{"date-parts":[[2024,4,30]]},"abstract":"<jats:p>Vehicle routing problem with time window (VRPTW) is of great importance for a wide spectrum of services and real-life applications, such as online take-out and car-hailing platforms. A promising method should generate high-qualified solutions within limited inference time, and there are three major challenges: (a) directly optimizing the goal with several practical constraints; (b) efficiently handling individual time-window limits; and (c) modeling the cooperation among the vehicle fleet. In this article, we present an end-to-end reinforcement learning framework to solve VRPTW. First, we propose an agent model that encodes constraints into features as the input and conducts harsh policy on the output when generating deterministic results. Second, we design a time penalty augmented reward to model the time-window limits during gradient propagation. Third, we design a task handler to enable the cooperation among different vehicles. We perform extensive experiments on two real-world datasets and one public benchmark dataset. Results demonstrate that our solution improves the performance by up to 11.7% compared to other RL baselines and could generate solutions for instances within seconds, while existing heuristic baselines take for minutes as well as maintain the quality of solutions. Moreover, our solution is thoroughly analyzed with meaningful implications due to the real-time response ability.<\/jats:p>","DOI":"10.1145\/3625232","type":"journal-article","created":{"date-parts":[[2024,1,25]],"date-time":"2024-01-25T07:37:43Z","timestamp":1706168263000},"page":"1-19","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":47,"title":["Reinforcement Learning for Solving Multiple Vehicle Routing Problem with Time Window"],"prefix":"10.1145","volume":"15","author":[{"ORCID":"https:\/\/orcid.org\/0009-0008-0003-1153","authenticated-orcid":false,"given":"Zefang","family":"Zong","sequence":"first","affiliation":[{"name":"Department of Electronic Engineering, Tsinghua University, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6994-6318","authenticated-orcid":false,"given":"Xia","family":"Tong","sequence":"additional","affiliation":[{"name":"Department of Computer Science, the University of Cambridge, Cambridge, UK"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0009-6486-379X","authenticated-orcid":false,"given":"Meng","family":"Zheng","sequence":"additional","affiliation":[{"name":"Hitachi (China) Research Development Corporation, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5617-1659","authenticated-orcid":false,"given":"Yong","family":"Li","sequence":"additional","affiliation":[{"name":"Department of Electronic Engineering, Tsinghua University, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,3,28]]},"reference":[{"key":"e_1_3_2_2_2","unstructured":"Irwan Bello Hieu Pham Quoc V. Le Mohammad Norouzi and Samy Bengio. 2016. Neural Combinatorial Optimization with Reinforcement Learning. arXiv:1611.09940"},{"key":"e_1_3_2_3_2","first-page":"6278","volume-title":"Advances in Neural Information Processing Systems","author":"Chen Xinyun","year":"2019","unstructured":"Xinyun Chen and Yuandong Tian. 2019. Learning to perform local rewriting for combinatorial optimization. In Advances in Neural Information Processing Systems. 6278\u20136289."},{"key":"e_1_3_2_4_2","unstructured":"Hanjun Dai Elias B. Khalil Yuyu Zhang Bistra Dilkina and Le Song. 2017. Learning Combinatorial Optimization Algorithms over Graphs. arXiv:1704.01665"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.6.1.80"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.40.2.342"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","unstructured":"Lu Duan Yang Zhan Haoyuan Hu Yu Gong Jiangwen Wei Xiaodong Zhang and Yinghui Xu. 2020. Efficiently solving the practical vehicle routing problem: A novel joint learning approach. 3054\u20133063. DOI:10.1145\/3394486.3403356","DOI":"10.1145\/3394486.3403356"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jksus.2010.03.002"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jksus.2010.03.002"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.2019.0909"},{"key":"e_1_3_2_11_2","first-page":"63","volume-title":"New Ideas in Optimization","author":"Gambardella Luca Maria","year":"1999","unstructured":"Luca Maria Gambardella, \u00c9ric Taillard, and Giovanni Agazzi. 1999. MACS-VRPTW: A multiple colony system for vehicle routing problems with time windows. In New Ideas in Optimization. McGraw-Hill, 63\u201376."},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.2.1.4"},{"key":"e_1_3_2_13_2","article-title":"Genetic algorithms in search","author":"Goldberg David E.","year":"1989","unstructured":"David E. Goldberg. 1989. Genetic algorithms in search. Optim. Mach. Learn. (1989).","journal-title":"Optim. Mach. Learn."},{"key":"e_1_3_2_14_2","unstructured":"Google. 2016. OR-Tools. Retrieved from https:\/\/developers.google.com\/optimization\/routing"},{"key":"e_1_3_2_15_2","article-title":"Spatio-temporal capsule-based reinforcement learning for mobility-on-demand coordination","author":"He Suining","year":"2020","unstructured":"Suining He and Kang G. Shin. 2020. Spatio-temporal capsule-based reinforcement learning for mobility-on-demand coordination. IEEE Trans. Knowl. Data Eng. (2020).","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.7551\/mitpress\/1090.001.0001"},{"issue":"1","key":"e_1_3_2_17_2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3412363","article-title":"Dynamic graph mining for multi-weight multi-destination route planning with deadlines constraints","volume":"15","author":"Huang Yu","year":"2020","unstructured":"Yu Huang, Josh Jia-Ching Ying, Philip S. Yu, and Vincent S. Tseng. 2020. Dynamic graph mining for multi-weight multi-destination route planning with deadlines constraints. ACM Trans. Knowl. Discov. Data 15, 1 (2020), 1\u201332.","journal-title":"ACM Trans. Knowl. Discov. Data"},{"key":"e_1_3_2_18_2","article-title":"Learning to delay in ride-sourcing systems: A multi-agent deep reinforcement learning framework","author":"Jintao K. E.","year":"2020","unstructured":"K. E. Jintao, Hai Yang, Jieping Ye, et\u00a0al. 2020. Learning to delay in ride-sourcing systems: A multi-agent deep reinforcement learning framework. IEEE Trans. Knowl. Data Eng. (2020).","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"e_1_3_2_19_2","unstructured":"Wouter Kool Herke van Hoof and Max Welling. 2018. Attention Learn to Solve Routing Problems! arXiv:1704.01665"},{"key":"e_1_3_2_20_2","article-title":"Cost optimization of the supply chain network using genetic algorithms-Withdrawn","author":"Lau Henry C. W.","year":"2009","unstructured":"Henry C. W. Lau, T. M. Chan, Wan Ting Tsui, and G. T. S. Ho. 2009. Cost optimization of the supply chain network using genetic algorithms-Withdrawn. IEEE Trans. Knowl. Data Eng. (2009).","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0377-2217(02)00486-1"},{"key":"e_1_3_2_22_2","article-title":"Deep reinforcement learning for electric vehicle routing problem with time windows","author":"Lin Bo","year":"2020","unstructured":"Bo Lin, Bissan Ghaddar, and Jatin Nathwani. 2020. Deep reinforcement learning for electric vehicle routing problem with time windows. arXiv preprint arXiv:2010.02068 (2020).","journal-title":"arXiv preprint arXiv:2010.02068"},{"key":"e_1_3_2_23_2","volume-title":"Vehicle Routing with Time Windows: Two Optimization Algorithms","author":"Madsen Oli B. G.","year":"1997","unstructured":"Oli B. G. Madsen, Marshall L. Fisher, and Kurt O. Jornsten. 1997. Vehicle Routing with Time Windows: Two Optimization Algorithms."},{"key":"e_1_3_2_24_2","unstructured":"Mohammadreza Nazari Afshin Oroojlooy Lawrence V. Snyder and Martin Tak\u00e1\u010d. 2018. Reinforcement Learning for Solving the Vehicle Routing Problem. arXiv:1802.04240"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-020-01523-z"},{"key":"e_1_3_2_26_2","unstructured":"Chengming Qi and Yunchuan Sun. 2008. An improved ant colony algorithm for VRPTW. 1 (2008) 455\u2013458."},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1006\/jcph.1999.6413"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1109\/TITS.2019.2947408"},{"key":"e_1_3_2_29_2","volume-title":"Reinforcement Learning: An Introduction","author":"Sutton Richard S.","year":"2018","unstructured":"Richard S. Sutton and Andrew G. Barto. 2018. Reinforcement Learning: An Introduction. MIT Press."},{"key":"e_1_3_2_30_2","article-title":"Learning to solve soft-constrained vehicle routing problems with lagrangian relaxation","author":"Tang Qiaoyue","year":"2022","unstructured":"Qiaoyue Tang, Yangzhe Kong, Lemeng Pan, and Choonmeng Lee. 2022. Learning to solve soft-constrained vehicle routing problems with lagrangian relaxation. arXiv preprint arXiv:2207.09860 (2022).","journal-title":"arXiv preprint arXiv:2207.09860"},{"key":"e_1_3_2_31_2","article-title":"The vehicle routing problem. Monographs","author":"Toth P.","year":"2002","unstructured":"P. Toth and D. Vigo. 2002. The vehicle routing problem. Monographs. In Discrete Mathematics and Applications, Society for Industrial and Applied Mathematics. SIAM.","journal-title":"Discrete Mathematics and Applications, Society for Industrial and Applied Mathematics"},{"key":"e_1_3_2_32_2","first-page":"5998","volume-title":"Advances in Neural Information Processing Systems","author":"Vaswani Ashish","year":"2017","unstructured":"Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, \u0141ukasz Kaiser, and Illia Polosukhin. 2017. Attention is all you need. In Advances in Neural Information Processing Systems. 5998\u20136008."},{"key":"e_1_3_2_33_2","first-page":"2692","volume-title":"Advances in Neural Information Processing Systems","author":"Vinyals Oriol","year":"2015","unstructured":"Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. 2015. Pointer networks. In Advances in Neural Information Processing Systems. 2692\u20132700."},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1145\/3292500.3330824"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF00992696"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1145\/3360048"},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ins.2019.03.070"},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2016.2604806"},{"key":"e_1_3_2_39_2","first-page":"311264","volume-title":"Proceedings of the International Conference on Artificial Intelligence","author":"Zhu Kenny Qili","year":"2000","unstructured":"Kenny Qili Zhu. 2000. A new genetic algorithm for VRPTW. In Proceedings of the International Conference on Artificial Intelligence. 311264."},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v36i9.21236"}],"container-title":["ACM Transactions on Intelligent Systems and Technology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3625232","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3625232","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T18:50:04Z","timestamp":1750272604000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3625232"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,3,28]]},"references-count":39,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,4,30]]}},"alternative-id":["10.1145\/3625232"],"URL":"https:\/\/doi.org\/10.1145\/3625232","relation":{},"ISSN":["2157-6904","2157-6912"],"issn-type":[{"value":"2157-6904","type":"print"},{"value":"2157-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,3,28]]},"assertion":[{"value":"2022-09-13","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-05-20","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-03-28","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}