集装箱码头装卸系统集成调度优化研究
|
摘要
作为跨国/地区之间主要贸易运输手段之一,集装箱运输在全球运输业中扮演着越来越重要的角色。集装箱码头是集装箱运输系统中的枢纽环节,码头集装箱装卸能力极大的制约着整个系统的运输效率,提高集装箱码头的作业效率对提高整个集装箱运输系统的能力,降低物流成本至关重要。
为提高集装箱码头作业效率,本文首先对装卸混合作业模式下的岸桥作业调度问题和单装/卸作业模式下的装卸系统集成调度问题进行了研究,针对集装箱码头装卸作业的特点,提出了装卸作业的预定义顺序约束、作业次序依赖的设备调整时间、及岸桥碰撞干涉约束等,并在此基础上建立了整数规划模型。分别提出了提出了基于遗传算法的岸桥调度优化算法和基于Johnson规则的启发式算法对上述问题进行求解。通过在数值实验中与低界进行比较,证明上述两个算法效果良好。特别对于规模较大的问题,也可以进行有效的求解。
在对上述两个问题研究基础上,本文对在装卸混合作业模式下的码头装卸系统集成调度问题进行了研究。提出了问题的整数规划模型并在拓展析取图上对问题可行解进行了分析,提出了利用原序分割规则进行邻域搜索的方法。并设计了基于模板的双层禁忌搜索算法以求解该问题,利用数值实验对算法性能进行了验证,证明在采取装卸混合模式进行作业时,装卸系统的整体效率较之采取单装/卸模式进行作业有很大提高。
As one of the major method of transnational/regional transportation, container transport is playing a more and more important role in global transportation. While the container terminals are the key hubs of the container transport system, whose efficiency is mainly limited by the operations in container terminals. It is critical to improve the capability of container transport system and decrease the logistic cost by optimizing the operations on container terminals.
To increase the efficiency of container terminals, the scheduling problem of quay cranes with dual cycling operations and the integrated scheduling problem of container handling system with single discharging/loading operations are studied at the beginning. The predefined discharging/loading constraints, sequence dependent setup time, quay crane interference constraints are proposed and studied. Based on these constraints, the integer programming models are built respectively. The modified genetic algorithm for quay crane scheduling and Johnson’s law based heuristic algorithm are developed for these problems. By comparing with the lower bounds, the numerical experiments prove the algorithms effective and efficient, particular for problems with a large size.
Based on the research for above two problems, the integrated scheduling problem of container handling system with dual cycling operations is discussed. The integer programming model is proposed and the property of the feasible solutions is analyzed on extended disjunctive graph. A neighborhood based on original partition is introduced for local search process, and finally a module based double layer tabu search algorithm is developed to solve the problem. In the experiments, the results show the container handling system can benefit dramatically by applying the dual cycling operations, comparing to the one that only single discharging/loading operations are applied.
为提高集装箱码头作业效率,本文首先对装卸混合作业模式下的岸桥作业调度问题和单装/卸作业模式下的装卸系统集成调度问题进行了研究,针对集装箱码头装卸作业的特点,提出了装卸作业的预定义顺序约束、作业次序依赖的设备调整时间、及岸桥碰撞干涉约束等,并在此基础上建立了整数规划模型。分别提出了提出了基于遗传算法的岸桥调度优化算法和基于Johnson规则的启发式算法对上述问题进行求解。通过在数值实验中与低界进行比较,证明上述两个算法效果良好。特别对于规模较大的问题,也可以进行有效的求解。
在对上述两个问题研究基础上,本文对在装卸混合作业模式下的码头装卸系统集成调度问题进行了研究。提出了问题的整数规划模型并在拓展析取图上对问题可行解进行了分析,提出了利用原序分割规则进行邻域搜索的方法。并设计了基于模板的双层禁忌搜索算法以求解该问题,利用数值实验对算法性能进行了验证,证明在采取装卸混合模式进行作业时,装卸系统的整体效率较之采取单装/卸模式进行作业有很大提高。
As one of the major method of transnational/regional transportation, container transport is playing a more and more important role in global transportation. While the container terminals are the key hubs of the container transport system, whose efficiency is mainly limited by the operations in container terminals. It is critical to improve the capability of container transport system and decrease the logistic cost by optimizing the operations on container terminals.
To increase the efficiency of container terminals, the scheduling problem of quay cranes with dual cycling operations and the integrated scheduling problem of container handling system with single discharging/loading operations are studied at the beginning. The predefined discharging/loading constraints, sequence dependent setup time, quay crane interference constraints are proposed and studied. Based on these constraints, the integer programming models are built respectively. The modified genetic algorithm for quay crane scheduling and Johnson’s law based heuristic algorithm are developed for these problems. By comparing with the lower bounds, the numerical experiments prove the algorithms effective and efficient, particular for problems with a large size.
Based on the research for above two problems, the integrated scheduling problem of container handling system with dual cycling operations is discussed. The integer programming model is proposed and the property of the feasible solutions is analyzed on extended disjunctive graph. A neighborhood based on original partition is introduced for local search process, and finally a module based double layer tabu search algorithm is developed to solve the problem. In the experiments, the results show the container handling system can benefit dramatically by applying the dual cycling operations, comparing to the one that only single discharging/loading operations are applied.
引文
[1] Bielli M., Boulmakoul A., Rida M. Object oriented model for container terminal distributed simulation [J]. European Journal of Operational Research. 2006.175: 1731-1751.
[2] Ebru K. Bish, A multiple-crane-constrained scheduling problem in a container terminal [J]. European Journal of Operational Research. 2003, 144(1): 409–417.
[3] Vis,F.A.I.,de Koster,R.,2003 Transshipment of containers at a container terminal:An overview. European Journal of Operational Research 147,2003.p.p.1-16
[4] Daganzo, C.F. The crane scheduling problem. Transportation Research Part B,1989, 23: 159–175.
[5] Peterkofsky, R.I., Daganzo, C.F. A branch and bound solution method for the crane scheduling problem. Transportation Research Part B, 1990, 24: 159–172.
[6] Lim, A., Rodrigues, B., Xiao, F., Zhu, Y. Crane scheduling with spatial constraints. Naval Research Logistics, 2004, 51: 386–406.
[7] Kim, K.H., Park, Y.M. A crane scheduling method for port container terminals. European Journal of Operation Research, 2004, 156: 752–768.
[8] Lee, D.H., Wang, H.Q., Miao, L.X. Quay crane scheduling with non-interference constraints in port container terminals. Transportation Research Part E: Logistics and Transportation Review, 2008, 44(1): 124-135.
[9] Cordeau, J.F., Gaudioso, M., Laporte, G., Moccia, L. A branch-and-cut algorithm forthe quay crane scheduling problem in a container terminal. AIRO annual conference. Camerino, Italy, 2005, September 6–9.
[10] Zhang H.P. , Kim K.H. , Maximizing the number of dual-cycle operations of quay cranes in container terminals [J], Computers & Industrial Engineering ,2009, 56: 979–992.
[11]缪立新.集装箱装船顺序优化模型及算法研究[C].第三节中国物流学术年会论文集,2004,p19-28.
[12]曾庆成,高宇.集装箱码头装卸桥调度优化模型与算法[J],计算机工程与应用, 2006, 42(32): 217-219.
[13]王辉球.集装箱岸吊的调度模型和算法研究[D].清华大学硕士学位论文,2006.
[14]孙俊清,李平,韩梅.装卸桥调度问题及其混合智能优化算法GASA[C].第26届中国控制会议论文集,2007,7,26-31,p3410-3414.
[15] Kim K.H., Kim Y.K., Routing straddle carriers for the loading operation of containers using a beam search algorithm [J]. Computers & Industrial Engineering. 1999, 36(1): 55–68.
[16] Ng W.C. , Mak K.L. ,Yard crane scheduling in port container terminals [J]. Applied Mathematical Modelling , 2005, 29(3): 263–276.
[17] Chen L., Bostel N., Dejax P. et al, A tabu search algorithm for the integrated scheduling problem of container handling systems in a maritime terminal [J]. European Journal of Operational Research. 2008.181(1): 40-58.
[18] Henry Y.K. Lau, Ying Zhao,2007, Integrated scheduling of handling equipment atautomated container terminals. International Journal of Production Economics (2007), doi:10.1016/j.ijpe.2007.05.015
[19]张婕姝.港口生产调度仿真模型[J].上海海事大学学报. 2005, 26(2):42-46.
[20]张海霖,江志斌,许泓.集装箱港口集疏运调度系统作业模式的仿真分析[J].上海交通大学学报. 2006, 40(6):1024-1030.
[21]周鹏飞,康海贵,面向随机环境的集装箱码头泊位-岸桥分配方法[J].系统工程理论与实践.2008,1(1): 168-169
[22]曾庆成,杨忠振.集装箱码头作业调度双层规划模型及求解算法[J].哈尔滨工程大学学报. 2007, 28(3): 277-281.
[23] Liu, C.Y., Chang, S.C., Scheduling flexible flow shops with sequence-dependent setup effects [J]. IEEE Transactions on Robotics and Automation , 2000,16(4): 408–419.
[24] Kurz, M.E., Askin, R.G., Comparing scheduling rules for flexible flow lines [J]. International Journal of Production Economics 2003, 85(3):371–388.
[25] Kurz, M.E., Askin, R.G., Scheduling flexible flow lines with sequence-dependent setup times [J]. European Journal of Operational Research, 2004, 159(1): 66–82.
[26] Zandieh M., Fatemi Ghomi S.M.T., Moattar Husseini S.M., An immune algorithm approach to hybrid flow shops scheduling with sequence-dependent setup times [J]. Applied Mathematics and Computation 2006, 180(1): 111–127.
[27] Goodchild A.V. , Daganzo C.F., double cycling in container ports: Planning methods and evaluation[J], Transportation Research Part B ,2007, 41: 875–891.
[28] A. Mascis, D. Pacciarelli, Job-shop scheduling with blocking and no-wait constraints[J], European Journal of Operational Research.2002. 143: 498-517.
[29] D. Pacciarelli, Alternative graph formulation for solving complex factory-scheduling problems [J], International Journal of Production Research .2002. 40 (15): 3641-3653.
[30] Y. Mati, N. Rezg, X. Xie, Scheduling problem of job-shop with blocking: A taboo search approach, Extended Abstracts, MIC 2001-4th Meta heuristics International Conference, Portugal, 2001, 643-648.
[31] Heinz Gr?flin , Andreas Klinkert,Feasible insertions in job shop scheduling,short cycles and stable sets [J],European Journal of Operational Research.2007. 177: 763-785.
[32] Heinz Gr?flin , Andreas Klinkert,A new neighborhood and tabu search for the Blocking Job Shop [J],Discrete Applied Mathematics, In Press.
[33] Glover F. Tabu search. PartⅠ[M]. Journal of Computing, 1989, 1 (3): 190- 206.
[34] Glover F. Tabu search. PartⅡ[M]. Journal of Computing, 1990, 2 (1):4- 32.
[35] Hollnad J H. Adaptation in Nature and Artificial sysetm.lsted., 1975,2ndEd., Cambridge, MA,MIT Press, 1992.
[2] Ebru K. Bish, A multiple-crane-constrained scheduling problem in a container terminal [J]. European Journal of Operational Research. 2003, 144(1): 409–417.
[3] Vis,F.A.I.,de Koster,R.,2003 Transshipment of containers at a container terminal:An overview. European Journal of Operational Research 147,2003.p.p.1-16
[4] Daganzo, C.F. The crane scheduling problem. Transportation Research Part B,1989, 23: 159–175.
[5] Peterkofsky, R.I., Daganzo, C.F. A branch and bound solution method for the crane scheduling problem. Transportation Research Part B, 1990, 24: 159–172.
[6] Lim, A., Rodrigues, B., Xiao, F., Zhu, Y. Crane scheduling with spatial constraints. Naval Research Logistics, 2004, 51: 386–406.
[7] Kim, K.H., Park, Y.M. A crane scheduling method for port container terminals. European Journal of Operation Research, 2004, 156: 752–768.
[8] Lee, D.H., Wang, H.Q., Miao, L.X. Quay crane scheduling with non-interference constraints in port container terminals. Transportation Research Part E: Logistics and Transportation Review, 2008, 44(1): 124-135.
[9] Cordeau, J.F., Gaudioso, M., Laporte, G., Moccia, L. A branch-and-cut algorithm forthe quay crane scheduling problem in a container terminal. AIRO annual conference. Camerino, Italy, 2005, September 6–9.
[10] Zhang H.P. , Kim K.H. , Maximizing the number of dual-cycle operations of quay cranes in container terminals [J], Computers & Industrial Engineering ,2009, 56: 979–992.
[11]缪立新.集装箱装船顺序优化模型及算法研究[C].第三节中国物流学术年会论文集,2004,p19-28.
[12]曾庆成,高宇.集装箱码头装卸桥调度优化模型与算法[J],计算机工程与应用, 2006, 42(32): 217-219.
[13]王辉球.集装箱岸吊的调度模型和算法研究[D].清华大学硕士学位论文,2006.
[14]孙俊清,李平,韩梅.装卸桥调度问题及其混合智能优化算法GASA[C].第26届中国控制会议论文集,2007,7,26-31,p3410-3414.
[15] Kim K.H., Kim Y.K., Routing straddle carriers for the loading operation of containers using a beam search algorithm [J]. Computers & Industrial Engineering. 1999, 36(1): 55–68.
[16] Ng W.C. , Mak K.L. ,Yard crane scheduling in port container terminals [J]. Applied Mathematical Modelling , 2005, 29(3): 263–276.
[17] Chen L., Bostel N., Dejax P. et al, A tabu search algorithm for the integrated scheduling problem of container handling systems in a maritime terminal [J]. European Journal of Operational Research. 2008.181(1): 40-58.
[18] Henry Y.K. Lau, Ying Zhao,2007, Integrated scheduling of handling equipment atautomated container terminals. International Journal of Production Economics (2007), doi:10.1016/j.ijpe.2007.05.015
[19]张婕姝.港口生产调度仿真模型[J].上海海事大学学报. 2005, 26(2):42-46.
[20]张海霖,江志斌,许泓.集装箱港口集疏运调度系统作业模式的仿真分析[J].上海交通大学学报. 2006, 40(6):1024-1030.
[21]周鹏飞,康海贵,面向随机环境的集装箱码头泊位-岸桥分配方法[J].系统工程理论与实践.2008,1(1): 168-169
[22]曾庆成,杨忠振.集装箱码头作业调度双层规划模型及求解算法[J].哈尔滨工程大学学报. 2007, 28(3): 277-281.
[23] Liu, C.Y., Chang, S.C., Scheduling flexible flow shops with sequence-dependent setup effects [J]. IEEE Transactions on Robotics and Automation , 2000,16(4): 408–419.
[24] Kurz, M.E., Askin, R.G., Comparing scheduling rules for flexible flow lines [J]. International Journal of Production Economics 2003, 85(3):371–388.
[25] Kurz, M.E., Askin, R.G., Scheduling flexible flow lines with sequence-dependent setup times [J]. European Journal of Operational Research, 2004, 159(1): 66–82.
[26] Zandieh M., Fatemi Ghomi S.M.T., Moattar Husseini S.M., An immune algorithm approach to hybrid flow shops scheduling with sequence-dependent setup times [J]. Applied Mathematics and Computation 2006, 180(1): 111–127.
[27] Goodchild A.V. , Daganzo C.F., double cycling in container ports: Planning methods and evaluation[J], Transportation Research Part B ,2007, 41: 875–891.
[28] A. Mascis, D. Pacciarelli, Job-shop scheduling with blocking and no-wait constraints[J], European Journal of Operational Research.2002. 143: 498-517.
[29] D. Pacciarelli, Alternative graph formulation for solving complex factory-scheduling problems [J], International Journal of Production Research .2002. 40 (15): 3641-3653.
[30] Y. Mati, N. Rezg, X. Xie, Scheduling problem of job-shop with blocking: A taboo search approach, Extended Abstracts, MIC 2001-4th Meta heuristics International Conference, Portugal, 2001, 643-648.
[31] Heinz Gr?flin , Andreas Klinkert,Feasible insertions in job shop scheduling,short cycles and stable sets [J],European Journal of Operational Research.2007. 177: 763-785.
[32] Heinz Gr?flin , Andreas Klinkert,A new neighborhood and tabu search for the Blocking Job Shop [J],Discrete Applied Mathematics, In Press.
[33] Glover F. Tabu search. PartⅠ[M]. Journal of Computing, 1989, 1 (3): 190- 206.
[34] Glover F. Tabu search. PartⅡ[M]. Journal of Computing, 1990, 2 (1):4- 32.
[35] Hollnad J H. Adaptation in Nature and Artificial sysetm.lsted., 1975,2ndEd., Cambridge, MA,MIT Press, 1992.