Nieklasyczne modele i metody planowania tras w systemach wspomagania planowania ruchu: analiza złożoności, efektywności i zastosowań

• Autorzy: Tarapata Z.

Warianty tytułu

EN

Non-classical models and methods of route planning in traffic planning support systems: analysis of complexity, effectiveness and applications

• Języki publikacji: PL

Abstrakty

PL

W referacie przedstawiono nieklasyczne modele i metody planowania tras stosowane w systemach wspomagania planowania ruchu związanych z różnymi dziedzinami (systemami transportowymi, systemami nawigacji satelitarnej, systemami planowania podróży, sieciami komputerowymi, systemami wspomagania planowania przegrupowania wojsk). Zdefiniowano uogólniony model planu trasy. Przeanalizowano szczegółowo modele drogi najprostszej oraz drogi najkrótszej w sieci uwarunkowanej czasowo. Omówiono podstawowe metody planowania tras oraz ich własności. Dokonano analizy wyników eksperymentalnego badania złożoności obliczeniowej prezentowanych metod i ich przydatności w systemach planowania ruchu.

EN

In the paper non-classical models and methods of route planning used in traffic planning support systems connected with different domains such as: transport systems, auto-navigation systems, computer networks, military movement planning systems are presented. Generalized model of route plan is defined. Models of simplest path and shortest path in time-dependent networks are analyzed in detail. Basic methods of route planning and their properties are discussed. Analysis of experimental complexity of presented algorithms is done and evaluation of their usefulness in traffic planning systems is carried out.

Słowa kluczowe

PL

planowanie tras; metody planowania tras; modele planowania tras; system transportowy; plan trasy; system logistyczny

EN

itinerary planning; methods of route planning; models route planning; transportation system; itinerary plan; logistic system

• Wydawca: Oficyna Wydawnicza Politechniki Warszawskiej
• Czasopismo: Prace Naukowe Politechniki Warszawskiej. Transport
• Rocznik: 2007
• Tom: z. 60
• Strony: 99--114
• Opis fizyczny: Bibliogr. 25 poz., rys., tab., wykr.

Twórcy

autor

Tarapata Z.

• Wojskowa Akademia Techniczna, Wydział Cybernetyki, ul. Kaliskiego 2, 00-908 Warszawa,

Bibliografia

• [1] Adamski A.: Inteligentne systemy transportowe: sterowanie, nadzór i zarządzanie. Wydawnictwo AGH, Kraków 2003.
• [2] Boyan J., Mitzenmacher M.: Improved results for route planning in stochastic transportation networks. Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms (Proceedings in Applied Mathematics 103), Washington 2001, 895÷902.
• [3] Cherkassky B. V., Goldberg A. V., and Radzik T., Shortest Paths Algorithms: Theory and Experimental Evaluation, Mathematical Programming 73, 1996, s. 129-174.
• [4] Chou Y., Romeijn E., Smith R.: Approximating Shortest Paths in Large-scale networks with an Application to Intelligent Transportation Systems, Journal on Computing, Volume 10, Issue 2 (February 1998), 163÷179.
• [5] Djidjev H., Pantziou G., Zaroliagis C.D.: On-Line And Dynamic Algorithms For Shortest Path Problems. Lecture Notes in Computer Science, vol.900, 1995, s. 193÷204.
• [6] Duckham M., Kulik L.: ,,Simplest" Paths: Automated Route Selection for Navigation, W: Kuhn W., Worboys M.F., Timpf S. (Eds), Spatial Information Technology: Foundations of Geographic Information Science, Lecture Notes in Computer Science, vol. 2825, Springer-Verlag, Berlin 2003, 182÷199.
• [7] Kaufman D. E., Smith R. L.: Fastest paths in time-dependent networks for intelligent vehicle highway systems applications. IVHS Journal, 1(1): 1 ÷ 11, 1993.
• [8] Korf R.E.: Artificial intelligence search algorithms, in Algorithms Theory Computation Handbook, Boca Raton, FL: CRC Press (1999).
• [9] Mark D.: Automated route selection for navigation. IEEE Aerospace and Electronic Systems Magazine 1 1986.
• [10] Orda A., Rom R.: Minimum Weight Paths in Time-Dependent Networks. Networks 3, 1991, 295÷319.
• [11] Orda A., Rom R.: Shortest-Path and Minimum Delay Algorithms in Networks with Time-Dependent Edge-Length. Journal of the ACM 37 (3), 1990, 607÷625.
• [12] Pallottino S., Scutella M. G.: Shortest Path Algorithms in Transportation models: classical and innovative aspects. Equilibrium and Advanced Transportation Modelling, Kluwer Academic Publishers 1998,245÷281.
• [13] Tarapata Z.: Adaptacyjny algorytm wyznaczania tras z prognozowaniem obcienia sieci, W: Grzywak A., Kwiecień A., Klamka J., Pochopień Cz. (red.): Nowe technologie sieci komputerowych, t.II, Wydawnictwo Komunikacji i Łączności, Warszawa 2006, 31÷41.
• [14] Tarapata Z.: Wielokryterialne problemy wyznaczania tras w sieciach komputerowych, W: Węgrzyn S., Czachorski T., Pochopień Cz. (red.): Wysokowydajne sieci komputerowe. Nowe technologie, Wydawnictwo Komunikacji i Łączności, Warszawa 2005, 183-193.
• [15] Tarapata Z.: Models and methods of movement planning and simulation in simulation aided system for operational training, Proceedings of the 6th NATO Regional Conference on Military Communication and Information Systems, 06-08 October, Zegrze (Poland) 2004, 152-161.
• [16] Tarapata Z.: Military route planning in battlefield simulation: effectiveness problems and potential solutions, Journal of Telecommunications and Information Technology, No. 4 (2003), 47÷56.
• [17] Wasiluk J.: Analiza porównawcza metod planowania tras w systemach nawigacji samochodowej. Praca magisterska napisana pod kierunkiem Z. Tarapaty, Wydział Cybernetyki, Wojskowa Akademia Techniczna, Warszawa 2006.
• [18] Wellman M., Ford M., Larson K.: Path planning under time-dependent uncertainty, Proceedings of the 11th Conference of Uncertainty in artificial intelligence, Montreal 1995, 532÷539.
• [19] Wójcik P.: Projekt i implementacja komputerowego systemu planowania przemieszczania w ruchu ulicznym z wykorzystaniem sieci uwarunkowanych czasowo. Praca magisterska napisana pod kierunkiem Z. Tarapaty, Wydział Cybernetyki, Wojskowa Akademia Techniczna, Warszawa 2005.
• [20] Wu Q., Hartley J., Al-Dabass D.: Time-Dependent Stochastic Shortest Path(s) Algorithms for a Scheduled Transportation Network. Intern. Journal of Simulation, vol.6, No 7-8, 2005, 53÷60.
• [21] Zhan F. B., Three Fastest Shortest Path Algorithms on Real Road Networks: Data Structures and Procedures, Journal of Geographic Information and Decision Analysis 1, 1997, 70+82.
• [22] Zhan F. B., Noon C. E., Shortest Path Algorithm: An Evaluation using Real Road Networks, Transportation Science 32, 1998, 65÷73.
• [23] Zhan F. B., Noon C. E.: A Comparison Between Label-Setting and Label-Correcting Algorithms for Computing One-to-One Shortest Paths, Journal of Geographic Information and Decision Analysis 4, 2000, 1÷13.
• [24] Zhao Y.: Vehicle Location and Navigation Systems, Artech House Publishers 1997.
• [25] http://geodepot.statcan.ca/Diss/2006Dissemination/Data/download_e.cfm.