滚装船舶配载优化问题的研究
摘要
随着我国经济正常有序的成长,航运业也得到了蓬勃的发展,散货船、集装箱船、滚装船在货物运输、进出口贸易中发挥着各自非常重要的作用,尤其是滚装船舶,以其自身独有的特点,越来越受到我国航运业的重视和青睐。
近几年来,无论是国内还是国外,滚装船舶都获得了很迅速的发展,这种情形大有代替中短途客船的趋势。滚装船舶市场发展潜力大,需求较旺盛,在这种情况下,船公司常常遇到供不应求的局面,面对这样一个潜力巨大的市场,如何保证在船舶安全航行的前提下,通过优化配载,利用有限的舱容来提高航次收入,是许多船东需要迫切解决的问题。这也是本文主要探究的一个问题。
国内外对滚装船配载优化的研究虽然不少,但是大都从定性方面来论述滚装船舶的安全问题,如车辆绑扎、系固,或者是从船舶自身的构造出发,进行设计。本文从船公司的角度出发,较深入地分析了滚装船舶配载的特点与意义,并针对不同情形,建立了单一装货港、单一卸货港的数学模型和多类型成品车的多装货港、多卸货港滚装船舶的数学模型,滚装船配载问题属于NP难问题,本文根据此问题的特点,将其归类成背包问题,并根据问题的特点,进行算法设计,通过大量的仿真实验以及与现实的调度规则的对比来验证算法的有效性和实用性,并且能够保证在合理的计算时间内就可找到高质量的近似解。
With the normal and orderly growing of the economy of our country, the shipping business undergoes flourishing development. The bulk carrier, the container ship and the roll-on roll-off ship are playing important part respectively in the shipment and the import and export trade, especially the roll-on roll-off ship. It receives more and more attention and favors.
In recent years, both in home and abroad, the roll-on roll-off ship has developed fast, which has the trend of taking place of the short and medium passenger ship. The market of the roll-on roll-off ship has great potentials in tremendous demand. The demand of the shipping company often exceeds supply. Faced with such a market, how to ensure that the revenue of voyage is increased with the limited capacity by optimized stowage under the premise of safe navigation. This is the research question being answered in this paper.
The overseas and domestic researches of optimized stowage of the roll-on roll-off ship are rare, most of which dwell on the safety issues of the roll-on roll-off ship in qualitative aspects. This paper deeply analyses the characteristics and significance of the stowage of the roll-on roll-off ship, and sets up the related mathematical model. In the issue of the stowage of the roll-on roll-off ship, it is an NP issue. This paper classifies this issue as the knapsack problem according to its characteristics and designs algorithm, and verifies the effectiveness of the proposed algorithm through examples, finding a high-quality approximate solution in reasonable time.
近几年来,无论是国内还是国外,滚装船舶都获得了很迅速的发展,这种情形大有代替中短途客船的趋势。滚装船舶市场发展潜力大,需求较旺盛,在这种情况下,船公司常常遇到供不应求的局面,面对这样一个潜力巨大的市场,如何保证在船舶安全航行的前提下,通过优化配载,利用有限的舱容来提高航次收入,是许多船东需要迫切解决的问题。这也是本文主要探究的一个问题。
国内外对滚装船配载优化的研究虽然不少,但是大都从定性方面来论述滚装船舶的安全问题,如车辆绑扎、系固,或者是从船舶自身的构造出发,进行设计。本文从船公司的角度出发,较深入地分析了滚装船舶配载的特点与意义,并针对不同情形,建立了单一装货港、单一卸货港的数学模型和多类型成品车的多装货港、多卸货港滚装船舶的数学模型,滚装船配载问题属于NP难问题,本文根据此问题的特点,将其归类成背包问题,并根据问题的特点,进行算法设计,通过大量的仿真实验以及与现实的调度规则的对比来验证算法的有效性和实用性,并且能够保证在合理的计算时间内就可找到高质量的近似解。
With the normal and orderly growing of the economy of our country, the shipping business undergoes flourishing development. The bulk carrier, the container ship and the roll-on roll-off ship are playing important part respectively in the shipment and the import and export trade, especially the roll-on roll-off ship. It receives more and more attention and favors.
In recent years, both in home and abroad, the roll-on roll-off ship has developed fast, which has the trend of taking place of the short and medium passenger ship. The market of the roll-on roll-off ship has great potentials in tremendous demand. The demand of the shipping company often exceeds supply. Faced with such a market, how to ensure that the revenue of voyage is increased with the limited capacity by optimized stowage under the premise of safe navigation. This is the research question being answered in this paper.
The overseas and domestic researches of optimized stowage of the roll-on roll-off ship are rare, most of which dwell on the safety issues of the roll-on roll-off ship in qualitative aspects. This paper deeply analyses the characteristics and significance of the stowage of the roll-on roll-off ship, and sets up the related mathematical model. In the issue of the stowage of the roll-on roll-off ship, it is an NP issue. This paper classifies this issue as the knapsack problem according to its characteristics and designs algorithm, and verifies the effectiveness of the proposed algorithm through examples, finding a high-quality approximate solution in reasonable time.
引文
[1]孙玉吕,龙熙陵.载车状态对滚装船稳性的影响航海工程,2004年第四期(总第161期)
[2]宋振洪.客滚船舶车辆的动态装载算法.计算机工程,2004.12.
[3]李冬梅.滚装客船承载车辆的积载、系固及其管理.中国海事.2008.
[4]王全作.滚装客船的积载、系固及其管理.航海技术,2000.
[5]洪碧光,夏国忠.滚装客船的安全性改进.世界海运,1999.
[6]杨晓红.基于Visual c++的0-1背包问题的贪婪算法.科技资讯导报,2007.
[7]Julije KARMINSKI. Ro-Ro Passenger Ship For Adriatic Outer Isles and the Croatian National Waters. BRODOGRADNJA,2005,315-322.
[8]Junbo Jia.Investigations of vehicle securing without lashings for Ro-Ro ships.J Mar Sci Technol.2007,12:43-57.
[9]Goyal S K. Economic packaging frequency of perishable jointly replenished. Operational Research Quarterly,1977,28(2):215-219.
[10]S.Surendran,S.K.Lee,J.Venkata Ramana Reddy,Gyoungwoo Lee.Non-linear roll dynamics of a Ro-Ro ship in waves. Ocean Engineering,2005,32(2005):1818-1828.
[11]薛毅,谢金星.优化建模与lindo/lingo软件.清华大学出版社,2005.
[12]魏明辉,崔英会.我国汽车滚装船运输发展研究.港口物流,2007.
[13]林鑫.基于0/1背包问题的讨论.微型电脑应用,2007.
[14]黄宇林.0/1背包问题的贪心算法.鄂州大学学报,2006.
[15]蒋力武坤.0-1背包问题贪婪算法应用研究.计算机与数学工程,2007.
[16]杜嘉立,张义军,船舶智能配载中的知识获取技术.大连海事大学学报,2006.
[17]王小平,曹立明.遗传算法.西安交通大学出版社,2002.
[18]王莉,稍定宏.基于遗传算法的0/1背包问题求解.计算机仿真,2006.3.
[19]耕新青.遗传算法及其应用.鞍山钢铁学院学报,2000.23(6)
[20]虞安波,杨家本.多背包问题的遗传算法求解.计算基数与自动化,2002.21(2)
[21]陈国良,王熙法,庄镇泉,王东生.遗传算法及其应用.人民邮电出版社,2001.
[22]孙玉吕,龙熙陵.滚装船的稳性横准.中国水运,2003.9.
[23]刘烽杰.船舶稳性研究.中国水运,2007.
[24]高勇军.汽车滚装运输船的特点和发展趋势.船舶设计通讯,2007.6.
[25]苗文钢,刘红.中国汽车滚装船运输发展存在的问题及应对措施.港航研究,2009.5.
[26]孙文一.中国汽车滚装船运输市场分析.世界海运,2007.12.
[27]任瑞征,严蔚敏.整数背包问题的应用及其算法研究.小型微型计算机系统,2001.2.
[28]严太山.用基于贪婪算法的混合遗传算法求解0/1背包问题.研究与开发,2007.8.
[29]王青春.滚装船发展前景及安全性World shipping,2000.4.
[30]靳志宏,金燕燕.滚装船配载优化算法及其软件化实现.中国航海,2010.
[31]刘培学.客滚船预配载软件系统的研究.大连海事大学学报,2009
[32]玄光南,程润伟.遗传算法与工程优化.清华大学出版社,2004.
[33]董美华,马汝建,徐梦华.基于Adina软件的滚装船模态分析.航海工程,2009.
[34]姚能文.滚装客船市场状况浅析.广船科技,2005.
[35]鲍江宏.用遗传算法实现罚函数法解多选择背包问题.计算机工程与设计,2008.9.
[36]唐喆.内贸滚装船运力及货量发展分析.工程技术,2009.
[37]郑建丽,马坤,纪卓尚.辽宁省陆岛现役滚装船的优选方法.船舶工程,2010.
[38]王金平,王玉新,曾维川.基于遗传算法的布局求解.天津大学学报,2005.
[39]陆鹏,高茂庭,李迎新.遗传算法在0-1一维背包问题上的应用研究.计算机与数字工程,2007.
[40]周云鹏,题正义.遗传算法在组合优化中的应用.辽宁工程技术大学学报,2007.
[41]P.C.CHU AND J.E.BEASLEY.A Genetic Algorithm for the Multidimensional Knapsack Problem. Journal of Heuristics,1998,4:63-86.
[42]Balas,E. An Additive Algorithm for Solving Linear Programs with Zero-one Variables. Operations Research,1965,13,517-546.
[43]Glover,F. Heuristics for Integer Programming Using Surrogate Constraints. Decision Science 8, 1997,156-166.
[44]Zanakis,S.H. Heuristics 0-1 Linear Programming:An Experimental Comparison of Three Methods. Management Science,1997,24,91-104.
[45]Freville,A.and GPlateau.An Efficient preprocessing Procedure for the Multidimensional 0-1 Knapsack Problem. Discrete Applied Mathematics,1994,49,189-212.
[46]Freville,A.and GPlateau.The 0-1 Bidimensional Knapsack Problem:Toward an Efficient High-Level Primitive Tool. Journal of Heuristics,1997,2,147-167.
[47]James S.K..Model and algorithms for multi-period sea cargo mix problem. European journal of Operation research,2006,5,1381-1393
[48]W.Shih.A branch and bound method for the multiconstraint zero-one knapsack problem. Management Science,1975,1417-1427
[49]E.F.Magirou,H.N.Psaraftis.Quantitative methods in shipping:A survey of current use and future trends. Athens University of Economics and Business,Report NO.E115,1992
[50]Y.Toyoda. A simplified algorithm for obtaining approximate solution to zero-one programming problems, Management Science,1975,1417-1427
[2]宋振洪.客滚船舶车辆的动态装载算法.计算机工程,2004.12.
[3]李冬梅.滚装客船承载车辆的积载、系固及其管理.中国海事.2008.
[4]王全作.滚装客船的积载、系固及其管理.航海技术,2000.
[5]洪碧光,夏国忠.滚装客船的安全性改进.世界海运,1999.
[6]杨晓红.基于Visual c++的0-1背包问题的贪婪算法.科技资讯导报,2007.
[7]Julije KARMINSKI. Ro-Ro Passenger Ship For Adriatic Outer Isles and the Croatian National Waters. BRODOGRADNJA,2005,315-322.
[8]Junbo Jia.Investigations of vehicle securing without lashings for Ro-Ro ships.J Mar Sci Technol.2007,12:43-57.
[9]Goyal S K. Economic packaging frequency of perishable jointly replenished. Operational Research Quarterly,1977,28(2):215-219.
[10]S.Surendran,S.K.Lee,J.Venkata Ramana Reddy,Gyoungwoo Lee.Non-linear roll dynamics of a Ro-Ro ship in waves. Ocean Engineering,2005,32(2005):1818-1828.
[11]薛毅,谢金星.优化建模与lindo/lingo软件.清华大学出版社,2005.
[12]魏明辉,崔英会.我国汽车滚装船运输发展研究.港口物流,2007.
[13]林鑫.基于0/1背包问题的讨论.微型电脑应用,2007.
[14]黄宇林.0/1背包问题的贪心算法.鄂州大学学报,2006.
[15]蒋力武坤.0-1背包问题贪婪算法应用研究.计算机与数学工程,2007.
[16]杜嘉立,张义军,船舶智能配载中的知识获取技术.大连海事大学学报,2006.
[17]王小平,曹立明.遗传算法.西安交通大学出版社,2002.
[18]王莉,稍定宏.基于遗传算法的0/1背包问题求解.计算机仿真,2006.3.
[19]耕新青.遗传算法及其应用.鞍山钢铁学院学报,2000.23(6)
[20]虞安波,杨家本.多背包问题的遗传算法求解.计算基数与自动化,2002.21(2)
[21]陈国良,王熙法,庄镇泉,王东生.遗传算法及其应用.人民邮电出版社,2001.
[22]孙玉吕,龙熙陵.滚装船的稳性横准.中国水运,2003.9.
[23]刘烽杰.船舶稳性研究.中国水运,2007.
[24]高勇军.汽车滚装运输船的特点和发展趋势.船舶设计通讯,2007.6.
[25]苗文钢,刘红.中国汽车滚装船运输发展存在的问题及应对措施.港航研究,2009.5.
[26]孙文一.中国汽车滚装船运输市场分析.世界海运,2007.12.
[27]任瑞征,严蔚敏.整数背包问题的应用及其算法研究.小型微型计算机系统,2001.2.
[28]严太山.用基于贪婪算法的混合遗传算法求解0/1背包问题.研究与开发,2007.8.
[29]王青春.滚装船发展前景及安全性World shipping,2000.4.
[30]靳志宏,金燕燕.滚装船配载优化算法及其软件化实现.中国航海,2010.
[31]刘培学.客滚船预配载软件系统的研究.大连海事大学学报,2009
[32]玄光南,程润伟.遗传算法与工程优化.清华大学出版社,2004.
[33]董美华,马汝建,徐梦华.基于Adina软件的滚装船模态分析.航海工程,2009.
[34]姚能文.滚装客船市场状况浅析.广船科技,2005.
[35]鲍江宏.用遗传算法实现罚函数法解多选择背包问题.计算机工程与设计,2008.9.
[36]唐喆.内贸滚装船运力及货量发展分析.工程技术,2009.
[37]郑建丽,马坤,纪卓尚.辽宁省陆岛现役滚装船的优选方法.船舶工程,2010.
[38]王金平,王玉新,曾维川.基于遗传算法的布局求解.天津大学学报,2005.
[39]陆鹏,高茂庭,李迎新.遗传算法在0-1一维背包问题上的应用研究.计算机与数字工程,2007.
[40]周云鹏,题正义.遗传算法在组合优化中的应用.辽宁工程技术大学学报,2007.
[41]P.C.CHU AND J.E.BEASLEY.A Genetic Algorithm for the Multidimensional Knapsack Problem. Journal of Heuristics,1998,4:63-86.
[42]Balas,E. An Additive Algorithm for Solving Linear Programs with Zero-one Variables. Operations Research,1965,13,517-546.
[43]Glover,F. Heuristics for Integer Programming Using Surrogate Constraints. Decision Science 8, 1997,156-166.
[44]Zanakis,S.H. Heuristics 0-1 Linear Programming:An Experimental Comparison of Three Methods. Management Science,1997,24,91-104.
[45]Freville,A.and GPlateau.An Efficient preprocessing Procedure for the Multidimensional 0-1 Knapsack Problem. Discrete Applied Mathematics,1994,49,189-212.
[46]Freville,A.and GPlateau.The 0-1 Bidimensional Knapsack Problem:Toward an Efficient High-Level Primitive Tool. Journal of Heuristics,1997,2,147-167.
[47]James S.K..Model and algorithms for multi-period sea cargo mix problem. European journal of Operation research,2006,5,1381-1393
[48]W.Shih.A branch and bound method for the multiconstraint zero-one knapsack problem. Management Science,1975,1417-1427
[49]E.F.Magirou,H.N.Psaraftis.Quantitative methods in shipping:A survey of current use and future trends. Athens University of Economics and Business,Report NO.E115,1992
[50]Y.Toyoda. A simplified algorithm for obtaining approximate solution to zero-one programming problems, Management Science,1975,1417-1427