OVERVIEW OF ROUTING TASKS REDUCIBLE TO THE TRAVELING SALESMAN PROBLEM

Ольга Борисовна Маций

Abstract


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.


Keywords


combinatorial optimization, transport logistics, routing problem, traveling salesman problem, routes, objective function

References


Bronshtein, E.M., Zaiko, T.A. (2010), Determinirovannye optimizacionnye zadachi transportnoi logistiki. Avtomatika i telemehanika, Vol. 10, рр. 113-147.

Emec, O.A., Parfenova, T.A (2010), Transportnye zadachi na perestanovkah: svoistva ocenok v metode vetvei i granic. Kibernetika i sistemnyi analiz, Vol. 6, рр. 106-112.

Литтл, D.J., Murti, K., Suini, D., Kerel, K. (1965), Algoritm dlya resheniya zadachi kommivoyajera. Ekonomika i matematicheskie metody, Vol/ 1, no. 1, pp. 90- 107.

Geri, M., Djonson, D. (1982), Vychislitel'nye mashiny i trudnoreshaemye zadachi. Mir, 416 p.

Mainika, E., Zaiko, T.A. (1981), Algoritmy optimizacii na setyah i grafah. Avtomatika i telemehanika, Mir, 323 p.

Panishev, A.V., Plechistyi, D.D. (2004), Modeli i metody optimizacii v probleme kommivoyajera. JGTU, 300 p.

Panishev, A.V., Danil'chenko, O.M., Skachkov, V.O. (2004), Vstup do teorії skladnostі diskretnih zadach. Avtomatika i telemehanika, Vol JGTU, 326 p.

Rezer, S.M., Loveckii, S.E., Melamed, I.I (1990), Matematicheskie metody optimal'nogo planirovaniya v transportnyh sistemah. Itogi nauki i tehniki, 171 p.




DOI: https://doi.org/10.32620/oikit.2019.86.11

Refbacks

  • There are currently no refbacks.