  One of the recent innovations in urban distribution is crowdsourced delivery,
where deliveries are made by occasional drivers who wish to utilize their
surplus resources (unused transport capacity) by making deliveries in exchange
for some compensation. The potential benefits of crowdsourced delivery include
reduced delivery costs and increased flexibility (by scaling delivery capacity
up and down as needed). The use of occasional drivers poses new challenges
because (unlike traditional couriers) neither their availability nor their
behavior in accepting delivery offers is certain. The relationship between the
compensation offered to occasional drivers and the probability that they will
accept a task has been largely neglected in the scientific literature.
Therefore, we consider a setting in which compensation-dependent acceptance
probabilities are explicitly considered in the process of assigning delivery
tasks to occasional drivers. We propose a mixed-integer nonlinear model that
minimizes the expected delivery costs while identifying optimal assignments of
tasks to a mix of professional and occasional drivers and their compensation.
We propose an exact two-stage solution algorithm that allows to decompose
compensation and assignment decisions for generic acceptance probability
functions and show that the runtime of this algorithm is polynomial under mild
conditions. Finally, we also study a more general case of the considered
problem setting, show that it is NP-hard and propose an approximate
linearization scheme of our mixed-integer nonlinear model. The results of our
computational study show clear advantages of our new approach over existing
ones. They also indicate that these advantages remain in dynamic settings when
tasks and drivers are revealed over time and in which case our method
constitutes a fast, yet powerful heuristic.
