Solving the communication network routing problem using scalarization method

Jacek Widuch

Abstract


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.

Keywords


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

Full Text:

PDF (Polski)

References


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.

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.

Coello Coello C. A., van Veldhuizen D. A., Lamont G. B.: Evolutionary algorithms for solving multi-objective problems. Kluwer Academic Publishers, New York 2002.

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.

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.

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

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.

Dell'Olmo P., Gentili M., Scozzari A.: On finding dissimilar Pareto-optimal paths. European Journal of Operational Research, Vol. 162, No. 1, 2005, s. 70-82.

Garey M., Johnson D.: Computers and intractibility: a guide to the theory of NP-completeness. W. H. Freeman & Co., New York, USA, 1990.

Hansen P.: Bicriterion path problems. Multiple Criteria Decision Making: Theory and Application, Springer-Verlag, Berlin, Germany, 1980, s. 109-127.

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

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

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.

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.

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.

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.

Martins E. Q. V.: On a multicriteria shortest path problem. European Journal of Operational Research, Vol. 16, No. 2, 1982, s. 236-245.

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).

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.

Pareto V.: Course dEconomie Politique, F. Rouge, Lausanne, 1896.

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

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.

Reingold E. M., Nievergelt J., Deo N.: Algorytmy kombinatoryczne. PWN, Warszawa 1985.

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.

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.

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.

Tung C.T., Chew K.L.: A bicriterion Pareto-optimal path algorithm. Asia-Pacific Journal of Operational Research, Vol. 5, 1988, s. 166-172.

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.

Voorneveld M.: Characterization of Pareto dominance. Operations Research Letters, Vol. 31, No. l,2003,s. 7-11.

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.

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

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

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

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.




DOI: http://dx.doi.org/10.21936/si2011_v32.n4A.213