考虑潮汐的多港池港口船舶调度优化
|
摘要
针对多港池港口船舶调度优化问题,重点考虑大型船舶乘潮进出港口的影响,兼顾单向航道下进出港船舶间需保持安全航行距离、进出港时段交替条件及连续泊位靠泊限制等现实约束,以所有船舶总等待时间最小为目标,构建了混合整数线性规划模型.基于船舶调度问题的特点,提出了启发式规则,将原问题分解为五个子问题进而获得初始解,并设计了改进和声搜索算法求解.在数值实验中,将该算法的求解结果同下界对比,平均相对偏差为2.19%,且求解耗时均少于1分钟,验证了算法的有效性;将方案的求解结果同两种现行调度规则对比,不同算例规模下平均目标值优化率分别为13.30%和27.35%,可显著提高港口船舶服务效率,验证了方案的有效性.
To optimize the ship scheduling in multi-harbor basin port, this paper focuses on the influence of large ships in/outbound harbor with tidal condition. A safe navigation distance for ships in/outbound harbor in one-way channel, in/outbound harbor time alternating conditions and berth limit of continuous berth is considered. A mixed integer linear programming model is proposed to minimize the total waiting time of all ships. Based on the characteristics of ship scheduling optimization, the original problem is decomposed into five sub-problems to obtain initial solution, and the improved harmony search algorithm is designed to solve the problem. In the numerical experiments, the proposed algorithm is compared with the lower bound of the model to illustrate the validity of the algorithm. Results show that the average relative deviation is 2.19%, and the computation time is less than 1 minute. The analyzing results are compared with those under two existing scheduling rules, in which the optimization rates of average objective values are 13.30% and 27.35% respectively for different experiment sizes. The proposed model and algorithm can significantly improve the service efficiency of the port for ships and verify the effectiveness of the schedules.
To optimize the ship scheduling in multi-harbor basin port, this paper focuses on the influence of large ships in/outbound harbor with tidal condition. A safe navigation distance for ships in/outbound harbor in one-way channel, in/outbound harbor time alternating conditions and berth limit of continuous berth is considered. A mixed integer linear programming model is proposed to minimize the total waiting time of all ships. Based on the characteristics of ship scheduling optimization, the original problem is decomposed into five sub-problems to obtain initial solution, and the improved harmony search algorithm is designed to solve the problem. In the numerical experiments, the proposed algorithm is compared with the lower bound of the model to illustrate the validity of the algorithm. Results show that the average relative deviation is 2.19%, and the computation time is less than 1 minute. The analyzing results are compared with those under two existing scheduling rules, in which the optimization rates of average objective values are 13.30% and 27.35% respectively for different experiment sizes. The proposed model and algorithm can significantly improve the service efficiency of the port for ships and verify the effectiveness of the schedules.
引文
[1] Imai A, Nishimura E, Papadimitriou S. The dynamic berth allocation problem for a container port[J]. Transportation Research Part B:Methodological, 2001, 35(4):401-417.
[2] Imai A, Nishimura E, Papadimitriou S. Berth allocation with service priority[J]. Transportation Research Part B:Methodological, 2003, 37(5):437-457.
[3] Imai A, Sun X, Nishimura E, et al. Berth allocation in a container port:Using a continuous location space approach[J]. Transportation Research Part B:Methodological, 2005, 39(3):199-221.
[4] Hansen P, Oguz C, Mladenovic N. Variable neighborhood search for minimum cost berth allocation[J]. EuropeanJournal of Operational Research, 2008, 191(3):636-649.
[5] Xu D, Li C L, Leung Y T. Berth allocation with time-dependent physical limitations on vessels[J]. European Journal of Operational Research, 2012, 216(1):47-56.
[6] Mauri G R, Ribeiro G M, Lan L, et al. An adaptive large neighborhood search for the discrete and continuous Berth allocation problem[J]. Computers&Operations Research, 2016, 70(C):140-154.
[7]曾庆成,冯媛君,度盼.面向干支线船舶衔接的集装箱码头泊位分配模型[J].系统工程理论与实践,2016,36(1):154-163.Zeng Q C, Feng Y J, Du P. Berth allocation model based on direct transshipment of trunk line and feeder vessels at container terminals[J]. Systems Engineering—Theory&Practice, 2016, 36(1):154-163.
[8] Park Y M, Kim K H. A scheduling method for berth and quay cranes[J]. OR Spectrum, 2003, 25(1):1-23.
[9] Han X L, Gong X, Jo J. A new continuous berth allocation and quay crane assignment model in container terminal[J]. Computers&Industrial Engineering, 2015, 89(C):15-22.
[10] Unsal O, Oguz C. Constraint programming approach to quay crane scheduling problem[J]. Transportation Research Part E:Logistics&Transportation Review, 2013, 59(59):108-122.
[11] Meisel F,Bierwirth C. A framework for integrated berth allocation and crane operations planning in seaport container terminals[J]. Transportation Science, 2013, 47(2):131-147.
[12]孙彬,孙俊清,陈秋双.基于鲁棒反应式策略的泊位和岸桥联合调度[J].系统工程理论与实践,2013, 33(4):1076-1083.Sun B, Sun J Q,Chen Q S. Integrated scheduling for berth and quay cranes based on robust and reactive policy[J]. Systems Engineering—Theory&Practice, 2013, 33(4):1076-1083.
[13] Tiirkogullari Y B, Taskin Z C, Aras N, et al. Optimal berth allocation, time-variant quay crane assignment and scheduling with crane setups in container terminals[J]. European Journal of Operational Research, 2016, 254(3):985-1001.
[14]郑红星,尹吴,曹红雷,等.考虑潮汐影响的离散型泊位和岸桥集成调度[J].运筹与管理,2017, 26(6):167-175.Zheng H X, Yin H, Cao H L, et al. Integrated discrete berth allocation and quay crane scheduling under tidal influence at container terminal[J]. Operations Research and Management Science, 2017, 26(6):167-175.
[15] Verstichel J, Causmaecker P D, Berghe G V. Scheduling algorithms for the lock scheduling problem[J]. Procedia—Social and Behavioral Sciences, 2011, 20(6):806-815.
[16]周鹏飞,史瑞粉,魏晓晓.港区航道系统综合通过能力仿真建模研究[J].系统仿真学报,2013, 25(6):1258-1263.Zhou P F, Shi R F, Wei X X. Study on simulation model of synthesis channel transit capacity of port[J]. Journal of System Simulation, 2013, 25(6):1258-1263.
[17] Lalla-Ruiz E, Shi X, VoβS. The waterway ship scheduling problem[J]. Transportation Research Part D:Transport&Environment, 2016, 220(4598):671-680.
[18] Zhang X Y, Lin J, Guo Z, et al. Vessel transportation scheduling optimization based on channel berth coordination[J]. Ocean Engineering, 2016, 112:145-152.
[19]张新宇,林俊,郭子坚,等.基于模拟退火多种群遗传算法的港口船舶调度优化[J].中国航海,2016, 39(1):26-30.Zhang X Y, Lin J, Guo Z J, et al. Vessel scheduling optimization based on simulated annealing and multiple population genetic algorithm[J]. Navigation of China, 2016, 39(1):26-30.
[2] Imai A, Nishimura E, Papadimitriou S. Berth allocation with service priority[J]. Transportation Research Part B:Methodological, 2003, 37(5):437-457.
[3] Imai A, Sun X, Nishimura E, et al. Berth allocation in a container port:Using a continuous location space approach[J]. Transportation Research Part B:Methodological, 2005, 39(3):199-221.
[4] Hansen P, Oguz C, Mladenovic N. Variable neighborhood search for minimum cost berth allocation[J]. EuropeanJournal of Operational Research, 2008, 191(3):636-649.
[5] Xu D, Li C L, Leung Y T. Berth allocation with time-dependent physical limitations on vessels[J]. European Journal of Operational Research, 2012, 216(1):47-56.
[6] Mauri G R, Ribeiro G M, Lan L, et al. An adaptive large neighborhood search for the discrete and continuous Berth allocation problem[J]. Computers&Operations Research, 2016, 70(C):140-154.
[7]曾庆成,冯媛君,度盼.面向干支线船舶衔接的集装箱码头泊位分配模型[J].系统工程理论与实践,2016,36(1):154-163.Zeng Q C, Feng Y J, Du P. Berth allocation model based on direct transshipment of trunk line and feeder vessels at container terminals[J]. Systems Engineering—Theory&Practice, 2016, 36(1):154-163.
[8] Park Y M, Kim K H. A scheduling method for berth and quay cranes[J]. OR Spectrum, 2003, 25(1):1-23.
[9] Han X L, Gong X, Jo J. A new continuous berth allocation and quay crane assignment model in container terminal[J]. Computers&Industrial Engineering, 2015, 89(C):15-22.
[10] Unsal O, Oguz C. Constraint programming approach to quay crane scheduling problem[J]. Transportation Research Part E:Logistics&Transportation Review, 2013, 59(59):108-122.
[11] Meisel F,Bierwirth C. A framework for integrated berth allocation and crane operations planning in seaport container terminals[J]. Transportation Science, 2013, 47(2):131-147.
[12]孙彬,孙俊清,陈秋双.基于鲁棒反应式策略的泊位和岸桥联合调度[J].系统工程理论与实践,2013, 33(4):1076-1083.Sun B, Sun J Q,Chen Q S. Integrated scheduling for berth and quay cranes based on robust and reactive policy[J]. Systems Engineering—Theory&Practice, 2013, 33(4):1076-1083.
[13] Tiirkogullari Y B, Taskin Z C, Aras N, et al. Optimal berth allocation, time-variant quay crane assignment and scheduling with crane setups in container terminals[J]. European Journal of Operational Research, 2016, 254(3):985-1001.
[14]郑红星,尹吴,曹红雷,等.考虑潮汐影响的离散型泊位和岸桥集成调度[J].运筹与管理,2017, 26(6):167-175.Zheng H X, Yin H, Cao H L, et al. Integrated discrete berth allocation and quay crane scheduling under tidal influence at container terminal[J]. Operations Research and Management Science, 2017, 26(6):167-175.
[15] Verstichel J, Causmaecker P D, Berghe G V. Scheduling algorithms for the lock scheduling problem[J]. Procedia—Social and Behavioral Sciences, 2011, 20(6):806-815.
[16]周鹏飞,史瑞粉,魏晓晓.港区航道系统综合通过能力仿真建模研究[J].系统仿真学报,2013, 25(6):1258-1263.Zhou P F, Shi R F, Wei X X. Study on simulation model of synthesis channel transit capacity of port[J]. Journal of System Simulation, 2013, 25(6):1258-1263.
[17] Lalla-Ruiz E, Shi X, VoβS. The waterway ship scheduling problem[J]. Transportation Research Part D:Transport&Environment, 2016, 220(4598):671-680.
[18] Zhang X Y, Lin J, Guo Z, et al. Vessel transportation scheduling optimization based on channel berth coordination[J]. Ocean Engineering, 2016, 112:145-152.
[19]张新宇,林俊,郭子坚,等.基于模拟退火多种群遗传算法的港口船舶调度优化[J].中国航海,2016, 39(1):26-30.Zhang X Y, Lin J, Guo Z J, et al. Vessel scheduling optimization based on simulated annealing and multiple population genetic algorithm[J]. Navigation of China, 2016, 39(1):26-30.