Solution Improvement Heuristics for the Vehicle Routing and Scheduling Problem with Time Window Constraints

SYNOPTIC ABSTRACT

Branch exchange techniques, such as the well-known 2-opt and 3-opt procedures, are among the most powerful heuristics available for the solution of the classic vehicle routing problem. The imposition of time window constraints on customer delivery time within the vehicle routing problem, however, introduces several complexities that can reduce the power of these techniques. In this paper, two test data sets for the vehicle routing and scheduling problem with time window constraints are studied. Initial solutions are obtained using a variety of heuristics. These solutions are then improved using branch exchange procedures modified to incorporate the time window constraints.

Key Words and Phrases:

• vehicle routing and scheduling
• time window constraints
• branch exchange heuristics