A Branch-and-Benders Cut Algorithm for a Stochastic Service Network Design with Crowdsourced Capacity

Abstract

We explore the stochastic service network design problem of an intracity courier service provider. To efficiently fulfill delivery tasks, the courier company employs a hybrid fleet consisting of contracted drivers, crowdshippers, and third-party drivers based on a planning framework that takes into account uncertainty in terms of demand and transportation capacity offered by crowdshippers. At the tactical level and taking into account future demand and crowdshipper capacity estimations, the courier company acquires transportation capacity through the forward market at a relatively low rate. At the operational level, however, once the demand and the available crowdshipper capacity are revealed, the courier company may supplement the existing transportation capacity by acquiring through the spot market and/or by employing crowdshippers. We model the problem at the tactical level as a two-stage stochastic problem with integer variables in both stages and develop a branch-and-Benders-cut with partial Benders decomposition approach to solve the model. In our solution framework, we incorporate the classical Benders decomposition, integer L-shaped method, and Benders dual decomposition to generate different types of optimality cuts. To improve the efficiency of our method, we employ accelerating strategies such as selective subproblems, parallelism, and [Formula: see text]-optimality. Further, to study the effect of possible plan revisions, we propose a partially adaptive stochastic programming approach that allows for a limited number of tactical-level plan adjustments given the extra information revealed at the operational phase. We quantify the benefits of such updates and evaluate the effect of the frequencies at which such updates are performed.