基于GAAA算法的码头集卡优化调度研究
|
摘要
集装箱卡车(简称集卡)是在集装箱码头起重要作用的一种水平运输设备,在卸下货物、装载货物、转堆的过程中运用极其灵活、具有很大规模的数量、运载过程较为复杂。因此我们只有合理调度集卡、并对集卡进行优化配置,才能使整个作业过程能够高效的运载;集卡的调度、优化配置的合理性与否能够极大地推动堆场的利用率、影响堆场的生产成本等多个方面、并且还能影响堆场的机械设备的装卸速度,因此对集装箱码头的发展有着极大的影响。
论文首先介绍遗传算法和蚁群算法的概念、特点,以及每种算法的不足,然后提出采用遗传蚁群相融合的GAAA算法,该算法能够避开遗传算法和蚁群算法这两种算法的缺点,更好的发挥各自的优势。
其次论文重点研究了集卡的动态实时调度,包括实时调度的原则、实时调度的原理以及动态实时调度算法的基本步骤。并且本文针对目前研究现状的不足提出了拥塞的定义,并在考虑拥塞的条件下对集卡的动态实时调度进行了研究。
最后,本论文还着重研究了GAAA算法在集卡优化调度中的应用,确定了可行点集,以及信息素的更新策略和路径点的选择方法,并将信息熵引入蚁群算法,把信息熵作为算法终止的准则,提高算法的运行速度,实现自适应调节。本文运用MATLAB和WITNESS对实时调度算法进行仿真,其结果表明本文提出的集卡实时调度策略是合理可行的,对提高码头资源的利用率有明显的作用。本文研究成果为集装箱码头改进作业调度提供了可靠的科学依据。
Container trucks in the container terminals play an important role in loading, unloading and shifting cargo, with a large number and complicated transport processes. Therefore, only reasonable dispatch and optimized configuration of container trucks can guarantee the efficiency of the whole transportation process. Also, the feasibility of optimized dispatch for container trucks can promote the utilization of container yards and the handling velocity of the mechanical equipment and reduce the production cost of container yards, so it has a great influence on the development of container terminals.
This paper first introduces the concept and characteristics as well as the deficiency of the ant colony algorithm and the genetic algorithm. Then propose the GAAA algorithm combining the genetic algorithm and the ant colony algorithm, The algorithm can avoid the shortcomings of the genetic algorithm and ant colony algorithm, and play their respective advantages.
Second, this paper mainly studies the dynamic dispatching of the container trucks, including the principles, theories, basic procedures and application of the GAAA algorithm. Congestion is also referred to in this paper, including its definition, the feasible points distribution, the update strategy of pheromone and the selection methods of path points.
Finally, this paper shows the simulation experiment based on MATLAB and WITNESS algorithm and the analysis of the results. The results show that the proposed set of cards real-time scheduling policy is feasible, improving the utilization of terminal resources, significant role. This results of the container terminal provides a reliable scientific basis to improve job scheduling.
论文首先介绍遗传算法和蚁群算法的概念、特点,以及每种算法的不足,然后提出采用遗传蚁群相融合的GAAA算法,该算法能够避开遗传算法和蚁群算法这两种算法的缺点,更好的发挥各自的优势。
其次论文重点研究了集卡的动态实时调度,包括实时调度的原则、实时调度的原理以及动态实时调度算法的基本步骤。并且本文针对目前研究现状的不足提出了拥塞的定义,并在考虑拥塞的条件下对集卡的动态实时调度进行了研究。
最后,本论文还着重研究了GAAA算法在集卡优化调度中的应用,确定了可行点集,以及信息素的更新策略和路径点的选择方法,并将信息熵引入蚁群算法,把信息熵作为算法终止的准则,提高算法的运行速度,实现自适应调节。本文运用MATLAB和WITNESS对实时调度算法进行仿真,其结果表明本文提出的集卡实时调度策略是合理可行的,对提高码头资源的利用率有明显的作用。本文研究成果为集装箱码头改进作业调度提供了可靠的科学依据。
Container trucks in the container terminals play an important role in loading, unloading and shifting cargo, with a large number and complicated transport processes. Therefore, only reasonable dispatch and optimized configuration of container trucks can guarantee the efficiency of the whole transportation process. Also, the feasibility of optimized dispatch for container trucks can promote the utilization of container yards and the handling velocity of the mechanical equipment and reduce the production cost of container yards, so it has a great influence on the development of container terminals.
This paper first introduces the concept and characteristics as well as the deficiency of the ant colony algorithm and the genetic algorithm. Then propose the GAAA algorithm combining the genetic algorithm and the ant colony algorithm, The algorithm can avoid the shortcomings of the genetic algorithm and ant colony algorithm, and play their respective advantages.
Second, this paper mainly studies the dynamic dispatching of the container trucks, including the principles, theories, basic procedures and application of the GAAA algorithm. Congestion is also referred to in this paper, including its definition, the feasible points distribution, the update strategy of pheromone and the selection methods of path points.
Finally, this paper shows the simulation experiment based on MATLAB and WITNESS algorithm and the analysis of the results. The results show that the proposed set of cards real-time scheduling policy is feasible, improving the utilization of terminal resources, significant role. This results of the container terminal provides a reliable scientific basis to improve job scheduling.
引文
[1]魏重.集装箱码头物流作业系统集成优化调度研究：(博士学位论文)北京：北京交通大学,2007
[2]汪锋.集装箱港口生产作业系统仿真与规划方法研究：(硕士学位论文).武汉：武汉理工大学,2003
[3]曹志伟.优化TPS集卡调度系统提高集装箱码头装卸效率：(硕士学位论文).上海：上海海运学院,2003
[4]严政,陶德馨.基于动态优化组合的集装箱码头集卡调度技术.武汉：武汉理工大学学报.2006.28(4)：26-27.
[5]江涛,集装箱码头集卡资源整合使用的路径优化研究：(硕士学位论文).上海：上海交通大学,2006.
[6]尚晶,陶德鑫.集装箱码头集卡调度策略的仿真研究.武汉理工大学学报.2006.30(5)：827-828.
[7]Chuqian Zhang, Yat-wah Wan, Jiyin Liu, et al. Dynamic crane deployment in container storage yards[J]. Transpotation Research Part B,2002(36):537-555.
[8]Ebru K Bish, Thin-Yin Leong, Chung-Lun Li, et al. Analysis of a new vehicle scheduling and location problem[J]. Naval Research Logistic,2001(48):363-385.
[9]Kap Hwan Kima, Ki Young Kim. Rounting straddle carriers for the loading operation of containers using a beam search algorithm[J]. Computers and Industrial Engineering. 1999(36):109-136
[10]李正宜,张维全,曾静康.道路交通工程.重庆：重庆大学出版社,1992：33-52.
[11]S. C. Cho and A. N. Perakis. Optimal Liner Fleet Routing Strategies. Maritime Policy and Management,1996(19):113-116.
[12]Koksalan M, Sural H, Kirca O.A loeation - distribution application for a beer company.Europen Journal of Operational Reseateh,1995,50:60 - 24.
[13]AGNETIS A.planning the routing mix in FASs to minimize totalt ransportation time, Iniemational Jotunal of Flexible Manufacturing Systems,1996, (2):131-157.
[14]Dantzig.G,Ramser.J.The Truck Dispatehing Problem.ManagementSei.1959,6:80 - 91.
[15]Bodin, Golden, Assad, Ball.Routing and Scheduling of Vehielesand Crews:The state of Art[J].ComPuters&Operations Researeh, VOI:10,1983.
[16]Bullnheimer B,Hartl R,Strauss C.An improved ant system algorithm for the vehicle routing problem.Annals of Operations Research,1999,89(13):319-328
[17]Reimann M,Doerner K,Richard F H.D-Ants:savings based ants divide and conquer the vehicle routing problem.Computers & Operations Research,2004,31(4):563-591
[18]Kap Hwan Kima, Ki Young Kim. Rounting straddle carriers for the loading operation of containers using a beam search algorithm. Computers and Industrial Engineering. 1999(36):109-136
[19]真虹,码头建设规模计算机动态图形仿真优化方法的研究。工程设计CAD与智能建筑,1999(8)pp16-20
[20]张文修,梁怡.遗传算法的数学基础,西安：西安交通大学出版社,2000.
[21]阎平凡,张长水.人工神经网络与模拟进化计算.北京：清华大学出版社,2000.
[22]黄浩锋,陈少英.混合遗传算法概述.科技资讯,2008(12).
[23]向佐勇,刘正才.一种改进的混合遗传算法研究.计算机工程与科学,2008(9).
[24]Pawlak A. Rough sets[J]. International Journal of Information and Compute Sciences.1982,11(5):341-356.
[25]吴启迪,汪镭.智能蚁群算法及应用.上海：上海科技教育出版社,2004：1-21.
[26]段海滨.蚁群算法原理及其应用.北京：科学出版社,2005.
[27]刘志硕,中金升.基于解均匀度的车辆路径问题的自适应蚁群算法.系统仿真学报,2005,17(5)：1079-1083.
[28]马良,姚俭,范炳全.蚂蚁算法在交通配流中的应用.科技通报,2003,19(5)：377-380
[29]崔雪丽,马良,范炳全.车辆路径问题的蚂蚁搜索算法.系统工程学报,2004,19(4)：418-422
[30]邱峰,陈学广,迟嘉昱.一种改进的蚂蚁算法在多目标配路中的应用.华中科技大学学报,2003,31(4)：39-41
[31]万旭,林键良,杨晓伟.改进的最大-最小蚂蚁算法在有时间窗车辆路径问题中的应用.计算机集成制造系统.2005,11(4)：572-576
[32]Chuqian Zhang, Yat-wah Wan, Jiyin Liu, et al. Dynamic crane deployment in container storage yards. Transpotation Research Part B,2002(36):537-555.
[33]Ebru K Bish, Thin-Yin Leong, Chung-Lun Li, et al. Analysis of a new vehicle scheduling and location problem[J]. Naval Research Logistic,2001(48):363-385.
[34]张海青,李军,兰顺国.集装箱卡车调度方法研究.物流科技,2008(3)：122-125
[35]David Ronen. Short-term scheduling of vessels for shipping bulk or semi-bulk commodities originating in a single area. Operation Research Society of America. 1986, Vol.34, No.1, January-February:164-173.
[36]D. E. LANE, T. D. HEAVER and D. UYENO. Planning and scheduling for efficiency in liner shipping. Maritime Policy and Management,1987, Vol.14, No.2:109-125.
[37]Cho and Perakis, Optimal liner fleet routing strategies. Maritime Policy and Management, Vol.23, No.3.1996:249-259.
[38]Iakovou, E. Douligeris, C, Li,H.1p,C. and Yudhbir, L. A Maritime Global Route Planning Model for Hazardous Materials Transportation. Transporation Science, Vol.33, No.1,1999:34-48.
[39]Krishan Rana and R.G.Vickson. Routing Container Ships Using Lagrangean Relaxation and Decomposition. Transportation Science,1991(25):201-214.
[40]S. C. Cho and A. N. Perakis. Liner and Integer Linear Programming Models for Container Liner Fleet Routing Strategy, January 1994.
[41]潘登,郑应平,陆小芳.避免车辆路径拥塞的动态蚁群算法.计算机工程,2008,34(5)：1-4
[42]Dorigo M, Gambardella L M. Ant Colony System:A Cooperative Learning Approach to the Traveling Salesman Problem. IEEE Trans, on Evolutionary Computation,1997, 1(1):53-66.
[43]Dorigo M, Gambardella L M. Ant Colonies for the Traveling Salesman Problem. IEEE Trans, on Evolutionary Computation, BioSystems,1997,43(2):73-81.
[44]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.
[45]李士勇. 蚁群算法及其应用. 哈尔滨： 哈尔滨工业大学出版社,2004.
[46]DongPing Song, Jie Zhang ect. On cost-efficiency of the global container shipping network. Maritime and Policy & Management.2005, Vol.32, No.1:15-30.
[47]Maniezzo V, Carbonaro A. An ANTS henristic for the frequency assignment problem. Future Generation Computer Systems,2000,16.
[48]Stutzle T, Hoos H. MAX-min ant system,Future Generation Computer systems,2000,16.
[49]A. N. Perakis and D. I. Jaramillo. Fleet Deployment Optimization for Liner Shipping. Maritime Policy and Management.1991, Vol.18, No.3:183-200.
[50]陈瑂,沈洁,秦玲.蚁群算法进行连续参数优化的新途径.系统工程理论优化与实践.2003,3.
[51]Iwamura K, Liu B. Chance constrained integer programming models for capital budgeting in fuzzy environments. Journal of the Operational Research Society,1998, 49 (8):854-860.
[52]朱华炳,吕冬梅.基于WINTESS的生产物流系统仿真与优化.机械工程师.2003,3：134-135.
[53]刘勇.基于WINTESS仿真技术的随机型库存决策研究：(硕士学位论文).天津：天津工业大学,2006.
[54]韦尧兵,谢晓利,雷春丽.基于WINTESS的配送中心系统仿真设计.中国制造业信息化.2007,3：13.
[55]汪峰,陶德鑫.WINTESS在集装箱码头模拟系统中的应用.交通与计算机.2003,2：64-65.
[56]赵巍,田春林,白子健.基于WINTESS的集装箱码头内部物流作业系统仿真建模.交通标准化.2009,1：134-135.
[57]周强,吴继红.集装箱码头物流系统的仿真建模技术.港口装卸,2005,5： 57-60.
[58]郑大钟,赵千川.离散事件动态系统.北京：清华大学出版社,2001.
[59]蔡芸,张艳伟.集装箱码头泊位分配的仿真优化方法[J].中国工程机械学报,2006,4：228-232
[60]BUTLER KEITH A, BAHRAMI AL I, ESPOSITO CHRIS. Conceptual models for coordinating the design of user work with the design of information systems. Data & Knowledge Engi2neering,2000,33 (2):191-198.
[61]E. Kozan, Comparison of analytical and simulation planning models of seaport container terminals, Transportation Planning and Technology,1997,20 (3):235-248
[62]胡幼华,潘荫荣.随机性的批量制造库存系统的仿真模型.计算机工程,2003,8：70-73.
[63]真虹,集装箱码头生产过程动态图形仿真优化的研究。中国图象图形学报,1999.4A(6)pp502-506.
[2]汪锋.集装箱港口生产作业系统仿真与规划方法研究：(硕士学位论文).武汉：武汉理工大学,2003
[3]曹志伟.优化TPS集卡调度系统提高集装箱码头装卸效率：(硕士学位论文).上海：上海海运学院,2003
[4]严政,陶德馨.基于动态优化组合的集装箱码头集卡调度技术.武汉：武汉理工大学学报.2006.28(4)：26-27.
[5]江涛,集装箱码头集卡资源整合使用的路径优化研究：(硕士学位论文).上海：上海交通大学,2006.
[6]尚晶,陶德鑫.集装箱码头集卡调度策略的仿真研究.武汉理工大学学报.2006.30(5)：827-828.
[7]Chuqian Zhang, Yat-wah Wan, Jiyin Liu, et al. Dynamic crane deployment in container storage yards[J]. Transpotation Research Part B,2002(36):537-555.
[8]Ebru K Bish, Thin-Yin Leong, Chung-Lun Li, et al. Analysis of a new vehicle scheduling and location problem[J]. Naval Research Logistic,2001(48):363-385.
[9]Kap Hwan Kima, Ki Young Kim. Rounting straddle carriers for the loading operation of containers using a beam search algorithm[J]. Computers and Industrial Engineering. 1999(36):109-136
[10]李正宜,张维全,曾静康.道路交通工程.重庆：重庆大学出版社,1992：33-52.
[11]S. C. Cho and A. N. Perakis. Optimal Liner Fleet Routing Strategies. Maritime Policy and Management,1996(19):113-116.
[12]Koksalan M, Sural H, Kirca O.A loeation - distribution application for a beer company.Europen Journal of Operational Reseateh,1995,50:60 - 24.
[13]AGNETIS A.planning the routing mix in FASs to minimize totalt ransportation time, Iniemational Jotunal of Flexible Manufacturing Systems,1996, (2):131-157.
[14]Dantzig.G,Ramser.J.The Truck Dispatehing Problem.ManagementSei.1959,6:80 - 91.
[15]Bodin, Golden, Assad, Ball.Routing and Scheduling of Vehielesand Crews:The state of Art[J].ComPuters&Operations Researeh, VOI:10,1983.
[16]Bullnheimer B,Hartl R,Strauss C.An improved ant system algorithm for the vehicle routing problem.Annals of Operations Research,1999,89(13):319-328
[17]Reimann M,Doerner K,Richard F H.D-Ants:savings based ants divide and conquer the vehicle routing problem.Computers & Operations Research,2004,31(4):563-591
[18]Kap Hwan Kima, Ki Young Kim. Rounting straddle carriers for the loading operation of containers using a beam search algorithm. Computers and Industrial Engineering. 1999(36):109-136
[19]真虹,码头建设规模计算机动态图形仿真优化方法的研究。工程设计CAD与智能建筑,1999(8)pp16-20
[20]张文修,梁怡.遗传算法的数学基础,西安：西安交通大学出版社,2000.
[21]阎平凡,张长水.人工神经网络与模拟进化计算.北京：清华大学出版社,2000.
[22]黄浩锋,陈少英.混合遗传算法概述.科技资讯,2008(12).
[23]向佐勇,刘正才.一种改进的混合遗传算法研究.计算机工程与科学,2008(9).
[24]Pawlak A. Rough sets[J]. International Journal of Information and Compute Sciences.1982,11(5):341-356.
[25]吴启迪,汪镭.智能蚁群算法及应用.上海：上海科技教育出版社,2004：1-21.
[26]段海滨.蚁群算法原理及其应用.北京：科学出版社,2005.
[27]刘志硕,中金升.基于解均匀度的车辆路径问题的自适应蚁群算法.系统仿真学报,2005,17(5)：1079-1083.
[28]马良,姚俭,范炳全.蚂蚁算法在交通配流中的应用.科技通报,2003,19(5)：377-380
[29]崔雪丽,马良,范炳全.车辆路径问题的蚂蚁搜索算法.系统工程学报,2004,19(4)：418-422
[30]邱峰,陈学广,迟嘉昱.一种改进的蚂蚁算法在多目标配路中的应用.华中科技大学学报,2003,31(4)：39-41
[31]万旭,林键良,杨晓伟.改进的最大-最小蚂蚁算法在有时间窗车辆路径问题中的应用.计算机集成制造系统.2005,11(4)：572-576
[32]Chuqian Zhang, Yat-wah Wan, Jiyin Liu, et al. Dynamic crane deployment in container storage yards. Transpotation Research Part B,2002(36):537-555.
[33]Ebru K Bish, Thin-Yin Leong, Chung-Lun Li, et al. Analysis of a new vehicle scheduling and location problem[J]. Naval Research Logistic,2001(48):363-385.
[34]张海青,李军,兰顺国.集装箱卡车调度方法研究.物流科技,2008(3)：122-125
[35]David Ronen. Short-term scheduling of vessels for shipping bulk or semi-bulk commodities originating in a single area. Operation Research Society of America. 1986, Vol.34, No.1, January-February:164-173.
[36]D. E. LANE, T. D. HEAVER and D. UYENO. Planning and scheduling for efficiency in liner shipping. Maritime Policy and Management,1987, Vol.14, No.2:109-125.
[37]Cho and Perakis, Optimal liner fleet routing strategies. Maritime Policy and Management, Vol.23, No.3.1996:249-259.
[38]Iakovou, E. Douligeris, C, Li,H.1p,C. and Yudhbir, L. A Maritime Global Route Planning Model for Hazardous Materials Transportation. Transporation Science, Vol.33, No.1,1999:34-48.
[39]Krishan Rana and R.G.Vickson. Routing Container Ships Using Lagrangean Relaxation and Decomposition. Transportation Science,1991(25):201-214.
[40]S. C. Cho and A. N. Perakis. Liner and Integer Linear Programming Models for Container Liner Fleet Routing Strategy, January 1994.
[41]潘登,郑应平,陆小芳.避免车辆路径拥塞的动态蚁群算法.计算机工程,2008,34(5)：1-4
[42]Dorigo M, Gambardella L M. Ant Colony System:A Cooperative Learning Approach to the Traveling Salesman Problem. IEEE Trans, on Evolutionary Computation,1997, 1(1):53-66.
[43]Dorigo M, Gambardella L M. Ant Colonies for the Traveling Salesman Problem. IEEE Trans, on Evolutionary Computation, BioSystems,1997,43(2):73-81.
[44]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.
[45]李士勇. 蚁群算法及其应用. 哈尔滨： 哈尔滨工业大学出版社,2004.
[46]DongPing Song, Jie Zhang ect. On cost-efficiency of the global container shipping network. Maritime and Policy & Management.2005, Vol.32, No.1:15-30.
[47]Maniezzo V, Carbonaro A. An ANTS henristic for the frequency assignment problem. Future Generation Computer Systems,2000,16.
[48]Stutzle T, Hoos H. MAX-min ant system,Future Generation Computer systems,2000,16.
[49]A. N. Perakis and D. I. Jaramillo. Fleet Deployment Optimization for Liner Shipping. Maritime Policy and Management.1991, Vol.18, No.3:183-200.
[50]陈瑂,沈洁,秦玲.蚁群算法进行连续参数优化的新途径.系统工程理论优化与实践.2003,3.
[51]Iwamura K, Liu B. Chance constrained integer programming models for capital budgeting in fuzzy environments. Journal of the Operational Research Society,1998, 49 (8):854-860.
[52]朱华炳,吕冬梅.基于WINTESS的生产物流系统仿真与优化.机械工程师.2003,3：134-135.
[53]刘勇.基于WINTESS仿真技术的随机型库存决策研究：(硕士学位论文).天津：天津工业大学,2006.
[54]韦尧兵,谢晓利,雷春丽.基于WINTESS的配送中心系统仿真设计.中国制造业信息化.2007,3：13.
[55]汪峰,陶德鑫.WINTESS在集装箱码头模拟系统中的应用.交通与计算机.2003,2：64-65.
[56]赵巍,田春林,白子健.基于WINTESS的集装箱码头内部物流作业系统仿真建模.交通标准化.2009,1：134-135.
[57]周强,吴继红.集装箱码头物流系统的仿真建模技术.港口装卸,2005,5： 57-60.
[58]郑大钟,赵千川.离散事件动态系统.北京：清华大学出版社,2001.
[59]蔡芸,张艳伟.集装箱码头泊位分配的仿真优化方法[J].中国工程机械学报,2006,4：228-232
[60]BUTLER KEITH A, BAHRAMI AL I, ESPOSITO CHRIS. Conceptual models for coordinating the design of user work with the design of information systems. Data & Knowledge Engi2neering,2000,33 (2):191-198.
[61]E. Kozan, Comparison of analytical and simulation planning models of seaport container terminals, Transportation Planning and Technology,1997,20 (3):235-248
[62]胡幼华,潘荫荣.随机性的批量制造库存系统的仿真模型.计算机工程,2003,8：70-73.
[63]真虹,集装箱码头生产过程动态图形仿真优化的研究。中国图象图形学报,1999.4A(6)pp502-506.