Solution problem of routing in transport network using pseudopolynomial model

Abstract

Solution of the vehicle routing problem lies in building routes from a motor transport enterprise to a certain number of consumers located in a geographic space. Development of efficient distribution systems allows minimizing delivery costs, which is an important trend in improving the work of an enterprise under present-day economic conditions, in order to provide sustainable transport links between consumers to ensure competitiveness in the transport services market. The article considers the problem of vehicle routing when serving consumers on several routes, taking into account time windows. It is considered that a vehicle can be assigned to work on more than one route during the planning period (working day). The algorithm for solving the problem is iterative based on the use of a pseudopolynomial network flow model where nodes represent points in time with the arcs showing the possible routes of vehicles. The algorithm was tested on a dataset of five consumers and two vehicles. It is also worth noting that the capacity of vehicles is a variable that has a significant impact on obtaining the optimal solution to the problem. In further research aimed at finding methods for solving the routing problem, it is recommended to take into account the value of fixed costs associated with the use of vehicles, since it has a significant impact on the cost minimization function if applied in practice. The proposed method makes it possible to consider this moment since the mathematical model and algorithm take account of the expenses in the objective function.