{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:19:53Z","timestamp":1750220393892,"version":"3.41.0"},"reference-count":24,"publisher":"Association for Computing Machinery (ACM)","issue":"11","license":[{"start":{"date-parts":[[2021,10,25]],"date-time":"2021-10-25T00:00:00Z","timestamp":1635120000000},"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":["Commun. ACM"],"published-print":{"date-parts":[[2021,11]]},"abstract":"<jats:p>In this paper, we describe multi-itinerary optimization (MIO)---a novel Bing Maps service that automates the process of building itineraries for multiple agents while optimizing their routes to minimize travel time or distance. MIO can be used by organizations with a fleet of vehicles and drivers, mobile salesforce, or a team of personnel in the field, to maximize workforce efficiency. It supports a variety of constraints, such as service time windows, duration, priority, pickup and delivery dependencies, and vehicle capacity. MIO also considers traffic conditions between locations, resulting in algorithmic challenges at multiple levels (e.g., calculating time-dependent travel-time distance matrices at scale and scheduling services for multiple agents).<\/jats:p>\n          <jats:p>To support an end-to-end cloud service with turnaround times of a few seconds, our algorithm design targets a sweet spot between accuracy and performance. Toward that end, we build a scalable approach based on the ALNS metaheuristic. Our experiments show that accounting for traffic significantly improves solution quality: MIO finds efficient routes that avoid late arrivals, whereas traffic-agnostic approaches result in a 15% increase in the combined travel time and the lateness of an arrival. Furthermore, our approach generates itineraries with substantially higher quality than a cutting-edge heuristic (LKH), with faster running times for large instances.<\/jats:p>","DOI":"10.1145\/3485626","type":"journal-article","created":{"date-parts":[[2021,10,25]],"date-time":"2021-10-25T15:13:37Z","timestamp":1635174817000},"page":"121-129","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Multi-itinerary optimization as cloud service"],"prefix":"10.1145","volume":"64","author":[{"given":"Alexandru","family":"Cristian","sequence":"first","affiliation":[{"name":"Microsoft Research, Redmond, WA"}]},{"given":"Luke","family":"Marshall","sequence":"additional","affiliation":[{"name":"Microsoft Research, Redmond, WA"}]},{"given":"Mihai","family":"Negrea","sequence":"additional","affiliation":[{"name":"Microsoft Research, Redmond, WA"}]},{"given":"Flavius","family":"Stoichescu","sequence":"additional","affiliation":[{"name":"Microsoft Research, Redmond, WA"}]},{"given":"Peiwei","family":"Cao","sequence":"additional","affiliation":[{"name":"Microsoft Research, Redmond, WA"}]},{"given":"Ishai","family":"Menache","sequence":"additional","affiliation":[{"name":"Microsoft Research, Redmond, WA"}]}],"member":"320","published-online":{"date-parts":[[2021,10,25]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Azure pricing. https:\/\/azure.microsoft.com\/en-us\/pricing\/details\/virtual-machines\/windows."},{"key":"e_1_2_1_2_1","unstructured":"Bing Maps Multi-Itinerary Optimization. https:\/\/microsoft.com\/en-us\/maps\/fleet-management."},{"key":"e_1_2_1_3_1","unstructured":"Google Maps Routes. https:\/\/cloud.google.com\/maps-platform\/routes."},{"key":"e_1_2_1_4_1","unstructured":"Resource Scheduling Optimization (RSO). https:\/\/dynamics.microsoft.com\/en-us\/field-service."},{"key":"e_1_2_1_5_1","unstructured":"Routific. https:\/\/routific.com."},{"key":"e_1_2_1_6_1","unstructured":"TomTom Routing API. https:\/\/developer.tomtom.com\/routing-api."},{"key":"e_1_2_1_7_1","unstructured":"TRSP instances. https:\/\/github.com\/microsoft\/trsp."},{"key":"e_1_2_1_8_1","series-title":"Lecture Notes in Computer Science","volume-title":"A hub-based labeling algorithm for shortest paths in road networks","author":"Abraham I.","year":"2011","unstructured":"Abraham, I., Delling, D., Goldberg, A.V., Werneck, R.F. A hub-based labeling algorithm for shortest paths in road networks. In Experimental Algorithms, P. M. Pardalos and S. Rebennack, eds. Lecture Notes in Computer Science (2011), Springer, Berlin Heidelberg, 230--241."},{"key":"e_1_2_1_9_1","first-page":"13","article-title":"Shortest paths in FIFO time-dependent networks: Theory and algorithms","author":"Dean B.C","year":"2004","unstructured":"Dean, B.C. Shortest paths in FIFO time-dependent networks: Theory and algorithms. Rapport Technique, 2004, 13.","journal-title":"Rapport Technique"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-05465-5_8"},{"key":"e_1_2_1_11_1","first-page":"68","article-title":"On the complexity of time-dependent shortest paths","volume":"4","author":"Foschini L.","year":"2014","unstructured":"Foschini, L., Hershberger, J., Suri, S. On the complexity of time-dependent shortest paths. Algorithmica 4, 68 (2014), 1075--1097.","journal-title":"Algorithmica"},{"key":"e_1_2_1_12_1","volume-title":"Engineering time-dependent one-to-all computation. arXiv:1010.0809 [cs]","author":"Geisberger R.","year":"2010","unstructured":"Geisberger, R. Engineering time-dependent one-to-all computation. arXiv:1010.0809 [cs] (2010)."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-68552-4_24"},{"key":"e_1_2_1_14_1","volume-title":"Computational complexity of time-dependent shortest path problems. Optimization Online","author":"He E.","year":"2019","unstructured":"He, E., Boland, N., Nemhauser, G., Savelsbergh, M. Computational complexity of time-dependent shortest path problems. Optimization Online (2019), 12."},{"key":"e_1_2_1_15_1","unstructured":"Helsgaun K. An Extension of the Lin-Kernighan-Helsgaun TSP Solver for Constrained Traveling Salesman and Vehicle Routing Problems. (2017)."},{"key":"e_1_2_1_16_1","first-page":"15","article-title":"Adaptive large neighborhood search for service technician routing and scheduling problems","volume":"5","author":"Kovacs A.A.","year":"2012","unstructured":"Kovacs, A.A., Parragh, S.N., Doerner, K.F., Hartl, R.F. Adaptive large neighborhood search for service technician routing and scheduling problems. J. Schedul. 5, 15 (2012), 579--600.","journal-title":"J. Schedul."},{"key":"e_1_2_1_17_1","volume-title":"Practical risk modeling for the stochastic technician routing and scheduling problem. Optim. Online","author":"Marshall L.","year":"2020","unstructured":"Marshall, L., Tankayev, T. Practical risk modeling for the stochastic technician routing and scheduling problem. Optim. Online (2020)."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.eswa.2016.07.022"},{"key":"e_1_2_1_19_1","first-page":"9","article-title":"Finding the shortest route between two points in a network","volume":"3","author":"Nicholson T.A.J","year":"1966","unstructured":"Nicholson, T.A.J. Finding the shortest route between two points in a network. Comput. J. 3, 9 (1966), 275--280.","journal-title":"Comput. J."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11590-012-0567-4"},{"key":"e_1_2_1_21_1","first-page":"34","article-title":"A general heuristic for vehicle routing problems","volume":"8","author":"Pisinger D.","year":"2007","unstructured":"Pisinger, D., Ropke, S. A general heuristic for vehicle routing problems. Comput. Oper. Res. 8, 34 (2007), 2403--2435.","journal-title":"Comput. Oper. Res."},{"key":"e_1_2_1_22_1","first-page":"40","article-title":"Vehicle routing problem with stochastic travel times including soft time windows and service costs","volume":"1","author":"Ta\u015f D.","year":"2013","unstructured":"Ta\u015f, D., Dellaert, N., van Woensel, T., de Kok, T. Vehicle routing problem with stochastic travel times including soft time windows and service costs. Comput. Oper. Res. 1, 40 (2013), 214--224.","journal-title":"Comput. Oper. Res."},{"key":"e_1_2_1_23_1","first-page":"72","article-title":"Vehicle routing problems with road-network information: State of the art","volume":"3","author":"Ticha H.B.","year":"2018","unstructured":"Ticha, H.B., Absi, N., Feillet, D., Quilliot, A. Vehicle routing problems with road-network information: State of the art. Networks 3, 72 (2018), 393--406.","journal-title":"Networks"},{"key":"e_1_2_1_24_1","volume-title":"Contraction hierarchies---Wikipedia, the free encyclopedia","author":"Wikipedia","year":"2020","unstructured":"Wikipedia contributors. Contraction hierarchies---Wikipedia, the free encyclopedia, 2020. Online [Accessed: 17-March-2020]."}],"container-title":["Communications of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3485626","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3485626","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:18:40Z","timestamp":1750191520000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3485626"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,10,25]]},"references-count":24,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2021,11]]}},"alternative-id":["10.1145\/3485626"],"URL":"https:\/\/doi.org\/10.1145\/3485626","relation":{},"ISSN":["0001-0782","1557-7317"],"issn-type":[{"type":"print","value":"0001-0782"},{"type":"electronic","value":"1557-7317"}],"subject":[],"published":{"date-parts":[[2021,10,25]]},"assertion":[{"value":"2021-10-25","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}