Crowdsourced delivery utilizes the services of independent actors. As opposed to traditional modes of delivery, availability and acceptance decisions of crowdshippers are uncertain and cannot be fully controlled by an operator. We consider a setting in which an operator groups tasks into bundles and in which the resulting bundles are offered to crowdshippers in exchange for some compensation. Uncertainty in the crowdshippers' behavior who may accept or reject offers is considered via (individual) acceptance probabilities. For the latter, we consider generic probability functions whose main parameters are the compensation offered, the number of tasks in a bundle, and the total detour to deliver a bundle. The objective of the resulting optimization problem is to minimize the expected total cost of delivery. We propose a mixed-integer non-linear programming (MINLP) formulation that simultaneously decides (i) how to group tasks into bundles, (ii) which bundles are offered to which crowdshipper, and (iii) the compensation offered for each bundle. We show that this MINLP can be reformulated as a mixed-integer linear program with an exponential number of variables. We present a column generation algorithm for solving instances of the latter whose pricing subproblem corresponds to an elementary shortest path problem with resource constraints (ESPPRC) and a nonlinear objective function. We develop a tailored algorithm for this variant of the ESPPRC that exploits theoretical bounds we derive on the routes of the crowdshippers. The preliminary computational experiments show that the algorithm is capable of solving large instances in a reasonable amount of time.
Please mind the date and time of this seminar!