Optimizing last-mile delivery: a dynamic compensation strategy for occasional drivers
Abstract
EconStor is a publication server for scholarly economic literature, provided as a non-commercial public service by the ZBW.
Full text
Schur, Rouven; Winheller, Kai Article — Published Version Optimizing last-mile delivery: a dynamic compensation strategy for occasional drivers OR Spectrum Suggested Citation: Schur, Rouven; Winheller, Kai (2024) : Optimizing last-mile delivery: a dynamic compensation strategy for occasional drivers, OR Spectrum, ISSN 1436-6304, Springer Berlin Heidelberg, Berlin/Heidelberg, Vol. 47, Iss. 4, pp. 1075-1132, https://doi.org/10.1007/s00291-024-00796-6 This Version is available at: https://hdl.handle.net/10419/333348 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/
Vol.:(0123456789) OR Spectrum (2025) 47:1075–1132 https://doi.org/10.1007/s00291-024-00796-6 ORIGINAL ARTICLE Optimizing last‑mile delivery: adynamic compensation strategy foroccasional drivers RouvenSchur1 · KaiWinheller1 Received: 19 February 2024 / Accepted: 28 October 2024 / Published online: 26 December 2024 © The Author(s) 2024 Abstract Amid the rapid growth of online retail, last-mile delivery faces significant challenges, including the cost-effective delivery of goods to all delivery locations. Our work contributes to this stream by applying dynamic pricing techniques to effectively model the possible involvement of the crowd in fulfilling delivery tasks. The use of occasional drivers (ODs) as a viable, cost-effective alternative to traditional dedicated drivers (DDs) prompts the necessity to focus on the inherent challenge posed by the uncertainty of ODs’ arrival times and willingness to perform deliveries. We introduce a dynamic programming framework that offers individualized bundles of a delivery task and compensation to ODs as they arrive. This model, akin to a reversed form of dynamic pricing, accounts for ODs’ decision-making by treating their acceptance thresholds as a random variable. Therefore, our model addresses the dynamic and stochastic nature of OD availability and decision-making. We analytically solve the stage-wise optimization problem, outline inherent challenges such as the curses of dimensionality, and present structural properties. Tailored to meet these challenges, our approximation methods aim to accurately determine avoided costs, which are a key factor in calculating optimal compensation. Our simulation study reveals that the savings generated by involving ODs in deliveries can be significantly increased through our individualized dynamic compensation policy. This approach not only excels in generating savings for the firm but also provides a utility surplus for ODs. Additionally, we demonstrate the applicability of our approach to scenarios with time windows and illustrate the trade-off that arises from time window partitioning. Keywords Dynamic pricing· Last-mile delivery· Occasional drivers· Approximate dynamic programming R. Schur and K. Winheller have contributed equally to this work. Extended author information available on the last page of the article
1076 R.Schur, K.Winheller 1 Introduction Fueled by the rapid growth of online retail and brick-and-mortar stores expanding into online sales, last-mile delivery has become increasingly important in the logistics sector. This trend has further accentuated the cost-intensive nature of urban transportation operations, necessitating innovative approaches to mitigate these challenges. One of these innovative approaches is the concept of using occasional drivers (ODs). ODs are (in-store) customers or individuals willing to divert their planned route to deliver online orders for monetary compensation. Thereby, they present a cost-effective alternative to dedicated drivers (DDs), who are employed or contracted through a third-party logistics provider. This OD approach, leveraging existing store traffic, offers not only economic benefits (Archetti etal. 2016; Dayarian and Savelsbergh 2020) but also aids in reducing pollution and urban traffic, while enhancing community ties (Buldeo Rai etal. 2018; Hutter and Neumann 2023). However, the unpredictability of ODs, influenced by factors like the frequency of store visits and their fluctuating willingness to undertake deliveries on that day, poses a significant challenge. This uncertainty in OD availability contrasts sharply with the reliability of DDs, which offer a more predictable delivery solution. A key factor influencing ODs’ willingness to participate is compensation, which effectively offsets the additional effort and time ODs invest in fulfilling delivery tasks (Archetti etal. 2016; Qi etal. 2018). While current implementations of similar concepts on platforms such as Walmart’s Spark or Shopopop have demonstrated practical feasibility, there remains a considerable gap in bringing out the intended potential of ODs. Specifically, current research has mainly focused on deterministic models with fixed acceptance criteria for ODs (Boysen etal. 2021), with little room for customized offers, while stochastic models typically ignore the dynamic nature of ODs’ arrivals or the role of compensation in decision-making (Savelsbergh and Ulmer 2022). Our research addresses these gaps by proposing a dynamic model that matches sequentially and stochastically arriving ODs with delivery tasks to minimize the expected costs (or equivalently to maximize expected savings) through additionally employing ODs along with DDs. Each OD is offered a customized bundle, consisting of a delivery task and compensation. This customized offer is influenced by the ODs’ destination, the remaining time, and the pool of potential future ODs. The acceptance threshold of the OD is considered a random variable, reflecting the unpredictable nature of their decision-making. Unassigned deliveries at the dispatch time are fulfilled by DDs. Since our focus is on investigating the cost-saving potential of engaging ODs for deliveries, we assume that DD capacity is sufficient to serve all delivery locations. However, our framework can also be applied in scenarios where DD capacity is insufficient, by incorporating an appropriate penalty term when evaluating DD delivery costs (refer to Sect.3.1). This approach, akin to a reversed form of dynamic pricing, is detailed in Fig.1 and offers a more realistic and effective solution for employing independent individuals in last-mile delivery scenarios.
1077 Optimizing last‑mile delivery: adynamic compensation strategy… 1.1 Problem description In the following, we describe our scenario in greater detail, beginning with the perspectives of online customers, ODs, and the firm. Furthermore, we point out that our problem characteristics are in line with current crowdshipping literature (refer also to Table1 in Sect.2.4). • The online customer’s perspective: Customers can place delivery orders at any time, but there is a communicated cutoff time that must be met for orders to be served in the upcoming delivery horizon. Orders placed after the cutoff time will be served at the next or a later delivery horizon. For example, an order placed before the store opens will be fulfilled on the same business day, whereas an order placed after the store opens will be fulfilled on the next business day. • The OD’s perspective: ODs are customers who regularly shop at the store and have, through a one-time registration, expressed their willingness to occasionally make deliveries. During registration, they also indicated their usual destinations, such as their home or workplace. Upon entering the store, each OD receives a customized offer, consisting of a specific delivery location along with the corresponding compensation. They can accept or decline this offer. On acceptance, ODs collect the order and compensation at the checkout counter and deliver the package en route to their predetermined destination. • The firm’s perspective: At the cutoff time, the firm knows all the orders that need to be handled in the upcoming delivery horizon (e.g., the business day). There is a latest dispatch time by which orders must leave the store to meet the promised delivery times. If the firm does not have its own fleet of DDs, the dispatch time is typically agreed upon with a third-party service provider (e.g., DHL, UPS). The firm is notified upon the arrival of registered ODs and informed of their usual destinations. This information allows the firm to make specific offers of compensation and delivery locations. Orders not handled by ODs are handed over to DDs at dispatch time. DDs are capable and willing to fulfill any assigned orders in a timely manner. Fig. 1 Dynamic programming process. This illustration depicts the sequential decision-making process as ODs arrive over time. It focuses on the current state, emphasizing three critical elements: the current OD, identified by their destination (represented by an arrow), potential future ODs, marked by their respective destinations (represented by circles), and open delivery tasks, characterized by their delivery locations (represented by triangles)
1078 R.Schur, K.Winheller Table 1 Summary of problem characteristics and model capabilities. Authors (Year) Problem characteristics Model capabilities Time windows Dispatch time for DD delivery Known OD destinations Known set of customer orders Single delivery per OD Anticipation of uncertain future arrival Anticipation of uncertain OD acceptance Compensation decision to influence uncertain OD behaviour Dynamic decision making Archetti etal. (2016) – X X X Kafle etal. (2017) X X X Gdowska etal. (2018) X X X X X Allahviranloo and Baghestani (2019) X – X X X Arslan etal. (2019) X X X X Dahle etal. (2019) X – X X X Mofidi and Pazour (2019) X X Dayarian and Savelsbergh (2020) X X X X Archetti etal. (2021) X X X X Feng etal. (2021) – X X Horner etal. (2021) – X X Le etal. (2021) X – X X X Ausseil etal. (2022) X – X X X X
1079 Optimizing last‑mile delivery: adynamic compensation strategy… Table 1 (continued) Authors (Year) Problem characteristics Model capabilities Time windows Dispatch time for DD delivery Known OD destinations Known set of customer orders Single delivery per OD Anticipation of uncertain future arrival Anticipation of uncertain OD acceptance Compensation decision to influence uncertain OD behaviour Dynamic decision making Boysen etal. (2022) – X X Mancini and Gansterer (2022) X X Mousavi etal. (2022) X X X Santani etal. (2022) X X X Silva and Pedroso (2022) X X X X X Torres etal. (2022a) X X X X Torres etal. (2022b) X X X X Barbosa etal. (2023) X X X X X Hou etal. (2023) X X X X X X Silva etal. (2023a) X X X X X Silva etal. (2023b) X X X X This work X X X X X X X X X The category “dispatch time for DD deliveries” is marked (X) for all studies that have a dedicated point in time in which all remaining tasks are outsourced to a fleet of DDs. Studies that do not incorporate DDs into their model (pure crowdshipping models) or do not specify the delivery time are excluded (-) from this category
1080 R.Schur, K.Winheller A cutoff time is widely used in practice (e.g., Amazon with next-day delivery) as well as in literature (see, e.g., Archetti etal. 2016; Boysen etal. 2022; Mousavi etal. 2022). The dispatch time can either be chosen by the firm as the time it must deploy its vehicle fleet, or it can be an agreed-upon time when a contracted third-party service provider picks up the orders from the store. Since our focus is on the optimal engagement of ODs, we will concentrate on the latter case, as it simplifies the evaluation of the final states in our dynamic programming formulation (see, Sect.3.2). However, note that all our results (particularly, our structural properties and solution methods) are still applicable in a scenario where the firm uses its own vehicle fleet and solves a vehicle routing problem for evaluating the final states. The period between cutoff and dispatch time can be used to engage any OD who enters the store during that timeframe. Clearly, crowdshipping can only have a measurable impact if this period is sufficiently long, where the required duration depends on store traffic and the ratio of ODs within this traffic. Exploiting this period for ODs naturally results in a framework where OD fulfillment precedes DD fulfillment. This approach ensures that all orders will be delivered within the promised delivery horizon, as no order will be left behind by DDs in the hope of an adequate OD arriving after the dispatch time. Consequently, this sequence of engaging ODs and having DDs handle the remaining deliveries afterward is widely observed in crowdshipping literature (see, e.g., Gdowska etal. 2018; Torres etal. 2022a; Silva etal. 2023b). As is common in a crowdshipping context (see, e.g., Archetti etal. 2016; Ausseil etal. 2022; Barbosa etal. 2023), we focus on orders manageable by a single person. This ensures that the orders are of reasonable size and weight, eliminating the need to track these attributes. Thus, the single characterizing attribute of an order is given by its delivery location. The firm makes a single offer consisting of one delivery location and compensation to each arriving OD, which minimizes communication between the OD and the firm and reduces the need to consider ODs’ capacity capabilities. This approach recognizes that ODs are individuals who do not primarily seek to earn a living through deliveries but are willing to spend a small part of their free time participating in crowdshipping. Therefore, it is crucial to reduce any inconvenience for them. Given this design choice, we do not consider the vehicle capacities of ODs to be a limiting factor. However, if ODs are unable to take on delivery for any reason (such as a fully-loaded vehicle, an unusual destination, or time constraints) they can always decline the offer. This flexibility is represented in the OD choice model by a random variable, accounting for the volatility in ODs’ willingness to participate. While our framework is most naturally suited for (same-day) unattended home delivery, which has got a lot of attention from recent crowdshipping research (see, e.g., Boysen et al. 2022; Mousavi et al. 2022; Silva et al. 2023b), it can also be adapted for scenarios with attended home delivery by shortening the delivery horizon to just a few hours instead of an entire business day. Note that the effectiveness of engaging ODs diminishes as the delivery horizon decreases. This is because ODs begin deliveries shortly after they arrive at the store, leaving a limited timeframe for the firm to identify and engage suitable ODs for a time-restricted delivery. Furthermore, smaller time windows usually necessitate that DDs cover multiple delivery
1081 Optimizing last‑mile delivery: adynamic compensation strategy… horizons within a single tour. This often means that orders must commence their journey before the firm has the opportunity to offer them to an OD. Consequently, ODs are less beneficial in scenarios with very small delivery windows. Nevertheless, medium-sized delivery windows, such as a few hours or half of the business day, align well with our approach when applied consecutively (see Sect.6). This consecutive approach to dealing with time windows is comparable to the approaches covered by Arslan etal. (2019) or Silva etal. (2023a). In our setting, ODs are customers who shop in the store and have previously expressed a general interest in occasionally taking on delivery, along with providing their usual destinations after shopping. Consequently, the firm has a pool of ODs and their respective destinations, a scenario that is often observed in the literature (see, e.g., Feng etal. 2021; Le etal. 2021; Mancini and Gansterer 2022). Through individualized offers, consisting of a specific delivery location and compensation, the firm can influence ODs’ willingness to participate in crowdshipping. By selecting the delivery location to offer, the firm determines the required detour for the OD. Simultaneously, it offers individual compensation to offset the inconveniences, incurred by fulfilling the delivery task. This assumption is in line with the literature, where higher compensations typically increase the willingness of ODs to accept these offers (see, e.g., Cachon etal. 2017; Taylor 2018; Yildiz and Savelsbergh 2019). 1.2 Contribution andoutline ofthepaper Our goal is to determine the optimal strategy for engaging ODs in making deliveries while modeling a realistic interaction between the firm and ODs. This approach contrasts sharply with current research, which often relies on simplifying assumptions such as deterministic or exogenous OD behavior. Additionally, many potential opportunities are overlooked in existing studies. Without incorporating a dynamic decision-making framework, firms lose the ability to swiftly respond to new information revealed through the arrivals and decisions of ODs. Moreover, by ignoring the impact of the firm’s decisions on OD decision-making, firms miss a crucial lever for controlling the entire decision process. To the best of our knowledge, we are the first to develop a dynamic optimization framework where ODs arrive dynamically and stochastically over time, prompting the firm to decide on the optimal offer, consisting of a specific delivery location and individual compensation. This compensation depends on the specific OD, the current state of the system, and the offered delivery location. Furthermore, OD behavior is adequately modeled, being influenced by the delivery location offered and the compensation provided. This paper makes several significant contributions to the field of logistics, utilizing dynamic pricing methodologies: 1. Introduction of the dynamic compensation problem for occasional drivers: We propose a novel framework that accounts for the sequential arrival of ODs
1082 R.Schur, K.Winheller and incorporates uncertainties related to their arrival and acceptance decisions in Sect.3. 2. Analytical solution to the stage-wise optimization problem: Utilizing a Bellman equation, we solve the stage-wise optimization problem. Additionally, Sect.4 discusses the structural properties and challenges to finding an optimal policy, laying the foundation to develop appropriate approximation methods. 3. Tailored approximation methods: In Sect.5, we introduce specialized adaptations of well-known approximation methods, specifically designed to align with the inherent structure of our problem. These include a parametric value function approximation and a fluid approximation, each designed to adapt to the dynamic nature of OD arrivals and reflect structural properties. 4. Comprehensive simulation study: In a detailed simulation study presented in Sect.6, we apply our algorithms to demonstrate the advantages of acknowledging the uncertainties inherent in employing ODs. This study not only validates our approach but also provides valuable insights into the benefits of dynamic compensation strategies across various urban configurations and OD arrival patterns. Additionally, we analyze the effect of time windows in our crowdshipping setting. The paper is structured as follows: We begin with a literature review in Sect.2. This is followed by a formal problem description in Sect.3, and an in-depth analysis of the problem in Sect.4. Our proposed solution approaches are detailed in Sect.5, and the results of our simulation study are presented in Sect.6. We conclude with a discussion of managerial insights and a summary of our key findings in Sect.7. 2 Literature review In the preceding discussion, we conceptualized an OD as an individual who may visit the store (which acts as the depot) and, if conditions align with their schedule, may undertake a delivery task. An important element in our analysis is the uncertainty associated with the arrival of ODs at the store and their decision to accept a task. We posit that compensations significantly influence ODs’ acceptance decisions. Based on this definition, we structure our literature review as follows. Initially, in Sect.2.1, we provide a concise overview of existing literature focused on a deterministic framework, which does not explicitly anticipate uncertainties regarding ODs’ arrival and task acceptance. Such studies have little in common with our research focus. Moving forward to Sect. 2.2, our attention turns to scenarios where the arrival and/or acceptance of ODs are stochastic. This section examines models that accommodate the uncertain behaviors of ODs, regarding their arrival at the depot or their decision to accept a delivery task. We specifically investigate studies suggesting that these behaviors can be effectively influenced or altered through the compensation strategies. This section of our review aligns more closely with our study. In Sect.2.3, we briefly discuss related studies that share similarities with our work in terms of model formulation and solution methods. Finally, in Sect.2.4, we conclude our review with a summary and provide an overview of how our problem
1089 Optimizing last‑mile delivery: adynamic compensation strategy… consist of paid compensations to ODs and costs of delivery by DDs. We will formulate this optimization problem using the Bellman equation in Sect.3.3, following the introduction of crucial components of our dynamic programming formulation in Sect.3.2. 3.2 Formulation asadynamic program The remaining problem description will be structured by the essential components of a dynamic program in line with Powell (2011). 3.2.1 States The progression through each period involves three primary types of states: prearrival ( SA t ), pre-decision ( SX t ), and post-decision state ( SP t ). Each state structure varies, encapsulating information specific to its context. A visual representation of the dynamic program is illustrated in Fig.2 as a decision tree, where circles represent random nodes, and squares denote decision nodes. 1. Pre-arrival states SA t contain information about potential OD arrivals, denoted as Ot , and open delivery tasks, denoted as Ct . For mally, SA t =(O t ,C t) . The pre-arrival state transitions into the pre-decision state with the arrival of an OD in period t. If no OD arrives during the pre-arrival state in period t, the subsequent states are skipped, and the next state becomes the pre-arrival state of period t+1 . Fig. 2 Tree representation of the dynamic program. Circles represent states in which the transition is determined by a random process, while squares represent states in which the subsequent state is determined by the firm’s decision
1090 R.Schur, K.Winheller 2. Pre-decision states SX t include all information from the preceding pre-arrival state and the specific OD arrival, denoted as ot , in period t. In mathematical terms, SX t =(O t ,C t ,o t) . With the knowledge of OD ot arriving, the firm must decide on the offered bundle (c,r), comprising a delivery task c∈Ct and a compensation r (refer to 3.2.3). 3. Post-decision states SP t encompass all information from the preceding pre-decision state and the bundle (c,r) offered to OD ot , i.e., SP t =(O t ,C t ,o t ,c,r ) . After OD ot makes a decision, the state transitions into the pre-arrival state of the next period by updating Ot and Ct accordingly, based on the OD’s decision. The transition from states over periods t is terminated when period T+1 is reached. For a comprehensive description of the transition function see 3.2.2. 3.2.2 Transitions We move through states within a period and from one period t to the next, integrating new information as the scenario evolves. Transitioning from pre-arrival to pre-decision state involves a stochastic process, where additional information is based on the stochastic arrival of up to one OD ot∈Ot . The transition from pre-decision to post-decision state is deterministic and dependent on the firm’s decision. Moving from post-decision to pre-arrival state in the subsequent period follows a stochastic process, reflecting the OD’s unknown decision regarding the firm’s offer. Specifically, OD ot is excluded from Ot , assuming departed ODs don’t return within the considered horizon. This mirrors their behavior as nonemployed individuals who complete their shopping in one visit and return only when supplies are depleted. Furthermore, based on OD ot accepting or rejecting the offered task c, c is either removed from or retained in Ct . In summary, the transition from one period to another can be characterized by: 3.2.3 The firm’s decisions The decision space, denoted as X=(XC,XR) , represents the entire collection of all possible decisions and depends on the current pre-decision state SX t . Consequently, we write X (S X t )=(X C (S X t ),X R (S X t)) . A decision is represented as ( c,r)∈X(S X t) , where c denotes a delivery location and r indicates the compensation paid to the OD for fulfilling this delivery. In our framework, we assume that the firm offers at most one delivery location at a time, eliminating the need to (1) S A t+1= ⎧ ⎪ ⎨ ⎪ ⎩ (Ot⧵{ot},Ct⧵{ct}) if OD otarrives and serves delivery location c t (Ot⧵{ot},Ct)if OD otarrives and rejects the offer (Ot,Ct)if no OD arrives in t
1091 Optimizing last‑mile delivery: adynamic compensation strategy… consider trunk space or weight limitations. This assumption emphasizes that ODs are viewed as opportunistic individuals rather than employed personnel, reflecting their preference for minimal commitment. Additionally, we do not impose further limitations on offers, making XC (S X t) equivalent to the most general case, Ct . XR (S X t) can be modeled as either a discrete set or a continuous range of possible compensations. In our work, we allow for the most general case, where XR (S X t )=ℝ + . 3.2.4 The OD’s decision Each OD possesses a unique indifference compensation (IC), which marks the minimum compensation that leads to accepting a delivery task to a specified delivery location. The prevailing trend in existing literature often assumes or implicitly suggests, that the ICs of ODs are known to the firm. To deviate from this trend, a crucial step is to establish a suitable representation of the IC. In our study, we propose that the IC is influenced by two factors: one encompasses observable information (such as detour, traffic, parking availability at the delivery location, weather, etc.), expressed as aoct indicating the monetary compensation required for known inconveniences; the other involves unobservable information (like the OD’s time constraints and mood on a specific day), represented by the random variable 𝜔 , denoting the additional (unknown) amount required to persuade the OD to accept today’s offer. Formally, it holds that We assume that 𝜔 follows a continuous distribution with positive support on [0, boct] , characterized by its cumulative distribution function denoted as F and its probability density function as f. While the choice of distribution is flexible and may vary across ODs, delivery locations, and periods (although we don’t explicitly specify this by using foct ), we restrict ourselves to a specific class of distributions characterized by the condition that f/F is decreasing.1 This condition ensures that our decision problem has a unique solution (refer to Proposition 1). Notably, every distribution with a decreasing f satisfies this criterion. Furthermore, this condition is akin to requiring that the reflected distribution, given by f(x)=f(−x) over the support [−boct,0] , exhibits an increasing failure rate h(x)=f(x)∕(1−F(x)) . Adopting the assumption of an increasing failure rate aligns with common practices in dynamic pricing literature. Random variables exhibiting increasing failure rates have a growing generalized failure rate, as discussed in Lariviere (2006). This choice is consistent with one of the three standard assumptions outlined in Ziya etal. (2004). Furthermore, it is compatible with numerous probability distributions, including but not limited to the uniform, triangular, normal, exponential, Weibull, Gumbel, and gamma distributions, and their truncated variants (some of them with restrictions regarding parameter choice) as documented in Banciu and Mirchandani (2) ICoct =aoct +𝜔. 1 We use decreasing/increasing and lower/higher in a weak sense.
1092 R.Schur, K.Winheller (2013). Each of these distributions can serve as f , further extending the possibilities for the selection of f. 3.3 The Bellman equation The objective is to minimize the total expected costs, denoted as V1(O1,C1) . Costs are incurred by fulfilling all delivery tasks c∈C1=C , either by employing DDs or leveraging the potential arrivals of ODs o∈O1=O . Consequently, they consist of all compensations paid to ODs during the planning horizon t=1, ..., T and to DDs at the dispatch time t=T+1 for all remaining delivery tasks CT+1 . Given the dynamic nature of this decision problem, we formulate it through a Bellman equation. The expected costs in a pre-arrival state SA t =( Ot , Ct) with remaining ODs Ot and remaining delivery tasks Ct can be represented as follows: with the boundary condition V T +1 (S A T+1 )=Θ(CT +1) . The expectation Eo covers all potential arrivals of ODs o∈Ot as well as the event of no arrival. In the latter case, the firm has no decision to make and faces expected future costs of Vt+1(Ot,Ct) . To minimize expected costs, our approach involves a unified decision-making process following the arrival of OD o. This entails the dual determination of selecting the delivery task c presented to OD o and simultaneously deciding on the compensation r offered for completing this task. The computation of expected costs for any given combination of o, c, and r considers two distinct outcomes: the OD’s acceptance of the proposed bundle, consisting of the delivery task and compensation, or their rejection. Acceptance incurs immediate costs r and future expected costs Vt+1(Ot⧵{o},Ct⧵{c}) for delivering the remaining tasks contained in Ct⧵{c} , with potential assistance from the remaining ODs given in Ot⧵{o} . Conversely, rejection has no immediate costs but leads to future expected costs Vt+1(Ot⧵{o},Ct) for fulfilling all deliveries in Ct with potential ODs from Ot⧵{o} . Notably, OD o accepts the offered bundle if and only if her indifference compensation ICoct =aoct +𝜔 is below the offered compensation r. By offering a bundle (c,r) to OD o, the firm hopes to reduce expected costs. Consequently, the firm avoids offers with r > Vt+1(Ot⧵{o},Ct)−Vt+1(Ot⧵{o},Ct⧵{c}) . We define as avoided costs, representing the difference between the expected costs of the next period’s pre-arrival states with and without the offered delivery location c. Furthermore, based on avoided costs, we define expected savings from offering the bundle (c,r) to OD o as: (3) V t (O t ,C t )=E o [min (c,r)∈X(Ot,Ct,o) {F(r−a oct ) ⋅ (r+V t+1 (O t ⧵{o},C t ⧵{c})) +(1−F(r−aoct)) ⋅ Vt+1( O t⧵{o}, C t)}] (4) ΔVt(Ot,Ct,o,c)=Vt+1(Ot⧵{o},Ct)−Vt+1(Ot⧵{o},Ct⧵{c}) (5) Savt(Ot,Ct,o,c,r)=F(r−aoct) ⋅ (ΔVt(Ot,Ct,o,c)−r).
1093 Optimizing last‑mile delivery: adynamic compensation strategy… With expected savings, we formulate an equivalent decision problem to the one integrated in (3). The following decision problem highlights the importance of avoided costs in our decision-making process and will be a cornerstone for our analysis of the problem and the creation of solution methods. It holds that Equation (6) demonstrates that maximizing expected savings is equivalent to minimizing expected costs, as Vt+1(Ot⧵{o},Ct) is independent of the decisions. In the remainder of this work, we focus on finding the optimal bundle (c(ot),r(ot)) for OD ot that maximizes expected savings in a given pre-decision state SX t =( Ot , Ct ,o t) : Observing the decision problem posed by equation (7), we encounter two crucial questions: First, does a unique optimal solution exist for every state, and can we effectively determine it? Second, if we can identify the optimal solution, is this sufficient to efficiently minimize the total expected costs V1(O1,C1) throughout the entire planning horizon? The first question is addressed in Sect.4, where we establish the uniqueness of the optimal solution and provide a sufficient optimality condition for any state. However, the second question demands more nuanced consideration: By solving the decision problem for each pre-decision state SP t =( Ot , Ct ,o t) in period t, we can compute the expected costs associated with every pre-arrival state SA t =( Ot , Ct) in the same period (refer to equations (3) and (6)). This process, in turn, yields the avoided costs ΔVt−1(Ot−1,Ct−1,ot−1,c) for each pre-decision state SP t−1 =( Ot−1 , Ct−1 ,o t−1) . By iteratively applying this methodology, we aim to minimize the total expected costs V1(O1,C1) . However, the sheer volume of potential pre-arrival and pre-decision states over the entire planning horizon grows exponentially, rendering a conventional roll-back procedure practically infeasible, even for relatively modest instances. Indeed, this dynamic problem is afflicted by the curses of dimensionality (refer to Powell 2011). Without constraining the number of states through rules, the cardinality of | S A t| becomes 2C+O in each period t. This prompts the need for a method that provides an approximation of the value function Vt(Ot,Ct) or the avoided costs ΔVt(Ot,Ct,o,c) . We address this issue in Sect.5. (6) min (c,r)∈X(Ot,Ct,o) {F(r−a oct ) ⋅ (r+V t+1 (O t ⧵{o},C t ⧵{c})) +(1−F(r−aoct)) ⋅Vt+1(Ot⧵{o},Ct)} =min(c,r)∈X(Ot,Ct,o){Vt+1(Ot⧵{o},Ct)−F(r−aoct)⋅(ΔVt(Ot,Ct,o,c)−r )) =Vt+1(Ot⧵{o},Ct)−max(c,r)∈X(O t ,C t ,o){Savt(Ot,Ct,o,c,r)} (7) max(c,r)∈ X ( O t, C t,ot){Savt(Ot,Ct,ot,c,r)}
1094 R.Schur, K.Winheller 4 Optimal solution andstructural properties In the first part of this section, we establish the existence of a unique solution to our decision problem outlined in equation (7). Additionally, we derive the optimal solution, showcasing its closed-form expression in the event of a uniformly distributed 𝜔 . Moving on to the second part of this section, we present an analysis of structural properties. We aim to glean insights into the model’s inherent characteristics, improving our capability to adequately approximate the value function or avoided costs in Sect.5. 4.1 Optimal state‑dependent solution In this section, we operate within an arbitrary pre-decision state SX t =(O t ,C t ,o ) , aiming to identify the optimal offer bundle ( c ( o ), r ( o )) ∈ X(Ot,Ct, o ) that maximizes (7). Our exploration begins by focusing on a fixed delivery task c∈Ct , and subsequently determining the optimal compensation r based on the interplay between OD o and the chosen delivery task c. Proposition 1 In a pre-decision state SX t =( Ot , Ct ,o ) , with a given c∈Ct , there is a unique r∈[aoct,boct +aoct] that maximizes Savt(Ot,Ct,ot,c,r) . This r either fulfills r + F(r−a oct ) f(r−aoct) =ΔVt(Ot,Ct,o,c ) or is on the bounds of [aoct,boct +aoct] . Proof Since f has positive support on [0, boct] , F(r−aoct) establishes a bijective function for r∈[aoct,boct +aoct] . Consequently, we can introduce 𝜃=F(r−aoct) as an alternative decision variable, where uniqueness carries over between the optimal r and the optimal 𝜃 . Utilizing 𝜃 offers the advantage that the second derivative is independent of Δ V t(Ot,Ct, o , c ) , allowing us to generally prove the concavity of the savings function in 𝜃 . With equation (5) and r( 𝜃 )= F −1( 𝜃 )+ a oct , we can formulate the first derivative of the savings function: The second derivative is expressed as: Given that r(𝜃) is increasing with 𝜃 and F(r−a oct ) f(r−a oct ) is increasing with r (as indicated in Sect.3.2.4), the second derivative is negative. Consequently, the savings function is (strictly) concave in 𝜃 . This leads to the existence of a unique 𝜃∈[0, 1] that maximizes the savings function for a given c. This uniqueness also extends to r∈[aoct,boct +aoct] . ◻ (8) d d 𝜃Savt(Ot,Ct,o,c,r(𝜃)) = (ΔVt(Ot,Ct,o,c)−F−1(𝜃)−aoct)− 𝜃 f(F−1(𝜃 )) = (ΔVt(Ot,Ct,o,c)−r(𝜃)) − F(r(𝜃)−aoct) f(r(𝜃)−aoct) . (9) d2 d 𝜃2Savt(Ot,Ct,o,c,r(𝜃)) = − d d𝜃r(𝜃) ( 1+d dr F(r−aoct) f(r−a oct ) | r=r(𝜃) ).
1095 Optimizing last‑mile delivery: adynamic compensation strategy… Remark 1 With a uniformly distributed 𝜔 , i.e., 𝜔∼U[0,boct ] , the optimal compensation r for a given pre-decision state SX t =( Ot , Ct ,o ) and a given delivery location c∈Ct can be derived by the following closed-form expression: Knowing the optimal compensation for a specific delivery location offers the advantage of evaluating various combinations of delivery locations and their corresponding optimal compensations to identify the most favorable combination. However, the computational effort increases with the number of remaining delivery tasks, making it more challenging to find the best delivery location. Fortunately, we can introduce a criterion to simplify this process. To do so, we first need two lemmas to prepare ourselves for demonstrating that this criterion indeed identifies the optimal delivery location. Lemma 1 In a pre-decision state SX t =( Ot , Ct ,o ) , with c,c∈Ct and corresponding optimal compensations r,r , respectively, the following implication holds: Proof Following a similar approach as in the proof of Proposition 1, we transition to alternative decision variables 𝜃=F(r−aoct) and 𝜃=F( r−aoct ) . It is noteworthy that 𝜃 and 𝜃 are optimal solutions for their respective savings functions. Utilizing equation (8) and the optimality of 𝜃 , we derive that: This implies that 𝜃 is greater than or equal to the optimal solution for the savings function with c , confir ming 𝜃≥ 𝜃 . Consequently, F(r−aoct) ≥ F( r−aoct) . ◻ Lemma 1 indicates that our optimal solution is selected in a manner where delivery locations exhibiting a larger difference between avoided costs and known inconveniences are paired with an optimal compensation that yields a higher probability of acceptance from the OD. The subsequent Lemma 2 conveys a related concept, emphasizing a higher realized saving rather than a higher probability. Lemma 2 In a pre-decision state SX t =(O t ,C t ,o ) , with c, c∈Ct and corresponding optimal compensations r,r , respectively, the following implication holds: (10) r = ⎧ ⎪ ⎨ ⎪ ⎩ aoct if ΔVt(Ot,Ct,o,c)≤aoct ΔVt(Ot,Ct,o,c)+aoct 2if aoct <ΔVt(Ot,Ct,o,c)<2boct +a oct b oct +a oct if ΔV t (O t ,C t ,o,c)≥2b oct +a oct (11) ΔVt(Ot,Ct,o,c)−aoct ≥ΔVt(Ot,Ct,o,c)−aoct ⟹ F(r−aoct)≥F(r−aoct) (12) 0 = (ΔVt(Ot,Ct,o,c)−aoct −F−1(𝜃)) − 𝜃 f(F−1(𝜃)) ≥(ΔVt(Ot,Ct,o,c)−aoct −F−1(𝜃)) − 𝜃 f(F −1 (𝜃)).
1096 R.Schur, K.Winheller Proof We set r=r+ΔVt(Ot,Ct,o, c)−ΔVt(Ot,Ct,o,c) and check whether this compensation is below or above the optimal compensation r . Utilizing Proposition 1, we observe: The inequality arises from ΔVt(Ot,Ct,o,c)−ΔVt(Ot,Ct,o,c)−aoct ≤−aoct and the observation that f(x)/F(x) is decreasing with x (as discussed in Sect.3.2.4). The final equality is a consequence of the optimality of r for c. This implies that r is greater than or equal to r . Consequently, r≤r=r+ΔVt(Ot,Ct,o,c)−ΔVt(Ot,Ct,o,c) , thus affirming the assertion of Lemma 2. ◻ Lemma 1 and Lemma 2 together carry a significant implication: A delivery location with a higher difference between avoided costs and known inconvenience results in an optimal compensation providing a higher probability of acceptance from the OD and greater realized savings in case of acceptance. This directly leads to the following proposition. Proposition 2 In a pre-decision state SX t =( Ot , Ct ,o ) , c(o)=argmaxc∈ C t{ΔVt(Ot,Ct,o,c)−aoct} is the optimal delivery location to offer to OD o. Proof The proof immediately follows from Lemmas 1 and 2, in conjunction with the definition of the savings function (refer to equation (5)). By definition, ΔVt(Ot,Ct,o,c(o)) − aoc(o)t≥ΔVt(Ot,Ct,o,c)−aoct for any c∈Ct . Moreover, according to Proposition 1, let r and r be the optimal compensation for c(o) and c , respectively. Then, ◻ Proposition 2 provides a simple criterion for determining the optimal delivery location. Given that Ct is discrete, aoct is a parameter, and ΔVt(Ot,Ct,o,c) is derived from the expected costs in the subsequent period t+1 through the (13) ΔV t (O t ,C t ,o,c)−a oct ≥ΔV t (O t ,C t ,o,c)−a oct ⟹ΔV t (O t ,C t ,o,c)−r≥ΔV t (O t ,C t ,o,c)− r (14) Δ Vt(Ot,Ct,o,c)−r− F(r−a oct ) f(r−aoct) =ΔVt(Ot,Ct,o,c)−r−F(r+ΔVt(Ot,Ct,o,c)−ΔVt(Ot,Ct,o,c)−aoct ) f(r+ΔVt(Ot,Ct,o,c)−ΔVt(Ot,Ct,o,c)−aoct) ≥ΔVt(Ot,Ct,o,c)−r−F(r−aoct) f(r−aoct) =0. (15) Sav t (O t ,C t ,o,c(o),r)=F(r−a oc(o)t ) ⋅ (ΔV t (O t ,C t ,o,c(o)) − r) ≥ F( r−aoct) ⋅ (ΔVt( O t, C t,o, c)− r)=Savt( O t, C t,o, c, r).
1097 Optimizing last‑mile delivery: adynamic compensation strategy… earlier step of a roll-back procedure, identifying the maximizer becomes a straightforward task. Following the identification of the optimal delivery location, the corresponding optimal compensation can be obtained using Proposition 1. These propositions collectively provide an immediate solution to determining the optimal offer bundle (c(o),r(o)) in a given pre-decision state SX t =( Ot , Ct ,o ) . The primary challenge lies in the computation of each ΔVt(Ot,Ct,o,c) , considering these avoided costs depend on Vt+1(Ot+1,Ct+1) for every possible subsequent pre-arrival state. The number of potential states grows exponentially with C and O, rendering the calculation of each instance beforehand a daunting task. Hence, there arises a necessity to approximate the value function or the avoided costs in an efficient manner. To minimize structural or systematic errors, our goal is to devise an approximation mechanism that faithfully captures the inherent structure of the value function and the avoided costs in Sect. 5. Consequently, we commence with the identification of such structural properties in the subsequent section. 4.2 Structural properties We commence our investigation into the structural properties by scrutinizing the monotonicities of the value function. Specifically, we draw inspiration from frequently observed structures in the realm of dynamic pricing, where concave-increas- ing expected revenues in remaining time and capacity are common. In our context, we will demonstrate that our objective function exhibits a similar monotonic increasing/decreasing behavior. Moreover, we will highlight the distinctive feature of our setting, where we typically do not observe a concave or convex behavior, setting it apart from standard dynamic pricing scenarios. Initially, we establish that expected costs increase with Ct and with t, while they decrease with Ot . Proposition 3 For any pre-arrival state SX t =(O t ,C t) , it holds: 1. Vt( O t, C t) ≤ Vt( O t, C t) with Ct ⊂C t 2. Vt( O t, C t) ≥ Vt( O t, C t) with Ot ⊂O t 3. Vt(Ot,Ct) ≤ Vt+1(Ot,Ct) with t≤T and time-homogeneous arrivals Proof The proof of Proposition 3 can be found in the Appendix (Section C.1). ◻ Besides monotonicities in the value function, an often observed pattern in dynamic pricing is that additional capacity and time have a diminishing effect with every additional unit, i.e. the value function is concave in these state variables. We show that there is no concave/convex structure present in our setting. Specifically, we show that avoided costs do not generally increase/decrease with Ct , Ot , or t. Proposition 4 For any pre-decision state SX t =( Ot , Ct ,o ) , it holds:
1098 R.Schur, K.Winheller 1. Neither Δ V t (O t , C t ,o,c)≤ΔV t (O t ,C t ,o,c ) nor Δ V t (O t , C t ,o,c)≥ΔV t (O t ,C t ,o,c ) is generally true for Ct ⊂C t 2. Neither Δ V t ( O t ,C t ,o,c)≤ΔV t (O t ,C t ,o,c ) nor Δ V t ( O t ,C t ,o,c)≥ΔV t (O t ,C t ,o,c ) is generally true for Ot ⊂O t 3. Neither ΔVt(Ot,Ct,o,c) ≤ ΔVt+1(Ot,Ct,o,c) nor ΔVt(Ot,Ct,o,c) ≥ ΔVt+1(Ot,Ct,o,c) is generally true for t≤T Proof The proof of Proposition 4 can be found in the Appendix (Section C.2). ◻ Proposition 4 underscores the complexity and context-specific nature of making operational decisions. This complexity arises because the value of avoided costs does not have a simple relationship with the state variables such as the available delivery locations, the remaining ODs, and the number of periods yet to come. The valuation is influenced by a multitude of factors, including but not limited to, the spatial distribution of locations, the timing and sequence of ODs, and the direct and indirect relationship between various delivery locations and ODs. As such, reducing state variables does not straightforwardly lead to higher or lower avoided costs, instead, the impact is contingent on the interplay of various factors at that moment in time. 5 Approximation methods In this section, we develop two algorithms that are used to approximate the avoided costs Δ V t (S X t ,c ) , associated with the costs that are avoided by removing a single delivery location c from the pre-arrival state of the next period. The first algorithm employs parametric value function approximation, rendering it a learning-based approach suitable for a broad spectrum of IC distributions discussed in Sect.3. The second algorithm, in contrast, adopts a FA. It demonstrates effective predictive capabilities particularly when the IC follows a uniform distribution. Both algorithms have undergone rigorous testing in the simulation study outlined in Sect.6. 5.1 Parametric value function approximation We propose a parametric VFA utilizing basis functions to effectively approximate avoided costs. The objective is to map a post-arrival state SX to a corresponding vector of expected avoided cost xc∈ ℝ ∀c∈Ct . As the exact avoided costs are computationally impractical to determine, a parametric VFA approximates these by employing a linear combination of features, also known as basis functions. These basis functions are scaled by a set of weights, which are learned during a dedicated learning phase. Once the learning phase concludes, the approximated avoided costs can be computed by building the linear combination of basis
1105 Optimizing last‑mile delivery: adynamic compensation strategy… The distance measure used is the Euclidean distance. We generated five graphs for each combination of C and O for both analyzed city structures that differ in the locations of their nodes. We combined these with the other parameters to create five distinct instances for each set of parameters to mitigate outliers. The performance of each method (see, Sect.6.1.2) was evaluated on 100 sampled OD arrival streams for each instance, and the average results of 500 simulation runs were analyzed for each set of parameters. 6.1.2 Comparative methods In line with the main incentive of our study, which is to analyze the advantages of optimizing individual dynamic compensations while anticipating uncertain OD arrivals and acceptance, we adopt a step-wise approach to analyze these model capabilities separately. To achieve this, we developed three methods, that draw inspiration from the literature and build progressively upon each other. The methods become gradually more complex as we introduce the capabilities of our model (refer to Table2): 1. Anticipation of uncertain dynamic arrivals of ODs 2. Anticipation of uncertain OD acceptance 3. Optimizing individual dynamic compensations In the first method, decisions are predetermined, disregarding the uncertain and dynamic nature of the arrival process. Delivery locations and ODs are matched by solving an assignment problem, that maximizes savings while ignoring uncertainty. This approach is comparable to the setting in Archetti etal. (2016), where OD arrival and acceptance are deterministic. As deterministic models often replace random variables with their expected values, we replace the IC with its expectation in this method. Consequently, the resulting compensation scheme mirrors the expected ICs, given by u oc +𝜅 4 . We refer to this method as IA (initial assignment). The second method addresses uncertain dynamic arrivals using a dynamic myopic assignment strategy, similar to approaches observed in related literature (e.g., Arslan etal. 2019; Dayarian and Savelsbergh 2020; Ausseil etal. 2022). In this method, the firm determines the optimal matching upon the arrival of each OD, focusing on the immediate effectiveness of a match, independent of uncertain future arrivals. This approach ensures that only arriving ODs are matched with delivery locations, and each OD receives the most suitable location. The compensation is chosen according to the expected IC. We refer to this method as DYN, reflecting its dynamic assignment strategy. The third method introduces the additional capability of anticipating uncertain OD acceptance and the ability to influence ODs’ decision-making through an optimized static compensation scheme. This method is inspired by similar approaches in literature (see, e.g., Silva and Pedroso 2022; Barbosa etal. 2023).
1106 R.Schur, K.Winheller Specifically, this method offers an optimized static compensation to all incoming ODs, mimicking the approach of Barbosa etal. (2023). In their work, the authors calculate the expected costs of the delivery process by offering a static compensation to ODs and using a full enumeration of all possible scenarios. However, due to the high complexity introduced by our dynamic approach, this brute-force evaluation is infeasible for relevant instance sizes. Instead, we replace full enumeration with a simulation of 100 arrival processes and use the average savings from these runs as the evaluation criterion. Consistent with Barbosa etal. (2023), we apply the golden ratio search algorithm to find the best static compensation. Matching decisions remain dynamic and myopic, in accordance with method DYN. We refer to this method as OSCS (optimized static compensation strategy). Fig. 3 Comparison of the average savings generated by each method, along with the respective 95% and 99% confidence intervals, for the base set of parameters Table 2 Summary of the model capabilities of the methods under comparison Incorporating Methods Anticipation of uncertain dynamic arrivals of ODs Anticipation of uncertain OD acceptance Optimizing individual dynamic compensations IA X X X DYN ✓ X X OSCS ✓ ✓ X VFA ✓ ✓ ✓
1107 Optimizing last‑mile delivery: adynamic compensation strategy… Table 3 Results of the sensitivity analysis. Each entry is the average value resulting from 500 simulation runs Research object Method Base C = 25 C = 75 Clustered O = 25 O = 75 T = 25 T = 75 a = 0.5uoc a = 1.5uoc b = 0.25𝜅 b = 0.75𝜅 Total Savings IA 69.66 44.63 95.18 74.09 61.59 69.18 43.11 84.85 77.11 44.35 70.34 41.94 DYN 94.47 67.15 104.62 104.47 64.90 107.01 62.73 111.66 103.52 88.72 113.21 77.14 OSCS 108.45 71.36 124.45 121.83 78.17 120.15 75.20 123.80 116.43 102.19 148.00 78.52 VFA 114.45 79.39 135.63 126.83 83.99 130.69 77.40 136.76 127.57 109.23 171.17 82.74 Relative savings 1 IA 100.00% 100.00% 100.00% 100.00% 100.00% 100.00% 100.00% 100.00% 100.00% 100.00% 100.00% 100.00% DYN 135.62% 150.44% 109.91% 141.00% 105.37% 154.68% 145.50% 131.61% 134.25% 200.07% 160.94% 183.92% OSCS 155.69% 159.87% 130.75% 164.44% 126.91% 173.67% 174.43% 145.91% 150.99% 230.44% 210.40% 187.21% VFA 164.31% 177.86% 142.50% 171.18% 136.36% 188.91% 179.55% 161.19% 165.43% 246.31% 243.33% 197.28% Compensations to ODs IA 101.04 48.21 124.82 95.49 83.97 97.98 62.03 122.61 68.17 51.71 52.18 75.84 DYN 54.81 54.45 51.14 54.39 38.86 62.15 33.31 65.66 52.64 50.88 37.41 70.50 OSCS 98.65 51.78 103.67 111.89 66.07 92.19 69.10 86.92 93.17 88.57 53.66 74.22 VFA 103.11 68.07 129.67 118.81 84.95 112.35 72.70 119.02 113.55 98.13 82.41 77.32 Relative OD costs 2 IA 23.48% 23.47% 19.06% 22.42% 19.15% 22.74% 13.58% 29.53% 16.12% 11.35% 12.14% 16.56% DYN 13.52% 29.78% 7.92% 13.75% 8.93% 15.81% 7.62% 16.91% 13.28% 12.37% 9.67% 16.67% OSCS 25.19% 28.99% 16.57% 29.59% 15.66% 24.27% 16.27% 23.10% 24.29% 22.26% 15.24% 17.61% VFA 26.74% 39.90% 21.11% 31.84% 20.42% 30.42% 17.20% 32.77% 30.49% 25.11% 25.06% 18.53% Number of served locations IA 17.07 9.28 22 16.95 14.55 16.71 10.51 20.74 14.52 9.60 12.25 11.77 DYN 14.92 12.16 15.57 15.88 10.37 16.916 9.60 17.73 15.61 13.96 15.06 14.76 OSCS 20.71 12.31 22.81 23.37 14.42 21.23 14.43 21.07 20.96 19.07 20.16 15.27 VFA 21.75 14.74 26.53 24.56 16.89 24.30 15.01 25.57 24.11 20.73 25.35 16.00 Relative number of served locations IA 34.14% 37.14% 29.33% 33.92% 29.11% 33.43% 21.03% 41.49% 29.06% 19.21% 24.50% 23.56% DYN 29.86% 48.64% 20.77% 31.77% 20.75% 33.83% 19.21% 35.46% 31.23% 27.92% 30.12% 29.53% OSCS 41.42% 49.26% 30.42% 46.74% 28.85% 42.47% 28.86% 42.14% 41.92% 38.15% 40.33% 30.55% VFA 43.51% 58.98% 35.37% 49.13% 33.79% 48.61% 30.02% 51.16% 48.22% 41.47% 50.72% 32.01%
1108 R.Schur, K.Winheller 1 Relative savings compared to IA 2 Relative OD costs refer to the share of costs that is attributed to compensations to ODs Table 3 (continued) Research object Method Base C=25 C=75 Clustered O=25 O=75 T=25 T=75 a = 0.5uoc a = 1.5uoc b=0.25𝜅 b=0.75𝜅 OD’s utility surplus IA 56.41 28.47 67.68 54.33 43.13 53.13 34.67 68.46 58.03 46.41 53.83 46.60 DYN 40.41 45.05 34.96 38.26 29.09 45.92 23.44 48.61 36.58 37.58 32.46 25.17 OSCS 56.91 39.51 66.77 64.11 42.15 56.42 40.53 61.89 58.78 48.38 47.38 30.95 VFA 64.61 47.53 77.04 75.39 50.55 69.97 44.55 74.61 69.87 61.33 61.49 45.67 Avg. compensation per OD IA 5.92 5.19 5.67 5.63 5.77 5.86 5.90 5.91 4.69 5.38 4.26 6.44 DYN 3.67 4.48 3.28 3.42 3.75 3.67 3.47 3.70 3.37 3.64 2.48 4.78 OSCS 4.76 4.21 4.54 4.79 4.58 4.34 4.79 4.12 4.45 4.64 2.66 4.86 VFA 4.74 4.62 4.89 4.84 5.03 4.62 4.84 4.65 4.71 4.73 3.25 4.83
1109 Optimizing last‑mile delivery: adynamic compensation strategy… Our approach combines all previously mentioned capabilities, optimizing individualized and dynamic compensations while anticipating uncertain dynamic arrivals and OD decision-making. The optimal solution is derived from Propositions 1 and 2, with avoided costs approximated using our methods from Sects.5.1 and 5.2. Both the VFA and FA, when combined with our analytical solution, demonstrated similarly strong performances across all instances, as illustrated in Fig.3 for the base set of parameters. To condense the results of our sensitivity analysis, we used the VFA to represent our approach that incorporates all model capabilities. 6.1.3 Results Table 3 presents the results of our simulation study. The savings generated by utilizing ODs vary significantly depending on the parameter set. However, a clear ranking of the analyzed methods emerges, where IA consistently produces the lowest savings and VFA yields the highest savings. For example, under the base set of parameters, the average savings compared to no OD utilization are 13.9% for IA and 22.9% for VFA. Figure4 illustrates the difference in savings between IA and VFA, as well as the proportion of costs attributed to OD compensations. To examine the cost-saving potential of each model capability, we consider the savings of IA as a lower bound and evaluate the relative savings when additional model capabilities are incorporated. The largest savings leap is observed when dynamic assignments are introduced in DYN. This alone accounts for 5%-100% of additional savings, depending on the set of parameters. The savings increase by an additional 3%-50% when an Fig. 4 Comparison of saved costs, compensations to ODs, and costs of DD delivery. The full circle represents the costs of a delivery without OD utilization. The middle column represents the base set of parameters, while the left and right columns represent the instances where C is decreased and increased, respectively
1110 R.Schur, K.Winheller instance-optimized static compensation in OSCS is used. By further considering individual dynamic compensations, our methodology could generate an additional savings of 5%-33%. Overall, our sensitivity analysis has identified three main factors that impact the savings and other metrics, which we will elaborate on below. Clustering tends to create more and better pairings (shorter detours) between ODs and delivery locations, leading to lower compensations and ultimately higher savings. Clustering also has a positive impact on the number of delivery orders served by ODs. The higher service rate also led to an increase in total paid compensation. The advantage of individual dynamic compensations (VFA) is persistent, but slightly lower compared to the base case. This is largely due to the more homogeneous IC resulting from shorter detours, which allows well-chosen static compensations to achieve decent results. The ratio of the number of arriving ODs to delivery locations is an important factor influencing savings. Increasing the number of periods (T) or the number of potential ODs (O) positively affects the average number of arriving ODs. In general, a higher average number of arriving ODs results in higher savings and higher utilization of ODs. At the same time, compensations per delivery decreased on average using OSCS and VFA in comparison to the instances with the base set of parameters. These methods benefit from the implicit and explicit anticipation of expected avoided costs. The advantages of individual dynamic compensations rose in the T=75 and the O=75 scenario with increasing average OD arrivals. This means the advantages of individual dynamic compensations are accelerated by a high OD emergence. A high supply of delivery orders (C) results in on average lower relative savings compared to the instances with the base set of parameters. However, total savings increase with C as more orders are accepted by ODs for lower compensations. The structure of the IC is crucial for the potential savings. It can be noted that reducing the impact of the detour on the IC through a reduction of the detour scalar aoct leads to higher average savings. We expected that with the decrease of aoct , the additional relative savings generated by individual dynamic compensations (VFA) would decrease since the IC becomes more homogeneous. Surprisingly, this was not the case, indicated by a higher relative savings gap between OSCS and VFA, compared to the base case. Further investigation revealed that not only compensations but also the additional non-myopic assignment strategy played a decisive role. When the interval length of the IC boct was reduced, the advantage of individual dynamic compensations increased significantly. The main reason for this is that OSCS had a structural disadvantage in this scenario because the ICs were more heterogeneous on average. Inspired by Le etal. (2021), we also tracked the average sum of OD utility surpluses, which is the difference between the realized IC and the compensation of an accepted delivery request. This can be seen as an indicator of the OD’s satisfaction with the participation and the chances of them participating again. The most important aspect, that was contradictory to what we were expecting is that the overall OD’s utility surplus was highest in VFA over all instances. This shows that individual compensations do not necessarily contradict a high OD satisfaction because
1111 Optimizing last‑mile delivery: adynamic compensation strategy… of IC exploitation. Quite to the contrary, both the store and the ODs can benefit from individual compensations. 6.2 Impact oftime windows In this section, we demonstrate that our framework, while primarily designed for unattended home delivery, can also be adapted to scenarios involving time windows, making it applicable to attended home delivery. For example, a customer may have the option to be delivered in the morning (8:00-12:00), the afternoon (12:00-16:00), or the evening (16:00-20:00). Each of these time windows can be treated as a delivery horizon, allowing us to consecutively apply our approach to effectively engage ODs during these periods (for similar approaches, see, e.g., Arslan etal. 2019; Silva etal. 2023a). However, we demonstrate the trade-off between offering short time windows and the potential savings achieved through OD utilization. This trade-off is not specific to our model but is inherent in engaging ODs. While narrow delivery time windows may be important for customer satisfaction, they reduce the likelihood of finding a suitable OD to carry out the delivery. In our computational study, we experimentally evaluate this trade-off, providing valuable insights for companies considering the integration of ODs into their delivery processes. We examine this trade-off by dividing the time horizon of our base case into several delivery horizons. For easier divisibility, we start with 60 delivery requests, 60 potential ODs, and 60 periods, representing, for example, a business day. The arrival rate is defined by 𝜆 ot =0.7 ⋅ 1 | O t| for o∈Ot . For the remainder of this section, all Fig. 5 Illustration of the time windows in each of the three scenarios Table 4 Results of the computational study on time windows # of TW Savings # Utilized ODs Avg. detour Avg. compensation 1 154.12 29 0.59 4.69 2 120.36 24 1.28 4.99 3 99.09 19 1.18 4.78
1112 R.Schur, K.Winheller other parameters are set according to the base set of parameters introduced in Sect.6.1. In each scenario, 10% of each delivery horizon is dedicated to DDs, while the remaining periods are available for engaging ODs. Figure5 illustrates the design of these delivery horizons, each consisting of a timeframe for OD engagement and DD deliveries, separated by the dispatch time. In all three scenarios we investigated, the 60 delivery tasks are evenly distributed across the time windows. To ensure comparability of simulated savings, all three scenarios share the same stream of ODs. This is crucial because different time window designs allocate varying periods for DD deliveries, affecting the availability of ODs who can only be engaged outside these periods. For example, if OD 63 arrives in period 28, they can only perform delivery in the first and third scenarios, as period 28 is dedicated to DD deliveries in scenario 2. If an OD arrives in any period (including those dedicated to DD deliveries), they are excluded from the set O of potential future ODs in the current and subsequent delivery horizon, reflecting the assumption that ODs go shopping at most once a day. The following results are generated by using our analytical solution (refer to Propositions 1 and 2) in combination with FA-SP. The results of the computational study (refer to Table 4) demonstrate that dividing the time horizon into multiple segments has a significant impact on savings. The highest savings, amounting to 154, were achieved without any division of the time horizon. When the time horizon was divided into two equal parts, the savings decreased to 120, which is around 22% less than the savings achieved without division. Further dividing the time horizon into three equal parts resulted in even lower savings of approximately 100, which is around 16.6% less than the savings from the two-part division (see Fig.6). This indicates that the division of the time horizon into multiple segments diminishes the cumulative savings that could be achieved over the entire business day without segmentation. The underlying reason for this reduction is that when delivery tasks are confined to specific time windows, certain pairings that were previously valid become invalid, necessitating the search for alternative pairings. Consequently, this leads to generally less profitable pairings and thus fewer assignments. Fig. 6 Visualization of the differences in savings and OD utilization with different time window granularities. The full circle depicts the costs that would have occurred without ODs
1113 Optimizing last‑mile delivery: adynamic compensation strategy… This trend is also reflected in the number of ODs utilized, which decreases from 29 without any time window division to 24 with a two-part division, and further down to 19 with a three-part division. However, the average detour taken by ODs does not exhibit a clear pattern. The lowest average detour, approximately 0.59, was observed in the scenario without any division. Contrary to expectations, the average detour in the two-part division scenario was higher at around 1.28, compared to 1.18 in the three-part division scenario. This anomaly can be explained by the reduced number of delivery tasks fulfilled by ODs in the segmented scenarios, leading to the exclusion of some less favorable pairings. In general, the choices become more limited as the number of time windows increases. In Fig.7 the assignments in each scenario are visualized. Each graph represents a full business day with 54 arrival periods. Despite the obvious tradeoff, even when dividing the business day into three-time windows, there are still significant benefits in utilizing ODs, indicated by savings of about 1 6 of the total costs without ODs. 7 Conclusion In our work, we introduce an innovative approach to leverage in-store customers, who may be willing to divert their planned route to deliver online orders for monetary compensation. While these occasional drivers present a cost-effective alternative to traditional dedicated drivers, they also pose additional challenges, arising from their unpredictable nature, manifested in their arrival time and decision-mak- ing. Our approach meets these characteristics by dynamically matching arriving occasional drivers with delivery tasks, incorporating individualized compensations that consider each occasional driver’s specific destination. This approach, similar to a reverse dynamic pricing model, explicitly accounts for the inherent unpredictability in the availability and decision-making of occasional drivers. Fig. 7 Visualization of the assignment policy observed in each scenario
1114 R.Schur, K.Winheller We prove several properties of the optimization problem, with a special focus on the optimal solution and avoided costs: First, we establish the existence of a unique optimum in the step-wise optimization. Furthermore, we provide a closed-form solution for scenarios where the IC is uniformly distributed, improving both computational efficiency and interpretability of the results. Second, we outline an efficient and simple method to find the optimal matching between OD and delivery locations, thereby refining the decisionmaking process. Finally, we shed light on the monotonic behavior of the avoided costs, paving the way for tailoring well-known approximation methods to our problem structure. In a comprehensive simulation study, we evaluate policies derived from our analytical state-dependent solution in combination with our approximation methods and compare resulting cost savings with those from methods inspired by recent literature. In these comparative methods, we incrementally introduce the capabilities of our approach: the anticipation of uncertain dynamic arrivals of ODs, the anticipation of uncertain OD acceptance, and the optimization of individual dynamic compensations for ODs. Our results suggest that significant savings can be achieved when all these capabilities are combined. However, the extent of the savings varies significantly depending on the set of parameters. For instance, scenarios with a high participation rate (i.e., a large number of potential ODs) tend to yield higher savings. Moreover, our approach not only demonstrated the highest savings potential across all instances but also proved to be the most beneficial for ODs in terms of their total utility surplus. Finally, we demonstrate the applicability of our framework in scenarios involving time windows, where it effectively generates significant savings. We also analyze the impact of time window length, offering firms a valuable decision-making tool for balancing the trade-off between OD engagement and time window design. Future research should focus on examining the IC of an OD population to better assess algorithm performance across different settings. Additionally, exploring the impact of variable cost structures for DDs, particularly those based on mileage, could provide significant benefits to companies that manage their fleet (Table5).
1121 Optimizing last‑mile delivery: adynamic compensation strategy… Depending on the setting, the neighborhood might be small or even empty. The size of the neighborhood can be increased by considering a higher-degree neighborhood. The second-order neighborhood is created by evaluating the neighborhood of every delivery location in N1 ( O , C ,c ) and combining all the resulting neighborhoods into one large neighborhood. One could further increase the size of the neighborhood by considering neighborhoods of any degree k, adding the first-order neighborhood of delivery locations included in the last iteration iteratively, i.e. N k( O , C ,c)= ⋃ c� ∶( ⋅,c� )∈ N k−1( O,C,c )N 1( O , C ,c �) . However, we found the second-order neighborhood to be sufficient to achieve high accuracy in predicting the avoided costs. A visual representation of the neighborhood generation is depicted in Fig.9. In this example, the second-degree neighborhood is created. Appendix C: Proofs C.1 Proofs ofproposition 3 Proof We will prove each statement individually. To establish the validity of the first and second statements, it is sufficient to demonstrate the assertions for any subsets Ct⊂ C t and Ot⊂ O t , where Ct⧵ C t={ct} and Ot⧵ O t={ot} for any ct and ot , respectively. By consistently applying the arguments outlined below for the first and second statements, we can verify the more general assertion of the proposition. We will establish the validity of the first two statements through induction over t. The statements are evidently true for the base case with t=T+1 , as Vt (O t , C t )= ∑c∈ C t 𝜅 c ≤ ∑c∈ C t 𝜅 c +𝜅 ct =V t (O t ,C t) , Vt (O t ,C t )= ∑c∈ C t 𝜅 c =V t ( O t ,C t) , allowing us to focus on the induction step. 1. Induction step, t+1→t : We examine two pre-arrival states ( O t, C t) and (Ot,Ct) . Both states contain the same set of remaining ODs, giving rise to related pre-decision states ( O t, C t,o) and (Ot,Ct,o) , respectively, with identical arrival probabilities 𝜆ot . In the following, we will prove that the expected costs associated with the pre-decision states ( O t, C t,o) are lower than the expected costs stemming from (Ot,Ct,o) for any o∈Ot . Let (c(o),r(o)) denote the optimal offer bundle in any pre-decision state (Ot,Ct,o) . Now, we manipulate the policy in the pre-decision states ( O t, C t,o) . Instead of applying the optimal policy, we offer (c(o),r(o)) if c(o)≠c , and (c,0) for an arbitrary c∈Ct if c(o)=c . Through the subsequent case analysis, we demonstrate that even with this suboptimal policy, we can still achieve lower expected costs originating from the state ( O t, C t,o) for any o∈Ot , implying expected costs in ( O t, C t) are lower than in (Ot,Ct) . Two cases can apply: Case 1: If we encounter an OD o with c(o)≠c , we have the same immediate costs transitioning from both states ( O t, C t,o) and (Ot,Ct,o) to the subsequent prearrival states. However, our induction hypothesis reveals that the expected future
1122 R.Schur, K.Winheller costs from the subsequent pre-arrival states are lower for ( O t ⧵{o}, C t ⧵{c(o )}) and ( O t ⧵{o}, C t) compared to (Ot⧵{o},Ct⧵{c(o)}) and (Ot⧵{o},Ct) , respectively. Therefore, in this case, the expected costs are lower for the pre-decision state ( O t , C t ,o ) than for (Ot,Ct,o) . Case 2:. If we encounter an OD o with c(o)=c , there are no immediate costs when transitioning from ( O t , C t ,o ) to ( O t ⧵{o}, C t) . Conversely, transitioning from (Ot,Ct,o) , leads to two possibilities: either incurring immediate costs by transitioning to (Ot⧵{o},Ct⧵{c}) , or incurring no immediate costs by transitioning to (Ot⧵{o},Ct) . In the first scenario, both pre-decision states ( O t , C t ,o ) and (Ot,Ct,o) result in the same subsequent pre-arrival state ( O t ⧵{o}, C t) . However, the latter transition involves immediate costs. In the second scenario, both transitions are free of immediate costs, but transitioning from (Ot,Ct,o) results in a subsequent pre-arrival state with higher expected future costs than transitioning from ( O t , C t ,o ) , as indicated by our induction hypothesis. 2. Induction step, t+1→t : We analyze two pre-arrival states, namely ( O t ,C t) and (Ot,Ct) . It is noteworthy that, in this scenario, the arrival of o ∈ O t is equally likely in both states. However, the arrival of o can only occur in the state (Ot,Ct) . Therefore, based on our assumptions, we have 𝜆ot +𝜆 t = 𝜆 0t , where 𝜆t and 𝜆0t represent the no-arrival probability of ODs in the states (Ot,Ct) and ( O t ,C t) , respectively. Let (c(o),r(o)) denote the optimal offer bundle in any pre-decision state ( O t ,C t ,o ) . Now, we manipulate the policy in the pre-decision states (Ot,Ct,o) . Instead of applying the optimal policy, we offer (c(o),r(o)) when OD o ∈ O t arrives, and (c,0) for an arbitrary c∈Ct when OD o arrives. With this suboptimal policy, we constructed a scenario in which pre-decision states ( O t ,C t ,o ) and (Ot,Ct,o) transition with the same immediate costs and probabilities to subsequent pre-arrival states, for each o ∈ O t , leading to expected future costs that are higher for the subsequent state of ( O t ,C t ,o ) than for the subsequent state of (Ot,Ct,o) . In the absence of any OD or the arrival of OD o , both pre-decision states transition without any immediate costs to subsequent pre-arrival states, where ( O t ,C t ,o ) once again finds itself in a subsequent state with higher expected future costs than its counterpart. 3. This proof diverges from the induction approach, relying instead on policy manipulation across the entire planning horizon. To begin, it is crucial to highlight that both pre-arrival states share an identical set of remaining ODs. Consequently, any OD o has the same probability of arriving in either state. Moreover, both states encompass the same remaining delivery locations. The sole distinction lies in the time period: while Vt(Ot,Ct) has T+1−t periods left to acquire ODs, Vt+1(Ot,Ct) has only T−t periods left. Let 𝜋t′ , with t+1≤t�≤T , represent the optimal policy employed to compute Vt+1(Ot,Ct) , where 𝜋t′ maps a pre-decision state in t′ with a bundle (c,r). We proceed to replicate this policy to calculate expected costs for (Ot,Ct) in period t. Therefore, we apply the policy 𝜋t′ in period t�−1 for every t+1≤t�≤T . This ensures that we encounter the same immediate costs and undergo identical transitions, regardless of whether we initiate the process in t or t+1 . Nevertheless,
1123 Optimizing last‑mile delivery: adynamic compensation strategy… commencing in t provides an extra period after the planning horizon, allowing us to further minimize expected costs when starting from t instead of t+1 . ◻ C.2 Proof ofproposition 4 Proof In order to validate the proposed propositions, we present counterexamples for each, utilizing a specially designed instance as depicted in Fig.10. This instance Fig. 10 Graphical representation of the created example instance
1124 R.Schur, K.Winheller is crafted to elucidate specific effects that invalidate potential monotonicities. While maintaining consistent coordinates, we vary the arrival probabilities and the presence of certain nodes across different scenarios. A key element of our analysis focuses on the detours associated with various delivery locations. Consider OD2, which is located at a distance r from the depot. It follows that any delivery location situated on a circle centered at OD2 with radius r would have a detour distance equivalent to its distance from the depot. Consequently, the detour from OD2 to C1 is quantified as 3 units, and from OD2 to C2 as 8 units. Additionally, we chose the location of OD3 along the orthogonal bisector of the line connecting C1 and the depot. This geometric alignment ensures that the detour for a path from OD3 to C1 is also 3 units. Furthermore, OD1 is strategically placed on the direct line between C1 and the depot. This implies that the detour for OD1 involves a double traversal of the segment between its location and C1, amounting to a total detour distance of 3 units (twice the x-coordinate difference of OD1 from C1). The detour values for each OD delivery location combination can be found in Table6. For clarity, we introduce a conceptual dummy OD4, characterized by an infinitely long detour to every delivery location and a guaranteed arrival in period 1. Throughout all instances, we assume a uniformly distributed ICoct which is independent of t and has the bounds aoct =uoc and boct =2 . Every delivery location is associated with a cost of 𝜅c =10 if it is not served by an OD until the time horizon is over. 1. In the first example, we analyze the change in avoided costs that occurs when adding an OD to Ot in a fixed pre-decision state Vt(Ot,Ct, o , c ) . Specifically, we show that the avoided costs ΔV1({1, 2, 4},{1, 2},4,1) increase when introducing OD3 while the avoided costs ΔV1({1, 2, 4},{1, 2},4,2) decrease. The arrival probabilities for the ODs are as follows: OD1 is certain to arrive in period 2 (probability of 1) with no arrival probability in other periods. OD2 and OD3, when the latter exists, have an arrival probability of 0.5 in periods 3 and 4. It is important to note that OD3 services no other delivery location than C1, as the lower bound of the IC for other delivery locations lies above the threshold 𝜅c . This renders offering these to OD3 economically irrelevant for the firm. The introduction of OD3 increases the likelihood of delivery location C1 being served in periods 3 or 4 due to the availability of two potential ODs for this location, subsequently influencing the Table 6 Detour matrix uoc C1 C2 C3 OD1 3 13.2 10.7 OD2 3 8 12 OD3 3 12.9 0
1125 Optimizing last‑mile delivery: adynamic compensation strategy… firm’s willingness to spend on serving delivery location C1 in period 2 when OD1 arrives. In Scenario 1, where OD3 is absent, the uncertainty of OD2’s arrival prompts the firm to offer OD1 a compensation of 4.8125 in period 2 for serving C1, which is accepted with a probability of 0.90625. This means that there is a high probability that delivery location C2 is the only one remaining to be serviced during the final two periods (3 and 4). Subsequently, should OD2 make an appearance in either of these periods, the firm offers delivery location C2, coupled with a compensation of 9. This offer has a 0.5 chance of acceptance. Consequently, the overall serving probability for delivery location C2, in this case, is calculated as 0.90625 ⋅ (1−0.52) ⋅ 0.5 ≈0.34 . If OD1 declines the offer to serve C1 in period 2, C2 is left without the possibility of being served by an OD. This outcome stems from the fact that the remaining driver, OD2, would face a significantly smaller detour to serve location C1. Consequently, from an economic standpoint, it becomes more beneficial for the firm to allocate OD2 to C1 rather than to C2. Building on the optimal policy in periods 2 to 4, we can calculate the avoided costs in period 1, resulting in ΔV1({1, 2, 4},{1, 2},4,2)≈9.68 , while ΔV1({1, 2, 4},{1, 2},4,1)≈4.98 . A tree representation of this scenario can be seen in Fig.11. Scenario 2 introduces OD3, providing an additional viable option to serve delivery location C1 in later periods. This increased competition for serving delivery location C1, due to more service opportunities, leads to avoided costs of ΔV1({1, 2, 3, 4},{1, 2},4,1)≈4.62 , a decrease compared to the avoided costs without the additional driver, OD3. The firm, therefore, reduces the amount it is willing to spend on serving C1 in early periods, which is reflected in a compensation of 4.125 for OD1 on arrival in period 2, leading to an acceptance probability of 0.5625. This decreased acceptance probability ultimately also reduces the total probability of delivery location C2 being served: Under this scenario, delivery Fig. 11 Tree diagram of the example instance of example 1 (without the additional OD)
1126 R.Schur, K.Winheller location C2 is served in two cases. First, if OD1 accepts the offer for serving C1 in period 2 and subsequently, OD2 arrives in a later period to serve delivery location C2 (probability of occurrence: 0.5625 ⋅ (1−0.52) ⋅ 0.5 ≈0.211 ). Second, if OD1 declines the offer, followed by OD3’s arrival in period 3, coupled with the acceptance of serving C1, and OD2’s arrival in period 4 to serve delivery location C2 (probability of occurrence: (1−0.5625) ⋅ 0.5 ⋅ 1 ⋅ 0.5 ⋅ 0.5 ≈0.0547 ). This results in a total serving probability for delivery location C2 of approximately 0.266 in Scenario 2, explaining why the avoided costs for delivery location C2 increase to 9.74 with the addition of OD 3, while the avoided costs for C1 decrease to 4.62. A tree representation of this scenario can be seen in Fig.12. 2. In the second example, we analyze the change in avoided costs that occurs when adding a delivery location to Ct in a fixed pre-decision state Vt(Ct,Ot, o , c ) . Specifically, we show that the avoided costs ΔV1({1, 2, 3, 4},{1, 2},4,1) increase when introducing delivery location 3, while the avoided costs ΔV1({1, 2, 3, 4},{1, 2},4,2) decrease. Considering that the scenario without the existence of delivery location C3 has been addressed previously (refer to 1., scenario 2, where the avoided costs for C1 and C2 were 4.62 and 9.74, respectively), we will focus our attention directly on the scenario where delivery location C3 is included. By comparing this new scenario with the first scenario from the previous example (where C3 and OD3 are absent), we observe notable similarities leading to the same avoided costs for delivery location C1 and C2. These similarities arise from the unique association between OD3 and C3, both situated in the same location. Fig. 12 Tree diagram of the example instance of example 1 (with the additional OD)
1127 Optimizing last‑mile delivery: adynamic compensation strategy… As a result, OD3 is consistently offered delivery location C3 for a compensation of 2 upon arrival, an offer that is accepted with a probability of 1. This arrangement effectively isolates OD3 to delivery location C3, as he becomes irrelevant for other nodes due to the strong match with delivery location C3. In the absence of delivery location C3, OD3 would have been a potential service provider for delivery location C1, resulting in the same effects already discussed in Scenario 2 of the previous example. The introduction of delivery location C3 and the consequent exclusive pairing with OD3 reduces the competition for serving delivery location C1. This reduction in competition leads to an increase in the avoided costs for delivery location C1, akin to a scenario where neither OD3 nor delivery location C3 exists (refer to 1., scenario 1). Consequently, this alteration in the service landscape enhances the probability of delivery location C2 being served, as OD1 now serves delivery location C1 with a certainty of approximately 0.906 instead of only 0.5625 in the second period. As a result of these shifts in service probabilities and competition dynamics, the avoided costs for delivery location C2 decrease, aligning back to approximately 9.68, as observed in the scenario without OD3 and C3. Analogously, the avoided costs for C1 increase, returning to approximately 4.98. A tree diagram with the effect can be seen in Fig.13. To simplify, the choices illustrated in the pre-decision states (represented as squares) have been reduced to only the optimal choices. 3. In the third example, we analyze the effect of decreasing the remaining time until the store closes. For this we hold the pre-decision state Vt(Ct,Ot, o , c ) fixed and observe how ΔVt({2, 3, 4},{1, 2}, 4, c) changes with t for each c. In this scenario, avoided costs can increase and decrease with period t. This example is set within a framework of only three periods, excluding OD1 and Fig. 13 Tree diagram of the example instance of example 2 (with the additional delivery location)
1128 R.Schur, K.Winheller delivery location C3 for clarity. To facilitate a comparison of avoided costs across stages, dummy OD4 might arrive in periods 1 and 2 respectively. The arrival probabilities are defined as follows: OD2 has a probability of 0.5 in periods 2 and 3, while OD3’s probabilities are 0.1 in period 2 and 0.5 in period 3. Notably, the avoided costs for delivery location C2 in period 1 are relatively high at 9.975. This outcome arises from the only viable service scenario for delivery location C2: OD3 must arrive in period 2, which occurs with a probability of 0.1. Upon arrival, OD3 is presented with an offer to serve C1, which he accepts with certainty (probability of 1), due to the compensation of 5. Following this, OD2’s arrival in period 3 (with a probability of 0.5) is necessary. OD2 must then accept an offer of 9 to serve C2 (which occurs with a probability of 0.5). The cumulative probability of these events leading to the service of C2 is calculated as 0.1 ⋅ 1 ⋅ 0.5 ⋅ 0.5 =0.025 . This implies that there’s a 2.5% chance for this sequence to unfold, resulting in a cost saving of 1 for serving C2 under these specific conditions. Advancing to the next period without altering the state renders it impossible for delivery location C2 to be served in the next period, as both ODs are offered delivery location C1 upon their arrival in period 3. As a result, the avoided costs for serving delivery location C2 increase to 10 in period 2. The avoided costs for delivery location C1 in period 1 amount to 5.35, reflecting primarily the immediate benefit of eliminating the need to serve C1 in later states. A portion of these avoided costs, although smaller, is attributed to the enhanced potential of serving C2 in the last two periods 3 and 4, assuming C1 has been serviced already. Moving on to period 2, we observe a decline of C1’s Fig. 14 Tree diagram of the example instance of Example 3 (progressing t)
1129 Optimizing last‑mile delivery: adynamic compensation strategy… avoided costs to 5.25. This decline is primarily due to the reduced opportunity for serving C2 in the absence of C1, given the diminishing time frame. With only period 4 remaining, the probability and, consequently, the strategic value of serving C2 decrease. A tree diagram with the effect can be seen in Fig.14. ◻ C.3 Proof ofLemma 3 Proof We will prove each statement individually. To establish the validity of the first and second statements, it is sufficient to demonstrate the assertions for any subsets Ct ⊂C t and Ot ⊂O t , where Ct ⧵ C t ={c t} and Ot ⧵ O t ={o t} for any ct and ot , respectively. By consistently applying the arguments outlined below for the first and second statements, we can verify the more general assertion of the proposition. 1. Expanding Ct to Ct by incorporating ct alters the formulation of the FA as follows: Firstly, we introduce the decision variables roct ≥0 to the optimization model. Secondly, a non-negative term is added to the objective function (22). Specifically, Thirdly, the set of constraints specified in (23) is enriched with the additional constraint ∑ o∈O t PAr(o)⋅PAc(o,ct,roc t )≤ 1 . Lastly, the non-negative term PAc(o,ctroct) is added to the left-side of constraints (24). Consequently, the optimal solution that yields Vt( O t, C t) remains feasible, upon removing the decision variable roct , for the optimization problem pertaining to state ( O t , C t) . Furthermore, we can infer that the objective value Vt( O t, C t) exceeds the value this feasible solution yields for the state ( O t , C t) . Since this suboptimal but feasible solution is below Vt( O t, C t) , it follows that the optimal solution is also below this value by definition. 2. This proof follows a similar logic to the one discussed above. By expanding the set of ODs from Ot to Ot by including ot , the FA undergoes analogous changes as outlined previously. Decision variables rotc≥0 are introduced into the model. A term, which is non-positive in the optimal solution, is added to the objective function: ∑ c∈C t PAr(ot)⋅PAc(ot,c,ro t c)⋅(ro t c−𝜅c ) . Additionally, the constraints in (23) and (24) are adjusted to accommodate the new set of decision variables. (28) ∑ c ∈Ct ∑ o∈Ot PAr(o)⋅PAc(o,c,roc)⋅roc + ∑ c∈Ct ( 1− ∑ o∈Ot PAr(o)⋅PAc(o,c,roc) ) ⋅𝜅c =∑ c∈ Ct∑ o∈Ot PAr(o)⋅PAc(o,c,roc)⋅roc +∑ c∈ Ct(1−∑ o∈Ot PAr(o)⋅PAc(o,c,roc))⋅𝜅 c + ∑ o∈ O t PAr(o)⋅PAc(o,ctroct)⋅roct+ ( 1− ∑ o∈ O t PAr(o)⋅PAc(o,ctroct) ) ⋅𝜅ct
1130 R.Schur, K.Winheller It is crucial to note that the optimal solution for the state ( O t ,C t) can be transformed into a feasible solution for the state (Ot,Ct) by setting r o t c =0 and retaining any other value over. Given that PAc(ot,c,0)=0 , this feasible solution yields the same objective value for the state (Ot,Ct) as the optimal objective value Vt ( O t ,C t) . Since we are dealing with a minimization problem, the optimal objective value is below this value. Thus, the statement holds true. 3. In this proof, we examine the implications of lowering t+1 to t. Employing the same methodology as before, we modify the optimal solution for t+1 to be feasible for t while resulting in a lower objective value than Vt+1 (O t ,C t) . As per its definition, PAr(o) increases with a decrease in t. This gives rise to a dual impact on the optimization model: firstly, the value function decreases for any solution roc ≤𝜅c . Secondly, constraints (23) become more stringent. So, how should we adapt the optimal solution of t+1 ? To adhere to the tightened constraints in (23), adjustments must be made to some of the roc . This entails lowering certain roc≤𝜅c values when the constraint is violated for c . More specifically, we can select these decision variables in a manner that reconstructs the same probabilities PAr(o) ⋅ PAc(o,c,roc) for t as we initially had for t+1 . Consequently, this particular delivery location now carries lower expected costs, leading to a reduction in the objective value. The decision variables concerning delivery locations where the constraint is not violated can remain the same and still result in lower expected costs (due to the increase in the arrival probability). Overall, these alterations lead to a feasible solution for t, yielding lower expected costs than for t+1 . ◻ 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/. References Akçay Y, Natarajan HP, Xu SH (2010) Joint dynamic pricing of multiple perishable products under consumer choice. Manag Sci 56(8):1345–1361. https:// doi. org/ 10. 1287/ mnsc. 1100. 1178 Allahviranloo M, Baghestani A (2019) A dynamic crowdshipping model and daily travel behavior. Transp Res Part E: Logist Transp Rev 128:175–190. https:// doi. org/ 10. 1016/j. tre. 2019. 06. 002 Archetti C, Savelsbergh M, Speranza MG (2016) The vehicle routing problem with occasional drivers. European J Op Res 254(2):472–480. https:// doi. org/ 10. 1016/j. ejor. 2016. 03. 049 Archetti C, Guerriero F, Macrina G (2021) The online vehicle routing problem with occasional drivers. Comp Op Res 127:105144. https:// doi. org/ 10. 1016/j. cor. 2020. 105144 Arslan AM, Agatz N, Kroon L, Zuidwijk R (2019) Crowdsourced delivery–a dynamic pickup and delivery problem with ad hoc drivers. Transp Sci 53(1):222–235. https:// doi. org/ 10. 1287/ trsc. 2017. 0803 Ausseil R, Pazour JA, Ulmer MW (2022) Supplier menus for dynamic matching in peer-to-peer transportation platforms. Transp Sci 56(5):1304–1326. https:// doi. org/ 10. 1287/ trsc. 2022. 1133