Route Planning in Large-Scale Transport Networks: A Multi-criteria Approach Using Prefractal Graphs with Optimization of Transportation Costs Chapter Conference Paper uri icon


  • The paper investigates the problem of planning transport routes in large-scale transport networks, taking into account multi-criteria optimization. We propose a new way to reduce the computational complexity of algorithms for finding optimal transport routes using prefractal graphs. Prefractal graphs allow one to naturally model the structure of the hierarchy of territorial ties and take into account the structural dynamics of systems. The paper constructs a multicriteria mathematical formulation of the problem of covering a prefractal graph with simple intersecting chains, to which the investigated problem of organizing routes in large-scale transport networks is reduced. The main social and economic requirements for the transport system are formulated and included in the model in the form of criteria. To solve the problem posed, polynomial algorithms have been constructed and proven, which have several times lower computational complexity compared to a similar problem on graphs. The optimality of the found solution according to the selected criterion is proved and estimates are given according to the remaining criteria.

publication date

  • 2021