面向随机环境的集装箱码头泊位分配研究
|
摘要
集装箱码头是国际物流体系中的一个重要节点,其作业效率对世界经济的效率有着直接的影响。过去的30多年是集装箱运输发展最为兴盛的时期,全球经济的高速发展拉动集装箱运输的发展,而集装箱运输的快速发展则带动着集装箱码头的发展,集装箱码头吞吐量不断增长。随着集装箱码头作业需求的增加,对码头岸线管理提出了更高要求。集装箱码头根据船舶公司提供的船舶到港信息以及集装箱量等,提前制定泊位分配计划。但码头作业过程中常常出现恶劣天气、机械故障等干扰事件,导致码头泊位计划失效或不可行。不确定环境下的泊位分配问题已成为码头运作优化管理的关键问题之一。
当较小的不确定性干扰事件发生时,可通过随机环境下的泊位分配计划自身的鲁棒性来消除干扰事件带来的负面影响。本文首先针对集装箱码头船舶到港时间和处理时间的不确定性,建立了随机环境下的泊位分配模型；考虑泊位分配问题的求解复杂性,并结合模型特点设计了基于CPLEX计算环境的滚动调动算法。模拟实验表明提出的算法较参考的启发式算法能在CPU允许的时间内得到更优结果。同时仿真实验分析了不同的船舶到港密集程度下模型保证率对目标函数的影响,存在最佳保证率使得船舶总在港停留时间最短。
当较大的不确定性干扰事件发生时,原泊位分配计划会变得不可行,需要制定干扰恢复计划。针对这种情况,本文建立了泊位分配干扰恢复模型来恢复泊位分配方案。采用基于禁忌搜索的重调度算法对模型进行了求解,模拟实验表明此算法能够在可接受的计算时间内获得满意解。
The container terminal is an important node in the international logistics system, whose operating efficiency has a direct impact on the efficiency of the world economy. The rapid development of the global economy has stimulated the development of container transport and then led the development of container terminal and the growing throughput of container terminal, so the past30years was the most flourishing period of the development of container transport. With the increase in demand of container terminal operations, the requirements for the wharf management of container terminal has gone up. The staff of the container terminal can make the berth allocation plan ahead according to the information of vessels arriving at port and the container volume.
However, uncertain disruption events always happen in container terminal operations, like bad weather and mechanical failure, which may make the original plan failure of infeasible. Thurs, berth allocation problem under stocastic environment has become one of the key issues of operational optimization management in container terminal.
When the impact which brought up by uncertain disruption events is small, the negative impact of the events can be eliminated by the robustness of the berth allocation plan under stocastic environment. Firstly, for the uncertainties of vessels'arriving time and processing time, this paper established a robust berth allocation model under stocastic environment. According to analyzing the complexity of solving berth allocation problem and the characteristics of the model, a rolling algorithm based on CPLEX was designed. When compared with the heuristic algorithm which was used by Zhang Haibin(2010), the experiment results show that the rolling algorithm based on CPLEX has a more satisfactory result within allowed consuming CPU time. Through simulation, it can be verified that guarantee rate under different vessle arrival intensities having different impact on the objective function. There exisits a best guarantee rate which can make the total dwelling time on port shorter.
When the impact which brought up by uncertain disruption events is big, the original plan will become infeasible and a recovery scenario needs to work out. In the third part of this paper, a disruption recovery model was put forward. A re-scheduling method based on taboo search was used to solve the model and the simulation results show that this algorithm is able to obtain a satisfactory solution in a shorter period of time.
当较小的不确定性干扰事件发生时,可通过随机环境下的泊位分配计划自身的鲁棒性来消除干扰事件带来的负面影响。本文首先针对集装箱码头船舶到港时间和处理时间的不确定性,建立了随机环境下的泊位分配模型；考虑泊位分配问题的求解复杂性,并结合模型特点设计了基于CPLEX计算环境的滚动调动算法。模拟实验表明提出的算法较参考的启发式算法能在CPU允许的时间内得到更优结果。同时仿真实验分析了不同的船舶到港密集程度下模型保证率对目标函数的影响,存在最佳保证率使得船舶总在港停留时间最短。
当较大的不确定性干扰事件发生时,原泊位分配计划会变得不可行,需要制定干扰恢复计划。针对这种情况,本文建立了泊位分配干扰恢复模型来恢复泊位分配方案。采用基于禁忌搜索的重调度算法对模型进行了求解,模拟实验表明此算法能够在可接受的计算时间内获得满意解。
The container terminal is an important node in the international logistics system, whose operating efficiency has a direct impact on the efficiency of the world economy. The rapid development of the global economy has stimulated the development of container transport and then led the development of container terminal and the growing throughput of container terminal, so the past30years was the most flourishing period of the development of container transport. With the increase in demand of container terminal operations, the requirements for the wharf management of container terminal has gone up. The staff of the container terminal can make the berth allocation plan ahead according to the information of vessels arriving at port and the container volume.
However, uncertain disruption events always happen in container terminal operations, like bad weather and mechanical failure, which may make the original plan failure of infeasible. Thurs, berth allocation problem under stocastic environment has become one of the key issues of operational optimization management in container terminal.
When the impact which brought up by uncertain disruption events is small, the negative impact of the events can be eliminated by the robustness of the berth allocation plan under stocastic environment. Firstly, for the uncertainties of vessels'arriving time and processing time, this paper established a robust berth allocation model under stocastic environment. According to analyzing the complexity of solving berth allocation problem and the characteristics of the model, a rolling algorithm based on CPLEX was designed. When compared with the heuristic algorithm which was used by Zhang Haibin(2010), the experiment results show that the rolling algorithm based on CPLEX has a more satisfactory result within allowed consuming CPU time. Through simulation, it can be verified that guarantee rate under different vessle arrival intensities having different impact on the objective function. There exisits a best guarantee rate which can make the total dwelling time on port shorter.
When the impact which brought up by uncertain disruption events is big, the original plan will become infeasible and a recovery scenario needs to work out. In the third part of this paper, a disruption recovery model was put forward. A re-scheduling method based on taboo search was used to solve the model and the simulation results show that this algorithm is able to obtain a satisfactory solution in a shorter period of time.
引文
[1]韩晓龙,丁以中.集装箱码头泊位配置优化[J].系统工程理论方法应用,2006,15(3)：275-278.
[2]周鹏飞.面向不确定环境的集装箱码头优化调度研究[D].大连：大连理工大学,2005.
[3]杜玉泉.两种不确定情况下的鲁棒泊位分配问题研究[D].天津：南开大学,2009.
[4]A Imai, K. Nagaiwa, W. T. Chan. Efficient planning of berth allocation for container terminals in Asia [J]. Journal of Advanced Transportation,1997, 31(1):75-94.
[5]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.
[6]Shabayek A A, Yeung W W. A simulation model for the Kwai Chung container terminals in Hong Kong [J].European Journal of Operational Research,2002,140:1-11.
[7]Bielli M, Boulmakoul A, Rida M. Object oriented model for container terminal distributed simulation [J]. European Journal of Operational Research,2006, 175:1731-1751.
[8]张海霖,江志斌,许泓.集装箱港口集疏运调度系统作业模式的仿真分析[J].上海交通大学学报,2006,40(6)：1024-1030.
[9]韩小龙,丁以中.集装箱港口装卸作业仿真系统[J].系统仿真学报,2006,19(8)：2366-2369.
[10]蔡芸,张艳伟.集装箱码头泊位分配的仿真优化方法[J].中国工程机械学报,2006,4(2)：228—232.
[11]Lai K K, Shih K. A study of container berth allocation [J]. Journal of Advanced Transportation, 1992,26(1):45-60.
[12]Brown G G, Lawphongpanich S, Thurman K P. Optimizing ship berthing [J]. Naval Research Logistics,1994,41:1-15.
[13]Brown G G, Cormican K J, Lawphongpanich S, et al. Optimizing submarine berthing with a persistence incentive [J]. Naval Research Logistics,1997,44:301-318.
[14]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.
[15]Imai A, Nishimura E, Papadimitriou S. The dynamic berth allocation problem for a container port [J]. Transportation Research Part B,2001,35:401-417.
[16]Nishimura E, Imai A, Papadimitriou S. Berth allocation planning in the public berth system by genetic algorithms [J]. European Journal of Operational Research,2001, 131:282-292.
[17]Imai A, Nishimura E, Masahiro H. Berth allocation at indented berths for mega-containerships [J]. European Journal of Operational Research,2007, 179 (2):579-593.
[18]Wang F, Lim A. A stochastic beam search for the berth allocation problem[J]. Decision Support Systems,2007,42(4):2186-2196.
[19]秦进,缪立新,陈长彬,陶经辉.时间窗限制下港口泊位优化分配问题模型[J].船海工程,2010,39(2)：142-145.
[20]Lim A, The berth scheduling problem [J]. Operations Research Letters,1998,22:105-110.
[21]Imai A, Sun X, Papadimitriou S. Berth allocation in a container port:Using a continuous location space approach [J]. Transportation Research Part B,2005,39:199-221.
[22]Li C L, Cai X, Lee C Y, Scheduling with multiple-job-on-one-processor pattern [J]. HE Transaction,1998,30:433-445.
[23]Kim K H, Moon K C. Berth scheduling by simulated annealing [J]. Transportation Research Part B,2003,37:541-560.
[24]周鹏飞,康海贵.面向随机环境的集装箱码头泊位-岸桥分配方法[J].系统工程理论与实践,2008,(1)：161-169.
[25]Mootthy R., Teo C. P.. Berth management in container terminal:the template design problem. OR Spectrum,2006,28(4):495-518.
[26]王红湘,严伟.基于启发式算法和仿真优化的岸壁线长度泊位分配策略[J].上海海事大学学报,2008,29(1)：19-22.
[27]G. Yu, M. Arguello, G. Song, S. M. McCowan, A. White. A new era for crew recovery at Continental Airlines [J]. Interfaces,2003,33(1):5-22.
[28]G. Wei, G Yu, M. song. Optimization model and algorithm for crew management during airline irregular operation [J]. Journal of Combinatorial Optimization,1997, 1(3):305-321.
[29]王明春,高成修,曾永廷VRPTW的扰动恢复及其TABU SEARCH算法[J].数学杂志,2006,26(2)：231-236.
[30]B. M. Lewis, A. L. Erera, C. C. White. The impact of temporary seaport closures on freight supply chain costs [J]. Report in Georgia Institute of Technology,2005.
[31]于辉,陈剑,于刚.协调供应链如何应对突发事件[J].系统工程理论与实践,2005,(7)：9-16.
[32]C. Y. Lee, J. Y. T. Leung, G. Yu. Two machine scheduling under disruptions with transportation considerations [J]. Journal of Scheduling,2006,9(1):35-48.
[33]X. T. Qi, J. F. Bard, G. Yu. Disruption management for machine scheduling:the case of APT schedules [J]. International Journal of Production Economics,2006,103 (1):166-184.
[34]P, Kouvelis, R. L. Daniels, G. Vairaktarakis. Robust scheduling of a two-machine flow shop with uncertain processing times [J]. HE Transaction on Scheduling and Logistics,2000,32(5):421-432.
[35]T. Stutzle. Iterated local search for the quadratic assignment problem[N]. Technical report, Technische Hochschule Darmstadt,1999.
[36]N. Mladenovic, P. Hansen. Variable neighborhood search [J]. Computers & Operations Research 1997,24(11):1097-1100.
[37]曾庆成,张倩.集装箱码头泊位分配干扰管理仿真优化模型与算法[J].中国科技论文在线,2009,4(10)：742-746.
[38]杨春霞,王诺.集装箱码头泊位分配干扰管理决策方法研究[J].运筹与管理,2011,20(4)：90-95.
[39]林治国.基于滚动窗口的集装箱码头泊位动态调度优化研究[D].大连：大连海事大学,2010.
[40]张海滨,张纪会,宣金钊.集装箱码头泊位调度问题的启发式算法研究[J].青岛大学学报(工程技术版).2010,25(4)：57-60.
[41]刑文训,谢金星.现代优化计算方法[M].北京：清华大学出版社,1999.
[42]张颖,刘艳秋.软计算方法[M].北京：科学出版社,2002.
[43]Kim K H, Moon K C. Berth scheduling by simulated annealing [J]. Transportation Research Part B,2003,37(6):541-560.
[44]G. Yu, X. T. Qi. Disruption management:Framework, Models and Application. Singapore: World Scientific Publishing Co. Pte. Ltd, 2004
[2]周鹏飞.面向不确定环境的集装箱码头优化调度研究[D].大连：大连理工大学,2005.
[3]杜玉泉.两种不确定情况下的鲁棒泊位分配问题研究[D].天津：南开大学,2009.
[4]A Imai, K. Nagaiwa, W. T. Chan. Efficient planning of berth allocation for container terminals in Asia [J]. Journal of Advanced Transportation,1997, 31(1):75-94.
[5]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.
[6]Shabayek A A, Yeung W W. A simulation model for the Kwai Chung container terminals in Hong Kong [J].European Journal of Operational Research,2002,140:1-11.
[7]Bielli M, Boulmakoul A, Rida M. Object oriented model for container terminal distributed simulation [J]. European Journal of Operational Research,2006, 175:1731-1751.
[8]张海霖,江志斌,许泓.集装箱港口集疏运调度系统作业模式的仿真分析[J].上海交通大学学报,2006,40(6)：1024-1030.
[9]韩小龙,丁以中.集装箱港口装卸作业仿真系统[J].系统仿真学报,2006,19(8)：2366-2369.
[10]蔡芸,张艳伟.集装箱码头泊位分配的仿真优化方法[J].中国工程机械学报,2006,4(2)：228—232.
[11]Lai K K, Shih K. A study of container berth allocation [J]. Journal of Advanced Transportation, 1992,26(1):45-60.
[12]Brown G G, Lawphongpanich S, Thurman K P. Optimizing ship berthing [J]. Naval Research Logistics,1994,41:1-15.
[13]Brown G G, Cormican K J, Lawphongpanich S, et al. Optimizing submarine berthing with a persistence incentive [J]. Naval Research Logistics,1997,44:301-318.
[14]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.
[15]Imai A, Nishimura E, Papadimitriou S. The dynamic berth allocation problem for a container port [J]. Transportation Research Part B,2001,35:401-417.
[16]Nishimura E, Imai A, Papadimitriou S. Berth allocation planning in the public berth system by genetic algorithms [J]. European Journal of Operational Research,2001, 131:282-292.
[17]Imai A, Nishimura E, Masahiro H. Berth allocation at indented berths for mega-containerships [J]. European Journal of Operational Research,2007, 179 (2):579-593.
[18]Wang F, Lim A. A stochastic beam search for the berth allocation problem[J]. Decision Support Systems,2007,42(4):2186-2196.
[19]秦进,缪立新,陈长彬,陶经辉.时间窗限制下港口泊位优化分配问题模型[J].船海工程,2010,39(2)：142-145.
[20]Lim A, The berth scheduling problem [J]. Operations Research Letters,1998,22:105-110.
[21]Imai A, Sun X, Papadimitriou S. Berth allocation in a container port:Using a continuous location space approach [J]. Transportation Research Part B,2005,39:199-221.
[22]Li C L, Cai X, Lee C Y, Scheduling with multiple-job-on-one-processor pattern [J]. HE Transaction,1998,30:433-445.
[23]Kim K H, Moon K C. Berth scheduling by simulated annealing [J]. Transportation Research Part B,2003,37:541-560.
[24]周鹏飞,康海贵.面向随机环境的集装箱码头泊位-岸桥分配方法[J].系统工程理论与实践,2008,(1)：161-169.
[25]Mootthy R., Teo C. P.. Berth management in container terminal:the template design problem. OR Spectrum,2006,28(4):495-518.
[26]王红湘,严伟.基于启发式算法和仿真优化的岸壁线长度泊位分配策略[J].上海海事大学学报,2008,29(1)：19-22.
[27]G. Yu, M. Arguello, G. Song, S. M. McCowan, A. White. A new era for crew recovery at Continental Airlines [J]. Interfaces,2003,33(1):5-22.
[28]G. Wei, G Yu, M. song. Optimization model and algorithm for crew management during airline irregular operation [J]. Journal of Combinatorial Optimization,1997, 1(3):305-321.
[29]王明春,高成修,曾永廷VRPTW的扰动恢复及其TABU SEARCH算法[J].数学杂志,2006,26(2)：231-236.
[30]B. M. Lewis, A. L. Erera, C. C. White. The impact of temporary seaport closures on freight supply chain costs [J]. Report in Georgia Institute of Technology,2005.
[31]于辉,陈剑,于刚.协调供应链如何应对突发事件[J].系统工程理论与实践,2005,(7)：9-16.
[32]C. Y. Lee, J. Y. T. Leung, G. Yu. Two machine scheduling under disruptions with transportation considerations [J]. Journal of Scheduling,2006,9(1):35-48.
[33]X. T. Qi, J. F. Bard, G. Yu. Disruption management for machine scheduling:the case of APT schedules [J]. International Journal of Production Economics,2006,103 (1):166-184.
[34]P, Kouvelis, R. L. Daniels, G. Vairaktarakis. Robust scheduling of a two-machine flow shop with uncertain processing times [J]. HE Transaction on Scheduling and Logistics,2000,32(5):421-432.
[35]T. Stutzle. Iterated local search for the quadratic assignment problem[N]. Technical report, Technische Hochschule Darmstadt,1999.
[36]N. Mladenovic, P. Hansen. Variable neighborhood search [J]. Computers & Operations Research 1997,24(11):1097-1100.
[37]曾庆成,张倩.集装箱码头泊位分配干扰管理仿真优化模型与算法[J].中国科技论文在线,2009,4(10)：742-746.
[38]杨春霞,王诺.集装箱码头泊位分配干扰管理决策方法研究[J].运筹与管理,2011,20(4)：90-95.
[39]林治国.基于滚动窗口的集装箱码头泊位动态调度优化研究[D].大连：大连海事大学,2010.
[40]张海滨,张纪会,宣金钊.集装箱码头泊位调度问题的启发式算法研究[J].青岛大学学报(工程技术版).2010,25(4)：57-60.
[41]刑文训,谢金星.现代优化计算方法[M].北京：清华大学出版社,1999.
[42]张颖,刘艳秋.软计算方法[M].北京：科学出版社,2002.
[43]Kim K H, Moon K C. Berth scheduling by simulated annealing [J]. Transportation Research Part B,2003,37(6):541-560.
[44]G. Yu, X. T. Qi. Disruption management:Framework, Models and Application. Singapore: World Scientific Publishing Co. Pte. Ltd, 2004