{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,8]],"date-time":"2026-07-08T15:55:26Z","timestamp":1783526126206,"version":"3.55.0"},"reference-count":28,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2022,3,9]],"date-time":"2022-03-09T00:00:00Z","timestamp":1646784000000},"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":[[2022,3,31]]},"abstract":"<jats:p>\n            Food delivery, today, is a multi-billion dollar industry. Minimizing food delivery time is a key contributor towards building positive customer experiences. More precisely, given a stream of food orders and available delivery vehicles, how should orders be assigned to vehicles so the delivery time is minimized? Several decisions have to be made: (1) assignment of orders to vehicles, (2) grouping orders into batches to cope with limited vehicle availability, (3) adapting to dynamic positions of delivery vehicles, and (4) ensuring scalability to the demands of real-world workloads. We show that the minimization problem is not only\n            <jats:italic>NP-hard<\/jats:italic>\n            but\n            <jats:italic>inapproximable<\/jats:italic>\n            in polynomial time. To mitigate this computational bottleneck, we develop an algorithm called\n            <jats:sc>FoodMatch<\/jats:sc>\n            , which maps the vehicle assignment problem to that of\n            <jats:italic>minimum weight perfect matching<\/jats:italic>\n            on a bipartite graph. To further reduce the quadratic construction cost of the bipartite graph, we deploy\n            <jats:italic>best-first search<\/jats:italic>\n            to only compute a subgraph that is highly likely to contain the minimum matching. The solution quality is further enhanced by reducing batching to a graph batching problem and anticipating dynamic positions of vehicles through\n            <jats:italic>angular distance<\/jats:italic>\n            . We perform extensive experiments on real food-delivery data from large metropolitan cities. Our results establish that\n            <jats:sc>FoodMatch<\/jats:sc>\n            imparts substantial improvements over baseline strategies across a host of metrics such as food delivery time, waiting time at restaurants, and orders delivered per kilometer. Furthermore,\n            <jats:sc>FoodMatch<\/jats:sc>\n            is efficient enough to handle real-world workloads.\n          <\/jats:p>","DOI":"10.1145\/3494530","type":"journal-article","created":{"date-parts":[[2022,3,9]],"date-time":"2022-03-09T09:24:06Z","timestamp":1646817846000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":22,"title":["FoodMatch: Batching and Matching for Food Delivery in Dynamic Road Networks"],"prefix":"10.1145","volume":"8","author":[{"given":"Manas","family":"Joshi","sequence":"first","affiliation":[{"name":"Indian Institute of Technology Delhi, Delhi, India"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Arshdeep","family":"Singh","sequence":"additional","affiliation":[{"name":"Indian Institute of Technology Delhi, Delhi, India"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sayan","family":"Ranu","sequence":"additional","affiliation":[{"name":"Indian Institute of Technology Delhi, Delhi, India"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Amitabha","family":"Bagchi","sequence":"additional","affiliation":[{"name":"Indian Institute of Technology Delhi, Delhi, India"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Priyank","family":"Karia","sequence":"additional","affiliation":[{"name":"Swiggy, Bangalore, India"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Puneet","family":"Kala","sequence":"additional","affiliation":[{"name":"Swiggy, Bangalore, India"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2022,3,9]]},"reference":[{"key":"e_1_3_1_2_2","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.1611675114"},{"key":"e_1_3_1_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/195058.195125"},{"key":"e_1_3_1_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/362919.362945"},{"key":"e_1_3_1_5_2","article-title":"\u201cHave 60% revenue market share in food delivery.\u201d","author":"Chanchani Madhav","year":"2019","unstructured":"Madhav Chanchani. 2019. \u201cHave 60% revenue market share in food delivery.\u201d Retrieved from https:\/\/timesofindia. indiatimes.com\/business\/india-business\/have-60-revenue-market-share-in-food-delivery\/articleshow\/72931327.cms.","journal-title":"Retrieved from https:\/\/timesofindia. indiatimes.com\/business\/india-business\/have-60-revenue-market-share-in-food-delivery\/articleshow\/72931327.cms."},{"key":"e_1_3_1_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3064008"},{"key":"e_1_3_1_7_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ifacol.2019.11.117"},{"key":"e_1_3_1_8_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ifacol.2019.11.156"},{"key":"e_1_3_1_9_2","volume-title":"Robust Exact Distance Queries on Massive Networks","author":"Delling Daniel","year":"2014","unstructured":"Daniel Delling, Andrew Goldberg, Thomas Pajor, and Renato Werneck. 2014. Robust Exact Distance Queries on Massive Networks. Technical Report MSR-TR-2014-12. Microsoft."},{"key":"e_1_3_1_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/3219819.3220055"},{"key":"e_1_3_1_11_2","unstructured":"Devansh Gupta. 2019. The Swiggy Delivery Challenge. Retrieved from https:\/\/bytes.swiggy.com\/the-swiggy-delivery-challenge-part-one-6a2abb4f82f6."},{"key":"e_1_3_1_12_2","article-title":"The Changing Market for Food Delivery","author":"Hirschberg Carsten","year":"2016","unstructured":"Carsten Hirschberg, Alexander Rajko, Thomas Schumacher, and Martin Wrulich. 2016. The Changing Market for Food Delivery. Retrieved from https:\/\/www.mckinsey.com\/industries\/technology-media-and-telecommunications\/our-insights\/the-changing-market-for-food-delivery.","journal-title":"Retrieved from https:\/\/www.mckinsey.com\/industries\/technology-media-and-telecommunications\/our-insights\/the-changing-market-for-food-delivery."},{"key":"e_1_3_1_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/3308558.3313464"},{"key":"e_1_3_1_14_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE51399.2021.00207"},{"key":"e_1_3_1_15_2","doi-asserted-by":"publisher","DOI":"10.5555\/312173.312174"},{"key":"e_1_3_1_16_2","volume-title":"Online Optimization: Competitive Analysis and Beyond","author":"Krumke Sven O.","year":"2002","unstructured":"Sven O. Krumke. 2002. Online Optimization: Competitive Analysis and Beyond. Technical Report ZIB Report 02-25. Technische Universitat Berlin."},{"key":"e_1_3_1_17_2","first-page":"410","volume-title":"Proceedings of the IEEE International Conference on Data Engineering","author":"Ma S.","year":"2013","unstructured":"S. Ma, Y. Zheng, and O. Wolfson. 2013. T-share: A large-scale dynamic taxi ridesharing service. In Proceedings of the IEEE International Conference on Data Engineering. 410\u2013421."},{"key":"e_1_3_1_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/1653771.1653818"},{"key":"e_1_3_1_19_2","article-title":"Planet dump retrieved from https:\/\/planet.osm.org","author":"contributors OpenStreetMap","year":"2017","unstructured":"OpenStreetMap contributors. 2017. Planet dump retrieved from https:\/\/planet.osm.org. Retrieved from https:\/\/www.openstreetmap.org.","journal-title":"Retrieved from https:\/\/www.openstreetmap.org"},{"key":"e_1_3_1_20_2","article-title":"The Meal Delivery Routing Problem","author":"Reyes Dami\u00e1n","year":"2018","unstructured":"Dami\u00e1n Reyes, Alan L. Erera, Martin W. P. Savelsbergh, Sagar Sahasrabudhe, and Ryan J. O\u2019Neil. 2018. The Meal Delivery Routing Problem. Optimization Online. Retrieved on January 21, 2022 from http:\/\/www.optimization-online.org\/DB_HTML\/2018\/04\/6571.html.","journal-title":"Optimization Online"},{"key":"e_1_3_1_21_2","article-title":"The Soon to Be 200B Online Food Delivery Is Rapidly Changing the Global Food Industry","author":"Singh Sarwant","year":"2019","unstructured":"Sarwant Singh. 2019. The Soon to Be 200B Online Food Delivery Is Rapidly Changing the Global Food Industry. Retrieved from https:\/\/www.forbes.com\/sites\/sarwantsingh\/2019\/09\/09\/the-soon-to-be-200b-online-food-delivery-is-rapidly-changing-the-global-food-industry\/.","journal-title":"Retrieved from https:\/\/www.forbes.com\/sites\/sarwantsingh\/2019\/09\/09\/the-soon-to-be-200b-online-food-delivery-is-rapidly-changing-the-global-food-industry\/."},{"key":"e_1_3_1_22_2","article-title":"Jeff Bezos Teams up with Narayana Murthy to Enter India\u2019s Food Delivery Biz","author":"Standard Business","year":"2020","unstructured":"Business Standard. 2020. Jeff Bezos Teams up with Narayana Murthy to Enter India\u2019s Food Delivery Biz. Retrieved from https:\/\/www.business-standard.com\/article\/companies\/jeff-bezos-partners-narayana-murthy-to-enter-food-delivery-biz-in-india-120022800111_1.html.","journal-title":"Retrieved from https:\/\/www.business-standard.com\/article\/companies\/jeff-bezos-partners-narayana-murthy-to-enter-food-delivery-biz-in-india-120022800111_1.html."},{"key":"e_1_3_1_23_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2019.03.008"},{"key":"e_1_3_1_24_2","doi-asserted-by":"publisher","DOI":"10.14778\/3236187.3236211"},{"key":"e_1_3_1_25_2","doi-asserted-by":"publisher","DOI":"10.14778\/3384345.3384348"},{"key":"e_1_3_1_26_2","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.2018.0887"},{"key":"e_1_3_1_27_2","doi-asserted-by":"publisher","DOI":"10.1145\/3308558.3313465"},{"key":"e_1_3_1_28_2","doi-asserted-by":"publisher","DOI":"10.14778\/3368289.3368297"},{"key":"e_1_3_1_29_2","doi-asserted-by":"publisher","DOI":"10.14778\/3204028.3204030"}],"container-title":["ACM Transactions on Spatial Algorithms and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3494530","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3494530","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:48:43Z","timestamp":1750193323000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3494530"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,3,9]]},"references-count":28,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,3,31]]}},"alternative-id":["10.1145\/3494530"],"URL":"https:\/\/doi.org\/10.1145\/3494530","relation":{},"ISSN":["2374-0353","2374-0361"],"issn-type":[{"value":"2374-0353","type":"print"},{"value":"2374-0361","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,3,9]]},"assertion":[{"value":"2021-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-03-09","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}