Skip to content
naulon
Not checkedNot checked for notices yet.

Problems on Shortest k-Node Cycles and Paths

Petro Stetsyuk, Dumitru Solomon, Maria Grygorak

Кібернетика та комп'ютерні технології · 2021

doi:10.34229/2707-451x.21.3.2 (opens in a new tab)

We email you when a new notice or a question about this paper appears.

Abstract

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.

Abstract licence: CC BY-NC

Reads

Read by people on this page

None yet.

Checked or read by AI through naulon

None yet.

A person counts once a day per paper. We keep no cookie and no address: a reader is a hash that changes every day. Any month under five reads shows no number.

Are you an author?

Is this your paper?

Claim it to add your note and be paid when agents cite it. Free.