Dynamic Empty-Vehicle Repositioning on Long-Haul Freight Corridors: Lower Bounds and Rolling-Horizon Policies Under Lead Times and Time Windows

Empty-vehicle repositioning is a persistent challenge in long-haul road freight because carriers must reduce empty mileage without sacrificing service reliability under lead times, appointment windows, and uncertain load realization. This paper formulates empty-vehicle repositioning on freight corridors as a stochastic control problem with explicit space–time feasibility and a stated within-epoch event order. Lead times couple current dispatch decisions to future capacity, pickup windows impose reachability constraints, and stochastic match feasibility captures information and market frictions. We develop dynamic lower bounds from time-expanded relaxations, showing that dual prices of inventory-balance constraints can be interpreted as space–time scarcity values. We further introduce an order-dependent nested friction decomposition that separates excess empty movement into spatial imbalance, temporal mismatch induced by lead times and time windows, and information frictions. Guided by this structure, we propose price-guided rolling-horizon and generalized-cost policies and evaluate them on synthetic corridor experiments organized around the three friction families. The results reveal service–empty-mileage trade-offs, a pronounced knee in the Pareto frontier, lower service loss under widened tight pickup windows, and strong sensitivity to match feasibility. The PG-RH policy reduces empty-distance exposure and total cost relative to static balancing in the main scenarios while maintaining comparable, but not uniformly dominant, service performance. The framework provides a diagnostic basis for identifying the sources of deadhead and for designing operational interventions that reduce empty mileage without undermining reliability.