{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,13]],"date-time":"2026-05-13T09:09:20Z","timestamp":1778663360504,"version":"3.51.4"},"reference-count":65,"publisher":"Institute for Operations Research and the Management Sciences (INFORMS)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Transportation Science"],"published-print":{"date-parts":[[2026,5]]},"abstract":"<jats:p>The increasing demand for expedited e-commerce deliveries, with delivery times of one to three days, highlights the importance of optimizing the middle-mile network. Most retailers store a considerable portion of their inventory at the regional distribution centers (RDCs) outside urban areas, from where it is moved to the customer zones equipped with last-mile distribution facilities as required. Thus, RDC locations become critical in middle-mile operations, directly impacting the transit times to customer zones and, ultimately, the delivery times in the last mile. This paper presents a middle-mile network design problem arising in the context of e-commerce companies in the presence of customers with different delivery time preferences. Specifically, it allows RDCs to satisfy demands from customer zones using delivery times longer than requested, albeit with penalties, if that helps reduce cost without violating the service level requirements of fulfilling at least a given threshold of the demands within the requested delivery times. The problem is formulated as a mixed-integer linear program, for which an exact Lagrangian relaxation-based branch-and-bound algorithm is proposed. Several enhancements to the algorithm are provided, including an efficient Lagrangian heuristic for the primal-bound, a Benders decomposition framework to solve one of the Lagrangian subproblems efficiently, an analytical approach for obtaining Benders optimality cuts, and a partial analytical characterization of Pareto-optimal Benders cuts. With these enhancements, our final algorithm substantially outperforms the state-of-the-art commercial solver, as highlighted by our computational experiments on an extensive set of 220 instances with up to 80 potential RDC locations and 1,000 customer zones. Our best algorithm solves 204 of the 220 instances to 0.50% duality gap compared with only 108 that CPLEX could solve to the same gap within an allowed 10-hour CPU time limit. Furthermore, it achieves an average time savings of 63.24% compared with CPLEX across all the instances.<\/jats:p>\n                  <jats:p>Supplemental Material: The online appendix is available at https:\/\/doi.org\/10.1287\/trsc.2024.0930 .<\/jats:p>","DOI":"10.1287\/trsc.2024.0930","type":"journal-article","created":{"date-parts":[[2026,3,2]],"date-time":"2026-03-02T16:31:38Z","timestamp":1772469098000},"page":"405-423","source":"Crossref","is-referenced-by-count":0,"title":["E-Commerce Middle-Mile Network Design with Delivery Speed Choices and Service Level Constraints"],"prefix":"10.1287","volume":"60","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5365-9517","authenticated-orcid":false,"given":"Aditya","family":"Malik","sequence":"first","affiliation":[{"name":"Supply Chain Consulting, NTT DATA Canada Inc., Halifax, Nova Scotia B3J 3K1, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2029-0204","authenticated-orcid":false,"given":"Shuvabrata","family":"Chakraborty","sequence":"additional","affiliation":[{"name":"Operations Management and Decision Sciences, Indian Institute of Management Raipur, Raipur 493661, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5321-8519","authenticated-orcid":false,"given":"Sachin","family":"Jayaswal","sequence":"additional","affiliation":[{"name":"Operations and Decision Sciences, Indian Institute of Management Ahmedabad, Ahmedabad 380015, India"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"109","reference":[{"key":"B1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2007.04.024"},{"key":"B2","unstructured":"Alamsyah AV , \nPurevdorj N   (2021)\n                      Carbon Efficient Network Design: Evaluating the Trade-offs Between Carbon Emissions, TransportationCost and Delivery Time for a Middle-Mile Distribution Network\n                      (MIT PRESS, Cambridge, MA)."},{"key":"B3","doi-asserted-by":"publisher","DOI":"10.1016\/j.trb.2015.06.001"},{"key":"B5","unstructured":"Amazon Annual Report (2022) Annual reports, proxies and shareholder letters. Accessed January 12, 2024, https:\/\/ir.aboutamazon.com\/annual-reports-proxies-and-shareholder-letters\/default.aspx."},{"key":"B6","doi-asserted-by":"publisher","DOI":"10.1287\/msom.1070.0182"},{"key":"B7","unstructured":"Benidis K , \nPaschos G , \nGross M , \nIosifidis G   (2023) Middle-mile optimization for next-day delivery. Preprint, submitted October 27, https:\/\/arxiv.org\/abs\/2310.18388."},{"key":"B8","doi-asserted-by":"publisher","DOI":"10.1007\/s10479-023-05499-9"},{"key":"B9","doi-asserted-by":"publisher","DOI":"10.1002\/net.22023"},{"key":"B10","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1060.0286"},{"key":"B11","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2018.12.021"},{"key":"B12","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2016.06.039"},{"key":"B13","doi-asserted-by":"publisher","DOI":"10.1002\/9781118537015.ch07"},{"key":"B14","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-88843-9_4"},{"key":"B15","doi-asserted-by":"publisher","DOI":"10.1287\/msom.2021.1045"},{"key":"B17","doi-asserted-by":"crossref","unstructured":"Feng Y, Caldentey R, Xin L, Zhong Y, Wang B, Hu H (2024) Designing sparse graphs for stochastic matching with an application to middle-mile transportation management.\n                      Management Sci.\n                      70(12):8988\u20139013.","DOI":"10.1287\/mnsc.2022.01588"},{"key":"B18","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-32177-2_4"},{"key":"B19","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.2016.2461"},{"key":"B20","doi-asserted-by":"publisher","DOI":"10.1287\/inte.15.2.10"},{"key":"B21","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.1040.0263"},{"key":"B22","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.2016.0692"},{"key":"B23","doi-asserted-by":"publisher","DOI":"10.1016\/j.trb.2023.102782"},{"key":"B24","doi-asserted-by":"publisher","DOI":"10.1007\/s10479-009-0546-z"},{"key":"B25","doi-asserted-by":"publisher","DOI":"10.1287\/opre.46.2.247"},{"key":"B26","doi-asserted-by":"publisher","DOI":"10.1287\/opre.48.3.461.12439"},{"key":"B27","doi-asserted-by":"publisher","DOI":"10.1016\/S0377-2217(98)00008-3"},{"key":"B28","unstructured":"Houston Strategy Forum (2021) Part 3\u2014What is middle mile?\u2014Dr. Scott Mason, Amazon\u2014Supply chain. Accessed June 2, 2024, https:\/\/www.youtube.com\/watch?v=nzxeX7XTIfc."},{"key":"B29","doi-asserted-by":"publisher","DOI":"10.1007\/s10479-016-2353-7"},{"key":"B30","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2023.01.066"},{"key":"B31","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2010.11.028"},{"key":"B32","doi-asserted-by":"publisher","DOI":"10.1111\/j.1937-5956.2002.tb00469.x"},{"key":"B33","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2003.10.031"},{"key":"B34","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-32177-2"},{"key":"B35","doi-asserted-by":"publisher","DOI":"10.1108\/IJPDLM-02-2017-0081"},{"key":"B36","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2020.12.017"},{"key":"B37","doi-asserted-by":"publisher","DOI":"10.1177\/03611981221103596"},{"key":"B38","doi-asserted-by":"publisher","DOI":"10.1287\/opre.29.3.464"},{"key":"B39","unstructured":"Malik A   (2021) Location problems in supply chain design: Concave costs, probabilistic service levels, and omnichannel distribution. PhD thesis, Concordia University, Montreal, Quebec, CA."},{"key":"B40","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.2022.1150"},{"key":"B41","doi-asserted-by":"publisher","DOI":"10.1111\/0022-4146.00100"},{"key":"B42","doi-asserted-by":"publisher","DOI":"10.1023\/A:1020989316737"},{"key":"B43","volume-title":"Knapsack Problems: Algorithms and Computer Implementations","author":"Martello S","year":"1990"},{"key":"B44","doi-asserted-by":"publisher","DOI":"10.1016\/S0377-2217(98)00303-8"},{"key":"B45","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2008.05.007"},{"key":"B46","unstructured":"Naughton K , \nBoyle M   (2019) Walmart targets automated \u2018middle-mile\u2019 delivery to cut shipping costs. Accessed January 25, 2024, https:\/\/www.ttnews.com\/articles\/walmart-targets-automated-middle-mile-delivery-cut-shipping-costs."},{"key":"B47","doi-asserted-by":"publisher","DOI":"10.1016\/S0377-2217(98)00186-6"},{"key":"B48","doi-asserted-by":"publisher","DOI":"10.1111\/itor.12433"},{"key":"B49","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2018.03.021"},{"key":"B50","volume-title":"Exact and Heuristic Approaches to Middle and Last Mile Logistics","author":"Petroianu LPG","year":"2020"},{"key":"B52","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2016.12.005"},{"key":"B53","doi-asserted-by":"publisher","DOI":"10.1016\/j.jtrangeo.2021.103058"},{"key":"B54","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2023.09.032"},{"key":"B55","doi-asserted-by":"publisher","DOI":"10.1016\/j.jtrangeo.2020.102825"},{"key":"B56","doi-asserted-by":"publisher","DOI":"10.4324\/9781003343196"},{"key":"B57","doi-asserted-by":"publisher","DOI":"10.1007\/s10479-012-1237-8"},{"key":"B58","doi-asserted-by":"publisher","DOI":"10.1016\/j.tre.2022.102903"},{"key":"B59","unstructured":"SellersCommerce (2024) Ecommerce statistics: Online shopping trends and data. Accessed May 29, 2025, https:\/\/www.sellerscommerce.com\/blog\/ecommerce-statistics\/."},{"key":"B60","doi-asserted-by":"publisher","DOI":"10.1016\/j.cie.2015.08.012"},{"key":"B61","unstructured":"Statista (2023) Expected delivery time of online purchases in the U.S.: 2021. Accessed February 14, 2024, https:\/\/www.statista.com\/statistics\/1271829\/expected-delivery-time-online-purchases-united-states\/#statisticContainer."},{"key":"B62","unstructured":"Statista (2024) Global retail e-commerce sales 2014-2027. Accessed May 29, 2025, https:\/\/www.statista.com\/statistics\/379046\/worldwide-retail-e-commerce-sales\/."},{"key":"B63","unstructured":"Tanash M   (2018) Hub network design and discrete location: Economies of scale, reliability and service level considerations. PhD thesis, Concordia University, Montreal, Quebec, CA."},{"key":"B64","doi-asserted-by":"publisher","DOI":"10.1007\/s10479-011-1050-9"},{"key":"B65","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2020.07.018"},{"key":"B66","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.1060.0173"},{"key":"B68","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2004.09.012"},{"key":"B69","unstructured":"Zetina CA , \nContreras I , \nJayaswal S   (2021) An exact algorithm for large-scale non-convex quadratic facility location. Preprint, submitted July 20, https:\/\/arxiv.org\/abs\/2107.09746."}],"container-title":["Transportation Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/pubsonline.informs.org\/doi\/pdf\/10.1287\/trsc.2024.0930","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,13]],"date-time":"2026-05-13T08:15:42Z","timestamp":1778660142000},"score":1,"resource":{"primary":{"URL":"https:\/\/pubsonline.informs.org\/doi\/10.1287\/trsc.2024.0930"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,5]]},"references-count":65,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2026,5]]}},"alternative-id":["10.1287\/trsc.2024.0930"],"URL":"https:\/\/doi.org\/10.1287\/trsc.2024.0930","relation":{},"ISSN":["0041-1655","1526-5447"],"issn-type":[{"value":"0041-1655","type":"print"},{"value":"1526-5447","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,5]]}}}