Formulation of the Vehicle Routing Problem and Analysis of Algorithms for its Solution.

In the current study the Travelling Salesman Problem (TSP) and its modification with the condition of using several cars - the Capacitated Vehicle Routing Problem with Time Windows (CVRPTW) have been considered. Since these problems belong to the class of NP-hard problems, exact solution algorithms cannot have a time complexity less than exponential, therefore, in addition to exact solution algorithms, there are approximate ones: heuristic and metaheuristic algorithms. In the practical section of the study the CVRPTW has been applied to the data on the delivery of goods from the construction hypermarket Leroy Merlin, which is located in Perm. The least expensive routes for the company in the CVRPTW have been obtained using the savings algorithm and the Christofides algorithm. In addition, it has been estimated that the increase in the company's costs would entail an additional payment for customers who want to receive delivery in short and specific time intervals in excess of the basic cost of delivery.