A Branch-and-Benders Cut Algorithm for a Stochastic Service Network Design with Crowdsourced Capacity
- 1 March 2026
- journal article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Transportation Science
- Vol. 60 (2) , 316-342
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 [ ]-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.Keywords
This publication has 53 references indexed in Scilit:
- An exact algorithm for the service network design problem with hub capacity constraintsNetworks, 2022
- Network Design with Applications to Transportation and Logistics2021
- Crowd-Based Business Models2021
- Scheduled service network design with resource acquisition and managementEURO Journal on Transportation and Logistics, 2018
- Stochastic dual dynamic integer programmingMathematical Programming, 2018
- The Vehicle Routing Problem with Occasional Drivers and Time Windows2017
- Sharing EconomyBusiness & Information Systems Engineering, 2016
- Introduction to Stochastic Programming2011
- Service network design for freight transportation: a reviewOR Spectrum, 2007
- Partitioning procedures for solving mixed-variables programming problemsNumerische Mathematik, 1962