集卡动态调度路径优化算法

李广儒; 杨大奔; 任大伟

doi:10.19818/j.cnki.1671-1637.2012.03.013

集卡动态调度路径优化算法

doi: 10.19818/j.cnki.1671-1637.2012.03.013

1.
大连海事大学航海学院, 辽宁大连 116026
2.
中国海事局船舶检验处, 北京 100023

基金项目:

"十一五"国家科技支撑计划项目 2009BAG18B03

中央高校基本科研业务费专项资金项目 2009QN013

详细信息

作者简介:
李广儒(1970-), 男, 辽宁大连人, 大连海事大学副教授, 工学博士, 从事海上智能交通信息处理研究

中图分类号: U691.3
计量
- 文章访问数: 832
- HTML全文浏览量: 117
- PDF下载量: 946
- 被引次数: 0
出版历程
- 收稿日期: 2012-01-09
- 刊出日期: 2012-06-25

Path optimization algorithm of dynamic scheduling for container truck

1.
School of Navigation, Dalian Maritime University, Dalian 116026, Liaoning, China
2.
Ship Survey Department, Maritime Safety Administration of the People's Republic of China, Beijing 100023, China

More Information

Author Bio:
LI Guang-ru (1970-), male, associate professor, PhD, +86-411-84724329, liguangru@sina.com

摘要

摘要: 从整体调度的角度出发, 分析了整个码头作业面的动态调度方案, 提出了一种新的集装箱卡车(集卡)动态调度路径的自适应蚁群算法。运用码头GPRS系统, 以集卡速度、流量、位置等相关数据建立了感知链。通过判断阻塞状况和调整可行点集, 确定了信息素浓度更新策略与转移概率计算方法。针对码头路网的复杂性和蚁群算法的实时计算效率, 设计了蚁群算法的步骤。将信息熵引入到蚁群算法中, 运用MATLAB软件, 对集卡的动态调度方案进行了仿真计算。计算结果表明: 当初始集卡速度分别为50、75 km·h^-1, 初始集卡流量分别为800、1 000 veh·h^-1时, 集卡行驶的最短路径为4.3 km, 行驶时间为0.057 h;集卡行驶的最优路径为8.3 km, 行驶时间为0.111 h。可见, 该算法能有效缓解码头阻塞问题, 提高集卡利用率和码头作业效率。
- 港口运输 /
- 码头调度 /
- 集卡分配 /
- 最优路径 /
- 蚁群算法 /
- 信息熵
Abstract: From the point of integrated scheduling, the dynamic scheduling method of whole terminal operating field was analyzed, and a new adaptive ant colony optimization of dynamic scheduling for container truck was put out.The GPRS system of terminal was used, and the perception chain was set up by using related data such as the speed, flow and position of container truck.Through judging obstruction status and adjusting feasible point set, the calculation methods of updating strategy and transition probability for pheromone concentration were determined.Aiming at the complexity of terminal road network and the real-time calculation efficiency of ant colony optimization, the steps of ant colony optimization were designed.The information entropy was introduced into ant colony optimization, the MATLAB software was used, and the simulation calculation of dynamic scheduling method for container truck was carried out.Simulation result shows that when the initial speeds of container trucks are 50, 75 km·h^-1 respectively and the initial flows of container trucks are 800, 1 000 veh·h^-1 respectively, the shortest driving path of container truck is 4.3 km, and the driving time is 0.057 h.The optimal driving path of container truck is 8.3 km, and the driving time is 0.111 h.By using the proposed algorithm, the obstruction problem of terminal can be remitted effectively, and the utilization ratio of container truck and the operating efficiency of terminal can increase obviously.
- port transportation /
- terminal scheduling /
- container truck allocation /
- optimal path /
- ant colony optimization /
- information entropy

HTML全文

图 1 最优路径

Figure 1. Optimal path

下载: 全尺寸图片幻灯片

图 2 最短路径

Figure 2. Shortest path

下载: 全尺寸图片幻灯片

表 1 信息参数

Table 1. Information parameters

下载: 导出CSV

表 2 节点像素坐标

Table 2. Pixel coordinates of nodes

下载: 导出CSV

表 3 路径计算结果

Table 3. Calculation result of paths

下载: 导出CSV

参考文献(16)

[1]	VIS I F A, DE KOSTER R. Transshipment of containers at a container terminal: an overview[J]. European Journal of Operational Research, 2003, 147(1): 1-16. doi: 10.1016/S0377-2217(02)00293-X
[2]	MURTYA K G, LIU Ji-yin, WAN Y W, et al. A decision support system for operations in a container terminal[J]. Decision Support Systems, 2005, 39(3): 309-332. doi: 10.1016/j.dss.2003.11.002
[3]	寿涌毅, 赖昌涛, 吕如福. 班轮船舶调度多目标优化模型与蚁群算法[J]. 交通运输工程学报, 2011, 11(4): 84-88. http://transport.chd.edu.cn/article/id/201104013 SHOU Yong-yi, LAI Chang-tao, LU Ru-fu, et al. Multi-objective optimization model and ant colony optimization of liner ship scheduling[J]. Journal of Traffic and Transporta-tion Engineering, 2001, 11(4): 84-88. (in Chinese). http://transport.chd.edu.cn/article/id/201104013
[4]	张海霖, 江志彬, 许泓. 集装箱港口集疏运调度系统作业模式的仿真分析[J]. 上海交通大学学报, 2006, 40(6): 1024-1030. doi: 10.3321/j.issn:1006-2467.2006.06.033 ZHANG Hai-lin, JIANG Zhi-bin, XU Hong. A simulation study of container terminal scheduling system[J]. Journal of Shanghai Jiaotong University, 2006, 40(6): 1024-1030. (in Chinese). doi: 10.3321/j.issn:1006-2467.2006.06.033
[5]	于蒙, 王少梅. 基于多Agent的集装箱码头生产调度系统建模研究[J]. 武汉理工大学学报: 交通科学与工程版, 2007, 31(3): 494-498. doi: 10.3963/j.issn.2095-3844.2007.03.032 YU Meng, WANG Shao-mei. Reseach on modeling of multi-agent-based scheduling system for container terminal[J]. Journal of Wuhan University of Technology: Transportation Science and Engineering, 2007, 31(3): 494-498. (in Chinese). doi: 10.3963/j.issn.2095-3844.2007.03.032
[6]	韩晓龙, 丁以中. 集装箱港口装卸作业仿真系统[J]. 系统仿真学报, 2006, 18(8): 2366-2369. doi: 10.3969/j.issn.1004-731X.2006.08.079 HAN Xiao-long, DING Yi-zhong. Simulation system of con-tainer terminal charge/discharge operations[J]. Journal of System Simulation, 2006, 18(8): 2366-2369. (in Chinese). doi: 10.3969/j.issn.1004-731X.2006.08.079
[7]	周强, 王孟昌, 杨国平, 等. 集装箱码头道路交通仿真模型研究[J]. 水运工程, 2007(2): 48-52. https://www.cnki.com.cn/Article/CJFDTOTAL-SYGC200702011.htm ZHOU Qiang, WANG Meng-chang, YANG Guo-ping, et al. On traffic simulation model of container terminals[J]. Port and Waterway Engineering, 2007(2): 48-52. (in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-SYGC200702011.htm
[8]	ZENG Qing-cheng, YANG Zhong-zhen, LAI Lu-yuan. Models and algorithms for multi-crane oriented scheduling method in container terminals[J]. Transport Policy, 2009, 16(5): 271-278. doi: 10.1016/j.tranpol.2009.08.006
[9]	PETERINGA M E H, MURTYB K G. Effect of block length and yard crane deployment systems on overall per-formance at a seaport container transshipment terminal[J]. Computers and Operations Research, 2009, 36(5): 1711-1725. doi: 10.1016/j.cor.2008.04.007
[10]	ZHAO Wen-juan, GOODCHILD A V. The impact of truck arrival information on container terminal rehandling[J]. Transportation Research Part E: Logistics and Transportation Review, 2010, 46(3): 327-343. doi: 10.1016/j.tre.2009.11.007
[11]	NETO R F T, FILHO M G. A software model to prototype ant colony optimization algorithms[J]. Expert Systems with Applications, 2011, 38(1): 249-259. doi: 10.1016/j.eswa.2010.06.054
[12]	杨大奔. 基于GAAA算法的码头集卡优化调度研究[D]. 大连: 大连海事大学, 2010. YANG Da-ben. GAAA algorithm-based optimized dispatch for container trucks in container terminals[D]. Dalian: Dalian Maritime University, 2010. (in Chinese).
[13]	潘登, 郑应平, 陆小芳. 避免车辆路径阻塞的动态蚁群算法[J]. 计算机工程, 2008, 34(5): 1-4. https://www.cnki.com.cn/Article/CJFDTOTAL-JSJC200805003.htm PAN Deng, ZHENG Ying-ping, LU Xiao-fang. Dynamic ant colony algorithm for avoiding congestion on vehicle routes[J]. Computer Engineering, 2008, 34(5): 1-4. (in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-JSJC200805003.htm
[14]	DORIGO M, GAMBARDELLA L M. Ant colony system: a cooperative learning approach to the traveling salesman prob-lem[J]. IEEE Transactions on Evolutionary Computation, 1997, 1(1): 53-66. https://ieeexplore.ieee.org/abstract/document/585892
[15]	GAMBARDELLA L M, TAILLARD E, DORIGO M. Ant colonies for the quadratic assignment problem[J]. Journal of the Operational Research Society, 1999, 50(2): 167-176. doi: 10.1057/palgrave.jors.2600676
[16]	REIMANN M, DOERNER K, HARTL R F. Ants: savings based ants divide and conquer the vehicle routing problem[J]. Computers and Operations Research, 2004, 31(4): 563-591. https://www.sciencedirect.com/science/article/pii/S0305054803000145