This paper addresses on a delivery problem of fuelproducts, i.e., gasoline, kerosene, and diesel oil, from asupply point to a number of destination points. Thedelivery is performed using tankers having somecompartments. Each compartment is dedicated to a certainfuel product type. A solution of the problem is todetermine a tanker’s routing plan for delivering the fuelproducts in order to fulfill the objective functions with thefollowing priority order: minimizing number of tankers,minimizing total completion time, and minimizing rangeof tour completion time. The routing problem discussed inthis paper is considered as a variant of vehicle routingproblems (VRPs) which has the following characteristics:split delivery, multiple routes (multiple trips), andmultiple products and compartments. A local searchtechnique is proposed as a solution technique for theproblem. The local search technique consists ofmechanisms for generating an initial solution andsearching candidate solutions. The initial solution isgenerated using a sequential insertion algorithm. In thesearching mechanism, relocation and exchange operatorsare used to generate candidate solutions. The solutiontechnique is applied in a numerical example of the fueldelivery problem.