考虑潮汐影响的班轮多船型船舶调度

来源:用户上传      作者:

　　摘 要：针对班轮企业由于提前公布船期表，但受货运需求的波动和潮汐的影响引起的多船型船舶调度问题进行研究。首先系统分析了一家班轮企业近洋运输航线结构;然后考虑大型船舶需乘潮进出港口，以及适当条件下允许租船的实际情况，兼顾班轮船期表的限制，构建了以运输总成本最小为目标的班轮多船型船舶调度非线性规划模型;最后考虑模型的特点，设计了嵌入基因修复的改进遗传算法（IGA）用于模型求解。实验结果表明，与传统的经验调度方案相比，得到的船舶调度方案在船舶利用率上能提高25%～35%;中规模算例下与CPLEX相比，IGA的CPU处理时间平均降低77%;中、大规模算例下与蚁群算法相比，IGA计算的运输费用平均降低15%。实验结果验证了所提模型和算法的有效性，可为班轮企业船舶调度提供参考。
　　关键词：班轮多船型船舶调度;船期表预知;非线性规划;可变航速;潮汐
　　中图分类号： U692.4+3
　　文献标志码：A
　　Abstract： 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.
　　Key words： multi-type liner scheduling; liner schedule prediction; nonlinear programming; variable speed; tide
　　0 引言
　　虽然班轮企业都会提前一个月左右公布船期表，但由于货运市场的起伏波动，以及天气和其他不确定因素的影响，使得每艘船舶的挂靠港口次序和每次运营的航线是不确定的。因此，为了尽可能保证货物按原船期表进行运输，并充分利用船队资源，提高航运企业的服务效率，需运用科学合理的方法对船舶调度进行优化。
　　船舶调度问题一直是相关各方研究的热点问题，是针对航运企业经营的每艘船，指定具体的航行路线、挂靠港口、运输任务及其运作时间表，通过合理的调度，高效利用船舶。船舶调度问题主要分为不定期船舶调度和班轮船舶调度两类。在不定期船舶调度方面，唐磊等[1]将船速对航次成本、航次时间的影响纳入到研究中，提出了不定期船舶调度的非线性网络规划模型，用于解决航速可变的船舶选线与调度规划问题，设计了基于集合划分方法的两阶段算法求解。钱燕等[2]针对不定期船舶调度中需求信息的动态变化、船舶类型的多样化以及船舶航线的不定性，以最小化航运成本为目标，建立了带滚动窗口的不定期多目标船舶调度优化模型，并制定了实时优化策略以实现需求信息变化时能快速调整船舶调度航线。Lin等[3]研究了不定期船舶分舱运输和货载转让的营运特点，建立船舶调度与货运分配组合优化的模型，并用遗传算法求解。
　　在班轮船舶调度方面，Agarwal等[4]将班轮运输中运输网络设计与船舶调度、货物路径问题进行联合优化，以船队在运输网络上的利润最大为目标，建立了混合整数规划模型，并用贪婪算法、列生成算法等三种算法求解。寿涌毅等[5]应用多目标规划方法研究了班轮运输的船舶调度问题，追求变动成本、航线运载量缺口和班轮航次总绝对偏差的共同最小化。Li等[6]側重于实时船期计划恢复问题，并考虑了常规不确定性和突发不确定性，目标是使延误惩罚总数最小化，以最有效的方式恢复受影响的时间表。Meng等[7]进行了班轮运输网络中有多个港口、多艘船的时间表设计和集装箱路线规划设计。杨立乾[8]基于轴辐式网络，在假定喂给港可被不同船舶多次挂靠的情况下，考虑船舶的运载能力以及班轮船期表的影响，建立集装箱支线运输多船型船舶调度模型，并利用粒子群算法求解。 　　但是以上班轮船舶调度均未考虑航速对船舶调度的影响。随着研究问题的深入，航速优化逐步成为船舶调度的一个侧重点，其中Qi等[9]考虑班轮时间表上不确定的港口时间和频率要求，考虑到航速的影响，以预期的总油耗最低为目标建立模型，制定了最佳船舶时间表。Lee等[10]使用一个动态规划方法设计了一个带有港口时间窗口的单船航线，每个港口只能被访问一次，将航速对航次时间的非线性影响纳入到船舶调度中，建立了以集装箱船舶运营成本最小的非线性混合整数规划模型来设计船期表。
　　综上，国内外对船舶调度的现有文献中，国外学者对于班轮船舶调度研究较多，而国内学者对不定期船舶调度研究居多;文献多以船舶运营总成本最小或者以利润最大为目标制定船舶调度计划，考虑航速变化对船舶调度的影响的文献近年来逐渐增加;具体到班轮船舶调度，多以船期表的制定为主，罕有考虑船期表提前公布情况下，研究为保证货物准时从启运港装卸并按时抵达目的港的船舶调度优化;且少有考虑自营船舶数目确定，适当时机可租船的实际情况;而针对现实作业中某些港口大型船舶需乘潮进/出港进而影响整个航线上船舶运输时间的问题目前几乎没有文献涉及。
　　区别于已有文献，本文针对船期表已提前公布的多条班轮航线，重点考虑船期表对船舶调度的约束，兼顾某些大型船舶需乘潮进出港的现实，以及航速变化对运输时间的影响，并涵盖可适时租船的情况，研究固定计划期内班轮船舶调度问题，以确保有船按时来港装卸货物，使得计划期内船舶运输总成本最低。
　　1 问题描述与建模
　　1.1 问题描述
　　针对一个已有班轮船队，班轮公司在经营范围内对货源、货流进行调查和预测，制定并公布未来一段时间的船期表。在该船期表使用过程中，受货运需求波动及潮汐等其他不确定因素的影响，船舶可能无法按照预计时间到港装卸货物，给班轮企业和客户带来损失。由于客户需要可靠的服务并期望準时交货，且企业要避免更高的运输成本受损，班轮企业需要根据具体货运需求调整航线上船舶的挂靠港、航速或租船，确保货物能按时装卸，以满足航线上港口的货运需求，而且能使班轮企业获得良好的经济效益。
　　问题描述：预知固定计划期内各航线的货运流量和船期表，探讨多个港口、多种船型的班轮船舶调度问题，在保证货物按时装卸的前提下，以计划期内所有船舶运输成本最低制定船舶调度方案。区别于已有文献，本文的侧重点主要有以下几个方面：
　　4 结语
　　本文在船期表预知的情况下，针对多条近洋航线考虑了船舶容量、数量、航速、班轮时间的限制以及大型船舶需乘潮进出港口的情况，构建了集装箱运输多船型船舶调度非线性规划模型，并设计了改进的遗传算法IGA求解。具体结论如下：
　　1）建立了考虑大型船舶需乘潮进出港口的实际情况的多船型船舶调度模型，在船期表预知的前提下，考虑调节船速有助于保证船舶按时到港装卸货物;考虑适时租船保证货量需求得到满足。尽管航速提高和租船会带来部分成本，但是与货物运输延误给班轮企业所带来的损失相比甚微。
　　2）设计了改进的遗传算法IGA，对于不同层的染色体根据其实际特点采取了不同的编码方式，融入了基因修复的思想，能为解决该类船舶调度问题的算法提供新的设计思路。
　　3）本文所设计的模型与算法可以为班轮企业船舶调度提供决策支持，对于客户满意度要求较高的班轮企业有借鉴意义。
　　考虑到客户需求的变化，未来可以研究需求变动下的班轮船舶调度问题。
　　参考文献：
　　[1] 唐磊，谢新连，王成武.基于集合划分的航速可变不定期船舶调度模型[J].上海交通大学学报，2013，47（6）：909-915.（TANG L， 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 Y Y， 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 H D. 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.
转载注明来源:https://www.xzbu.com/8/view-14941664.htm