基于滚动窗口的集装箱码头泊位动态调度优化研究
|
摘要
在码头岸线资源有限的情况下,合理的泊位调度方案能有效缩短船舶在港时间,提高码头生产效率,进而增加码头自身竞争力。泊位调度问题是集装箱码头生产组织优化的基础问题,其任务是,在泊位数量、作业岸桥数、码头前方堆场规模等有限的资源条件下,确定各船舶的靠泊位置和靠泊时间,从而合理的安排岸桥进行装卸作业,以确保所选定的生产目标最优。由于班轮运输方式的广泛运用,集装箱码头的调度管理人员便可根据船公司到港之前提供的船期表和装卸箱量等信息,提前制定泊位调度计划,保证了船舶进港作业的有序性。目前,集装箱码头泊位调度理论研究大多采用面向静态生产环境的调度优化方法,即考虑调度计划执行过程中,内外部环境不发生变化。然而在实际生产中,泊位调度经常要面临非常复杂的不确定性环境,这就使得这种静态调度优化方法经常难以满足实际生产需要。为此,本文提出了一种基于滚动窗口的动态泊位调度优化方法：首先建立最小化船舶平均在港时间和靠泊顺序偏离度的多目标优化模型；为求解该模型,通过基于周期和事件驱动的混合再调度机制将调度过程分成连续静态调度区间,在每个区间内采用Memetic算法对窗口船舶集进行调度优化。算例中,首先求解了初始调度方案,然后针对船舶紧急靠泊、船舶延迟到港以及岸桥发生故障三种情况,分别进行再调度,并提出再调度方案。结果表明,相对静态调度方法,基于滚动窗口的动态泊位调度优化方法更能适应复杂的动态生产环境,其优化结果也更符合集装箱码头泊位调度的实践需求。
Under the limitation of container terminal coastal resources, reasonable berth scheduling scheme can effectively shorten the time of ship's staying in the terminal, improve terminal productivity and increase the terminal's competitiveness. Berth scheduling is the basic problem in the production organization optimization of container terminal and is the key indicator in determining the level of container terminal services. The task of berth scheduling is to determine the berthing position and berthing time, and then arrange the cranes reasonable to load and discharge the cargo so as to make sure that the production targets selected can be optimal under the limitation of terminal resources, such as the number of berth, quay cranes and the scale of container yard. Because of the wide use of liner transportation mode, the scheduling manager can arrange the berth scheduling plan in advance according to the information of sailing schedule and container volume supplied by shipping company before arriving at the terminal, which ensures the order of ships'operation in the port.At present, berth scheduling optimization was usually researched under a static production environment. However, there were many uncertainties in practice, thus it was often difficult to use the static approach to satisfy the actual needs. Therefore, a dynamic berth scheduling optimization approach was presented based on rolling window in this paper. With the minimization of the average transshipment time of all ships and the deviation of berthing sequence considered, a multi-objective optimization model was established. To solve the model, the scheduling process was divided into a series of continual and static scheduling intervals based on a periodic and event driven rescheduling strategy, and then the multi-objective genetic algorithm was adopted in each rolling-horizon. Moreover, numerical examples were given to evaluate the efficiency of the proposed approach through the simulation of dynamic events or emergency events from ships. The results show that compared with the static approach, the proposed approach is more suitable for the complex dynamic environment, and the final scheme can better satisfy the decision demands of berth scheduling in the container terminal.
Under the limitation of container terminal coastal resources, reasonable berth scheduling scheme can effectively shorten the time of ship's staying in the terminal, improve terminal productivity and increase the terminal's competitiveness. Berth scheduling is the basic problem in the production organization optimization of container terminal and is the key indicator in determining the level of container terminal services. The task of berth scheduling is to determine the berthing position and berthing time, and then arrange the cranes reasonable to load and discharge the cargo so as to make sure that the production targets selected can be optimal under the limitation of terminal resources, such as the number of berth, quay cranes and the scale of container yard. Because of the wide use of liner transportation mode, the scheduling manager can arrange the berth scheduling plan in advance according to the information of sailing schedule and container volume supplied by shipping company before arriving at the terminal, which ensures the order of ships'operation in the port.At present, berth scheduling optimization was usually researched under a static production environment. However, there were many uncertainties in practice, thus it was often difficult to use the static approach to satisfy the actual needs. Therefore, a dynamic berth scheduling optimization approach was presented based on rolling window in this paper. With the minimization of the average transshipment time of all ships and the deviation of berthing sequence considered, a multi-objective optimization model was established. To solve the model, the scheduling process was divided into a series of continual and static scheduling intervals based on a periodic and event driven rescheduling strategy, and then the multi-objective genetic algorithm was adopted in each rolling-horizon. Moreover, numerical examples were given to evaluate the efficiency of the proposed approach through the simulation of dynamic events or emergency events from ships. The results show that compared with the static approach, the proposed approach is more suitable for the complex dynamic environment, and the final scheme can better satisfy the decision demands of berth scheduling in the container terminal.
引文
[1]Lim, A., the Berth planning problem. Operations Research Letters,1998.22(2-3): P.105-110.
[2]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.
[3]Imai A, Nishimura E, Papadimitriou S. The dynamic Berth allocation for a container Port. Transportation Research (Part B) (2001)35:401-417.
[4]Kap Hwan Kim, Kyung Chan Moon Berth scheduling by simulated annealing, Transportation Research Part B 37(2003)541-560.
[5]Edmond E D, Maggs R P. How useful are queue models in port investment derisions For containers berths [J]. Journal of the Operational Research Society.1978,19 (8): 741-750.
[6]Chen C Y, Hsieh T W. A time space network model for the berth allocation problem.19th IFIP TC6 Conference on System Modeling and Optimization, Cam bridge, UK,1999,7.
[7]张煜,王少梅.基于遗传算法的泊位连续化动态调度研究[J].系统仿真学报,2007,19(10)：2161-2164.
[8]韩笑乐,陆志强,奚立峰.具有服务优先级别的动态离散泊位调度优化.上海交通大学学报,2009,43(6).
[9]欧阳玲萍,王锡淮,肖健梅.基于蚁群算法的泊位调度问题.控制工程,2009(16).
[10]周鹏飞,康海贵.面向随机环境的集装箱码头泊位-岸桥分配方法[J].系统工程理论与实践,2008,1：161-168.
[11]韩骏,孙晓娜,靳志宏.集装箱码头泊位与岸桥协调调度优化.大连海事大学学报,2008,34(2)：117-121.
[12]曾庆成,杨忠振.集装箱码头作业调度双层规划模型及求解算法[J].哈尔滨工程大学学报.2007,28(3)：277-281.
[13]曾庆成,杨忠振.集装箱码头卸船作业调度方案的两阶段禁忌搜索算法[J].交通运输工学报.2007,17(4)：109-122.
[14]曾庆成,杨忠振.集装箱码头集卡调度模型与Q学习算法[J].哈尔滨工程大学学报,2008,29(1)：1-4.
[15]蔡芸.港口集装箱物流系统仿真和优化方法的研究及应用[D].武汉理工大学,2005.
[16]蔡芸,孙国正.同时求解泊位分配及岸桥调度问题的仿真优化方法[A].可持续发展的中
国交通—2005全国博士生学术论坛(交通运输工程学科)论文集(C),2005.
[17]Richard Dawkins. The Selfish Gene. Oxford University Press,1976.
[18]Pablo Moscato, Michael G. Norman. A Memetic Approach for the Traveling Salesman Problem-implementation of a Computational Ecology for Combinatorial Optimization On Message-passing Systems. In Proceedings of the International Conference on Parallel Computing and Transport Applications.1992.
[19]Nicholas J. Radcliff, Patrick D. Surry. Formal Memetic Algorithms. Evolutionary Computing,1994.
[20]Peter Merz, Bernd Freisleben. Memetic Algorithms and the Fitness Landscape of The Graph Bi Partitioning Problem. PPSN VLNCS 1998, pp.765-774.
[21]Peng Zou, Zhi Zhou, Guoliang Chen, Xin Yao et al. A Novel Memetic Algorithm With Random Multi-local-search:A case study of TSP. Proceedings of the 2004 Congress on Evolutionary Computation, VOL 1 and 2,2004.
[22]Paulo M. Franca, Pablo Moscato. New Memetic Algorithm for the Asymmetric Traveling Salesman Problem. Journal of Heuristics,10:483-506,2004.
[23]Runwei Cheng, Mitsuo Gen. Parallel machine scheduling problems using Memetic Algorithms. Computers Industrial Engineering. Volume 33:761-764,1997.
[24]Paulo M. Franca, Alexandre Mendes, and Paulo Moscato. A Memetic Algorithm for the Total Tardiness Single Machine Scheduling Problem. European Journal of Operational Research,2000.
[25]W. C. Yeh. A Memetic Algorithm for the n/2/Flowshop/aF+bCmax Scheduling Problem. Int J Adv Manuf Technol. Vol20:464-473,2002.
[26]P. Merz, B. Freisleben, Fitness landscape analysis and memetic algorithms for the quadratic assignment problem. IEEE Transactions on Evolutionary Computation, Volume 4, Page(s):337-352,2000.
[27]A. Brabazon, de Sousa T. F., Silva A.. A Memetic Model of Product Invention. Evolutionary Computation,2005. The 2005 IEEE Congress on Volume 2, Page(s):1053-1060,2005.
[28]W. C. Yeh. An efficient memetic algorithm for the multi-stage supply chain network problem. Int J Adv ManufTechnol,2005.
[29]Toby O. Hara, Larry Bull. A Memetic Accuracy-based Neural Learning Classifier System. Evolutionary Computation,2005. The 2005 IEEE Congress on Volume 3, Page (s):2040-2045.
[30]H. A. Abbass, et al. A Memetic Pareto Evolutionary Approach to Artificial Neural
Networks. The Australian Joint Conference on Artificial Intelligence, Adelaide, Dec.2001.
[31]Tatiane R. Bonfim, Akebo Yamakami. Neural Network Applied to the Coevolution of the Memetic Algorithm for Solving the Makespan Minimization Problem in Parallel Machine Scheduling. Proceedings of the VII Brazilian Symposium on Neural Networks (SBRN02).2002.
[32]Kok W. Wong, Yew S. Ong, Halit Eren et al. Hybrid Fuzzy Modeling Using Memetic Algorithm for Hydro cyclone Control. Proceedings of the Third International Conference on Machine Learning and Cybernetics,2004.
[33]李青,钟铭,李振福,刘兆健.用于集装箱配装问题的Memetic算法.辽宁工程技术大学学报,2006,25(3).
[34]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.
[35]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.
[36]齐延才.集装箱物流操作实务[M].大连：大连海事大学出版社.2007.5：73-107.
[37]Nelson R T, Holloway C A, Wong R M. Centralized scheduling and priority Implementation heuristics for a dynamic job shop model with due dates and variable Processing time. AIIE Transactions,1977,19:96-102.
[38]Y S Ong, M H Lim, N Zhu, et al. Classification of adaptive Memetic algorithm: A comparative study. IEEE Trans. On Systems, Man, and Cybernetics-Part B: Cybernetics,2007,37(1):6-17.
[39]N Krasnogor, J Smith. A tutorial for competent Memetic algorithms:model, taxonomy, and design issues. IEEE Trans. On Evolutionary Computation,2000,4(4).
[40]Z G Tu, Y Lu. A robust stochastic genetic algorithm for global numerical Optimization. IEEE trans. On Evolutionary Computation,2004,8(5):456-470.
[41]Panwalker S. S., Iskander W. A survey of scheduling rules. Operation Research, 1977,25(1):45-61.
[42]张国辉,高亮,刘文君.基于Memetic算法的车间动态调度策略研究[J].中国机械工程,2008,19(15)：1827-1831.
[43]周鹏飞,康海贵.面向随机环境的集装箱码头泊位-岸桥分配方法[J].系统工程理论与实践,2008,1：161-168.
[44]张燕涛.基于遗传算法的泊位调度问题优化研究及仿真[D].武汉理工大学硕士学位论文,2005.3.
[45]徐磊.基于遗传算法的多目标优化问题的研究与应用[D].中南大学硕士学位论文,2007.5.
[46]雷德明,严新平.多目标智能优化算法及其应用[M].北京：科学出版社.2009.3：31-33.
[47]崔逊学.多目标进化算法及其应用[M].北京：国防工业出版社,2006：40-76.
[48]高亮,刘文君,周驰.用Memetic算法求解有时间约束的TSP问题[J].华中科技大学学报(自然科学学报),2008,36(7)：93-96.
[49]雄禾根,李建军,孔建益等.考虑工序相关性的动态Jobshop调度问题启发式算法[J].机械工程学报,2006,42(s)：51-55.
[50]王健,杨建军,杨达玲.基于约束满足的Jobshop车间生产再调度系统[J].现代制造工程,2006,12：16-18.
[51]郭秀萍,杨根科,吴智铭.一种混合自适应多目标Memetic算法[J].控制与决策.2006,21(11)：1234-1238.
[52]李平.港口泊位分配与装卸桥调度系统的建模与优化[D].天津：天津理工大学,2007.
[53]韩晓龙,丁以中.集装箱港口泊位配置优化[J].系统工程理论方法应用,2006,15(3)：275-278.
[54]张超勇.基于自然启发式算法的作业车间调度问题理论与应用研究.博士论文.华中科技大学,2006.
[55]陆翰.作业车间调度的建模及优化方法研究：硕士论文.上海：上海交通大学机械与动力工程学院,2007.2.
[56]王凌.智能优化算法及其应用[M].清华大学出版社,2001.
[57]信昆仑、刘遂庆,混合编码遗传算法基于面向对象方法的实现及应用,计算机工程与应用,2003(21)
[58]邢文训,谢金星.现代优化计算方法.清华大学出版社,1999.
[59]真虹.港口生产调度过程优化.上海科学技术文献出版社,1999.
[60]李郝林,施展.遗传算法在生产调度应用中的关键技术.组合机床与自动化加工技术,2003.7.
[61]王万良.生产调度智能算法及其应用[M].科学出版社,2007.07.
[62]李岩,吴智铭.遗传算法在柔性动态调度中的应用[J].上海交通大学学报,2001,35(2)：250-25.
[2]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.
[3]Imai A, Nishimura E, Papadimitriou S. The dynamic Berth allocation for a container Port. Transportation Research (Part B) (2001)35:401-417.
[4]Kap Hwan Kim, Kyung Chan Moon Berth scheduling by simulated annealing, Transportation Research Part B 37(2003)541-560.
[5]Edmond E D, Maggs R P. How useful are queue models in port investment derisions For containers berths [J]. Journal of the Operational Research Society.1978,19 (8): 741-750.
[6]Chen C Y, Hsieh T W. A time space network model for the berth allocation problem.19th IFIP TC6 Conference on System Modeling and Optimization, Cam bridge, UK,1999,7.
[7]张煜,王少梅.基于遗传算法的泊位连续化动态调度研究[J].系统仿真学报,2007,19(10)：2161-2164.
[8]韩笑乐,陆志强,奚立峰.具有服务优先级别的动态离散泊位调度优化.上海交通大学学报,2009,43(6).
[9]欧阳玲萍,王锡淮,肖健梅.基于蚁群算法的泊位调度问题.控制工程,2009(16).
[10]周鹏飞,康海贵.面向随机环境的集装箱码头泊位-岸桥分配方法[J].系统工程理论与实践,2008,1：161-168.
[11]韩骏,孙晓娜,靳志宏.集装箱码头泊位与岸桥协调调度优化.大连海事大学学报,2008,34(2)：117-121.
[12]曾庆成,杨忠振.集装箱码头作业调度双层规划模型及求解算法[J].哈尔滨工程大学学报.2007,28(3)：277-281.
[13]曾庆成,杨忠振.集装箱码头卸船作业调度方案的两阶段禁忌搜索算法[J].交通运输工学报.2007,17(4)：109-122.
[14]曾庆成,杨忠振.集装箱码头集卡调度模型与Q学习算法[J].哈尔滨工程大学学报,2008,29(1)：1-4.
[15]蔡芸.港口集装箱物流系统仿真和优化方法的研究及应用[D].武汉理工大学,2005.
[16]蔡芸,孙国正.同时求解泊位分配及岸桥调度问题的仿真优化方法[A].可持续发展的中
国交通—2005全国博士生学术论坛(交通运输工程学科)论文集(C),2005.
[17]Richard Dawkins. The Selfish Gene. Oxford University Press,1976.
[18]Pablo Moscato, Michael G. Norman. A Memetic Approach for the Traveling Salesman Problem-implementation of a Computational Ecology for Combinatorial Optimization On Message-passing Systems. In Proceedings of the International Conference on Parallel Computing and Transport Applications.1992.
[19]Nicholas J. Radcliff, Patrick D. Surry. Formal Memetic Algorithms. Evolutionary Computing,1994.
[20]Peter Merz, Bernd Freisleben. Memetic Algorithms and the Fitness Landscape of The Graph Bi Partitioning Problem. PPSN VLNCS 1998, pp.765-774.
[21]Peng Zou, Zhi Zhou, Guoliang Chen, Xin Yao et al. A Novel Memetic Algorithm With Random Multi-local-search:A case study of TSP. Proceedings of the 2004 Congress on Evolutionary Computation, VOL 1 and 2,2004.
[22]Paulo M. Franca, Pablo Moscato. New Memetic Algorithm for the Asymmetric Traveling Salesman Problem. Journal of Heuristics,10:483-506,2004.
[23]Runwei Cheng, Mitsuo Gen. Parallel machine scheduling problems using Memetic Algorithms. Computers Industrial Engineering. Volume 33:761-764,1997.
[24]Paulo M. Franca, Alexandre Mendes, and Paulo Moscato. A Memetic Algorithm for the Total Tardiness Single Machine Scheduling Problem. European Journal of Operational Research,2000.
[25]W. C. Yeh. A Memetic Algorithm for the n/2/Flowshop/aF+bCmax Scheduling Problem. Int J Adv Manuf Technol. Vol20:464-473,2002.
[26]P. Merz, B. Freisleben, Fitness landscape analysis and memetic algorithms for the quadratic assignment problem. IEEE Transactions on Evolutionary Computation, Volume 4, Page(s):337-352,2000.
[27]A. Brabazon, de Sousa T. F., Silva A.. A Memetic Model of Product Invention. Evolutionary Computation,2005. The 2005 IEEE Congress on Volume 2, Page(s):1053-1060,2005.
[28]W. C. Yeh. An efficient memetic algorithm for the multi-stage supply chain network problem. Int J Adv ManufTechnol,2005.
[29]Toby O. Hara, Larry Bull. A Memetic Accuracy-based Neural Learning Classifier System. Evolutionary Computation,2005. The 2005 IEEE Congress on Volume 3, Page (s):2040-2045.
[30]H. A. Abbass, et al. A Memetic Pareto Evolutionary Approach to Artificial Neural
Networks. The Australian Joint Conference on Artificial Intelligence, Adelaide, Dec.2001.
[31]Tatiane R. Bonfim, Akebo Yamakami. Neural Network Applied to the Coevolution of the Memetic Algorithm for Solving the Makespan Minimization Problem in Parallel Machine Scheduling. Proceedings of the VII Brazilian Symposium on Neural Networks (SBRN02).2002.
[32]Kok W. Wong, Yew S. Ong, Halit Eren et al. Hybrid Fuzzy Modeling Using Memetic Algorithm for Hydro cyclone Control. Proceedings of the Third International Conference on Machine Learning and Cybernetics,2004.
[33]李青,钟铭,李振福,刘兆健.用于集装箱配装问题的Memetic算法.辽宁工程技术大学学报,2006,25(3).
[34]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.
[35]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.
[36]齐延才.集装箱物流操作实务[M].大连：大连海事大学出版社.2007.5：73-107.
[37]Nelson R T, Holloway C A, Wong R M. Centralized scheduling and priority Implementation heuristics for a dynamic job shop model with due dates and variable Processing time. AIIE Transactions,1977,19:96-102.
[38]Y S Ong, M H Lim, N Zhu, et al. Classification of adaptive Memetic algorithm: A comparative study. IEEE Trans. On Systems, Man, and Cybernetics-Part B: Cybernetics,2007,37(1):6-17.
[39]N Krasnogor, J Smith. A tutorial for competent Memetic algorithms:model, taxonomy, and design issues. IEEE Trans. On Evolutionary Computation,2000,4(4).
[40]Z G Tu, Y Lu. A robust stochastic genetic algorithm for global numerical Optimization. IEEE trans. On Evolutionary Computation,2004,8(5):456-470.
[41]Panwalker S. S., Iskander W. A survey of scheduling rules. Operation Research, 1977,25(1):45-61.
[42]张国辉,高亮,刘文君.基于Memetic算法的车间动态调度策略研究[J].中国机械工程,2008,19(15)：1827-1831.
[43]周鹏飞,康海贵.面向随机环境的集装箱码头泊位-岸桥分配方法[J].系统工程理论与实践,2008,1：161-168.
[44]张燕涛.基于遗传算法的泊位调度问题优化研究及仿真[D].武汉理工大学硕士学位论文,2005.3.
[45]徐磊.基于遗传算法的多目标优化问题的研究与应用[D].中南大学硕士学位论文,2007.5.
[46]雷德明,严新平.多目标智能优化算法及其应用[M].北京：科学出版社.2009.3：31-33.
[47]崔逊学.多目标进化算法及其应用[M].北京：国防工业出版社,2006：40-76.
[48]高亮,刘文君,周驰.用Memetic算法求解有时间约束的TSP问题[J].华中科技大学学报(自然科学学报),2008,36(7)：93-96.
[49]雄禾根,李建军,孔建益等.考虑工序相关性的动态Jobshop调度问题启发式算法[J].机械工程学报,2006,42(s)：51-55.
[50]王健,杨建军,杨达玲.基于约束满足的Jobshop车间生产再调度系统[J].现代制造工程,2006,12：16-18.
[51]郭秀萍,杨根科,吴智铭.一种混合自适应多目标Memetic算法[J].控制与决策.2006,21(11)：1234-1238.
[52]李平.港口泊位分配与装卸桥调度系统的建模与优化[D].天津：天津理工大学,2007.
[53]韩晓龙,丁以中.集装箱港口泊位配置优化[J].系统工程理论方法应用,2006,15(3)：275-278.
[54]张超勇.基于自然启发式算法的作业车间调度问题理论与应用研究.博士论文.华中科技大学,2006.
[55]陆翰.作业车间调度的建模及优化方法研究：硕士论文.上海：上海交通大学机械与动力工程学院,2007.2.
[56]王凌.智能优化算法及其应用[M].清华大学出版社,2001.
[57]信昆仑、刘遂庆,混合编码遗传算法基于面向对象方法的实现及应用,计算机工程与应用,2003(21)
[58]邢文训,谢金星.现代优化计算方法.清华大学出版社,1999.
[59]真虹.港口生产调度过程优化.上海科学技术文献出版社,1999.
[60]李郝林,施展.遗传算法在生产调度应用中的关键技术.组合机床与自动化加工技术,2003.7.
[61]王万良.生产调度智能算法及其应用[M].科学出版社,2007.07.
[62]李岩,吴智铭.遗传算法在柔性动态调度中的应用[J].上海交通大学学报,2001,35(2)：250-25.