An overview of a heuristic for vehicle routing problem with time windows

In this paper, a two-stage metaheuristic based on a new neighborhood struct ure is proposed to solve the vehicle routing problem with time windows. Our neighborhood construction focuses on the relationship between route(s) and node(s). Unlike the conventional methods for parallel route construction, we construct routes in a nested parallel manner to obtain higher solution q uality. Computational results for 60 benchmark problems are reported. The r esults indicate that our approach is highly competitive with all existing h euristics, in particular very promising for solving problems with large siz e. (C) 1999 Elsevier Science Ltd. All rights reserved.