ABSTRACT

One of the well known problems in distribution is the Vehicle Routing Problem (VRP). In this problem, vehicles start their tours from a depot, they visit the customers and finish their tours in the depot again. There are several variants of VRP. Fuel distribution provides a different kind of VRP which is called as Multi Compartment Vehicle Routing Problem (MCVRP). In MCRVP vehicles have compartments and incompatible petroleum products are delivered in different compartments of a vehicle. For both of the problems solution methods can be classified into two categories; route construction heuristics and improvemenet heuristics. While there is a significant literature on VRP regarding these heuristics, the literature on MCVRP is much more limited. The aim of this study is to offer a construction heuristics for a fuel distribution problem in Turkey. The problem has some features such as compartments, visiting customers more than once and tolerance which turns it into a MCVRP problem. Savings Algorithm (SA) and a loading algorithm is integrated to develop a construction heuristics for the problem. Proposed heuristics is tested on test problems and acceptable results obtained when compared with the literature. A real life fuel distribution problem is solved with the propsed heuristics and significant cost reduction has been achieved. The proposed method can be used as a construction method in MCVRP and as a practical solution for real life problems in fuel distribution in Turkey.