Scheduling optimization of tramp shipping based on temporal and spatial attributes of shipping demand
-
摘要: 考虑货主的选择行为与运输需求的时空分布特征, 把承运人的船舶运营期划分为多个连续的时间窗, 基于离散选择模型把货主的选择惯性转化为承运人在航段上的市场份额, 对不同时间窗内承运人在即期市场上应承担的货运量进行优化; 以承运人利润最大为目标构建优化模型, 求解规划期内船舶的运营调度方案, 确定船舶承运的货物和航次衔接; 选取太平洋地区包括中国、加拿大、澳大利亚、俄罗斯、印度尼西亚、巴西和美国在内的7个国家作为干散货主要进出口国, 在每个国家确定一个港口作为网络节点, 根据克拉克森官网发布的航线、运价与干散货需求等数据对不定期船舶进行调度优化, 并采用遗传算法求解模型。计算结果表明: 在相同的运输时间窗内, 在优化方案下, 船舶航行时间为58 d, 收益为3.01×105美元, 在传统调度模式下, 单纯追求每个航段的收益最大化, 船舶航行时间为56 d, 收益为2.48×105美元, 优化方案的利润高出5.30×104美元, 因此, 为了最大化运营期的利润, 在货运需求时空变化和货主选择惯性的影响下, 船舶在某些时间窗内应执行空载或利润较低的航次。Abstract: The shippers' choice behaviors and the temporal and spatial distribution characteristics of shipping demand were considered, the carrier's ship operation period was divided into multiple continuous time windows, the selection inertia of the shipper was transformed into the potential market shares of the carriers on the shipping segment based on the discrete selection model, and the freight volumes of the carriers in the spot market in different time windows were optimized. An optimization model was built with the maximum profits of the carriers as the objective, and the shipping scheduling scheme was solved during the planning period, so as to determine the shipping cargo and voyage connection. Seven countries in the Pacific region, including China, Canada, Australia, Russia, Indonesia, Brazil, and America, were selected as the main importers and exporters of dry bulk cargoes, and one port of each country was selected as the node of transport network. According to the data published by Clarkson's official website, such as the routes, freight rates, and demand of dry bulk cargoes, the optimal scheduling of tramp ships be obtained by the genetic algorithm. Computation result shows that in the same shipping time window, the sailing time and profit of the ship are 58 days and 3.01×105 USD under the optimal scheduling scheme, respectively. While, in the traditional scheduling scheme maximizing the profit on each segment, the sailing time and profit of the ship are 56 days and 2.48×105 USD, respectively, and the profit is 5.30×104 USD lower than the profit under the optimal scheduling scheme. Therefore, in order to maximize the profit in the shipping period, under the influence of the temporal and spatial change of freight demand and the inertia of shipper choice, the ship should carry out the voyage without profit or with low profit in some time windows.
-
表 1 参数定义
Table 1. Parameters description
W 承运人的利润 xijvt 0-1变量, 1表示船舶v第t个时间窗在航段i-j (港口i到j) 行驶, 反之为0 xijvn 0-1变量, 1表示船舶v在航次n航段i-j行驶, 反之为0 Rijt 在时间窗t内航段i-j的收益 Sijt 在时间窗t内航段i-j的船舶数量 Cij 航段i-j的运输成本 fijt 在时间窗t内航段i-j的运价 λ 运价与距离的相关系数 a 时间窗t所在的季度 dij 航段i-j的距离 αa 运价在季节a的季度系数, 可根据BFI指数计算得到 S 船舶容量 lijt′ 当前时间窗t′内承运人在航段i-j上投放的船舶数量 nijt′ 当前时间窗t′内承运人完成可得到的货物需求所需要的船舶数量 Sijt′ 当前时间窗t′内承运人投入的船舶中满载的船舶数量 Tvn 船舶v在航次n的开始时间 s 船舶的经济航速 tvn 船舶v在航次n的开始时间窗内 Δt 时间窗长度, 干散货可延迟揽货时间一般为5 d δvnt′ 0-1变量, 1表示船舶v在航次n的开始时间在时间窗t′内, 反之为0 当前时间窗t′内承运人可得到的货物需求, 等于承运人在时间窗t′内在航段i-j的市场份额乘以对应的货运需求 Qija 航段i-j在季度a的货运需求 Pijt′r 当前时间窗t内, 承运人r在航段i-j上可得到的市场份额, r=1表示对象承运人, r=2表示其他所有的承运人 Uijt'r 到当前时间窗t′为止, 承运人r在航段i-j上的运输次数和规模所影响的效用函数 β1 船舶数量参数 β2 承运人规模参数 yr 承运人r的规模 
下载: 导出CSV
表 2 港口间干散货运输需求
Table 2. Shipping demands of dry bulk between ports
106 t 港口 终到港口 黒德兰港 丹戎巴拉港 青岛港 沃斯托奇内港 七岛港 休斯顿港 图巴朗港 起运港口 黒德兰港 0 0 35 752 0 0 15 0 丹戎巴拉港 0 0 7 237 0 0 0 0 青岛港 0 0 0 0 0 0 0 沃斯托奇内港 0 0 2 910 0 0 0 0 七岛港 0 0 155 0 0 11 0 休斯顿港 0 0 128 0 0 0 0 图巴朗港 0 0 1 672 0 0 38 0
下载: 导出CSV
表 3 船舶调度方案
Table 3. Scheduling schemes of ships
船舶 年利润/106美元 航次 空载航次 航线 1 1.962 12 5 1-6-7-6-3-1-6-5-3-1-6-7-3 2 1.794 14 7 2-3-4-3-1-6-7-3-1-6-3-4-3-2-1 3 1.728 17 7 7-6-4-3-2-3-1-6-5-6-7-6-3-4-3-1-6-3 4 2.423 12 5 6-5-3-1-6-3-1-6-3-2-1-6-3 5 0.948 16 8 5-6-5-6-7-6-3-2-1-6-7-3-4-3-4-6-3 6 1.724 15 7 5-3-2-3-1-6-5-3-4-3-1-6-7-3-4-3
下载: 导出CSV
表 4 船舶4收益对比
Table 4. Comparison of ship 4 earnings
方案 第1航段 第2航段 前2个航段的时间窗 收益/105美元 优化前 6-3 3-1 12 2.48 优化后 6-5 5-3 12 3.01
下载: 导出CSV
-
[1] BR∅NMO G, CHRISTIANSEN M, NYGREEN B. Ship routing and scheduling with flexible cargo sizes[J]. Journal of the Operational Research Society, 2007, 58 (9): 1167-1177. doi: 10.1057/palgrave.jors.2602263 [2] NORSTAD I, FAGERHOLT K, LAPORTE G. Tramp ship routing and scheduling with speed optimization[J]. Transportation Research Part C: Emerging Technologies, 2011, 19 (5): 853-865. doi: 10.1016/j.trc.2010.05.001 [3] REINHARDT L B, PISINGER D. A branch and cut algorithm for the container shipping network design problem[J]. Flexible Services and Manufacturing Journal, 2012, 24 (3): 349-374. doi: 10.1007/s10696-011-9105-4 [4] HALVORSEN-WEARE E E, FAGERHOLT K. Routing and scheduling in a liquefied natural gas shipping problem with inventory and berth constraints[J]. Annals of Operations Research, 2013, 203 (1): 167-186. doi: 10.1007/s10479-010-0794-y [5] PANG King-wah, XU Zhou, LI Chung-lun. Ship routing problem with berthing time clash avoidance constraints[J]. International Journal of Production Economics, 2011, 131 (2): 752-762. doi: 10.1016/j.ijpe.2011.03.013 [6] 唐磊, 谢新连, 王成武. 基于集合划分的航速可变不定期船舶调度模型[J]. 上海交通大学学报, 2013, 47 (6): 909-915. https://www.cnki.com.cn/Article/CJFDTOTAL-SHJT201306011.htmTANG Lei, XIE Xin-lian, WANG Cheng-wu. Model of tramp ship scheduling with variable speed based on set partition approach[J]. Journal of Shanghai Jiaotong University, 2013, 47 (6): 909-915. (in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-SHJT201306011.htm [7] 钱燕, 周良. 基于遗传算法的不定期船舶调度优化模型研究[J]. 计算机与数字工程, 2014, 42 (4): 601-605. doi: 10.3969/j.issn1672-9722.2014.04.015QIAN Yan, ZHOU Liang. Optimization model of tramp ship scheduling based on genetic algorithm[J]. Computer and Digital Engineering, 2014, 42 (4): 601-605. (in Chinese). doi: 10.3969/j.issn1672-9722.2014.04.015 [8] FAGERHOLT K, CHRISTIANSEN M. A combined ship scheduling and allocation problem[J]. Journal of the Operational Research Society, 2000, 51 (7): 834-842. doi: 10.1057/palgrave.jors.2600973 [9] FAGERHOLT K, CHRISTIANSEN M. A travelling salesman problem with allocation, time window and precedence constraints—an application to ship scheduling[J]. International Transactions in Operational Research, 2000, 7 (3): 231-244. doi: 10.1111/j.1475-3995.2000.tb00196.x [10] 谢新连. 船队规划的动态模型与算法[J]. 中国造船, 1992 (3): 102-110. https://www.cnki.com.cn/Article/CJFDTOTAL-ZGZC199203010.htmXIE Xin-lian. A dynamic model and algorithm for fleet planning[J]. Shipbuilding of China, 1992 (3): 102- 110. (in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-ZGZC199203010.htm [11] 余绍明. 航线配船的数学优化方法[J]. 交通与计算机, 1997, 15 (5): 44-45, 57. https://www.cnki.com.cn/Article/CJFDTOTAL-JTJS199705010.htmYU Shao-ming. Mathematical optimization method for ship routing[J]. Computer and Communications, 1997, 15 (5): 44-45, 57. (in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-JTJS199705010.htm [12] FAGERHOLT K. A computer-based decision support system for vessel fleet scheduling—experience and future research[J]. Decision Support Systems, 2004, 37 (1): 35-47. doi: 10.1016/S0167-9236(02)00193-8 [13] 金雁, 赵耀. 基于蚁群算法的航线配船[J]. 计算机工程与应用, 2007, 43 (25): 231-233. doi: 10.3321/j.issn:1002-8331.2007.25.068JIN Yan, ZHAO Yao. Utilization of ant colony algorithms in shipping arrangement[J]. Computer Engineering and Applications, 2007, 43 (25): 231-233. (in Chinese). doi: 10.3321/j.issn:1002-8331.2007.25.068 [14] 苏绍娟, 王丽铮, 王呈方. 不确定性航线配船数学模型建模方法[J]. 船海工程, 2007, 36 (4): 100-103. doi: 10.3963/j.issn.1671-7953.2007.04.032SU Shao-juan, WANG Li-zheng, WANG Cheng-fang. Mathematical model and method research of ships routing for indeterminate route[J]. Ship and Ocean Engineering, 2007, 36 (4): 100-103. (in Chinese). doi: 10.3963/j.issn.1671-7953.2007.04.032 [15] BR∅NMO G, NYGREEN B, LYSGAARD J. Column generation approaches to ship scheduling with flexible cargo sizes[J]. European Journal of Operational Research, 2010, 200 (1): 139-150. doi: 10.1016/j.ejor.2008.12.028 [16] KORSVIK J E, FAGERHOLT K, LAPORTE G. A large neighborhood search heuristic for ship routing and scheduling with split loads[J]. Computers and Operations Research, 2011, 38 (2): 474-483. doi: 10.1016/j.cor.2010.07.005 [17] 丁一, 仲颖, 林国龙, 等. 软时间窗与随机航行时间的不定期船舶航线规划[J]. 华中师范大学学报(自然科学版), 2015, 49 (3): 387-391. doi: 10.3969/j.issn.1000-1190.2015.03.014DING Yi, ZHONG Ying, LIN Guo-long, et al. Tramp ship routing plan with soft time window and random sailing time[J]. Journal of Central China Normal University (Natural Science Edition), 2015, 49 (3): 387-391. (in Chinese). doi: 10.3969/j.issn.1000-1190.2015.03.014 [18] PERAKIS A N, BREMER W M. An operational tanker scheduling optimization system: background, current practice and model formulation[J]. Maritime Policy and Management, 1992, 19 (3): 177-187. doi: 10.1080/751248659 [19] BREMER W M, PERAKIS A N. An operational tanker scheduling optimization system: model implementation, results and possible extensions[J]. Maritime Policy and Management, 1992, 19 (3): 189-199. doi: 10.1080/751248660 [20] GÄRLING T, AXHAUSEN K W. Introduction: habitual travel choice[J]. Transportation, 2003, 30 (1): 1-11. doi: 10.1023/A:1021230223001 [21] GARVILL J, MARELL A, NORDLUND A. Effects of increased awareness on choice of travel mode[J]. Transportation, 2003, 30 (1): 63-79. doi: 10.1023/A:1021286608889 [22] CANTILLO V, DE DIOS ORTÚZAR J, WILLIAMS H C W L. Modeling discrete choices in the presence of inertia and serial correlation[J]. Transportation Science, 2007, 41 (2): 195-205. doi: 10.1287/trsc.1060.0178 [23] CHERCHI E, MANCA F. Accounting for inertia in modal choices: some new evidence using a RP/SP dataset[J]. Transportation, 2011, 38 (4): 679-695. doi: 10.1007/s11116-011-9338-9 [24] 赵传林, 黄海军. 基于满意准则的有限理性用户均衡流量分配性质研究[J]. 系统工程理论与实践, 2014, 34 (12): 3073-3078. doi: 10.12011/1000-6788(2014)12-3073ZHAO Chuan-lin, HUANG Hai-jun. Properties of boundedly rational user equilibrium under satisficing rule in traffic assignment problem[J]. Systems Engineering—Theory and Practice, 2014, 34 (12): 3073-3078. (in Chinese). doi: 10.12011/1000-6788(2014)12-3073 [25] ZHANG Jun-lin, YANG Hai. Modeling route choice inertia in network equilibrium with heterogeneous prevailing choice sets[J]. Transportation Research Part C: Emerging Technologies, 2015, 57: 42-54. doi: 10.1016/j.trc.2015.06.005 [26] 黄溶冰, 张大勇. 摆脱行为惯性: 成长期企业应关注的问题[J]. 管理现代化, 2005 (3): 37-39. https://www.cnki.com.cn/Article/CJFDTOTAL-GLXX200503012.htmHUANG Rong-bing, ZHANG Da-yong. Getting rid of behavioral inertia: the issues that should be paid attention to in growing enterprises[J]. Modernization of Management, 2005 (3): 37-39. (in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-GLXX200503012.htm [27] 王宏. 浅析企业持续技术创新中的行为惯性[J]. 商业经济研究, 2010 (15): 88. doi: 10.3969/j.issn.1002-5863.2010.15.041WANG Hong. Brief analysis of behavioral inertia in enterprises' continuous technological innovation[J]. Journal of Commercial Economics, 2010 (15): 88. (in Chinese). doi: 10.3969/j.issn.1002-5863.2010.15.041 [28] CHEN Kang, CHEN Dong-xu, SUN Xue-shan, et al. Container ocean-transportation system design with the factors of demand fluctuation and choice inertia of shippers[J]. Transportation Research Part E: Logistics and Transportation Review, 2016, 95: 267-281. doi: 10.1016/j.tre.2016.09.015 [29] 陆婧, 杨忠振, 王文娣. 市场培养期内机场长途巴士时刻表动态优化[J]. 管理科学学报, 2016, 19 (12): 14-24. doi: 10.3969/j.issn.1007-9807.2016.12.002LU Jing, YANG Zhong-zhen, WANG Wen-di. Dynamic optimization of the timetable of airport coach during cultivation period[J]. Journal of Management Sciences in China, 2016, 19 (12): 14-24. (in Chinese). doi: 10.3969/j.issn.1007-9807.2016.12.002 [30] 陈康, 郭利泉, 杨忠振. 基于混合航线结构的集装箱航线与空重箱运输综合优化模型[J]. 系统工程理论与实践, 2014, 34 (1): 122-128. https://www.cnki.com.cn/Article/CJFDTOTAL-XTLL201401014.htmCHEN Kang, GUO Li-quan, YANG Zhong-zhen. Optimization model for container ship routing and empty/full container transport in the context of mixed route structure[J]. Systems Engineering—Theory and Practice, 2014, 34 (1): 122-128. (in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-XTLL201401014.htm -
点击查看大图
图(10) / 表(4)
计量
- 文章访问数: 771
- HTML全文浏览量: 183
- PDF下载量: 443
- 被引次数: 0
