More Web Proxy on the site http://driver.im/

research-article

Learning to Bundle Proactively for On-Demand Meal Delivery

Authors:

Pei LeeAuthors Info & Claims

CIKM '21: Proceedings of the 30th ACM International Conference on Information & Knowledge Management

Pages 3898 - 3905

https://doi.org/10.1145/3459637.3481931

Published: 30 October 2021 Publication History

Abstract

On-demand meal delivery (ODMD) platforms such as DoorDash and Ele.me have experienced explosive growth in recent years. Effective logistics optimization strategies that could guarantee high service standards with controlled costs are crucial for the long-term sustainability of these platforms, and yet are also non-trivial due to the nature of ODMD operations. In particular, most of the orders are not known until they are placed by the customers, and any dispatching policy that only considers known requests would risk making myopic decisions in such a setting.

In this paper, we propose a novel approach to address this problem. At the core of our method is a learning-based metric called Proactive Bundle Cost Vector (PBCV), which quantifies the easiness of bundling a particular order with future orders. Based on PBCV, we build a proactive bundling policy that that considers the viability of serving unknown requests. Extensive online A/B tests demonstrate that the resultant policy has shown significant improvements of key performance metrics over baseline policies. Our solution has been successfully deployed at one of the world's largest ODMD platforms, serving tens of millions of customers on a daily basis.

References

[1]

Nabila Azi, Michel Gendreau, and Jean-Yves Potvin. 2012. A dynamic vehicle routing problem with multiple delivery routes. Annals of Operations Research, Vol. 199, 1 (2012), 103--112.

[2]

Irwan Bello. 2021. LambdaNetworks: Modeling long-range Interactions without Attention. In ICLR.

[3]

Gerardo Berbeglia, Jean-Francc ois Cordeau, and Gilbert Laporte. 2010. Dynamic pickup and delivery problems. European journal of operational research, Vol. 202, 1 (2010), 8--15.

[4]

Daxue Consulting. 2019. The food delivery market in Great China in 2019. https://daxueconsulting.com/o2o-food-delivery-market-in-china/ Retrieved September 1, 2019 from

[5]

Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019. BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding. In NAACL. 4171--4186.

[6]

Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszkoreit, and Neil Houlsby. 2021. An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale. In ICLR.

[7]

Joe Harkman and Santhosh Hari. 2020. Solving for Unobserved Data in a Regression Model Using a Simple Data Adjustment. https://doordash.engineering/2020/10/14/solving-for-unobserved-data-in-a-regression-model/ Retrieved February 2, 2021 from

[8]

Jonathan Ho, Nal Kalchbrenner, Dirk Weissenborn, and Tim Salimans. 2019. Axial attention in multidimensional transformers. arXiv preprint arXiv:1912.12180 (2019).

[9]

Sepp Hochreiter and Jürgen Schmidhuber. 1997. Long short-term memory. Neural computation, Vol. 9, 8 (1997), 1735--1780.

Digital Library

[10]

Chuck Holland, Jack Levis, Ranganath Nuggehalli, Bob Santilli, and Jeff Winters. 2017. UPS Optimizes Delivery Routes. Interfaces, Vol. 47, 1 (Feb. 2017), 8--23.

Digital Library

[11]

Lars M Hvattum, Arne Løkketangen, and Gilbert Laporte. 2006. Solving a dynamic and stochastic vehicle routing problem with a sample scenario hedging heuristic. Transportation Science, Vol. 40, 4 (2006), 421--438.

Digital Library

[12]

Soumia Ichoua, Michel Gendreau, and Jean-Yves Potvin. 2006. Exploiting knowledge about future demands for real-time vehicle dispatching. Transportation Science, Vol. 40, 2 (2006), 211--225.

Digital Library

[13]

David Kastelman and Raghav Ramesh. 2018. Switchback Tests and Randomized Experimentation Under Network Effects at DoorDash. https://doordash.engineering/2018/02/13/switchback-tests-and-randomized-experimentation-under-network-effects-at-doordash/ Retrieved January 1, 2021 from

[14]

Guolin Ke, Qi Meng, Thomas Finley, Taifeng Wang, Wei Chen, Weidong Ma, Qiwei Ye, and Tie-Yan Liu. 2017. Lightgbm: A highly efficient gradient boosting decision tree. In NeurlPS. 3146--3154.

Digital Library

[15]

Alexander Poot, Goossen Kant, and Albert Peter Marie Wagelmans. 2002. A savings based method for real-life vehicle routing problems. Journal of the Operational Research Society, Vol. 53, 1 (2002), 57--68.

[16]

Raghav Ramesh. 2018. How DoorDash leverages AI in its world-class on-demand logistics engine. https://conferences.oreilly.com/artificial-intelligence/ai-ny-2018/public/schedule/detail/65038/ Retrieved December 15, 2019 from

[17]

Damián Reyes, Alan L Erera, and Martin WP Savelsbergh. 2018. Complexity of routing problems with release dates and deadlines. European journal of operational research, Vol. 266, 1 (2018), 29--34.

[18]

Diego Gabriel Rossit, Daniele Vigo, Fernando Tohmé, and Mariano Frutos. 2019. Visual attractiveness in routing problems: A review. Computers & Operations Research, Vol. 103 (2019), 13--34.

[19]

Sarwant Singh. 2019. The Soon To Be 200B Online Food Delivery Is Rapidly Changing The Global Food Industry. https://www.forbes.com/sites/sarwantsingh/2019/09/09/the-soon-to-be-200b-online-food-delivery-is-rapidly-changing-the-global-food-industry/ Retrieved September 20, 2019 from

[20]

Yongxin Tong, Yuqiang Chen, Zimu Zhou, Lei Chen, Jie Wang, Qiang Yang, Jieping Ye, and Weifeng Lv. 2017. The simpler the better: a unified approach to predicting original taxi demands based on large-scale online platforms. In SIGKDD international. 1653--1662.

Digital Library

[21]

Marlin W. Ulmer, Barrett W. Thomas, Ann Melissa Campbell, and Nicholas Woyak. 2021. The Restaurant Meal Delivery Problem: Dynamic Pickup and Delivery with Deadlines and Random Ready Times. Transportation Science, Vol. 55, 1 (2021), 75--100.

Digital Library

[22]

Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. 2017. Attention is all you need. arXiv preprint arXiv:1706.03762 (2017).

[23]

Dong Wang, Wei Cao, Jian Li, and Jieping Ye. 2017. DeepSD: Supply-demand prediction for online car-hailing services using deep neural networks. In ICDE. IEEE, 243--254.

[24]

Xing Wang, Shengyao Wang, Ling Wang, Huanyu Zheng, Jinghua Hao, Renqing He, and Zhizhao Sun. 2020. An Effective Iterated Greedy Algorithm for Online Route Planning Problem. In CEC. 1--8.

[25]

Yuandong Wang, Hongzhi Yin, Hongxu Chen, Tianyu Wo, Jie Xu, and Kai Zheng. 2019. Origin-Destination Matrix Prediction via Graph Convolution: A New Perspective of Passenger Demand Modeling. In SIGKDD. 1227--1235.

Digital Library

[26]

Zhe Xu, Zhixin Li, Qingwen Guan, Dingshui Zhang, Qiang Li, Junxiao Nan, Chunyang Liu, Wei Bian, and Jieping Ye. 2018. Large-scale order dispatch in on-demand ride-hailing platforms: A learning and planning approach. In SIGKDD. 905--913.

Digital Library

[27]

Huaxiu Yao, Fei Wu, Jintao Ke, Xianfeng Tang, Yitian Jia, Siyu Lu, Pinghua Gong, Jieping Ye, and Zhenhui Li. 2018. Deep multi-view spatial-temporal network for taxi demand prediction. In AAAI, Vol. 32.

[28]

Baris Yildiz and Martin Savelsbergh. 2019. Provably High-Quality Solutions for the Meal Delivery Routing Problem. Transportation Science, Vol. 53, 5 (2019), 1372--1388.

Digital Library

Cited By

Wang SGuo BDing YWang GHe SZhang DHe T(2024)Time-Constrained Actor-Critic Reinforcement Learning for Concurrent Order Dispatch in On-Demand DeliveryIEEE Transactions on Mobile Computing10.1109/TMC.2023.334281523:8(8175-8192)Online publication date: Aug-2024
https://doi.org/10.1109/TMC.2023.3342815
Michalopoulou MKolios PPanayiotou TEllinas G(2024)Meal delivery services: Current practices, challenges, and future directionsIEEE Potentials10.1109/MPOT.2023.332779843:1(20-27)Online publication date: Jan-2024
https://doi.org/10.1109/MPOT.2023.3327798
Quin FWeyns DGalster MSilva C(2024)A/B testingJournal of Systems and Software10.1016/j.jss.2024.112011211:COnline publication date: 2-Jul-2024
https://dl.acm.org/doi/10.1016/j.jss.2024.112011

Index Terms

Learning to Bundle Proactively for On-Demand Meal Delivery

Recommendations

On-Demand Meal Delivery Platforms: Operational Level Data and Research Opportunities
This paper describes the operations of most on-demand meal delivery platforms and discusses how empirical research can improve the operational performance of these platforms. To support and encourage more studies on the operations of on-demand delivery ...
Provably High-Quality Solutions for the Meal Delivery Routing Problem
Online restaurant aggregators with integrated meal delivery networks have become more common and more popular in the past few years. Meal delivery is arguably the ultimate challenge in last-mile logistics: a typical order is expected to be delivered ...
Minimizing Bandwidth Requirements for On-Demand Data Delivery

Two recent techniques for multicast or broadcast delivery of streaming media can provide immediate service to each client request, yet achieve considerable client stream sharing which leads to significant server and network bandwidth savings. This paper ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

CIKM '21: Proceedings of the 30th ACM International Conference on Information & Knowledge Management

October 2021

4966 pages

ISBN:9781450384469

DOI:10.1145/3459637

General Chairs:
Gianluca Demartini
The University of Queensland, Australia
,
Guido Zuccon
The University of Queensland, Australia
,
Program Chairs:
J. Shane Culpepper
RMIT University, Australia
,
Zi Huang
The University of Queensland, Australia
,
Hanghang Tong
University of Illinois at Urbana-Champaign, USA

Copyright © 2021 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 30 October 2021

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

CIKM '21

Sponsor:

CIKM '21: The 30th ACM International Conference on Information and Knowledge Management

November 1 - 5, 2021

Queensland, Virtual Event, Australia

Acceptance Rates

Overall Acceptance Rate 1,861 of 8,427 submissions, 22%

Upcoming Conference

CIKM '25

Sponsor:
sigir
sigir

The 34th ACM International Conference on Information and Knowledge Management

November 10 - 14, 2025

Seoul , Republic of Korea

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
322
Total Downloads

Downloads (Last 12 months)109
Downloads (Last 6 weeks)12

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Wang SGuo BDing YWang GHe SZhang DHe T(2024)Time-Constrained Actor-Critic Reinforcement Learning for Concurrent Order Dispatch in On-Demand DeliveryIEEE Transactions on Mobile Computing10.1109/TMC.2023.334281523:8(8175-8192)Online publication date: Aug-2024
https://doi.org/10.1109/TMC.2023.3342815
Michalopoulou MKolios PPanayiotou TEllinas G(2024)Meal delivery services: Current practices, challenges, and future directionsIEEE Potentials10.1109/MPOT.2023.332779843:1(20-27)Online publication date: Jan-2024
https://doi.org/10.1109/MPOT.2023.3327798
Quin FWeyns DGalster MSilva C(2024)A/B testingJournal of Systems and Software10.1016/j.jss.2024.112011211:COnline publication date: 2-Jul-2024
https://dl.acm.org/doi/10.1016/j.jss.2024.112011

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents