摘要
集装箱船配载是海上集装箱运输的重要环节,随着集装箱船型的不断增大以及在各挂靠港口所装卸集装箱数量的增加,集装箱船配载问题的难度不断提高。集装箱船舶配载问题受到的约束条件较多、且不同目标之间相互制约,该问题是一个复杂的多目标优化问题。由于该问题的空间复杂性和时间复杂性,仅仅通过单一的优化方法来求解该问题是不现实的。本文在对该问题分析的基础上,将该问题分解为三个子问题进行研究。即集装箱船配载总图问题、集装箱堆场优化问题和集装箱箱位布置优化问题。
首先,根据集装箱船配载问题的特点,将集装箱船配载的总图确定问题作为一个物品尺寸可变、箱子容量可变的装箱问题,对传统的最优降序适应装箱算法进行了改进,采用对箱子和物品均进行排序的方法,建立了确定集装箱船舶配载总图的改进装箱算法。
集装箱堆场布置的好坏对集装箱码头的作业效率和装船质量影响很大,由于集装箱到港的随机性和箱子重量分布的随机性,在通常情况下要获得较好的堆场布置十分困难。在分析集装箱堆场和码头作业方式的基础上,采用启发式算法建立了集装箱堆场优化模型,为后续方便集装箱装船和保证装船后有良好的航行性能奠定了基础。
在确定集装箱船配载总图和建立集装箱堆场优化模型的基础上,为了获得更好的配载结果,建立了混合蚁群算法来优化集装箱在船上具体的箱位。通过该混合算法能够在保证装船速度的基础上获得较佳的箱位布置。
最后,根据集装箱船配载的结果,采用模糊综合评判的方法建立了集装箱船舶配载方案的综合评判系统,采用该系统能够较为客观地评价和选择配载方案。
Container ship's stowage is a key stage to container sea transportation. The problem of container ship's stowage optimization is getting more difficult due to the increasing of container ship's size and the number of containers loaded at calling ports. The problem is a multi-objectives combinatorial optimization with several operational and safety constraints. And different objectives are often in conflict. It is unrealistic to solve this problem through sole optimization algorithm. Based on analyzing the influencing factors to container ship's stowage, the problem is divided into three sub-problems:general plan problem, position optimization for export containers in yard and container position optimization on board.
At first, container ship's general plan problem can be treated as a Bin-packing problem with variable item size and bin capacity, while the items are containers and bins are different bays on board. An improved best fit decreasing algorithm is established by sorting both of items and bins according human planner's experience.
Container yard's layout also plays an important role on ship's stowage. But due to the randomicity of each export container's arrival and weight, it is very difficult to get a sound container yard layout. An optimization model based on heuristic algorithm is proposed to get better container yard layout while the way of handling and handling equipments in yard are taken into consideration.
In order to get better stowage result, a mixed Ant Colony Algorithm incorporated with Tabu Search is put up forward to allot each container's position on board. The mixed algorithm can refine the stowage position arrangement of containers while no hampering to loading efficiency and operation difficulty.
Finally, a fuzzy evaluation system is used to assess different stowage plans and select the best one.
引文
[1]Anna Sciomachen, Elena Tanfani. A 3D-BPP approach for optimising stowage plans and terminal productivity [J]. European Journal of Operational Research,2007,183:1433-1446.
[2]Ambrosino, D., Sciomachen, A., Tanfani, E. Stowing a containership:The Master Bay Plan problem [J]. Transportation Research,2004,A38:81-99.
[3]Ambrosino, D., Sciomachen, A., Tanfani, E. A Bay Assignment Algorithm for the containership stowage problem [J].Journal of Heuristics,2006,12(3):211-233.
[4]Imai, A., Nishimura, E., Papadimitriu, S., Sasaki, K. The containership loading problem [J]. International Journal of Maritime Economics,2002,4:126-148.
[5]Qingcheng Zeng, ZhongzhenYang. Integrating simulation and optimization to schedule loading operations in container terminals [J]. Computers & Operations Research,2009, 36:1935-1944.
[6]Qingcheng Zeng, ZhongzhenYang. Integrating simulation and optimization to schedule loading operations in container terminals [J]. Computers & Operations Research,2009, 36:1935-1944.
[7]Dubrovsky, O., Levitin, G., Penn, M. A genetic algorithm with compact solution encoding for the container ship stowage problem [J]. Journal of Heuristics,2002.8:585-599.
[8]Wilson, I.D., Roach, P.A. Container stowage planning:a methodology for generating computerised solutions [J]. Journal of the Operational Research Society,2000,51:1248-1255.
[9]汤岩,贾宏雨,廖洁君.混合遗传算法在装箱问题中的应用研究[J].计算机与现代化,2004,11：13-18.
[10]肖力.基于改进的免疫克隆算法的装箱问题研究[J].微计算机信息,2008,1：288-289.
[11]张大斌,刘桂琴,王婧,朱侯.基于群体编码方式的遗传算法求解装箱问题[J].计算机工程与设计,2008,12：3154-3156.
[12]屈援,王雪莲.大型二维装箱问题及其禁忌算法研究[J].安徽大学学报(自然科学版),2007,05：32-35.
[13]陈建新,杨宇航,龚玲,曾鹏.两种准在线装箱算法[J].计算机工程,2006,13：4-6.
[14]张德富,魏丽军,陈青山,陈火旺.三维装箱问题的组合启发式算法[J].软件学报,2007,09：2083-2089.
[15]徐丽丽,季忠,夏继梅.同规格货物装箱问题的优化计算[J].山东大学学报(工学版),2008,03：14-17.
[16]李波,石冰心.一种松弛的尺寸可变装箱问题及其在线算法[J].华中科技大学学报(自然科 学版),2005,02：28-30.
[17]尹晓峰,刘春煌.二次指派问题的蚁群算法研究[J].铁道运输与经济,2005,05：68-70.
[18]Nihan Cetin Demirel, M. Duran Toksari. Optimization of the quadratic assignment problem using an ant colony algorithm [J]. Applied Mathematics and Computation,2006,183(1):427-435.
[19]Peng-Yeng Yin, Shiuh-Sheng Yu, Pei-Pei Wang, Yi-Te Wang. Multi-objective task allocation in distributed computing systems by hybrid particle swarm optimization [J]. Applied Mathematics and Computation,2007,184(2):407-420.
[20]Dianxun Shuai, Qing Shuai, Yumin Dong. Particle model to optimize resource allocation and task assignment [J]. Information Systems,2007,32(7):987-995.
[21]Alfonsas Misevicius. An improved hybrid genetic algorithm:new results for the quadratic assignment problem [J].Knowledge-Based Systems,2004,17(2-4):65-73.
[22]Ayed Salman, Imtiaz Ahmad, Sabah Al-Madani. Particle swarm optimization for task assignment problem [J]. Microprocessors and Microsystems,2002,26(8):363-371.
[23]Y. Hani, L. Amodeo, F. Yalaoui, H. Chen.Ant colony optimization for solving an industrial layout problem [J].European Journal of Operational Research,2007,183(2):633-642.
[24]Tabitha James, Cesar Rego, Fred Glover.A cooperative parallel tabu search algorithm for the quadratic assignment problem [J].European Journal of Operational Research,2009,195(3):810-826.
[25]Zne-Jung Lee, Chou-Yuan Lee, Shun-Feng Su. An immunity-based ant colony optimization algorithm for solving weapon-target assignment problem [J].Applied Soft Computing,2002,2(1): 39-47.
[26]Kuo-Ling Huang, Ching-Jong Liao. Ant colony optimization combined with taboo search for the job shop scheduling problem [J].Computers & Operations Research,2008,35(4):1030-1046.
[27]谈文芳,赵强,余胜阳,肖人彬.改进粒子群优化算法求解任务指派问题[J].计算机应用,2007,12：2892-2895.
[28]黄茹.一种解决指派问题的蚁群算法[J].西安邮电学院学报,2006,03：106-109.
[29]焦永兰,刘晓霞,孙秉珍.最优指派问题的动态规划模型及算法[J].甘肃联合大学学报(自然科学版),2008,04：24-26.
[30]许殿,史小卫,程睿.回归蚁群算法[J].西安电子科技大学学报,2005,06：944-947.
[31]杨瑞,张海英,潘永湘.混合自适应蚁群算法及其应用研究[J].两安理工大学学报,2005,04：405-408.
[32]姜长元.动态信息素更新蚁群算法在指派问题中的应用[J].计算机工程,2008,15：187-189.
[33]李雪芹,彭其渊,丰伟,谢小淞.二维不平衡指派问题模型及粒子群算法求解[J].西南交通大学学报,2008,04：535-539.
[34]吴艳群,董鹏.求解大规模不对称指派问题的通用模拟退火算法[J].兰州交通大学学报, 2008,04：149-151.
[35]殷人昆,吴阳,张晶炜.蚁群算法解决指派问题的研究和应用[J].计算机工程与科学,2008,04：43-46.
[36]Yusin Lee, Shih-Liang Chao. A neighborhood search heuristic for pre-marshalling export containers [J]. European Journal of Operational Research,2009,196(2):468-475.
[37]Qingcheng Zeng, Zhongzhen Yang. Integrating simulation and optimization to schedule loading operations in container terminals [J].Computers & Operations Research,2009,36(6): 1935-1944.
[38]王伟.基于桥机效率的配载优化方法研究(硕士论文)[D].上海：上海交通大学,2007.
[39]高鹏.集装箱堆场作业调度优化问题研究(硕士论文)[D].大连：大连理工大学,2005.
[40]王孟昌.集装箱码头堆场箱位动态分配优化策略研究(硕士论文)[D].武汉：武汉理工大学,2007.
[41]李建忠,丁以中,王斌.集装箱堆场空间动态配置模型[J].交通运输工程学报,2007,(03)：50-55.
[42]张维英,林焰,纪卓尚.集装箱船全航线Bay位排箱优化模型[J].上海交通大学学报,2007,02：199-204.
[43]Peter Preston, Erhan Kozan. An approach to determine storage locations of containers at seaport terminals [J]. Computers & Operations Research,2001,28(10):983-995.
[44]张维英.集装箱船全航线配载智能优化研究(博士论文)[D].大连：大连理工大学,2005.
[45]车鉴.集装箱船舶配载计划优化研究(硕士论文)[D].上海：上海交通大学,2008.
[46]王晓,陈海燕,王超,刘单,吕长虹.关于合理确定集装箱码头装船顺序的算法[J].经济数学,2005,03：284-290.
[47]郝聚民,纪卓尚,戴寅生,林焰.集装箱船舶实配过程的遗传算法解决策略[J].中国造船,1999,03：8-14.
[48]张新艳.基于进化策略的港口集装箱装船作业优化[J].同济大学学报(自然科学版),2005,03：262-265.
[49]魏恒州.集装箱码头、船舶及装卸桥等级划分研究[C].天津港国际集装箱运输发展论坛论文集.2003.
[50]郝聚民.集装箱船舶实配遗传优化模型研究(博士论文)[D].大连：大连理工大学,1999.
[51]魏恒州.我国集装箱码头装卸工艺模式及发展[J].水运工程,2002,04：28-36.
[52]杨军.集装箱码头装卸设施使用状况和发展趋势[J].集装箱化,2006,12：21-24.
[53]黄平,孟永钢.最优化理论与方法[M].北京：清华大学出版社,2009.
[54]王凌.智能优化算法及其应用[M].北京：清华大学出版社,2001.
[55]邢文训,谢金星.最优化计算方法[M].北京：清华大学出版社,2005.
[56]王正元.基于状态转移的组合优化方法[M].西安：西安交通大学出版社,2010.
[57]Sneana Mitrovic-Minic, Abraham P.Punnen. Local search intensified:Very large-scale variable neighborhood search for the multi-resource generalized assignment problem [J]. Discrete Optimization,2009,6:370-377.
[58]黄友锐.智能优化算法及其应用[M].北京：国防工业出版社,2008.
[59]袁亚湘,孙文瑜.最优化理论与方法[M].北京：科学出版社,1997.
[60]唐焕文,秦学志.实用最优化方法[M].大连：大连理工大学出版社,2002.
[61]陈宝林.最优化理论与算法[M].北京：清华大学出版社,1989.
[62]徐成贤,陈志平,李乃成[M].近代优化方法.北京：科学出版社,2002.
[63]梁艳春,吴春国,时小虎等[M].群智能优化算法理论与应用.北京：科学出版社,2009.
[64]赖炎连,贺国平.最优化方法[M].北京：清华大学出版社,2008.
[65]李春明.优化方法[M].南京：东南大学出版社,2009.
[66]王晓陵,陆军.最优化方法与最优控制[M].哈尔滨：哈尔滨工程大学出版社,2006.
[67]何坚勇.最优化方法[M].北京：清华大学出版社,2007.
[68]Botter, R.C., Brinati, M.A.,. Stowage container planning:A model for getting an optimal solution [C]. IFIP Transactions B (Applications in Technology) 1992, B-5:217-229.
[69]Iris F.A. Vis,Rene de Koster.Transshipment of containers at a container terminal:an overview[J]. European Journal of Operational Research.2003,147:1-16.
[70]李锡蔚.集装箱船舶积载[M].北京：人民交通出版社,1997.
[71]Coffman E G, Garey M R, Johnson DS. Approximation algorithms for binpacking:a survey [A] [M]. Boston, MA.:PWS Publishing,1996:46-93.
[72]CoffmanE G,GalambosG, Martello S. Bin packing approximation algorithms:combinatorial analysis[A] [M]. Kluwer Academic Publishers,1998.
[73]张玉栋,蔡静,郝自军,何尚录.尺寸可变的装箱问题的近似算法的研究[J].兰州交通大学学报,2007,01：146-148.
[74]丁丹军.一种尺寸可变的装箱问题的在线近似算法[J].科技创新导报,2008,04：164.
[75]邢文训,陈锋.超尺寸物品装箱问题及其算法[J].应用数学学报,2002,01：8-14.
[76]C. Zhang, J. Liu, Y. Wan. Storage space allocation in container terminals [J]. Transportation Research,2003,B37:883-903.
[77]K. Kim, Y. Park, K. Ryu. Deriving decision rules to locate export containers in container yards [J]. European Journal of Operational Research,2000,124:89-101.
[78]Peter Preston, Erhan Kozan. An approach to determine storage locations of containers at seaport terminals [J]. Computers & Operations Research,2001,28:983-995.
[79]K. Kim, J. Bae. Re-marshalling export containers in port container terminals [J].Computers and Industry Engineering,1998,35:655-658.
[80]Y. Lee, N.Y. Hsu. An optimization model for the container Pre-Marshalling Problem [J]. Computers & Operations Research,2007,34:3295-3313.
[81]杨淑芹,张运杰,王志强.集装箱堆场问题的一个数学模型及其算法(英文)[J].大连海事大学学报,2002,S1：115-117.
[82]李建忠,丁以中,王斌.集装箱堆场空间动态配置模型[J].交通运输工程学报,2007,03：50-55.
[83]陈庆伟,王继荣.集装箱堆场出口箱堆存模型及其算法[J].物流科技,2007,7：106-108.
[84]张维英,林焰,纪卓尚.吴毅刚.出口集装箱堆场取箱作业优化模型研究[J].武汉理工大学学报(交通科学与工程版),2006,02：512-515.
[85]Akio Imai, Kazuya Sasaki, Etsuko Nishimura, Stratos Papadimitriou. Multi-objective simultaneous stowage and load planning for a container ship with container rehandle in yard stacks [J]. European Journal of Operational Research,2006,171(2):373-389.
[86]Kap Hwan Kim. Evaluation of the number of rehandles in container yards [J]. Computers & Industrial Engineering, Volume 32, Issue 4, September 1997, Pages 701-711.
[87]Kim KH. Evaluation of the number of rehandles in container yards [J]. Computers and Industry Engineering,1997,32:701-11.
[88]Yusin Lee, Shih-Liang Chao. A neighborhood search heuristic for pre-marshalling export containers [J].European Journal of Operational Research,2009,196:468-475.
[89]Anna Sciomachen, Elena Tanfani. A 3D-BPP approach for optimising stowage plans and terminal productivity [J].European Journal of Operational Research,2007,183(3):1433-1446.
[90]Vu Duc Nguyen, Kap Hwan Kim. A dispatching method for automated lifting vehicles in automated port container terminals [J]. Computers & Industrial Engineering,2009,56(3):1002-1020.
[91]Etsuko Nishimura, Akio Imai, Gerrit K. Janssens, Stratos Papadimitriou. Container storage and transshipment marine terminals [J].Transportation Research Part E:Logistics and Transportation Review,2009,45(5):771-786.
[92]郝聚民,纪卓尚,林焰.混合顺序作业堆场BAY优化模型[J].大连理工大学学报,2000,01：102-105.
[93]Dorigo M, Stutzle T. Ant colony optimization [M]. Cambridge,MA:MIT Press,2004.
[94]C.B. Cheng, C.P. Mao.A modified ant colony system for solving the travelling salesman problem with time windows [J]. Mathematical and Computer Modelling,2007,46:1225-1235.
[95]S.K. Chaharsooghi, Amir H. Meimand Kermani. An effective ant colony optimization algorithm (ACO) for multi-objective resource allocation problem (MORAP) [J]. Applied Mathematics and Computation,2008,200:167-177.
[96]Chi-Ming Lin, Mitsuo Gen. Multi-objective resource allocation problem by multistage decision-based hybrid genetic algorithm [J]. Applied Mathematics and Computation,2007,187: 574-583.
[97]W.J. Gutjahr,M.S. Rauner. An ACO algorithm for a dynamic regional nurse-scheduling problem in Austria [J]. Comp. Oper. Res,2007,41 (3):642-666.
[98]Aymerich F, Serra M. An ant colony optimization algorithm for stacking sequence design of composite laminates [J]. CMES-Comput Model Eng Sci,2006,13(1):49-66.
[99]Y. Gajpal,C. Rajendran. An ant-colony optimization algorithm for minimizing the completion-time variance of jobs in flowshops [J].Int. J. Prod. Econom,2006,101:259-272.
[100]Blum C. Ant colony optimization:introduction and recent trends [J].Phys Life Rev,2005, 2:353-73.
[101]R.J. Mullen, D. Monekosso, S. Barman. A review of ant algorithms [J]. Expert Systems with Applications,2009,36:9608-9617.
[102]汪定伟,王俊伟,王洪峰等.智能优化方法[M].北京：高等教育出版社,2007.
[103]Walter J. Gutjahr. First steps to the runtime complexity analysis of ant colony Optimization [J]. Computers & Operations Research,2008,35:2711-2727.
[104]石鸿雁,苏晓明.实用智能优化方法[M].大连：大连理工大学出版社,2009.
[105]Ozgur Baskan, Soner Haldenbilen, Huseyin Ceylan. A new solution algorithm for improving performance of ant colony optimization [J]. Applied Mathematics and Computation,2009, 211:75-84.
[106]M.H. Afshar. Improving the efficiency of ant algorithms using adaptive refinement: Application to storm water network design [J]. Advances in Water Resources,2006,29:1371-382.
[107]高尚.蚁群算法理论、应用及其与其他算法的混合(博士论文)[D].南京：南京理工大学,2005.
[108]胡保清.模糊理论基础[M].武昌：武汉大学出版社,2004.10.
[109]彭祖赠,孙韫玉.模糊数学(fuzzy)及其应用[M].武昌：武汉大出版社,2004.3.
[110]伍进.现代系统科学方法论及应用[M].成都：电子科技大学出版社,2005.
[111]中培萍.全局优化方法[M].北京：科学出版社,2006.
[112]施光燕,钱伟懿,庞丽萍.最优化方法[M].北京：高等教育出版社,2007.
[113]Csirik,A.van Vliet. An on-line algorithm formultidimensional bin packing[J].Operations ResearchLetters,1993, (13):149-158.
[114]尹晓峰,刘春煌.二次指派问题的蚁群算法研究[J].铁道运输与经济,2005,05：68-70.
[115]谈文芳,赵强,余胜阳,肖人彬.改进粒子群优化算法求解任务指派问题[J].计算机应用,2007,12：2892-2895.
[116]刘洋,樊治平.具有多种形式信息的指派问题的求解方法[J].系统工程,2008,05：73-78.
[117]黄茹.一种解决指派问题的蚁群算法[J].西安邮电学院学报,2006,03：106-109.
[118]梁耀,覃征,杨利英,黄茹.指派问题的变异蚁群算法求解[J].微电子学与计算机,2005,06：80-83.
[119]宿洁,韩强.多目标相关性指派问题的模拟退火算法[J].计算机工程与应用,2004,10：10-13.
[120]Xiaofan Yang, Qing Lu, Chuandong Li, Xiaofeng Liao.Biological computation of the solution to the quadratic assignment problem [J]. Applied Mathematics and Computation,2008,200(1): 369-377.
[121]Chin-Ching Chiu, Yi-Shiung Yeh, Jue-Sam Chou. A fast algorithm for reliability-oriented task assignment in a distributed system [J].Computer Communications,2002,25(17):1622-1630.
[122]Peng-Yeng Yin, Jing-Yu Wang. A particle swarm optimization approach to the nonlinear resource allocation problem [J].Applied Mathematics and Computation,2006,183(1):232-242.
[123]Valentina Ciriani, Nadia Pisanti, Anna Bernasconi. Room allocation:a polynomial subcase of the quadratic assignment problem [J]. Discrete Applied Mathematics,2004,144(3):263-269.
[124]David Pisinger. A fast algorithm for strongly correlated knapsack problems [J].Discrete Applied Mathematics,1998,89(1-3):197-212.
[125]Dianxun Shuai, Qing Shuai, Yumin Dong. Particle model to optimize resource allocation and task assignment [J]. Information Systems,2007,32(7):987-995.
[126]Alfonsas Misevicius. An improved hybrid genetic algorithm:new results for the quadratic assignment problem [J].Knowledge-Based Systems,2004,17(2-4):65-73.
[127]Ayed Salman, Imtiaz Ahmad, Sabah Al-Madani. Particle swarm optimization for task assignment problem [J]. Microprocessors and Microsystems,2002,26(8):363-371.
[128]Yossi Azar, Oded Regev, Jiri Sgall, Gerhard J. Woeginger. Off-line temporary tasks assignment [J].Theoretical Computer Science,2002,287(2):419-428.
[129]许殿,史小卫,程睿.回归蚁群算法[J].西安电子科技大学学报,2005,06：944-947.
[130]杨瑞,张海英,潘永湘.混合自适应蚁群算法及其应用研究[J].西安理工大学学报,2005,04：405-408.
[131]黄永青,梁昌勇,张祥德.基于均匀设计的蚁群算法参数设定[J].控制与决策,2006,01：93-96.
[132]林锦,朱文兴.凸整数规划问题的混合蚁群算法[J].福州大学学报(自然科学版),1999, 06：5-9.
[133]姜长元.动态信息素更新蚁群算法在指派问题中的应用[J].计算机工程,2008,15：187-189.
[134]刘心.关于多因素模糊指派问题的数学模型[J].东北财经大学学报,2008,06：26-28.
[135]任仙海,杨乐平,朱彦伟.基于整数规划的在轨服务任务指派问题研究[J].装备指挥技术学院学报,2008,02：52-56.
[136]李秦渝,代存杰.禁忌搜索算法解指派问题[J].甘肃科技,2007,10：24-26.
[137]吕宏伟,高永,黄启来,杨根源.空战多目标分配的指派模型[J].海军航空工程学院学报,2008,01：59-61.
[138]吴艳群,董鹏.求解大规模不对称指派问题的通用模拟退火算法[J].兰州交通大学学报,2008,04：149-151.
[139]郭强.人数少于任务数的全指派问题的迭代算法[J].计算机工程与应用,2007,24：91-94.
[140]刘飞,董明,侯文皓,翟钰.设施布局多重指标优化[J].上海交通大学学报,2007,04：664-668.
[141]王延臣,王全文,吴振奎.一个特殊指派问题及其解法[J].天津商学院学报,2007,06：25-28.
[142]樊治平,刘洋,孙永洪.一种具有序区间排序信息的多目标指派方法[J].工业工程与管理,2008,03：42-46.