Package routing problem with registered couriers and stochastic demand

Providing the crowd-sourced delivery capacity and hence enabling the practice, occasional couriers (OC) are the most critical resource in crowd-shipping (CS). Therefore, as well as establishing and retaining a solid OC base, using the OC trips efficiently is of utmost importance for the viability of the CS applications. One auspicious idea to enhance the efficiency, i.e., cover a larger demand set with the available OC trips, is to use transshipments (deliver packages with a coordinated effort of OCs) and collect OC trip information in advance to efficiently coordinate them, which gives rise to the package routing problem with registered couriers (PRP-R) we introduce in this paper. In particular, we study a CS model in which the couriers register their trips in advance while the express shipping demands arrive through a stochastic process, and the network management needs to dynamically decide package-courier assignments to carry out deliveries in the most efficient way. We develop a novel rolling horizon algorithm to solve this challenging problem in real-time, which explicitly considers the limited OC capacities and use of a back-up delivery capacity (company-owned or third party provided) to ensure the service quality. Beyond the classical rolling horizon approaches, the suggested methodology uses a novel Monte Carlo procedure to take anticipated future system conditions into account, and thus can provide package-courier assignments that have almost the same cost with the optimal solution of the static version of the problem where all demand arrivals are known a-priory. The comprehensive numerical experiments attest to the efficacy of our methodology for the real-time management of the CS operations and provide significant managerial insights about the design of CS networks.