The paper aims at obtaining an optimal route of a fleet of oildelivery tankers from a source to a number of service stations. The distance between any two stations and demand(s) for each station are given. The objective is to find an optimal route undertaken by tankers such that the requirements of stations are met, the total distance travelled by the Tankers and the backload of the Tankers is to be minimized under the considerations. Also, the Tanker should visit a pair of stations exactly once. Further, a tanker does not supply the requirements of the stations partially. Here the tanker carries back the residue to the depot the available amount of oil will be considered as Backload or undelivered oil when the Tanker returns to depot (source station) or the maximum utilization of the capacity of Tankers in a trip schedule. Dantzig and Ramser-[4] investigated the problem of "The Truck Dispatching Problem" without the minimum backload and obtained a near optimal solution with the dynamic programming approach. For obtaining the optimal solution of the same problem with minimum backload, we proposed the Lexicographic Search approach. The algorithm is tested using C-language and the computational details are also reported, observed that it takes less computational time for higher size of problems.