Development of an approach to the design of new transport routes based on methods used in graph theory

The article addresses the problem of developing intracity water transport routes in Saint Petersburg. The relevance of the topic is due to the extensive network of rivers and canals, which provides an opportunity for regular passenger transportation. Existing routes are exclusively tourist and excursion-oriented. Barriers to the development of transport routes include the insufficient development of berthing infrastructure and the monopoly over their use. The task addressed in the article is to develop an approach for designing new transport routes based on methods used in graph theory under conditions of limited berthing infrastructure. The formation of a new route is examined using the example of the existing public berthing infrastructure in the city, with tariff and operational features being described. The analysis shows that berths can simultaneously accommodate between 1 and 6 vessels when moored alongside. Based on graph theory, a potential route network for circular transport routes in the historic city center is constructed. The article discusses several graph theory methods used to analyze the developed routes: finding the longest path, constructing Hamiltonian paths, solving the traveling salesman problem, and determining a spanning tree. Graph theory is considered an effective tool for constructing and analyzing rational route networks. The possibilities of using edge weights in the graph to assess distances between berths, passenger flows, fuel consumption, and traffic intensity on a route section are described. The results obtained in the article can be applied in practice when developing regular transport routes in Saint Petersburg.