표제지
요약(국문초록)
목차
1. 서론 17
1.1. 연구 배경 17
1.2. 관련 연구 19
1.2.1. 연안 항해 계획 19
1.2.2. 대양 항해 계획 22
1.3. Contributions 29
1.4. 논문의 구성 30
2. 이론적 근거 32
2.1. 지형 정보 표현 방법 32
2.1.1. 균일 격자 32
2.1.2. 쿼드트리 격자 33
2.1.3. 보로노이 다이어그램 35
2.2. 그래프 기반 항로 탐색 36
2.2.1. 다익스트라 알고리즘 38
2.2.2. A* 알고리즘 39
2.3. 항로 단순화 40
2.3.1. 더글라스-퓨커 알고리즘 40
2.3.2. 가시성 그래프 42
2.4. 항로 최적화 44
3. 데이터 획득 및 전처리 47
3.1. 수심 데이터 47
3.2. 해기상 데이터 51
3.2.1. GFS 52
3.2.2. RTOFS 55
4. 쿼드트리를 이용한 초기 항로 58
4.1. 쿼드트리 구조 58
4.2. 쿼드트리 그래프 생성 70
4.3. 가시성 그래프를 이용한 항로 단순화 93
5. 항법 그래프 97
5.1. 항로 탐색 범위 정의 97
5.2. 2D 항법 그래프 102
6. 항로 최적화 108
6.1. 연료 소모량 추정 108
6.2. 3D 동적 프로그래밍 117
7. 실험 결과 137
7.1. 문제 정의 137
7.2. 항법 그래프 생성 141
7.3. 항법 그래프 탐색 범위 제한 154
7.4. 항로 최적화 161
8. 결론 및 향후 연구 196
참고 문헌 200
Abstract 206
Table 1-1. Related works 28
Table 3-1. Metocean data 51
Table 3-2. GFS data spec 53
Table 3-3. RTOFS data spec 56
Table 5-1. Summary of variables 98
Table 6-1. Summary of variables 108
Table 6-2. Summary of variables 119
Table 6-3. Node properties at Stage 1, Node 0 129
Table 6-4. Node properties at Stage 4 131
Table 7-1. Principal dimensions of the KVLCC2 139
Table 7-2. Principal dimensions of the 1,800 TEU 139
Table 7-3. Quadtree computation time 142
Table 7-4. Result of building navigational graph, case 1 and 2 146
Table 7-5. Result of building navigational graph, case 3 and 4 148
Table 7-6. Navigational graph, case 5 and 6 150
Table 7-7. Navigational graph, case 7 and 8 152
Table 7-8. FOC reduction and computation time of different △t 155
Table 7-9. Comparison with varying boundary distances 158
Table 7-10. Comparison of the route optimization results in case 1 and 2 165
Table 7-11. Comparison of the route optimization results in case 3 and 4 168
Table 7-12. Comparison of the route optimization results in case 5 and 6 171
Table 7-13. Comparison of the route optimization results in case 7 and 8 174
Table 7-14. Optimization result of Suez Canal and Panama Canal case 186
Table 7-15. Expanded ETA range 192
Figure 1-1. Computed path on a real-world scenario. 20
Figure 1-2. Comparison of the shortest paths for the quadtree and visibility-graph for South Korea 21
Figure 1-3. Search area along great circle route 23
Figure 1-4. Extended search area along great circle line 24
Figure 1-5. Route planning in visibility graph map 25
Figure 1-6. Search graph generated with AIS trajectory data 26
Figure 1-7. Overall process of the paper 31
Figure 2-1. Edge connection from a node to 32 directions 33
Figure 2-2. Result of the application of PMR quadtree to South Korean islands 34
Figure 2-3. Undirected graph(left) and directed graph(right) 36
Figure 2-4. Route simplification using the ODP algorithm 42
Figure 2-5. Route simplification with visibility graph 43
Figure 2-6. Example of weather routing 45
Figure 3-1. Example of ENC data 48
Figure 3-2. GEBCO example, around the world(up), around the Jeju Island(down) 50
Figure 3-3. GFS wave mean period example 53
Figure 3-4. GFS wave significant height example 54
Figure 3-5. GFS wind speed example 54
Figure 3-6. RTOFS current example 56
Figure 3-7. Data overlay of the multilayer architecture 57
Figure 4-1. Terminology used to build quadtree structure 60
Figure 4-2. Example of region quadtree(left) and point region quadtree(right) 61
Figure 4-3. Example of polygonal map quadtree 61
Figure 4-4. Quadtree division example, step 1(depth 0) 62
Figure 4-5. Quadtree division example, step 2(depth 1) 63
Figure 4-6. Quadtree division example, step 3(depth 2) 63
Figure 4-7. Quadtree division example, step 4(depth 3) 64
Figure 4-8. Quadtree structure after division process with leaf node labeling 65
Figure 4-9. Comparison of the size of GEBCO data and root node of the quadtree with a depth of 17 66
Figure 4-10. Pseudo code of the quadtree division process 67
Figure 4-11. Example of ocean leaf nodes with no minimum depth condition 69
Figure 4-12. Example of ocean leaf node with minimum depth condition 5 70
Figure 4-13. Quadtree edge connection example. Visualization of edges(left), connection in quadtree structure(right) 71
Figure 4-14. Quadrants and sides 72
Figure 4-15. Neighbor connection operators 73
Figure 4-16. Example of the SONTYPE operator 73
Figure 4-17. Example of the ADJ operator 74
Figure 4-18. Example of the REFLECT operator 75
Figure 4-19. Example of the COMMONSIDE operator 75
Figure 4-20. Pseudo code of the great or equal adjacent neighbor search 76
Figure 4-21. Pseudo code of the smaller adjacent neighbor search 77
Figure 4-22. Pseudo code of the great or equal corner neighbor search 77
Figure 4-23. Pseudo code of the smaller corner neighbor search 78
Figure 4-24. Pseudo code of the neighbor connection methods for horizontal, vertical, and diagonal directions 78
Figure 4-25. Neighbor connection of equal size node with sharing parent 80
Figure 4-26. Neighbor connection of greater size node 82
Figure 4-27. Neighbor connection of smaller size node 85
Figure 4-28. Neighbor connection of worst case 87
Figure 4-29. Pseudo code of quadtree neighbor connection method to all directions 88
Figure 4-30. Disconnected nodes at the date line 89
Figure 4-31. Quadtree graph after stitching nodes at the date line 90
Figure 4-32. Dijkstra algorithm 91
Figure 4-33. (a)Uniform grid, (b) Quadtree grid, (c) Quadtree graph, (d) Initial route 92
Figure 4-34. Pseudo code of the visibility graph generation 93
Figure 4-35. Example of the visibility graph generation 95
Figure 4-36. Collision checks on (a)uniform grid, (b)quadtree grid 96
Figure 5-1. Adaptive boundary generation 101
Figure 5-2. 2D navigational graph 103
Figure 5-3. Active and inactive vertices and edges 104
Figure 5-4. Node connection constraints 105
Figure 5-5. Search space reduction 107
Figure 6-1. Wind resistance coefficients for tanker 110
Figure 6-2. Wind resistance coefficients for containership 110
Figure 6-3. Sign convention for wind direction 111
Figure 6-4. Brake horsepower estimation 114
Figure 6-5. Search for overlapping weather grids with a leg 116
Figure 6-6. Concept of the definition of ETA range 122
Figure 6-7. 3D nodes(right) defined on top of 2D navigational graph(left) 123
Figure 6-8. Example of forward propagation 124
Figure 6-9. Sub-optimality example of forward propagation 125
Figure 6-10. Pseudo code of the 3D dynamic programming 126
Figure 6-11. Navigational graph example 127
Figure 6-12. Node propagation from stage 0 to stage 1 128
Figure 6-13. Node propagation from stage 1 to node (2,0) 130
Figure 6-14. Node propagation from stage 2 to node (3,0) 130
Figure 6-15. Node propagation from stage 3 to node (4,0) 131
Figure 6-16. Node propagation from stage 1 to stage 2 133
Figure 6-17. Node propagation from stage 2 to stage 3 134
Figure 6-18. Node propagation from stage 3 to stage 4 135
Figure 6-19. Comparison between original solution and 3DDP solution 136
Figure 7-1. Original world map 143
Figure 7-2. Quadtree nodes after division with no minimum depth threshold 144
Figure 7-3. Quadtree nodes after division with minimum depth threshold 8 144
Figure 7-4. Quadtree graph example around south Korea 145
Figure 7-5. Process of building navigational graph of case 1 and 2, (a)initial path under quadtree, (b)visibility graph, (c)reference route, (d) navigational graph 147
Figure 7-6. Process of building navigational graph of case 3 and 4 (a)initial path under quadtree, (b)visibility graph, (c)reference route, (d) navigational graph 149
Figure 7-7. Process of building navigational graph of case 5 and 6 (b)visibility graph, (c)reference route, (d) navigational graph 151
Figure 7-8. Process of building navigational graph of case 7 and 8, (a)initial path under quadtree, (b)visibility graph, (c)reference route, (d) navigational graph 153
Figure 7-9. 3DDP routes with multiple △t in case 1 (eastbound) 156
Figure 7-10. 3DDP routes with multiple △t in case 2 (westbound) 157
Figure 7-11. Optimal routes with different boundary distances in case 7: 300km ~ 900km 160
Figure 7-12. Optimal routes with different boundary distances in case 8: 300km ~ 900km 161
Figure 7-13. Reference route 161
Figure 7-14. Speed optimization 162
Figure 7-15. Dijkstra + Speed optimization 163
Figure 7-16. Comparison of the route optimization results in case 1 166
Figure 7-17. Comparison of the route optimization results in case 2 167
Figure 7-18. Comparison of the route optimization results in case 3 169
Figure 7-19. Comparison of the route optimization results in case 4 170
Figure 7-20. Comparison of the route optimization results in case 5 172
Figure 7-21. Comparison of the route optimization results in case 6 173
Figure 7-22. Comparison of the route optimization results in case 7 175
Figure 7-23. Comparison of the route optimization results in case 8 176
Figure 7-24. Optimum route comparison in case 1 (eastbound) 177
Figure 7-25. Optimum route comparison in case 2 (westbound) 178
Figure 7-26. Optimum route comparison in case 3 (eastbound) 179
Figure 7-27. Optimum route comparison in case 4 (westbound) 180
Figure 7-28. Optimum route comparison in case 5 (eastbound) 181
Figure 7-29. Optimum route comparison in case 6 (westbound) 182
Figure 7-30. Optimum route comparison in case 7 (eastbound) 183
Figure 7-31. Optimum route comparison in case 8 (westbound) 184
Figure 7-32. Canal graph generation, Panama Canal (left) and Suez Canal (right) 186
Figure 7-33. Optimum route comparison in Panama Canal case 188
Figure 7-34. Optimum route comparison in Suez Canal case 189
Figure 7-35. Original ETA range 190
Figure 7-36. ETA-FOC curve with original ETA range in case 5 191
Figure 7-37. ETA-FOC curve with extended ETA range in case 1 193
Figure 7-38. ETA-FOC curve with extended ETA range in case 2 193
Figure 7-39. ETA-FOC curve with extended ETA range in case 3 194
Figure 7-40. ETA-FOC curve with extended ETA range in case 4 194
Figure 7-41. ETA-FOC curve with extended ETA range in case 5 194
Figure 7-42. ETA-FOC curve with extended ETA range in case 6 195
Figure 7-43. ETA-FOC curve with extended ETA range in case 7 195
Figure 7-44. ETA-FOC curve with extended ETA range in case 8 195