基于多目标遗传算法的集装箱泊位—岸桥分配优化研究
|
摘要
泊位作为集装箱码头的稀缺资源,其调度工作质量的高低直接影响码头装卸作业的效率,影响集装箱班轮的船期和港口企业的声誉,同时,也体现着码头的管理水平和综合竞争实力。实践中,泊位分配的同时也进行相应作业岸桥数目的安排,即码头调度人员根据一定的优化策略及泊位、岸桥是否空闲等约束条件,为一系列到港船舶安排靠泊顺序、靠泊泊位及确定作业岸桥数目。与单纯的泊位分配和岸桥分配相比,泊位-岸桥分配把两者当成一个整体,能有效反映其相互影响相互制约的关系,更符合码头生产组织的实际情况。
集装箱码头泊位、岸桥分配问题是典型的NP难题,一直以来很难用精确算法求解。目前,大多数研究以缩短船舶在港时间或者码头生产成本最低为目标,采用启发式算法或全局搜索进化算法进行求解。但这些研究倾向于单目标求解算法或者将多目标转化为单目标进行求解,而集装箱码头泊位优化分配本应对多个目标同时进行优化,这对算法实施的结果影响较大。因此,在多目标模型求解过程中显然需要加以考虑。
考虑到泊位-岸桥多目标优化分配模型求解的复杂性,本文在前人研究的基础上,提出了一种改进多目标遗传算法,用以求解集装箱码头泊位-岸桥优化分配问题。模型部分,从船舶服务需求和码头综合效益两方面出发,主要选取以船舶平均在港时间和码头生产成本为目标的数学模型。模型求解采用改进多目标遗传算法,首先采用染色体组的方式表示个体即模型的可行解,为保证Pareto最优解集的分散性和均匀性,采用随机方法生成初始种群；其次,给出了多个约束条件下的交叉算子运算规则,同时引入岸桥分配启发式算法确定模型从属变量,以求得个体的目标函数值,并应用Pareto分级方法和个体拥挤距离计算进行适应度值评价；最后,针对算法求出的Pareto最优解集,给出了一种泊位-岸桥分配最终实施方案的选择策略。经过算例表明,与传统单目标优化相比,本文提出的优化方法能获得使码头综合效益较大的满意解,同时也证明了该优化模型和算法的有效性。
As rare resources of container terminals, the berths'scheduling levels directly affect the efficiency of cargo-handling in terminal, sailing schedule of container liner and reputation of port enterprise, and reflect management level and comprehensive competitive power of terminal, In practice, berths scheduling together with the allocation of quay cranes, that is, according to a certain optimizing tactics and some constraints such as the berth, quay cranes are free or not, the terminal scheduling worker arranges berthing order, berth and the quality of loading-uploading quay cranes for the container vessels arrived. Comparing with the separated berth allocation or quay crane allocation, the berth-quay crane allocation makes the two as a whole system, which can efficiently reflects the relationship of each influence and each restriction, it corresponds with the actual terminal production organization better.
The berth-quay crane allocation problem of container terminal is typical NP-hard problem, which is hardly solved by exact algorithm. At moment, most researches make the reduction of vessels'service time or the terminal's production cost as the goals, then sovle the problem by heuristic algorithm or global search evolutionary algorithm. But this kind of researches prefer to the single optimization or changing MOP into single optimization, the berth allocation optimization should solve the goals together, which has confluences on results of the algorithm. So it is apparent to consider the factors in the berth scheduling optimization.
Considering the complexity of berth-quay crane allocation MOP's solution, the multi-objective genetic algorithm is adopted in this essay, and improved based on the study of predecessors, in order to solve the berth-quay crane allocation problem of container terminals. In model, starting from vessels'service demand and container terminal's comprehensive benefits, this paper chooses a multi-objective optimization model, simultaneously considering the stay time of vessels and the production cost as optimization objectives. To solve the model, improved multi-objective genetic algorithm is adopted. Firstly, the individuals, which are the feasible solutions of model, are expressed by genome. In order to ensure the dispersion and uniformity of Pareto optimum set, the initial population is produced by the way of random method. Secondly, a cross rule is given to deal with the restriction conditions as well as model's dependent variables are determined by a quay crane heuristic, to calculate the individuals values, and the individuals'fitness is evaluated by the Pareto ranking method. Further more, a strategy is suggested to choose a valid berth-quay crane allocation schedule from the Pareto optimum solutions. Finally, experiments are given to verify the efficiency of the model and method, while the results show that a satisfied solution can be obtained by the approach proposed in this thesis.
集装箱码头泊位、岸桥分配问题是典型的NP难题,一直以来很难用精确算法求解。目前,大多数研究以缩短船舶在港时间或者码头生产成本最低为目标,采用启发式算法或全局搜索进化算法进行求解。但这些研究倾向于单目标求解算法或者将多目标转化为单目标进行求解,而集装箱码头泊位优化分配本应对多个目标同时进行优化,这对算法实施的结果影响较大。因此,在多目标模型求解过程中显然需要加以考虑。
考虑到泊位-岸桥多目标优化分配模型求解的复杂性,本文在前人研究的基础上,提出了一种改进多目标遗传算法,用以求解集装箱码头泊位-岸桥优化分配问题。模型部分,从船舶服务需求和码头综合效益两方面出发,主要选取以船舶平均在港时间和码头生产成本为目标的数学模型。模型求解采用改进多目标遗传算法,首先采用染色体组的方式表示个体即模型的可行解,为保证Pareto最优解集的分散性和均匀性,采用随机方法生成初始种群；其次,给出了多个约束条件下的交叉算子运算规则,同时引入岸桥分配启发式算法确定模型从属变量,以求得个体的目标函数值,并应用Pareto分级方法和个体拥挤距离计算进行适应度值评价；最后,针对算法求出的Pareto最优解集,给出了一种泊位-岸桥分配最终实施方案的选择策略。经过算例表明,与传统单目标优化相比,本文提出的优化方法能获得使码头综合效益较大的满意解,同时也证明了该优化模型和算法的有效性。
As rare resources of container terminals, the berths'scheduling levels directly affect the efficiency of cargo-handling in terminal, sailing schedule of container liner and reputation of port enterprise, and reflect management level and comprehensive competitive power of terminal, In practice, berths scheduling together with the allocation of quay cranes, that is, according to a certain optimizing tactics and some constraints such as the berth, quay cranes are free or not, the terminal scheduling worker arranges berthing order, berth and the quality of loading-uploading quay cranes for the container vessels arrived. Comparing with the separated berth allocation or quay crane allocation, the berth-quay crane allocation makes the two as a whole system, which can efficiently reflects the relationship of each influence and each restriction, it corresponds with the actual terminal production organization better.
The berth-quay crane allocation problem of container terminal is typical NP-hard problem, which is hardly solved by exact algorithm. At moment, most researches make the reduction of vessels'service time or the terminal's production cost as the goals, then sovle the problem by heuristic algorithm or global search evolutionary algorithm. But this kind of researches prefer to the single optimization or changing MOP into single optimization, the berth allocation optimization should solve the goals together, which has confluences on results of the algorithm. So it is apparent to consider the factors in the berth scheduling optimization.
Considering the complexity of berth-quay crane allocation MOP's solution, the multi-objective genetic algorithm is adopted in this essay, and improved based on the study of predecessors, in order to solve the berth-quay crane allocation problem of container terminals. In model, starting from vessels'service demand and container terminal's comprehensive benefits, this paper chooses a multi-objective optimization model, simultaneously considering the stay time of vessels and the production cost as optimization objectives. To solve the model, improved multi-objective genetic algorithm is adopted. Firstly, the individuals, which are the feasible solutions of model, are expressed by genome. In order to ensure the dispersion and uniformity of Pareto optimum set, the initial population is produced by the way of random method. Secondly, a cross rule is given to deal with the restriction conditions as well as model's dependent variables are determined by a quay crane heuristic, to calculate the individuals values, and the individuals'fitness is evaluated by the Pareto ranking method. Further more, a strategy is suggested to choose a valid berth-quay crane allocation schedule from the Pareto optimum solutions. Finally, experiments are given to verify the efficiency of the model and method, while the results show that a satisfied solution can be obtained by the approach proposed in this thesis.
引文
[1]Edmond E D, Maggs R P. How useful are queue models in port investment decisions for container berths[J]. Journal of the Operational Research Society.1978,19(8): 741-750.
[2]Lai K K, Shih K. A study of container berth allocation[J]. Journal of advanced transportation,1992,26(1):45-60.
[3]Imai A, Nagaiwa K, Tat C W. Efficient planning of berth allocation for container terminals in Asia[J]. Journal of advanced transportation,1997,31(1):75-94.
[4]Imai A, Nishimura E, Papadimitriou S. The dynamic berth allocation problem for a container port[J]. Transportation Research Part B,2001,35:401-417.
[5]Chen C Y, Hsieh T W. A time space network model for the berth allocation problem[J].19th IFIP TC6 Conference on System Modeling and Optimization, Cambridge, UK,1999,7.
[6]Legato P, Mazza R M. Berth planning and resources optimization at a container terminal via discrete event simulation [J]. European Journal of Operational Research,2001,133(3):537-547.
[7]韩笑乐,陆志强,奚立峰。具有服务优先级别的动态离散泊位调度优化[J],上海交通大学学报,2009.43(6)：902-905
[8]李强,杨春霞,王诺,佟士祺.集装箱码头泊位生产调度均衡优化[J].沈阳建筑大学学报(自然科学版),2008,24(6)：1132-1136.
[9]Lim A. The berth scheduling problem[J]. Operations Research Letters,1998, 22:105-110.
[10]Kim K H, Moon K C. Berth scheduling by simulated annealing[J]. Transportation Research Part B,2003,37:541-560.
[11]张煜,王少梅.基于遗传算法的泊位连续化动态调度研究[J].系统仿真学报,2007,19(10)：2161-2164.
[12]王红湘,严伟.基于启发式算法与仿真优化的岸壁线长度泊位分配策略[J].上海海事大学学报,2008,29(1)：19-22.
[13]GUAN Y P, XIAO W Q, CHEUNG R K, et al. A multi-processor task scheduling model for berth allocation:Heuristic and worst-case analysis[J]. Operations Research Letters,2002,30:343-350.
[14]KIM K H, Park Y M. A crane scheduling method for port container terminals[J]. European Journal of Operational Research,2004,156(3):752-768.
[15]周鹏飞,面向不确定环境的集装箱码头优化调度研究[D].大连理工大学博士学位论文,2005.10.
[16]蔡云,孙国正.同时求解泊位分配及岸桥调度问题的仿真优化方法.2005年全国博士生学术论坛交通运输工程学科论文集.北京：2005年全国博士生学术论坛组委会,2005：542-546.
[17]韩骏,孙晓娜,靳志宏.集装箱码头泊位与岸桥协调调度优化[J].大连海事大学学报,2008,34(2)：117-121.
[18]LIANG C, HUANG Y, YANG Y. A quay crane dynamic scheduling problem by hybrid evolutionary algorithm for berth allocation planning[J]. Computers & Industrial Engineering,2009,56:1021-1028.
[19]LEE Y, CHEN C Y. An optimization heuristic for the berth scheduling problem[J]. European Journal of Operation Research,2009,196:500-508.
[20]Steuer R E, Multiple Criteria Optimization; Theroy, Computation, and Application. New York; Wiley,1986.
[21]崔逊学.多目标进化算法及其应用[M].北京：国防工业出版社,2006：40-76.
[22]阮宏博,基于遗传算法的工程多目标优化研究[D],大连理工大学硕士学位论文,2007.6.
[23]刘光,基于多目标粒子群算法的港口调度系统设计与实现[D],哈尔滨工程大学硕士学位论文,2008.2.
[24]R.S.Rosenberg. Simulation of genetic populations with biochemical properties[D]. PhD thesis. University of Michigan Ann Harbor, Michigan,1967.
[25]ISHIBASHI H, AGUIRRE H E, TANAKA K, et al. Multi-objective optimization with improved genetic algorithm[C]. Systems, Man, and Cybernetics,2002.
[26]KALYANMOY D, AMRIT P, SAMEER A, et al. A fast and elitist multi-objective genetic algorithm NSGA-II[J]. IEEE Transactions on Evolutionary Computation,2002,6 (2):182-197.
[27]H. W. Kuhn and A. W. Tucker. Nonlinear programming. In J. Neyman, editor, Proceedings of the Second Berkeley Symposium on Mathematical Statistics and Probability[R], Berkeley, California, University of California Press,1951,:481-492
[28]Schaffer, J. D., Some experiments in machine learning using vector evaluated genetic algorithms. Unpublished doctoral dissertation, Vanderbilt University, 1984.
[29]Fonseca C M, Fleming P J.Genetic algorithms for Multiobjective optimization: Formulation, discussion and generalization[J]. Presented at Proceeding of the 5th International Conference on Genetic Algorithms, San Mateo, California,1993.
[30]Todd D. S. Sen P. A. Multiple Criteria Genetic Algorithm for Container ship Loading[J]. Proceedings of the Seventh International Conference on Genetic Algorithms, Miehigan State University:Morgan Kaufmann Publishers,1997:674-681.
[31]齐延才.集装箱物流操作实务[M].大连：大连海事大学出版社.2007.5：73-107.
[32]蔡芸,张艳伟.集装箱码头泊位分配的仿真优化方法[J].中国工程机械学报.2006.4(2)：228-232
[33]张燕涛.基于遗传算法的泊位调度问题优化研究及仿真[D].武汉理工大学硕士学位论文,2005.3.
[34]杨春霞,王诺.基于Memetic算法的集装箱码头泊位岸桥调度问题研究[J].计算机应用研究.2007.24(6).
[35]周鹏飞,康海贵.面向随机环境的集装箱码头泊位-岸桥分配方法[J].系统工程理论与实践,2008,1：161-168.
[36]唐焕文,秦学志.实用最优化方法[M].大连：大连理工大学出版社,2004：244-249.
[37]玄光男,程润伟.遗传算法与工程优化[M].北京：清华大学出版社,2004：79-82.
[38]雷德明,严新平.多目标智能优化算法及其应用[M].北京：科学出版社.2009.3：31-33.
[39]Goldberg D E. Genetic Algorithm in Search, Optimization and Machine Learning. NJ:Addison Wesley,1989.
[40]潘正军,康立山,陈毓屏.演化计算.北京：清华大学出版社,1999：65-99.
[41]Goldberg D E, Deb K. A Comparative analysis of selection schemes used in genetic algorithms//Rawlins G. Foundations of Genetic Algorithm. San Fransisco:Morgan Kaufmann,1991:76-78.
[42]Syswerda G. Uniform crossover in gernetic algorithm//Proceeding of 3th International Conference on Genetic algorithms. San Fransisco:Morgan Kaufmann,1993:124-131.
[43]蔡焕芹,基于多目标遗传算法的预拌混凝土车辆调度[D],上海交通大学硕士学位论文,2007.2.
[44]崔逊学.多目标进化算法及其应用[M].北京：国防工业出版社,2006：9-11.
[45]柴志刚.集装箱码头泊位调度多目标优化方法研究[D].大连海事大学硕士学位论文,2009.6.
[46]郑金华.多目标进化算法及其应用[M].北京：科学出版社,2007：105-123.
[47]宋羚.基于多目标遗传算法和SVM的特征选择方法[D].华中科技大学硕士学位论文.2007.6.
[48]Zitzler E, Thiele L. Multibojective evolutionary algorithms:A comparative case study and strength Pareto approach. IEEE Transaction on Evolutionary Computation, 1999,3:257-271.
[49]Coello C A C. Constraint-handling using an evolutionary multibojective optimization technique. Civil Engineering and Environmental System,2000, 17:319-346.
[50]Surry P D, Radcliffe N J. The COMOGA Method:Constrained Optimisation by Multiobjective Genetic Algorithms. Control and Cybernetics,1997.26:391-412.
[51]王小平,曹立明.遗传算法—理论、应用与软件实现,西安：西安交通大学出版社,2002.1
[52]徐磊.基于遗传算法的多目标优化问题的研究与应用[D].中南大学硕士学位论文,2007.5.
[53]靳志宏,计明军.物流实用优化技术[M].北京：中国物资出版社,2008.8：36-56.
[54]雷英杰,张善文,李续武等.MATLAB遗传算法工具箱及应用[M].西安：西安电子科技大学出版社,2005.4：146-207.
[55]曹岩,李明雨,李勇等.MATLAB R2008数学和控制实例教程[M].北京：化学工业出版社,2009.9：145-182.
[2]Lai K K, Shih K. A study of container berth allocation[J]. Journal of advanced transportation,1992,26(1):45-60.
[3]Imai A, Nagaiwa K, Tat C W. Efficient planning of berth allocation for container terminals in Asia[J]. Journal of advanced transportation,1997,31(1):75-94.
[4]Imai A, Nishimura E, Papadimitriou S. The dynamic berth allocation problem for a container port[J]. Transportation Research Part B,2001,35:401-417.
[5]Chen C Y, Hsieh T W. A time space network model for the berth allocation problem[J].19th IFIP TC6 Conference on System Modeling and Optimization, Cambridge, UK,1999,7.
[6]Legato P, Mazza R M. Berth planning and resources optimization at a container terminal via discrete event simulation [J]. European Journal of Operational Research,2001,133(3):537-547.
[7]韩笑乐,陆志强,奚立峰。具有服务优先级别的动态离散泊位调度优化[J],上海交通大学学报,2009.43(6)：902-905
[8]李强,杨春霞,王诺,佟士祺.集装箱码头泊位生产调度均衡优化[J].沈阳建筑大学学报(自然科学版),2008,24(6)：1132-1136.
[9]Lim A. The berth scheduling problem[J]. Operations Research Letters,1998, 22:105-110.
[10]Kim K H, Moon K C. Berth scheduling by simulated annealing[J]. Transportation Research Part B,2003,37:541-560.
[11]张煜,王少梅.基于遗传算法的泊位连续化动态调度研究[J].系统仿真学报,2007,19(10)：2161-2164.
[12]王红湘,严伟.基于启发式算法与仿真优化的岸壁线长度泊位分配策略[J].上海海事大学学报,2008,29(1)：19-22.
[13]GUAN Y P, XIAO W Q, CHEUNG R K, et al. A multi-processor task scheduling model for berth allocation:Heuristic and worst-case analysis[J]. Operations Research Letters,2002,30:343-350.
[14]KIM K H, Park Y M. A crane scheduling method for port container terminals[J]. European Journal of Operational Research,2004,156(3):752-768.
[15]周鹏飞,面向不确定环境的集装箱码头优化调度研究[D].大连理工大学博士学位论文,2005.10.
[16]蔡云,孙国正.同时求解泊位分配及岸桥调度问题的仿真优化方法.2005年全国博士生学术论坛交通运输工程学科论文集.北京：2005年全国博士生学术论坛组委会,2005：542-546.
[17]韩骏,孙晓娜,靳志宏.集装箱码头泊位与岸桥协调调度优化[J].大连海事大学学报,2008,34(2)：117-121.
[18]LIANG C, HUANG Y, YANG Y. A quay crane dynamic scheduling problem by hybrid evolutionary algorithm for berth allocation planning[J]. Computers & Industrial Engineering,2009,56:1021-1028.
[19]LEE Y, CHEN C Y. An optimization heuristic for the berth scheduling problem[J]. European Journal of Operation Research,2009,196:500-508.
[20]Steuer R E, Multiple Criteria Optimization; Theroy, Computation, and Application. New York; Wiley,1986.
[21]崔逊学.多目标进化算法及其应用[M].北京：国防工业出版社,2006：40-76.
[22]阮宏博,基于遗传算法的工程多目标优化研究[D],大连理工大学硕士学位论文,2007.6.
[23]刘光,基于多目标粒子群算法的港口调度系统设计与实现[D],哈尔滨工程大学硕士学位论文,2008.2.
[24]R.S.Rosenberg. Simulation of genetic populations with biochemical properties[D]. PhD thesis. University of Michigan Ann Harbor, Michigan,1967.
[25]ISHIBASHI H, AGUIRRE H E, TANAKA K, et al. Multi-objective optimization with improved genetic algorithm[C]. Systems, Man, and Cybernetics,2002.
[26]KALYANMOY D, AMRIT P, SAMEER A, et al. A fast and elitist multi-objective genetic algorithm NSGA-II[J]. IEEE Transactions on Evolutionary Computation,2002,6 (2):182-197.
[27]H. W. Kuhn and A. W. Tucker. Nonlinear programming. In J. Neyman, editor, Proceedings of the Second Berkeley Symposium on Mathematical Statistics and Probability[R], Berkeley, California, University of California Press,1951,:481-492
[28]Schaffer, J. D., Some experiments in machine learning using vector evaluated genetic algorithms. Unpublished doctoral dissertation, Vanderbilt University, 1984.
[29]Fonseca C M, Fleming P J.Genetic algorithms for Multiobjective optimization: Formulation, discussion and generalization[J]. Presented at Proceeding of the 5th International Conference on Genetic Algorithms, San Mateo, California,1993.
[30]Todd D. S. Sen P. A. Multiple Criteria Genetic Algorithm for Container ship Loading[J]. Proceedings of the Seventh International Conference on Genetic Algorithms, Miehigan State University:Morgan Kaufmann Publishers,1997:674-681.
[31]齐延才.集装箱物流操作实务[M].大连：大连海事大学出版社.2007.5：73-107.
[32]蔡芸,张艳伟.集装箱码头泊位分配的仿真优化方法[J].中国工程机械学报.2006.4(2)：228-232
[33]张燕涛.基于遗传算法的泊位调度问题优化研究及仿真[D].武汉理工大学硕士学位论文,2005.3.
[34]杨春霞,王诺.基于Memetic算法的集装箱码头泊位岸桥调度问题研究[J].计算机应用研究.2007.24(6).
[35]周鹏飞,康海贵.面向随机环境的集装箱码头泊位-岸桥分配方法[J].系统工程理论与实践,2008,1：161-168.
[36]唐焕文,秦学志.实用最优化方法[M].大连：大连理工大学出版社,2004：244-249.
[37]玄光男,程润伟.遗传算法与工程优化[M].北京：清华大学出版社,2004：79-82.
[38]雷德明,严新平.多目标智能优化算法及其应用[M].北京：科学出版社.2009.3：31-33.
[39]Goldberg D E. Genetic Algorithm in Search, Optimization and Machine Learning. NJ:Addison Wesley,1989.
[40]潘正军,康立山,陈毓屏.演化计算.北京：清华大学出版社,1999：65-99.
[41]Goldberg D E, Deb K. A Comparative analysis of selection schemes used in genetic algorithms//Rawlins G. Foundations of Genetic Algorithm. San Fransisco:Morgan Kaufmann,1991:76-78.
[42]Syswerda G. Uniform crossover in gernetic algorithm//Proceeding of 3th International Conference on Genetic algorithms. San Fransisco:Morgan Kaufmann,1993:124-131.
[43]蔡焕芹,基于多目标遗传算法的预拌混凝土车辆调度[D],上海交通大学硕士学位论文,2007.2.
[44]崔逊学.多目标进化算法及其应用[M].北京：国防工业出版社,2006：9-11.
[45]柴志刚.集装箱码头泊位调度多目标优化方法研究[D].大连海事大学硕士学位论文,2009.6.
[46]郑金华.多目标进化算法及其应用[M].北京：科学出版社,2007：105-123.
[47]宋羚.基于多目标遗传算法和SVM的特征选择方法[D].华中科技大学硕士学位论文.2007.6.
[48]Zitzler E, Thiele L. Multibojective evolutionary algorithms:A comparative case study and strength Pareto approach. IEEE Transaction on Evolutionary Computation, 1999,3:257-271.
[49]Coello C A C. Constraint-handling using an evolutionary multibojective optimization technique. Civil Engineering and Environmental System,2000, 17:319-346.
[50]Surry P D, Radcliffe N J. The COMOGA Method:Constrained Optimisation by Multiobjective Genetic Algorithms. Control and Cybernetics,1997.26:391-412.
[51]王小平,曹立明.遗传算法—理论、应用与软件实现,西安：西安交通大学出版社,2002.1
[52]徐磊.基于遗传算法的多目标优化问题的研究与应用[D].中南大学硕士学位论文,2007.5.
[53]靳志宏,计明军.物流实用优化技术[M].北京：中国物资出版社,2008.8：36-56.
[54]雷英杰,张善文,李续武等.MATLAB遗传算法工具箱及应用[M].西安：西安电子科技大学出版社,2005.4：146-207.
[55]曹岩,李明雨,李勇等.MATLAB R2008数学和控制实例教程[M].北京：化学工业出版社,2009.9：145-182.