| Summary |
Chuen-Yih Wang,2007.08
Department of Transportation Technology and Management National Chiao Tung University
Vehicle Routing Problem with Time Windows (VRPTW), an extension of the classical Vehicle Routing Problem (VRP), has been widely applied to logistics and home delivery. The VRPTW considers that customers request the carrier to serve them within a specific time interval, i.e. time window. Such a constraint makes the VRPTW harder to slove than the VRP. Therefore, most of the solution methods for VRPTW are heuristics or metaheuristics.
The objective function of the VRPTW considered combines the minimization of the number of vehicles (first priority) and the total travel distance (second priority). Our research is based on the two-phase hybrid metaheuristics introduced by Homberger and Gehring (2005). The aim of the first phase is the minimization of the number of vehicles by means of a (μ, λ)-evolution strategy, and in the second phase, the total distance is minimized using Backtracking Adaptive Threshold Accepting (BATA) proposed by Tarantilis et al. (2001). Solomon’s 56 benchmark VPRTW instances were utilized to evaluate the performance of this hybrid evolutionary metaheuristics.
In this thesis, we propose a vehicle saving acceptance rule to enhance the performance of (μ, λ)-evolution strategy. In BATA, we test several combinations of parameters and improvement methods. All the experiments of this metaheuristics are coded in C# and implemented on a computer with AMD Athlon(tm) 64 Processor 3000+.
As to all of the 56 instances tested, the total number of vehicles of the best solution found by our proposed hybrid evolutionary metaheuristics is 416, and the total travel distance is 58001.90. As compared to the best known solutions of the benchmark instances, the average deviation of required vehicles is 2.97%, and the average deviation of total distance is 2.41%. Among those 56 benchmark instances, we have found the best known solutions in 10 instances. |
