Abstract—A hybrid tabu searchalgorithm, which generates initial solution by Genetic Algorithm, is proposedhere to solve the vehicle routing problems with time windows (VRPTW).Experimental result shows that this algorithm is better than the other knownalgorithms.

Keywords-vehicle routing problems with time windows (VRPTW);hybrid tabu search algorith; genetic algorithm
                                                                                                                                                                I. Introduction

Inthe classical vehicle routing problem (VRP), which was proposed by Dantzig andRamser(1959), customers with known demands and service time are visited by ahomogeneous fleet of vehicles with limited capacity and initially located at acentral depot. Routes are assumed to start and end at the depot. The objectiveis to minimize total traveled distance, such that each customer is servicedexactly once (by a single vehicle), total load on any vehicle associated with agiven route does not exceed vehicle capacity and route duration combiningtravel and service time is bounded to a preset limit.

Theproblem (VRPTW) addressed here can be described as the special problem of VRP,in which the routes must be designed in such a way that each point is visitedonly once by exactly one vehicle within a given time interval, all routes startand end at the depot. Since a lot of problems in the actual life can be modeledas VRPTW, such as postal service delivers, the train or the bus schedule, whosehandles the goodness and badness will have direct impact to the service qualityarriving at enterprise. So this problem attracts a lot of focus.

Manyheuristic algorithms are capable of giving feasible solutions for VRPTW.Heuristics search strategies based on Genetic Algorithms (Bräysy, 2001),Simulated Annealing (Chiang, 1996), Tabu Search (Bräysy, 2001) and ant colonyalgorithm (Zhi, 2005) have been explored in recent years in order to improvethe solutions. All these algorithms can help to obtain better solutions forVRPTW. In this paper, the solution of hybrid Tabu search algorithm, which isthe hybrid of generic algorithm and Tabu search algorithm, is presented tosolve VRPTW.