Rozwiązanie problemu wyznaczania połączeń w sieciach komunikacyjnych za pomocą zmodyfikowanego algorytmu wyznaczania K najkrótszych ścieżek

• Autorzy: Widuch J.

Warianty tytułu

EN

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

• Języki publikacji: PL

Abstrakty

PL

Problem wyznaczania połączeń w sieciach komunikacyjnych jest przykładem zadania optymalizacji wielokryterialnej, którego rozwiązaniem jest zbiór rozwiązań niezdominowanych. Wyznaczanie połączeń polega na rozwiązaniu dwu kryterialnego problemu wyznaczania najkrótszej ścieżki w grafie ważonym. W pracy przedstawiono algorytm umożliwiający wyznaczenie wszystkich połączeń należących do zbioru rozwiązań niezdominowanych. Podstawą do opracowania algorytmu był algorytm wyznaczania K najkrótszych ścieżek. Problem wyznaczania K najkrótszych ścieżek został omówiony w pracy oraz przedstawiono algorytm umożliwiający jego rozwiązanie.

EN

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.

Słowa kluczowe

PL

problem transportowy; optymalizacja wielokryterialna; drzewo ścieżek

EN

transportation problem; multicriteria optimization

• Wydawca: Wydawnictwo Politechniki Śląskiej
• Czasopismo: Studia Informatica
• Rocznik: 2010
• Tom: Vol. 31, nr 1
• Strony: 55--70
• Opis fizyczny: Bibliogr. 11 poz.

Twórcy

autor

Widuch J.

• Instytut Informatyki, Politechnika Śląska, ul. Akademicka 16, 44-100 Gliwice,

Bibliografia

• 1. Widuch J.: Problem wyznaczania połączeń w sieciach komunikacyjnych. ZN Pol. Śl. Studia Informatica, Vol. 22, No. 4(46), Gliwice 2001, s. 117-134.
• 2. 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.
• 3. Peschel M., Riedel С: Polioptymalizacja. Metody podejmowania decyzji kompromisowych w zagadnieniach inżynieryjno-technicznych. WNT, Warszawa 1979.
• 4. 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.
• 5. Cormen Т. Н., Leiserson Ch. E., Rivest R. L.: Wprowadzenie do algorytmów. WNT, Warszawa 2000.
• 6. Lipski W.: Kombinatoryka dla programistów. WNT, Warszawa 1989.
• 7. 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.
• 8. 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.
• 9. Martins E. Q. V., Pascoal M. M. В.: 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).
• 10. Jungnickel D.: Graphs, networks and algorithms. Springer, Berlin 1999.
• 11. Widuch J.: Algorytmy optymalizacji wielokryterialnej w problemach komunikacyjnych. Rozprawa doktorska. Politechnika Śląska, Gliwice 2007.