On the design of crowdsourced delivery fleets: Strategic decisions
and operational implications
J. Luya,∗ , G. Hiermanna , M. Schiffera,ba Technical University of Munich, School of Management, Munich, Germanyb Munich Data Science Institute, Technical University of Munich, Munich, Germany{julius.luy,gerhard.hiermann,schiffer}@tum.de∗ Corresponding author
Extended abstract submitted for presentation at the 11th Triennial Symposium on
Transportation Analysis conference (TRISTAN XI)
June 19-25, 2022, Mauritius IslandApril 3, 2022
Keywords: Crowdsourced delivery, dynamic programming, stochastic workforce planning

1IntroductionLogistics service providers (LSP) increasingly use crowdsourced workforce on the last-mile tofulfill customers’ expectations regarding same-day or on-demand delivery. Crowdsourced couriers, typically independent contractors, flexibly decide when and how much to work (see, e.g.,
Amazon Flex or DoorDash), thereby introducing uncertainty to an LSP’s strategical and operational planning. Accordingly, current research on crowdsourced deliveries focuses on developing
algorithms for operational decision-making under supply uncertainty. Both, static (see, e.g.,Archetti et al. (2016)) and dynamic approaches (see, e.g., Arslan & Zuidwijk (2016)) exist andconsider mostly two different crowdsourced driver types: gigworkers and occasional drivers. Theformer are primarily financially incentivized and the work for the LSP constitutes a significant
amount of their income. The latter are financially independent of the LSP and typically only
accept deliveries that overlap with routes they intend to take anyway. To mitigate supply uncertainty, LSPs rely on full-time employees, in the following called fixed drivers, to compensate
for periods with low availability of crowdsourced drivers. This yields a planning problem with apartially uncertain workforce, which has been analyzed in the context of shift scheduling (Ulmer& Savelsbergh, 2020).
So far, the strategic workforce planning question of how many fixed drivers to hire for acertain time horizon, while anticipating operational implications, has not been studied in a
crowdsourced delivery context. Answering this question entails a trade-off between the costsof hiring a new employee and relying on crowdsourced workforce. Against this background,
we study a novel approach that integrates the strategic workforce planning problem with its
operational implications. We consider an LSP that operates a mixed fleet consisting of fixeddrivers, gigworkers and occasional drivers in an area M, knowing the expected demand at every
location i ∈ M. The LSP has to make decisions on two planning levels: On the strategic level,
she has to decide on the number of fixed drivers to hire in every time step t over a time horizon T .
On the operational level, defined on time horizon T̃ , she has to find an optimal routing policy forher fixed drivers while outsourcing requests to crowdsourced drivers. We find that integratingthese two planning levels and taking into account future crowdsourced driver capacity in theworkforce planning problem yields a significant total cost reduction compared to an approachthat only considers immediate operational implications.
TRISTAN XI Symposium

Original abstract submittal

J. Luy, G. Hiermann, M. Schiffer

22Methodology

This section details the introduced problem setting. In a first step we describe the strategic andin a second step the operational level.

2.1

Strategic level

We formulate the decision making problem under uncertainty faced by the LSP as a MarkovDecision Process.
 We describe the state of the fleet St in every time step t ∈ T by St =GW , nOD ∈ N3 . State variable nFD represents the number of fixed drivers (FD), nGWnFD,nt
tttt
0
the number of gigworkers (GW), and nOD
the number of occasional drivers (OD). We denotet
the total costs of the LSP in time step t with Cttot . These consist of fixed costs C fix per fixeddriver and time step and of operational costs Ctops , that are evaluated on the operational level:
ops FD GW
GWfix FD
Cttot (nFD, nOD, nODnt .
t , ntt ) = Ct (nt , ntt )+C(1)

At the beginning of each time step t thehow many fixed drivers to add to her
 LSP decides
FDfleet. We define the action space by A = 0, ..., amax ∈ N0 with aFD
max being the maximum fixed
driver fleet size increment. Upon the hiring decision, we evaluate the operational problem andsubsequently the joining and resignation process of crowdsourced drivers. The joining processmodels new private individuals intending to work as crowdsourced drivers for the LSP, startingin time step t. We describe the joining process by a fleet size increase rate q α (α ∈ {GW, OD}),
expressed as percentage of nαt , and model it as a normally distributed random variable. Theresignation process describes crowdsourced drivers that decide not to work for the LSP anymore,e.g., because they found a better outside option. We denote the probability of drivers of type αto resign at the end of time step t with pα and the total number of drivers of type α resigningwith X α . The resulting number of drivers in the next time step then reads
nαt+1 = nαt − X α + q α · nαt .

(2)Starting in S0 , the LSP’s objective is to minimize expected future total costs over T"t#max
X
GWv(S0 ) = min E
γ t · Cttot nFD, nOD|S0 .
t , nttπ∈Π(3)t=0Here Π denotes the set of all policies, π refers to a single policy and γ is the discount factor. Wesolve this problem with backward dynamic programming.

2.2

Operational level

The problem on the operational level consists of finding optimal routing policies for the fixeddrivers, while possibly outsourcing some requests to crowdsourced drivers. We define the operational problem on a different time horizon T̃ and we denote its time variable with t̃. The strategiclevel’s time variable t can be segmented into N representative time intervals. The operational
ops
ops
problem is then solved
for each interval, yielding Ct,nfor n ∈ {1, ..., N }. The resulting Ct,nisPops
ops
obtained via Ct,n= n dn · Ct,n, where dn is the number of occurrences of time interval n in t.
We face a pick-up and delivery problem, where requests arise at some location i ∈ M andneed to be delivered to a destination j ∈ M. We denote with Eij (t̃) the number of FDs drivingfrom location i ∈ M to location j ∈ M without serving a request. The variable Eii (t̃) describes
waiting FDs at location i. Further, Fij (t̃) describes the number of FDs delivering a requestfrom i to j. Requests follow a Poisson arrival process, with arrival rate λRi . Upon arrival atlocation i, a request is matched to an FD, GW, or OD, or not matched at all. We denote routing
costs by cβij (β ∈ {FD, GW, OD, ∅}), where c∅ij is a penalty that arises when a request cannot be
served and leaves the system. While routing costs for FDs and GWs depend on the trip length,
TRISTAN XI Symposium

Original abstract submittal

J. Luy, G. Hiermann, M. Schiffer

3ODs receive a fixed compensation per request. Similarly, crowdsourced driver arrivals follow aPoisson process with rate λαi , where λGW
depends on nGW
and the distribution of requests.
tiODOD
The arrival rate λi depends on nt and area specific mobility patterns.
We denote with Q the empty FD-routing policy, i.e., a decision rule determining whether an
FD should remain at station i or drive without freight to a location j. The objective is to finda policy Q that minimizes total routing costsXX βEij (t̃) · cFD
cij · Aiβ (t̃)
β ∈ {FD, GW, OD, ∅} .
(4)minij +Qi,j∈M

βThe variable Aiβ (t̃) denotes the number of requests matched to option β at station i. This
problem becomes intractable for large fleets sizes. Therefore, we follow a fluid approximation
approach based on the results from Braverman et al. (2019). We interpret the system as aclosed queueing network with |M| single server queues representing FDs not carrying load and2waiting at station i (Eii ) and service rate λR
i , |M| − |M| infinite server queues representing
fixed drivers driving from i to j (Eij ) without serving a request, and |M|2 infinite server queues
for fixed drivers serving a request from i to j (Fij ) with service rate µij . We represent witheij and fij the fluid scaled queue lengths Eij and Fij , i.e., eij =Eij (t̃→∞)F (t̃→∞)
and fij = ijnFD .
nFDtt

We denote with aβi the fraction of requests served by fixed drivers, by crowdsourced drivers, orunserved requests. The terms PijR , PijG and PijO describe request, GW, and OD route patterns
respectively. The operational problem is then formulated as the following linear program:XX X ββRFD FDmincij · λR
(5)i · ai · Pij + cij nt eij
e,f,aβijβFD
FD(λR· PijR = µij · fiji /nt ) · ai∀i, j ∈ M

(6a)

GW· PijGW
λR· PijR ≤ λGW
i · aii∀i, j ∈ M

(6b)

OD
λR· PijR ≤ λOD· PijOD
i · aii∀i, j ∈ M

(6c)∀i, j ∈ M

(6d)

µki fki∀i ∈ M(6e)µki fki∀i ∈ M(6f)

aFD+ aGW+ aOD+ a∅i = 1iii

∀i ∈ M(6g)µij eij ≤Xµki fki , i 6= jkXFDFDµki eki ≤ (λR≤i /nt ) aik, k6=i
FDFD(λR+i /nt ) aiXµki eki +k, k6=iX

µij eij =j, j6=iXk, k6=iXkµki eki +Xk

The objective describes the minimization of operational costs arising from delivering requests andempty-FD-routing. Constraints (6a) to (6c) describe Little’s law of flow conservation. Constraint(6d) is the relaxed Little’s law, stating that the mass of out-going empty FDs in one direction j
at one location i cannot be higher than the mass of incoming full FDs. Constraints (6e) and (6f)state equality between the total rate of outflow from location i to the total rate of inflow. Finally,
constraint (6g) ensures that at every location i a request is either matched or not matched. The
objective of this linear program yields the approximated operational cost of a representative timeinterval, which can then be used to compute Ctops as input for the strategic level’s problem.

3Preliminary results

In our preliminary experiments, we study an LSP with an initial fleet of ten FD, one GW, andone OD. We consider costs per request of 4$ and 2$ respectively for GWs and ODs; FDs receive
TRISTAN XI Symposium

Original abstract submittal

J. Luy, G. Hiermann, M. Schiffer

4

a fixed wage of 20$/h. Furthermore, we consider a joining rate with distribution N (0.3, 0.05)
to model an average increase of the crowdsourced driver fleet of 30% per time step. We choosea resignation probability of pα = 0.1, which seems to be a reasonable choice when comparing
to established crowdsourced platforms, e.g., Uber (Hall & Krueger, 2018). The area consists of
6 locations, and we consider a demand of on average 6 requests per location per hour for theoperational level. We choose a time horizon of 30 weeks on the strategic level to account for
the long-term costs of hiring fixed drivers and assume constant demand levels over the strategic
time horizon. To benchmark our approach, which integrates future crowdsourced driver capacity
via backward dynamic programming (BDP), we compare it with a myopic approach, that bases
hiring decisions only on immediate operational costs.
Figure 1 shows the accumulated total cost over time for both the BDP and the myopic
approach. One can see that the hiring policy drawn from the BDP approach leads to lower total
costs at the end of the time horizon. In the beginning, however, total costs for BDP are higher
since it does not hire as many FDs as the myopic approach and has to pay penalties on notserved requests. Figure 2 shows the accumulated total costs in the last time step. The two rightbars result from a different study, in which the degree of synchronization of OD-specific mobility
patterns and request patterns is lowered. The second case’s higher costs emphasize the influenceof mobility patterns on the success of crowdsourced delivery services.

Figure 1 – Accumulated total costs Cttot overtime (based on 1000 runs)

Figure 2 – High vs. low degree of synchronization (based on 1000 runs)

References
Archetti, C., Savelsbergh, M., & Speranza, G. 2016. The Vehicle Routing Problem with Occasional
Drivers. European Journal of Operational Research, 254(2), 472–480.
Arslan, A.M., & Zuidwijk, R. 2016. Crowdsourced Delivery, A Dynamic Pickup and Delivery Problemwith Ad Hoc Drivers. Transportation Science, 53(1), 472–480.
Braverman, A., Dai, J. G., Liu, X., & Ying, L. 2019. Empty-Car Routing in Ridesharing Systems.
Operations Research, 67(5), 1209–1502.
Hall, J. V., & Krueger, A. B. 2018. An Analysis of the Labor Market for Uber Driver-Partners in theUnited States. ILR Review, 71(3), 705–732.
Ulmer, M. W., & Savelsbergh, M. 2020. Workforce Scheduling in the Era of Crowdsourced Delivery.
Transportation Science, 54(4), 1113–1133.

TRISTAN XI Symposium

Original abstract submittal