{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,20]],"date-time":"2026-04-20T18:54:28Z","timestamp":1776711268795,"version":"3.51.2"},"reference-count":42,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2022,4,29]],"date-time":"2022-04-29T00:00:00Z","timestamp":1651190400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,4,29]],"date-time":"2022-04-29T00:00:00Z","timestamp":1651190400000},"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,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Uncertainty is everywhere in the food delivery process, which significantly influences decision-making for complex on-demand food delivery problems, affecting delivery efficiency and customer satisfaction. Especially, the service time is an indispensable part of the delivery process impacted by various uncertain factors. Due to the simplicity and high accuracy requirement, we model the uncertain service time as a Gaussian mixture model (GMM). In detail, we transform the distribution estimation problem into a clustering problem by determining the probability of each data belonging to each component (each cluster as well). A hybrid estimation of distribution algorithm is proposed to intelligently solve the clustering problem with the criterion to optimize quality and simplicity simultaneously. First, to optimize the simplicity, problem-specific encoding and decoding methods are designed. Second, to generate initial solutions with good clustering results, a Chinese restaurant process-based initialization mechanism is presented. Third, a weighted-learning mechanism is proposed to effectively guide the update of the probability model. Fourth, a local intensification based on maximum likelihood is used to exploit better solutions. The effect of critical parameters on the performances of the proposed algorithm is investigated by the Taguchi design of the experimental method. To demonstrate the effectiveness of the proposed algorithm, we carry out extensive offline experiments on real-world historical data. Besides, we employ the GMMs obtained by our algorithm in a real-world on-demand food delivery platform, Meituan, to assist decision-making for order dispatching. The results of rigorous online A\/B tests verify the practical value of introducing the uncertainty model into the real-life application.<\/jats:p>","DOI":"10.1007\/s40747-022-00719-4","type":"journal-article","created":{"date-parts":[[2022,4,29]],"date-time":"2022-04-29T09:04:00Z","timestamp":1651223040000},"page":"4939-4953","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":12,"title":["Modeling stochastic service time for complex on-demand food delivery"],"prefix":"10.1007","volume":"8","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9640-1604","authenticated-orcid":false,"given":"Jie","family":"Zheng","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":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8698-2532","authenticated-orcid":false,"given":"Jing-fang","family":"Chen","sequence":"additional","affiliation":[]},{"given":"Xing","family":"Wang","sequence":"additional","affiliation":[]},{"given":"Haining","family":"Duan","sequence":"additional","affiliation":[]},{"given":"Yile","family":"Liang","sequence":"additional","affiliation":[]},{"given":"Xuetao","family":"Ding","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,4,29]]},"reference":[{"key":"719_CR1","doi-asserted-by":"publisher","first-page":"100014","DOI":"10.1016\/j.clrc.2021.100014","volume":"2","author":"JIB Janairo","year":"2021","unstructured":"Janairo JIB (2021) Unsustainable plastic consumption associated with online food delivery services in the new normal. Clean Responsible Consumpt 2:100014","journal-title":"Clean Responsible Consumpt"},{"key":"719_CR2","unstructured":"Meituan and 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\/84f7f3e18c6e2-7cb32227534f640bd45.pdf"},{"issue":"4","key":"719_CR3","doi-asserted-by":"publisher","first-page":"276","DOI":"10.1109\/TITS.2004.837813","volume":"5","author":"C-H Wu","year":"2004","unstructured":"Wu C-H, Ho J-M, Lee D-T (2004) Travel-time prediction with support vector regression. IEEE Trans Intel Transp 5(4):276\u2013281","journal-title":"IEEE Trans Intel Transp"},{"key":"719_CR4","doi-asserted-by":"publisher","unstructured":"Zheng J, Wang S, Wang L, Chen J-F, Wang L, Hao J, Sun Z (2020) A two-stage algorithm for fuzzy online order dispatching problem. In: 2020 IEEE congress on evolutionary computation (CEC). https:\/\/doi.org\/10.1109\/CEC48606.2020.9185858","DOI":"10.1109\/CEC48606.2020.9185858"},{"key":"719_CR5","doi-asserted-by":"publisher","first-page":"1445","DOI":"10.1007\/s40747-021-00291-3","volume":"7","author":"Y Zhou","year":"2021","unstructured":"Zhou Y, Huang J, Shi J, Wang R, Huang K (2021) The electric vehicle routing problem with partial recharge and vehicle recycling. Complex Intell Syst 7:1445\u20131458","journal-title":"Complex Intell Syst"},{"key":"719_CR6","doi-asserted-by":"publisher","DOI":"10.1007\/s40747-021-00401-1","author":"H Wu","year":"2021","unstructured":"Wu H, Gao Y, Wang W, Zhang Z (2021) A hybrid ant colony algorithm based on multiple strategies for the vehicle routing problem with time windows. Compl Intell Syst. https:\/\/doi.org\/10.1007\/s40747-021-00401-1","journal-title":"Compl Intell Syst"},{"key":"719_CR7","doi-asserted-by":"publisher","first-page":"144","DOI":"10.1016\/j.cie.2018.07.042","volume":"125","author":"A Gutierrez","year":"2018","unstructured":"Gutierrez A, Dieulle L, Labadie N, Velasco N (2018) A multi-population algorithm to solve the VRP with stochastic service and travel times. Comput Ind Eng 125:144\u2013156","journal-title":"Comput Ind Eng"},{"issue":"1","key":"719_CR8","doi-asserted-by":"publisher","first-page":"98","DOI":"10.1016\/j.ejor.2020.05.037","volume":"288","author":"Y Zhan","year":"2021","unstructured":"Zhan Y, Wang Z, Wan G (2021) Home service routing and appointment scheduling with stochastic service times. Eur J Oper Res 288(1):98\u2013110","journal-title":"Eur J Oper Res"},{"issue":"23\u201324","key":"719_CR9","doi-asserted-by":"publisher","first-page":"9990","DOI":"10.1016\/j.apm.2016.06.025","volume":"40","author":"R Kuo","year":"2016","unstructured":"Kuo R, Wibowo B, Zulvia F (2016) Application of a fuzzy ant colony system to solve the dynamic vehicle routing problem with uncertain service time. Appl Math Model 40(23\u201324):9990\u201310001","journal-title":"Appl Math Model"},{"issue":"3","key":"719_CR10","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1007\/s13676-016-0101-4","volume":"7","author":"F Errico","year":"2018","unstructured":"Errico F, Desaulniers G, Gendreau M, Rei W, Rousseau L-M (2018) The vehicle routing problem with hard time windows and stochastic service times. EURO J Transp Logist 7(3):223\u2013251","journal-title":"EURO J Transp Logist"},{"key":"719_CR11","doi-asserted-by":"publisher","first-page":"64","DOI":"10.1016\/j.cor.2015.07.001","volume":"65","author":"S Binart","year":"2016","unstructured":"Binart S, Dejax P, Gendreau M, Semet F (2016) A 2-stage method for a field service routing problem with stochastic travel and service times. Comput Oper Res 65:64\u201375","journal-title":"Comput Oper Res"},{"issue":"1","key":"719_CR12","doi-asserted-by":"crossref","first-page":"1","DOI":"10.24867\/IJIEM-2020-1-editorial","volume":"11","author":"M Nasri","year":"2020","unstructured":"Nasri M, Metrane A, Hafidi I, Jamali A (2020) A robust approach for solving a vehicle routing problem with time windows with uncertain service and travel times. Int J Ind Eng Comp 11(1):1\u201316","journal-title":"Int J Ind Eng Comp"},{"issue":"2","key":"719_CR13","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1016\/j.jmsy.2013.12.009","volume":"33","author":"N Tajik","year":"2014","unstructured":"Tajik N, Tavakkoli-Moghaddam R, Vahdani B, Mousavi SM (2014) A robust optimization approach for pollution routing problem with pickup and delivery under uncertainty. J Manuf Syst 33(2):277\u2013286","journal-title":"J Manuf Syst"},{"key":"719_CR14","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1016\/j.trc.2015.06.011","volume":"57","author":"B Bian","year":"2015","unstructured":"Bian B, Zhu N, Ling S, Ma S (2015) Bus service time estimation model for a curbside bus stop. Transp Res Part C Emerg Technol 57:103\u2013121","journal-title":"Transp Res Part C Emerg Technol"},{"key":"719_CR15","doi-asserted-by":"crossref","unstructured":"Wang Y, Zheng Y, Xue Y (2014) Travel time estimation of a path using sparse trajectories. In: Proceedings of the 20th ACM SIGKDD, pp 25\u201334","DOI":"10.1145\/2623330.2623656"},{"key":"719_CR16","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1016\/j.ins.2018.07.056","volume":"467","author":"HD Nguyen","year":"2018","unstructured":"Nguyen HD, Wang D, McLachlan GJ (2018) Randomized mixture models for probability density approximation and estimation. Inform Sci 467:135\u2013148","journal-title":"Inform Sci"},{"issue":"4","key":"719_CR17","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1007\/s40747-016-0028-2","volume":"2","author":"W Li","year":"2016","unstructured":"Li W, Wang Z, Yuan Y, Guo L (2016) Particle filtering with applications in networked systems: a survey. Complex Intell Syst 2(4):293\u2013315","journal-title":"Complex Intell Syst"},{"issue":"2","key":"719_CR18","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1137\/1026034","volume":"26","author":"RA Redner","year":"1984","unstructured":"Redner RA, Walker HF (1984) Mixture densities, maximum likelihood and the EM algorithm. SIAM Rev 26(2):195\u2013239","journal-title":"SIAM Rev"},{"issue":"3\u20134","key":"719_CR19","doi-asserted-by":"publisher","first-page":"561","DOI":"10.1016\/S0167-9473(02)00163-9","volume":"41","author":"C Biernacki","year":"2003","unstructured":"Biernacki C, Celeux G, Govaert G (2003) Choosing starting values for the EM algorithm for getting the highest likelihood in multivariate Gaussian mixture models. Comput Stat Data An 41(3\u20134):561\u2013575","journal-title":"Comput Stat Data An"},{"issue":"8","key":"719_CR20","doi-asserted-by":"publisher","first-page":"759","DOI":"10.1016\/S0167-8655(00)00031-3","volume":"21","author":"AM Mart\u0131nez","year":"2000","unstructured":"Mart\u0131nez AM, Vitria J (2000) Learning mixture models using a genetic version of the EM algorithm. Pattern Recogn Lett 21(8):759\u2013769","journal-title":"Pattern Recogn Lett"},{"issue":"2","key":"719_CR21","doi-asserted-by":"publisher","first-page":"298","DOI":"10.1109\/TSMCB.2009.2015054","volume":"40","author":"S Kiranyaz","year":"2009","unstructured":"Kiranyaz S, Ince T, Yildirim A, Gabbouj M (2009) Fractional particle swarm optimization in multidimensional search space. IEEE Trans Syst Man Cybern B 40(2):298\u2013319","journal-title":"IEEE Trans Syst Man Cybern B"},{"key":"719_CR22","first-page":"109","volume":"11","author":"W Kwedlo","year":"2014","unstructured":"Kwedlo W (2014) Estimation of parameters of Gaussian mixture models by a hybrid method combining a self-adaptive differential evolution with the EM algorithm. Adv Comput Sci Res 11:109\u2013123","journal-title":"Adv Comput Sci Res"},{"key":"719_CR23","unstructured":"Biernacki C, Govaert G (1997) Using the classification likelihood to choose the number of clusters. Comput Sci Sta, 451\u2013457."},{"issue":"6","key":"719_CR24","doi-asserted-by":"publisher","first-page":"1381","DOI":"10.1016\/j.csda.2011.11.002","volume":"56","author":"V Melnykov","year":"2012","unstructured":"Melnykov V, Melnykov I (2012) Initializing the EM algorithm in Gaussian mixture models with an unknown number of components. Comput Stat Data An 56(6):1381\u20131395","journal-title":"Comput Stat Data An"},{"issue":"8","key":"719_CR25","doi-asserted-by":"publisher","first-page":"1344","DOI":"10.1109\/TPAMI.2005.162","volume":"27","author":"F Pernkopf","year":"2005","unstructured":"Pernkopf F, Bouchaffra D (2005) Genetic-based EM algorithm for learning Gaussian mixture models. IEEE Trans Pattern Anal 27(8):1344\u20131348","journal-title":"IEEE Trans Pattern Anal"},{"issue":"4","key":"719_CR26","doi-asserted-by":"publisher","first-page":"4452","DOI":"10.1109\/LRA.2019.2932610","volume":"4","author":"E Pignat","year":"2019","unstructured":"Pignat E, Calinon S (2019) Bayesian Gaussian mixture model for robotic policy imitation. IEEE Robot Autom Lett 4(4):4452\u20134458","journal-title":"IEEE Robot Autom Lett"},{"issue":"1","key":"719_CR27","doi-asserted-by":"publisher","first-page":"012084","DOI":"10.1088\/1742-6596\/1725\/1\/012084","volume":"1725","author":"J Mirra","year":"2021","unstructured":"Mirra J, Abdullah S (2021) Bayesian gaussian finite mixture model. J Phys Conf Ser 1725(1):012084","journal-title":"J Phys Conf Ser"},{"key":"719_CR28","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1016\/j.neunet.2018.10.002","volume":"109","author":"G Liu","year":"2019","unstructured":"Liu G, Liu Y, Guo M, Li P, Li M (2019) Variational inference with Gaussian mixture model and householder flow. Neural Netw 109:43\u201355","journal-title":"Neural Netw"},{"key":"719_CR29","doi-asserted-by":"crossref","unstructured":"Hershey JR, Olsen PA (2007) Approximating the Kullback Leibler divergence between Gaussian mixture models. In: 2007 IEEE international conference on acoustics, speech and signal processing-ICASSP, vol 4, pp 317\u2013320","DOI":"10.1109\/ICASSP.2007.366913"},{"key":"719_CR30","doi-asserted-by":"crossref","unstructured":"Chen L, Wang D, Gan Z, Liu J, Henao R, Carin L (2021) Wasserstein contrastive representation distillation. In: Proceedings of the IEEE\/CVF conference on computer vision and pattern recognition, pp 16296\u201316305","DOI":"10.1109\/CVPR46437.2021.01603"},{"issue":"4","key":"719_CR31","doi-asserted-by":"publisher","first-page":"784","DOI":"10.1137\/1118101","volume":"18","author":"S Vallender","year":"1974","unstructured":"Vallender S (1974) Calculation of the Wasserstein distance between probability distributions on the line. Theor Prob Appl 18(4):784\u2013786","journal-title":"Theor Prob Appl"},{"issue":"3","key":"719_CR32","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1016\/j.swevo.2011.08.003","volume":"1","author":"M Hauschild","year":"2011","unstructured":"Hauschild M, Pelikan M (2011) An introduction and survey of estimation of distribution algorithms. Swarm Evol Comput 1(3):111\u2013128","journal-title":"Swarm Evol Comput"},{"issue":"4","key":"719_CR33","doi-asserted-by":"publisher","first-page":"283","DOI":"10.1007\/s40747-018-0080-1","volume":"4","author":"R Cheng","year":"2018","unstructured":"Cheng R, He C, Jin Y, Yao X (2018) Model-based evolutionary algorithms: a short survey. Complex Intell Syst 4(4):283\u2013292","journal-title":"Complex Intell Syst"},{"key":"719_CR34","doi-asserted-by":"publisher","first-page":"105536","DOI":"10.1016\/j.knosys.2020.105536","volume":"194","author":"J Zheng","year":"2020","unstructured":"Zheng J, Wang L, Wang J (2020) A cooperative coevolution algorithm for multi-objective fuzzy distributed hybrid flow shop. Knowl-Based Syst 194:105536","journal-title":"Knowl-Based Syst"},{"issue":"1","key":"719_CR35","doi-asserted-by":"publisher","first-page":"42","DOI":"10.1109\/TETCI.2020.3013652","volume":"5","author":"W Shi","year":"2020","unstructured":"Shi W, Chen W-N, Gu T, Jin H, Zhang J (2020) Handling uncertainty in financial decision making: a clustering estimation of distribution algorithm with simplified simulation. IEEE Trans Emerg Top Comput Intel 5(1):42\u201356","journal-title":"IEEE Trans Emerg Top Comput Intel"},{"issue":"2","key":"719_CR36","doi-asserted-by":"publisher","first-page":"1693","DOI":"10.1016\/j.asej.2020.07.034","volume":"12","author":"BP Chandran","year":"2020","unstructured":"Chandran BP, Selvakumar AI, Let GS, Sathiyan SP (2020) Optimal model parameter estimation of solar and fuel cells using improved estimation of distribution algorithm. Ain Shams Eng J 12(2):1693\u20131700","journal-title":"Ain Shams Eng J"},{"issue":"2","key":"719_CR37","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1667053.1667056","volume":"57","author":"DM Blei","year":"2010","unstructured":"Blei DM, Griffiths TL, Jordan MI (2010) The nested chinese restaurant process and bayesian nonparametric inference of topic hierarchies. J ACM 57(2):1\u201330","journal-title":"J ACM"},{"issue":"2","key":"719_CR38","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1214\/aos\/1176342360","volume":"1","author":"TS Ferguson","year":"1973","unstructured":"Ferguson TS (1973) A Bayesian analysis of some nonparametric problems. The Ann Stat 1(2):209\u2013230","journal-title":"The Ann Stat"},{"key":"719_CR39","doi-asserted-by":"crossref","unstructured":"Pfeifer T, Protzel P (2019) Expectation-maximization for adaptive mixture models in graph optimization. In: 2019 international conference on robotics and automation (ICRA), pp 3151\u20133157.","DOI":"10.1109\/ICRA.2019.8793601"},{"key":"719_CR40","doi-asserted-by":"publisher","first-page":"80716","DOI":"10.1109\/ACCESS.2020.2988796","volume":"8","author":"KP Sinaga","year":"2020","unstructured":"Sinaga KP, Yang M-S (2020) Unsupervised K-means clustering algorithm. IEEE. Access 8:80716\u201380727","journal-title":"Access"},{"key":"719_CR41","doi-asserted-by":"publisher","unstructured":"Chen J, Wang S, Wang L, Zheng J, Cha Y, Hao J, He R, Sun Z (2020) A hybrid differential evolution algorithm for the online meal delivery problem. In: IEEE congress on evolutionary computation (CEC). https:\/\/doi.org\/10.1109\/CEC48606.2020.9185792","DOI":"10.1109\/CEC48606.2020.9185792"},{"key":"719_CR42","doi-asserted-by":"publisher","DOI":"10.1007\/s40747-021-00340-x","author":"J Chen","year":"2021","unstructured":"Chen J, Wang L, Wang S, Wang X, Ren H (2021) An effective matching algorithm with adaptive tie-breaking strategy for online food delivery problem. Compl Intell Syst. https:\/\/doi.org\/10.1007\/s40747-021-00340-x","journal-title":"Compl Intell Syst"}],"container-title":["Complex &amp; Intelligent Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s40747-022-00719-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s40747-022-00719-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s40747-022-00719-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,27]],"date-time":"2022-10-27T12:08:45Z","timestamp":1666872525000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s40747-022-00719-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,4,29]]},"references-count":42,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2022,12]]}},"alternative-id":["719"],"URL":"https:\/\/doi.org\/10.1007\/s40747-022-00719-4","relation":{},"ISSN":["2199-4536","2198-6053"],"issn-type":[{"value":"2199-4536","type":"print"},{"value":"2198-6053","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,4,29]]},"assertion":[{"value":"6 October 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 March 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 April 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"On behalf of all authors, the corresponding author states that there is no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}