| Summary |
Chung-Hao Chen , 2008.06
Department of Transportation Technology and Management National Chiao Tung University
Vehicle Routing Problem with Backhauls and Time Windows (VRPBTW), an extension of the classical Vehicle Routing Problem, is a very complicated NP-Hard problem. The VRPBTW assumes that all linehaul customers should be visited before any backhaul customer, and all customers need to be visited within a specific time window.
In this thesis, we proposed a two-phase approach to solve the VRPBTW problems. In the first phase, we transformed the VRPBTW problems to approximate VRPB problems, removing the time window constraints from the original problems. We also proposed Problem Scale Simplification Strategy to reduce the size of the transformed VRPB problems. The second phase is focused on solving the transformed VRPB problems using a meta-heuristic approach. A feasible initial solution was first generated by Nearest Neighbor algorithm, and improved by neighborhood search methods such as Reduction, 1-0, 1-1, S-S, Or-opt. We then applied Backtracking Adaptive Threshold Accepting (BATA) to further improve the solutions.
The 15 benchmark problems described by Gelinas et al. (1995) were selected for the evaluation of our meta-heuristics. Our proposed heuristics were coded in Visual C# and tested on a Intel(R) Core(TM)2 CPU 2.00GHz personal computer. We found that our proposed Problem Scale Simplification Strategy can effectively reduce the number of nodes and arcs by 15.3% and 97.3% respectively on average. Results showed that for the 15 benchmark problems, the average deviation from the best known solutions are 0.87 in fleet size, and 5.32% in total distance respectively. We also found five best known solutions of the 15 VRPBTW benchmarks. The results of our study implied that our proposed time window discretization approach is most effective for solving VRPBTW problems with uniform and relatively small time windows. |
