Rozwiązanie problemu wyznaczania połączeń w sieciach komunikacyjnych z zastosowaniem metody skalaryzacji

Widuch, J.

Artykuł - szczegóły

Tytuł artykułu

Rozwiązanie problemu wyznaczania połączeń w sieciach komunikacyjnych z zastosowaniem metody skalaryzacji

Autorzy

Widuch J.

Identyfikatory

Warianty tytułu

Solving the communication network routing problem using scalarization method

Języki publikacji

Abstrakty

Problem wyznaczania połączeń w sieciach komunikacyjnych jest przykładem zadania optymalizacji wiełokryterialnej, którego rozwiązaniem jest zbiór rozwiązań niezdominowanych. Wyznaczenie połączeń polega na rozwiązaniu dwukryterialnego problemu najkrótszych ścieżek w grafie ważonym o zmiennych wagach. W pracy przedstawiono algorytm umożliwiający wyznaczenie połączeń należących do zbioru rozwiązań niezdominowanych. Rozwiązania są wyznaczane z użyciem metody skalaryzacji, w której k (k>1) funkcji kryterialnych jest zastępowanych jedną ważoną funkcją kryterialną. Zaprezentowano także przykładowe wyniki przeprowadzonych badań eksperymentalnych.

The communication networks routing problem is an example of mulitcriteria optimization problem which the solution is the set of non-dominated solutions. Establishing routes consists in solving the bicriterion shortest path problem in the weighted graph with non-constant weights. In the paper an algorithm which determines routes belong to the set of non-dominated solutions is shown. The solutions are computed using scalarization method where the k (k > 1) criterion functions are replaced with single weighted criterion function. Apart from that a sample results of experimental tests are presented.

Słowa kluczowe

transport rozwiązanie niezdominowane optymalizacja wielokryterialna metoda skalaryzacji drzewo ścieżek sieć komunikacyjna

transportation non-dominated solution multicriteria optimization scalarization method paths tree communication network

Wydawca

Wydawnictwo Politechniki Śląskiej

Czasopismo

Studia Informatica

Rocznik

2011

Tom

Vol. 32, nr 4A

Strony

57--81

Opis fizyczny

Bibliogr. 34 poz.

Twórcy

autor

Widuch J.

Politechnika Śląska, Instytut Informatyki Gliwice, Akademicka 16, pokój 509, jacek.widuch@polsl.pl

Bibliografia

1. Brumbaugh-Smith J., Shier D.: An empirical investigation of some bicriterion shortest path algorithms. European Journal of Operational Research, Vol. 43, No. 2, 1989, s. 216-224.
2. Climaco J. C, Martins E. Q. V.: A bicriterion shortest path algorithm. European Journal of Operational Research, Vol. 11, No. 4, 1982, s. 399-404.
3. Coello Coello C. A., van Veldhuizen D. A., Lamont G. B.: Evolutionary algorithms for solving multi-objective problems. Kluwer Academic Publishers, New York 2002.
4. Corley H.W., Moon I. D.: Shortest paths in networks with vector weights. Journal of Optimization Theory and Application, Vol. 46, No. 1, 1985, s. 79-86.
5. Coutinho-Rodrigues J. M., Climaco J. C, Current J. R.: An interactive bi-objective shortest path approach: searching for unsupportet nondominated solutions. Computers & Operations Research, Vol. 26, No. 8, 1999, s. 789-798.
6. Cormen T. H., Leiserson Ch. E., Rivest R. L.: Wprowadzenie do algorytmów. WNT, Warszawa 2000.
7. Daellenbach H. G., De Kluyver C. A.: Note on multiple objective dynamie programming. Journal of the Operational Research Society, Vol. 31, No. 7, 1980, s. 591-594.
8. DelfOlmo P., Gentili M., Scozzari A.: On finding dissimilar Pareto-optimal paths. European Journal of Operational Research, Vol. 162, No. 1, 2005, s. 70-82.
9. Garey M., Johnson D.: Computers and intractibility: a guide to the theory of NP-completeness. W. H. Freeman & Co., New York, USA, 1990.
10. Hansen P.: Bicriterion path problems. Multiple Criteria Decision Making: Theory and Application, Springer-Verlag, Berlin, Germany, 1980, s. 109-127.
11. Jungnickel D.: Graphs, networks and algorithms. Springer, Berlin 1999.
12. Lipski W.: Kombinatoryka dla programistów. WNT, Warszawa 1989.
13. Machuca E., Mandow L., Perez de la Cruz J.L.: An Evaluation of Heuristic Functions for Bicriterion Shortest Path Problems. Proceedings of the XIV Portuguese Conference on Artificial Inteligence (EPIA 2009), Universidade de Aveiro, 2009, s. 205-216.
14. Mandow L., Perez de la Cruz J. L.: Frontier search for Bicriterion Shortest Path Problems. Proceeding of the 2008 conference on ECAI2008 18th European Conference on Artificial Intelligence, IOS Press, 2008, s. 480-484.
15. Mandow L., Perez de la Cruz J. L.: Path recovery in frontier search for multiobjective shortest path problems. Journal of Intelligent Manufacturing, Vol. 21, No. 1, 2008, s. 89-99.
16. Martí R., Gonzalez Velarde J. L., Duarte A.: Heuristics for the bi-objective path dissimilarity problem. Computers & Operations Research, Vol. 36, No. 11, 2009, s. 2905-2912.
17. Martins E. Q. V.: On a multicriteria shortest path problem. European Journal of Operational Research, Vol. 16, No. 2, 1982, s. 236-245.
18. 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).
19. Mote J., Murthy I., Olson D. L.: A parametric approach to sohring bicriterion shortest path problems. European Journal of Operational Research, Vol. 53, No. 1, 1991, s. 81-92.
20. Pareto V.: Course dEconomie Politique, F. Rouge, Lausanne, 1896.
21. Peschel M., Riedel C: Polioptymalizacja. Metody podejmowania decyzji kompromisowych w zagadnieniach inżynieryjno-technicznych. WNT, Warszawa 1979.
22. Raith A., Ehrgott M.: A comparison of solution strategies for biobjective shortest path problems. Journal Computers and Operations Research, Vol. 36, No. 4, 2009, s. 1299-1331.
23. Reingold E. M., Nievergelt J., Deo N.: Algorytmy kombinatoryczne. PWN, Warszawa 1985.
24. 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.
25. Skriver A. J. V., Andersen K. A.: A classification of bicriteria shortest path (BSP) algorithms. Asia-Pacific Journal of Operational Research, Vol. 17, 2000, s. 199-212.
26. Stadler W.: A survey of Multicriteria Otimization or the Vector Maximum Problem. Part I: 1776-1960, Journal of Optimization Theory & Aplication, Vol. 29, No. 1, 1979, s. 1-52.
27. Tung C.T., Chew K.L.: A bicriterion Pareto-optimal path algorithm. Asia-Pacific Journal of Operational Research, Vol. 5, 1988, s. 166-172.
28. Ulungu E. L., Teghem J.: Multi-objective combinatorial optimization problems: a survey. Journal of Multi-Criteria Decision Analysis, Vol. 3, No. 2, 1994, s. 83-104.
29. Voorneveld M.: Characterization of Pareto dominance. Operations Research Letters, Vol. 31, No. l,2003,s. 7-11.
30. White D. J.: The set of efficient solutions for multiple objective shortest path problems. Computers & Operations Research, Vol. 9, No. 2, 1982, s. 101-107.
31. Widuch J.: Problem wyznaczania połączeń w sieciach komunikacyjnych. Studia Informatica, Vol. 22, No. 4(46), Gliwice 2001, s. 117-134.
32. Widuch J.: Wyznaczanie połączeń w sieciach komunikacyjnych o zmiennych wagach. Studia Informatica, Vol. 23, No. 4(51), Gliwice 2002, s. 85-104.
33. Widuch J.: Algorytmy optymalizacji wielokryterialnej w problemach komunikacyjnych. Rozprawa doktorska, Politechnika Śląska, Gliwice 2008.
34. Widuch J.: Rozwiązanie problemu wyznaczania połączeń w sieciach komunikacyjnych za pomocą zmodyfikowanego algorytmu wyznaczania K najkrótszych ścieżek. Studia Informatica, Vol. 31, No. 1(88), Gliwice 2010, s. 55-70.

Typ dokumentu

Bibliografia

Identyfikator YADDA

bwmeta1.element.baztech-article-BSL1-0019-0009