| Summary |
Tai-Yi Wu, 2006.07
Institute of Transportation Technology and Management
National Chiao Tung University
Under strong market competition, the goal of the distributors is to satisfy the needs of the customers rapidly at the lowest cost. Considering the demand of the customers and the operational constraint such as vehicle capacity and time requirement, the distributors can significantly raise their competitiveness, if they can determine the economical routes for delivery with low transportation cost. The most important study in this area is the vehicle routing problem (VRP).
We used the well-known set covering problem (SCP) to model the vehicle routing problem and developed a Lagrangian relaxation based heuristics. We also adopted the concept of column generation (CG), enerating a partial set of feasible routes to be the solution space.?The solution space is carefully adjusted through the iterative solution procedure to contain relatively better routes, and the solution found is subsequently improved. To sum up, the major contribution of this study is to design a simple but effective Lagrangian relaxation based heuristics, which contains only few routes in the solution space, to alleviate the computational load and to find the near optimal solution in a short period of time.
The numerical experiment is carried out with respect to the popular vehicle routing test problem set in the literature. This heuristic algorithm has good and stable performance in the experiment, and the heuristic solutions are closely to the optimal solutions. The extension of this research can be focused on refining the heuristic algorithm and on developing the algorithm for various versions of the vehicle routing problems. |
