¹Yonsei University, Seoul, Korea

Correspondence: YH Lee, Department of Information and Industrial Engineering, Yonsei University, 134 Shinchon-Dong, Seodaemoon-Ku, Seoul 120-749 Korea. E-mail: youngh@yonsei.ac.kr

Received August 2005; Accepted March 2007; Published online 6 June 2007.

Abstract

The vehicle fleet mix problem is a special case of the vehicle routing problem where customers are served by a heterogeneous fleet of vehicles with various capacities. An efficient heuristic for determining the composition of a vehicle fleet and travelling routes was developed using tabu search and by solving set partitioning problems. Two kinds of problems have appeared in the literature, concerning fixed cost and variable cost, and these were tested for evaluation. Initial solutions were found using the modified sweeping method. Whenever a new solution in an iteration of the tabu search was obtained, optimal vehicle allocation was performed for the set of routes, which are constructed from the current solution by making a giant tour. Experiments were performed for the benchmark problems that appeared in the literature and new best-known solutions were found.