Abstract
Vehicle routing problem plays an important role in logistic management. The objective of a vehicle routing problem is to minimize the fleet traveling distance and the utilization of fleet numbers, so it will decrease the physical distribution cost. With the practical environment changing, more constraints will increase the complexity of vehicle routing problem. Vehicle routing problem has been studied for more than forty years, and many researchers have used different approaches to solve this problem. Two-phased method is often used to solve a vehicle routing problem. The first phase is to use simple heuristic algorithm to obtain initial routes, and the second phase is to improve the quality of initial solution. We use a greedy algorithm and a column generation method to solve multi-depot and multi-trip vehicle routing problem. According to Skitt and Levary (1985), they constructed a linear problem to model a multi-depot and multi-trip vehicle routing problem. The column represents the route, and they construct another integer programming problem as sub-problem to generate new route. We calculate different size of problem and compare with the result obtained by Skitt and Levary. Our experimental result shows that using column generation method can get solution efficiently. Keywords: vehicle routing problem, column generation.