{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:22:49Z","timestamp":1750220569980,"version":"3.41.0"},"reference-count":51,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2021,9,3]],"date-time":"2021-09-03T00:00:00Z","timestamp":1630627200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Spatial Algorithms Syst."],"published-print":{"date-parts":[[2021,12,31]]},"abstract":"<jats:p>\n            The Vehicle Routing Problem (VRP) is an NP hard problem where we need to optimize itineraries for agents to visit multiple targets. When considering real-world travel (road-network topology, speed limits and traffic), modern VRP\n            <jats:italic>solvers<\/jats:italic>\n            can only process small instances with a few hundred targets. We propose a framework (VRPDiv) that can scale any\n            <jats:italic>solver<\/jats:italic>\n            to support larger VRP instances with up to ten thousand targets (10k) by dividing them into smaller clusters. VRPDiv supports the multiple VRP scenarios and contains a pool of clustering algorithms from which it chooses the ideal one depending on properties of the instance. VRPDiv assigns agents based on cluster demand and targets compatibility (i.e. realizable time-windows and capacity limitations). We incorporate the framework into the Bing Maps Multi-Itinerary Optimization (MIO)\n            <jats:sup>1<\/jats:sup>\n            online service. This architecture allows MIO to scale up from solving instances with a few hundred to over 10k targets in under 10 minutes. We evaluate our framework on public datasets and publish a new dataset ourselves, as large enough instances supporting real-world travel were impossible to find. We investigate multiple clustering methods and show that choosing the correct one is critical with differences of up to 60% in quality. We compare with relevant baselines and report a 40% improvement in target allocation and a 9.8% improvement in itinerary durations. We compare with existing scores and report an average delta of 10%, with lower values (&lt;5%) in instances with low workload (few targets per agent), which are acceptable for an online service.\n          <\/jats:p>","DOI":"10.1145\/3474832","type":"journal-article","created":{"date-parts":[[2021,9,4]],"date-time":"2021-09-04T03:45:43Z","timestamp":1630727143000},"page":"1-41","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["VRPDiv: A Divide and Conquer Framework for Large Vehicle Routing Problems"],"prefix":"10.1145","volume":"7","author":[{"given":"Radu","family":"Mariescu-Istodor","sequence":"first","affiliation":[{"name":"Microsoft, Timi\u0219oara, Romania and University of Eastern Finland, Joensuu, Finland"}]},{"given":"Alexandru","family":"Cristian","sequence":"additional","affiliation":[{"name":"Microsoft, Timi\u0219oara, Romania"}]},{"given":"Mihai","family":"Negrea","sequence":"additional","affiliation":[{"name":"Microsoft, Timi\u0219oara, Romania"}]},{"given":"Peiwei","family":"Cao","sequence":"additional","affiliation":[{"name":"Microsoft, Seattle, WA, USA"}]}],"member":"320","published-online":{"date-parts":[[2021,9,3]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.6.1.80"},{"key":"e_1_2_1_2_1","volume-title":"(Eds.)","author":"Golden B. L.","year":"2008","unstructured":"B. L. Golden , S. Raghavan , and E. A. Wasil . (Eds.) . 2008 . The vehicle routing problem: Latest advances and new challenges (Vol. 43). Springer Science & Business Media . B. L. Golden, S. Raghavan, and E. A. Wasil. (Eds.). 2008. The vehicle routing problem: Latest advances and new challenges (Vol. 43). Springer Science & Business Media."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10732-005-5431-6"},{"key":"e_1_2_1_4_1","doi-asserted-by":"crossref","unstructured":"M. Gendreau J. Y. Potvin O. Br\u00e4umlaysy G. Hasle and A. L\u00f8kketangen. 2008. Metaheuristics for the vehicle routing problem and its extensions: A categorized bibliography. In The Vehicle Routing Problem: Latest Advances and New Challenges (pp. 143\u2013169). Springer Boston MA.  M. Gendreau J. Y. Potvin O. Br\u00e4umlaysy G. Hasle and A. L\u00f8kketangen. 2008. Metaheuristics for the vehicle routing problem and its extensions: A categorized bibliography. In The Vehicle Routing Problem: Latest Advances and New Challenges (pp. 143\u2013169). Springer Boston MA.","DOI":"10.1007\/978-0-387-77778-8_7"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cie.2015.12.007"},{"key":"e_1_2_1_6_1","unstructured":"Li et al. 2019. A pedestrian level strategy to minimize outdoor sunlight exposure in hot summer. arXiv:1910.04312.  Li et al. 2019. A pedestrian level strategy to minimize outdoor sunlight exposure in hot summer. arXiv:1910.04312."},{"key":"e_1_2_1_7_1","doi-asserted-by":"crossref","unstructured":"Krumm and Horvitz. 2017. Risk-aware planning: Methods and case study for safer driving routes. In AAAI (pp. 4708\u20134714).  Krumm and Horvitz. 2017. Risk-aware planning: Methods and case study for safer driving routes. In AAAI (pp. 4708\u20134714).","DOI":"10.1609\/aaai.v31i2.19099"},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","unstructured":"Kuo and Wang. 2011. Optimizing the VRP by minimizing fuel consumption. Management of Environmental Quality: An International Journal.  Kuo and Wang. 2011. Optimizing the VRP by minimizing fuel consumption. Management of Environmental Quality: An International Journal.","DOI":"10.1108\/14777831111136054"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.eswa.2013.07.107"},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","unstructured":"A. Gagliano P. G. Villani A. Manelli S. Paglia P. A. Bisagni G. M. Perotti and M. Lombardo. 2020. COVID-19 epidemic in the middle province of Northern Italy: Impact logistics and strategy in the first line hospital. Disaster Medicine and Public Health Preparedness 1\u20135.  A. Gagliano P. G. Villani A. Manelli S. Paglia P. A. Bisagni G. M. Perotti and M. Lombardo. 2020. COVID-19 epidemic in the middle province of Northern Italy: Impact logistics and strategy in the first line hospital. Disaster Medicine and Public Health Preparedness 1\u20135.","DOI":"10.1017\/dmp.2020.51"},{"key":"e_1_2_1_11_1","unstructured":"D. L. Applegate R. M. Bixby and V. Cook Chv\u00e1tal. 2006. The traveling salesman problem.  D. L. Applegate R. M. Bixby and V. Cook Chv\u00e1tal. 2006. The traveling salesman problem."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.3390\/app9193985"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.46.3.316"},{"volume-title":"Proceedings of the 27th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (pp. 279\u2013288)","author":"Cristian A.","key":"e_1_2_1_14_1","unstructured":"A. Cristian , L. Marshall , M. Negrea , F. Stoichescu , P. Cao , and I. Menache . 2019. Multi-itinerary optimization as cloud service (Industrial Paper) . In Proceedings of the 27th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (pp. 279\u2013288) . A. Cristian, L. Marshall, M. Negrea, F. Stoichescu, P. Cao, and I. Menache. 2019. Multi-itinerary optimization as cloud service (Industrial Paper). In Proceedings of the 27th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (pp. 279\u2013288)."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0377-2217(99)00284-2"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2018.06.039"},{"key":"e_1_2_1_17_1","unstructured":"T. H. Cormen C. E. Leiserson R. L. Rivest and C. Stein. 2009. Introduction to Algorithms. MIT press.  T. H. Cormen C. E. Leiserson R. L. Rivest and C. Stein. 2009. Introduction to Algorithms. MIT press."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.3.4.376"},{"key":"e_1_2_1_19_1","volume-title":"Fast travel-distance estimation using overhead graph. Journal of Location Based Services","author":"Mariescu-Istodor Radu","year":"2021","unstructured":"Radu Mariescu-Istodor and Pasi Fr\u00e4nti . 2021. Fast travel-distance estimation using overhead graph. Journal of Location Based Services ( 2021 ), 1\u201319. Radu Mariescu-Istodor and Pasi Fr\u00e4nti. 2021. Fast travel-distance estimation using overhead graph. Journal of Location Based Services (2021), 1\u201319."},{"key":"e_1_2_1_20_1","volume-title":"Hybrid genetic search for the CVRP: Open-source implementation and SWAP* Neighborhood. arXiv preprint arXiv:2012.10384","author":"Vidal Thibaut","year":"2020","unstructured":"Thibaut Vidal . 2020. Hybrid genetic search for the CVRP: Open-source implementation and SWAP* Neighborhood. arXiv preprint arXiv:2012.10384 ( 2020 ). Thibaut Vidal. 2020. Hybrid genetic search for the CVRP: Open-source implementation and SWAP* Neighborhood. arXiv preprint arXiv:2012.10384 (2020)."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10732-014-9251-4"},{"key":"e_1_2_1_22_1","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 2000. Kenny Qili Zhu. 2000. A new genetic algorithm for VRPTW. In Proceedings of the International Conference on Artificial Intelligence 2000."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/CSSE.2008.1339"},{"volume-title":"International Workshop on Experimental and Efficient Algorithms (pp. 319\u2013333)","author":"Geisberger R.","key":"e_1_2_1_24_1","unstructured":"R. Geisberger , P. Sanders , D. Schultes , and D. Delling . 2008. Contraction hierarchies: Faster and simpler hierarchical routing in road networks . In International Workshop on Experimental and Efficient Algorithms (pp. 319\u2013333) . Springer, Berlin. R. Geisberger, P. Sanders, D. Schultes, and D. Delling. 2008. Contraction hierarchies: Faster and simpler hierarchical routing in road networks. In International Workshop on Experimental and Efficient Algorithms (pp. 319\u2013333). Springer, Berlin."},{"volume-title":"International Symposium on Experimental Algorithms (pp. 100\u2013111)","author":"Geisberger R.","key":"e_1_2_1_25_1","unstructured":"R. Geisberger and C. Vetter . 2011. Efficient routing in road networks with turn costs . In International Symposium on Experimental Algorithms (pp. 100\u2013111) . Springer, Berlin. R. Geisberger and C. Vetter. 2011. Efficient routing in road networks with turn costs. In International Symposium on Experimental Algorithms (pp. 100\u2013111). Springer, Berlin."},{"key":"e_1_2_1_26_1","first-page":"768","article-title":"Cluster analysis of multivariate data: Efficiency versus interpretability of classifications","volume":"21","author":"Forgy E. W.","year":"1965","unstructured":"E. W. Forgy . 1965 . Cluster analysis of multivariate data: Efficiency versus interpretability of classifications . Biometrics 21 (1965), 768 \u2013 769 . E. W. Forgy. 1965. Cluster analysis of multivariate data: Efficiency versus interpretability of classifications. Biometrics 21 (1965), 768\u2013769.","journal-title":"Biometrics"},{"key":"e_1_2_1_27_1","volume-title":"Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability 1, 14","author":"MacQueen J.","year":"1967","unstructured":"J. MacQueen . 1967 . Some methods for classification and analysis of multivariate observations . In Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability 1, 14 , 281\u2013297. J. MacQueen. 1967. Some methods for classification and analysis of multivariate observations. In Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability 1, 14, 281\u2013297."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1982.1056489"},{"volume-title":"Joint IAPR International Workshops on Statistical Techniques in Pattern Recognition (SPR) and Structural and Syntactic Pattern Recognition (SSPR) (pp. 32\u201341)","author":"Malinen M. I.","key":"e_1_2_1_29_1","unstructured":"M. I. Malinen and P. Fr\u00e4nti . 2014. Balanced k-means for clustering . In Joint IAPR International Workshops on Statistical Techniques in Pattern Recognition (SPR) and Structural and Syntactic Pattern Recognition (SSPR) (pp. 32\u201341) . Springer, Berlin. M. I. Malinen and P. Fr\u00e4nti. 2014. Balanced k-means for clustering. In Joint IAPR International Workshops on Statistical Techniques in Pattern Recognition (SPR) and Structural and Syntactic Pattern Recognition (SSPR) (pp. 32\u201341). Springer, Berlin."},{"key":"e_1_2_1_30_1","doi-asserted-by":"crossref","unstructured":"R. Burkard M. Dell'Amico and S. Martello. 2012. Assignment problems revised reprint (Vol. 106). Siam.  R. Burkard M. Dell'Amico and S. Martello. 2012. Assignment problems revised reprint (Vol. 106). Siam.","DOI":"10.1137\/1.9781611972238"},{"key":"e_1_2_1_31_1","first-page":"727","article-title":"X-means: Extending k-means with efficient estimation of the number of clusters","volume":"1","author":"Pelleg D.","year":"2000","unstructured":"D. Pelleg and A. W. Moore . 2000 . X-means: Extending k-means with efficient estimation of the number of clusters . In Icml 1 (2000), 727 \u2013 734 . D. Pelleg and A. W. Moore. 2000. X-means: Extending k-means with efficient estimation of the number of clusters. In Icml 1 (2000), 727\u2013734.","journal-title":"Icml"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/s100440070007"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/0-387-25465-X_15"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/16.1.30"},{"key":"e_1_2_1_35_1","volume-title":"Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data (pp. 443\u2013454)","author":"Mamoulis M. L.","year":"2004","unstructured":"M. L. Yiuand N. Mamoulis . 2004 . Clustering objects on a spatial network . In Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data (pp. 443\u2013454) . M. L. Yiuand N. Mamoulis. 2004. Clustering objects on a spatial network. In Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data (pp. 443\u2013454)."},{"key":"e_1_2_1_36_1","first-page":"1","article-title":"An introduction to MDS. Sound Quality Research Unit, Aalborg University","volume":"46","author":"Wickelmaier F.","year":"2003","unstructured":"F. Wickelmaier . 2003 . An introduction to MDS. Sound Quality Research Unit, Aalborg University , Denmark 46 , 5 (2003), 1 \u2013 26 . F. Wickelmaier. 2003. An introduction to MDS. Sound Quality Research Unit, Aalborg University, Denmark 46, 5 (2003), 1\u201326.","journal-title":"Denmark"},{"volume-title":"International Conference on Geographic Information Science (pp. 85\u201399)","author":"Kaiser C.","key":"e_1_2_1_37_1","unstructured":"C. Kaiser , F. Walsh , C. J. Farmer , and A. Pozdnoukhov . 2010. User-centric time-distance representation of road networks . In International Conference on Geographic Information Science (pp. 85\u201399) . Springer, Berlin. C. Kaiser, F. Walsh, C. J. Farmer, and A. Pozdnoukhov. 2010. User-centric time-distance representation of road networks. In International Conference on Geographic Information Science (pp. 85\u201399). Springer, Berlin."},{"key":"e_1_2_1_38_1","unstructured":"L. Marshall and T. Tankayev. Practical risk modeling for the stochastic technician routing and scheduling problem.  L. Marshall and T. Tankayev. Practical risk modeling for the stochastic technician routing and scheduling problem."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2019.03.006"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2016.08.012"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1080\/00330124.2011.583586"},{"key":"e_1_2_1_42_1","volume-title":"Pattern recognition with fuzzy objective function algorithms","author":"Bezdek C. James","year":"2013","unstructured":"C. James Bezdek . 2013. Pattern recognition with fuzzy objective function algorithms . Springer Science & Business Media 2013 . C. James Bezdek. 2013. Pattern recognition with fuzzy objective function algorithms. Springer Science & Business Media 2013."},{"key":"e_1_2_1_43_1","first-page":"226","article-title":"A density-based algorithm for discovering clusters in large spatial databases with noise","volume":"96","author":"Ester Martin","year":"1996","unstructured":"Martin Ester , Hans-Peter Kriegel , J\u00f6rg Sander , and Xiaowei Xu . 1996 . A density-based algorithm for discovering clusters in large spatial databases with noise . In Kdd 96 , 34 (1996), 226 \u2013 231 . Martin Ester, Hans-Peter Kriegel, J\u00f6rg Sander, and Xiaowei Xu. 1996. A density-based algorithm for discovering clusters in large spatial databases with noise. In Kdd 96, 34 (1996), 226\u2013231.","journal-title":"Kdd"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2018.00058"},{"key":"e_1_2_1_45_1","volume-title":"The optimal sequenced route query. The VLDB Journal 17. 4","author":"Sharifzadeh Mehdi","year":"2008","unstructured":"Mehdi Sharifzadeh and Mohammad Kolahdouzan , and Cyrus Shahabi . 2008. The optimal sequenced route query. The VLDB Journal 17. 4 ( 2008 ), 765\u2013787. Mehdi Sharifzadeh and Mohammad Kolahdouzan, and Cyrus Shahabi. 2008. The optimal sequenced route query. The VLDB Journal 17. 4 (2008), 765\u2013787."},{"key":"e_1_2_1_46_1","first-page":"147","volume-title":"2014 IEEE 30th International Conference on Data Engineering","author":"Bin Yang","year":"2014","unstructured":"Yang Bin , Chenjuan Guo , Christian S. Jensen , Manohar Kaul , and Shuo Shang . 2014 . Stochastic skyline route planning under time-varying uncertainty . In 2014 IEEE 30th International Conference on Data Engineering pp. 136\u2013 147 . IEEE, 2014. Yang Bin, Chenjuan Guo, Christian S. Jensen, Manohar Kaul, and Shuo Shang. 2014. Stochastic skyline route planning under time-varying uncertainty. In 2014 IEEE 30th International Conference on Data Engineering pp. 136\u2013147. IEEE, 2014."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-017-0491-4"},{"key":"e_1_2_1_48_1","volume-title":"Worst-case analysis of a new heuristic for the travelling salesman problem","author":"Christofides Nicos","year":"1976","unstructured":"Nicos Christofides . 1976. Worst-case analysis of a new heuristic for the travelling salesman problem . Carnegie-Mellon Univ Pittsburgh Pa Management Sciences Research Group 1976 . Nicos Christofides. 1976. Worst-case analysis of a new heuristic for the travelling salesman problem. Carnegie-Mellon Univ Pittsburgh Pa Management Sciences Research Group 1976."},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/290179.290180"},{"key":"e_1_2_1_50_1","volume-title":"Cook","author":"Applegate David L.","year":"2011","unstructured":"David L. Applegate , Robert E. Bixby , Va\u0161ek Chv\u00e1tal , and William J . Cook . 2011 . The Traveling Salesman Problem. Princeton university press . David L. Applegate, Robert E. Bixby, Va\u0161ek Chv\u00e1tal, and William J. Cook. 2011. The Traveling Salesman Problem. Princeton university press."},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1136\/bmjopen-2016-013059"}],"container-title":["ACM Transactions on Spatial Algorithms and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3474832","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3474832","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:28:44Z","timestamp":1750195724000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3474832"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,9,3]]},"references-count":51,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,12,31]]}},"alternative-id":["10.1145\/3474832"],"URL":"https:\/\/doi.org\/10.1145\/3474832","relation":{},"ISSN":["2374-0353","2374-0361"],"issn-type":[{"type":"print","value":"2374-0353"},{"type":"electronic","value":"2374-0361"}],"subject":[],"published":{"date-parts":[[2021,9,3]]},"assertion":[{"value":"2020-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-09-03","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}