Urban Pickup-and-Delivery VRP with Soft Time Windows Under Travel-Time Uncertainty: An Empirical Comparison of Robust and Deterministic Approaches

Urban freight pickup-and-delivery services operate in road networks where travel times are highly variable due to congestion, incidents, and operational restrictions. Such variability threatens the punctuality of deliveries and complicates the design of reliable service schedules. This paper examines an urban pickup-and-delivery vehicle routing problem with soft time windows under travel-time uncertainty and provides an empirical comparison of robust and deterministic planning approaches on a real road network. The problem is formulated as a time-dependent pickup-and-delivery VRP with soft time windows, where link travel times are represented by a finite set of scenarios calibrated from observed network conditions. The objective function combines four components that are central to urban freight operations: total travel time, total distance, and penalties for earliness and lateness relative to customer time windows. This structure captures the trade-off between routing efficiency and service quality. On this basis, a robust model is constructed that optimises tour plans with respect to scenario-based worst-case or risk-aggregated costs, while a standard deterministic model minimises the same objective using nominal (average) travel times only. An empirical study on a real urban network compares the deterministic and robust solutions with respect to delivery punctuality, tour length, and time-window violations across a range of demand and variability settings. The results show that robust routing systematically reduces the frequency and magnitude of late deliveries at the expense of only moderate increases in planned distance and travel time. Although energy use and emissions are not modelled explicitly, the improved reliability and reduced need for reactive re-routing indicate a potential to support more reliable and resource-efficient urban freight operations in the context of sustainable city logistics.