| Summary |
Kun-yu Ho, 2006.06
Institute of Transportation Technology and Management
National Chiao Tung University
The Vehicle Routing Problem with Time Window (VRPTW), an extension of the classical Vehicle Routing Problems (VRP), is 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 solve than the VRP. Therefore, most of the solution methods for VRPTW are heuristics or meta-heuristics.
The Threshold Accepting (TA) and the Great Deluge Algorithm (GDA) are two meta-heuristics that have been developed in early 90’s. In this thesis, we developed two solution methods combining TA and GDA with traditional construction and neighborhood search algorithm, to solve the VRPTW. Furthermore, we proposed a compound cost function which simultaneously calculates the value of surplus capacity and travel time into a single and normalized function while evaluating the exchange cost of movement.
We coded the computer programs in Visual C++, and tested on a 3G-Hz PC with Windows XP Operation System. A bank of Solomon’s 56 benchmark VRPTW instances was utilized to identify the performance of these TA and GDA methods. Results showed that the compound cost function is more effective than traditional cost function on solving VRPTW. As compared to the GDA-based method, the TA-based method implemented significantly more efficient and yielded results with slightly less number of vehicles required but about 2% more distance traveled.
As to all of the 56 instances tested, the best solutions found by our proposed TA and GDA methods are respectively 418 vehicles and 57515.52 distance units. The average deviation of required vehicles is 0.21, and the average deviation of distance percentage is 1.87%. In sum, the performance of proposed TA and GDA methods is of competition to other meta-heuristics.
|
