基于集合划分的航速可变不定期船舶调度模型

摘要/Abstract

摘要：

基于不定期船多货物、多船舶、多挂靠港口和多航线的运营组织特征，综合考虑船速对航次时间、航次成本的非线性影响，提出了不定期船舶调度的非线性网络规划模型，用于解决航速可变的船舶选线与调度规划问题.针对模型的结构特点，设计了基于集合划分方法的两阶段求解算法.通过案例计算验证了模型和算法的效果.计算结果表明：考虑船速可变，制定的船舶调度方案能使营运收益提高10%~25%.新建立的模型能够对船舶运行计划、货载选择、包运货物运输组织方式和船速等进行统筹规划，制定详细的船舶运行时刻表，为不定期船舶调度实务提供决策支持.

关键词: 不定期船调度, 集合划分, 航速, 非线性规划

Abstract:

According to the operation feature of tramp shipping which involves numerous cargos, ships, ports and lanes, a tramp ship scheduling and speed optimization model was proposed to deal with the ship scheduling problem with variable speed, after analysis of the effect of ship speed on fuel cost and time table. In light of the structure of the model, the two phase algorithm based on set partition model was designed. The availability and reasonability of the model and algorithm was tested and proved by some cases. The results show that the operating income increases by 10%~25%, when speed is taken as a decision variable. The model established could comprehensively optimize ship scheduling, cargo selection, contractual cargo transportation organization, and ship speed, which can provide decision-making support for tramp schedule practice.

Key words: tramp ship schedule, set partition, sailing speed, nonlinear programming

中图分类号:

U 692

唐磊1，谢新连1，王成武2. 基于集合划分的航速可变不定期船舶调度模型[J]. 上海交通大学学报（自然版）, 2013, 47(06): 909-915.

TANG Lei1,XIE Xinlian1，WANG Chenwu2. Model of Tramp Ship Scheduling with Variable Speed Based on Set Partition Approach[J]. Journal of Shanghai Jiaotong University, 2013, 47(06): 909-915.

参考文献

［1］Christiansen M, Fagerholt K, Ronen D. Ship routing and scheduling: status and perspective［J］. Transportation Science, 2004, 38(1):118.

［2］Brnmo G, Christiansen M, Nygreen B. Ship routing and scheduling with flexible cargo sizes［J］. Journal of the Operational Research, 2007, 58:11671177.

［3］Zeng Q C, Yang Z Z. Model integrating fleet design and ship routing problems for coal shipping［C］//Shi Y, Albada G D, Dongarra J, et al. Computational ScienceICCS2007.German: Sprinter, 2007:10001003.

［4］靳志宏,解玉真,李阳,等.集装箱支线运输船舶调度优化问题［J］.中国航海,2008, 31(4):416419.

JIN Zhihong, XIE Yuzhen, LI Yang, et al. Scheduling optimization problems of feeder line container ships［J］. Navigation of China, 2008, 31(4): 416419.

［5］Hwang H S. A branchandpriceandcut method for ship scheduling with limited risk［J］. Transportation Science, 2008, 42(3):336351.

［6］Lin D Y, Liu H Y. Combined ship allocation, routing and freight assignment in tramp shipping［J］. Transportation Research E, 2011, 47:414431.

［7］寿涌毅,赖昌涛,吕如福.班轮船舶调度多目标优化模型与蚁群算法［J］.交通运输工程学报,2011, 11(4):8488.

SHOU Yongyi, LAI Changtao, LV Rufu. Multiobjective optimization model and ant colony optimization of liner ship scheduling［J］. Journal of Traffic and Transportation Engineering, 2011, 11(4): 8488.

［8］Ronen D. The effect of oil price on the optimal speed of ships ［J］. The Journal of the Operational Research Society,1982, 33(11):10351040.

［9］殷翔宇,张俊,谢新连.不定期船最佳航速优化研究［J］.中国航海, 2012, 35(1):9497.

YIN Xiangyu, ZHANG Jun, XIE Xinlian. Research on the optimal speed of tramp vessel［J］. Mavigation of China, 2012, 35(1):9497.

［10］谢新连.船舶运输管理与经营［M］. 2版.大连:大连海事大学出版社,2009.

［11］谢新连,杨秋平.船舶调度与船队规划方法［M］. 2版.大连:大连海事大学出版社,2012.

［12］谢亮,江晓东,李少华.基于混合校正内点法的最优潮流［J］.上海交通大学学报, 2011,45(6):

804808.

XIE Liang, JIANG Xiaodong, LI Shaohua. Hybrid corrector interior point method for optimal power flow［J］. Journal of Shanghai Jiaotong University, 2011, 45(6): 804808.

［13］Brnmo G, Christiansen M, Fagerholt K, et al. A multistart local search heuristic for ship schedulinga computational study［J］. Computers and Operations Research,2007, 34：900917.

［14］陈康,杨忠振.基于三方博弈的短途班轮航线优化模型［J］.交通运输工程学报, 2011, 11(6):7481.

CHEN Kang, YANG Zhongzhen. Optimization model of shortdistance liner ship route based on tripartite game［J］. Journal of Traffic and Transportation Engineering, 2011, 11(6):7481.

［15］林智勇.带约束集合划分优化问题及其求解［J］.计算机工程与科学, 2005, 27(7):97100.

LIN Zhiyong. The problem of set partitin optimization with constraints and its solution［J］. Computer Engineering & Science, 2005, 27(7):97100.

［16］国际海事信息网.世界干散货船租赁成交报告［EB/OL］.(2010414) ［2012420］. http://www.simic.net.cn/news_show.php?id=53868.

[1]	李臻, 许冰青, 李庆波, 鄢雄伟, 李博雅. 基于序列凸优化算法的飞行器轨迹规划[J]. 空天防御, 2021, 4(4): 50-56.
[2]	范厚明, 于佳琪, 马梦知, 蒋晓丹, 慈吉利, 翟志伟. 模糊时间窗下多船型不定期船调度与航速联合优化[J]. 上海交通大学学报, 2021, 55(3): 297-310.
[3]	薄翠梅a, b, 汤吉海a, 乔旭a, 丁良辉a, 崔咪芬a. 苯氯化侧反应精馏过程的模拟优化与系统实现方法[J]. 上海交通大学学报（自然版）, 2011, 45(08): 1157-1161.
[4]	谢亮1, 江晓东2, 李少华1. 基于混合校正内点法的最优潮流[J]. 上海交通大学学报（自然版）, 2011, 45(06): 804-808.
[5]	张宝吉，马坤. 基于Rankine源法的船体线型优化设计 [J]. 上海交通大学学报（自然版）, 2010, 44(10): 1414-1417.
[6]	杨洪杰, 葛修润, 王建华, 傅德明. 序列二次规划（SQP)算法在三维下限分析中的应用[J]. 上海交通大学学报, 2004, 38(06): 992-995.
[7]	杨洪杰, 沈珠江, 王建华, 张宙云. c-O材料的三维上限分析[J]. 上海交通大学学报, 2003, 37(12): 1923-1926.