Scientific publications of the Ivan Franko National University of Lviv

Visnyk of the Lviv University. Series Applied Mathematics and Computer Science

Additional information
Year 2006
Volume 11
Authors Prytula N., Yeleyko Ya., Prytula M.
Name of the article Problems and algorithms of distribution of discrete streams on networks
Abstract The nonlinear transport problems on graphs are considered in this work. Under nonlinear transport problems we understand extreme problems on networks of this or that nature with nonlinear criterion function and the restrictions which are set in units and on arches. The basic information in nonlinear transport models is such data as data of need for moving different components, characteristics of elements of a network and processes of transfer, transportation, sizes of resources. Besides, there are also important parameters of loading of elements of a network by the transported components and levels of a technical condition of arches and units of a network. Thus it is considered in models, that streams on the set network can be formed as centralized as decentralized too, as according to the certain plan as casually too. We shall consider discrete streams. It can be streams of motor vehicles or streams of the cars, the incorporated discrete streams in groups - streams of trains. Actuality of such problems have got today special value because of transition to operative management of such systems. The approach offered in this work, has enabled to develop graph-analytical system of the railway of Ukraine. The problem about calculation of moving parameters is solved for the established way between two any vertices of the graph. The algorithm of solving the problem, allows to find the minimal power expenses for moving of group of correspondence at minimal time for moving and distribution of speed along a trajectory of moving. The same algorithm has enabled to find minimal time which divides two any groups of correspondence which move one after one. It has enabled to find, on the one hand, throughput of edges, and of another to build the optimum schedule of moving of groups of correspondence. It is possible to search for such minimal time distance between groups of correspondence not only on separately taken span (edge), but also on all way of movement of correspondence. On the basis of above mentioned algorithm, the complex of programs is developed. It has passed approbation and at present is successfully used for development the schedules of train movements. The problem of formation the streams of groups of correspondence has been solved for real matrixes of the correspondence. At present time the adaptation of algorithm for needs of the railway of Ukraine is being done. The offered algorithm has allowed to construct more effective train diagram of cargo trains comparing with the existing ones. It was possible to construct enough exact estimation from above optimum size of expenses for the schedule of moving of groups of correspondence for any matrix of correspondence. The results of work of algorithm are close to optimum and proof enough to casual indignation of matrix elements of correspondence in significant borders (up to 30 %). Thus, about 5 % of groups of correspondence change the schedule. It is considered transport networks and discrete streams on them in work. For the specified adjusted class of streams poses optimization problems. Ways of the decision of separate tasks are offered
Language Ukrainian
PDF format Prytula N., Yeleyko Ya., Prytula M. Problems and algorithms of distribution of discrete streams on networks
small logo
©2003-2012 Lviv University | Contacts