A thesis submitted in partial fulfilment of the requirements for the degree of Master of Engineering, School of Advanced Technologies

Thesis (M.Eng.) - Asian Institute of Technology, 1998

In this study, a solution for a large scale fleet sizing vehicle routing problem ( FS VRP ) has been presented which occurs in a major LPG distribution company in Hochiminh City. The company serves more than 200 customers with different amounts of order and at different frequency. The schedule needs to be made over one week horizon. Optimal fleet size is also considered in the general context that minimizes the total distribution cost. A mathematical model of the type mixed integer program ( MIP ) is applicable to very small size problems ( composed of from five to ten customers on two days ). Mathematical approach has proved to be impractical for real life situations. Therefore, a tabu search based heuristic which consists of three phases has been proposed. In phase 1, a goal programming model to decompose a multiple period VRP into some single period VRPs has been established. Phase 2 determines a set of routes which are required to visit all customers each day of the period. Dispatching of routes to vehicles in the fleet has been presented in phase 3. Tabu search technique is applied for phase 2 and phase 3 . As an outcome of the heuristic, the number of trucks, the number of customers each day and the sequence of each delivery route are obtained. Tabu search heuristic is tested with some available benchmark problems. In all cases, it obtains exactly the same or very close to the best solution known. Some elements of tabu search are also studied in order to improve the quality of search process.