{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,12]],"date-time":"2026-01-12T22:23:33Z","timestamp":1768256613975,"version":"3.49.0"},"reference-count":41,"publisher":"MDPI AG","issue":"4","license":[{"start":{"date-parts":[[2022,4,9]],"date-time":"2022-04-09T00:00:00Z","timestamp":1649462400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100009821","name":"Amt der K\u00e4rntner Landesregierung","doi-asserted-by":"publisher","award":["CARINTHIja 2020"],"award-info":[{"award-number":["CARINTHIja 2020"]}],"id":[{"id":"10.13039\/501100009821","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>The steadily growing popularity of grocery home-delivery services is most likely based on the convenience experienced by its customers. However, the perishable nature of the products imposes certain requirements during the delivery process. The customer must be present when the delivery arrives so that the delivery process can be completed without interrupting the cold chain. Therefore, the grocery retailer and the customer must mutually agree on a time window during which the delivery can be guaranteed. This concept is referred to as the attended home delivery (AHD) problem in the scientific literature. The phase during which customers place orders, usually through a web service, constitutes the computationally most challenging part of the logistical processes behind such services. The system must determine potential delivery time windows that can be offered to incoming customers and incrementally build the delivery schedule as new orders are placed. Typically, the underlying optimization problem is a vehicle routing problem with a time windows. This work is concerned with a case given by an international grocery retailer\u2019s online shopping service. We present an analysis of several efficient solution methods that can be employed to AHD services. A framework for the operational planning tools required to tackle the order placement process is provided. However, the basic framework can easily be adapted to be used for many similar vehicle routing applications. We provide a comprehensive computational study comparing several algorithmic strategies, combining heuristics utilizing local search operations and mixed-integer linear programs, tackling the booking process. Finally, we analyze the scalability and suitability of the approaches.<\/jats:p>","DOI":"10.3390\/a15040125","type":"journal-article","created":{"date-parts":[[2022,4,9]],"date-time":"2022-04-09T05:13:08Z","timestamp":1649481188000},"page":"125","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["Computational Approaches for Grocery Home Delivery Services"],"prefix":"10.3390","volume":"15","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9018-4269","authenticated-orcid":false,"given":"Christian","family":"Truden","sequence":"first","affiliation":[{"name":"Department of Mathematics, University of Klagenfurt, 9020 Klagenfurt, Austria"},{"name":"Department of Operations, Energy, and Environmental Management, University of Klagenfurt, 9020 Klagenfurt, Austria"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6455-5297","authenticated-orcid":false,"given":"Kerstin","family":"Maier","sequence":"additional","affiliation":[{"name":"Department of Mathematics, University of Klagenfurt, 9020 Klagenfurt, Austria"},{"name":"MANSIO Karl Popper Kolleg, University of Klagenfurt, 9020 Klagenfurt, Austria"}]},{"given":"Anna","family":"Jellen","sequence":"additional","affiliation":[{"name":"MANSIO Karl Popper Kolleg, University of Klagenfurt, 9020 Klagenfurt, Austria"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9596-1298","authenticated-orcid":false,"given":"Philipp","family":"Hungerl\u00e4nder","sequence":"additional","affiliation":[{"name":"Department of Mathematics, University of Klagenfurt, 9020 Klagenfurt, Austria"}]}],"member":"1968","published-online":{"date-parts":[[2022,4,9]]},"reference":[{"key":"ref_1","unstructured":"Eurostat (2022, March 05). Internet Purchases by Individuals (Until 2019) (Online Data Code: ISOC_EC_IBUY). Available online: https:\/\/ec.europa.eu\/eurostat\/databrowser\/view\/ISOC_EC_IBUY."},{"key":"ref_2","unstructured":"Eurostat (2022, March 05). Internet Purchases by Individuals (2020 Onwards) (Online Data Code: ISOC_EC_IB20). Available online: https:\/\/ec.europa.eu\/eurostat\/databrowser\/view\/ISOC_EC_IB20\/."},{"key":"ref_3","unstructured":"Eurostat (2022, March 05). Internet Purchases\u2014Goods or Services (2020 Onwards) (Online Data Code: ISOC_EC_IBGS). Available online: https:\/\/ec.europa.eu\/eurostat\/databrowser\/view\/ISOC_EC_IBGS."},{"key":"ref_4","unstructured":"Nielsen (2022, March 05). The Future of Grocery. Available online: https:\/\/www.nielsen.com\/wp-content\/uploads\/sites\/3\/2019\/04\/nielsen-global-e-commerce-new-retail-report-april-2015.pdf."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"227","DOI":"10.1108\/JHLSCM-07-2020-0062","article-title":"Protecting vulnerable people during pandemics through home delivery of essential supplies: A distribution logistics model","volume":"11","author":"Breitbarth","year":"2021","journal-title":"J. Humanit. Logist. Supply Chain. Manag."},{"key":"ref_6","unstructured":"Publications Office of the European Union (2019). Overview Report Official Controls on Internet Sales of Food in EU Member States, European Union."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"313","DOI":"10.1287\/trsc.1040.0105","article-title":"Decision Support for Consumer Direct Grocery Initiatives","volume":"39","author":"Campbell","year":"2005","journal-title":"Transp. Sci."},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Vazquez-Noguerol, M., Comesa\u00f1a-Benavides, J., Poler, R., and Prado-Prado, J.C. (2020). An optimisation approach for the e-grocery order picking and delivery problem. Cent. Eur. J. Oper. Res.","DOI":"10.1007\/s10100-020-00710-9"},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Vazquez-Noguerol, M., Comesa\u00f1a-Benavides, J.A., Riveiro-Sanroman, S., and Prado-Prado, J.C. (2021). A mixed integer linear programming model to support e-fulfillment strategies in warehouse-based supermarket chains. Cent. Eur. J. Oper. Res.","DOI":"10.1007\/s10100-021-00778-x"},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Haber, P., Lampoltshammer, T., Mayr, M., and Plankensteiner, K. (2020, January 13). Shift Planning for Smart Meter Service Operators. Proceedings of the Data Science\u2014Analytics and Applications, Dornbirn, Austria.","DOI":"10.1007\/978-3-658-32182-6"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1007\/s11301-008-0036-4","article-title":"A survey on pickup and delivery problems: Part II: Transportation between pickup and delivery locations","volume":"58","author":"Parragh","year":"2008","journal-title":"J. Betriebswirtschaft"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1016\/j.cor.2016.07.019","article-title":"Home health care routing and scheduling: A review","volume":"77","author":"Fikar","year":"2017","journal-title":"Comput. Oper. Res."},{"key":"ref_13","unstructured":"Rousseau, L.M., and Stergiou, K. An Optimization Approach to the Ordering Phase of an Attended Home Delivery Service. Proceedings of the Integration of Constraint Programming, Artificial Intelligence, and Operations Research, Thessaloniki, Greece, 4\u20137 June 2019."},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Golden, B., Raghavan, S., and Wasil, E. (2008). Challenges and Opportunities in Attended Home Delivery. The Vehicle Routing Problem: Latest Advances and New Challenges, Springer.","DOI":"10.1007\/978-0-387-77778-8"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"966","DOI":"10.1016\/j.ejor.2017.03.060","article-title":"Appointment scheduling and routing optimization of attended home delivery system with random customer behavior","volume":"262","author":"Han","year":"2017","journal-title":"Eur. J. Oper. Res."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"1917","DOI":"10.1108\/IMDS-10-2016-0432","article-title":"Using customer-related data to enhance e-grocery home delivery","volume":"117","author":"Pan","year":"2017","journal-title":"Ind. Manag. Data Syst."},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Ehmke, J.F. (2012). Attended Home Delivery. Integration of Information and Optimization Models for Routing in City Logistics, Springer.","DOI":"10.1007\/978-1-4614-3628-7"},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Gayialis, S.P., Kechagias, E.P., and Konstantakopoulos, G.D. (2022). A city logistics system for freight transportation: Integrating information technology and operational research. Oper. Res. Int. J.","DOI":"10.1007\/s12351-022-00695-0"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"473","DOI":"10.1287\/trsc.2014.0549","article-title":"Choice-Based Demand Management and Vehicle Routing in E-Fulfillment","volume":"50","author":"Yang","year":"2016","journal-title":"Transp. Sci."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"330","DOI":"10.1287\/opre.46.3.330","article-title":"A Generalized Insertion Heuristic for the Traveling Salesman Problem with Time Windows","volume":"46","author":"Gendreau","year":"1998","journal-title":"Oper. Res."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"102023","DOI":"10.1016\/j.omega.2019.01.001","article-title":"Flexible time window management for attended home deliveries","volume":"91","author":"Ehmke","year":"2020","journal-title":"Omega"},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"146","DOI":"10.1287\/ijoc.4.2.146","article-title":"The Vehicle Routing Problem with Time Windows: Minimizing Route Duration","volume":"4","author":"Savelsbergh","year":"1992","journal-title":"ORSA J. Comput."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"492","DOI":"10.1016\/j.trpro.2017.12.046","article-title":"On the Slot Optimization Problem in On-Line Vehicle Routing","volume":"27","author":"Rendl","year":"2017","journal-title":"Transp. Res. Procedia"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"128","DOI":"10.1057\/rpm.2012.51","article-title":"Revenue management opportunities for Internet retailers","volume":"12","author":"Agatz","year":"2013","journal-title":"J. Revenue Pricing Manag."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"435","DOI":"10.1287\/trsc.1100.0346","article-title":"Time Slot Management in Attended Home Delivery","volume":"45","author":"Agatz","year":"2011","journal-title":"Transp. Sci."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"1233","DOI":"10.1111\/itor.12403","article-title":"Heuristics for tactical time slot management: A periodic vehicle routing problem view","volume":"24","author":"Hernandez","year":"2017","journal-title":"Int. Trans. Oper. Res."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"236","DOI":"10.1287\/trsc.2017.0738","article-title":"Differentiated Time Slot Pricing Under Routing Considerations in Attended Home Delivery","volume":"53","author":"Klein","year":"2019","journal-title":"Transp. Sci."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1007\/s12599-014-0321-9","article-title":"When are deliveries profitable?","volume":"6","author":"Cleophas","year":"2014","journal-title":"Bus. Inf. Syst. Eng."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1016\/j.ejor.2013.08.028","article-title":"Customer acceptance mechanisms for home deliveries in metropolitan areas","volume":"233","author":"Ehmke","year":"2014","journal-title":"Eur. J. Oper. Res."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"102305","DOI":"10.1016\/j.omega.2020.102305","article-title":"Multi-criteria decision making in dynamic slotting for attended home deliveries","volume":"102","author":"Lang","year":"2021","journal-title":"Omega"},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"246","DOI":"10.1016\/j.ejor.2008.03.005","article-title":"Dynamic pricing of multiple home delivery options","volume":"196","author":"Asdemir","year":"2009","journal-title":"Eur. J. Oper. Res."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"969","DOI":"10.1007\/s00291-017-0501-3","article-title":"A model-based approximation of opportunity cost for dynamic pricing in attended home delivery","volume":"40","author":"Klein","year":"2018","journal-title":"OR Spectr."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"935","DOI":"10.1016\/j.ejor.2017.06.034","article-title":"An approximate dynamic programming approach to attended home delivery management","volume":"263","author":"Yang","year":"2017","journal-title":"Eur. J. Oper. Res."},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"106242","DOI":"10.1016\/j.cie.2019.106242","article-title":"A taxonomic review of metaheuristic algorithms for solving the vehicle routing problem and its variants","volume":"140","author":"Elshaer","year":"2020","journal-title":"Comput. Ind. Eng."},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"977","DOI":"10.1287\/opre.1040.0124","article-title":"Scenario-based planning for partially dynamic vehicle routing with stochastic customers","volume":"52","author":"Bent","year":"2004","journal-title":"Oper. Res."},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1002\/net.3230110211","article-title":"Complexity of vehicle routing and scheduling problems","volume":"11","author":"Lenstra","year":"1981","journal-title":"Networks"},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"327","DOI":"10.1287\/trsc.1050.0136","article-title":"Incentive Schemes for Attended Home Delivery Services","volume":"40","author":"Campbell","year":"2006","journal-title":"Transp. Sci."},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"369","DOI":"10.1287\/trsc.1030.0046","article-title":"Efficient Insertion Heuristics for Vehicle Routing and Scheduling Problems","volume":"38","author":"Campbell","year":"2004","journal-title":"Transp. Sci."},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"395","DOI":"10.1287\/opre.45.3.395","article-title":"An Optimization Algorithm for the Vehicle Routing Problem with Time Windows Based on Lagrangian Relaxation","volume":"45","author":"Kohl","year":"1997","journal-title":"Oper. Res."},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1016\/j.trpro.2018.09.018","article-title":"Efficient and Easy-to-Implement Mixed-Integer Linear Programs for the Traveling Salesperson Problem with Time Windows","volume":"30","author":"Truden","year":"2018","journal-title":"Transp. Res. Procedia"},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"671","DOI":"10.1126\/science.220.4598.671","article-title":"Optimization by Simulated Annealing","volume":"220","author":"Kirkpatrick","year":"1983","journal-title":"Science"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/15\/4\/125\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T22:50:52Z","timestamp":1760136652000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/15\/4\/125"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,4,9]]},"references-count":41,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2022,4]]}},"alternative-id":["a15040125"],"URL":"https:\/\/doi.org\/10.3390\/a15040125","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,4,9]]}}}