A two-stage stochastic programming method for a heterogeneous vehicle routing problem with time windows and stochastic demand

This study addresses a heterogeneous vehicle routing problem with time windows and stochastic demand (HVRPTWSD), motivated by real-world logistics operations at JD Logistics. The research develops strategic delivery solutions under demand uncertainty while incorporating heterogeneous fleet, time window constraints, and multiple operational factors. We propose two modeling approaches: a primary stochastic programming with recourse (SPR) using a no-split detour to depot policy, and a comparative chance-constrained programming (CCP). Our SPR method advances existing VRPTWSD research by incorporating previously simplified constraints, including actual vehicle speed, service time, and multiple depot return trips, through a simulation-based recourse procedure. To solve these models, we develop an improved hybrid algorithm combining variable neighborhood search with simulated annealing. The algorithm features four key improvements: a local search procedure allowing infeasible solutions, a Makefeasible function, a flexible recourse procedure, and a restart mechanism. Comparative experiments on Solomon's VRPTW benchmark instances validate the algorithm's effectiveness compared to four other competing algorithms. Results show that SPR consistently outperforms CCP, particularly under high demand uncertainty and strict capacity chance constraints. In the real-world case study, SPR solutions achieve an average cost reduction of 2.35 % compared to CCP solutions. The proposed SPR method significantly reduces fleet operating cost while effectively addressing real-world demand uncertainties, providing enhanced practical applicability through its flexible recourse procedure.