Analysis of the Degree of Difficulty in Solving Vehicle Routing Problem with Time Windows

Vehicle routing problem with time windows (VRPTW) is a well-known NP-complete problem in operational research and computer science. In the literature, a great amount of research has been focused on various genetic algorithms (GAs) to solve VRPTW. However, little attention is made to measure to what degree a particular instance of VRPTW is difficult when GA is used. In this paper, fitness distance correlation (FDC) analysis is adopted to predict the problem difficulty of a given instance of VRPTW, being able to guide the design of well-suited GAs. Solomon´s R1 instances are used as test instances and the FDC results shows all the instances are classified as deceptive and misleading problems where fitness increases with distances decreasing.