The following article addresses a complex combinatorial optimization and integer-programming problem, referred to as the vehicle routing problem, which is typically related to the field of transportation logistics. The aim of the research is to combine a set of objective functions, number of common generalizations and extensions of the problem, arising in distributed services or goods supply. For this purpose, literature on the subject has been analysed, leading to the mathematical modelling method being applied. At the current moment such complicated variants of the problem present high importance for research because of both practical applications and high complexity. The paper proposes a new generalized multi-objective vehicle routing problem with multiple depots and heterogeneous vehicles fleet with regard to various factors affecting costs. The problem statement is presented as a mixed integer linear program. Objectives scalarization approach is proposed in order to reduce decision-maker participation. Shortcomings of the single-criterion formulation and negative effects of replacing the criteria with constraints are shown. The results provide initial data for solving a large number of transportation problems that are reduced to the vehicle routing problem. In particular, the application of the ant colony optimization as a method for solving the problem is discussed.