Zastosowanie grafu widoczności w planowaniu trasy przejścia statku

Application of a visibility graph in ship’s path planning
Abstract: 

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.

Citation pattern: Lazarowska A., Zastosowanie grafu widoczności w planowaniu trasy przejścia statku, Scientific Journal of Gdynia Maritime University, No. 098, pp. 116-121, 2017

BibTeX     EndNote