{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,26]],"date-time":"2026-03-26T08:54:03Z","timestamp":1774515243769,"version":"3.50.1"},"reference-count":44,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2021,4,8]],"date-time":"2021-04-08T00:00:00Z","timestamp":1617840000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,4,8]],"date-time":"2021-04-08T00:00:00Z","timestamp":1617840000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"National Science Fund for Distinguished Young Scholars of China","award":["61525304"],"award-info":[{"award-number":["61525304"]}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61873328"],"award-info":[{"award-number":["61873328"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Complex Intell. Syst."],"published-print":{"date-parts":[[2022,2]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>With the prosperity of e-commerce, ordering food online has become increasingly prevalent nowadays. Derived from the dispatching problem in Meituan, a real online food delivery (OFD) platform in China, this paper addresses an OFD problem (OFDP). To solve the OFDP efficiently, an effective matching algorithm with adaptive tie-breaking strategy (MAATS) is proposed by collaboratively fusing the optimization methods with machine learning (ML) techniques. First, to efficiently generate a partial solution with a certain quality, a best-matching heuristic is proposed. Second, to break the ties occurring in the best-matching heuristic and obtain a complete solution with high quality, multiple tie-breaking operators are designed. Third, to adapt to different scenarios, the tie-breaking operators are utilized in a dynamic way which is achieved by using ML methods including decision trees and a specially-designed deep neural network. Fourth, problem-specific features are extracted as decision information to assist the ML models to predict the best tie-breaking operator for use in the current scenario. Preliminary offline simulations are carried out on real historical data sets to validate the effectiveness of the proposed algorithm. Moreover, rigorous online A\/B tests are conducted to evaluate the performance of MAATS in practical applications. The results of offline and online tests demonstrate both the effectiveness of MAATS to solve the OFDP and the application value to improve customer satisfaction and delivery efficiency on Meituan platform.<\/jats:p>","DOI":"10.1007\/s40747-021-00340-x","type":"journal-article","created":{"date-parts":[[2021,4,8]],"date-time":"2021-04-08T08:03:18Z","timestamp":1617868998000},"page":"107-128","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":30,"title":["An effective matching algorithm with adaptive tie-breaking strategy for online food delivery problem"],"prefix":"10.1007","volume":"8","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8698-2532","authenticated-orcid":false,"given":"Jing-fang","family":"Chen","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8964-6454","authenticated-orcid":false,"given":"Ling","family":"Wang","sequence":"additional","affiliation":[]},{"given":"Shengyao","family":"Wang","sequence":"additional","affiliation":[]},{"given":"Xing","family":"Wang","sequence":"additional","affiliation":[]},{"given":"Hao","family":"Ren","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,4,8]]},"reference":[{"key":"340_CR1","unstructured":"Aleksandrov M, Barahona P, Kilby P, Walsh T (2013) Heuristics and policies for online pickup and delivery problems. In: 2013 AAAI conference on artificial intelligence (AAAI), Bellevue, Washington, USA"},{"key":"340_CR2","doi-asserted-by":"publisher","first-page":"222","DOI":"10.1287\/trsc.2017.0803","volume":"53","author":"AM Arslan","year":"2019","unstructured":"Arslan AM, Agatz N, Kroon L, Zuidwijk R (2019) Crowdsourced delivery\u2014a dynamic pickup and delivery problem with ad hoc drivers. Transp Sci 53:222\u2013235","journal-title":"Transp Sci"},{"key":"340_CR3","doi-asserted-by":"publisher","first-page":"8","DOI":"10.1016\/j.ejor.2009.04.024","volume":"202","author":"G Berbeglia","year":"2010","unstructured":"Berbeglia G, Cordeau J-F, Laporte G (2010) Dynamic pickup and delivery problems. Eur J Oper Res 202:8\u201315","journal-title":"Eur J Oper Res"},{"key":"340_CR4","doi-asserted-by":"publisher","first-page":"46","DOI":"10.1016\/j.cam.2008.10.038","volume":"232","author":"O Br\u00e4ysy","year":"2009","unstructured":"Br\u00e4ysy O, Nakari P, Dullaert W, Neittaanm\u00e4ki P (2009) An optimization approach for communal home meal delivery service: a case study. J Comput Appl Math 232:46\u201353","journal-title":"J Comput Appl Math"},{"key":"340_CR5","doi-asserted-by":"crossref","unstructured":"Chen J, Wang S, Wang L et al (2020) A hybrid differential evolution algorithm for the online meal delivery problem. In: 2020 IEEE congress on evolutionary computation (CEC), Glasgow, United Kingdom","DOI":"10.1109\/CEC48606.2020.9185792"},{"key":"340_CR6","doi-asserted-by":"crossref","unstructured":"Chen T, Guestrin C (2016) XGBoost: a scalable tree boosting system. In: Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining (KDD), San Francisco, USA, pp 785\u2013794","DOI":"10.1145\/2939672.2939785"},{"key":"340_CR7","first-page":"511","volume":"52","author":"M Cosmi","year":"2019","unstructured":"Cosmi M, Nicosia G, Pacifici A (2019) Scheduling for last-mile meal-delivery processes. IFAC-Pap 52:511\u2013516","journal-title":"IFAC-Pap"},{"key":"340_CR8","doi-asserted-by":"publisher","first-page":"537","DOI":"10.1016\/j.orl.2019.09.007","volume":"47","author":"M Cosmi","year":"2019","unstructured":"Cosmi M, Oriolo G, Piccialli V, Ventura P (2019) Single courier single restaurant meal delivery (without routing). Oper Res Lett 47:537\u2013541","journal-title":"Oper Res Lett"},{"key":"340_CR9","doi-asserted-by":"crossref","unstructured":"Dev VA, Eden MR (2019) Gradient boosted decision trees for lithology classification. In: Proceedings of the 9th international conference on foundations of computer-aided process design (FOCAPD), Raleigh, North Carolina, USA, vol 47, pp 113\u2013118","DOI":"10.1016\/B978-0-12-818597-1.50019-9"},{"key":"340_CR10","doi-asserted-by":"publisher","first-page":"149","DOI":"10.3390\/info9070149","volume":"9","author":"S Dhaliwal","year":"2018","unstructured":"Dhaliwal S, Nahid A-A, Abbas R (2018) Effective intrusion detection system using XGBoost. Information 9:149","journal-title":"Information"},{"key":"340_CR11","doi-asserted-by":"publisher","first-page":"721","DOI":"10.1007\/s40747-020-00173-0","volume":"6","author":"Y Feng","year":"2020","unstructured":"Feng Y, Wang D, Yin Y et al (2020) An XGBoost-based casualty prediction method for terrorist attacks. Complex Intell Syst 6:721\u2013740","journal-title":"Complex Intell Syst"},{"key":"340_CR12","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1016\/j.cor.2013.12.012","volume":"45","author":"V Fernandez-Viagas","year":"2014","unstructured":"Fernandez-Viagas V, Framinan JM (2014) On insertion tie-breaking rules in heuristics for the permutation flowshop scheduling problem. Comput Oper Res 45:60\u201367","journal-title":"Comput Oper Res"},{"key":"340_CR13","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.trb.2014.02.001","volume":"63","author":"F Ferrucci","year":"2014","unstructured":"Ferrucci F, Bock S (2014) Real-time control of express pickup and delivery processes in a dynamic environment. Transp Res Part B Methodol 63:1\u201314","journal-title":"Transp Res Part B Methodol"},{"key":"340_CR14","doi-asserted-by":"crossref","unstructured":"Fkaier ZK, Chaar BF (2013) Online K-means based heuristic for the dynamic pickup and delivery problem solving. In: 2013 world congress on computer and information technology (WCCIT), Sousse, Tunisia, pp 1\u20136","DOI":"10.1109\/WCCIT.2013.6618717"},{"key":"340_CR15","doi-asserted-by":"crossref","unstructured":"Guo H, Tang R, Ye Y et al (2017) DeepFM: a factorization-machine based neural network for CTR prediction. In: Proceedings of the 26th international joint conference on artificial intelligence (IJCAI), Melbourne, Australia, pp 1725\u20131731","DOI":"10.24963\/ijcai.2017\/239"},{"key":"340_CR16","doi-asserted-by":"publisher","first-page":"5528","DOI":"10.3390\/su12145528","volume":"12","author":"C Li","year":"2020","unstructured":"Li C, Mirosa M, Bremer P (2020) Review of online food delivery platforms and their impacts on sustainability. Sustainability 12:5528","journal-title":"Sustainability"},{"key":"340_CR17","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.cor.2019.05.024","volume":"111","author":"Y Liu","year":"2019","unstructured":"Liu Y (2019) An optimization-driven dynamic vehicle routing algorithm for on-demand meal delivery using drones. Comput Oper Res 111:1\u201320","journal-title":"Comput Oper Res"},{"key":"340_CR18","doi-asserted-by":"publisher","first-page":"1288","DOI":"10.1109\/TMC.2018.2861864","volume":"18","author":"Y Liu","year":"2019","unstructured":"Liu Y, Guo B, Chen C et al (2019) FooDNet: toward an optimized food delivery network based on spatial crowdsourcing. IEEE Trans Mob Comput 18:1288\u20131301","journal-title":"IEEE Trans Mob Comput"},{"key":"340_CR19","doi-asserted-by":"crossref","unstructured":"Lu Y, Wu Y, Zhou Y (2017) Order assignment and routing for online food delivery: two meta-heuristic methods. In: Proceedings of the 2017 international conference on intelligent systems, metaheuristics and swarm intelligence (ISMSI), Hong Kong, China, pp 125\u2013129","DOI":"10.1145\/3059336.3059349"},{"key":"340_CR20","unstructured":"Luo H, Liufu M, Li D (2020) Intelligent online food delivery system: a dynamic model to generate delivery strategy and tip advice. arXiv preprint arXiv: 2002.01713."},{"key":"340_CR21","unstructured":"Meituan, CFLP (2019) Report on the development of Chinese immediate delivery business in 2019. http:\/\/pdf.dfcfw.com\/pdf\/H3_AP202006011381522218_1.pdf. Accessed 15 Dec 2020"},{"key":"340_CR22","unstructured":"Meituan, China Hospitality Association (2020) Report on the development of Chinese take-out industry in 2019 and the first half of 2020. https:\/\/ncstatic.clewm.net\/rsrc\/2020\/0628\/09\/84f7f3e18c6e27cb32227534f640bd45.pdf. Accessed 15 Dec 2020"},{"key":"340_CR23","doi-asserted-by":"publisher","first-page":"e127","DOI":"10.7717\/peerj-cs.127","volume":"3","author":"R Mitchell","year":"2017","unstructured":"Mitchell R, Frank E (2017) Accelerating the XGBoost algorithm using GPU computing. PeerJ Comput Sci 3:e127","journal-title":"PeerJ Comput Sci"},{"key":"340_CR24","unstructured":"Morgan Stanley Research (2017) Is online food delivery about to get \u2019amazoned\u2019? https:\/\/www.morganstanley.com\/ideas\/online-food-delivery-market-expands. Accessed 18 May 2020"},{"key":"340_CR25","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1287\/trsc.2014.0569","volume":"49","author":"D Mu\u00f1oz-Carpintero","year":"2015","unstructured":"Mu\u00f1oz-Carpintero D, S\u00e1ez D, Cort\u00e9s CE, N\u00fa\u00f1ez A (2015) A methodology based on evolutionary algorithms to solve a dynamic pickup and delivery problem under a hybrid predictive control approach. Transp Sci 49:239\u2013253","journal-title":"Transp Sci"},{"key":"340_CR26","doi-asserted-by":"crossref","unstructured":"Nargesian F, Samulowitz H, Khurana U et al (2017) Learning feature engineering for classification. In: Proceedings of the 26th international joint conference on artificial intelligence (IJCAI), Melbourne, Australia, pp 2529\u20132535","DOI":"10.24963\/ijcai.2017\/352"},{"key":"340_CR27","doi-asserted-by":"publisher","DOI":"10.1109\/TCBB.2019.2911071","author":"A Ogunleye","year":"2019","unstructured":"Ogunleye A, Wang QG (2019) XGBoost model for chronic kidney disease diagnosis. IEEE\/ACM Trans Comput Biol Bioinform. https:\/\/doi.org\/10.1109\/TCBB.2019.2911071","journal-title":"IEEE\/ACM Trans Comput Biol Bioinform"},{"key":"340_CR28","unstructured":"Reyes D, Erera A, Savelsbergh M et al (2018) The meal delivery routing problem. Optim Online"},{"key":"340_CR29","doi-asserted-by":"publisher","first-page":"455","DOI":"10.1287\/trsc.1050.0135","volume":"40","author":"S Ropke","year":"2006","unstructured":"Ropke S, Pisinger D (2006) An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows. Transp Sci 40:455\u2013472","journal-title":"Transp Sci"},{"key":"340_CR30","doi-asserted-by":"publisher","first-page":"178","DOI":"10.1016\/j.tra.2013.01.032","volume":"49","author":"PK Sheridan","year":"2013","unstructured":"Sheridan PK, Gluck E, Guan Q et al (2013) The dynamic nearest neighbor policy for the multi-vehicle pick-up and delivery problem. Transp Res Part Policy Pract 49:178\u2013194","journal-title":"Transp Res Part Policy Pract"},{"key":"340_CR31","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1016\/j.cor.2019.03.008","volume":"107","author":"Z Steever","year":"2019","unstructured":"Steever Z, Karwan M, Murray C (2019) Dynamic courier routing for a food delivery service. Comput Oper Res 107:173\u2013188","journal-title":"Comput Oper Res"},{"key":"340_CR32","doi-asserted-by":"publisher","first-page":"1","DOI":"10.4018\/jdwm.2007070101","volume":"3","author":"G Tsoumakas","year":"2007","unstructured":"Tsoumakas G, Katakis I (2007) Multi-label classification: an overview. Int J Data Warehous Min 3:1\u201313","journal-title":"Int J Data Warehous Min"},{"key":"340_CR33","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.2020.1000","author":"M Ulmer","year":"2017","unstructured":"Ulmer M, Thomas BW, Campbell AM, Woyak N (2017) The restaurant meal delivery problem: dynamic pick-up and delivery with deadlines and random ready times. Transp Sci. https:\/\/doi.org\/10.1287\/trsc.2020.1000","journal-title":"Transp Sci"},{"key":"340_CR34","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1007\/s10479-014-1683-6","volume":"236","author":"S Vonolfen","year":"2016","unstructured":"Vonolfen S, Affenzeller M (2016) Distribution of waiting time for dynamic pickup and delivery problems. Ann Oper Res 236:359\u2013382","journal-title":"Ann Oper Res"},{"key":"340_CR35","doi-asserted-by":"crossref","unstructured":"Wang X, Wang S, Wang L et al (2020) An effective iterated greedy algorithm for online route planning problem. In: 2020 IEEE congress on evolutionary computation (CEC), Glasgow, United Kingdom","DOI":"10.1109\/CEC48606.2020.9185864"},{"key":"340_CR36","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1109\/4235.585893","volume":"1","author":"DH Wolpert","year":"1997","unstructured":"Wolpert DH, Macready WG (1997) No free lunch theorems for optimization. IEEE Trans Evol Comput 1:67\u201382","journal-title":"IEEE Trans Evol Comput"},{"key":"340_CR37","doi-asserted-by":"publisher","first-page":"150","DOI":"10.1016\/j.jretconser.2016.12.013","volume":"35","author":"VCS Yeo","year":"2017","unstructured":"Yeo VCS, Goh S-K, Rezaei S (2017) Consumer experiences, attitude and behavioral intention toward online food delivery (OFD) services. J Retail Consum Serv 35:150\u2013162","journal-title":"J Retail Consum Serv"},{"key":"340_CR38","doi-asserted-by":"publisher","first-page":"1372","DOI":"10.1287\/trsc.2018.0887","volume":"53","author":"B Yildiz","year":"2019","unstructured":"Yildiz B, Savelsbergh M (2019) Provably high-quality solutions for the meal delivery routing problem. Transp Sci 53:1372\u20131388","journal-title":"Transp Sci"},{"key":"340_CR39","unstructured":"Yildiz H, Johnson MP, Roehrig S (2005) A genetic algorithm for the home-delivered meals location-routing problem. Heinz Coll Res"},{"key":"340_CR40","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-020-00615-y","author":"H Yu","year":"2020","unstructured":"Yu H, Luo X, Wu T (2020) Online pickup and delivery problem with constrained capacity to minimize latency. J Comb Optim. https:\/\/doi.org\/10.1007\/s10878-020-00615-y","journal-title":"J Comb Optim"},{"key":"340_CR41","doi-asserted-by":"publisher","first-page":"1819","DOI":"10.1109\/TKDE.2013.39","volume":"26","author":"M-L Zhang","year":"2014","unstructured":"Zhang M-L, Zhou Z-H (2014) A review on multi-label learning algorithms. IEEE Trans Knowl Data Eng 26:1819\u20131837","journal-title":"IEEE Trans Knowl Data Eng"},{"key":"340_CR42","unstructured":"Zheng H, Wang S, Cha Y et al (2019) A two-stage fast heuristic for food delivery route planning problem. In: Informs annual meeting, Seattle, Washington, USA"},{"key":"340_CR43","doi-asserted-by":"crossref","unstructured":"Zheng J, Wang S, Wang L et al (2020) A two-stage algorithm for fuzzy online order dispatching problem. In: 2020 IEEE congress on evolutionary computation (CEC), Glasgow, United Kingdom","DOI":"10.1109\/CEC48606.2020.9185858"},{"key":"340_CR44","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1016\/j.ins.2015.09.006","volume":"329","author":"Z Zhu","year":"2016","unstructured":"Zhu Z, Xiao J, He S et al (2016) A multi-objective memetic algorithm based on locality-sensitive hashing for one-to-many-to-one dynamic pickup-and-delivery problem. Inf Sci 329:73\u201389","journal-title":"Inf Sci"}],"container-title":["Complex &amp; Intelligent Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s40747-021-00340-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s40747-021-00340-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s40747-021-00340-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,3,3]],"date-time":"2022-03-03T12:30:17Z","timestamp":1646310617000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s40747-021-00340-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,4,8]]},"references-count":44,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,2]]}},"alternative-id":["340"],"URL":"https:\/\/doi.org\/10.1007\/s40747-021-00340-x","relation":{},"ISSN":["2199-4536","2198-6053"],"issn-type":[{"value":"2199-4536","type":"print"},{"value":"2198-6053","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,4,8]]},"assertion":[{"value":"15 December 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 March 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 April 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that we have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}