考虑潮汐影响的班轮多船型船舶调度
|
摘要
针对班轮企业由于提前公布船期表,但受货运需求的波动和潮汐的影响引起的多船型船舶调度问题进行研究。首先系统分析了一家班轮企业近洋运输航线结构;然后考虑大型船舶需乘潮进出港口,以及适当条件下允许租船的实际情况,兼顾班轮船期表的限制,构建了以运输总成本最小为目标的班轮多船型船舶调度非线性规划模型;最后考虑模型的特点,设计了嵌入基因修复的改进遗传算法(IGA)用于模型求解。实验结果表明,与传统的经验调度方案相比,得到的船舶调度方案在船舶利用率上能提高25%～35%;中规模算例下与CPLEX相比,IGA的CPU处理时间平均降低77%;中、大规模算例下与蚁群算法相比,IGA计算的运输费用平均降低15%。实验结果验证了所提模型和算法的有效性,可为班轮企业船舶调度提供参考。
The multi-type liner scheduling problem in liner enterprises caused by the fluctuation of cargo demand and tide with line schedule announced in advance was studied.Firstly,the structure of near-sea transportation routes of a liner enterprise was systematically analyzed.Then,with the consideration of the real situations like large ships need to tide in and out of ports,ship renting is permitted under appropriate conditions,and the limits of a liner schedule,a nonlinear programming model of multi-type liner scheduling was built with the objective of minimizing the total transportation cost.Finally,in view of the characteristics of the model,an Improved Genetic Algorithm(IGA)embedded with gene repair was designed to solve the problem.Experimental results show that the proposed liner scheduling scheme can improve the ship utilization ratio by 25%-35% compared with the traditional experiential liner scheduling scheme,the CPU processing time of IGA is reduced by 32%on average compared with CPLEX in medium scale,and the transportation cost of IGA is reduced by 12% on average compared with ant colony algorithm in medium and large scales.All above demonstrates the validity of the proposed model and algorithm which can provide a reference for liner enterprises in liner scheduling.
The multi-type liner scheduling problem in liner enterprises caused by the fluctuation of cargo demand and tide with line schedule announced in advance was studied.Firstly,the structure of near-sea transportation routes of a liner enterprise was systematically analyzed.Then,with the consideration of the real situations like large ships need to tide in and out of ports,ship renting is permitted under appropriate conditions,and the limits of a liner schedule,a nonlinear programming model of multi-type liner scheduling was built with the objective of minimizing the total transportation cost.Finally,in view of the characteristics of the model,an Improved Genetic Algorithm(IGA)embedded with gene repair was designed to solve the problem.Experimental results show that the proposed liner scheduling scheme can improve the ship utilization ratio by 25%-35% compared with the traditional experiential liner scheduling scheme,the CPU processing time of IGA is reduced by 32%on average compared with CPLEX in medium scale,and the transportation cost of IGA is reduced by 12% on average compared with ant colony algorithm in medium and large scales.All above demonstrates the validity of the proposed model and algorithm which can provide a reference for liner enterprises in liner scheduling.
引文
[1]唐磊,谢新连,王成武.基于集合划分的航速可变不定期船舶调度模型[J].上海交通大学学报,2013,47(6):909-915.(TANGL,XIE X L,WANG C W.Model of tramp ship scheduling with variable speed based on set partition approach[J].Journal of Shanghai Jiao Tong University,2013,47(6):909-915.)
[2]钱燕,周良.基于遗传算法的不定期船舶调度优化模型研究[J].计算机与数字工程,2014,42(4):601-605.(QIAN Y,ZHOU L.Optimization model of tramp ship scheduling based on genetic algorithm[J],Computer and Digital Engineering,2014,42(4):601-605.)
[3]LIN D-Y,LIU H-Y.Combined ship allocation,routing and freight assignment in tramp shipping[J].Transportation Research Part E:Logistics and Transportation Review,2010,47(4):414-431.
[4]AGARWAL R,ERGUN O.Ship scheduling and network design for cargo routing in liner shipping[J].Transportation Science,2008,42(2):175-196.
[5]寿涌毅,赖昌涛,吕如福.班轮船舶调度多目标优化模型与蚁群算法[J].交通运输工程学报,2011,11(4):84-88.(SHOU YY,LAI C T,LYU R F.Multi-objective optimization model and ant colony optimization of liner ship scheduling[J].Journal of Traffic and Transportation Engineering,2011,11(4):84-88.)
[6]LI C,QI X,SONG D.Real-time schedule recovery in liner shipping service with regular uncertainties and disruption events[J].Transportation Research Part B:Methodological,2016,93:762-788.
[7]MENG Q,WANG S.Schedule design and container routing in liner shipping[J].Transportation Research Record,2011,2222(1):25-33.
[8]杨立乾.基于轴辐式网络的集装箱支线运输多船型船舶调度模型[J].中国管理科学,2015,23(SI):860-864.(YANG L Q.Scheduling model of feeder line multi-hull container ships based on hub-and-spoke network[J].Chinese Jurnal of Management Science,2015,23(SI):860-864.)
[9]QI X,SONG D-P.Minimizing fuel emissions by optimizing vessel schedules in liner shipping with uncertain port times[J].Transportation Research Part E:Logistics and Transportation Review,2012,48(4):863-880.
[10]LEE C-Y,MENG Q.Handbook of Ocean Container Transport Logistics:Making Global Supply Chains Effective[M].Berlin:Springer,2015:279-373.
[11]靳志宏,解玉真,李阳,等.集装箱支线运输船舶调度优化问题[J].中国航海,2008,31(4):416-419.(JIN Z H,XIE Y Z,LI Y,et al.Scheduling optimization problems of feeder line container ships[J].Navigation of China,2011,31(11):3075-3077.)
[12]吕靖,毛鹤达.硫排放控制区和碳排放限制下的班轮航线配船模型[J].大连海事大学学报,2017,43(1):101-105.(LYU J,MAO HD.Fleet deployment for liner shipping under the restriction of SOx emission control areas and CO2 emission[J].Journal of Dalian Maritime University,2017,43(1):101-105.)
[13]杜剑,赵旭,王军.内支线集装箱班轮航线优化设计模型[J].交通运输系统工程与信息,2017,17(3):178-191.(DU J,ZHAO X,WANG J.Container feeder liner shipping service optimal design model[J].Journal of Transportation Systems Engineering and Information Technology,2017,17(3):178-191.)
[14]DULEBENETS M A.The vessel scheduling problem in a liner shipping route with heterogeneous fleet[J].International Journal of Civil Engineering,2018,16(1):19-32.
[2]钱燕,周良.基于遗传算法的不定期船舶调度优化模型研究[J].计算机与数字工程,2014,42(4):601-605.(QIAN Y,ZHOU L.Optimization model of tramp ship scheduling based on genetic algorithm[J],Computer and Digital Engineering,2014,42(4):601-605.)
[3]LIN D-Y,LIU H-Y.Combined ship allocation,routing and freight assignment in tramp shipping[J].Transportation Research Part E:Logistics and Transportation Review,2010,47(4):414-431.
[4]AGARWAL R,ERGUN O.Ship scheduling and network design for cargo routing in liner shipping[J].Transportation Science,2008,42(2):175-196.
[5]寿涌毅,赖昌涛,吕如福.班轮船舶调度多目标优化模型与蚁群算法[J].交通运输工程学报,2011,11(4):84-88.(SHOU YY,LAI C T,LYU R F.Multi-objective optimization model and ant colony optimization of liner ship scheduling[J].Journal of Traffic and Transportation Engineering,2011,11(4):84-88.)
[6]LI C,QI X,SONG D.Real-time schedule recovery in liner shipping service with regular uncertainties and disruption events[J].Transportation Research Part B:Methodological,2016,93:762-788.
[7]MENG Q,WANG S.Schedule design and container routing in liner shipping[J].Transportation Research Record,2011,2222(1):25-33.
[8]杨立乾.基于轴辐式网络的集装箱支线运输多船型船舶调度模型[J].中国管理科学,2015,23(SI):860-864.(YANG L Q.Scheduling model of feeder line multi-hull container ships based on hub-and-spoke network[J].Chinese Jurnal of Management Science,2015,23(SI):860-864.)
[9]QI X,SONG D-P.Minimizing fuel emissions by optimizing vessel schedules in liner shipping with uncertain port times[J].Transportation Research Part E:Logistics and Transportation Review,2012,48(4):863-880.
[10]LEE C-Y,MENG Q.Handbook of Ocean Container Transport Logistics:Making Global Supply Chains Effective[M].Berlin:Springer,2015:279-373.
[11]靳志宏,解玉真,李阳,等.集装箱支线运输船舶调度优化问题[J].中国航海,2008,31(4):416-419.(JIN Z H,XIE Y Z,LI Y,et al.Scheduling optimization problems of feeder line container ships[J].Navigation of China,2011,31(11):3075-3077.)
[12]吕靖,毛鹤达.硫排放控制区和碳排放限制下的班轮航线配船模型[J].大连海事大学学报,2017,43(1):101-105.(LYU J,MAO HD.Fleet deployment for liner shipping under the restriction of SOx emission control areas and CO2 emission[J].Journal of Dalian Maritime University,2017,43(1):101-105.)
[13]杜剑,赵旭,王军.内支线集装箱班轮航线优化设计模型[J].交通运输系统工程与信息,2017,17(3):178-191.(DU J,ZHAO X,WANG J.Container feeder liner shipping service optimal design model[J].Journal of Transportation Systems Engineering and Information Technology,2017,17(3):178-191.)
[14]DULEBENETS M A.The vessel scheduling problem in a liner shipping route with heterogeneous fleet[J].International Journal of Civil Engineering,2018,16(1):19-32.