VEHICLE-ROUTEING WITH TIME WINDOWS AND TIME-VARYING CONGESTION

Abstract

This paper discusses vehicle-routeing and scheduling problems subject to time window restriction and time-varying traffic congestion. Time-varying congestion increases the complications of the problems and, in fact, makes it challenging even to find feasible solutions. Numerous heuristics have been developed for problems with time windows only, but few for those with both time windows and time-varying congestion. We identify a simple yet robust monotonicity property of arrival times, which allows us to simplify the computation. This property enhances the performance of existing heuristics. The feasibility check routines built upon this property considerably reduce computational burden.