Problems on Shortest k-Node Cycles and Paths

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 p...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Petro Stetsyuk, Dumitru Solomon, Maria Grygorak
Formato:	article
Lenguaje:	EN RU UK
Publicado:	V.M. Glushkov Institute of Cybernetics 2021
Materias:	digraph shortest path boolean variable linear programming hamiltonian cycle hamiltonian path travelling salesman problem ampl gurobi cplex Cybernetics Q300-390
Acceso en línea:	https://doaj.org/article/46a9d8d25fe74c8d9ce9f25291bd18d3
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:46a9d8d25fe74c8d9ce9f25291bd18d3
record_format	dspace
spelling	oai:doaj.org-article:46a9d8d25fe74c8d9ce9f25291bd18d32021-11-08T19:44:54ZProblems on Shortest k-Node Cycles and Paths2707-45012707-451X10.34229/2707-451X.21.3.2https://doaj.org/article/46a9d8d25fe74c8d9ce9f25291bd18d32021-09-01T00:00:00Zhttp://cctech.org.ua/13-vertikalnoe-menyu-en/269-abstract-21-3-2-artehttps://doaj.org/toc/2707-4501https://doaj.org/toc/2707-451XThe 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.Petro StetsyukDumitru SolomonMaria GrygorakV.M. Glushkov Institute of Cyberneticsarticledigraphshortest pathboolean variablelinear programminghamiltonian cyclehamiltonian pathtravelling salesman problemamplgurobicplexCyberneticsQ300-390ENRUUKКібернетика та комп'ютерні технології, Iss 3, Pp 15-33 (2021)
institution	DOAJ
collection	DOAJ
language	EN RU UK
topic	digraph shortest path boolean variable linear programming hamiltonian cycle hamiltonian path travelling salesman problem ampl gurobi cplex Cybernetics Q300-390
spellingShingle	digraph shortest path boolean variable linear programming hamiltonian cycle hamiltonian path travelling salesman problem ampl gurobi cplex Cybernetics Q300-390 Petro Stetsyuk Dumitru Solomon Maria Grygorak Problems on Shortest k-Node Cycles and Paths
description	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.
format	article
author	Petro Stetsyuk Dumitru Solomon Maria Grygorak
author_facet	Petro Stetsyuk Dumitru Solomon Maria Grygorak
author_sort	Petro Stetsyuk
title	Problems on Shortest k-Node Cycles and Paths
title_short	Problems on Shortest k-Node Cycles and Paths
title_full	Problems on Shortest k-Node Cycles and Paths
title_fullStr	Problems on Shortest k-Node Cycles and Paths
title_full_unstemmed	Problems on Shortest k-Node Cycles and Paths
title_sort	problems on shortest k-node cycles and paths
publisher	V.M. Glushkov Institute of Cybernetics
publishDate	2021
url	https://doaj.org/article/46a9d8d25fe74c8d9ce9f25291bd18d3
work_keys_str_mv	AT petrostetsyuk problemsonshortestknodecyclesandpaths AT dumitrusolomon problemsonshortestknodecyclesandpaths AT mariagrygorak problemsonshortestknodecyclesandpaths
_version_	1718441467108655104

Problems on Shortest k-Node Cycles and Paths

Ejemplares similares