Open AccessОГЛЯД ЗАВДАНЬ МАРШРУТИЗАЦІЇ, ЩО ЗВОДЯТЬСЯ ДО ЗАДАЧІ КОМІВОЯЖЕРА
Author(s) -
Ольга Борисовна Маций
Publication year - 2020
Publication title -
otkrytye informacionnye i kompʹûternye integrirovannye tehnologii
Language(s) - English
Resource type - Journals
eISSN - 2663-2411
pISSN - 2071-1077
DOI - 10.32620/oikit.2019.86.11
Subject(s) - travelling salesman problem , vehicle routing problem , routing (electronic design automation) , computer science , 2 opt , mathematical optimization , traveling purchaser problem , set (abstract data type) , task (project management) , process (computing) , bottleneck traveling salesman problem , operations research , mathematics , engineering , computer network , systems engineering , programming language , operating system
The solution to the problem of improving the management of the transport process depends not only on the level of modernization of vehicles and the degree of use of modern information technologies, but also on the choice of routes that reduce the cost of transporting goods and passengers. Actual working conditions of vehicles in road networks put forward a number of tasks for optimizing closed routes, which are based on the classic routing problem (VRP - Vehicle Routing Problem).VRP is one of the generalizations of the hard-to-solve traveling salesman problem. The traveling salesman task is NP-complete. It refers to the main tasks of combinatorial optimization and, forming a continuously replenished set of applications and generalizations, remains an urgent research topic. An exact solution to the traveling salesman problem can be found only by reducing the enumeration of the type of branches and boundaries, which are not always applicable in operational planning by vehicle traffic. Therefore, the development of new and improvement of currently known methods for solving routing problems, reducible to the traveling salesman problem, and their software implementation is both a theoretical and practically important problem.The article considers the class of routing problems reducible to the traveling salesman problem. It is shown that optimization tasks for closed routes (routing problems), which are an important part of transport logistics, occupy key positions in the management of the processes of moving goods and passengers with the support of modern information technologies. An obvious feature that combines the considered list of routing problems (the symmetric traveling salesman problem, the problem of packing in containers, the school bus problem) is that they are formulated as generalizations or variants of the NP-complete traveling salesman problem with restrictions that narrow the scope of feasible solutions. The strongest restrictions become insufficient solvability conditions, stimulating interest in the study of combinatorial optimization problems associated with the traveling salesman problem.