集装箱港口堆场资源的优化配置
|
摘要
随着世界经济一体化和全球化的发展,集装箱的吞吐量在逐年增长,随之对港口的建设、生产设备、经营管理提出了更高的要求。而堆场是码头作业中最复杂的部分,那么如果想提高港口自身的竞争力,集装箱码头堆场资源的优化配置则是提高港口整体效率影响因素中重要的一环,本文综合运用了运筹学、优化理论和计算机仿真相结合的方法对堆场空间资源与设备资源进行了优化配置,其主要内容如下:
研究建立了前、后方堆场分开堆存进、出口箱的混合整数模型。该模型以最小化集卡行走距离及平衡箱区间作业量为目标,旨在将运进堆场的集装箱直接分配到各箱区贝位中;考虑到便于集装箱码头堆场的实际运作,通过采取在前、后方堆场分别设立缓冲区的方式,以此加速船舶装卸作业及提高堆场空间利用率。最后通过优化软件lingo求解算例,所得优化结果表明该模型在实现集卡行走距离最短的前提下,同时也保证了龙门吊在箱区间作业量的总体平衡。
研究建立了决策出口集装箱在堆场中堆存位置的动态规划模型。基于提高船舶服务的满意度,使集装箱装船时不倒箱或者少倒箱,在集装箱到达堆场后文中采取了“预倒箱”的方法,使得待出口的集装箱在前方堆场可以按照装船时间第一、重量因素第二的原则有序地堆放;该模型以放箱时间内所有出口集装箱完全入堆后,龙门吊进行的预倒箱总数最小化为目标,旨在为每个新到来的出口箱决策其欲堆存的最佳箱位。鉴于该模型用动态规划方法求解的时间复杂度呈指数阶递增,设计遗传算法对其进行了求解,结果显示所设计的算法对于求解一定规模的实例不仅可以找到其最优解而且能够降低时间复杂度。
研究建立了多台龙门吊的优化调度模型。基于在集疏港作业过程中,大量集装箱任务急需在最短的时间内运入或运离堆场,该模型以最小化所有集装箱任务完成总时间及龙门吊作业量平衡为目标,旨在为每台龙门吊决策其欲处理的集装箱任务集并对作业序列进行优化;结合堆场的实际运作情况,模型中考虑了集装箱任务间可能存在的某种优先关系。该模型可归约为多旅行商问题,属于NP难问题,鉴于问题的复杂度,采用遗传算法对其进行了求解;并将实验结果与模拟退火算法做了比较,结果表明在可接受的时间内,采用遗传算法所得结果较模拟退火算法好。
With the integration of economic in the world and the development of the globalization,the throughput of container is increasing year by year,which will put forward higher requirements to the construction,equipment and management in the port.However, the storage yard is the most complex part of the container terminal in the operation procedure.It can be said that the optimization of resources in the yard play an important role in the improving the overall efficiency of the port.This paper focus on the optimization of the space and equipment resources in the storage yard by combining with operation research,optimization theory and computer simulation,which includes the main contents as follows:
The study has established a mixed integer model which is applied to the space allocation for export and import containers.The model aims to determine the storage bay for the arriving containers with the objective of minimizing the moving distance of trucks and balancing the workload of gantry cranes.Considering facilitating the practical operation of the yard,buffer zones are respectively established in the front and rear yard in order to accelerate the loading /unloading operation for vessels and improve the utilization of storage space.Finally,the model is sloved by lingo.The results show that the model not only realizes that the total moving distance of truck is the shortest but also guarantees the workload balance of gantry cranes.
The study has established a dynamic programming model to determine the optimal storage slot in a yard-bay for an export container.In order to improve the satisfaction of the shipping, we make every stack abide by the principle that the time factor is prior to the weight one. Then we can respectively find the proper slots and store it into the yard-bay by the relocation movement of cranes.The objective is to minimize the total number of the relocation movement.In view that the time complexity is exponentially increasing with dynamic programming method, we adopt the genetic algorithm to resolve it and its results show that the algorithm not only finds the optimal solution but also decreases the time complexity.
The study has established a mixed integer programming model about the scheduling of gantry cranes when large quantity of containers need to be transported to/from the yard as soon as possible.The model is to decide how to allocate the tasks to each crane and how to arrange for the cranes the servicing sequence with the objective of minimizing the total handling time and balancing the workload of cranes which considers the case of existing the precedence relations between tasks. The model can be reduced to the Multiple Traveling Salesman problem which is an NP-hard problem.Given the complexity of the problem,the genetic algorithm is utilized for solving.Then we compare its results with that of simulated annealing algorithm which show that the genetic algorithm is more suitable for solving.
研究建立了前、后方堆场分开堆存进、出口箱的混合整数模型。该模型以最小化集卡行走距离及平衡箱区间作业量为目标,旨在将运进堆场的集装箱直接分配到各箱区贝位中;考虑到便于集装箱码头堆场的实际运作,通过采取在前、后方堆场分别设立缓冲区的方式,以此加速船舶装卸作业及提高堆场空间利用率。最后通过优化软件lingo求解算例,所得优化结果表明该模型在实现集卡行走距离最短的前提下,同时也保证了龙门吊在箱区间作业量的总体平衡。
研究建立了决策出口集装箱在堆场中堆存位置的动态规划模型。基于提高船舶服务的满意度,使集装箱装船时不倒箱或者少倒箱,在集装箱到达堆场后文中采取了“预倒箱”的方法,使得待出口的集装箱在前方堆场可以按照装船时间第一、重量因素第二的原则有序地堆放;该模型以放箱时间内所有出口集装箱完全入堆后,龙门吊进行的预倒箱总数最小化为目标,旨在为每个新到来的出口箱决策其欲堆存的最佳箱位。鉴于该模型用动态规划方法求解的时间复杂度呈指数阶递增,设计遗传算法对其进行了求解,结果显示所设计的算法对于求解一定规模的实例不仅可以找到其最优解而且能够降低时间复杂度。
研究建立了多台龙门吊的优化调度模型。基于在集疏港作业过程中,大量集装箱任务急需在最短的时间内运入或运离堆场,该模型以最小化所有集装箱任务完成总时间及龙门吊作业量平衡为目标,旨在为每台龙门吊决策其欲处理的集装箱任务集并对作业序列进行优化;结合堆场的实际运作情况,模型中考虑了集装箱任务间可能存在的某种优先关系。该模型可归约为多旅行商问题,属于NP难问题,鉴于问题的复杂度,采用遗传算法对其进行了求解;并将实验结果与模拟退火算法做了比较,结果表明在可接受的时间内,采用遗传算法所得结果较模拟退火算法好。
With the integration of economic in the world and the development of the globalization,the throughput of container is increasing year by year,which will put forward higher requirements to the construction,equipment and management in the port.However, the storage yard is the most complex part of the container terminal in the operation procedure.It can be said that the optimization of resources in the yard play an important role in the improving the overall efficiency of the port.This paper focus on the optimization of the space and equipment resources in the storage yard by combining with operation research,optimization theory and computer simulation,which includes the main contents as follows:
The study has established a mixed integer model which is applied to the space allocation for export and import containers.The model aims to determine the storage bay for the arriving containers with the objective of minimizing the moving distance of trucks and balancing the workload of gantry cranes.Considering facilitating the practical operation of the yard,buffer zones are respectively established in the front and rear yard in order to accelerate the loading /unloading operation for vessels and improve the utilization of storage space.Finally,the model is sloved by lingo.The results show that the model not only realizes that the total moving distance of truck is the shortest but also guarantees the workload balance of gantry cranes.
The study has established a dynamic programming model to determine the optimal storage slot in a yard-bay for an export container.In order to improve the satisfaction of the shipping, we make every stack abide by the principle that the time factor is prior to the weight one. Then we can respectively find the proper slots and store it into the yard-bay by the relocation movement of cranes.The objective is to minimize the total number of the relocation movement.In view that the time complexity is exponentially increasing with dynamic programming method, we adopt the genetic algorithm to resolve it and its results show that the algorithm not only finds the optimal solution but also decreases the time complexity.
The study has established a mixed integer programming model about the scheduling of gantry cranes when large quantity of containers need to be transported to/from the yard as soon as possible.The model is to decide how to allocate the tasks to each crane and how to arrange for the cranes the servicing sequence with the objective of minimizing the total handling time and balancing the workload of cranes which considers the case of existing the precedence relations between tasks. The model can be reduced to the Multiple Traveling Salesman problem which is an NP-hard problem.Given the complexity of the problem,the genetic algorithm is utilized for solving.Then we compare its results with that of simulated annealing algorithm which show that the genetic algorithm is more suitable for solving.
引文
[1]陈戌源.集装箱码头业务管理[M].大连海事大学出版社,2002.
[2]Taleb-Ibrahimi Mounira,de Castilho BernardoDaganzo, Carlos F.Storage space vs handling work in container terminals[J].Transportation Research part B,1993,27,pp.13-32.
[3]Bernardo de Castillo , Carlos F. Daganzo.Handing strategies for import container at marine terminal[J].Transportation Research part B,1993,27(2),pp.151-166.
[4]Katta G. Murty , Jiyin Liu.Dss for operation in container shipping terminal , working paper.University of Michigan,Ann Arbor,2000.
[5]Peter Preston , Erhan Kozan.An approach to determine storage locations of containers at seaport terminal[J].Computers &Operations Research,2001,28(10),pp.983-995.
[6]Kap Hwan Kim , Kang Tae Park.A note on a dynamic space-allocation method for outbound containers[J].European Journal of Operation Research,2003,148(1),pp.92-101.
[7]Ebru K. Bish. A multiple-crane-Constrainted scheduling problem in a container terminal[J]. European Journal of Operation Research,2003,144 (1) ,pp.83-107.
[8]Jean-francois Cordeau,Manlio Gaudioso,Gilbert Laporte.Solving berth scheduling and yard management problems at the Gioia Tauro Martime Terminal[J].2007.
[9]Chuqian Zhang , Jiyin Liu , Yat-wah Wan.Storage space allocation in container terminal[J].Transportation Research Part B,2003 (37),pp.883–903.
[10]Kap Hwan Kim,Young Man Park,Kwang-Ryul Ryu.Deriving decision rules to locate export containers in container yards[J].European Journal of Operational Research ,2000(124),pp.89-101.
[11]陈智.中小码头堆场翻箱问题优化模型及优化设计[D].武汉理工大学,2010.
[12]徐亚,陈秋双.基于多目标规划的堆场空间分配问题研究[J].系统工程学报,2009,24 (3),pp.365-369.
[13]陶经辉,汪敏.基于混堆模式的集装箱堆场区段分配[J].系统工程理论与实践,2009,29 (8),pp.185-192.
[14]卫家骏.出口集装箱堆场位置的优化[J].重庆交通大学学报,2010,29(3),pp.470-473.
[15]王斌.集装箱堆场基于混堆的滚动式计划堆存方法[J].系统工程学报,2005,20(5),pp.466-471.
[16]王斌.集装箱码头堆场的一种动态随机堆存方法[J].系统工程理论与实践,2007,4,pp.147-153.
[17]郝聚民,纪卓尚,林焰.混合顺序作业堆场BAY优化模型[J].大连理工大学学报,2000,40 (1),pp.102-105.
[18]沈剑峰,金淳,高鹏,基于知识的集装箱堆场箱位分配计划研究[J],计算机应用研究,2007,24(9),pp.146-151.
[19]Lai K K,Kokim Lam.A study of container yard equipment allocation strategy in Hong Kong[J].International Journal of Modeling and Simulation,1994,14(3),pp.134-138.
[20]KAP HWAN KIM,KI YOUNG KIM.An optimal routing algorithm for a transfer crane in port container terminals[J].Transportation Science,1999,33(1),pp.17–33.
[21]Zhang C,Wan Y,Liu J.Dynamic crane deployment in container storage yards[J].Transportation Research B,2002,36,pp.537–555.
[22]W.C.Ng.Crane scheduling in container yards with inter-crane interference.European Journal of Operational Research,2005,164,pp.64–78.
[23]Richard J. Linn,ChuQian Zhang.A heruistic for dynamic yard crane deployment in a container terminal[J].IIE Transaction,2000,2,12.
[24]Wenkai Li,Yong Wu,M.E.H. Petering. Discrete time model and algorithms for container yard crane scheduling[J].European Journal of Operational Research,2009,198,pp.165-172.
[25]李建忠.码头堆场龙门吊起重机动态配置优化模型[J].交通运输工程学报,2005,1(5),pp.70-74.
[26]韩晓龙.集装箱港口装卸中的龙门吊数量配置[J].系统工程,2005,pp.13-16.
[27]韩晓龙.集装箱港口龙门吊的最优路径问题[J].上海海事大学学报,2005,26(2),pp.39-41.
[28]杨国兴.一种多出发点多旅行商问题到旅行商问题的转换[J].系统工程理论方法应用,1993,2(3),pp.66-68.
[29]李建忠.集装箱港口堆场资源配置问题研究[D].上海海事大学,2005.
[30]谈超凤.集装箱码头堆场资源管理优化研究.大连海事大学,2010.
[31]Zhang C.Resource Planning in container storage yard[J].Hongkong University of Science and Technology,2000,pp.35-36.
[32]刑文训,谢金星.现代优化计算方法[M].清华大学出版社,2005.
[33]Stephen J.Chapman.Matlab编程.科学出版社,2003.
[34]王小平,曹立明.遗传算法-理论、应用与软件实现[M].西安交通大学出版社,2002.
[35]Edwin S.H.Hou, Nirwan Ansari.A genetic algorithm for multiprocessor scheduling[J].IEEE Transactions on parallel and distributed systems, 1994, 5(2),pp.113-120.
[36]Dirk.Steenken, Stefan.Vob.Container terminal operation and operations research-a classification and literature review. OR Spectrum, 2004, 26,pp.3-49.
[37]W.C.Ng, K.L.Mak.Yard crane scheduling in port container terminal[J]. Applied Mathematical Modelling, 2005, 29,pp.263-276.
[38]Peterkofsky, Daganzo. A branch and bound solution method for the crane scheduling problem. Transportation Research Part B, 1990, 24(3),pp.159– 172.
[39] Lai, Leung. Analysis of yard crane deployment strategies in a container terminal. Proceedings of the International Conference on Computers and Industrial Engineering, 1996, pp.1187– 1190.
[40] Daganzo. The crane scheduling problem. Transportation Research Part B, 1989, 23(3):159-175.
[41] Li.Cai.Lee. Scheduling with multi-job-on-one-processor pattern[J]. IIE Transactions, 1998, 30,pp.433– 445.
[42] Kozan.E, Preston.P.Genetic algorithm to schedule container transfers at multimodal terminals[J]. International Transactions in Operational Research, 1999,pp.311–329.
[43]张涛,苗明,金淳.基于仿真优化的集装箱堆场资源配置研究[J].系统仿真学报,2007,19(24),pp.5631-5634.
[2]Taleb-Ibrahimi Mounira,de Castilho BernardoDaganzo, Carlos F.Storage space vs handling work in container terminals[J].Transportation Research part B,1993,27,pp.13-32.
[3]Bernardo de Castillo , Carlos F. Daganzo.Handing strategies for import container at marine terminal[J].Transportation Research part B,1993,27(2),pp.151-166.
[4]Katta G. Murty , Jiyin Liu.Dss for operation in container shipping terminal , working paper.University of Michigan,Ann Arbor,2000.
[5]Peter Preston , Erhan Kozan.An approach to determine storage locations of containers at seaport terminal[J].Computers &Operations Research,2001,28(10),pp.983-995.
[6]Kap Hwan Kim , Kang Tae Park.A note on a dynamic space-allocation method for outbound containers[J].European Journal of Operation Research,2003,148(1),pp.92-101.
[7]Ebru K. Bish. A multiple-crane-Constrainted scheduling problem in a container terminal[J]. European Journal of Operation Research,2003,144 (1) ,pp.83-107.
[8]Jean-francois Cordeau,Manlio Gaudioso,Gilbert Laporte.Solving berth scheduling and yard management problems at the Gioia Tauro Martime Terminal[J].2007.
[9]Chuqian Zhang , Jiyin Liu , Yat-wah Wan.Storage space allocation in container terminal[J].Transportation Research Part B,2003 (37),pp.883–903.
[10]Kap Hwan Kim,Young Man Park,Kwang-Ryul Ryu.Deriving decision rules to locate export containers in container yards[J].European Journal of Operational Research ,2000(124),pp.89-101.
[11]陈智.中小码头堆场翻箱问题优化模型及优化设计[D].武汉理工大学,2010.
[12]徐亚,陈秋双.基于多目标规划的堆场空间分配问题研究[J].系统工程学报,2009,24 (3),pp.365-369.
[13]陶经辉,汪敏.基于混堆模式的集装箱堆场区段分配[J].系统工程理论与实践,2009,29 (8),pp.185-192.
[14]卫家骏.出口集装箱堆场位置的优化[J].重庆交通大学学报,2010,29(3),pp.470-473.
[15]王斌.集装箱堆场基于混堆的滚动式计划堆存方法[J].系统工程学报,2005,20(5),pp.466-471.
[16]王斌.集装箱码头堆场的一种动态随机堆存方法[J].系统工程理论与实践,2007,4,pp.147-153.
[17]郝聚民,纪卓尚,林焰.混合顺序作业堆场BAY优化模型[J].大连理工大学学报,2000,40 (1),pp.102-105.
[18]沈剑峰,金淳,高鹏,基于知识的集装箱堆场箱位分配计划研究[J],计算机应用研究,2007,24(9),pp.146-151.
[19]Lai K K,Kokim Lam.A study of container yard equipment allocation strategy in Hong Kong[J].International Journal of Modeling and Simulation,1994,14(3),pp.134-138.
[20]KAP HWAN KIM,KI YOUNG KIM.An optimal routing algorithm for a transfer crane in port container terminals[J].Transportation Science,1999,33(1),pp.17–33.
[21]Zhang C,Wan Y,Liu J.Dynamic crane deployment in container storage yards[J].Transportation Research B,2002,36,pp.537–555.
[22]W.C.Ng.Crane scheduling in container yards with inter-crane interference.European Journal of Operational Research,2005,164,pp.64–78.
[23]Richard J. Linn,ChuQian Zhang.A heruistic for dynamic yard crane deployment in a container terminal[J].IIE Transaction,2000,2,12.
[24]Wenkai Li,Yong Wu,M.E.H. Petering. Discrete time model and algorithms for container yard crane scheduling[J].European Journal of Operational Research,2009,198,pp.165-172.
[25]李建忠.码头堆场龙门吊起重机动态配置优化模型[J].交通运输工程学报,2005,1(5),pp.70-74.
[26]韩晓龙.集装箱港口装卸中的龙门吊数量配置[J].系统工程,2005,pp.13-16.
[27]韩晓龙.集装箱港口龙门吊的最优路径问题[J].上海海事大学学报,2005,26(2),pp.39-41.
[28]杨国兴.一种多出发点多旅行商问题到旅行商问题的转换[J].系统工程理论方法应用,1993,2(3),pp.66-68.
[29]李建忠.集装箱港口堆场资源配置问题研究[D].上海海事大学,2005.
[30]谈超凤.集装箱码头堆场资源管理优化研究.大连海事大学,2010.
[31]Zhang C.Resource Planning in container storage yard[J].Hongkong University of Science and Technology,2000,pp.35-36.
[32]刑文训,谢金星.现代优化计算方法[M].清华大学出版社,2005.
[33]Stephen J.Chapman.Matlab编程.科学出版社,2003.
[34]王小平,曹立明.遗传算法-理论、应用与软件实现[M].西安交通大学出版社,2002.
[35]Edwin S.H.Hou, Nirwan Ansari.A genetic algorithm for multiprocessor scheduling[J].IEEE Transactions on parallel and distributed systems, 1994, 5(2),pp.113-120.
[36]Dirk.Steenken, Stefan.Vob.Container terminal operation and operations research-a classification and literature review. OR Spectrum, 2004, 26,pp.3-49.
[37]W.C.Ng, K.L.Mak.Yard crane scheduling in port container terminal[J]. Applied Mathematical Modelling, 2005, 29,pp.263-276.
[38]Peterkofsky, Daganzo. A branch and bound solution method for the crane scheduling problem. Transportation Research Part B, 1990, 24(3),pp.159– 172.
[39] Lai, Leung. Analysis of yard crane deployment strategies in a container terminal. Proceedings of the International Conference on Computers and Industrial Engineering, 1996, pp.1187– 1190.
[40] Daganzo. The crane scheduling problem. Transportation Research Part B, 1989, 23(3):159-175.
[41] Li.Cai.Lee. Scheduling with multi-job-on-one-processor pattern[J]. IIE Transactions, 1998, 30,pp.433– 445.
[42] Kozan.E, Preston.P.Genetic algorithm to schedule container transfers at multimodal terminals[J]. International Transactions in Operational Research, 1999,pp.311–329.
[43]张涛,苗明,金淳.基于仿真优化的集装箱堆场资源配置研究[J].系统仿真学报,2007,19(24),pp.5631-5634.