基于移动轨迹的集装箱码头中控调度研究
|
摘要
中控调度优化问题是港口物流作业中的重要研究课题。通过提高集装箱码头作业效率和降低作业成本来提高自身竞争力,已成为每个集装箱港口最为关心的问题之一。而中控调度作为每个港口业务的核心环节,其调度方式和执行效率对港口的日常经营有着直接的影响。
中控调度负责管理集装箱码头内部的所有集装箱业务的组织、资源分配和现场指挥工作。传统的针对机械设备、堆场翻箱和装卸作业线三种局部调度的研究,较少地考虑不同港口的差异性问题,也缺乏对业务全局的统筹规划。基于移动轨迹的中控调度立足于集装箱港口的所有业务全局进行研究,屏蔽了内陆港和海港的差异性,以实现最小翻箱量、最少业务执行代价为目标,进而提高港口的作业效率。从集装箱码头实际使用的信息系统和港口实际作业两个方面互动进行分析优化,最终实现两者共赢。
论文首先对集装箱码头中控调度的研究现状做了综述,分析当前对于中控调度研究的侧重点以及存在的问题。其次,介绍了集装箱港口的作业类型以及中控调度方式,提出了移动轨迹理论模型,并以大重庆范围内的五大港口的业务为原型,建立了符合集装箱码头堆场约束的移动轨迹数学模型。然后,针对集装箱港口的中控调度问题是一个NP-hard问题的情况,在第三章引入了适用于求解复杂系统优化问题的遗传算法,介绍了遗传算法的相关理论,并将移动轨迹理论与遗传算法的非线性优化方法相结合,给出了基于移动轨迹中控调度的编码方式、约束处理、适应度函数、相关运行参数以及改进的遗传迭代操作。其中在编码方式中,提出了一种变长染色体多参数交叉编码,使得移动轨迹模型染色体的解的空间与遗传算法的搜索空间一一对应起来,另外在遗传算法种群初始化后所进行的约束选择处理也大大提高了算法的收敛性能。最后,运用有向邻接矩阵相关知识表达了移动轨迹遗传迭代的过程,并结合实际集装箱港务物流系统,从移动轨迹执行代价、机械执行代价以及系统资源对比上证明了方法的优越性和实用性。
Scheduling problem is an important research topic in the control of harbor logistics operations. By increasing efficiency and reducing operating costs to improve their own competitiveness in the container terminal, has become one of the most concerns. As the core of each link in the harbor operations, mode and efficiency of control scheduling directly impact on the port's daily business activities.
The control scheduling is responsible for managing organization, resources allocation and to direct work of all containers within the container terminal business. Differences between the different ports are not considered and global businesses are not arranged in traditional researches on machinery and equipment, loading and unloading yard box and turned the three lines of local scheduling. The control scheduling in the container terminal about movement traces which are based on all the operations of the global container port, shields the inland port and harbor of the differences, to achieve the minimum container volume, at least for a consideration of the business objectives of the implementation of port operations to improve efficiency. Container terminals and port operational information system is bi-directional optimization, and ultimately both win.
Firstly, the focus and the problems of current research in the control scheduling are analyzed through summarizing research in the container terminal. Second, the type and mode of operation scheduled in the container terminal are introduced, the theory of movement traces has been proposed. The container port is NP-hard problem of a situation in the control of scheduling problem. The genetic algorithm, a system for solving complex optimization problems, is recommended in the third chapter. The theory of genetic algorithms is introduced, and theory and genetic algorithm trajectory combination of nonlinear optimization method which is based on the mobile trajectory is given the encoding control scheduling, constraint handling, fitness function, the relevant operating parameters and to improve the genetic iterative operation. In the encoding, a variable-length multi-parameter cross-coding of chromosome has been proposed, making the solution trajectory model chromosome space and genetic algorithm search space correspond. Constraint handling and selection for population initialization of genetic algorithm also greatly enhanced the selection convergence performance. Finally, the genetic expression of the iterative process trajectory is expressed by the adjacency matrix of the genetic, combined with the actual container port logistics system, to prove the superiority and practicality of the method in the trajectory of the executive price, cost and the mechanical implementation of system resources.
中控调度负责管理集装箱码头内部的所有集装箱业务的组织、资源分配和现场指挥工作。传统的针对机械设备、堆场翻箱和装卸作业线三种局部调度的研究,较少地考虑不同港口的差异性问题,也缺乏对业务全局的统筹规划。基于移动轨迹的中控调度立足于集装箱港口的所有业务全局进行研究,屏蔽了内陆港和海港的差异性,以实现最小翻箱量、最少业务执行代价为目标,进而提高港口的作业效率。从集装箱码头实际使用的信息系统和港口实际作业两个方面互动进行分析优化,最终实现两者共赢。
论文首先对集装箱码头中控调度的研究现状做了综述,分析当前对于中控调度研究的侧重点以及存在的问题。其次,介绍了集装箱港口的作业类型以及中控调度方式,提出了移动轨迹理论模型,并以大重庆范围内的五大港口的业务为原型,建立了符合集装箱码头堆场约束的移动轨迹数学模型。然后,针对集装箱港口的中控调度问题是一个NP-hard问题的情况,在第三章引入了适用于求解复杂系统优化问题的遗传算法,介绍了遗传算法的相关理论,并将移动轨迹理论与遗传算法的非线性优化方法相结合,给出了基于移动轨迹中控调度的编码方式、约束处理、适应度函数、相关运行参数以及改进的遗传迭代操作。其中在编码方式中,提出了一种变长染色体多参数交叉编码,使得移动轨迹模型染色体的解的空间与遗传算法的搜索空间一一对应起来,另外在遗传算法种群初始化后所进行的约束选择处理也大大提高了算法的收敛性能。最后,运用有向邻接矩阵相关知识表达了移动轨迹遗传迭代的过程,并结合实际集装箱港务物流系统,从移动轨迹执行代价、机械执行代价以及系统资源对比上证明了方法的优越性和实用性。
Scheduling problem is an important research topic in the control of harbor logistics operations. By increasing efficiency and reducing operating costs to improve their own competitiveness in the container terminal, has become one of the most concerns. As the core of each link in the harbor operations, mode and efficiency of control scheduling directly impact on the port's daily business activities.
The control scheduling is responsible for managing organization, resources allocation and to direct work of all containers within the container terminal business. Differences between the different ports are not considered and global businesses are not arranged in traditional researches on machinery and equipment, loading and unloading yard box and turned the three lines of local scheduling. The control scheduling in the container terminal about movement traces which are based on all the operations of the global container port, shields the inland port and harbor of the differences, to achieve the minimum container volume, at least for a consideration of the business objectives of the implementation of port operations to improve efficiency. Container terminals and port operational information system is bi-directional optimization, and ultimately both win.
Firstly, the focus and the problems of current research in the control scheduling are analyzed through summarizing research in the container terminal. Second, the type and mode of operation scheduled in the container terminal are introduced, the theory of movement traces has been proposed. The container port is NP-hard problem of a situation in the control of scheduling problem. The genetic algorithm, a system for solving complex optimization problems, is recommended in the third chapter. The theory of genetic algorithms is introduced, and theory and genetic algorithm trajectory combination of nonlinear optimization method which is based on the mobile trajectory is given the encoding control scheduling, constraint handling, fitness function, the relevant operating parameters and to improve the genetic iterative operation. In the encoding, a variable-length multi-parameter cross-coding of chromosome has been proposed, making the solution trajectory model chromosome space and genetic algorithm search space correspond. Constraint handling and selection for population initialization of genetic algorithm also greatly enhanced the selection convergence performance. Finally, the genetic expression of the iterative process trajectory is expressed by the adjacency matrix of the genetic, combined with the actual container port logistics system, to prove the superiority and practicality of the method in the trajectory of the executive price, cost and the mechanical implementation of system resources.
引文
[1]合众出口网.中国称雄国际集装箱[EB/OL]. http://info.jctrans.com/ocean/jxsc/gqts/200510311769.shtml,2010-01-12.
[2]汤海旺.重庆港集装箱运输发展战略分析[J].交通企业管理,2010,263(7):52-54.
[3]刘新荣.内陆港口物流竞争力培养刍议[J].生态经济,2010,233(4):79-82.
[4]邢文训,谢金星.现代优化计算方法[M].北京:清华大学出版社,2005.
[5]刘勇.非数值并行算法第二册-遗传算法[M].北京:科学出版社,2003.
[6] Kim K H, Park Y M. Deriving decision rules to locate export containers in container yards[J].European Journal of Operational Research 2000,124(2):89-101.
[7] W.C.Ng. Crane scheduling in container yards with inter-crane interference[J].European Journal of Operational Research,2005,164:64-78.
[8] Francesco Longo. Design and integration of the containers inspection activities in the container terminal operations[J].Production Economics,2010,125(3):272-283.
[9] ImaiA,NishimuraE,Papadimitriou S. Berth allocation with service priority[J].Transportation Research Part B,2003,37:437-57.
[10]王志明,符云清.基于遗传算法的集装箱后方堆场箱位分配策略[J].计算机应用研究,2010,27(8):2939-2941.
[11]徐亚,陈秋双,龙磊等.集装箱倒箱问题的启发式算法研究[J].系统仿真学报,2008,20(14):3666-3669.
[12]曾庆成,胡祥培,杨忠振.集装箱码头泊位分配—装卸桥调度管理干扰模型[J].系统工程理论与实践,2010,30(11):2026-2035.
[13]林志国.基于滚动窗口的集装箱码头泊位动态调度优化研究[D].大连:大连海事大学硕士论文,2010,8-35.
[14] Bis, IFA, Koster R, Roodbergen K J. Determination of the number of automated guided vehicles required at a semi-automated container terminal.Journal of the Operational Research Society,2001,52:409-417.
[15] Nguyen V D, Kim K H. A dispatching method for automated lifting vehicles in automated port container terminals[J].Computers & Ind Eng,2009,56(3):1002-1020.
[16]蔡寒,基于仿真的集装箱码头拖车调度研究[D].北京:清华大学硕士论文,2007:13-71.
[17]张莉.基于排队网络理论的集装箱码头设备配置优化研究[D].上海:同济大学博士论文,2007:3-110.
[18]徐健,陈启军.基于MAS的集装箱自动化码头调度算法[J].系统仿真学报,2009,21(15):4888-4891.
[19]曾庆成,杨忠振.集装箱码头集成调度模型与混合优化算法[J].系统工程学报,2010,25(2):264-269.
[20]杨鹏,柴小燕,孙俊清.集装箱码头场桥协同调度研究[J].计算机工程与应用,2011,47(1):231-233.
[21] Avriel M, penn M, Shpirer N. Stowage planning for container ship to reduce the number of shifts[J]. Annals of Operation Research,1998,76:55-71.
[22] Kim K H, Park Y M. A crane scheduling method for port container Terminals[J].European Journal of Operational Research,2004,156(3):628-752.
[23]缪立新,乌英.遗传算法在集装箱码头综合调度中的应用[J].集装箱化,2008,204(7):18-21.
[24]梁亮,陆志强.集装箱码头装卸系统集成调度的建模与优化[J].系统工程理论与实践,2010,30(3):476-483.
[25]李艳.基于敏捷性的集装箱码头[D].江苏:江苏大学硕士论文,2010:6-44.
[26]赵宁.集装箱码头作业线调度决策支持系统[D].大连:大连海事大学硕士论文,2006:10-48.
[27]谈超凤.集装箱码头堆场资源管理优化研究[D].大连:大连海事大学硕士论文,2010:10-18.
[28]曹春晖.港口集装箱流作业优化方法研究[D].成都:西南交通大学硕士论文,2000:5-39.
[29]白治江.动态负载下堆场资源规划的在线决策[J].上海海事大学学报,2010,31(3):52-56.
[30]宗蓓华,真虹.港口装卸工艺学[M].北京:人民交通出版社,2003.
[31] Seidmann A, Sund Ararajan A. The effects of task and information asymmetry on business process redesign [J].International Journal of Production Economics, 1997, 50 (2-3): 117-128.
[32]周明,孙树栋.遗传算法原理及应用[M].北京:国防工业出版社,1992.
[33]戴晓晖,李敏强,寇纪淞.遗传算法理论研究综述[J].控制与决策.2000,15(3):263-268.
[34]玄光男,程润伟等.遗传算法与工程设计[M].北京:清华大学出版社,2004.
[35]张铃,张钹.遗传算法机理的研究[J].软件学报.2000.11(7):945-952.
[36]王小平,曹立明.遗传算法-理论、应用与软件实现[M].西安:西安交通大学出版社, 2002.
[37]陈永兵.遗传算法及其在结构工程优化中的应用研究[D].西安:西北工业大学硕士论文,2001:11-59
[38]杨浩.模型与算法[M].北京:北京交通大学出版社,2002
[39] Jomikow C Z, Michalcwicz Z. An experimental comparison of binary and floating point representations in genetic algorithm. In: Proc. Of 4th Inl. Conf. on Genetic Algorithms, Morgan Kaufmann,1991:31-36.
[40]鲁子爱.港口服务系统仿真与港口规模优化研究[D].南京:河海大学博士论文,2002:18-62.
[41] Rafiei FM, Manzari SM, Bostanian S. Financial health prediction models using artificial neural networks, genetic algorithm and multivariate discriminant analysis:Iranian evidence [J].ExpertSystems with Applications,2011,38(8):10210-10217.
[42]席裕庚,柴天佑,挥为民.遗传算法综述[J].控制理论与应用,1996,13(6):697-708.
[43]刘勇等.非数值并行计算法-遗传算法.北京:科学出版社,1996.
[44]陈国良等.遗传算法及其应用.北京:人民邮电出版社,1996.
[45]姜昌华.遗传算法在物流系统优化中的应用研究[D].上海:华东师范大学博士论文,2007:12-22.
[46] Ervin Laszlo,阂家撒等.进化-广义综合理论[M].北京:社会科学文献出版社,1988.
[47] Liu Y. Research on fitness function in genetic algorithm[J]. Journal of Lanzhou Polyechnic College,2006,13(3):4-8.
[48]谭伟.基于遗传算法的多项目网络计划优化研究[D].武汉:中国地质大学硕士论文,2009:7-10.
[49]潘正君,康立山,陈毓屏著.演化计算[M].北京:清华大学出版社,1998.
[50] Back T. The Interaction of nutation rate, selection and self-adaptation within a genetic algorithm. In: Parallel Problem Solving from Nature 2, North Holland,1992:84-94.
[2]汤海旺.重庆港集装箱运输发展战略分析[J].交通企业管理,2010,263(7):52-54.
[3]刘新荣.内陆港口物流竞争力培养刍议[J].生态经济,2010,233(4):79-82.
[4]邢文训,谢金星.现代优化计算方法[M].北京:清华大学出版社,2005.
[5]刘勇.非数值并行算法第二册-遗传算法[M].北京:科学出版社,2003.
[6] Kim K H, Park Y M. Deriving decision rules to locate export containers in container yards[J].European Journal of Operational Research 2000,124(2):89-101.
[7] W.C.Ng. Crane scheduling in container yards with inter-crane interference[J].European Journal of Operational Research,2005,164:64-78.
[8] Francesco Longo. Design and integration of the containers inspection activities in the container terminal operations[J].Production Economics,2010,125(3):272-283.
[9] ImaiA,NishimuraE,Papadimitriou S. Berth allocation with service priority[J].Transportation Research Part B,2003,37:437-57.
[10]王志明,符云清.基于遗传算法的集装箱后方堆场箱位分配策略[J].计算机应用研究,2010,27(8):2939-2941.
[11]徐亚,陈秋双,龙磊等.集装箱倒箱问题的启发式算法研究[J].系统仿真学报,2008,20(14):3666-3669.
[12]曾庆成,胡祥培,杨忠振.集装箱码头泊位分配—装卸桥调度管理干扰模型[J].系统工程理论与实践,2010,30(11):2026-2035.
[13]林志国.基于滚动窗口的集装箱码头泊位动态调度优化研究[D].大连:大连海事大学硕士论文,2010,8-35.
[14] Bis, IFA, Koster R, Roodbergen K J. Determination of the number of automated guided vehicles required at a semi-automated container terminal.Journal of the Operational Research Society,2001,52:409-417.
[15] Nguyen V D, Kim K H. A dispatching method for automated lifting vehicles in automated port container terminals[J].Computers & Ind Eng,2009,56(3):1002-1020.
[16]蔡寒,基于仿真的集装箱码头拖车调度研究[D].北京:清华大学硕士论文,2007:13-71.
[17]张莉.基于排队网络理论的集装箱码头设备配置优化研究[D].上海:同济大学博士论文,2007:3-110.
[18]徐健,陈启军.基于MAS的集装箱自动化码头调度算法[J].系统仿真学报,2009,21(15):4888-4891.
[19]曾庆成,杨忠振.集装箱码头集成调度模型与混合优化算法[J].系统工程学报,2010,25(2):264-269.
[20]杨鹏,柴小燕,孙俊清.集装箱码头场桥协同调度研究[J].计算机工程与应用,2011,47(1):231-233.
[21] Avriel M, penn M, Shpirer N. Stowage planning for container ship to reduce the number of shifts[J]. Annals of Operation Research,1998,76:55-71.
[22] Kim K H, Park Y M. A crane scheduling method for port container Terminals[J].European Journal of Operational Research,2004,156(3):628-752.
[23]缪立新,乌英.遗传算法在集装箱码头综合调度中的应用[J].集装箱化,2008,204(7):18-21.
[24]梁亮,陆志强.集装箱码头装卸系统集成调度的建模与优化[J].系统工程理论与实践,2010,30(3):476-483.
[25]李艳.基于敏捷性的集装箱码头[D].江苏:江苏大学硕士论文,2010:6-44.
[26]赵宁.集装箱码头作业线调度决策支持系统[D].大连:大连海事大学硕士论文,2006:10-48.
[27]谈超凤.集装箱码头堆场资源管理优化研究[D].大连:大连海事大学硕士论文,2010:10-18.
[28]曹春晖.港口集装箱流作业优化方法研究[D].成都:西南交通大学硕士论文,2000:5-39.
[29]白治江.动态负载下堆场资源规划的在线决策[J].上海海事大学学报,2010,31(3):52-56.
[30]宗蓓华,真虹.港口装卸工艺学[M].北京:人民交通出版社,2003.
[31] Seidmann A, Sund Ararajan A. The effects of task and information asymmetry on business process redesign [J].International Journal of Production Economics, 1997, 50 (2-3): 117-128.
[32]周明,孙树栋.遗传算法原理及应用[M].北京:国防工业出版社,1992.
[33]戴晓晖,李敏强,寇纪淞.遗传算法理论研究综述[J].控制与决策.2000,15(3):263-268.
[34]玄光男,程润伟等.遗传算法与工程设计[M].北京:清华大学出版社,2004.
[35]张铃,张钹.遗传算法机理的研究[J].软件学报.2000.11(7):945-952.
[36]王小平,曹立明.遗传算法-理论、应用与软件实现[M].西安:西安交通大学出版社, 2002.
[37]陈永兵.遗传算法及其在结构工程优化中的应用研究[D].西安:西北工业大学硕士论文,2001:11-59
[38]杨浩.模型与算法[M].北京:北京交通大学出版社,2002
[39] Jomikow C Z, Michalcwicz Z. An experimental comparison of binary and floating point representations in genetic algorithm. In: Proc. Of 4th Inl. Conf. on Genetic Algorithms, Morgan Kaufmann,1991:31-36.
[40]鲁子爱.港口服务系统仿真与港口规模优化研究[D].南京:河海大学博士论文,2002:18-62.
[41] Rafiei FM, Manzari SM, Bostanian S. Financial health prediction models using artificial neural networks, genetic algorithm and multivariate discriminant analysis:Iranian evidence [J].ExpertSystems with Applications,2011,38(8):10210-10217.
[42]席裕庚,柴天佑,挥为民.遗传算法综述[J].控制理论与应用,1996,13(6):697-708.
[43]刘勇等.非数值并行计算法-遗传算法.北京:科学出版社,1996.
[44]陈国良等.遗传算法及其应用.北京:人民邮电出版社,1996.
[45]姜昌华.遗传算法在物流系统优化中的应用研究[D].上海:华东师范大学博士论文,2007:12-22.
[46] Ervin Laszlo,阂家撒等.进化-广义综合理论[M].北京:社会科学文献出版社,1988.
[47] Liu Y. Research on fitness function in genetic algorithm[J]. Journal of Lanzhou Polyechnic College,2006,13(3):4-8.
[48]谭伟.基于遗传算法的多项目网络计划优化研究[D].武汉:中国地质大学硕士论文,2009:7-10.
[49]潘正君,康立山,陈毓屏著.演化计算[M].北京:清华大学出版社,1998.
[50] Back T. The Interaction of nutation rate, selection and self-adaptation within a genetic algorithm. In: Parallel Problem Solving from Nature 2, North Holland,1992:84-94.