Strategic Workforce Planning in Crowdsourced Delivery With Hybrid Driver Fleets

Abstract

Nowadays, logistics service providers (LSPs) increasingly consider using a crowdsourced workforce on the last mile to fulfill customers’ expectations regarding same-day or on-demand delivery at reduced costs. The crowdsourced workforce’s availability is, however, uncertain. Therefore, LSPs often hire additional fixed employees to perform deliveries when the availability of crowdsourced drivers is low. In this context, the reliability versus flexibility trade-off which LSPs face over a longer period, for example, a year, remains unstudied. Against this background, we jointly study a workforce planning problem that considers salaried drivers (SDs) and the temporal development of the crowdsourced driver (CD) fleet over a long-term time horizon. We consider two types of CDs, dedicated gig-drivers (DDs) and opportunistic gig-drivers (ODs). While DDs are not sensitive to the request’s destination and typically exhibit high availability, ODs only serve requests whose origin and destination coincide with their own private route’s origin and destination. Moreover, to account for time horizon-specific dynamics, we consider stochastic turnover for both SDs and CDs as well as stochastic CD fleet growth. We formulate the resulting workforce planning problem as a Markov decision process whose reward function reflects total costs, that is, wages and operational costs arising from serving demand with SDs and CDs, and solve it via approximate dynamic programming. Applying our approach to an environment based on real-world demand data from GrubHub, we find that in fleets consisting of SDs and CDs, approximate dynamic programming (ADP)-based hiring policies can outperform myopic hiring policies by up to $19\mathrm{\%}$ and lookahead policies with perfect knowledge of future information by up to $10\mathrm{\%}$ in total costs. In the studied setting, we observed that DDs reduce the LSP’s total costs more than ODs. When we account for CDs’ increased resignation probability when not being matched with enough requests, the amount of required SDs increases.

1. Introduction

In recent years, on-demand home delivery services experienced significant growth, especially in urban areas. Global e-commerce sales grew by $38\mathrm{\%}$ in a year-over-year comparison in 2021 (Forbes, 2021), and consumers increasingly use meal and grocery delivery apps. This rapid growth in demand for delivery services leads to increased customer expectations regarding same-hour or same-day delivery. Herein, logistics service providers (LSPs) face a dilemma as they must provide sufficient delivery capacity to rapidly serve increasing demand while maintaining low costs to remain competitive. To address this challenge, LSPs increasingly consider crowdsourcing: they outsource delivery requests to crowdsourced drivers (CDs), that is, independent contractors who flexibly decide when and where to work and are paid per request and not per hour. CDs can decide to leave the LSP’s fleet at any time. The LSP profits from the CDs as an easily scalable workforce at the price of uncertainty in the CDs’ availability, both from a strategic long-term and an operational short-term perspective. While many LSPs base their business models exclusively on CDs, for example, Doordash or Grubhub, some companies operate hybrid driver fleets, that is, fleets consisting of CDs and salaried drivers (SDs), who receive compensation regardless of their utilization during the contract period, to reduce the uncertainty arising from the use of CDs. For example, Bringg’s partnership with WorkWhile aims at providing additional delivery capacity through a pool of CDs to LSPs with existing SD fleets (Freightwaves, 2022).

To account for heterogeneous CD behavior, we consider two predominant types of CDs: the first type of CDs are dedicated gig-drivers (DDs), whose request acceptance behavior is not sensitive to the request’s destination and who typically exhibit high availability. Example companies relying on this type of workforce are Postmates, Instacart, DoorDash (in the US), or Rappi (in South America). DDs install an app on their phone and receive a notification when a new delivery request arises. They can then either accept the request or wait for another request. When serving the request, they receive compensation, typically proportional to the distance of the request’s route. Second, we consider ODs, which only serve requests whose origin and destination coincide with their private route’s origin and destination. For example, the company Roadie relies on this type of driver. As such a concept leverages pre-existing routes, it potentially reduces delivery traffic, emissions, and costs.

One major challenge of a mixed fleet of SDs and CDs is to ensure minimum service levels, which the LSP achieves by hiring the right number of SDs based on the expected demand and the uncertain CD supply unfolding throughout the planning horizon. While initially hired SDs might become obsolete if the number of CDs grows, not hiring enough SDs early negatively impacts the LSP’s service level in early time periods. Hence, the main focus of this article is to examine the trade-off between hiring a reliable workforce supply via SDs, who receive compensation regardless of their utilization during the contract period, and the uncertain supply from CDs, whose compensation is proportional to their utilization. Hiring obsolete SDs poses an issue especially if the contract duration for SDs is long. Such long contract durations are particularly prevalent in regions with stringent labor regulations, for example, the European Union. If the contract duration is rather short (cf. Amazon, 2023) the LSP is less committed to SDs and can decide ad-hoc whether to prolong the SDs’ contract or not.

Since the level of required SDs to match the demand depends on operational aspects, for example, request route patterns, we develop a framework that integrates decision-making on two planning levels: the strategic level, where the LSP makes hiring decisions, and the operational level, where the LSP decides on how to route its SDs and which request to outsource to CDs. In the remainder of this section, we relate our work to the existing literature (Section 1.1), state our contribution (Section 1.2), and outline the article’s structure (Section 1.3).

1.1. Related Literature

Three streams of literature relate to our work: vehicle routing problems (VRPs) with CDs, strategic workforce planning problems with conventional employees, and studies combining workforce planning and crowdsourcing for general on-demand service platforms and last-mile delivery companies. We detail these streams in the following.

A large body of literature emerged in the field of VRPs with CDs. First studies consider an LSP that optimizes route plans for deliveries from a single depot for SDs and expected CDs in a static day-ahead manner (Archetti et al., 2016; Gdowska et al., 2018; Torres et al., 2022). Other papers study delivery with CDs in a multi-depot (Sampaio et al., 2019) or many-to-many network (Raviv and Tenzer, 2018; Voigt and Kuhn, 2022). Further works consider a dynamic delivery problem (DDP) in a crowdsourced context (Arslan and Zuidwijk, 2019; Dayarian and Savelsbergh, 2020; Mak, 2020), which is a special class of a dynamic pick-up and delivery problem (Berbeglia et al., 2010), wherein drivers do not change their route or pick-up another request once they began serving the current one. More recently, the meal delivery routing problem (MDRP) led to an increased focus on the DDP with CDs. In the MDRP, requests arise dynamically at random regions and must be delivered instantly to their destinations. In this context, some works consider random CD supply (Reyes et al., 2018), while others assume that CDs’ availability is known to the LSP (Ulmer et al., 2021; Yildiz and Savelsbergh, 2019). Our problem corresponds to a DDP in a many-to-many network using CDs, and we refer to the literature review of crowdsourced delivery in Alnaggar et al. (2021) and Savelsbergh and Ulmer (2022) for a comprehensive overview. So far, studies on the dynamic delivery setting consider relatively small instance sizes to benchmark their order matching and courier routing policies, for example, 24 drivers (Ulmer et al., 2021). Moreover, to the best of our knowledge, all works considering the dynamic delivery problem with CDs envision CDs to behave like DDs and neglect the potential of synchronizing demand with ODs.

In the strategic workforce planning problem with conventional employees, the objective minimizes costs from hiring, compensating, promoting, and operating a workforce over a certain time horizon. Several studies model employee hiring, training and learning, and turnover dynamics as a sequential decision-making problem formalized as a Markov decision process (MDP). Gans and Zhou (2002) considered the employee hiring problem of a service organization that wants to serve uncertain demand. They model hiring decisions, up-skilling transitions, employees’ turnover rates and formulate a total cost minimization objective, including an operational cost element. Similar studies include firing decisions (Ahn et al., 2005), propose heuristics to solve large instances (Song and Huang, 2008), consider worker heterogeneity (Arlotto et al., 2014), account for inter-departmental worker mobility (Dimitriou et al., 2013), model decisions on multiple organizational levels (Guerry and De Feyter, 2012), or focus on a specific application case, for example, healthcare (Hu et al., 2016). Further works use multi-stage stochastic programming combined with linearizations, Bender’s decomposition, or conic optimization (cf. De Feyter et al., 2017; Jaillet et al., 2022; Zhu and Sherali, 2009). Similar to these studies, we aim at finding total cost minimizing SD hiring policies over a long-term planning horizon. None of these works, however, considers the presence of a partially uncertain workforce whose size cannot be controlled. Incorporating such an uncertain workforce in our long-term SD hiring problem is the focus of our work.

Some studies investigate workforce management in a crowdsourced context. One stream of works analyzes general on-demand platforms controlling the supply of crowdsourced workers indirectly by adjusting the compensation offered for a service. Gurvich et al. (2019) studied such a platform and consider self-scheduling agents that decide to work based on expected compensation and their availabilities. Similar works focus on surge pricing to balance demand and supply (Cachon et al., 2017), on the influence of agents’ independence and customers’ delay sensitivity (Taylor, 2018), and platform commission schemes (Zhou et al., 2019). Similarly to these works, we consider self-scheduling agents as part of our workforce. However, our problem formulation differs significantly from existing works, as we consider them jointly with conventional employees (the SDs) and control our workforce solely through the hiring process of SDs. Finally, studies combining workforce planning and crowdsourced delivery are closest to our work. Dai et al. (2017) studied a problem with in-house drivers (equivalent to permanent employees), part- and full-time CDs, and derive optimal in-house driver and CD staffing levels at different depots and times of one day based on a deterministic demand scenario. Similarly, Behrendt et al. (2022a), Cheng et al. (2023), and Goyal et al. (2023) considered hybrid crowdsourced fleets with joint SD fleet-sizing and operational decision making, respectively focusing on warehouse allocation decisions, robust workforce management, and order pricing. All of these studies are restricted to a time horizon of one day, similar to Ulmer and Savelsbergh (2020) and Behrendt et al. (2022b), who focus on pure CD fleets and consider two types of CDs: scheduled CDs that announce their availability prior to the operational time horizon and unscheduled couriers, that arrive ad-hoc while the LSP already operates. They aim to find the optimal set of schedules for one day to minimize fixed costs associated with scheduled CDs and operational costs. While the former employ a classical value function approximation approach, the latter use neural networks to find the optimal set of shifts. Finally, Lei et al. (2020) also considered a one-day planning horizon and an entirely crowdsourced delivery platform and study mechanisms to reduce demand-supply imbalance by outsourcing excess requests to drivers willing to prolong their scheduled shifts. While these works study joint SD acquisition and operational planning, they consider short-term planning horizons. Hence, these works do not account for long-term dynamics, for example, workforce turnover or stochastic CD fleet growth. Moreover, the LSPs’ contractual commitment when hiring SDs reduces itself to one day in the studies above. However, in many legislative systems, contracts for fixed employees must have a minimum duration of a year, even when considering temporary contracts. Changing demand levels or increasing CD supply might make these fixed employees obsolete before their minimum contract duration terminates. Our work will address this untouched issue by considering long-term time horizons.

In conclusion, our work closes three gaps in the literature, combining crowdsourced delivery and workforce management. First, to the best of our knowledge, no work considers joint SD fleet sizing and operational decision-making on a long-term time horizon, thereby neglecting dynamics such as workforce turnover or stochastic CD fleet growth. Second, all works considering the dynamic delivery problem with CDs envision CDs to behave like DDs, hence disregarding the potential to synchronize demand with ODs. Third, studies on the dynamic delivery setting with CDs consider relatively small instance sizes. Yet, the instant delivery market, especially in urban areas, is expected to grow significantly, thus calling for studies accounting for large demand scenarios and large delivery fleets.

1.2. Contribution

To close the research gaps outlined above, we develop a novel framework to study the long-term workforce planning problem in the context of hybrid crowdsourced delivery fleets. To account for the interplay between workforce planning and operations, we integrate hiring decisions for a long-term time horizon with operational decisions regarding SD relocation and outsourcing of demand to CDs. Moreover, we consider two CD types, DDs and ODs, which exhibit distinct request acceptance behaviors. While the former is less sensitive to a request’s origin and destination and typically exhibits higher availability, the latter only accepts requests whose origin and destination coincide with their private route’s origin and destination.

Figure 1.

Different temporal entities and their dependency. Here, $K$ denotes the number of sub-horizons of $\overline{\mathcal{T}}$ . The variables $t$ and $\overline{t}$ represent the time steps of the strategic and operational level time horizons, respectively.

Specifically, our contribution is threefold. First, we formalize the strategic level planning problem as a novel stochastic workforce planning problem, wherein the LSP needs to decide on how many SDs to hire or fire while taking into account uncertain CD supply. We model the strategic level as a finite-horizon MDP. Here, the objective is to minimize total costs arising from SD wages and operational costs. To obtain the latter term for large fleets within reasonable computation times, we approximate the operational problem with a fluid model. Second, we prove the value function’s convexity along the SD dimension and use this property to develop a look-ahead policy based on piecewise linear value function approximation (PL-VFA), which approximately solves our strategic problem. Third, we conduct numerical studies based on real-world data provided by Grubhub (2018), wherein we benchmark our PL-VFA against a myopic policy and a lookahead policy with perfect knowledge of future information. Furthermore, we evaluate sensitivities of strategic and operational levels’ parameters, for example, joining and resignation rates of CDs. Our main findings are as follows: (i) A hiring policy obtained from PL-VFA can yield up to $19\mathrm{\%}$ lower total costs than a myopic hiring policy and up to $10\mathrm{\%}$ lower total costs than a lookahead policy with perfect knowledge of future information. It does so by hiring less SDs than required in early time steps and by relying on future CD supply. (ii) SDs remain an important cost driver of total costs in the hybrid fleet, constituting up to 50% of total costs. Thus, developing better hiring SD policies can significantly impact total costs. DDs are the main cost driver among CDs, whereas ODs bear a significant potential when their spatial and temporal patterns are synchronized with request patterns. (iii) When we take into account that CDs leave the LSP’s platform with a higher likelihood if they are matched to a lower number of requests, we observe a lower effective CD supply, which leads to a higher amount of required SDs.

1.3. Structure

We structure the remainder of this work as follows. In Section 2, we introduce our problem setting, describing decisions and events on the strategic level and the dynamics of the operational level. In Section 3, we formalize the strategic level as an MDP and introduce a closed queueing network to model the operational level. Moreover, we introduce our PL-VFA for finding the optimal number of SDs and derive a fluid approximation for our operational planning problem. We detail the design of experiments for our numerical study in Section 4 and discuss results in Section 5. We conclude this article with a short synthesis in Section 6.

2. Problem Setting

In the following, we introduce our problem setting. First, we provide a high-level descriptive overview in Section 2.1, before we formalize and detail the problem dynamics and objectives in Section 2.2.

Figure 2.

Sequence of events and decisions in time step $t$ .

2.1. Descriptive Overview

In this article, we focus on an LSP providing on-demand delivery services in an urban area $\mathcal{M}$ by operating a mixed fleet of SDs, DDs, and ODs. We decompose the problem setting into two nested levels. First, on a strategic level, we consider the LSP’s problem of composing its mixed delivery fleet by hiring and firing SDs, and by observing the outcomes of stochastic CD joining and resignation processes. We define the strategic level problem on time horizon $\mathcal{T}$ spanning multiple months to a couple of years, wherein the time steps represent, for example, weeks. Second, we consider an operational level, which is embedded within one time step of the strategic level problem. Herein, we treat the LSP’s problem of leveraging their mixed fleet to serve on-demand requests arising stochastically in different regions within $\mathcal{M}$ . The LSP can either dispatch its SDs or outsource requests to CDs. Moreover, the LSP can relocate idling SDs to more promising regions. We define the operational level problem on time horizon $\overline{\mathcal{T}}$ which can consist of multiple sub-horizons representing different time intervals of interest, for example, morning or afternoon time windows. Each of the sub-horizons can be discretized, for example, into minutes or hours. We visualize the dependency between the different temporal entities and their corresponding structure in Figure 1. We assume that SDs who were hired and CDs who joined in one time step $t\in \mathcal{T}$ are available throughout the respective $\overline{\mathcal{T}}$ . While SDs are hired as fixed employees, CDs register on the LSP’s crowdsourced delivery platform, for example, via an app, through which they receive notifications about potential delivery requests. They can de-register from the platform in any time step $t\in \mathcal{T}$ . Thus, the LSP neither controls the CDs’ joining nor their resignation processes. The LSP’s objective is total cost minimization. On the operational level, costs consist of the variable SD dispatching and relocation costs, of the payments to CDs, and of penalties for undelivered requests. We base payments to DDs on the delivery distance. Such distance-based compensation schemes are similar to compensation schemes employed by on-demand delivery companies, for example, GrubHub. In line with existing works, we assume that the ODs’ compensation is independent of the request distance (cf. Archetti et al., 2016). Such a compensation implies that ODs accept requests up to a certain detour, which depends on their value of time and the offered constant compensation. On the strategic level, we account for the fixed personnel costs of SDs and the severance payments for firing SDs. In the next section, we provide a detailed mathematical formalization of the problem setting.

2.2. Mathematical Formalization

We start by describing the sequence of events and decisions during one time step $t\in \mathcal{T}$ of the strategic level, see Figure 2. Let $n_t^{\mathrm{SD}}$ , $n_t^{\mathrm{DD}}$ , and $n_t^{\mathrm{OD}}$ describe the number of SDs, DDs, and ODs, respectively, available to the LSP in time step $t\in \mathcal{T}$ . Firstly, the LSP decides on the net number $a_t$ of newly hired ( $a_t>0$ ) or laid-off SDs $(a_t<0)$ . Secondly, the LSP serves requests on the operational level by matching them to SDs and CDs and by relocating SDs to ensure high service levels. Thirdly, at the end of time step $t$ , some SDs and CDs resign, while some new CDs decide to join the LSP’s platform. Let ${\tilde{x}}^{\alpha }$ denote the random variable describing the number of drivers resigning at the end of $t$ with $\alpha \in \{\mathrm{SD},\mathrm{DD},\mathrm{OD}\}$ . We let ${\tilde{x}}^{\alpha }$ follow a probability distribution ${\mathcal{X}}^{\alpha }$ , which we will detail in Section 4. Analogously, we model the number of newly joining CDs, ${\tilde{y}}^{\alpha }$ , to follow a probability distribution ${\mathcal{Y}}^{\alpha }$ . We assume the distributions ${\mathcal{X}}^{\alpha }$ and ${\mathcal{Y}}^{\alpha }$ to be independent. This is plausible since they represent different types of workforce exhibiting distinct behaviors and motivations to work for the LSP. The evolution of the number of drivers available to the LSP, from one time step $t$ to $t+1$ , then reads

$$\begin{array}{rl}{n}_{t+1}^{\mathrm{SD}}& =n_t^{\mathrm{SD}}+a_t-{\tilde{x}}^{\mathrm{SD}};n_{t+1}^{\mathrm{DD}}=n_t^{\mathrm{DD}}+{\tilde{y}}^{\mathrm{DD}}-{\tilde{x}}^{\mathrm{DD}};\\ n_{t+1}^{\mathrm{OD}}& =n_t^{\mathrm{OD}}+{\tilde{y}}^{\mathrm{OD}}-{\tilde{x}}^{\mathrm{OD}}.\end{array}$$

(2.1)

Now we describe the costs that the LSP incurs at each time step $t$ . Let the constant $C^{\mathrm{fix}}$ denote the wage per SD and time step $t$ . Moreover, let $C^{\mathrm{sev}}$ denote the severance payment per laid-off SD and time step $t$ . Finally, let the function $C_t^{\mathrm{ops}}(n_t^{\mathrm{SD}},n_t^{\mathrm{DD}},n_t^{\mathrm{OD}},{\mathcal{R}}^t)$ denote costs from serving requests on the operational level. Here, ${\mathcal{R}}^t$ represents the demand to be served. We assume a deterministic demand curve over the strategic time horizon $\mathcal{T}$ and no shortages in SD supply. Thus, the LSP can hire enough SDs to cover the entire demand in each time step $t$ .

To obtain $C_t^{\mathrm{ops}}(n_t^{\mathrm{SD}},n_t^{\mathrm{DD}},n_t^{\mathrm{OD}},{\mathcal{R}}^t)$ , we now describe the operational level problem in detail. Requests arise dynamically in some region $i\in \mathcal{M}$ and need to be delivered instantaneously to region $j\in \mathcal{M}$ . We model request arrivals in region $i$ with a Poisson process with arrival rates ${\lambda }_{it}^{\mathrm{R}}\in {\mathcal{R}}^t$ . We describe requests’ destinations by a request origin-destination matrix $P_{ij}^R$ . Requests not being served in time step $\overline{t}\in \overline{\mathcal{T}}$ disappear from the system and result in a penalty. Likewise, we let CD arrivals follow a Poisson process. We link arrival rates at regions $i$ , denoted by ${\lambda }_{it}^{\mathrm{DD}}$ and ${\lambda }_{it}^{\mathrm{OD}}$ , to the number of CDs currently active on the LSP’s platform, to ${\zeta }^{\alpha }$ , and to demand and area specific availability patterns $I_i^{\mathrm{DD}}$ and $I_i^{\mathrm{OD}}$ for DDs and ODs, respectively. Area specific availability patterns describe the share of CD arrivals in region $i$ , that is, $I_i^{\alpha }=\frac{\text{Arrivals of CDs of type }\alpha \text{ in }i\text{ for }{\overline{\mathcal{T}}}_k}{\text{All arrivals of CDs of type }\alpha \text{ in area }\mathcal{M}\text{ for }{\overline{\mathcal{T}}}_k}$ . The constants ${\zeta }^{\alpha }$ quantify the CDs’ share of available drivers of type $\alpha$ within ${\overline{\mathcal{T}}}_k$ compared to the total number of drivers of type $\alpha$ , that is, ${\zeta }^{\alpha }=\frac{\text{Available CDs of type }\alpha \text{ within }\overline{{\mathcal{T}}_k}}{\text{Total no. of CDs of type }\alpha }$ . The arrival rates, therefore, result to

$${\lambda }_{it}^{\mathrm{DD}}=n_t^{\mathrm{DD}}{\zeta }^{\mathrm{DD}}{I}_i^{\mathrm{DD}},{\lambda }_{it}^{\mathrm{OD}}=n_t^{\mathrm{OD}}{\zeta }^{\mathrm{OD}}{I}_i^{\mathrm{OD}},$$

(2.2)

where ${\zeta }^{\alpha }$ and $I_i^{\alpha }$ depend on the problem instances. While ODs only accept requests whose origins coincide with the origin of their individually planned routes, DDs seek regions with high request density to maximize earnings. Hence, we consider $I_i^{\mathrm{DD}}=\frac{{\lambda }_{it}^{\mathrm{R}}}{\sum _j^{|\mathcal{M}|}{\lambda }_{jt}^{\mathrm{R}}}$ . Contrarily, ODs’ availability patterns differ from request patterns as detailed in Section 4. Moreover, we denote request, DD, and OD route patterns by $P_{ij}^{\mathrm{R}}$ , $P_{ij}^{\mathrm{DD}}$ , and $P_{ij}^{\mathrm{OD}}$ respectively. Route patterns describe the share of requests, DDs, and ODs starting in $i\in \mathcal{M}$ and heading towards $j\in \mathcal{M}$ . Analogously to availability patterns, we assume $P_{ij}^{\mathrm{R}}=P_{ij}^{\mathrm{DD}}$ , and $P_{ij}^{\mathrm{OD}}$ being independent of request patterns, as detailed in Section 4. We assume that requests and CDs who are not matched to a driver or request within $\overline{t}$ leave the system. This assumption aligns with the on-demand delivery context we study, wherein requests need to be delivered instantaneously, for example, because they consist of perishable goods. The penalty cost $c_{ij}^{\mathrm{\varnothing }}$ accounts for both opportunity costs and actual costs of paying an expensive third-party courier to perform the delivery. The assumption regarding CDs is sensible as CDs find better outside options if not being matched because they often register at different delivery platforms simultaneously (Wired, 2018).

We denote the costs of serving a request with delivery option $\beta$ by $c_{ij}^{\beta }$ and the penalty costs for not serving a request by $c_{ij}^{\mathrm{\varnothing }}$ . We assume that $c_{ij}^{\mathrm{SD}}<c_{ij}^{\mathrm{DD}}$ and $c_{ij}^{\mathrm{SD}}<c_{ij}^{\mathrm{OD}}$ . This is plausible since SD’s variable costs only include mileage costs, whereas CD’s variable costs need to cover mileage costs and a profit margin which motivates them to serve the request. We model the DDs’ compensation to depend on the distance between a request’s origin and the request’s destination. Hence, $c_{ij}^{\mathrm{DD}}=c_{\mathrm{var}}^{\mathrm{DD}}{r}_{ij}$ , where $r_{ij}$ is the origin-destination matrix, and $i$ and $j$ are the origin and destination of the request. The constant $c_{\mathrm{var}}^{\mathrm{DD}}$ denotes the per distance-unit costs of DDs. As mentioned in Section 2.1, we consider a constant $c_{\mathrm{var}}^{\mathrm{OD}}$ (cf. Archetti et al., 2016). To summarize the behavioral differences between SDs, DDs, and ODs, we highlight their key characteristics across the strategic and operational level in Table 1. Let $R_{ij}(\overline{t})$ denote the number of SDs that the LSP decides to relocate from $i$ to $j$ in time step $\overline{t}$ , and let $A_{ij}^{\beta }(\overline{t})$ be the number of requests the LSP decides to match to delivery option $\beta \in \{\mathrm{SD},\mathrm{DD},\mathrm{OD},\mathrm{\varnothing }\}$ , with $A_{ij}^{\mathrm{\varnothing }}(\overline{t})$ being the number of requests not matched to any driver. The expected operational costs in $t$ then read

$$\begin{array}{rl}& C_t^{\mathrm{ops}}(n_t^{\mathrm{SD}}+a_t,n_t^{\mathrm{DD}},n_t^{\mathrm{OD}},{\mathcal{R}}^t)\\ & =\sum _k\left(\underset{R_{ij}^k,A_{ij}^{\mathrm{SD},\mathrm{k}}}{\min }\mathbb{E}\left[\sum _{\overline{t}\in {\overline{\mathcal{T}}}_k}\left[\sum _{ij}(\sum _{\beta }[c_{ij}^{\beta }{A}_{ij}^{\beta ,k}(\overline{t})]+c_{ij}^{\mathrm{SD}}{R}_{ij}^k(\overline{t}))\right]\right]\right).\end{array}$$

(2.3)

In the remainder of this article, we assume that $\overline{\mathcal{T}}$ consists of $K$ sub-horizons ${\overline{\mathcal{T}}}_k$ , each of which represents a periodically occurring time-window, for example, the same afternoon time-window of each day belonging to the strategic level time step. We assume that arrival patterns for requests and CDs follow the same distribution for each of the periodically occurring ${\overline{\mathcal{T}}}_k$ . This allows us to drop index $k$ , as the operational costs for each of these different ${\overline{\mathcal{T}}}_k$ are approximately the same. Hence, we obtain the total operational costs in $t$ by calculating them once and multiplying them by $K$ . We refer the interested reader to Appendix A in the E-Companion for details on how to adapt our methodology to unequal ${\overline{\mathcal{T}}}_k$ .

Table 1.

Characteristics of SDs, DDs and ODs.

	SDs	DDs	ODs
Fixed costs	$C^{\mathrm{fix}}$ and $C^{\mathrm{sev}}$ per $t$	None
Variable costs	Distance-based	Distance-based	Constant per request
Joining pattern	Deterministic hiring	Stochastic
Resignation pattern	Deterministic firing & stochastic resignation	Stochastic resignations
Availability patterns $I_i^{\beta }$	n/a	$\frac{{\lambda }_{it}^{\mathrm{R}}}{\sum _j^{|\mathcal{M}|}{\lambda }_{jt}^{\mathrm{R}}}$	Independent of ${\lambda }_{it}^{\mathrm{R}}$
Route patterns $P_{ij}^{\beta }$	n/a	$P_{ij}^{\mathrm{DD}}=P_{ij}^{\mathrm{R}}$	Independent of $P_{ij}^{\mathrm{R}}$

SDs = salaried drivers; DDs = dedicated gig-drivers; ODs = opportunistic gig-drivers.

We now describe the set of constraints we need to fulfill in each time step $\overline{t}$ of the operational level’s problem. Let $O_{ij}(\overline{t})$ denote the number of requests occurring in time step $\overline{t}$ for a specific origin-destination pair $(i,j)$ . Furthermore, we denote the number of SDs in the process of relocating from $i$ to $j$ with $E_{ij}(\overline{t})$ , for $i\ne j$ . For $i=j$ , $E_{ij}(\overline{t})$ describes the number of SDs idling in $i$ . Let $F_{ij}(\overline{t})$ describe the number of SDs in the process of currently serving a request from $i$ to $j$ . We denote by $E_{ij}^{\prime }(\overline{t})$ and $F_{ij}^{\prime }(\overline{t})$ the number of SDs completing their relocation and request delivery respectively. Finally, let $X_{ij}^{\beta }(\overline{t})$ , $\beta \in \{\mathrm{DD},\mathrm{OD}\}$ , denote the number of CDs available in time step $\overline{t}$ , which we sample based on ${\lambda }_{it}^{\beta }$ and $P_{ij}^{\beta }$ as defined above. The operational costs and the respective constraints for each $\overline{t}$ then read

$$\begin{array}{rlr}{C}_t^{\mathrm{ops}}& =K\left(\underset{R_{ij},A_{ij}^{\mathrm{SD}}}{\min }\mathbb{E}\left[\sum _{\overline{t}\in \overline{\mathcal{T}}}\left[\sum _{ij}(\sum _{\beta }[c_{ij}^{\beta }{A}_{ij}^{\beta }(\overline{t})]+c_{ij}^{\mathrm{SD}}{R}_{ij}(\overline{t}))\right]\right]\right)& \end{array}$$

(2.4a)

$$\begin{array}{rlr}\mathrm{s}.\mathrm{t}.& F_{ij}(\overline{t}-1)+A_{ij}^{\mathrm{SD}}(\overline{t})-F_{ij}^{\prime }(\overline{t})=F_{ij}(\overline{t})& \mathrm{\forall }i,j\in \mathcal{M},\mathrm{\forall }\overline{t}\in \overline{\mathcal{T}},\end{array}$$

(2.4b)

$$\begin{array}{rlr}& A_{ij}^{\beta }(\overline{t})\le X_{ij}^{\beta }(\overline{t})& \mathrm{\forall }i,j\in \mathcal{M},\beta \in \{\mathrm{DD},\mathrm{OD}\},\mathrm{\forall }\overline{t}\in \overline{\mathcal{T}},\end{array}$$

(2.4c)

$$\begin{array}{rlr}& E_{ij}(\overline{t}-1)+R_{ij}(\overline{t})-E_{ij}^{\prime }(\overline{t})=E_{ij}(\overline{t})& \mathrm{\forall }i,j,\in \mathcal{M},i\ne j,\mathrm{\forall }\overline{t}\in \overline{\mathcal{T}},\end{array}$$

(2.4d)

$$\begin{array}{rlr}& E_{ii}(\overline{t}-1)+\sum _{j,j\ne i}{E}_{j{i}^{\mathrm{\prime }}}(\overline{t})+\sum _j{F}_{j{i}^{\mathrm{\prime }}}(\overline{t})-\left(\sum _{j,j\ne i}{R}_{ij}(\overline{t})+\sum _j{A}_{ij}^{\mathrm{SD}}(\overline{t})\right)=E_{ii}(\overline{t})& \mathrm{\forall }i\in \mathcal{M},\mathrm{\forall }\overline{t}\in \overline{\mathcal{T}},\end{array}$$

(2.4e)

$$\begin{array}{rlr}& \sum _{\beta }{A}_{ij}^{\beta }(\overline{t})=O_{ij}(\overline{t})& \mathrm{\forall }i,j\in \mathcal{M},\mathrm{\forall }\overline{t}\in \overline{\mathcal{T}},\end{array}$$

(2.4f)

$$\begin{array}{rlr}& R_{ij}(\overline{t})\ge 0,R_{ii}(\overline{t})=0,A_{ij}^{\beta }(\overline{t})\ge 0& \mathrm{\forall }i,j\in \mathcal{M},\beta \in \{\text{SD},\text{DD},\text{OD},\mathrm{\varnothing }\},\mathrm{\forall }\overline{t}\in \overline{\mathcal{T}},\end{array}$$

(2.4g)

$$\begin{array}{rlr}& \sum _{ij}(E_{ij}(\overline{t})+F_{ij}(\overline{t}))=n_t^{\mathrm{SD}}& \mathrm{\forall }\overline{t}\in \overline{\mathcal{T}}.\end{array}$$

(2.4h)

Constraints (2.4b) ensure that $F_{ij}(\overline{t})$ corresponds to the number of SDs in the last time step plus the number of SDs starting a delivery from $i$ to $j$ minus the number of SDs completing their delivery. Constraints (2.4c) guarantee that the number of requests matched to CDs does not surpass the number of CDs available in time step $\overline{t}$ . Constraints (2.4d) ensure the same conditions for $E_{ij}(\overline{t})$ as Constraints (2.4b) do for $F_{ij}(\overline{t})$ . Constraints (2.4e) guarantee that the number of idling SDs equals the sum of SDs arriving in $i$ as they complete their relocation or their request delivery minus the sum of SDs leaving $i$ as they are relocated or matched to a request. Finally, Constraints (2.4f), (2.4g), and (2.4h), respectively, ensure that all requests are matched to one delivery option, the positivity of $R_{ij}(\overline{t})$ and $A_{ij}^{\beta }(\overline{t})$ , and that all drivers are considered. We note that we do not consider relocations from $i$ to $i$ , ensured by $R_{ii}(\overline{t})=0$ (cf. Constraints (2.4g)), as this does not yield any benefit to the LSP.

Let us for now assume that we obtain some approximation for $C_t^{\mathrm{ops}}(n_t^{\mathrm{SD}}+a_t,n_t^{\mathrm{DD}},n_t^{\mathrm{OD}},{\mathcal{R}}^t)$ . Then, total costs $C_t^{\mathrm{tot}}$ in time step $t$ result to

$$\begin{array}{rl}& C_t^{\mathrm{tot}}(n_t^{\mathrm{SD}}+a_t,n_t^{\mathrm{DD}},n_t^{\mathrm{OD}},{\mathcal{R}}^t)=C_t^{\mathrm{ops}}(n_t^{\mathrm{SD}}+a_t,n_t^{\mathrm{DD}},n_t^{\mathrm{OD}},{\mathcal{R}}^t)\\ & +(C^{\mathrm{fix}}\cdot (n_t^{\mathrm{SD}}+a_t)+C^{\mathrm{sev}}|\min (0,a_t)|).\end{array}$$

(2.5)

The LSP aims at minimizing its expected total costs over the time horizon $\mathcal{T}$ . Due to the stochastic nature of the problem, this objective formally results to

$$\begin{array}{rl}& \min \mathbb{E}\left[\sum _{t=0}^{|\mathcal{T}|}{C}_t^{\mathrm{tot}}\right]=\min \mathbb{E}[\sum _{t=0}^{|\mathcal{T}|}(C_t^{\mathrm{ops}}(n_t^{\mathrm{SD}}+a_t,\cdot )\\ & +(C^{\mathrm{fix}}(n_t^{\mathrm{SD}}+a_t)+C^{\mathrm{sev}}|\min (0,a_t)|))\phantom{\left[\sum _{t=0}^{|\mathcal{T}|}{C}_t^{\mathrm{tot}}\right]=\min \mathbb{E}[\sum _{t=0}^{|\mathcal{T}|}(C_t^{\mathrm{ops}}(n_t^{\mathrm{SD}}+a_t,\cdot )}].\end{array}$$

(2.6)

Some comments on our modeling choices and assumptions are in order. First, we do not account for uncertainty in the parameters governing the evolution of future demand levels, that is, the set of Poisson rates ${\mathcal{R}}^t$ in each time step $t$ of the strategic level’s problem, as we want to exclusively analyze the effect of uncertain CD supply. Therefore, we assume that robust forecasts concerning these parameters can be carried out on the strategic level’s planning horizon. This is plausible because LSPs indirectly control future demand levels and distributions through the contracts they set up with demand sources, for example, restaurants or supermarkets, before the strategic level’s planning horizon starts.

Second, we assume that there are no SD supply shortages, as we restrict our problem to urban areas that typically have an abundant workforce supply, especially in the gig economy sector.

Third, severance payments implicitly prescribe the minimum duration for which the LSP must hire SDs. If $C^{\mathrm{fix}}(T-t)<C^{\mathrm{sev}}$ , the LSP will not fire SDs as it is cheaper to pay them until the end of the time horizon. This allows us to model both short-term (low $C^{\mathrm{sev}}$ ) and long-term (high $C^{\mathrm{sev}}$ ) hiring decisions. We note that in real-world applications short-term hiring decisions are typically achieved by issuing short-term contracts, which do not require paying a severance fee when the contract expires and the LSP does not extend it.

Finally, we consider a finite time horizon on the strategic level since LSPs’ strategic workforce planning process relies on finite horizons, for which they can leverage a robust forecast. This is in line with works in the strategic workforce planning literature (cf. Gans and Zhou, 2002).

3. Methodology

This section formalizes the problem setting presented in Section 2. We model the strategic level’s problem as an MDP (Section 3.1) and the operational level’s problem as a closed queueing network (Section 3.2). Finally, we present an approximate dynamic programming approach to solve large instance sizes in Section 3.3.

3.1. Strategic Level Workforce Planning

In this section, we formalize the LSP’s workforce planning problem, outlined in Section 2, as an MDP. In the following, we will successively describe the state, the feasible actions, the state transition, the policy, and the objective function.

Pre-decision state: We denote pre-decision states that represent the fleet composition in time step $t$ by $s_t=(n_t^{\mathrm{SD}},n_t^{\mathrm{DD}},n_t^{\mathrm{OD}})\in {\mathbb{N}}_0^3$ with $s\in \mathcal{S}=\{0,\dots ,N^{\mathrm{SD}}\}\times \{0,\dots ,N^{\mathrm{DD}}\}\times \{0,\dots ,N^{\mathrm{OD}}\}\times \{0,\dots ,T\}$ , where $\mathcal{S}$ denotes the state space. Pre-decision states describe the fleet composition at the beginning of time step $t$ before making any decisions. Variables $N^{\mathrm{SD}}$ , $N^{\mathrm{DD}}$ , and $N^{\mathrm{OD}}$ represent the maximum number of drivers attainable for each driver type, for example, the maximum number of individuals with the intention to work for the LSP within urban area $\mathcal{M}$ . Similarly, we denote the state space in time step $t$ by ${\mathcal{S}}_t=\{0,\dots ,N^{\mathrm{SD}}\}\times \{0,\dots ,N^{\mathrm{DD}}\}\times \{0,\dots ,N^{\mathrm{OD}}\}$ .

Feasible actions and post-decision state: The LSP decides on the number of SDs to hire or fire. The action space ${\mathcal{A}}_t=\{-n_t^{\mathrm{SD}},\dots ,N^{\mathrm{SD}}\}\in \mathbb{Z}$ describes the possible hiring decisions that the LSP can make. The maximum number of SDs that can be fired depends on the current time step, as the LSP cannot fire more SDs than currently employed. When the LSP decides on an action $a_t\in {\mathcal{A}}_t$ , we reach the post-decision state $s_t^a=(n_t^{\mathrm{SD}}+a_t,n_t^{\mathrm{DD}},n_t^{\mathrm{OD}})$ and evaluate the operational problem to approximate the operational costs $C_t^{\mathrm{ops}}(s_t^a,{\mathcal{R}}^t)$ .

State transition: We transition to the next time step by following a resignation process for all drivers and a joining process for CDs, described by equation (2.1). Let $P(s_{t+1}|s_t^a)\in [0,1{]}^{|\mathcal{S}|\times |\mathcal{S}|}$ denote the transition probability matrix, describing the probability of transitioning to state $s_{t+1}$ when being in state $s_t^a$ . Accordingly, as the distributions ${\mathcal{X}}^{\alpha }$ and ${\mathcal{Y}}^{\alpha }$ are assumed to be independent, each entry of $P$ reads

$$\begin{array}{rl}P(s_{t+1}|s_t^a)& =\mathbb{P}({\tilde{x}}_t^{\mathrm{SD}}|s_t^a)\cdot \mathbb{P}({\tilde{x}}_t^{\mathrm{DD}}|s_t^a)\cdot \mathbb{P}({\tilde{x}}_t^{\mathrm{OD}}|s_t^a)\cdot \mathbb{P}({\tilde{y}}_t^{\mathrm{DD}}|s_t^a)\\ & \cdot \mathbb{P}({\tilde{y}}_t^{\mathrm{OD}}|s_t^a).\end{array}$$

(3.1)

Policy: We denote a deterministic state-dependent hiring and firing policy by $\pi :\mathcal{S}\to \mathcal{A}$ . It assigns an action $a_t\in \mathcal{A}(s_t)$ to each pre-decision state $s_t\in {\mathcal{S}}_t$ . Moreover, we denote the set of all possible policies by $\mathrm{\Pi }$ .

Objective: Starting in an initial state $s_0$ , the LSP’s objective is to minimize expected future total costs over the time horizon $\mathcal{T}$ , formally

$$\begin{array}{rl}{V}_0(s_0)& =\underset{\pi \in \mathrm{\Pi }}{\min }\mathbb{E}[\sum _{t=0}^T{\gamma }^t\cdot (C_t^{\mathrm{ops}}(n_t^{\mathrm{SD}}+a_t,\cdot )\\ & +K(C^{\mathrm{fix}}(n_t^{\mathrm{SD}}+a_t)+C^{\mathrm{sev}}|\min (0,a_t)|))|s_0\phantom{[\sum _{t=0}^T{\gamma }^t\cdot (C_t^{\mathrm{ops}}(n_t^{\mathrm{SD}}+a_t,\cdot )}],\end{array}$$

(3.2)

wherein $\gamma$ denotes the discount factor. Equation (3.2) formalizes the LSP’s objective (cf. equation (2.6)) as finding the hiring/firing policy $\pi$ minimizing the sum of discounted costs over the planning horizon $\mathcal{T}$ . The following section introduces the model for determining operational costs $C_t^{\mathrm{ops}}$ .

3.2. Formalization of the Operational Level’s Problem

Given the necessity to solve the operational level’s problem in each time step of the strategic level, an efficient approximation is essential to preserve computational tractability. Current research on mobility on demand (MoD), similar to the on-demand last-mile delivery problem examined in our study, show that greedy matching heuristics are only marginally surpassed by lookahead policies based on methods such as model predictive control or deep reinforcement learning (Enders et al., 2023). Therefore, we rely on greedy driver-to-request matching and use a forward-looking SD relocation policy. This approach allows us to employ a fluid approximation model for the operational costs as suggested by Braverman et al. (2019). First, we formalize the operational level’s problem as a closed queueing network. We base our formulation of the queueing network on the model from Zhang and Pavone (2016). Herein, we assume that requests can only be served by drivers in the same region as the request’s origin. This is plausible if the discretization of the area $\mathcal{M}$ results in large regions, such that drivers outside of the region cannot reach the request in time. Moreover, we assume that the model is agnostic to the varying distance between different drivers within the region and a request’s origin. Hence, the greedy matching policy results into matching requests to the cheapest available driver located in the region. We describe the number of SDs idling in region $i$ with $|\mathcal{M}|$ single server queues, denoted by $E_{ii}(\overline{t})$ , as we have $|\mathcal{M}|$ regions. Each $E_{ii}(\overline{t})$ has a service rate ${\lambda }_{it}^{\mathrm{R}}$ . We describe the number of SDs relocating from $i$ to $j$ with $|\mathcal{M}{|}^2-|\mathcal{M}|$ infinite server queues $E_{ij}(\overline{t})$ , each having a service rate ${\mu }_{ij}$ . Finally, we describe the number of SDs serving a request from $i$ to $j$ with $|\mathcal{M}{|}^2$ infinite server queues, denoted by $F_{ij}(\overline{t})$ , also having a service rate ${\mu }_{ij}$ , as we assume that drivers relocate with the same speed as they deliver a request. Here, $1/{\mu }_{ij}$ denotes the travel time matrix.

We now introduce the fluid approximation of the presented closed queueing network as proposed by Braverman et al. (2019). Herein, we consider steady-state conditions, that is, $\overline{t}\to \mathrm{\infty }$ . This holds approximately in on-demand delivery services in urban areas if the operational planning horizon is sufficiently small, for example, 60 min.

The fluid approximation reformulates the closed-queueing system as a network flow problem, whose counterparts to the closed-queueing system’s queue lengths $E_{ij}$ and $F_{ij}$ are network flows from region $i$ to $j$ . We denote these network flows by $e_{ij}$ and $f_{ij}$ . They correspond to single and infinite server queues in steady-state conditions, respectively, and read

$$e_{ij}=\frac{E_{ij}(\overline{t}\to \mathrm{\infty })}{n_t^{\mathrm{SD}}};f_{ij}=\frac{F_{ij}(\overline{t}\to \mathrm{\infty })}{n_t^{\mathrm{SD}}}.$$

(3.3)

Moreover, we denote by $a_i^{\mathrm{SD}}$ the fraction of requests in region $i$ matched to SDs in region $i$ in steady-state conditions. Analogously, let us denote by $a_{ij}^{\mathrm{DD}}$ and $a_{ij}^{\mathrm{OD}}$ , the corresponding fractions of requests matched to DDs and ODs, respectively, on routes $i,j$ . Consider the following linear program (LP), whose full derivation we detail in Appendix B in the E-Companion. It represents the network flow problem whose objective value is the operational cost over time horizon $\overline{\mathcal{T}}$

$$\begin{array}{rl}& C_t^{\mathrm{ops}}=K\underset{e,f,a}{\min }\sum _{i\in \mathcal{M}}\sum _{j\in \mathcal{M}}[{\lambda }_{it}^{\mathrm{R}}(\sum _{\beta \in \{\mathrm{DD},\mathrm{OD},\mathrm{\varnothing }\}}(c_{ij}^{\beta }\cdot a_{ij}^{\beta })+c_{ij}^{\mathrm{SD}}\cdot P_{ij}^{\mathrm{R}}\cdot a_i^{\mathrm{SD}})+(1-{\delta }_{ij})c_{ij}^{\mathrm{SD}}{n}_t^{\mathrm{SD}}{e}_{ij}]\end{array}$$

(3.4a)

$$\begin{array}{rl}& ({\lambda }_{it}^{\mathrm{R}}/n_t^{\mathrm{SD}})\cdot a_i^{\mathrm{SD}}\cdot P_{ij}^{\mathrm{R}}={\mu }_{ij}\cdot f_{ij}\mathrm{\forall }i,j\in \mathcal{M},\end{array}$$

(3.4b)

$$\begin{array}{rl}& {\lambda }_{it}^{\mathrm{R}}\cdot a_{ij}^{\mathrm{DD}}\le {\lambda }_{it}^{\mathrm{DD}}{P}_{ij}^{\mathrm{DD}}\mathrm{\forall }i,j\in \mathcal{M},\end{array}$$

(3.4c)

$$\begin{array}{rl}& {\lambda }_{it}^{\mathrm{R}}\cdot a_{ij}^{\mathrm{OD}}\le {\lambda }_{it}^{\mathrm{OD}}{P}_{ij}^{\mathrm{OD}}\mathrm{\forall }i,j\in \mathcal{M},\end{array}$$

(3.4d)

$$\begin{array}{rl}& {\mu }_{ij}{e}_{ij}\le \sum _k{\mu }_{ki}{f}_{ki},i\ne j\mathrm{\forall }i,j\in \mathcal{M},\end{array}$$

(3.4e)

$$\begin{array}{rl}& \sum _{k,k\ne i}{\mu }_{ki}{e}_{ki}\le ({\lambda }_{it}^{\mathrm{R}}/n_t^{\mathrm{SD}})a_i^{\mathrm{SD}}\le \sum _{k,k\ne i}{\mu }_{ki}{e}_{ki}+\sum _k{\mu }_{ki}{f}_{ki}\mathrm{\forall }i\in \mathcal{M},\end{array}$$

(3.4f)

$$\begin{array}{rl}& ({\lambda }_{it}^{\mathrm{R}}/n_t^{\mathrm{SD}})a_i^{\mathrm{SD}}+\sum _{j,j\ne i}{\mu }_{ij}{e}_{ij}=\sum _{k,k\ne i}{\mu }_{ki}{e}_{ki}+\sum _k{\mu }_{ki}{f}_{ki}\mathrm{\forall }i\in \mathcal{M},\end{array}$$

(3.4g)

$$\begin{array}{rl}& a_i^{\mathrm{SD}}+\sum _j(a_{ij}^{\mathrm{DD}}+a_{ij}^{\mathrm{OD}}+a_{ij}^{\mathrm{\varnothing }})=1\mathrm{\forall }i\in \mathcal{M},\end{array}$$

(3.4h)

$$\begin{array}{rl}& 0\le a_i^{\mathrm{SD}}\le 1\mathrm{\forall }i,j\in \mathcal{M},\end{array}$$

(3.4i)

$$\begin{array}{rl}& 0\le a_{ij}^{\mathrm{DD}}\le P_{ij}^{\mathrm{R}};0\le a_{ij}^{\mathrm{OD}}\le P_{ij}^{\mathrm{R}}\mathrm{\forall }i,j\in \mathcal{M},\end{array}$$

(3.4j)

$$\begin{array}{rl}& 0\le a_{ij}^{\mathrm{\varnothing }}\le 1\mathrm{\forall }i,j\in \mathcal{M},\end{array}$$

(3.4k)

$$\begin{array}{rl}& 0\le e_{ij}\le 1,0\le f_{ij}\le 1,\sum _i\sum _j{e}_{ij}+f_{ij}=1\mathrm{\forall }i,j\in \mathcal{M}.\end{array}$$

(3.4l)

Objective (3.4a) describes the minimization of operational costs based on costs from serving requests and the empty routing costs, with ${\delta }_{ij}=\{\begin{array}{l}0,\text{if }i\ne j,\\ 1,\text{if }i=j.\end{array}$ being an indicator function. Constraints (3.4b) to (3.4d) ensure flow conservation. Constraints (3.4e) to (3.4g) result from a linear relaxation. Constraints (3.4e) reflect the relaxed Little’s law, which states that the outgoing flow of relocating SDs in one direction $j$ at one region $i$ cannot be higher than the incoming flow of SDs that serve requests. Constraints (3.4f) and (3.4g) ensure that the total SD flow leaving region $i$ is equal to the total SD flow entering region $i$ . Constraints (3.4h) ensure that a request is either matched or not matched in every region $i$ . Constraints (3.4i) to (3.4k) ensure that no more requests are matched to the corresponding delivery option than possible. Finally, Constraints (3.4l) ensure that the sum of SD flows sums up to 1. We can readily compute the optimal solution to this LP with commercially available solvers.

Proposition 1

The optimal objective of the LP described by equations (3.4a) to (3.4l) is a lower bound on the operational costs, as $n_t^{\mathrm{SD}}\to \mathrm{\infty }$ and ${\lambda }_{it}^R(t)\to \mathrm{\infty }$ .

Proof: See Appendix B in the E-Companion.

We use the solution of the LP 3.4 to approximate the operational costs obtained in $\overline{\mathcal{T}}$ .

3.3. Dynamic Programming on the Strategic Level

In this section, we present a stochastic dynamic programming approach to solve the workforce planning problem on the strategic level. Section 3.3.1 shortly discusses a standard backward dynamic programming (BDP) procedure to find the optimal policy $\pi$ . As this approach becomes intractable for large fleet sizes, we present a PL-VFA in Section 3.3.2, to compute a near-optimal $\pi$ .

Figure 3.

Piecewise linear approximation along the salaried driver (SD) dimension for a fixed $W_t$ .

3.3.1. Exact Approach: Backward Dynamic Programming

We start by describing a BDP approach, which allows us to determine the optimal workforce planning policy $\pi$ . Herein, we consider a deterministic policy $\pi$ and recall that the value function $V_t$ of being in pre-decision state $s_t$ reads

$$\begin{array}{rl}{V}_t(s_t)& =\underset{\pi \in \mathrm{\Pi }}{\min }\mathbb{E}[\sum _{t^{\prime }=t}^T{\gamma }^{t^{\prime }-t}\cdot C_{t^{\prime }}^{\mathrm{tot}}|s_t]\\ & =\underset{a_t}{\min }(C_t^{\mathrm{tot}}(s_t^a,{\mathcal{R}}^t)+\gamma \mathbb{E}[V_{t+1}(s_{t+1})|s_t^a]),\end{array}$$

(3.5)

where the value of being in state $s_{t+1}$ is defined as follows:

$$V_{t+1}(s_{t+1})=\underset{\pi \in \mathrm{\Pi }}{\min }\mathbb{E}[\sum _{t^{\prime }=t+1}^T{\gamma }^{t^{\prime }-t-1}\cdot C_{t^{\prime }}^{\mathrm{tot}}|s_{t+1}].$$

(3.6)

Using the transition probabilities as defined in equation (3.1) we can rewrite equation (3.5) as

$$\begin{array}{r}{V}_t(s_t)=\underset{a_t}{\min }(C_t^{\mathrm{tot}}(s_t^a,{\mathcal{R}}^t)+\gamma \sum _{s_{t+1}}P(s_{t+1}|s_t^a)V_{t+1}(s_{t+1}|s_t^a)).\end{array}$$

(3.7)

Since the strategic level’s time horizon $\mathcal{T}$ is finite, we can apply BDP, as described in Appendix C in the E-Companion. For LSPs operating with fleets of more than $1,000$ drivers per type, BDP would require to solve the operational problem more than one billion times per time step and becomes intractable. Accordingly, we develop an approximate algorithm to solve (3.7) in the following section, which allows us to study larger fleet sizes in reasonable computation times and to consider unbounded state spaces.

3.3.2. Piecewise Linear Value Function Approximation

In this section, we introduce an algorithm that approximates the value of being in post-decision state $s_t^{a_t}$ , represented by $V_t^a(s_t^{a_t})$ . Let us denote the set of all possible CD combinations in $t$ by ${\mathcal{W}}_t$ , and one CD combination in time step $t$ by $w_t=(n_t^{\mathrm{DD}},n_t^{\mathrm{OD}})$ . For each $w_t\in {\mathcal{W}}_t$ , we seek for a piecewise linear approximation of $V_t^a(s_t^{a_t})$ along the SD dimension. To efficiently obtain this approximation, we rely on Propositions 2 and 3, which state that $C_t^{\mathrm{tot}}$ and $V_t^a(s_t^{a_t})$ are piecewise-linear convex in $a_t$ .

Proposition 2

$C_t^{tot}(n_t^{\mathrm{SD}}+a_t,w_t)$ is piecewise-linear and convex in $a_t$ .

Proof: See Appendix D in the E-Companion.

Proposition 3

$V_t^a(n_t^{\mathrm{SD}}+a_t,w_t)$ is piecewise-linear and convex in $a_t$ .

Proof: See Appendix E in the E-Companion.

We denote the number of SDs in the post-decision state by $n_t^{\mathrm{SD},a_t}=n_t^{\mathrm{SD}}+a_t$ . Let $v_t(w_t)$ denote the set of slopes describing $V_t^a(s_t^{a_t})$ along the SD dimension for fixed $w_t$ , and let $v_t(n_t^{\mathrm{SD},a_t},w_t)$ be the slope to the “left” of $n_t^{\mathrm{SD},a_t}$ , as illustrated in Figure 3. The value of the post-decision state $s_t^{a_t}$ , $V_t^a(s_t^{a_t})$ , then reads

$$\begin{array}{r}{V}_t^a(s_t^{a_t})=V_t^a(0,w_t)+\sum _{k=0}^{n_t^{\mathrm{SD}}+a_t}{v}_t(k,w_t).\end{array}$$

(3.8)

From here on, we omit $V_t^a(0,w_t)$ as shifting the value function by a constant does not impact the optimal decision. We obtain the value of being in a pre-decision state as

$$V_t^a(n_t^{\mathrm{SD},a_t},w_t)=\underset{a_t}{\min }(C_t^{\mathrm{tot}}(n_t^{\mathrm{SD},a_t},w_t)+\sum _{k=0}^{n_t^{\mathrm{SD},a_t}}v(k,w_t))$$

(3.9)

and the optimal number of SDs as

$$a_t^{*}=\underset{a_t}{\mathrm{argmin}}(C_t^{\mathrm{tot}}(n_t^{\mathrm{SD},a_t},w_t)+\sum _{k=0}^{n_t^{\mathrm{SD},a_t}}v(k,w_t)).$$

(3.10)

We denote the post-decision states to the left and right of $s_t^a$ by $s_t^{a-}=(n_t^{\mathrm{SD}}+a_t-1,w_t)$ and $s_t^{a+}=(n_t^{\mathrm{SD}}+a_t+1,w_t)$ , respectively, see Figure 3. Moreover, we denote by $s_{t+1}^{-}$ and $s_{t+1}^{+}$ the pre-decision states in $t+1$ , to which we transition from $s_t^{a-}$ and $s_t^{a+}$ respectively. Accordingly, we denote by $n_t^{\mathrm{SD},a-}$ and $n_t^{\mathrm{SD},a+}$ the number of SDs in $s_t^{a-}$ and $s_t^{a+}$ , and by $n_{t+1}^{\mathrm{SD}-}$ and $n_{t+1}^{\mathrm{SD}+}$ the number of SDs in $s_{t+1}^{-}$ and $s_{t+1}^{+}$ . We use the following relations:

$$\begin{array}{rl}{V}_t^a(s_t^{a_t})& =\mathbb{E}[V_{t+1}(s_{t+1})],V_t^a(s_t^{a-})=\mathbb{E}[V_{t+1}(s_{t+1}^{-})],\\ V_t^a(s_t^{a+})& =\mathbb{E}[V_{t+1}(s_{t+1}^{+})],\end{array}$$

to obtain an explicit expression of the slopes to the “left” and “right” of the post-decision state $s_t^{a_t}$

$$\begin{array}{rl}{v}_t(s_t^{a-})& =V_t^a(s_t^{a_t})-V_t^a(s_t^{a-})=\mathbb{E}[V_{t+1}(s_{t+1})]-\mathbb{E}[V_{t+1}(s_{t+1}^{-})],\\ v_t(s_t^{a+})& =V_t^a(s_t^{a+})-V_t^a(s_t^{a_t})=\mathbb{E}[V_{t+1}(s_{t+1}^{+})]-\mathbb{E}[V_{t+1}(s_{t+1})].\end{array}$$

To approximate the slopes of the optimal value function, we adapt an iterative approach initially proposed by Nascimento and Powell (2009). We denote the approximated slopes by $\overline{v}$ . Moreover, we indicate sample information by $(\hat{\cdot })$ . Algorithm 1 shows the procedure for calculating approximated value function slopes. We initialize the approximated slopes with zeros (l. 1). Then, we sample, for each episode, an initial state (l. 3). Subsequently, we walk through the episode and first obtain a decision, $a_t$ , by solving (3.10) (l. 5) and sample the transition to the next state according to our transition function described by the resignation and joining processes of CDs (l. 7).

Then, we observe samples of $s_{t+1}$ (l. 8), $s_{t+1}^{-}$ (l. 9), and $s_{t+1}^{+}$ (l. 10), and use these to calculate $v(s_t^{a-})$ (l. 11) and $v(s_t^{a+})$ (l. 12). We store the current slope approximations in a temporary vector $z$ (l. 13) and obtain a new slope based on a running mean update (l. 14 and 15), where $\alpha$ denotes the learning rate. These updates can lead to temporary convexity violations. We therefore preserve convexity by correcting the slopes to the “left” and “right” of $n_t^{\mathrm{SD},a_t}$ as follows:

$$\mathtt{\text{Conv}}(z(n,w))=\{\begin{array}{l}z(n_t^{\mathrm{SD},a_t},w_t),\mathrm{if}n<n_t^{\mathrm{SD},a_t},\\ w=w_t\mathrm{and}z(n,w)>z(n_t^{\mathrm{SD},a_t},w_t)\\ z(n_t^{\mathrm{SD},a_t}+1,w_t),\mathrm{if}n>n_t^{\mathrm{SD},a_t}+1,\\ w=w_t\mathrm{and}z(n,w)<z(n_t^{\mathrm{SD},a_t}+1,w_t)\\ z(n,w),\mathrm{else}\end{array}$$

(3.11)

Finally, learning the slopes for all $w_t\in {\mathcal{W}}_t$ requires many iterations to ensure that each CD combination $w_t$ is sufficiently sampled. To reduce the number of samples required, we consider a homogeneous aggregation approach, in which we aggregate ${\mathcal{W}}_t$ (cf. Powell, 2011: 144). Let us denote the aggregation factors for the DD and OD dimension by $k^{\mathrm{DD}}$ and $k^{\mathrm{OD}}$ , respectively, and the corresponding aggregated CD fleet sizes by ${\overline{n}}_t^{\mathrm{DD}}=\lfloor \frac{n_t^{\mathrm{DD}}}{k^{\mathrm{DD}}}\rfloor$ and ${\overline{n}}_t^{\mathrm{OD}}=\lfloor \frac{n_t^{\mathrm{OD}}}{k^{\mathrm{OD}}}\rfloor$ , respectively. Moreover, we let ${\overline{w}}_t=({\overline{n}}_t^{\mathrm{DD}},{\overline{n}}_t^{\mathrm{OD}})$ . Then, when considering homogeneous aggregation, the approximation of a slope for some $n_t^{\mathrm{SD},a_t}$ and $w_t$ reads

$$\begin{array}{rl}{\overline{v}}_t(n_t^{\mathrm{SD},a_t},w_t)& ={\overline{v}}_t(n_t^{\mathrm{SD},a_t},n_t^{\mathrm{DD}},n_t^{\mathrm{OD}})\approx {\overline{v}}_t(n_t^{\mathrm{SD},a_t},{\overline{n}}_t^{\mathrm{DD}},{\overline{n}}_t^{\mathrm{OD}})\\ & ={\overline{v}}_t(n_t^{\mathrm{SD},a_t},{\overline{w}}_t).\end{array}$$

(3.12)

We obtain the PL-VFA algorithm with homogeneous aggregation by replacing all $w_t$ by ${\overline{w}}_t$ in Algorithm 1.

4. Design of Experiments

This section describes our experimental setup for a subsequent managerial analysis. In the first part, we present the setup for the operational level’s problem, which bases on a real-world data set describing spatial and temporal order patterns for on-demand food deliveries. In the second part, we discuss the parameter settings on the strategic level and sensitivities to be analyzed.

Figure 4.

Spatial and temporal request patterns in instance 0o100t75s1p100. (a) Origin and destination pairs of orders; (b) no. of orders between $t=0$ and $t=850$ .

4.1. Experimental Setup

To account for a real-world scenario, we consider a data set provided by Grubhub (2018), which describes anonymized food delivery orders. The data set consists of 10 different instances. Each instance represents one US metropolitan area. Each order is characterized by its origin and destination coordinates. Moreover, each order is described by its placement and ready time. The former is when a customer orders through the Grubhub platform, and the latter is when the order is ready to be delivered. To keep the computational complexity of our experimental evaluation manageable, we randomly chose the instance type with initial digits “0o100” and only used the order information contained within them. The “0” encodes the metropolitan area on which the order information bases. The “o100” describes that 100% of orders are used. The remaining digits encode driver schedules, that is, times and locations at which and where drivers start and end their shift. As we do not model driver shifts on the operational level, we ignore the remaining digits. Figure 4 highlights its spatial and temporal order distribution. Orders occur from minute $t=0$ to minute $t=850$ . We use the provided data as base for deriving the origin-destination distance matrix $r_{ij}$ , the order arrival rates per region $i\in \mathcal{M}$ , and the request pattern matrix $P_{ij}^{\mathrm{R}}$ as follows. First, to account for average zip code surfaces, we discretize the area into squares of $4{\mathrm{km}}^2$ (visualized by the gray grid in Figure 4(a)), each representing a region $i\in \mathcal{M}$ . We obtain $r_{ij}$ , for $i\ne j$ , as the Euclidean distance between centers of regions $i$ and $j$ . We assume that $r_{ii}$ corresponds to the half of the square’s side length, which is the average distance between any two points within a square, in this case $1\mathrm{km}$ . This results in 18 regions and consequently in a $18\times 18$ origin-destination matrix. Based on the request distribution and the aggregated regions, we obtain the demand pattern matrix $P_{ij}^{\mathrm{R}}$ and demand arrival rates ${\lambda }_{it}^{\mathrm{R}}$ . We briefly discuss the adequateness of the chosen discretization in Appendix F in the E-Companion. Moreover, since the data set is anonymized, the metropolitan area on which the data bases is unknown. Hence, we sample DD and OD arrivals. We let DD arrivals depend on the arrival patterns of requests, and we set the DD arrival intensity function $I_i^{\mathrm{DD}}$ to $I_i^{DD}=\frac{{\lambda }_{it}^{\mathrm{R}}}{\sum _j{\lambda }_{jt}^{\mathrm{R}}}$ , and obtain ${\lambda }_{it}^{\mathrm{DD}}$ via equation (2.2). This modeling approach reflects the main characteristic of DDs, which financially depend on the work for LSPs and, therefore, try to maximize their earnings by frequenting regions with high demand for deliveries. We randomly generate OD arrivals $I_i^{\mathrm{OD}}$ and mobility patterns $P_{ij}^{\mathrm{OD}}$ . We report CD mobility and request patterns in Appendix G in the E-Companion. We consider an average travel speed of $v^{\mathrm{avg}}=19\mathrm{km}/\mathrm{h}$ as reported in the Grubhub data set for all driver types.

We set the strategic time horizon to a year and divide it into $T=26$ two-week segments. We restrict our study on the operational level to the time window between minutes 550 and 600 (cf. Figure 4(b)) of instance 0o100t75s1p100 in the Grubhub data set, wherein we can assume steady-state conditions.

4.2. Description of Base Case Parameters and Variations

We now present the parameter settings required for the strategic level MDP and the fluid approximation on the operational level. We start by describing a base case and then present parameter variations.

We motivate the base case resignation probability and joining rate by a statistical evaluation initially made for Uber drivers between 2012 and 2016 (Hall and Krueger, 2018). On the strategic level, we consider a constant resignation probability of $p^{\alpha }=0.01$ for the base case. Hence, the number ${\tilde{x}}_t^{\alpha }$ out of $n_t^{\alpha }$ drivers that decide to leave the platform in time step $t$ follows a binomial distribution. Therefore, the probability of ${\tilde{x}}_t^{\alpha }$ leaving, reads

$$\mathbb{P}({\tilde{x}}_t^{\alpha })=(\genfrac{}{}{0ex}{}{n_t^{\alpha }}{{\tilde{x}}_t^{\alpha }}){(p^{\alpha })}^{{\tilde{x}}_t^{\alpha }}{(1-p^{\alpha })}^{n_t^{\alpha }-{\tilde{x}}_t^{\alpha }},\alpha \in \{\mathrm{DD},\mathrm{OD}\}.$$

(4.1)

In Section 5.5, we consider $p^{\alpha }$ to depend on the CDs’ matching sensitivity, that is, their increased likelihood to leave the LSP’s platform when they do not receive sufficiently many requests. Let us denote the slack variables from equations (3.4c) and (3.4d), which bound the number of CDs being matched to requests on the operational level, by $s_{ij}^{\mathrm{DD}}$ and $s_{ij}^{\mathrm{OD}}$ . Then, we can model $p^{\alpha }$ as

$$\begin{array}{r}{p}^{\alpha }=p_{\mathrm{high}}^{\alpha }\cdot \frac{\sum _{ij}{s}_{ij}^{\alpha }}{n_t^{\alpha }}+p_{\mathrm{low}}^{\alpha }\cdot (1-\frac{\sum _{ij}{s}_{ij}^{\alpha }}{n_t^{\alpha }}),\alpha \in \{\mathrm{DD},\mathrm{OD}\}.\end{array}$$

(4.2)

Herein $p_{\mathrm{high}}^{\alpha }$ and $p_{\mathrm{low}}^{\alpha }$ are upper and lower resignation probabilities, which we set to 1 (all CDs resign when not being matched at all) and 0.01 (base case resignation probability), respectively. The term $\frac{\sum _{ij}{s}_{ij}^{\alpha }}{n_t^{\alpha }}$ describes the share of unmatched CDs. When $\frac{\sum _{ij}{s}_{ij}^{\alpha }}{n_t^{\alpha }}$ is high $p_{\mathrm{high}}^{\alpha }$ receives a higher weight and resignations take place at a higher rate. When $\frac{\sum _{ij}{s}_{ij}^{\alpha }}{n_t^{\alpha }}$ is low, the opposite is the case. Note that if CD resignation rates depend on the operational level’s cost function and accordingly non-linearly on the number of CDs, the convexity of the post-decision state’s value function is not guaranteed anymore.

To model the joining process, we assume the number of newly joining CDs ${\tilde{y}}_t^{\alpha }$ to also follow a binomial distribution. Hence, the probability of ${\tilde{y}}_t^{\alpha }$ newly joining CDs reads

$$\mathbb{P}({\tilde{y}}_t^{\alpha })=(\genfrac{}{}{0ex}{}{n_t^{\alpha }}{{\tilde{y}}_t^{\alpha }}){(q^{\alpha })}^{{\tilde{y}}_t^{\alpha }}{(1-q^{\alpha })}^{n_t^{\alpha }-{\tilde{y}}_t^{\alpha }},\alpha \in \{\mathrm{DD},\mathrm{OD}\}.$$

where $n_t^{\alpha }$ is the number of CDs currently active on the platform, and $q^{\alpha }$ is the average joining rate of CDs. The number of CDs in the next time step can be calculated based on equation (2.1). Making the number of newly joining CDs dependent on the currently available ones allows us to account for network effects, that is, platforms with more users/workers attract more users/workers. We set $q^{\alpha }=0.09$ in the base case. Now, we describe the fraction of CDs being active on the operational level and start by DDs. As DDs align their working times to the demand distribution, and the demand peaks in the $[550,600]$ time window, we assume that all DDs are active. Hence, we set ${\zeta }^{\mathrm{DD}}=1$ . ODs’ main working times are aligned with their primary occupation and lie mainly in the late afternoon/evening times, for example, when returning home from work (Le and Ukkusuri, 2019; Galkin et al., 2021). Accordingly, we assume OD arrivals to occur uniformly within the $[400,800]$ time window. This results to a share of OD arrivals within $\tilde{\mathcal{T}}$ of ${\zeta }^{\mathrm{OD}}=\frac{50}{400}=0.125$ .

We consider a homogeneous demand growth rate of roughly $0.6\mathrm{\%}$ per strategic time step, leading to a compound annual growth rate of $20\mathrm{\%}$ . We consider an overall hourly demand comparable to New York City of $\sim$ 24,000 requests (The Washington Post, 2022). Since the area we consider has a surface of $\sim$ $100{\mathrm{km}}^2$ (cf. Figure 4(a)), which is smaller than New York City ( $\sim 800{\mathrm{km}}^2$ ), we divide the overall demand by a factor of 8 and obtain a total demand of $\sum _i{\lambda }_{iT}^{\mathrm{R}}=3,000$ requests per hour in the final time-step. We assume that the spatial distribution of requests remains constant over $\mathcal{T}$ . The request arrival rate reads ${\lambda }_{it}^{\mathrm{R}}=\frac{3,000}{{1.006}^{T-t}}\frac{{\lambda }_{it}^{\mathrm{R}}}{\sum _j^{|\mathcal{M}|}{\lambda }_{jt}^{\mathrm{R}}}$ .

In the base case (see Table 2), we set wages for SDs to $20\mathrm{\$}/\mathrm{h}$ (Hall and Krueger, 2018) and their variable costs to $0.34\mathrm{\$}/\mathrm{km}$ (Bösch et al., 2018; Lanzetti et al., 2023). For DDs, we use route-based compensation schemes (see, e.g., Grubhub or postmates), and for ODs, we assume a constant compensation per request as ODs are only paid for the detour from their private route. Moreover, we assume that CDs’ value of time corresponds to $0.225\mathrm{\$}/\min$ in the base case (Wadud, 2017). Hence, if we take into account the instance’s average velocity of $v=19\mathrm{km}/\mathrm{h}$ , we obtain a payment per km of $c^{\mathrm{DD}}=\frac{0.225\frac{\mathrm{\$}}{\min }\cdot 60\frac{\min }{\mathrm{h}}}{19\frac{\mathrm{km}}{\mathrm{h}}}\approx 0.7\mathrm{\$}/\mathrm{km}$ for DDs. We set the OD compensation to $c_{ij}^{\mathrm{OD}}=c^{\mathrm{OD}}=5\text{\$/request}$ in the base case, as this corresponds to the minimum compensation expectation for ODs when delivering a request, according to a representative study (cf. Le and Ukkusuri, 2019). In the base case, we set $C^{\mathrm{sev}}=\mathrm{\infty }$ to account for a context wherein firing is impossible. Moreover, we consider a penalty of 10$ per undelivered request. This ensures that it is always cheaper to outsource requests to CDs or deliver them with SDs than not delivering them in the base case. We set the initially available CDs to 500 for both DDs and ODs in the base case. We perform sensitivity analyses for all parameters according to Table 2.

Table 2.

Base case parameters and their variations.

Quantity	Parameter	Base case	Variation range
CD joining rates (cf. equation (4.2))	$q^{\alpha }$	0.09	$[0.01,0.17]$
Severance payment (cf. equation (2.5))	$C^{\mathrm{sev}}$	$\mathrm{\infty }$	$[0,60]$
SD fix costs per hour (cf. equation (2.5))	$C^{\mathrm{fix}}$	$20\mathrm{\$}/\mathrm{h}$	$[4,34]$
DD per km costs (cf. equation (3.4a))	$c^{\mathrm{DD}}$	$0.7\mathrm{\$}/\mathrm{km}$	$[0.5,7.5]$
OD costs per request (cf. equation (3.4a))	$c^{\mathrm{OD}}$	$5.5\mathrm{\$}/\mathrm{request}$	$[1,8]$
Share of CD arrivals within $\overline{\mathcal{T}}$	${\zeta }^{\alpha }$	${\zeta }^{\mathrm{DD}}=1,{\zeta }^{\mathrm{OD}}=0.13$	$[0.25,1]$
Number of requests (request density)	$\sum _{i\in \mathcal{M}}{\lambda }_{iT}$	3,000	$[1,000,5,000]$

Table 3.

Deviation from optimal solution, $\delta (\mathrm{\%})$ , of policies obtained with PL-VFA, MY, and $n$ -step lookahead policy for different initial DD fleet sizes and demand scenarios. The best performing approach is marked in bold.

	Constant					Growth					Peak
$(n_0^{\mathrm{SD}},n_0^{\mathrm{DD}},n_0^{\mathrm{OD}})$	MY	$n=1$	$n=2$	$n=3$	PL-VFA	MY	$n=1$	$n=2$	$n=3$	PL-VFA	MY	$n=1$	$n=2$	$n=3$	PL-VFA
(0,6,0)	4.18	4.19	4.19	4.13	0.00	1.63	1.63	1.64	1.64	0.02	4.25	4.42	4.68	3.62	0.02
(0,9,0)	5.79	4.09	3.15	2.68	0.05	2.92	2.96	2.96	2.97	0.53	4.69	4.41	4.44	3.44	0.40
(0,12,0)	3.38	3.42	3.42	3.43	0.15	3.12	3.04	1.77	1.22	0.51	4.17	4.33	4.58	3.63	0.28

PL-VFA = piecewise linear value function approximation; MY = myopic policy; DD = dedicated gig-driver; SD = salaried driver; OD = opportunistic gig-driver.

To assess the results, we evaluate the quotient $h$ (%) between total cumulated costs in the final time step of a mixed fleet (i.e., consisting of SDs and CDs) and an SD-only fleet, and the cost saving $\overline{h}(\mathrm{\%})$

$$\begin{array}{rl}h(\mathrm{\%})& =100\frac{\sum _{t=0}^T{C}_{\mathrm{t}}^{\mathrm{tot}}(\text{mixed fleet of SDs and CDs)}}{\sum _{t=0}^T{C}_{\mathrm{t}}^{\mathrm{tot}}(\text{SD-only fleet})};\\ \overline{h}(\mathrm{\%})& =100(\mathrm{\%})-h(\mathrm{\%}).\end{array}$$

(4.3)

5. Results

In the first part of this section, we validate our PL-VFA (Section 5.1) before analyzing the structural properties of a policy derived by PL-VFA in the base case (Section 5.2). In Section 5.3, we study the policies’ and parameter variations’ impact on total costs from an LSP perspective. Finally, we take the CDs’ perspective and compare different behavioral assumptions. We implemented the strategic level’s MDP in Python and used Gurobi 9.1.2 to solve the operational problem. We performed all experiments on a workstation with a GHz i9-9900 CPU at 16 $\times$ 3.10 GHz and 16 GB RAM. If not mentioned otherwise, reported results are average values based on executing the respective policy 50 consecutive times.

5.1. Validation of PL-VFA

To validate the PL-VFA approach, we evaluate PL-VFA on smaller instances and consider only DDs. In these instances, we can compute a solution with BDP. We study three demand scenarios: constant demand, growing demand, and peak demand. Moreover, we vary the initially available numbers of DDs. We benchmark the results obtained by PL-VFA with a myopic policy (MY), which always hires enough SDs to serve the demand in the current time step $t$ , and an $n$ -step lookahead policy that bases its hiring decisions on the assumed perfect information available for $n$ future steps. We set $n=1,2,3$ to simulate perfect forecasts of up to 6 weeks and refer to Appendix H in the E-Companion for details. We compare the results to BDP, which yields the optimal solution. We define the total cumulated costs ${\overline{C}}_T$ in the final time step $T$ and the gap to the optimal solution $\delta (\mathrm{\%})$ as

$${\overline{C}}_T=\sum _{t=0}^T{C}_t^{\mathrm{tot}};\delta (\mathrm{\%})=100\cdot \frac{{\overline{C}}_T-{\overline{C}}_T^{\mathrm{BDP}}}{{\overline{C}}_T^{\mathrm{BDP}}}.$$

We summarize the average gaps $\delta$ in Table 3. The PL-VFA algorithm converged after $10\mathrm{k}$ iterations for the constant and growth demand case and after $5\mathrm{k}$ iterations for the peak demand case. We refer the interested reader to Appendix I in the E-Companion for a more detailed comparison of this section’s results and the instance’s characteristics. PL-VFA (almost) matches BDP results in all cases. The remaining approaches show deviations of up to $5.79\mathrm{\%}$ . Given that PL-VFA’s costs consistently stay within an error margin of a maximum of $0.53\mathrm{\%}$ compared to the costs derived from BDP, it can serve as a reliable and effective tool to obtain hiring policies.

5.2. Hiring Policy Comparison in the Base Case

We begin this section by studying the difference in the number of SDs hired by a policy obtained from PL-VFA and MY, which we denote by ${\pi }^{\mathrm{PL}-\mathrm{VFA}}$ and ${\pi }^{\mathrm{MY}}$ , respectively. To this end, Figure 5(a) shows the difference in the number of SDs hired between ${\pi }^{\mathrm{MY}}$ and ${\pi }^{\mathrm{PL}-\mathrm{VFA}}$ in $t=0$ as a function of initial DDs and ODs. Firstly, we observe that the difference is always positive, hence ${\pi }^{\mathrm{MY}}$ always hires more SDs than ${\pi }^{\mathrm{PL}-\mathrm{VFA}}$ . The difference increases with the number of DDs. This is plausible as if CD supply is initially not high, ${\pi }^{\mathrm{MY}}$ hires enough SDs to minimize total costs in $t$ , whereas ${\pi }^{\mathrm{PL}-\mathrm{VFA}}$ hires less SDs than required to minimize total costs in $t$ to prevent an oversupply of SDs in later time steps, where it cannot fire SDs anymore. When CD supply is initially very low, ${\pi }^{\mathrm{PL}-\mathrm{VFA}}$ hires similarly many SDs as ${\pi }^{\mathrm{MY}}$ , because the CD fleet will not become large enough over time to contribute to request deliveries. Appendix K in the E-Companion details the number of SDs hired for ${\pi }^{\mathrm{PL}-\mathrm{VFA}}$ and ${\pi }^{\mathrm{MY}}$ . Next we study the difference between ${\pi }^{\mathrm{PL}-\mathrm{VFA}}$ and ${\pi }^{\mathrm{MY}}$ from a temporal point of view. Let $n_t^{\mathrm{SD},\mathrm{opt}}$ denote the number of SDs required to cover the entire demand in a time step $t$ , given the current CD fleet composition and demand. Figure 5(b) shows the difference between $n_t^{\mathrm{SD},\mathrm{opt}}$ and $n_t^{\mathrm{SD}}$ as a function of $t$ for both ${\pi }^{\mathrm{PL}-\mathrm{VFA}}$ and ${\pi }^{\mathrm{MY}}$ . When using ${\pi }^{\mathrm{PL}-\mathrm{VFA}}$ the LSP underhires, that is, does not have sufficient drivers to serve all requests, in the first time steps of the time horizon and overhires, that is, has more drivers than they require, in the second half. When using ${\pi }^{\mathrm{MY}}$ the LSP overhires from the first time steps on. The number of overhired SDs is $\sim 20\mathrm{\%}$ lower in the final time step $T$ when using ${\pi }^{\mathrm{PL}-\mathrm{VFA}}$ than when using ${\pi }^{\mathrm{MY}}$ . The results are plausible, as ${\pi }^{\mathrm{PL}-\mathrm{VFA}}$ anticipates future CD supply, it refrains from hiring many SDs which might become obsolete as the number of CDs grows. The myopic policy ${\pi }^{\mathrm{MY}}$ does not take into account future CD supply and, therefore, always tries to fulfill the demand in the current time step, which causes increased overhiring over time.

Figure 5.

Difference between ${\pi }^{\mathrm{PL}-\mathrm{VFA}}$ and ${\pi }^{\mathrm{MY}}$ and over- versus underhiring over time. (a) ${\pi }^{\mathrm{MY}}-{\pi }^{\mathrm{PL}-\mathrm{VFA}}$ in $t=0$ ; (b) over- versus underhiring over time. PL-VFA = piecewise linear value function approximation; MY = myopic policy.

Result 1

The number of overhired SDs in $T$ is $\sim 20\mathrm{\%}$ lower when using ${\pi }^{\mathrm{PL}-\mathrm{VFA}}$ than when using ${\pi }^{\mathrm{MY}}$ . The myopic nature of ${\pi }^{\mathrm{MY}}$ causes it to overhire SDs from early time steps on.

5.3. Sensitivity Analysis

Figure 6 shows $\overline{h}$ as a function of different DD and OD joining rates. With increasing CD joining rates, we observe higher cost savings of up to $81\mathrm{\%}$ , when increasing $q^{\mathrm{DD}}$ , and of up to $78\mathrm{\%}$ , when increasing $q^{\mathrm{OD}}$ . Moreover, we observe that for increasing $q^{\alpha }$ , ${\pi }^{\mathrm{PL}-\mathrm{VFA}}$ outperforms ${\pi }^{\mathrm{MY}}$ by up to 5 percentage points when varying $q^{\mathrm{DD}}$ (cf. Figure 6(a)), and 2 percentage points when varying $q^{\mathrm{OD}}$ (cf. Figure 6(b)). A 5 percentage points higher $\overline{h}$ corresponds to $19\mathrm{\%}$ lower total costs when using ${\pi }^{\mathrm{PL}-\mathrm{VFA}}$ . Moreover, ${\pi }^{\mathrm{PL}-\mathrm{VFA}}$ outperforms or equals the performance of $n$ -step lookahead methods in almost every scenario, except for $q^{\mathrm{OD}}=0.01$ . Notably, unlike the $n$ -step lookaheads which rely on perfect forecasts for $n$ steps, ${\pi }^{\mathrm{PL}-\mathrm{VFA}}$ operates without assuming exact future knowledge. Remarkably, PL-VFA secures up to a 2-percentage point advantage over the highest performing benchmark, translating into $10\mathrm{\%}$ lower total costs than the best performing benchmark. The total cost decrease’s sensitivity concerning the variation of $q^{\mathrm{OD}}$ is low compared to the sensitivity concerning $q^{\mathrm{DD}}$ . This is plausible, as the ODs’ likelihood of being matched to requests is lower than that of DDs. Opposed to DDs, ODs only accept requests whose origin and destination correspond to their origin and destination. Moreover, the share of ODs arriving within $\overline{\mathcal{T}}$ is lower, that is, ${\zeta }^{\mathrm{OD}}\ll {\zeta }^{\mathrm{DD}}$ .

Figure 6.

Variation of CD joining rate. (a) Variation of the DD joining rate $q^{\mathrm{DD}}$ ; (b) variation of OD joining rate $q^{\mathrm{OD}}$ . CD = crowdsourced driver; DD = dedicated gig-driver; OD = opportunistic gig-driver.

Figure 7.

$n_t^{\mathrm{SD}}-n_t^{\mathrm{SD},\mathrm{opt}}$ for each time step $t$ . (a) $q^{\mathrm{DD}}=0.05$ ; (b) $q^{\mathrm{DD}}=0.09$ ; (c) $q^{\mathrm{DD}}=0.17$ . SD = salaried driver; DD = dedicated gig-driver.

Result 2

The advantage of ${\pi }^{\mathrm{PL}-\mathrm{VFA}}$ over ${\pi }^{\mathrm{MY}}$ grows with increasing $q^{\alpha }$ and can lead to up to $19\mathrm{\%}$ lower total costs compared to ${\pi }^{\mathrm{MY}}$ , while almost always matching or outperforming methods based on perfect information lookahead, yielding up to $10\mathrm{\%}$ lower total costs.

To provide a better intuition on how ${\pi }^{\mathrm{PL}-\mathrm{VFA}}$ achieves smaller total costs than ${\pi }^{\mathrm{MY}}$ , we study the temporal development of the number of SDs. To this end, Figure 7 shows the difference between $n_t^{\mathrm{SD},\mathrm{opt}}$ and $n_t^{\mathrm{SD}}$ as a function of $t$ for $q^{\mathrm{DD}}=0.05$ , $q^{\mathrm{DD}}=0.09$ (base case), and $q^{\mathrm{DD}}=0.17$ . For $q^{\mathrm{DD}}=0.05$ (cf. Figure 7(a)), the difference between $n_t^{\mathrm{SD},\mathrm{opt}}$ and $n_t^{\mathrm{SD}}$ grows over the time horizon. While ${\pi }^{\mathrm{PL}-\mathrm{VFA}}$ underhires in the first time steps, ${\pi }^{\mathrm{MY}}$ overhires over the entire time horizon. For $q^{\mathrm{DD}}=0.09$ (cf. Figure 7(b)) the behavior is similar to $q^{\mathrm{DD}}=0.05$ , but the number of under- and overhired SD increases. Moreover, the difference between ${\pi }^{\mathrm{MY}}$ and ${\pi }^{\mathrm{PL}-\mathrm{VFA}}$ also increases. Figure 7(c) explores under- and overhiring for $q^{\mathrm{DD}}=0.17$ . When using ${\pi }^{\mathrm{PL}-\mathrm{VFA}}$ , we observe the same behavior as for $q^{\mathrm{DD}}=0.05$ and $q^{\mathrm{DD}}=0.09$ , however, with even stronger under- and overhiring as well as a stronger difference between ${\pi }^{\mathrm{MY}}$ and ${\pi }^{\mathrm{PL}-\mathrm{VFA}}$ . When CD joining rates are low, ${\pi }^{\mathrm{PL}-\mathrm{VFA}}$ cannot leverage potential future CD supply in its decision-making and the need for SDs remains higher over the entire time horizon. Hence, the difference between ${\pi }^{\mathrm{MY}}$ and ${\pi }^{\mathrm{PL}-\mathrm{VFA}}$ is lower. When CD joining rates are higher, SDs risk becoming obsolete. Hence, ${\pi }^{\mathrm{PL}-\mathrm{VFA}}$ underhires in early time steps to prevent an obsolete SD pool in later time steps. As total cumulated costs are smaller for $q^{\mathrm{DD}}=0.17$ than for $q^{\mathrm{DD}}=0.09$ , we interpret the previous result as follows: by underhiring in early time steps ${\pi }^{\mathrm{PL}-\mathrm{VFA}}$ hedges against overhiring in later time steps, that is, against having to remunerate a large amount of SDs that are not required anymore as the number of CDs increased over time. We provide the impact of underhiring on the LSP’s service level in Appendix L in the E-Companion.

Result 3

${\pi }^{\mathrm{PL}-\mathrm{VFA}}$ hedges against overhiring in later time steps by hiring up to 50 SDs less than required in early time steps and, therefore, investing in penalties for requests not delivered.

We now study the effect of $q^{\mathrm{DD}}$ and $q^{\mathrm{OD}}$ jointly. To this end, Figure 8(a) shows the cost saving compared to an SD-only fleet, $\overline{h}$ . We observe that increasing joining rates lead to higher cost savings. Moreover, we can see that cost savings are more sensitive to $q^{\mathrm{DD}}$ than to $q^{\mathrm{OD}}$ . For example, when $q^{\mathrm{DD}}=0.13$ , varying $q^{\mathrm{OD}}$ has no impact on cost savings. The LSP achieves the highest cost saving, that is, $78\mathrm{\%}$ , when $q^{\mathrm{DD}}$ is highest.

Figure 8.

Combined impact of varying joining rates on $\overline{h}$ (left) and $h$ (right) in $t=T$ . (a) Cost saving $\overline{h}$ ; (b) cost ratio $h$ (split into components).

Figure 9.

Variation of CD costs. (a) DDs’ costs per km $c^{\mathrm{DD}}$ ; (b) ODs’ costs per request $c^{\mathrm{OD}}$ . CD = crowdsourced driver; DD = dedicated gig-driver; OD = opportunistic gig-driver.

Result 4

The increase of $q^{\mathrm{DD}}$ reduces costs by up to $78\mathrm{\%}$ and, therefore, more than the increase of $q^{\mathrm{OD}}$ . Hence, DDs are the main driver for cost savings within the CD fleet.

Figure 8(b) shows the driver and penalty cost split as a percentage of total costs for varying $q^{\mathrm{DD}}$ and $q^{\mathrm{OD}}$ . We observe that SDs have, overall, the highest cost share, with up to $50\mathrm{\%}$ for $q^{\mathrm{DD}}=q^{\mathrm{OD}}=0.01$ . DD costs have the overall second highest cost share with up to $30\mathrm{\%}$ when $q^{\mathrm{DD}}=0.13$ , while ODs have lower importance in the cost mix. Penalty costs are only high when the DD joining rate is low and highest for $(q^{\mathrm{DD}}=0.01,q^{\mathrm{OD}}=0.01)$ with a share of up to $40\mathrm{\%}$ .

Result 5

In mixed fleets, SDs are the main total costs driver with a cost share of up to $50\mathrm{\%}$ , followed by DDs with up to $30\mathrm{\%}$ .

Figure 10.

Variation of severance payment and SD fix costs. (a) Variation of severance payment $C^{\mathrm{sev}}$ ; (b) variation of SDs’ fix costs $C^{\mathrm{fix}}$ . SD = salaried driver.

In Figure 9(a), we report DD costs per km. The cost-saving potential decreases with increasing $c^{\mathrm{DD}}$ . For low $c^{\mathrm{DD}}$ the advantage of using ${\pi }^{\mathrm{PL}-\mathrm{VFA}}$ is highest and leads to higher cost savings compared to ${\pi }^{\mathrm{MY}}$ of up to 5 percentage points. In Figure 9(a), we report OD costs per request. We observe that $\overline{h}$ remains constant over the entire range of $c^{\mathrm{OD}}$ . The advantage of using ${\pi }^{\mathrm{PL}-\mathrm{VFA}}$ observed for low $c^{\mathrm{DD}}$ in Figure 9(a) is plausible since the LSP can increasingly leverage DDs when their costs are low. Finally, ${\pi }^{\mathrm{PL}-\mathrm{VFA}}$ matches or outperforms lookahead policies for all $c^{\mathrm{DD}}$ and $c^{\mathrm{OD}}$ , and different values of  $n$ .

Result 6

The cost saving potential is more sensitive to DD costs than to OD costs. The advantage of ${\pi }^{\mathrm{PL}-\mathrm{VFA}}$ is highest when CD costs are low, for which ${\pi }^{\mathrm{PL}-\mathrm{VFA}}$ yields more than 5 percentage points higher cost savings than ${\pi }^{\mathrm{MY}}$ . Moreover, ${\pi }^{\mathrm{PL}-\mathrm{VFA}}$ is able to match or outperform the strongest lookahead policy in all cases by up to 0.5 percentage points.

Finally, to understand the impact of firing flexibility in workforce planning, we vary the severance payment $C^{\mathrm{sev}}$ according to Table 2 and report the results in Figure 10(a). We also report the base case, wherein $C^{\mathrm{sev}}=\mathrm{\infty }$ for comparison. We observe that with increasing $C^{\mathrm{sev}}$ , the saving potential compared to an SD-only fleet decreases. The cost advantage of using ${\pi }^{\mathrm{PL}-\mathrm{VFA}}$ increases with increasing $C^{\mathrm{sev}}$ and remains approximately constant from $C^{\mathrm{sev}}=40\mathrm{\$}$ on. When $C^{\mathrm{sev}}$ is low, the LSP can lay off SDs at any time without additional costs. Hence, the advantage of using PL-VFA is negligible. When $C^{\mathrm{sev}}$ is higher, the value of not hiring SDs is potentially higher as SDs can become obsolete in later time steps. Firing them then results in penalty costs that could have been avoided if they were not hired in the first place. This trade-off is only made by ${\pi }^{\mathrm{PL}-\mathrm{VFA}}$ . Moreover, we note that when $C^{\mathrm{sev}}$ is low, PL-VFA holds no discernible advantage compared to the lookahead policies, as the optimal policy simply involves greedy hiring and firing. With moderately high $C^{\mathrm{sev}}$ , ${\pi }^{\mathrm{PL}-\mathrm{VFA}}$ falls short of the lookahead methods’ performance. We can attribute this to the PL-VFA’s challenge in identifying the optimal slope set, exacerbated by a larger action space due to extra firing decisions. The $n$ -step lookaheads’ apparent superiority stems from their unrealistic advantage of perfect future predictions, an advantage not available in practical scenarios. As the severance costs $C^{\mathrm{sev}}$ increase, approaching the base case where $C^{\mathrm{sev}}=\mathrm{\infty }$ , firing becomes impossible. Consequently, the action space reduces to only hiring decisions, for which PL-VFA manages to approximate the optimal slope set, thereby outperforming all other methods including the lookahead policies. In Figure 10(b), we explore the impact of $C^{\mathrm{fix}}$ on $\overline{h}$ . For small $C^{\mathrm{fix}}$ $\overline{h}$ is smaller and the difference between ${\pi }^{\mathrm{PL}-\mathrm{VFA}}$ and ${\pi }^{\mathrm{MY}}$ is negligible. The cost saving potential increases up to $82.5\mathrm{\%}$ for ${\pi }^{\mathrm{PL}-\mathrm{VFA}}$ and $81\mathrm{\%}$ for ${\pi }^{\mathrm{MY}}$ . The difference between ${\pi }^{\mathrm{PL}-\mathrm{VFA}}$ and ${\pi }^{\mathrm{MY}}$ increases up to 7 percentage points when $C^{\mathrm{fix}}=16\mathrm{\$}$ , which corresponds to $19\mathrm{\%}$ lower total costs. When $C^{\mathrm{fix}}$ increases further, the difference between both policies decreases again. For low fixed SD costs, the decision of hiring or not hiring SDs does not significantly impact total costs. As $C^{\mathrm{fix}}$ increases, this decision needs to be traded off more carefully. Interestingly, the advantage of using PL-VFA vanishes for even higher fixed costs, as both policies refrain from hiring costly SDs. When varying $C^{\mathrm{fix}}$ , ${\pi }^{\mathrm{PL}-\mathrm{VFA}}$ always outperforms the $n$ -step lookhahead policies, with a cost saving advantage of up to $1$ percentage points compared to $n=3$ when $C^{\mathrm{fix}}=3\mathrm{\$}$ , which corresponds to $3\mathrm{\%}$ lower costs.

Result 7

Compared to ${\pi }^{\mathrm{MY}}$ , ${\pi }^{\mathrm{PL}-\mathrm{VFA}}$ achieves three percentage points higher cost savings when severance payments become infinite (base case) and 7 percentage points higher cost savings, that is, $19\mathrm{\%}$ lower total costs, when SD fix costs are set to $16\mathrm{\$}/\mathrm{h}$ . While ${\pi }^{\mathrm{PL}-\mathrm{VFA}}$ cannot outperform the $n$ -step lookahead approaches for varying $C^{\mathrm{sev}}$ , it does for varying $C^{\mathrm{fix}}$ with total lower costs of up to $3\mathrm{\%}$ .

Varying the share of CDs being active within $\overline{\mathcal{T}}$ , ${\zeta }^{\alpha }$ , (see Figure 11(a)) reveals that higher ${\zeta }^{\alpha }$ lead to a higher share of CD costs in the cost mix of up to $35\mathrm{\%}$ when ${\zeta }^{\mathrm{DD}}={\zeta }^{\mathrm{OD}}=1$ , thereby reducing SDs’ utilization. Additionally, for identical ${\zeta }^{\alpha }$ , DDs incur higher costs, suggesting their preferential use by the LSP over ODs. Finally, varying the request density (cf. Figure 11(b)) shows that with higher request density, SD costs rise to $82\mathrm{\%}$ of total costs, while being at $0\mathrm{\%}$ when the request density is low. This increase is plausible, given that more requests necessitate a larger delivery supply for maintaining high service levels. With CD supply remaining the same, the additional demand is met by an increase in SD usage.

Figure 11.

Variation of ${\zeta }^{\alpha }$ and request density $\sum _{i\in \mathcal{M}}{\lambda }_{iT}$ . (a) Variation of ${\zeta }^{\alpha }$ ; (b) variation of $\sum _{i\in \mathcal{M}}{\lambda }_{iT}$ .

Result 8

When the availability of CDs increases to ${\zeta }^{\mathrm{DD}}={\zeta }^{\mathrm{OD}}=1$ within $\overline{\mathcal{T}}$ , the share of CD costs rises to $35\mathrm{\%}$ , indicating a higher degree of outsourcing by the LSP. When the request density increases, the LSP increasingly relies on SDs, which yields an increased share in total costs of up to $82\mathrm{\%}$ .

5.4. Impact Factors on Delivery Option Attractiveness

To understand the conditions under which an operator prefers certain drivers over others in the delivery process, we perform a scenario analysis: we first construct scenarios that vary by one parameter compared to the base case. Then, we analyze the average share of requests delivered by each driver type over the time horizon $\mathcal{T}$ . First, we focus on parameters directly controlled by the LSP, that is, personnel costs for SDs and payments to CDs. For SDs, we focus on low $C^{\mathrm{fix}}$ implying a scenario in which SDs’ wage expectation is low, which allows the LSP to hire more SDs. For CDs, we focus on scenarios with low $c^{\mathrm{DD}}$ and $c^{\mathrm{OD}}$ implying low payment per request expectations of CDs. We vary the payments to CDs within a corridor, in which we assume no impact on the driver supply ( $q^{\mathrm{DD}}$ and $q^{\mathrm{OD}}$ ). This is plausible since lower payments make CDs more attractive in the request matching process, thereby compensating for the reduced payments per request via an increased amount of total requests assigned. Second, we consider two parameters the LSP has only indirect control over (e.g., via promotional campaigns): low and high CD supply. We summarize the scenarios in the first column of Table 4 and add the base case for reference. For each scenario, we analyze whether a certain driver type dominates the other driver types or if the requests are equally split between multiple driver types.

Table 4.

Scenarios and preferred delivery option.

	Preferred
	delivery
Scenario	optiona
Base case (BC): See Table 2	Balanced
Scenario 1 (S1): Low SD wages ( $C^{\mathrm{fix}}=4\mathrm{\$}$ )	Balanced
Scenario 2 (S2): Low DD costs ( $c^{\mathrm{DD}}=0.5\mathrm{\$}/\mathrm{km}$ )	DD
Scenario 3 (S3): Low OD costs ( $c^{\mathrm{OD}}=1\mathrm{\$}/\mathrm{req}.$ )	Balanced
Scenario 4 (S4): Low CD supply ( $q^{\alpha }=0.01$ )	SD
Scenario 5 (S5): High CD supply ( $q^{\alpha }=0.13$ )	Balanced

SD = salaried driver; DD = dedicated gig-driver; OD = opportunistic gig-driver; CD = crowdsourced driver.

^aShare of delivered requests of $\ge 60\mathrm{\%}$ not considered balanced, but dominated by one driver type

Figure 12 shows the average share of requests served by each driver type over the time horizon $\mathcal{T}$ for each of the scenarios in Table 4 and we summarize Figure 12's results in the second column of Table 4. In BC, S1, S3, and S5, the majority of requests is served by either SDs or DDs. Thus, we consider the preferred delivery option to be balanced. Interestingly, the LSP still relies in almost equal shares on DDs in S1, although SD wages are low. This can be attributed to the sufficient supply of DDs in the base case and, which eliminates the need of hiring many SDs although they are cheap. In S5, SDs remain crucial in the delivery mix despite high CD supply, which indicates their importance for certain request routes for which CDs are unsuitable. In S2 DDs serve more than 60% of requests, clearly being the preferred delivery option for the LSP, which is plausible as low DD costs substantially favor DDs. Contrarily, SDs are the preferred option delivery option for the LSP in S4, which can be explained by the lack of CD supply. We observe that, even if conditions are favoring ODs (S3), they are only responsible for a small share of delivered requests.

Figure 12.

Average share of requests delivered (in %) over $\mathcal{T}$ by different driver types.

Result 9

In the base case, when SD wages are low, and when CD supply is high, the delivery options are balanced. However, when payments to DDs and CD supply are low, the share of requests surpasses $60\mathrm{\%}$ for DDs and SDs, respectively.

In the previous analysis, we observed that ODs play a minor role in the request delivery process. Apart from payments to ODs, two more factors influence ODs’ share in request matches: temporal patterns ( ${\zeta }^{\mathrm{OD}}$ ) and spatial patterns ( $P_{ij}^{\mathrm{OD}}$ ). However, the LSP has no control over these operational factors. To understand their impact we investigate the share of requests delivered by ODs for different number of DDs and ODs for three scenarios: the base case for reference, a varied temporal pattern, and a varied spatial pattern (cf. Figure 13). In Figure 13(b), we change ODs’ temporal patterns, represented by ${\zeta }^{\mathrm{OD}}$ , from 0.13 to 0.5, thereby increasing the number of ODs being active within $\overline{\mathcal{T}}$ . The share of requests delivered by ODs reaches around $50\mathrm{\%}$ when the number of ODs is high, and only a few DDs are available. However, when the number of DDs is high, the share of requests delivered by ODs remains as low as in the base case. In Figure 13(c), we synchronize ODs’ spatial driving patterns, $P_{ij}^{\mathrm{OD}}$ , with request route patterns, that is, $P_{ij}^{\mathrm{OD}}=P_{ij}^{\mathrm{R}}$ . This has a stronger impact on the share of requests delivered by ODs as it reaches values of above $80\mathrm{\%}$ when the number of ODs is high and DDs is low. This bears a significant potential for municipalities to ameliorate sustainable logistics. Unlike DDs, ODs do not induce traffic, and municipalities could motivate LSPs to implement measures increasing the share of OD deliveries. LSPs can, for example, provide incentives for customers to buy during OD peak times by offering rebates during these times, or synchronize request and OD routes by pooling requests at micro-hubs which coincide with regions frequently visited by ODs.

Figure 13.

Share of requests delivered by ODs (in %) in $t=0$ and $n_0^{\mathrm{SD}}=0$ for different fleet compositions for the base case, varied temporal patterns, and varied spatial patterns. (a) Base case; (b) increase of ${\zeta }^{\mathrm{OD}}$ to 0.5; (c) synchronizing OD and request routes. ODs = opportunistic gig-drivers; SD = salaried driver.

Result 10

ODs’ share in requests delivered increases to more than $80\mathrm{\%}$ when synchronizing ODs’ temporal and spatial patterns with those of requests and the number of DDs is low.

So far, we assumed that CDs leave the LSP according to a fixed resignation rate. In the next section, we study the effect of a resignation probability that depends on the number of unmatched CDs.

5.5. Analysis of Unmatched CDs

Figure 14 reports the average percentage of unmatched DDs and ODs for different joining rates over the entire time horizon. We observe that the percentage of unmatched DDs (cf. Figure 14(a)) is higher than the percentage of unmatched ODs, especially when $q^{\mathrm{DD}}$ is high. For high $q^{\mathrm{DD}}$ , the percentage of unmatched DDs amounts to $60\mathrm{\%}$ . The percentage of unmatched ODs is lower and amounts to a constant value of $10\mathrm{\%}$ across different joining rates (cf. Figure 14(b)).

Figure 14.

Percentage of unmatched CDs when the resignation probability does not depend on the number of unmatched CDs. The $z$ -axis is logarithmically scaled. (a) Percentage of unmatched DDs; (b) Percentage of unmatched ODs. CDs = crowdsourced drivers; DDs = dedicated gig-drivers; ODs = opportunistic gig-drivers.

As the joining rate grows, CD supply surpasses demand, and the LSP can no longer outsource demand to CDs. Furthermore, the higher quotient of unmatched DDs is plausible since more DDs are active on the operational level than ODs due to their higher ${\zeta }^{\mathrm{DD}}$ . Hence, they are more likely to be active when there is no demand.

Figure 15 shows the number of unmatched CDs now assuming that CDs’ resignation probability depends on $s_{ij}^{\alpha }$ (cf. equation (4.2)). Overall, the quotient of unmatched CDs is significantly lower than in Figure 14. Moreover, the difference between DDs and ODs is small. Both have a relatively constant ratio of unmatched drivers across joining rates of around $10\mathrm{\%}$ . The lower ratio of unmatched DDs is plausible, as the DDs’ resignation probability depends on the number of DDs unmatched. Hence, it can significantly surpass the base case resignation probability of 0.01 and, therefore, the joining rate. When DDs leave the LSP’s platform at a higher rate than joining it, the LSP accumulates fewer DDs than in the case when the resignation probability has a constant value of 0.01. Fewer DDs imply less unmatched DDs. In Figure 16, we show the difference in the number of SDs and CDs in the final time step $t=T$ between the case wherein the resignation probability depends and wherein the resignation probability does not depend on the percentage of unmatched CDs. We observe that the LSP hires more than 100 additional SDs and has significantly less CDs at their disposition when the resignation probability depends on the number of unmatched CDs. The lower CD supply urges the LSP to hire more SDs to ensure high service levels.

Figure 15.

Percentage of unmatched CDs when CDs’ resignation probability depends on number of unmatched CDs. The $z$ -axis is logarithmically scaled. (a) Percentage of unmatched DDs; (b) percentage of unmatched ODs. CDs = crowdsourced drivers; DDs = dedicated gig-drivers; ODs = opportunistic gig-drivers.

Figure 16.

Difference between the total number of drivers when resignation probability depends on the number of unmatched CDs and when it does not. The $z$ -axis is logarithmically scaled. (a) Difference for SDs; (b) Difference for DDs; (c) Difference for ODs. CDs = crowdsourced drivers; SDs = salaried drivers; DDs = dedicated gig-drivers; ODs = opportunistic gig-drivers.

Result 11

The LSP has to hire $\ge 100$ more SDs, when the resignation probability depends on the number of unmatched CDs, as the effective CD supply is significantly lower.

6. Conclusion

In this article, we studied the strategic workforce planning of an LSP providing on-demand delivery services with a mixed fleet of couriers consisting of SDs and CDs. We integrated long-term strategic SD hiring decisions and short-term operational decisions regarding driver dispatching. We formalized the strategic hiring and firing problem as an MDP and solved it with approximate dynamic programming based on piecewise linear value function approximation, which allows us to study large-scale instances. We incorporated operational costs in the MDP’s cost function using a fluid approximation to account for delivery operations.

We conducted a case study based on a real-world data set from Grubhub for food delivery in a metropolitan area located in the US. Herein, our studies led to several findings, which we synthesize in the following.

Total costs obtained with PL-VFA are either equal to or up to $19\mathrm{\%}$ lower than total costs obtained with a myopic hiring policy, while mostly matching our outperforming an up to 3-step lookahead policy with perfect information by up to $10\mathrm{\%}$ . PL-VFA achieved this cost saving by hiring less SDs than required to serve the demand and consequently accepts lower service levels in early time steps. It does so to hedge against remunerating obsolete SDs in later time steps as the amount of CDs grew.

SDs and DDs are the main cost drivers in the total cost mix with up to a 50% and a 30% share in total costs, respectively. The significance of SD costs in the total cost mix stresses the importance of finding good SD hiring policies, which minimize the number of SDs hired. DDs have the second highest contribution to total costs, when $q^{\mathrm{DD}}$ is high. The DDs’ contribution is more significant than the one of ODs because ODs only accept requests coinciding with their origin and destination. Moreover, their share of arrivals within $\overline{\mathcal{T}}$ is significantly lower than the one of DDs.

The LSP has to hire more than $100$ additional SDs when CDs are matching sensitive as an oversupply of CDs, that is, a higher number of CDs than required to serve the demand, does not arise anymore.

This work opens up a promising new research avenue in the field of crowdsourced deliveries, by combining the study of crowdsourced delivery fleets with long-term workforce planning. Specifically, this work provides a foundation for follow-up studies. Firstly, the SD workforce planning problem could be extended by accounting for SDs with different contract durations or working schedules. Moreover, one could introduce uncertainty in the demand dimension on the strategic workforce planning level. Finally, one could implement behavioral components for CDs, for example, discrete choice models based on real-world data, to more accurately represent the CDs’ behavior, for example, regarding resignation processes.

Supplemental Material

sj-pdf-1-pao-10.1177_10591478241268602 - Supplemental material for Strategic Workforce Planning in Crowdsourced Delivery With Hybrid Driver Fleets

Supplemental material, sj-pdf-1-pao-10.1177_10591478241268602 for Strategic Workforce Planning in Crowdsourced Delivery With Hybrid Driver Fleets by Julius Luy, Gerhard Hiermann and Maximilian Schiffer in Production and Operations Management