A Hybrid Search Alogrithm for the Vehicle Routing Problem With Time Windows

The vehicle routing problem with time windows (VRPTW) is an extension of the well-known vehicle routing problem (VRP). It involves a fleet of homogeneous vehicles, originating and terminating at a central depot, with limited capacity and maximum travel time to service a set of customers with known demands and service-time windows. The objective is to find a set of feasible routes that minimizes the total costs using some measures of solution quality. This paper focuses on the study of a hybrid of two search heuristics, Tabu Search (TS) and Genetic Algorithm (GA) on VRPTW. TS is a local search technique that has been successfully applied to many NP-complete problems. On the other hand, GA which is capable of searching multiple search areas in a search space is good in diversification. In this paper, we create a hybrid that combines the strengths of the two search heuristics. Experimental results indicate that such a hybrid outperforms the individual heuristics alone.