abbr. SJ GMU
ISSN 2657-5841 (printed)
ISSN 2657-6988 (online)
DOI: 10.26408
Zastosowanie grafu widoczności w planowaniu trasy przejścia statku
Application of a visibility graph in ship’s path planning
https://orcid.org/0000-0002-6869-5553Abstract:
The article presents a proposal for solving the problem of determining a ship’s safe path using one of the graph theory methods. The aim of the study was to evaluate the possibility of the selected graph theory method application in planning a ship’s global route, taking into account the static navigational restrictions (lands, shallows). The navigational environment was modelled as a visibility graph using a rotational plane sweep algorithm. The shortest ship’s path is then determined using a Dijkstra's algorithm.
Streszczenie:
W artykule przedstawiono propozycję rozwiązania problemu wyznaczania trasy przejścia statku przy zastosowaniu jednej z metod teorii grafów. Celem pracy była ocena możliwości zastosowania wybranej metody teorii grafów w planowaniu globalnej trasy przejścia statku, uwzględniającej statyczne ograniczenia nawigacyjne (lądy, mielizny). Środowisko nawigacyjne zostało zamodelowane w postaci grafu widoczności przy zastosowaniu algorytmu obrotowego zamiatania płaszczyzny. Najkrótsza trasa przejścia statku wyznaczono następnie za pomocą algorytmu Dijkstry.
Słowa kluczowe:
algorytm Dijkstry
graf widoczności
planowanie trasy przejścia
teoria grafów
Issue:
Pages:
116
121
Download full text in pdf:
References:
Berg, M., Cheong, O., Kreveld, M., Overmars, M., 2008, Computational Geometry: Algorithms and Applications, Springer-Verlag.
Cormen, T.H., Stein, C., Rivest, R.L., Leiserson, C.E., 2001, Introduction to Algorithms, McGraw- Hill Higher Education.
Kuczkowski, Ł., Śmierzchalski, R., 2013, Zastosowanie wielopopulacyjnego algorytmu ewolucyjnego do problemu wyznaczania ścieżki przejścia, Zeszyty Naukowe Wydziału Elektrotechniki i Automatyki Politechniki Gdańskiej, nr 36.
Wojciechowski, J., Pieńkosz, K., 2013, Grafy i sieci, Wydawnictwo Naukowe PWN, Warszawa.