Soft Time-Window Constraints in Crystal-Ice Distribution: A Cheapest-Insertion VRPTW Case Study with Non-Refrigerated Vehicles

Abstract

Abstract

Perishable product distribution requires efficient route planning because delivery duration, route sequence, and transportation conditions directly affect product quality, service reliability, and operational performance. This study evaluates hard and penalty-based soft time-window routing for crystal-ice distribution in a small-scale enterprise distribution system comprising one depot, 60 scheduled customers, and two non-refrigerated vehicles. A quantitative computational case-study approach was applied using the Vehicle Routing Problem with Time Windows (VRPTW) and the Cheapest Insertion Heuristic (CIH). Soft time-window performance was evaluated using lateness penalties of λ = 0.1, 0.5, 1, 2, and 5 km/min. The hard time-window solution produced a fleet distance of 86.87 km and zero lateness. At λ = 0.1, the soft model reduced the fleet distance to 85.29 km but generated 8.95 minutes of total lateness across two customers. Increasing the penalty to λ = 0.5 eliminated all lateness and produced the same 86.87-km route as the hard model. Compared with the observed company baseline, the selected zero-lateness route reduced fleet distance from 99.84 to 86.87 km (12.99%) and route exposure duration from approximately 1,200 to 1,043.59 minutes (13.03%). Model-estimated product loss decreased from an observed baseline of 580 kg to 507.95 kg, corresponding to an estimated reduction of 72.05 kg (12.42%). These findings show that soft time-window penalties can reveal the trade-off between marginal distance savings and service punctuality.