EUVIMEDEUVIMED entdecken
Crossref

FoodMatch: Batching and Matching for Food Delivery in Dynamic Road Networks

Manas Joshi, Arshdeep Singh, Sayan Ranu, Amitabha Bagchi, Priyank Karia, Puneet Kala

ACM Transactions on Spatial Algorithms and Systems · 31.03.2022 · 8 (1) · 1-25

DOI: 10.1145/3494530 ↗

Kurz gefasst

Fachartikel in der Zeitschrift ACM Transactions on Spatial Algorithms and Systems, online erschienen am 09.03.2022. Verfasst von Manas Joshi und 5 weiteren Autor:innen. Die Arbeit wurde bisher 25-mal zitiert (Crossref) und nennt 28 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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 NP-hard but inapproximable in polynomial time. To mitigate this computational bottleneck, we develop an algorithm called FoodMatch , which maps the vehicle assignment problem to that of minimum weight perfect matching on a bipartite graph. To further reduce the quadratic construction cost of the bipartite graph, we deploy best-first search 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 angular distance . We perform extensive experiments on real food-delivery data from large metropolitan cities. Our results establish that FoodMatch 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, FoodMatch is efficient enough to handle real-world workloads.

Zitieren

APA

Joshi, M., Singh, A., Ranu, S., Bagchi, A., Karia, P., & Kala, P. (2022). FoodMatch: Batching and Matching for Food Delivery in Dynamic Road Networks. ACM Transactions on Spatial Algorithms and Systems, 8(1), 1-25. https://doi.org/10.1145/3494530

Vancouver

Joshi M, Singh A, Ranu S, Bagchi A, Karia P, Kala P. FoodMatch: Batching and Matching for Food Delivery in Dynamic Road Networks. ACM Transactions on Spatial Algorithms and Systems. 2022;8(1):1-25. doi:10.1145/3494530

BibTeX
@article{Joshi2022,
  author = {Joshi, Manas and Singh, Arshdeep and Ranu, Sayan and Bagchi, Amitabha and Karia, Priyank and Kala, Puneet},
  title = {FoodMatch: Batching and Matching for Food Delivery in Dynamic Road Networks},
  journal = {ACM Transactions on Spatial Algorithms and Systems},
  year = {2022},
  volume = {8},
  number = {1},
  pages = {1--25},
  doi = {10.1145/3494530}
}
Kostenlos starten →