2021, issue 3, p. 15-33
Received 23.07.2021; Revised 14.08.2021; Accepted 28.09.2021
Published 30.09.2021; First Online 25.10.2021
https://doi.org/10.34229/2707-451X.21.3.2
Previous | FULL TEXT (in Ukrainian) | Next
Problems on Shortest k-Node Cycles and Paths
Petro
Stetsyuk 1 * 
,
Dumitru Solomon 2, Maria Grygorak 3
1 V.M. Glushkov Institute of Cybernetics of the NAS of Ukraine, Kyiv
2 Institute of Mathematics and Informatics of the Academy of Sciences of Moldova, Chisinau
3 National Aviation University, Kyiv
* Correspondence: This email address is being protected from spambots. You need JavaScript enabled to view it.
The paper is devoted to the construction of mathematical models for problems on the shortest cycles and paths, that pass through a given number of nodes of a directed graph. Such cycles and paths are called k-node, where 1<k <n, n is the number of nodes in the graph.
Section 1 formulates two problems for finding the shortest k-node cycle – a mixed Boolean and linear programming problem and a discrete programming problem. Both problems include constraints from the classical assignment problem, describing a one-time entry into a node and a one-time exit from a node for those nodes through which the cycle passes. The cycle connectivity in the first problem is ensured by modeling the flow problem, and in the second problem, it is ensured by using the A. Tucker constraints for the travelling salesman problem.
Section 2 establishes a connection between the formulations of both problems from Section 1 and the travelling salesman problem and investigates the efficiency of their solution using modern versions of gurobi and cplex programs and the AMPL modeling language.
Section 3 contains the formulation of the shortest k-node path problem, which is represented by a mixed Boolean and linear programming problem. With its help, the optimal routes were found for visiting the wine-making points of the Malopolskie Wine Route in the direction Lviv-Wroclaw-Lviv (Section 4). Here a map for the 20 most visited wine-making points of the Malopolskie Wine Route and a table of the distances between them and the distances from them to Lviv and Wroclaw, calculated using the Google Maps web service, are presented.
The developed mathematical models of the problems of finding the shortest k-node paths and cycles and the developed software in the AMPL modeling language can be used for the design and arrangement of technical objects, optimization of the transportation of products, analysis and forecasting of economic processes, determination of optimal routes when planning passenger and freight traffic, optimal organization of the process of managing a set of transactions and queries during their implementation in network databases and other classes of applied optimization problems.
Keywords: digraph, shortest path, Boolean variable, linear programming, Hamiltonian cycle, Hamiltonian path, travelling salesman problem, AMPL, gurobi, cplex.
Cite as: Stetsyuk P., Solomon D., Grygorak M. Problems on Shortest k-Node Cycles and Paths. Cybernetics and Computer Technologies. 2021. 3. P. 15–33. (in Ukrainian) https://doi.org/10.34229/2707-451X.21.3.2
References
1. Christofides N. Graph Theory. An Algorithmic Approach, New York: Academic, 1975.
2. Ermol'ev Y.M. Shortest admissible paths. I. Cybern Syst Anal. 1966. 2 (3). P. 74–79. https://doi.org/10.1007/BF01071635
3. Ermol'ev Y.M., Mel'nik I.M. The shortest admissible paths. II. Cybern Syst Anal. 1967. 3 (1). P. 52–58. https://doi.org/10.1007/BF01072848
4. Ermoliev Yu.M., Melnik I.M. Extremal problems on graphs. Kiev: Nauk.dumka, 1968. 176 p. (In Russian)
5. Stetsyuk P.I., Petrukhin V.A., Bugrov N.V., Khripko K.Yu. Ellipsoid method and conditionally optimal route. International Scientific Conference "Modern Informatics: Problems, Achievements and Prospects for Development", dedicated to the 90th anniversary of the birth of Academician V.M. Glushkov (September 12–13, 2013). Kyiv: V.M. Glushkov Institute of Cybernetics of the NAS of Ukraine, 2013. P. 111–113. (In Russian)
6. Gavish B., Graves S.C. The travelling salesman problem and related problems. Working Paper OR-078-78, 1978. Operations Research Center, MIT, Cambridge, MA.
7. Miller C.E., Tucker A.W., Zemlin R.A. Integer programming formulation of travelling salesman problem. J. ACM. 1960. 3. P. 326–329. https://doi.org/10.1145/321043.321046
8. Alekseeva E.V. Construction of mathematical models of integer linear programming. Examples and problems: Ucheb. Posobie / Novosib.gos. universitet. Novosibirsk, 2012. 131 p. (In Russian)
9. Gameckiy A.F., Solomon D.I. Operations research. V. II. Chisinau, Evrika, 2008 . 592 p. (In Russian)
10. Stetsyuk P.I. Problem Statements for k-Node Shortest Path and k-Node Shortest Cycle in a Complete Graph. Cybern. Syst. Anal. 2016. 52. Р. 71–75. https://doi.org/10.1007/s10559-016-9801-x
11. Stetsyuk P.I. Two problems on the shortest k-node cycle. Proceedings of the XIII International scientific-practical conference "Mathematical and software of intelligent systems (MPZIS-2015)" (November 18–20, 2015, Dnipropetrovsk). P. 215–221. (In Russian)
12. Stetsyuk P.I., Solomon D.I. Computational aspects of the travelling salesman problem. Abstracts of the VIII International Science and Technology Conference "Information and Computer Technologies 2016" (April 22–23, 2016). Zhytomyr: ZhDTU, 2016. P. 91–92. (In Russian)
13. Solomon Dumitru. Transporturi rutiere de mărfuri si pasageri. Cartea I. Organizarea transporturilor rutiere de mărfuri. (Proiect de an). Ch.: Evrica, 2014. 170 p. (in Moldavian)
14. Gurobi Optimization, Inc., Gurobi Optimizer Reference Manual, 2014. http://www.gurobi.com/
15. CPLEX Optimizer. High-performance mathematical programming solver for linear programming, mixed-integer programming and quadratic programming. https://www.ibm.com/analytics/cplex-optimizer
16. NEOS Solver. https://neos-server.org/neos/solvers/
17. Fourer R., Gay D., Kernighan B. AMPL, A Modeling Language for Mathematical Programming. Belmont: Duxburry Press, 2003. 517 p.
18. Stetsyuk P.I., Lefterov A.V., Fedoseev A.I. The shortest k-node path. Komp. Matematika. 2015. 2. P. 3–11. (In Russian) http://dspace.nbuv.gov.ua/handle/123456789/168375
19. Stetsyuk P.I., Lefterov A.V., Likhovid A.P., Fedoseev A.I. Optimization service for choosing wine routes. Mathematical modeling, optimization and information technologies: materials of the 5th Intern. scientific. conf. (Chisinau, March 22–25, 2016). Chisinau: Evrika, 2016. V. II. P. 337–344. (In Russian)
20. Andrianova E.G., Raev V.K., Filgus D.I. Determination of the Shortest Hamiltonian Paths in an Arbitrary Graph of Distributed Databases. Russian Technological Journal. 2019. 7 (4). P. 7–20. (In Russian) https://doi.org/10.32362/2500-316X-2019-7-4-7-20
ISSN 2707-451X (Online)
ISSN 2707-4501 (Print)
Previous | FULL TEXT (in Ukrainian) | Next