Consistent routing for local same-day delivery via micro-hubs

Ackva, Charlotte; Ulmer, Marlin W. Article — Published Version Consistent routing for local same-day delivery via microhubs OR Spectrum Provided in Cooperation with: Springer Nature Suggested Citation: Ackva, Charlotte; Ulmer, Marlin W. (2023) : Consistent routing for local same-day delivery via micro-hubs, OR Spectrum, ISSN 1436-6304, Springer, Berlin, Heidelberg, Vol. 46, Iss. 2, pp. 375-409, https://doi.org/10.1007/s00291-023-00735-x This Version is available at: https://hdl.handle.net/10419/317069 Standard-Nutzungsbedingungen: Die Dokumente auf EconStor dürfen zu eigenen wissenschaftlichen Zwecken und zum Privatgebrauch gespeichert und kopiert werden. Sie dürfen die Dokumente nicht für öffentliche oder kommerzielle Zwecke vervielfältigen, öffentlich ausstellen, öffentlich zugänglich machen, vertreiben oder anderweitig nutzen. Sofern die Verfasser die Dokumente unter Open-Content-Lizenzen (insbesondere CC-Lizenzen) zur Verfügung gestellt haben sollten, gelten abweichend von diesen Nutzungsbedingungen die in der dort genannten Lizenz gewährten Nutzungsrechte. Terms of use: Documents in EconStor may be saved and copied for your personal and scholarly purposes. You are not to copy documents for public or commercial purposes, to exhibit the documents publicly, to make them publicly available on the internet, or to distribute or otherwise use the documents in public. If the documents have been made available under an Open Content Licence (especially Creative Commons Licences), you may exercise further usage rights as specified in the indicated licence. http://creativecommons.org/licenses/by/4.0/ OR Spectrum (2024) 46:375–409 https://doi.org/10.1007/s00291-023-00735-x ORIGINAL ARTICLE Consistent routing for local same-day delivery via micro-hubs Charlotte Ackva1 ·Marlin W. Ulmer1 Received: 1 July 2022 / Accepted: 25 September 2023 / Published online: 15 December 2023 © The Author(s) 2023 Abstract An increasing number of local shops offer same-day delivery in order to compete with the online giants. However, the distribution of parcels from individual shops to customers reduces the rare consolidation opportunities in the last mile even further. Thus, shops start collaborating on urban same-day delivery by using shared vehicles and micro-depots for consolidated transportation of parcels. At this, many stakeholders (storekeepers, drivers, and customers) need to be coordinated. Consistent routes between micro-hubs simplify the distribution process and increase reliability for all stakeholders involved. The shared vehicles thus conduct consistent daily routes between micro-hubs in the city, serving as transshipment and consolidation centres. This allows stores to bring orders to the next micro-hub, where the parcel is picked up by a vehicle and delivered to the micro-hub closest to its destination—if it is feasible with respect to the vehicle’s consistent daily schedule. Creating effective schedules is therefore very important. The difficulty of finding an effective consistent route is amplified by the daily uncertainty in order placements. We model the problem as a two-stage stochastic program. While the first stage determines the vehicle schedules, the second stage optimises the flow of realised orders. The goal is to satisfy as many orders per day as possible with the shared vehicles. We propose a time-expanded network formulation of the problem which is solved to optimality using commercial MIP-software. We assess our model against a non-consistent upper bound and a practically-inspired heuristic to evaluate the cost of consistency and the consolidation of goods. We analyse the performance of our method for a variety of instance settings. We observe that collaborative delivery via micro-hubs is worthwhile for delivery time promises of two hours or more. Noticeably, for these service promises, the costs of consistency are surprisingly low. BCharlotte Ackva charlotte.ackv[email protected] 1Otto-von-Guericke Universität Magdeburg, Fakultät für Wirtschaftswissenschaft, Management Science, Magdeburg, Germany 123 376 C. Ackva, M. Ulmer Keywords Micro-hubs ·Same-day delivery ·Routing consistency ·Two-stage stochastic programming 1 Introduction Urban areas are facing an increasing amount of parcel transportations. This is reinforced by various factors, first and foremost the expanding e-commerce. In 2020, about 4.05 billion courier, express, and parcel deliveries were made in Germany according to the German Federal Association of Parcel and Express Logistics (Bundesverband Paket und Expresslogistik e.V. (BIEK) 2021). These numbers indicate that customer behaviour is shifting more and more towards online shopping. Purchasing online from the comfort of one’s own home is more convenient and saves customers the inconvenience of a trip to the crowded and congested city centre as well as from queuing in shops. At the same time, online shopping shows disadvantages. Conventional next-day delivery requires waiting for the customers. According to the Ecommerce Delivery Benchmark Report 2022, 37.5% of UK shoppers see the speed of delivery as the most important incentive to purchase online (Metapack 2022). Seeking an instant gratification of their orders, customers hence prefer a same-day or even instant delivery, if available. However, same-day delivery is usually only offered for a small range of products. Local shops can close the gap, offering a large variety of goods relatively close to the customers. To participate in the e-commerce boom, many local businesses thus start to offer fast same-day delivery. Often, they promise to deliver orders within a few hours. Operating an own delivery fleet however, is very cost- and time-intensive for local retailers as additional expenses for staff and vehicles are incurred. Especially for small shops, owning a fleet is usually not worthwhile, as delivery volumes are relatively small. To overcome these problems, local shops start collaborating for joint delivery, allowing them to offer a fast delivery service to customers, while improving low vehicle fill rates and driving down transportation costs (Datex 2021). In a local collaborative distribution network, goods of local shops can be purchased via an online platform and shipment is organised through the collaborative network. Visiting the individual shops for every order is very time-consuming. Moreover, shops are often located in clusters within the city. Therefore, local delivery models make use of transshipment centres within the city to bundle orders of different stores (Burns et al. 2022). A number of services working with a similar strategy can be found in various places, e.g., in several Dutch, Scandinavian and German cities (Cameron 2022; velove 2022; Kiezbote 2021). Such transshipment centres—from now on called micro-hubs—increase consolidation opportunities in the joint delivery process even further. In the local collaborative distribution network, they are used as drop-off and pickup points for online orders. Shops can bring their goods to the closest micro-hub and customers can pick them up a short time later at a nearby micro-hub. Between the micro-hubs, low-emission vehicles such as cargo-bikes perform tours to transport the orders within the network. Organising delivery through micro-hubs offers benefits for storekeepers, drivers, and customers. Storekeepers can participate easily by bringing batches of orders to the nearby micro-hubs a few times per day. Drivers do not need to visit individual stores and customers in unfamiliar and crowded streets anymore. 123 Consistent routing for local same-day delivery via micro-hubs 377 Moreover, customers are no longer constrained to remain at home and wait for their deliveries but have high flexibility concerning the pickup of their parcels. In the local collaborative distribution network, many stakeholders are involved: different storekeepers, drivers, and customers all need to be coordinated. For this reason, the collaborative system must be error-resistant, transparent, and reliable. Consistency in the vehicle tours meets these requirements. Consistent tours in which vehicles follow a predefined daily schedule visiting micro-hubs at predefined times and in a predefined order help to simplify the distribution process and provide reliability to all stakeholders. For storekeepers, consistent routes between micro-hubs offer a reliable structure and planning stability because they can prepare and collect all orders and organise delivery to the next micro-hub at fixed hours every day. Consistent tours are also desirable for drivers. They do not only like to be familiar with facilities, but also with their routes (Wang et al. 2021; Smilowitz et al. 2013;Lian2017). Fixed consistent routes provide operational stability for drivers which improves their satisfaction and hence their productivity (Kovacs et al. 2014a). Besides this, a consistent schedule is also less error-prone. Since consistent schedules offer reliable arrival times, they also increase customers’ satisfaction and trust as well as their attitude towards the supplier (Mancini et al. 2021; Wang et al. 2021; Zhen et al. 2020). This shows positive effects on the overall business and hence can be a significant competitive advantage for the supplier (Subramanyam and Gounaris 2018; Groër et al. 2009). Nahata (2022) argue that the constant online availability of products has raised the expectation that purchases are to be delivered fast and as accurately as promised. Consistent schedules between micro-hubs allow to successfully satisfy these delivery promises without the need of timely re-scheduling calculations. In this paper, we aim to investigate how local collaborative delivery can be performed in a consistent way while using micro-hubs as consolidation centres. Particularly, we are interested in how to design effective consistent routes. We aim to analyse the cost to which consistent tours can be implemented if compared to a non-consistent routing, and to detect the conditions under which consolidation at micro-hubs is beneficial. While consistent routes bring many advantages for shops, customers and drivers, finding effective tours is very challenging given the differences in day-to-day orders. Consistent tours need to ensure high service-availability every day, regardless the realised demand. Customers that cannot be served have to be outsourced or served the next day, which is expensive or may lead to dissatisfaction, respectively. Thus, the goal is to find a consistent tour between micro-hubs that maximises the expected amount of delivered parcels per day. In order to provide effective schedules, it is important that they are robust to demand variations in time, respect the pickup and delivery sequence of parcels, and capture the expected daily demand pattern. We formulate the problem as a two-stage stochastic program. The first stage of the model aims to find a consistent routing schedule for the delivery vehicle between micro-hubs without the exact demand being known. Given this schedule, the second stage determines the flow of realised parcel orders for a specific day. We model the problem over a discrete time horizon using a time-expanded network formulation. Our formulation allows solving realistically-sized instances with commercial MIP- solvers. To determine a solution for the first stage of the problem, several potential future demand scenarios are sampled, which are considered simultaneously in the 123 378 C. Ackva, M. Ulmer extended form of the two-stage stochastic model. The extended form is then solved with Gurobi (Gurobi Optimization 2021). In a computational study, we assess the exact solution against a number of benchmarks with respect to solution quality and total runtime. To evaluate the cost of consistency, we use a solution without consistency constraints, i.e. a daily re-optimised solution, as an upper bound. We further implement a scenario-decomposition approach as well as a practically-inspired heuristic solution as benchmarks. In our computational study, we observe that optimisation is very valuable compared to the practically-inspired heuristic. Even the scenario-decomposition approach leads to substantial improvements. We further show that the costs of consistency for same-day delivery are rather negligible if compared to a daily re-optimised, non-consistent routing policy. If delivery time promises get tighter however (e.g. 2h), the costs of consistency become noticeable. Moreover, we find that consolidation of parcels at micro-hubs may be worthwhile only for delivery promises of two hours or more. We further evaluate the solutions determined by our model in a dynamic simulation and find that they are quite effective for the large majority of instances. The contributions of this paper are as follows. We are among the first to investigate how micro-hubs can be utilised for collaborative same-day delivery of local shops and for what type of delivery promise they are effective. We further analyse at which cost consistent routes can be implemented between micro-hubs in this delivery system. We present a stochastic two-stage integer program that finds a consistent tour between micro-hubs for pickup and delivery of parcels in a collaborative local delivery system. We provide a formulation that allows us to solve realistically-sized instances to optimality. We perform a targeted analysis and identify important managerial insights. The remaining part of this paper is structured as follows. In Sect.2, we present related literature. In Sect.3, we define the model for consistent pickup and delivery routing. In Sect.4, we present setup and results of the computational experiments. We finish our paper with a conclusion and outlook in Sect. 5. 2 Literature review on consistent vehicle routing Several aspects have to be considered when planning consistent schedules in local delivery services: pickup and delivery needs to be organised through a two-echelon transportation system with transshipment facilities, while consistency in vehicle’s routes is to be maintained. This problem of picking up and delivering parcels during one route is denoted as the vehicle routing problem (VRP) with simultaneous pickup and delivery; a review on such problems can be found in Koç et al. (2020). Introducing transshipment facilities to a pickup and delivery problem leads to a two-echelon logistic system which is usually operated by two fleets of vehicles. In general, this is denoted as the two-echelon vehicle routing problem (2E-VRP). A literature review on such problems is presented by Cuda et al. (2015) and more recently by Jiang and Li (2021) and Sluijk et al. (2022). However, most papers focus on delivery only, assume demand to be deterministic, and consequently route first and second fleet at the same time. In contrast, our model aims to determine a routing schedule for the first fleet only in order to provide consistent pickup and delivery service despite daily varying demand. 123 Consistent routing for local same-day delivery via micro-hubs 379 We hence seek to find consistent tours for the fleet serving micro-hubs. We therefore refer to different concepts of consistency in the following. Kovacs et al. (2014a) provide a survey on consistency in VRPs. They distinguish arrival time, person-oriented, and delivery quantity consistency, and provide modelling concepts and solution methodology for each type. In our context, we require the even stronger concept of routing consistency: vehicles should always conduct the very same tour, i.e. visit the same micro-hubs at the same times each day. This captures the pickup and delivery dimension of our problem and allows storekeepers to organise transportation of their orders to corresponding micro-hubs in time for further shipment. Literature on this concept of routing consistency is very scarce. A close concept is presented by Wang et al. (2021) who develop a VRP for simultaneous distribution and collection of packages over several days with generalised consistency requirements. In their paper, schedules are called consistent if they satisfy consistency in three dimensions: the arrival time at customer locations should not vary more than a number of Ltime units (time consistency), customers should not be served with more than a number Eof different drivers (driver consistency), and vehicle routes should not vary by more than Fdifferent arcs (route consistency). The authors propose an exact solution method to deal with the generalised consistency constraints. Our understanding of route consistency corresponds to the special case of Wang et al. (2021) with L=0, E=1, and F=1 /D, where Dis the number of days in the planning horizon. However, the problem studied by Wang et al. (2021) addresses deterministic demand, whereas demand is considered to be stochastic in our problem setting. Besides this, arrival time consistency is the closest concept to route consistency in literature and common modelling approaches are imposing hard or soft constraints, previously assigning time windows to customers or determining routes a-priori. We emphasize here that arrival time consistency is not sufficient in our context. For a parcel request to be fulfilled, pickup and delivery micro-hub need to visited after each other, otherwise the order cannot be fulfilled. The sequence of stops thus plays a major role for the success of the system, consequently consistency should be interpreted in terms of entire routes. Exemplary publications and different approaches on arrival time consistency can be found in Kovacs et al. (2014a) and more recently in Song et al. (2020). Most relevant to our work are consistent VRPs including pickup and delivery. Zhen et al. (2020) propose a consistent VRP for simultaneous distribution and collection in reverse logistics. Emadikhiav et al. (2020) address the simultaneous pickup and delivery of orders of an instrument-calibration company. The goal is to minimise transportation costs while limiting late deliveries and enforcing consistent arrival times. A prominent technique to maintain time consistency is bounding the variation in arrival times at customer locations over the planning horizon, which usually consists of several days. Among others, this approach is applied by Groër et al. (2009) who introduce the consistent VRP (ConVRP) for serving customers repeatedly over a given planning horizon. They present a mixed-integer formulation and a solution approach based on a record-to-record travel algorithm. Tarantilis et al. (2012) and Kovacs et al. (2014b) develop further solution approaches to the same problem. Extending this problem, Subramanyam and Gounaris (2018) suggest a TSP with arrival time consistency where waiting at customer locations is allowed. They further present an exact branch-and-bound-search procedure. Some works combine arrival time and 123 380 C. Ackva, M. Ulmer driver consistency. Lian (2017) for example, investigates the trade-off between travel costs and service consistency through a multi-objective ConVRP. Mancini et al. (2021) introduce a ConVRP with time and driver consistency, as well as workload balance in collaborative logistics. They apply a matheuristic and an iterated local search algorithm to solve their problem. All ConVRP-variants deal with serving known customers over a number of periods and are therefore, in contrast to our work, deterministic. Still, our solution method samples a set of scenarios to cope for the uncertainty in demand and solves the corresponding deterministic problem. Thus, there are some similarities to the ConVRP, but also significant differences, since we consider pickup and delivery as well as repeated visits of the same micro-hub locations over the course of day. Two other prominent consistency concepts are assigning time windows to customers previously or determining tours a-priori which are possibly adapted later to the realised demand through recourse actions. The latter can be applied for stochastic customers as well as stochastic demand while the former is applicable only if customer locations are known in advance and only demand volumes vary from day to day. Assigning time windows is often modelled by a two-stage stochastic programming formulation. Spliet and Gabor (2015) for example assign time windows to each customer at the first stage. They formulate a MIP for this stage with the objective to minimise expected travel costs. Once demand volumes are revealed, a VRP has to be solved meeting the previously determined time windows. Dalmeijer and Spliet (2018) and Dalmeijer and Desaulniers (2021) can improve the computational performance of this problem by strengthening the problem formulation through valid inequalities and by developing symmetry breaking strategies. A discrete variant of the above problem is presented by Spliet and Desaulniers (2015). They also propose an exact branch-price-and-cut algorithm. Spliet et al. (2018) extend the problem to time-dependent travel times and develop a branch-price-and-cut algorithm to solve the problem to optimality. A similar problem of previously assigning time windows to customers on first and routing vehicles on second stage is proposed by Subramanyam et al. (2018). They additionally consider stochastic travel times and propose a scenario decomposition algorithm to solve the problem. Precedently assigning time windows is not enough for our pickup and delivery routing problem as we look for a schedule with exact time synchronisation. We are facing stochastic demand and need to determine routes before demand becomes known, e.g. based on stochastic information. This concept of time consistency is called a priori routing or finding master tours. When demand is revealed, these routes are commonly updated using recourse actions, such as skipping customers or restocking at the depot for example. Some common recourse strategies are explained in Kovacs et al. (2014a). Often, such problems are modelled as a two-stage stochastic program: at the first stage, an a-priori routing is determined under uncertain demand. At the second stage, uncertainty is revealed and corresponding recourse actions are selected. Reviews on a-priori routing problems and corresponding solution methods can be found in Bertsimas et al. (1990); Campbell and Thomas (2008) and Kovacs et al. (2014a). We concentrate on the most relevant work for our context in the following. Hvattum et al. (2006) use a multistage stochastic programming formulation to model a VRP with both deterministic and stochastic customers. Recourse strategies are applied repetitively based on a sample scenarios heuristic approach. Sungur et al. (2010) describe a courier 123 Consistent routing for local same-day delivery via micro-hubs 381 delivery problem with stochastic customers and uncertain service times. They offer a multi-objective two-stage program for a variant of the ConVRP with time windows to develop a-priori master tours using a scenario-based solution approach. Uncertain travel times and stochastic customers are also considered in Sampaio et al. (2019), who propose a VRP with roaming delivery locations which they solve with a scenariobased sample average approximation. Angelelli et al. (2017) solve a probabilistic team orienteering problem through a two-stage stochastic program that maximises the expected profit of visited customers. They solve their problem applying a branch- and-cut approach as well as different heuristic methods. There is some recent work on two-stage stochastic programs for VRPs with stochastic demands and recourse actions. Lagos et al. (2019) suggest such a model minimising the expected travel costs. The models proposed by Bernardo and Pannek (2018); Salavati-Khoshghalb et al. (2019) and Florio et al. (2022) additionally aim to minimise the expected costs of recourse actions. Similar to our problem, Crainic et al. (2016) suggest a two-stage stochastic programming formulation for the 2E-VRP with stochastic demand. At the first stage, an urban-vehicle service network design model routes the first fleet and determines the general load of micro-hubs, using an approximation of the routing cost from microhubs to customers. The second stage concerns the routing of second fleet vehicles and possible recourse actions for the first fleet. The authors evaluate different recourse strategies through repetitively applying the adjusted plan for each planning period. Their work differs from ours as determining loads of hubs is not part of our problem, further we do not apply recourse strategies since we seek a consistent routing between micro-hubs. Consistent master routes are also determined in the work of Visser and Savelsbergh (2019). They investigate a strategic time slot management problem where master tours and time windows at customer locations are determined simultaneously on first stage, facing uncertain demand. In difference to our problem, assigning time slots instead of precise arrival times is sufficient. Further, recourse actions may be applied after demand realisation in the sense that customers may be skipped if they cannot be served within their time window. A different approach for consistent vehicle tours is used by Orenstein and Raviv (2022). The authors propose an urban parcel pickup and delivery system including so called service points that can serve as consolidation, transshipment, and pickup point for customers or drivers. Customers may be served from several service points, what further increases flexibility in the delivery process. They develop a myopic policy to route stochastically arriving parcels based on given vehicle routes. Vehicle routes are determined a-priori using a math heuristic. The mentioned papers suggest how to derive consistent tours with later recourse actions for different problem settings. Here, skipping customer nodes or returning to the depot preemptively are the most prominent recourse actions. In our context however, skipping micro-hubs might prevent some parcels to be delivered, others to be picked up, eventually leading to a lower total delivery volume. Because of the consolidation of parcels at micro-hubs, it is highly unlikely that a micro-hub shows no demand. Note that this is a significant difference to the traditional ConVRP literature, where usually one node corresponds to a single customer, making the presence of demand more volatile. To this end, we do not include recourse actions in our model. We summarise related literature on two-stage stochastic routing problems in Table 1. For each paper, we classify the type of route consistency, the source of uncertainty, 123 382 C. Ackva, M. Ulmer Table 1 Related literature on two-stage stochastic routing problems Paper Consistency Stochasticity 1st Stage 2nd Stage Objective Solution method M TW Pickup/delivery Demand Time M TW Parcel flow Routing Service Costs Scenario-based Exact Hvattum et al. (2006)()()()() Sungur et al. (2010)()()()() Spliet and Gabor (2015) Spliet and Desaulniers (2015) Crainic et al. (2016)()() Angelelli et al. (2017)()()()() Bernardo and Pannek (2018)()()() Dalmeijer and Spliet (2018) Spliet et al. (2018) Subramanyam et al. (2018) Lagos et al. (2019)()()() Salavati-Khoshghalb et al. (2019)()()() Sampaio et al. (2019)()()() Visser and Savelsbergh (2019)()()() Song et al. (2020)() Florio et al. (2022)()()() Our paper      Following abbreviations are used: M, master tour (with recourse); TW, time window assignment 123 Consistent routing for local same-day delivery via micro-hubs 389 xk (i,t),( j,u)for each k∈Kand for each (i,t), ( j,u)∈AK. It is defined as: xk (i,t),( j,u):= 1,if vehicle ktravels directly from node (i,t)to node (j,u), 0,otherwise. The second stage concerns the operational daily planning of which parcels to serve. Therefore, we use a binary second stage decision variable yp,sfor all p∈Psto decide whether parcel pis served in scenario s∈Sor not: yp,s:= 1,parcel pis served in scenario s∈S, 0,otherwise. We further consider binary second stage decision variables for parcels to decide which arcs they use on their itineraries. For each scenario s∈S, each parcel p∈Ps, and each arc (i,t), ( j,u)∈Ap,swe hence define: zp (i,t),( j,u),s:= 1,if parcel p∈Pstravels directly from node (i,t)to node (j,u)in scenario s∈S, 0,otherwise. The objective of the model is to maximise the expected number of delivered parcels. 3.3.2 The stochastic two-stage model With the notation above we now state the two-stage stochastic integer program for consistent routing in collaborative urban delivery as follows. Let x,ys, and zsbe the vectors with entries defined as above. Then we are looking for a solution of the form x,(ys,zs)s∈Sto the two-stage stochastic program: max  s∈S ps p∈Ps yp,s(2-SP) s.t. (x,ys,zs)∈Cs∀s∈S, where Csrepresents the feasible set corresponding to scenario sdefined by Constraints (1)to(15) following below. The objective of (2-SP) maximises the expected amount of parcels that can be served, according to the probability of occurrence of each scenario. Note that the first-stage decision variable xis invariant with regard to the resulting scenario. Thus, the following constraints ensure a feasible routing for the vehicles for any demand realisation. Constraints (1) and (2) ensure that each vehicle starts and ends its tour at the depot. Through Constraints (3) each vehicle leaves the depot at most once, i.e. vehicles do not return to the depot during their route. Together with the flow conservation constraints in Constraints (4), this prohibits vehicles to visit the depot during service. 123 390 C. Ackva, M. Ulmer  ((0,0),( j,u))∈AK xk (0,0),( j,u)=1∀k∈K,(1)  ((i,t),(0,Tmax))∈AK xk (i,t),(0,Tmax)=1∀k∈K,(2)  ((0,t),( j,u))∈AK\AV0 xk (0,t),( j,u)≤1∀k∈K,(3)  ((i,t),( j,u))∈AK xk (i,t),( j,u)= ((j,u),(i,t))∈AK xk (j,u),(i,t)∀j∈VH∪V0,∀k∈K, ∀u∈T\{0,Tmax}.(4) The following Constraints (5)to(8) are concerned with the routing of parcels, that does depend on the resulting scenario. For this reason, all following constraints must be kept for any demand realisation s∈S. Constraints (5) ensure that each parcel p∈Pshas to start its itinerary at its pickup micro-hub opat its release time rp.In the case where pickup and delivery customer are mapped to the same micro-hub, no transportation by vehicle is needed. This is captured by Constraints (6). Constraints (7) and (8) state that each parcel that is served must leave its pickup hub and enter its delivery hub. Note that with this formulation parcels must leave their pickup hub at time t=rpand enter their delivery hub at time t=rp+TP. However, this may be satisfied via waiting arcs such that physical leaving and entering may happen later and earlier, respectively. Parcels hence are present in the system between their release time rpand the end of their delivery promise rp+TP, which is when the customer picks up the order. Within this time, flow conservation of parcels at micro-hubs is required, guaranteed by Constraints (9).  ((i,rp),( j,u))∈Ap,s,i=op zp (i,rp),( j,u),s=0∀p∈Ps,∀s∈S,(5) zp (i,t),( j,u),s=0∀(i,t), ( j,u)∈Ap,s\AWp,s, ∀p∈Ps:op=dp,∀s∈S,(6)  ((op,rp),( j,u))∈Ap,s zp (op,rp),( j,u),s=yp,s∀p∈Ps,∀s∈S,(7)  ((i,t),(dp,rp+TP))∈Ap,s zp (i,t),(dp,rp+TP),s=yp,s∀p∈Ps,∀s∈S,(8)  ((i,t),( j,u))∈Ap,s zp (i,t),( j,u),s= ((j,u),(i,t))∈Ap,s zp (j,u),(i,t),s∀j∈VH, ∀t∈T:rp<t<rp+TP. ∀p∈Ps,∀s∈S.(9) Parcels cannot move independently in the network but have to be transported by vehicles. To this end, Constraints (10) link the routes of parcels to those of vehicles. 123 Consistent routing for local same-day delivery via micro-hubs 391 More precisely, Constraints (10) make sure a parcel can move along an arc only if transported by a vehicle on that arc. With this formulation, parcels may change vehicles (at micro-hubs) on their route. zp (i,t),( j,u),s≤ k∈K xk (i,t),( j,u)∀((i,t), ( j,u))∈Ap,s\AWp,s, ∀p∈Ps,∀s∈S.(10) To not exceed vehicle capacity constraints, we have to control the maximum load capacity on vehicle arcs, which is done with Constraints (11). Note here that the homogeneous parcel volume of 1 is important so that Constraints (11) are meaningfully defined. Otherwise, if the parcel volume is not an integer divisor of the vehicle capacity CK, this formulation might cause split deliveries, which is not allowed. Limited microhub capacity is controlled via restricting the load on waiting arcs through Constraints (12).  p∈P((i,t),( j,u),s) zp (i,t),( j,u),s≤CK· k∈K xk (i,t),( j,u)∀((i,t), ( j,u))∈ p∈Ps Ap,s\AWp,s,∀s∈S, (11)  p∈P((i,t),( j,u),s) zp (i,t),( j,u),s≤CH∀((i,t), ( j,u))∈ p∈Ps AWp,s,∀s∈S.(12) Finally, Constraints (13)to(15) state the domain of the decision variables. xk (i,t),( j,u)∈{0,1}∀((i,t), ( j,u)) ∈AK, ∀k∈K,(13) zp (i,t),( j,u),s∈{0,1}∀((i,t), ( j,u)) ∈Ap,s, ∀p∈Ps,∀s∈S,(14) yp,s∈{0,1}∀p∈Ps,∀s∈S.(15) Note that for our computational study the decision variables yp,s,p∈Ps,s∈S,are relaxed to be continuous, i.e. yp,s∈[0,1]∀p∈Ps∀s∈S. This is computationally advantageous (see Appendix A.2 for details), and integrality is implied by Constraints (7), (8), and (14). 3.3.3 The deterministic second-stage and single-stage model Although demand is not known at the first stage, the two-stage program allows us to find a vehicle routing schedule that maximises the expected number of fulfilled orders. Based on this schedule  x, the actual flow of parcels can be planned at the second stage once demand is revealed. For this, we define the deterministic second-stage model for 123 392 C. Ackva, M. Ulmer a given vehicle routing  xand a realised demand scenario sas follows: max  p∈Ps yp,s(2nd-SP) s.t.  x,ys,zs∈Cs. The feasible set Csis defined as above, Constraints (1)to(15), with the only difference that  xis treated like a given value instead of a decision variable. The objective of model (2nd-SP) is to serve as many parcel requests as possible. In our computational study we use a scenario decomposition heuristic (see Sect.4.2) which requires solving the routing of vehicles and the flow of parcels simultaneously for a given realised demand scenario. To that end, we define the deterministic singlestage problem for a specific scenario s∈Ssimilar to Model (2nd-SP)as: max  p∈Ps yp,s(1-SP) s.t. (xs,ys,zs)∈Cs, where now xsconstitutes a scenario-dependent decision variable. 4 Computational study In this section we present the experimental setup and results of our computational study. In Sect. 4.1, we explain how instances are generated. In Sect.4.2, we introduce benchmark policies to assess the solutions obtained by our approach. In Sect. 4.4, present our computational results. 4.1 Instance generation The following explains how we generate different possible demand scenarios. We assume demand to be distributed over a square city area with a radius of r=10 (km). We motivate our instances by the city structure of Braunschweig, Germany, see Ulmer and Streng (2019). Braunschweig shows the classical European city structure with a city centre and several ring roads. Several parcel locker stations of the German post service DHL are placed on the main ring road in Braunschweig. Inspired by this, we place 5 micro-hubs equidistantly on a circle with a radius of 5 (km), which is half of the city radius. Moreover, with such a circular structure the micro-hubs are evenly spread over the city area. The depot is located at the middle of the upper edge of town. Figure5gives an illustration of the circular location of five micro-hubs and the depot in a square city. We assume that each micro-hub has a maximum capacity of 20 parcels. One delivery vehicle conducts service between micro-hubs. In our computational study, we assume the vehicle to be a large cargo bike with a speed of 25 (km /h) and maximum capacity of 20 parcels. 123 Consistent routing for local same-day delivery via micro-hubs 393 Fig. 5 Example of demand structure uniform (left) and clustered (right) For our experiments, we test different delivery promises and service time horizons. We investigate three service designs: “instant”—instant delivery (60 min) in a short horizon (240 min.); “fast”—fast delivery (120 min) in a medium horizon (360 min); and “same-day”—delivery on the same day (480 min) in a large horizon (480 min). The latter is equivalent to not imposing customer time windows. We use a discrete step size of δ:= 10 minutes in the time expanded network. The travel time ti,jbetween two locations i,j∈VH∩V0is computed via the Euclidean distance between iand jdivided by the vehicle’s velocity and is then rounded up to the next multiple of δ. For each service design, we run our experiments with a varying number of parcels, |P|∈{40,80,120}. For each parcel request we sample a release time, a pickup store and a delivery customer location within the city area. All parcels have a homogeneous volume of one. The release time of a parcel is drawn uniformly over the time horizon T={0,10,...,Tmax −120}. Pickup micro-hub (origin) and delivery micro-hub (destination) of a parcel are the micro-hub closest to the corresponding pickup store and delivery customer, respectively. For spatial distribution of stores and customers we consider two different demand patterns: •uniform: Stores and customers are uniformly distributed over the entire city area. An example of this customer distribution is shown on the left-hand side of Fig.5. This is inspired by the city structure of Göttingen, Germany, where stores can be found over the entire city area and inhabitants live both inside and outside the city centre. •clustered: Stores and customers are clustered within the city. Inspired by the city structure of Braunschweig, we designate the inner part of the city as city centre, the south-western part as industrial area, and northern as well as eastern part as residential area. The exact layout is shown on the right-hand side of Fig.5.Stores are located in the city centre and industrial area; customers mostly in residential, but also in the industrial area. More details are presented in Appendix A.1. In Table 3we summarise the parameter values used for scenario generation in the computational experiments. 123 394 C. Ackva, M. Ulmer Table 3 Parameter values used in computational experiments Description Notation Instant Fast Same-Day Service time horizon Tmax 240 360 480 Delivery promise TP60 120 480 Nr. parcels |P|40, 80, 120 Demand pattern – uniform, clustered Nr. micro-hubs |VH|5 Nr. vehicles |K|1 Max. capacity micro-hub CH20 Max. capacity vehicle CK20 Vehicle velocity vK25 Parcel volume up1 Length of discrete time step δ10 4.2 Benchmarks In our computational study, we solve the extended form of the two-stage model (2-SP) for a sampled set of scenarios, which are generated as described in Sect. 4.1. We refer to this approach as the EXACT method or policy. In our computational analysis, we compare this policy to several benchmark policies, which we introduce below. •DAILY: First, we use a policy in which routing consistency constraints are relaxed. To this end, we solve the deterministic single-stage model (1-SP) separately for each scenario. As this is done scenario-dependent, we can determine vehicle routing and parcel flow simultaneously on one stage. Given the optimal solution for this deterministic “daily” problem, this constitutes a non-consistent upper bound to the stochastic two-stage problem. Since this policy requires re-planning on a daily basis, we refer to this as the DAILY policy. •DECOMPOSITION: Next, we present a scenario decomposition method. For a given set of sampled scenarios and their solutions, we choose the scenario solution with best expected performance. For this, each scenario-dependent solution is evaluated on a number of new scenarios using the deterministic second-stage model (2nd-SP) and its corresponding objective value is computed. Finally, the scenario solution with best average objective value is selected, as this one is expected to perform best regardless of the true future demand scenario. •FIXED: Last, we implement a practically-inspired FIXED policy that aims on a high flexibility and reachability among micro-hubs. The policy should allow to reach all micro-hubs from any micro-hub and further should not loose too much time between any two visits. Therefore, we suggest a circular route. The vehicle leaves the depot and visits each micro-hub, in ascending order. When the last micro-hub is reached, the vehicle continues to micro-hub 1 to close the circle. Instead of traversing the same circle again, the vehicle turns and takes the same route back to the depot, visiting all micro-hubs again, but in descending order. This guarantees that not too much time is needed for delivery between two micro-hubs. 123 Consistent routing for local same-day delivery via micro-hubs 395 Fig. 6 FIXED policy for Tmax =360, in minutes after the start of the service horizon If the service time horizon is longer than the total tour length, the vehicle starts its tour such that the tour finishes at Tmax. This is motivated by the idea to increase consolidation opportunities: visiting micro-hubs at a later point in time may allow to transport more parcels, as more demand will arise during the course of the day. In Fig.6, we provide an illustration of the FIXED policy for Tmax =360. 4.3 Implementation In this section, we comment on the implementation of the models (1-SP) and (2-SP) and describe how the different benchmarks are evaluated. Both models (1-SP) and (2-SP) are implemented in Gurobi 9.1. (Gurobi Optimization 2021). For optimisation in Gurobi, we set a time limit of 24h per instance. We further provide a feasible starting solution in which the vehicle stays in the depot and hence no parcels are transported. If the problem cannot be solved to optimality within this time, the current best solution and relative MIP optimality gap are recorded. Based on preliminary experiments, we set the number of scenarios to 15 (in-sample). This number is used for the EXACT and the DECOMPOSITION policies. The FIXED policy is rule-based and does not require any scenarios, while the DAILY policy is calculated independently for every scenario. For final evaluation of the different benchmarks, the solutions obtained by each policy are evaluated on a set of 100 new generated scenarios (out-of-sample), using the deterministic second-stage model (2nd-SP), and average objective values are computed for final comparison. 4.4 Computational results We present our computational results in the following. In Sect.4.4.1, we conduct a method analysis investigating the runtime and the performance of the extended twostage model and benchmark policies. In Sect. 4.4.2, we then analyse the effect of different service designs and demand patterns and assess the value of consolidation 123 396 C. Ackva, M. Ulmer at micro-hubs as well as the cost of consistent routing, In Sect. 4.4.3, we examine the structure of the consistent routes in more detail. 4.4.1 Method analysis In this section, we first analyse the runtime needed for the different policies and then investigate the resulting objective values and their gap to the DAILY policy. Runtime Analysis. In this section, we analyse the different consistent policies with respect to their total runtime. Table 4shows the total runtime of the EXACT and the DECOMPOSITION policy on each instance in seconds. As the route of the FIXED policy is given beforehand, only arrival times of the predefined sequence of stops have to be computed. This requires less than 0.0001s per instance, thus it is not included in the table. Recall that the time limit for the EXACT policy was set to 24h, i.e. 86400s. If the optimal solution is not found within this time limit, this is indicated by “>86400” in the table. In this case, the current best solution xand objective upper bound UB are recorded. With this, we compute the relative MIP optimality gap as (UB−x) /UB.Asthe problem at hand is an maximisation problem, this gives an estimate about the quality of the solution found so far. The table displays the gap of each solution determined via the EXACT method in brackets behind its runtime. From the table, we deduce the following main observations. First, the total runtime of the extended two-stage model increases as the number of parcels increases and as the service time horizon gets larger. Both factors raise the complexity of the combinatorial optimisation problem, thus making it harder to solve. Instances with 120 parcels can only be solved to optimality on the instant service design. On the fast and same-day service design, the time limit is hit without finding the optimal solution. However, in case of the fast service design, the solutions found within the time limit have a relatively small optimality gap of 1.34% and 5.31% for uniform and clustered demand, respectively. On the same-day service design in contrast, the optimality gap for 120 parcels is above 40% on both demand patterns. We also see that an increase in the number of parcels has a greater effect on the increase in runtime than an increase in the service time horizon. The second observation we make is that the solutions for the DECOMPOSITION policy are computed in much shorter time than the EXACT solution. While the DECOMPOSITION policy requires about the same runtime on instances with the instant service design, on the fast service design it requires only 0.84–6.47% of the runtime that is needed to determine the EXACT solution. On the same-day service design, it requires at most 2.93% of the runtime of the EXACT method (on those instances that were solved to optimality). Computation time of the DECOMPOSITION policy is thus significantly lower than for the EXACT method. While the EXACT method cannot solve instances with 120 parcels on the fast and same-day service design to optimality, the DECOMPOSITION policy can treat those instances within less than 5h. Objective Values. After analysing the runtime of the different policies, we investigate their average performance in this section. Figure7and Fig.8show the average ser- 123 Consistent routing for local same-day delivery via micro-hubs 397 Table 4 Total runtime in seconds for the EXACT and the DECOMPOSITION policy on all instances, with relative MIP optimality gap for the EXACT policy Design Policy 40 Parcels 80 Parcels 120 Parcels Instant Uniform EXACT 38.44 (0%) 97.13 (0%) 96.20 (0%) DECOMPOSITION 38.23 81.00 130.98 Clustered EXACT 39.18 (0%) 82.52 (0%) 301.64 (0%) DECOMPOSITION 36.87 80.19 132.68 Fast Uniform EXACT 4000.41 (0%) 38477.79 (0%) >86400 (1.34%) DECOMPOSITION 131.25 324.57 1470.46 Clustered EXACT 2174.11 (0%) 15793.85 (0%) >86400 (5.31%) DECOMPOSITION 140.68 438.76 6281.76 Same-day Uniform EXACT 58032.19 (0%) 84227.65 (0%) >86400 (41.50%) DECOMPOSITION 548.03 2464.99 10755.90 Clustered EXACT 54528.15 (0%) >86400 (4.22%) >86400 (45.96%) DECOMPOSITION 520.36 3411.93 17789.62 123 398 C. Ackva, M. Ulmer Fig. 7 Average service rates on uniform demand vice rates that are obtained by the different policies for each combination of parcel requests (columns) and service designs (rows). As explained in Sect.4.3, each policy is evaluated on a set of 100 out-of-sample scenarios. On instances where the extended two-stage model is not solved to optimality within the time limit, this is highlighted by dashes on the corresponding bar. We see that the EXACT method outperforms the remaining consistent benchmarks on all instances where it is solved to optimality (except the DAILY policy, which represents an upper bound). Even when not solved to optimality, it exceeds the remaining policies slightly except on instances with the same-day service design and 120 parcels (where the MIP optimality gap is above 45%). In particular, the EXACT method reaches average service rates that are very close to the DAILY upper-bound policy on the same-day service design. With clustered demand and 40 parcels for example, it allows to fulfil 39.77 parcel requests on average which is only little behind the upper bound of 39.99 parcel requests. We further observe that the FIXED benchmark performs worst on almost all instances. Since this policy does not incorporate any knowledge about potential 123 Consistent routing for local same-day delivery via micro-hubs 405 the routing of the courier bikes. Delivery time promises are then to be implemented in a door-to-door policy to ensure that the local collaborative system is prompt, reliable, and tailored to meet customers’ needs. There are several avenues for future research. We have seen that micro-hubs can be very valuable for deliveries within two hours. Future work may further investigate what deliveries are suitable for consolidated shipping and which should be shipped directly. In our research, we have focused on the single-vehicle case for moderately sized cities to analyse the functionality of the two-stage model and the impact of consistent routes. Future work may extend the computational study to larger cities and fleets. While the proposed model is already designed to capture multiple vehicles, it is very likely that the second stage problems cannot be solved with standard methodology. Instead, metaheuristics might be developed. Our model further is restricted to one microhub per shop and per customer. To increase the flexibility of stores and customers, several close-by micro-hubs may be used for drop-off and pickup, respectively. This would require a reformulation of the model, explicitly deciding about the origin and destination of each parcel. Furthermore, recourse actions such as skipping hubs may become useful in this case. Further, in this research we have assumed that all parcels become known at once during the day. As suggested above, future work may model the arrival of parcels dynamically every day. This would replace the second stage of our model with a stochastic dynamic process, for which anticipatory dynamic policies for the parcel flow decisions may be developed. Determining the consistent tour from a dynamic routing policy of the vehicles would be another, currently unexplored, research opportunity. Acknowledgements The authors’ research is partially funded by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) Emmy Noether Programme, project 444657906. We gratefully acknowledge their support. Funding Open Access funding enabled and organized by Projekt DEAL. Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/. A Appendix In this appendix we provide background information on some parts of our work. In Appendix A.1, we explain the distribution of shops and customers in the clustered demand pattern. In Appendix A.2, we present a brief runtime comparison of the single stage model (1-SP) when decision variables yp,p∈Ps,s∈Sare defined to be binary or continuous, respectively. In Appendix A.3, we state the pseudo-code for the dynamic evaluation of the second stage. 123 406 C. Ackva, M. Ulmer Table 5 Average runtime (in seconds) for the model with binary or continuous decision variables yp,s, p∈Ps,s∈S Uniform Clustered Service design Binary Continuous Binary Continuous Instant 11.18 11.18 24.30 24.81 Fast 61.99 60.24 320.56 317.91 Same-day 37.41 38.27 68.01 66.60 A.1 Clustered demand pattern In this section we explain in more detail the clustered demand pattern. As shown in Fig.5, the city is divided into city centre, industrial area, and residential areas. Pickup and delivery customer locations are sampled as follows. Half of the pickup customer locations are generated uniformly over the city centre, the other half is generated uniformly over the industrial zone. This is motivated by shops and companies being located in these areas usually. As companies also might order goods or people might order parcels to their work place instead of their home, a fourth of the delivery customer locations is sampled uniformly within the industrial zone. Still, the majority of parcels is ordered to private households. Therefore the remaining four quarters of delivery customer locations are distributed uniformly in the residential areas. A.2 Runtime comparison for relaxed decision variables yp,s In this section we make a runtime comparison to evaluate the model (1-SP) with the decision variables yp,s∈{0,1}∀p∈Ps∀s∈Sagainst the model with yp,s∈[0,1] ∀p∈Ps∀s∈S. We create instances with uniform or clustered demand and 100 parcels. For each service design (instant, fast and same-day), we run the model on 100 different instances. Table 5shows the average runtimes of both versions in seconds. From Table 5we see that on uniform demand with instant service, both models run equally long on average. On uniform demand with same-day service and on clustered demand with fast service the model with binary decision variables yp,sis slightly faster. On the remaining instances, the model with continuous decision variables yp,s is solved within a shorter time. It is remarkable that instances with fast service require significant more time to be solved than the rest of the instances. Also, the runtime reduction on these instances is larger than the runtime growth on other instances. We hence conclude that relaxing the decision variables yp,sto be continuous is generally beneficial, although this should be checked for different instances. A.3 Implementation of the dynamic second stage evaluation Algorithm 1states the pseudo code for the dynamic evaluation of the second stage. In short, the algorithm re-solves the second stage each time a new order arrives. For this, the algorithm requires a first stage solution xand a set of parcel requests Pas 123 Consistent routing for local same-day delivery via micro-hubs 407 an input. To each parcel request, a corresponding release time, pickup, and delivery location is given. To initialise the algorithm, the parcel requests are sorted by their release time in ascending order. Moreover, an empty set of available parcels and of already checked parcels are created. Within the algorithm, they will help to keep track of which parcels are to be investigated and for which parcels a solution has already been determined. Every time a new parcel request pis placed, the algorithm adds this parcel to the list of available parcels. Then, the deterministic second stage model (2nd-SP)is solved where only the set of available parcels is considered. In (2nd-SP), the first stage decision variables x, i.e. the consistent tour of the vehicle, are fixed. Further, the decision variables of all parcels whose solution has already been determined in a previous iteration are fixed as well. This way, the solution of one more parcel is fixed in each iteration. In other words, only the decision variables concerning parcel pare to be determined by the model. Given the vehicle tour and the parcel flow of earlier orders, the model hence determines whether the new parcel can be transported with the given schedule and availabe capacities, or not. After a solution has been found, parcel pis added to the list of checked parcels and a new iteration starts. In each iteration k, the current objective value p∈Pkyk pspecifies the number of parcels that can be transported by the shared vehicle so far. After the last iteration, this is the total number of delivered parcels. Algorithm 1: Dynamic Evaluation of the Second Stage Input:x– consistent tour (first stage decision variables) P– set of parcels, each associated with a release time, pickup, and delivery location Initialisation: Psorted ←− list of all parcels p∈Psorted by their release time P0←− ∅ (list of available parcels) D0←− ∅ (list of checked parcels) k←− 1 for p∈Psorted do add p to list of available parcels: Pk←− Pk−1∪{p} solve (2nd-SP) for the set of available parcels Pkwhere vehicle tour and all checked parcels Dk−1are fixed: yk,zk←− arg max p∈Pkyk p|x,yk,zk∈Cs,yk p=yk−1 p,zk p=zk−1 p∀p∈Dk−1 add p to list of checked parcels: Dk←− Dk−1∪{p} k←− k+1 end Output:p∈Pkyk pis the total number of delivered parcels. References Angelelli E, Archetti C, Filippi C, Vindigni M (2017) The probabilistic orienteering problem. Comput Oper Res 81:269–281 Bernardo M, Pannek J (2018) Robust solution approach for the dynamic and stochastic vehicle routing problem. J Adv Transp 2018:1–11 123 408 C. Ackva, M. Ulmer Bertsimas DJ, Jaillet P, Odoni AR (1990) A priori optimization. Oper Res 38(6):1019–1033 Bundesverband Paket und Expresslogistik e.V. (BIEK) (2021) KE-CONSULT Kurte & Esser GbR: Möglichmacher in bewegten Zeiten, KEP-Studie 2021—Analyse des Marktes in Deutschland. https://www. biek.de/publikationen/studien.html. Accessed 25 Feb 2022 Burns T, Davis A, Harris T, Kuzmanovic A (2022) Beyond the distribution center. https://www.mckinsey. com/industries/retail/our-insights/beyond-the-distribution-center. Accessed 24 June 2022 Cameron I (2022) Metapack integrates with Homerr to offer sustainable deliveries for retailers. https://www. chargedretail.co.uk/2022/05/27/metapack-integrates-with-homerr-to-offer-sustainable-deliveries- for-retailers/. Accessed 24 June 2022 Campbell AM, Thomas BW (2008) Challenges and advances in a priori routing. In: The vehicle routing problem: latest advances and new challenges. Springer, pp 123–142 Crainic TG, Errico F, Rei W, Ricciardi N (2016) Modeling demand uncertainty in two-tier city logistics tactical planning. Transp Sci 50(2):559–578 Cuda R, Guastaroba G, Speranza MG (2015) A survey on two-echelon routing problems. Comput Oper Res 55:185–199 Dalmeijer K, Desaulniers G (2021) Addressing orientation symmetry in the time window assignment vehicle routing problem. INFORMS J Comput 33(2):495–510 Dalmeijer K, Spliet R (2018) A branch-and-cut algorithm for the time window assignment vehicle routing problem. Comput Oper Res 89:140–152 Datex (2021) 2021 update: e-commerce, last mile delivery and 3PLs. https://www.datexcorp.com/2021- update-e-commerce-last-mile-delivery-and-3pls/. Accessed 29 June 2022 Emadikhiav M, Bergman D, Day R (2020) Consistent routing and scheduling with simultaneous pickups and deliveries. Prod Oper Manag 29(8):1937–1955 Florio AM, Feillet D, Poggi M, Vidal T (2022) Vehicle routing with stochastic demands and partial reoptimization. Transp Sci 56(5):1393–1408 Groër C, Golden B, Wasil E (2009) The consistent vehicle routing problem. Manuf Serv Oper Manag 11(4):630–643 Gurobi Optimization LLC (2021) Gurobi optimizer reference manual. http://www.gurobi.com Hvattum LM, Løkketangen A, Laporte G (2006) Solving a dynamic and stochastic vehicle routing problem with a sample scenario hedging heuristic. Transp Sci 40(4):421–438 Jiang D, Li X (2021) Order fulfilment problem with time windows and synchronisation arising in the online retailing. Int J Prod Res 59(4):1187–1215 Kiezbote (2021) Berliner Kiezbote liefert Pakete zur Wunschzeit: Aus Forschungsprojekt wird ein Start-up. https://www.htw-berlin.de/einrichtungen/zentrale-referate/kommunikation/pressemitteilungen/ berliner-kiezbote-liefert-pakete-zur-wunschzeit-aus-forschungsprojekt-wird-ein-start-up/. Accessed 04 Nov 2022 Koç Ç, Laporte G, Tükenmez ˙ I (2020) A review of vehicle routing with simultaneous pickup and delivery. Comput Oper Res 122:104987 Kovacs AA, Golden BL, Hartl RF, Parragh SN (2014a) Vehicle routing problems in which consistency considerations are important: a survey. Networks 64(3):192–213 Kovacs AA, Parragh SN, Hartl RF (2014b) A template-based adaptive large neighborhood search for the consistent vehicle routing problem. Networks 63(1):60–81 Lagos F, Klapp MA, Toriello A (2019) Branch-and-price for routing with probabilistic customers. Research Report. Working Paper Lian K (2017) Service consistency in vehicle routing. PhD thesis. University of Arkansas Mancini S, Gansterer M, Hartl RF (2021) The collaborative consistent vehicle routing problem with workload balance. Eur J Oper Res 293(3):955–965 Metapack (2022) Ecommerce delivery benchmark report 2022. https://info.metapack.com/ ecommerce-delivery-benchmark-report-2022.html?utm_source=press&utm_medium=referral& utm_campaign=delivery+benchmark+2022. Accessed 29 June 2022 Nahata K (2022) Why retailers must simplify complex last-mile delivery. https://www.retailtouchpoints. com/topics/fulfillment-last-mile/why-retailers-must-simplify-complex-last-mile-delivery. Accessed 04 Nov 2022 Neumann-Saavedra BA, Crainic TG, Gendron B, Mattfeld DC, Römer M (2016) Service network design of bike sharing systems with resource constraints. In: Computational logistics: 7th international conference, ICCL 2016, Lisbon, Portugal, September 7–9, 2016, Proceedings 7 Springer (event), pp 352–366 123 Consistent routing for local same-day delivery via micro-hubs 409 Orenstein I, Raviv T (2022) Parcel delivery using the hyperconnected service network. Transp Res Part E Logist Transp Rev 161:102716 Salavati-Khoshghalb M, Gendreau M, Jabali O, Rei W (2019) An exact algorithm to solve the vehicle routing problem with stochastic demands under an optimal restocking policy. Eur J Oper Res 273(1):175–189 Sampaio A, Kinable J, Veelenturf LP, Van Woensel T (2019) A scenario-based approach for the vehicle routing problem with roaming delivery locations under stochastic travel times. In: Optimization online, pp 1–29 Sluijk N, Florio AM, Kinable J, Dellaert N, Van Woensel T (2022) Two-echelon vehicle routing problems: a literature review. Eur J Oper Res 304(3):865–886 Smilowitz K, Nowak M, Jiang T (2013) Workforce management in periodic delivery operations. Transp Sci 47(2):214–230 Song Y, Ulmer MW, Thomas BW, Wallace SW (2020) Building trust in home services-stochastic teamorienteering with consistency constraints. Transp Sci 54(3):823–838 Spliet R, Dabia S, Van Woensel T (2018) The time window assignment vehicle routing problem with time-dependent travel times. Transp Sci 52(2):261–276 Spliet R, Desaulniers G (2015) The discrete time window assignment vehicle routing problem. Eur J Oper Res 244(2):379–391 Spliet R, Gabor AF (2015) The time window assignment vehicle routing problem. Transp Sci 49(4):721–731 Subramanyam A, Gounaris CE (2018) A decomposition algorithm for the consistent traveling salesman problem with vehicle idling. Transp Sci 52(2):386–401 Subramanyam A, Wang A, Gounaris CE (2018) A scenario decomposition algorithm for strategic time window assignment vehicle routing problems. Transp Res Part B Methodol 117:296–317 Sungur I, Ren Y, Ordóñez F, Dessouky M, Zhong H (2010) A model and algorithm for the courier delivery problem with uncertainty. Transp Sci 44(2):193–205 Tarantilis CD, Stavropoulou F, Repoussis PP (2012) A template-based tabu search algorithm for the consistent vehicle routing problem. Expert Syst Appl 39(4):4233–4239 Ulmer MW, Streng S (2019) Same-day delivery with pickup stations and autonomous vehicles. Comput Oper Res 108:1–19 velove (2022) https://www.velove.se/. Accessed 05 May 2022 Visser T, Savelsbergh M (2019) Strategic time slot management: a priori routing for online grocery retailing. Research Report. Working Paper Wang K, Zhen L, Xia J, Baldacci R, Wang S (2021) Routing optimization with generalized consistency requirements. Transp Sci 56(1):223–244 Zhen L, Lv W, Wang K, Ma C, Xu Z (2020) Consistent vehicle routing problem with simultaneous distribution and collection. J Oper Res Soc 71(5):813–830 Publisher’s Note Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations. 123