Vehicle Routing Problems With soft Time Windows: Analysis of Computational Complexity and Sensitivity

Abstract

A unified VRPwithtimewindows framework is presented in which four normalized penalty schemeslinear, stepwise, quadratic, and exponentialare compared on a common 300-unit ceiling at ?30 min. Each scheme is implemented in Python/Gurobi, calibrated for uniform maximum cost, and applied to a 10-customer test instance solved to optimality in under 0.3 s per run. Comparative analysis is performed to demonstrate how non-linear penalties allow controlled timing deviations to reduce travel distance, whereas the linear rule enforces strict punctuality. A penalty-aware ALNS meta-heuristic is also proposed for larger instances, with custom destroy/repair operators designed to balance distance and soft time-window penalties.