基于动态网格模型的航线自动生成算法

李源惠; 潘明阳; 吴娴

基于动态网格模型的航线自动生成算法

大连海事大学航海学院, 辽宁大连 116026

基金项目:

国家自然科学基金项目 60172044

详细信息

作者简介:
李源惠(1963-), 女, 山东青岛人, 大连海事大学副教授, 从事海上交通信息系统研究

中图分类号: U675
计量
- 文章访问数: 274
- HTML全文浏览量: 84
- PDF下载量: 220
- 被引次数: 0
出版历程
- 收稿日期: 2007-03-05
- 刊出日期: 2007-06-25

Automatic creating algorithm of route based on dynamic grid model

School of Navigation, Dalian Maritime University, Dalian 116026, Liaoning, China

More Information

Author Bio:
Li Yuan—hui(1963-), female, associate professor, +86-411-84729297, liyhdmu@sina.com

摘要

摘要: 为了充分利用电子海图信息, 进行航线设计, 提出了基于动态网格模型的航线自动生成算法。采用一个判断网格模型中方格可航性的快速算法, 对方格的可航性进行分类; 给出了一个有效地使用8个字节表示邻接方格8个方向的编码方法, 使邻接方格的连通性与字节的逻辑操作相对应; 提出了网格路径权序列均匀度概念, 给出了距离等长路径的优选方法, 分析了路径与所对应的实际航路长度的差异; 基于二分查找法, 求出航线上所有转向点的路径方格序列。研究结果表明: 基于动态网格模型所生成的航线可避开危险的障碍物, 是合理、安全的。
- 交通规划 /
- 网格模型 /
- 航线设计 /
- 电子海图
Abstract: In order to use the abundant information of electronic chart to plan route, an automatic creating algorithm of route based on dynamic grid model was put forward. The navigability of every single square in the model was judged and classified by using a fast algorithm. A coding scheme of square connectivity was proposed, square connectivity in eight directions was expressed by using byte with eight bits, so that square connectivity corresponds to the logical operation of byte.A concept of uniformity degree of path weigh in grid was given, and a method was proposed to select the optimal path from the same distance routes. The error analysis of the shortest path was done. The path square sequence of all redirection points in route was solved by using dimidiate search algorithm. Study result shows that the route generated by the algorithm is safe and rational because of keeping away from dangerous obstacles.
- traffic planning /
- grid model /
- route planning /
- electronic chart

HTML全文

图 1 方格可航性

Figure 1. Navigability of square

下载: 全尺寸图片幻灯片

图 2 不完全可航方格

Figure 2. Incomplete navigable square

下载: 全尺寸图片幻灯片

图 3 方格连通性与编码

Figure 3. Square connectivity and code

下载: 全尺寸图片幻灯片

图 4 简单不完全可航方格的连通性

Figure 4. Connectivity of simple incomplete navigable square

下载: 全尺寸图片幻灯片

图 5 方格的分解

Figure 5. Square decomposition

下载: 全尺寸图片幻灯片

图 6 等长度路径优选

Figure 6. Optimal routes with equal length

下载: 全尺寸图片幻灯片

图 7 路径长度误差分析

Figure 7. Error analysis of route length

下载: 全尺寸图片幻灯片

图 8 路径折线化

Figure 8. Line-folded route

下载: 全尺寸图片幻灯片

图 9 有效性的继承

Figure 9. Validity inheriting

下载: 全尺寸图片幻灯片

图 10 航线自动生成系统

Figure 10. Automatic creating system of route

下载: 全尺寸图片幻灯片

参考文献(11)

[1]	Gunnarsson H, Ronnqvist M, Carlsson D. Acombined terminal location and ship routing problem[J]. Journal of the Operational Research Society, 2006, 57(8): 928-938. doi: 10.1057/palgrave.jors.2602057
[2]	Christiansen M, Fagerholt K, Ronen D. Ship routing and scheduling: status and perspectives[J]. Transportation Science, 2004, 38(1): 1-18. doi: 10.1287/trsc.1030.0036
[3]	Azaron A, Kianfar F. Dynamic shortest path in stochastic dynamic networks: ship routing problem[J]. European Journal of Operational Research, 2003, 144(1): 138-156. doi: 10.1016/S0377-2217(01)00385-X
[4]	Bijlsma S J. On the applications of the principle of optimal evolutionin ship routing[J]. Journal of the Institute of Navigation, 2004, 51(2): 93-100. doi: 10.1002/j.2161-4296.2004.tb00343.x
[5]	李远林, 陈宏彬. 船舶最佳气象航线的设计[J]. 华南理工大学学报: 自然科学版, 1997, 25(12): 65-69. doi: 10.3321/j.issn:1000-565X.1997.12.013 Li Yuan-lin, Chen Hong-bin. Design of optimum ship route using weather routing techniques[J]. Journal of South China University of Technology: Natural Science, 1997, 25(12): 65-69. (in Chinese) doi: 10.3321/j.issn:1000-565X.1997.12.013
[6]	王凤武, 贾传荧. 船舶优选航线的研究[J]. 大连海事大学学报: 自然科学版, 1998, 24(2): 61-64. https://www.cnki.com.cn/Article/CJFDTOTAL-DLHS802.014.htm Wang Feng-wu, Jia Chuan-ying. The study on the optimal ship routing[J]. Journal of Dalian Mariti me University: Natural Science Edition, 1998, 24(2): 61-64. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-DLHS802.014.htm
[7]	张德高. 船舶航行计划[J]. 中国航海, 2001, 37(1): 66-69. https://www.cnki.com.cn/Article/CJFDTOTAL-ZGHH202001023.htm Zhang De-gao. Ship navigational plan[J]. Navigation of China, 2001, 37(1): 66-69. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-ZGHH202001023.htm
[8]	许开宇. 航路监视和航线设计的实现[J]. 上海海运学院学报, 2000, 21(4): 108-112. https://www.cnki.com.cn/Article/CJFDTOTAL-SHHY200004015.htm Xu Kai-yu. The completion of ship s track monitoring and route design[J]. Journal of Shanghai Maritime University, 2000, 21(4): 108-112. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-SHHY200004015.htm
[9]	李源惠, 孙少鹏, 于卫红. 电子海图中计划航线可行性的自动判别[J]. 大连海事大学学报: 自然科学版, 2000, 26(2): 40-43. https://www.cnki.com.cn/Article/CJFDTOTAL-DLHS200002010.htm Li Yuan-hui, Sun Shao-peng, Yu Wei-hong. Auto evaluation of the feasibility of planned sea route in ECDIS[J]. Journal of Dalian Maritime University: Natural Science Edition, 2000, 26(2): 40-43. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-DLHS200002010.htm
[10]	王志明. 航线设计教学软件系统的开发与研究[J]. 中国航海, 2000, 36(1): 88-94. https://www.cnki.com.cn/Article/CJFDTOTAL-ZGHH200001015.htm Wang Zhi-ming. Research and development of teaching software system of route planning[J]. Navigation of China, 2000, 36(1): 88-94. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-ZGHH200001015.htm
[11]	王晓东. 算法设计与分析[M]. 北京: 清华大学出版社, 2003.