Solving the communication networks routing problem using modified algorithm for finding K shortest paths

Jacek Widuch

Abstract


The communication networks routing problem is an example of multicriteria optimization which the solution is the set of non-dominated solutions. Establishing routes consists in solving the bicriterion shortest path problem. In the paper an algorithm which determines all routes belong to the set of non-dominated solutions is shown. The algorithm is based on the algorithm for finding K shortest paths. It addition, the K shortest paths problem and an algorithm for solving it are presented.

Keywords


transportation problem; multicriteria optimization; set of non-dominated solutions; bicriterion shortest path problem; the K shortest path problem; paths tree

Full Text:

PDF (Polski)

References


Widuch J.: Problem wyznaczania połączeń w sieciach komunikacyjnych. ZN Pol. Śl. Studia Informatica, Vol. 22, No. 4(46), Gliwice 2001, s. 117-134.

Widuch J.: Wyznaczanie połączeń w sieciach komunikacyjnych o zmiennych wagach. ZN Pol. Śl. Studia Informatica, Vol. 23, No. 4(51), Gliwice 2002, s. 85-104.

Peschel M., Riedel C.: Polioptymalizacja. Metody podejmowania decyzji kompromisowych w zagadnieniach inżynieryjno-technicznych. WNT, Warszawa 1979.

Stadler W.: A survey of Multicriteria Otimization or the Vector Maximum Problem. Part I: 1776-1960, Journal of Optimization Theory & Application, tom 29, nr 1, USA wrzesień 1979, s. 1-52.

Cormen T. H., Leiserson Ch. E., Rivest R. L.: Wprowadzenie do algorytmów. WNT, Warszawa 2000.

Lipski W.: Kombinatoryka dla programistów. WNT, Warszawa 1989.

Skriver A.J.V., Andersen K.A.: A label correcting approach for solving bicriterion shortest-path problems. Computers & Operations Research, Vol. 27,2000, s. 507-524.

Brumbaugh-Smith J., Shier S.: An empirical investigation of some bicriterion shortest path algorithms. European Journal of Operational Research, Vol. 43, North-Holland 1989, s. 216-224.

Martins E. Q. V., Pascoal M. M. B.: An algorithm for ranking optimal paths. Departamento de Matematica, Universidade de Coimbra, Technical Report 01/004, CISUC, 2000 (http://www.mat.uc.pt/~marta/Publicacoes/rank_optimal.ps.gz).

Jungnickel D.: Graphs, networks and algorithms. Springer, Berlin 1999.

Widuch J.: Algorytmy optymalizacji wielokryterialnej w problemach komunikacyjnych. Rozprawa doktorska. Politechnika Śląska, Gliwice 2007.




DOI: http://dx.doi.org/10.21936/si2010_v31.n1.15