Algorytm wyznaczania połączenia komunikacyjnego o minimalnym czasie przejazdu z dodatkową minimalizacją kosztu przejazdu

• Autorzy: Widuch J. , Wicher D.

Warianty tytułu

EN

A algorithm for finding the route minimizing the time of travel and minimizing the cost of travel additionally

• Języki publikacji: PL

Abstrakty

PL

Wyznaczanie tras przejazdu jest jednym z badanych problemów transportowych. W niniejszej pracy przedstawiono problem wyznaczania połączeń w sieciach komunikacyjnych, którego celem jest wyznaczenie połączenia o minimalnym czasie przejazdu dla zadanej pary przystanków początkowego i końcowego oraz godziny rozpoczęcia podróży. Jeżeli istnieje więcej połączeń o minimalnym czasie przejazdu, to spośród nich należy wyznaczyć połączenie o minimalnym koszcie przejazdu. W pracy zaprezentowano algorytm umożliwiający rozwiązanie badanego problemu. Zaprezentowano także przykładowe wyniki przeprowadzonych badań eksperymentalnych z użyciem rzeczywistej sieci komunikacyjnej.

EN

The routing problem is one of the studied transportation problems. In the paper the communication networks routing problem is presented, in which the goal is to find a route from the start stop to the final stop minimizing the time of travel, where the time of starting travel at the start stop is given. If there are more routes with minimal the time of travel, among them the route with minimal the cost of travel should be determined. In the paper the algorithm for solving the communication networks routing problem is presented. Apart from that a sample results of experimental tests using the real communication network are presented.

Słowa kluczowe

PL

problem transportowy; skierowany graf ważony; zmienne wagi; najkrótsza ścieżka; relacyjna baza danych; procedura składowana

EN

transportation problem; directed weighted graph; variable weights; shortest path; relational database model (RDM); stored procedures

• Wydawca: Wydawnictwo Politechniki Śląskiej
• Czasopismo: Studia Informatica
• Rocznik: 2012
• Tom: Vol. 33, nr 4
• Strony: 59--79
• Opis fizyczny: Bibliogr. 42 poz.

Twórcy

autor

Widuch J.

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

autor

Wicher D.

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

Bibliografia

• 1.Barker R.: CASE*Method – modelowanie związków encji. WNT, Warszawa 1996.
• 2.Bellman R.: On a routing problem. Quarterly of Applied Mathematics, Vol. 16(1), p. 87–90, 1958.
• 3.Brumbaugh–Smith J., Shier S.: An empirical investigation of some bicriterion shortest path algorithms. European Journal of Operational Research, Vol. 43, p. 216–224, 1989.
• 4.Climaco J. C., Martins E. Q. V.: A bicriterion shortest path algorithm. European Journal of Operational Research, Vol. 11, No. 4, p. 399–404, 1982.
• 5.Coello Coello C. A., van Veldhuizen D. A., Lamont G. B.: Evolutionary algorithms for solving multi–objective problems. Kluwer Academic Publishers, New York, 2002.
• 6.Corley H. W., Moon I. D.: Shortest paths in networks with vector weights. Journal of Optimization Theory and Application, Vol. 46, No. 1, p. 79–86, 1985.
• 7.Cormen T. H., Leiserson Ch. E., Rivest R. L.: Wprowadzenie do algorytmów. WNT, Warszawa 2000.
• 8.Daellenbach H. G., De Kluyver C. A.: Note on multiple objective dynamic programming. Journal of the Operational Research Society, Vol. 31, No. 7, p. 591–594, 1980.
• 9.Date C.J.: Wprowadzenie do baz danych. WNT, Warszawa 1981.
• 10.Dell'Olmo P., Gentili M., Scozzari A.: On finding dissimilar Pareto–optimal paths. European Journal of Operational Research, Vol. 162, No. 1, p. 70–82, 2005.
• 11.Dijkstra E. W.: A note on two problems in connexion with graphs. Numerical Mathematics, Vol. 1, p. 269–271, 1959.
• 12.Ford L. R.: Network Flow Theory. Report P–923, The Rand Corporation, Santa Monica, CA, USA, 1956.
• 13.Floyd R.: Algorithm 97: Shortest path. Communications of the ACM, Vol. 5(6), p. 345, 1962.
• 14.Hansen P.: Bicriterion path problems. Multiple Criteria Decision Making: Theory and Application, Springer–Verlag , Berlin, Germany, p. 109–127 , 1980.
• 15.Jaszkiewicz A.: Inżynieria oprogramowania. Wydawnictwo HELION, Gliwice 1997.
• 16.Johnson D. B.: Efficient algorithms for shortest paths in sparse networks. Journal of the ACM, Vol. 24(1), p. 1–13, 1977.
• 17.Lipski W.: Kombinatoryka dla programistów. WNT, Warszawa 1989.
• 18.Machuca E., Mandow L., Pérez 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, p. 205–216, 2009.
• 19.Mandow L., Pérez de la Cruz J. L.: Frontier search for Bicriterion Shortest Path Problems. Proceeding of the 2008 conference on ECAI 2008 18th European Conference on Artificial Intelligence, p. 480–484, IOS Press, 2008.
• 20.Mandow L., Pérez de la Cruz J. L.: Path recovery in frontier search for multiobjective shortest path problems. Journal of Intelligent Manufacturing, Vol. 21, No. 1, p. 89–99, 2008.
• 21.Martins E. Q. V.: On a multicriteria shortest path problem. European Journal of Operational Research, Vol. 16, No. 2, p. 236–245, 1982.
• 22.Martins E. Q. V.: On a multicriteria shortest path problem. European Journal of Operational Research, Vol. 16, No. 2, p. 236–245, 1982.
• 23.Martí R., González Velarde J. L., Duarte A.: Heuristics for the bi–objective path dissimilarity problem. Computers & Operations Research, Vol. 36, No. 11, p. 2905–2912, 2009.
• 24.Mote J., Murthy I., Olson D. L.: A parametric approach to solving bicriterion shortest path problems. European Journal of Operational Research, Vol. 53, No. 1, p. 81–92, 1991.
• 25.Pareto V.: Course d'Economie Politique, F. Rouge, Lausanne, 1896.
• 26.Peschel M., Riedel C.: Polioptymalizacja. Metody podejmowania decyzji kompromisowych w zagadnieniach inżynieryjno-technicznych. WNT, Warszawa 1979.
• 27.Raith A., Ehrgott M.: A comparison of solution strategies for biobjective shortest path problems. Journal Computers and Operations Research, Vol. 36, No. 4, p. 1299–1331, 2009.
• 28.Reingold E. M., Nievergelt J., Deo N.: Algorytmy kombinatoryczne. PWN, Warszawa 1985.
• 29.Skriver A. J. V., Andersen K.A.: A label correcting approach for solving bicriterion shortest-path problems. Computers & Operations Research, Vol. 27, p. 507–524, 2000.
• 30.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, p. 1–52, 1979.
• 31.Tung C. T., Chew K. L.: A bicriterion Pareto–optimal path algorithm. Asia–Pacific Journal of Operational Research, Vol. 5, p. 166–172, 1988.
• 32.Ulungu E. L., Teghem J.: Multi–objective combinatorial optimization problems: a survey. Journal of Multi-Criteria Decision Analysis, Vol. 3, No. 2, p. 83–104, 1994.
• 33.Voorneveld M.: Characterization of Pareto dominance. Operations Research Letters, Vol. 31, No. 1, p. 7–11, 2003.
• 34.Warshall S.: A theorem on Boolean matrices. Journal of the ACM, Vol. 9(1), p. 11–12, 1962.
• 35.Widuch J.: Problem wyznaczania połączeń w sieciach komunikacyjnych. Studia Informatica, Vol. 22, nr 4(46), p. 117–134, Gliwice 2001.
• 36.Widuch J.: Wyznaczanie połączeń w sieciach komunikacyjnych o zmiennych wagach. Studia Informatica, Vol. 23, nr 4(51), p. 85–104, Gliwice 2002.
• 37.Widuch J.: Algorytmy optymalizacji wielokryterialnej w problemach komunikacyjnych. Rozprawa doktorska, Politechnika Śląska, Gliwice 2008.
• 38.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, nr 1(88), p. 55–70, Gliwice 2010.
• 39.Widuch J.: Rozwiązanie problemu wyznaczania połączeń w sieciach komunikacyjnych z zastosowaniem metody skalaryzacji. Studia Informatica, Vol. 32, nr 4A(100), p. 57–81, Gliwice 2011.
• 40.Widuch J.: Algorytmy optymalizacji tras przejazdu pojazdów. Studia Informatica, Vol. 32, nr 4A(100), p. 83–111, 2011.
• 41.Yourdon E.: Współczesna analiza strukturalna. WNT, Warszawa 1996.
• 42.Strona domowa przewoźnika KZK GOP: http://www.kzkgop.com.pl/