The paper deals with the Fleet Composition Problem (FCP) for a 2-echelon fuel distribution system, composed of a fuel regional warehouse (depot) and 100 gas stations (customers). The customers’ orders include random quantities of 4 types of fuel, which are distributed by a specialized fleet of road tankers. The fleet includes 4- and 8-chamber tankers that are characterized by different load capacities and fixed and variable costs. Since different types of fuel cannot be mixed together during transportation process specific assignment of orders (transportation tasks) to the vehicles (their chambers) is required. The decision problem consists in composing an optimal fleet of tankers, i.e. in defining optimal types of tankers to be used and an optimal number of vehicles in each type. It is considered as a vehicle assignment problem in which different types of vehicles are assigned to customers’ orders and formulated as a single objective mathematical programming problem, where the optimization criterion is a total daily distribution cost. Two alternative formulations of the decision problem are proposed, based on different definitions of the vehicles to be assigned to transportation tasks. To solve the problem, represented by both formulations, specialized alternative heuristic procedures are constructed. They are based on: local search (LS), evolutionary algorithms (EA) and hybrid algorithm (LS + EA). Computational experiments are carried out and their results are presented and compared in the paper.