Algorithms for the Vehicle Routing Problems with Time Deadlines

Publisher Website
Google Scholar
Abstract
The vehicle routing problem with time deadlines (VRPTD) is an extension of the classical vehicle routing problem (VRP) with constraints on the latest allowable time (deadline) for servicing each customer. The objective is to minimize the number of vehicles and the distance travelled without exceeding the capacity of the vehicles or violating the customer deadlines. VRPTD belongs to the class of NP-complete problems. As the computational time taken to solve such problems using exact methods is prohibitive, heuristic methods are used instead to obtain near optimal solutions for large-size problems. We develop three heuristics to solve the VRPTD: deadline sweep, push-forward insertion and genetic sectoring. The solutions obtained by these heuristics are improved using a local post-optimization procedure. Computational analysis of the three heuristics are reported on 25 problems consisting of 200 customers each with different geographical and temporal characteristics.