Integrating parking delay uncertainty in urban delivery tour planning

Securing curb space near a delivery location is a major source of uncertainty for urban commercial vehicle drivers. While tour planning tools increasingly account for time-dependent traffic conditions, they typically ignore parking delays, even though evidence shows they vary systematically across locations and times of day. This paper empirically examines how expected parking delays affect urban delivery tour planning. Using GPS data from real-world delivery operations, we estimate time- and location-specific parking delays and incorporate them into a Time-Dependent Traveling Salesman Problem with Time Windows. We compare conventional parking-blind planning, which considers only travel times, with parking-aware planning, which additionally accounts for expected parking delays. The results show that parking-blind planning substantially underestimates tour duration and overestimates schedule feasibility. When realistic parking conditions are considered, parking delays accounted for about 33% of total delivery tour duration and generate substantial increases in lateness and time-window violations. Parking-aware planning reduces tour duration by 3.4% on average (17.4 min), with some instances obtaining total tour duration reductions of more than 10%, by trading slightly longer driving times for lower parking delays, while reducing time spent in parking delays by 11% on average. More importantly, it substantially improves service reliability, reducing average lateness and greatly decreasing the frequency of time-window violations. These improvements are achieved primarily through small adjustments in stop sequencing and service timing that shift deliveries toward periods with lower expected parking delays.