Joint Optimization of Incentive and Routing for Crowdsourced Last-mile Delivery

Abstract

This study presents a pioneering model, the Crowdsourced Incentive-Driven Vehicle Routing Problem with Time Windows (CS-IDVRPTW), designed to jointly optimize routing and incentive strategies for the crowdsourced last-mile delivery. This model uniquely considers the order acceptance probability of crowd-carriers, which is influenced by incentives and detour distances. The CS-IDVRPTW model is constructed as a Mixed Integer Nonlinear Programming (MINLP) problem with the objective of minimizing total expected delivery costs. The model is formulated into two versions: an arc-based formulation and a route-based formulation. Based on the route-based formulation, we propose a branch-and-price-and-cut (BPC) algorithm to obtain the exact solution. Extensive numerical studies validate the algorithm’s ability to consistently yield optimal solutions with notable efficiency, outperforming commercial solvers such as Gurobi across various instances. Lastly, a sensitivity analysis is conducted, investigating the impact of crowd-carriers’ order acceptance probability under different additional incentives and detour distance sensitivities.