Joint Order Pricing, Partitioning, and Routing for Hybrid
Courier Fleets on Crowdsourced Delivery Platforms
A. Behrendta,∗ , M. Savelsbergha and H. Wangaa Georgia Institute of Technology, Atlanta, USA

adam.behrendt@gatech.edu, martin.savelsbergh@isye.gatech.edu, he.wang@isye.gatech.edu∗ Corresponding author
Extended abstract submitted for presentation at the 11th Triennial Symposium onTransportation Analysis conference (TRISTAN XI)
June 19-25, 2022, Mauritius Island

December 28, 2021
Keywords: crowdsourced delivery, last-mile delivery, pricing, vehicle routing, column generation

1INTRODUCTION AND MOTIVATION

Last-mile delivery has been marked by sustained and rapid growth in the last decade. Consumer
participation in, and reliance on, E-commerce is a predominant driver for this increase in delivery
demand. This trend has accelerated during the COVID-19 pandemic, exemplified by demand
surges in food, grocery, and package delivery. Due to cascading effects of the pandemic, many
delivery platforms face driver supply shortages, so maximizing a delivery platform’s operating
efficiency becomes an essential competitive advantage.
At the same time, the emergence of the gig economy has brought with it a new type ofcourier, one which we refer to as an ad-hoc courier. Whereas a traditional courier, referred toas a committed courier, is employed by the delivery platform and can be dispatched to executedelivery plans, an ad-hoc courier is a non-employee courier (an independent contractor) whochooses his own work schedule and selects delivery tasks to perform in order to maximize his
personal utility. Recently founded delivery platforms like Convoy (freight trucking), Roadie (lastmile delivery), and Instacart (grocery delivery) utilize ad-hoc couriers to serve demand.
In this paper, we consider a crowdsourced delivery platform that employs both committed
and ad-hoc couriers. The benefit of utilizing both courier types goes beyond increasing delivery capacity. Each courier type has its own advantage: ad-hoc couriers are more flexible andcommitted couriers are more reliable. We show that by intelligently designing an integrated system using order partitioning, dynamic pricing (for ad-hoc couriers), and routing (for committedcouriers), the delivery platform can exploit the benefits of each courier base to improve customer
service and minimize total costs.

2PROBLEM STATEMENT

We consider a dynamic pickup and delivery problem on a bounded service region from theperspective of a delivery platform. Let T = [0, T ] be the operating period in which N customer
orders arrive according to a Poisson process with rate λ. Each order has a placement time,pickup location (origin), ready time, delivery location (destination) and a deadline. We define
the distance (d) of an order to be the Euclidean distance from the pickup to delivery locationrounded to the nearest integer and the relative lead time (τ ) to be the remaining time until thelatest possible pickup time for the order to be delivered on time.
TRISTAN XI Symposium

Original abstract submittal

A. Behrendt, M. Savelsbergh and H. Wang

2In order to serve these dynamically arriving orders, a crowdsourced delivery platform employs
two types of couriers: committed and ad-hoc. In general, M committed couriers are hired priorto T (and paid a fixed wage w) and are assigned routes, i.e., sequences of delivery tasks, bythe crowdsourced delivery platform. Ad-hoc couriers, on the other hand, arrive (at a randomlocation) according to a Poisson process with rate µ. Upon arriving, ad-hoc couriers select anorder (or no order) from a bulletin board of the current open orders according to a multinomiallogit (MNL) choice model. After selecting an order, ad-hoc couriers receive a payout pτ d which
is a function of the relative lead time and O-D distance of the order. We refer to the problemof minimizing the total cost over T as the Dynamic Hybrid Capacity Management Problem(DHCMP). The delivery platform then has to decide:
1. The number of committed couriers to hire at the start of the time horizon, M ;2. An order allocation policy that splits arriving orders between the two types of couriersystems;
3. The (dynamic) prices posted on the bulletin board for delivery tasks for ad-hoc couriers
denoted by P = {pτ d : ∀τ = 1, ..., B; s = 1, ..., S}; and4. A policy that manages the delivery routes of committed couriers.

3ANALYSIS

3.1

FLUID MODEL

To analyze the system in a tractable way, we propose a fluid (deterministic) model to approximate
the original stochastic system. In the fluid model, the states of all open orders at a specific time
are represented by a matrix, depicted in Figure 1, where L is the maximum relative lead time anddmax is the maximum possible distance between origin and destination. The row of the matrix

Figure 1 – An order status matrix illustrating how the states of all open orders are characterized
and the flow dynamics for a given state (L = 3 and dmax = 4.)
represents orders’ relative lead time, and the column represent orders’ service time. Parameterλτ d is the rate at which orders with a specific relative lead time and distance arrive the systemand Xτ d represents how many open orders have distance d and relative lead time τ . As time
passes, the relative lead time decreases, and for each unit of time that passes, the values in thematrix shift one column to the left. For simplicity, we define the decision variable yτ d to be therate at which orders transition to the subsequent cell. The fluid model approximates the system
in steady state, where each entry of the order status matrix reaches a flow balance, allowing us
to model the system as a deterministic optimization problem.
TRISTAN XI Symposium

Original abstract submittal

A. Behrendt, M. Savelsbergh and H. Wang

3

Utilizing this fluid approximation, we formulate multiple optimization problems to study
optimal policies for the DHCMP. Firstly, we formulate a pure ad-hoc courier system where theoptimal price is derived from the MNL choice model. We characterize the structure of thesolution to this formulation, and prove that this implies that the optimal price is non-decreasingin the relative deadline of an order (i.e. more urgent orders will have a higher price.) Secondly,
we formulate a pure committed courier system, where the number of couriers to hire, M , is adecision. Unlike an ad-hoc system where the rate at which orders are selected is constrained by
the arrival rate of couriers, the hiring decision M controls the maximum rate at which orders
can be served. We model this effect in a similar manner to Castillo et al. (2017) by introducing
a constraint which essentially splits the total number of committed couriers into those that areidle, currently delivering orders, or en-route to a pickup location. Next, we model two versionsof a hybrid system, a pooled and dedicated system. In the pooled system, committed and adhoc couriers select from the same pool of orders; in contrast, in the dedicated system, orders
are partitioned according to a rule in an irrevocable manner, namely, once an order has been
assigned to a courier type it cannot be changed.

3.2

COMPUTATIONAL RESULTS

We present some computational results in Figure 2 that illustrate how our analytical results ofthe fluid model translate to the original stochastic model in a simulation setting. Several order
allocation policies are considered in this simulation. In the pooled policy, all open orders areavailable for selection by ad-hoc or committed couriers. The random, JSQ and JSQ-condition
policies are all variants of a dedicated, irrevocable policy. When an order arrives, it is either
assigned to the ad-hoc or committed subsystems. For random, the assignment is dictated byprobabilities directly from the hybrid formulation (low distance orders have a higher probabilityof being assigned to the committed subsystem.) For JSQ, the order simply joins the subsystemwith the smallest current expected waiting time. Lastly, the JSQ-condition policy is simply theJSQ policy, under the condition that the order must below a fixed distance to join the committedqueue. Notice that the random policy does well in heavy traffic (defined by higher demand toFigure 2 – Total cost and expired order percentage under varying traffic intensity.
capacity ratios), as the benefit of utilizing committed couriers becomes more and more important
for reducing the number of expired orders (an order expires if it cannot be delivered at or before
its deadline). However in low traffic, cost is associated with assigning orders to the bulletin board
TRISTAN XI Symposium

Original abstract submittal

A. Behrendt, M. Savelsbergh and H. Wang

4

when they could have been served by committed couriers. While JSQ does not perform as wellas pooled or random in heavy traffic, we are able to leverage the benefit of intelligently selectingorders with specific characteristics (orders below a certain O-D distance) to go to the committed
subsystem with JSQ-condition. In turn, we can outperform a pooled system in both low andheavy traffic conditions by simply restricting the distances of orders in the committed system.
This results serves as motivation for the next section, where we present a method of taking
complex routing decisions into account when partitioning orders and show it further improves
our solutions.

4JOINT PARTITIONING AND ROUTING

Using the optimal prices for delivery tasks for ad-hoc couriers derived above, we consider joint
order partitioning and committed courier routing decisions in the DHCMP. We present a rollinghorizon approach. At the start of the time horizon, we first solve a single-stage optimization
problem for the fluid approximation of the hybrid system for the number of couriers hired M
and the price matrix P. Then, at each subsequent decision epoch, we formulate the decision
problem as a fixed fleet pickup and delivery problem with order dependent outsourcing costs.
Algorithm 1 illustrates the basic implementation of our column generation method to be executedat each decision epoch.
Algorithm 1: A column generation approach to joint routing and order allocation atdecision epoch t.
Data: gt : vector of expected costs of assigning each open order to the ad-hocsubsystem at time t.
colt−1 : the columns (feasible routes) found from the last decision epoch.
Result: routingPlan, adhocList
Init: startColumns ← truncate(colt−1 );improvingColumns ← basis(newOrders);columns ← startColumns ∪ improvingColumns
while improvingColumns ̸= ∅;doimprovingColumns ← dual_directed_search(newOrders, columns, gt );columns ← columns ∪ improvingColumns
routingPlan, adhocList = solve_IP(columns, gt );return routingPlan, adhocList

5DISCUSSIONIn sum, this work presents an integrated decision problem faced by crowdsourced delivery platforms using a hybrid fleet of committed and ad-hoc couriers, provides theoretical insight byintroducing and analyzing fluid formulations, proposes a column generation method for joint
order partitioning and routing, and validates the approaches outlined in this work with computational experiments. As such, this work is of interest to those engaged in modern logisticsresearch and industry partners.

References
Castillo, Juan Camilo, Knoepfle, Dan, & Weyl, Glen. 2017. Surge pricing solves the wild goose chase.
Pages 241–242 of: Proceedings of the 2017 ACM Conference on Economics and Computation.

TRISTAN XI Symposium

Original abstract submittal