A Traffic-Aware Time-Dependent Vehicle Routing Problem for Middle-Mile Deliveries under Uncertain Travel Time

Abstract

Urban freight distribution faces highly variable traffic conditions, where recurring congestion and unexpected disruptions can undermine delivery reliability and efficiency. This study develops a traffic-aware optimization framework for middle-mile urban logistics through a Stochastic TimeDependent Vehicle Routing Problem with Time Windows (STDVRPTW). The model integrates time-varying traffic conditions, stochastic travel-time disruptions, and customer service requirements within a unified framework. It is formulated as a two-stage stochastic program in which first-stage routing and scheduling decisions are evaluated across multiple traffic scenarios. To solve the large-scale problem efficiently, we propose an improved Benders decomposition algorithm with problem-specific valid inequalities that exploit the structure of time buckets and vehicle capacity constraints. Numerical results show that the proposed algorithm outperforms Gurobi and standard Benders decomposition. The findings also provide operational insights into how congestion pricing, delivery time-window flexibility, and fleet deployment interact, showing that pricing policies can encourage off-peak deliveries and changes in fleet utilization.