模糊时间窗下多船型不定期船调度与航速联合优化

doi:10.16183/j.cnki.jsjtu.2019.215

摘要/Abstract

摘要：

为了提高货主满意度的同时船公司能获得更好的经济效益，对不定期船调度与航速联合优化问题进行了研究，利用模糊时间窗刻画货主满意度，考虑自有船舶与租用船舶配置情况、航速等因素对船舶调度计划的影响，以航行成本、港口成本、时间成本、租船成本之和最小为目标，建立模糊时间窗下多船型不定期船调度与航速优化模型．提出一种变邻域遗传模拟退火算法进行求解：先将船型与货物匹配，再根据时间约束生成路径，最后采用邻域搜索策略提高求解质量．算例验证表明：船舶调度与航速联合优化可降低航行成本；注重货主的时间要求可提高其满意度．研究成果拓展了船舶调度及航速优化的相关理论，可为船公司优化不定期船调度及航速提供理论指导．

关键词: 不定期船, 航速优化, 船舶调度, 模糊时间窗

Abstract:

In order to improve the cargo owner’s satisfaction and obtain better economic benefits for shipping companies, the ship deployment along routes and speed optimization of tramp ships are studied, considering the influencing factors of ship scheduling with the configuration and speed of self-owned ships and chartered ships. A goal is developed by minimizing sailing cost, fuel, and waiting cost at ports, penalty cost for late arrival at ports, time cost, and voyage ship chartering cost by applying fuzzy time window to characterize the cargo owner’s satisfaction. The model of scheduling and speed optimization with fuzzy time window for heterogeneous tramp ships is established. A variable neighborhood genetic simulated annealing (VNGSA) algorithm is presented to solve the problem. First, the ship type is matched with the cargo. Then the route is generated according to the time constraint. Finally, the neighborhood search strategy is adopted to improve the solution quality. Computational results indicate that integrated planning for ship scheduling and speed can reduce sailing cost; considering time requirement of cargo owners can increase their satisfaction. This paper can enrich tramp ship routing and speed optimization problems and provide a theoretical tool for shipping companies to make related decisions.

Key words: tramp ship, speed optimization, ship schedule, fuzzy time window

中图分类号:

U692

范厚明, 于佳琪, 马梦知, 蒋晓丹, 慈吉利, 翟志伟. 模糊时间窗下多船型不定期船调度与航速联合优化[J]. 上海交通大学学报, 2021, 55(3): 297-310.

FAN Houming, YU Jiaqi, MA Mengzhi, JIANG Xiaodan, CI Jili, ZHAI Zhiwei. Heterogeneous Tramp Ship Scheduling and Speed Optimization with Fuzzy Time Window[J]. Journal of Shanghai Jiao Tong University, 2021, 55(3): 297-310.

图/表 16

图1

图2

图3

图4

图5

图6

表1

表2

表3

表4

图7

表5

表6

表7

图8

表8

参考文献 30

[1]	JETLUND A S, KARIMI I A. Improving the logistics of multi-compartment chemical tankers[J]. Computers and Chemical Engineering, 2004, 28: 1267-1283.
[2]	FAGERHOLT K. Ship scheduling with soft time windows: An optimisation based approach[J]. European Journal of Operational Research, 2001, 131(3): 559-571.
[3]	BRONMO G, CHRISTIANSEN M, FAGERHOLT K, et al. A multi-start local search heuristic for ship scheduling—A computational study[J]. Computers & Operations Research, 2007(34): 900-917.
[4]	KORSVIK J E, FAGERHOLT K, LAPORTE G. A tabu search heuristic for ship routing and scheduling[J]. Journal of the Operational Research Society, 2010, 61(4): 594-603.
[5]	FAGERHOLT K, HVATTUM L, TROND A, et al. Routing and scheduling in project shipping[J]. Annals of Operations Research, 2013, 207(1): 67-81.
[6]	HEMMATI A, STALHANE M, HVATTUM L M. An effective heuristic for solving a combined cargo and inventory routing problem in tramp shipping. Computer Operation Research, 2015, 64: 274-282.
[7]	ARMAS J, LALLA E, CHRISTOPHER E, et al. A hybrid GRASP-VNS for ship routing and scheduling problem with discretized time windows[J]. Engineering Applications of Artificial Intelligence, 2015, 45: 350-360.
[8]	KORSVIK J E, FAGERHOLT K. A tabu search heuristic for ship routing and scheduling with flexible cargo quantities[J]. Journal of Heuristics, 2010, 16(2): 117-137.
[9]	BRØNMO G, NYGREEN B, LYSGAARD J. Column generation approaches to ship scheduling with flexible cargo sizes[J]. European Journal of Operational Research, 2010, 8: 139-150.
[10]	MENG Q, WANG S A, CHUNG-YEE L. A tailored branch-and-price approach for a joint tramp ship routing and bunkering problem[J]. Transportation Research Part B, 2015, 72: 1-19.
[11]	LIN D Y, LIU H Y. Combined ship allocation, routing and freight assignment in tramp shipping[J]. Transportation Research Part E, 2011, 47: 414-431.
[12]	YU B, PENG Z X, TIAN Z H, et al. Sailing speed optimization for tramp ships with fuzzy time window[J]. Flexible Services and Manufacturing Journal, 2019, 31: 308-330.
[13]	THAI V, TAY W, TAN R, et al. Defining service quality in tramp shipping: Conceptual model and empirical evidence[J]. The Asian Journal of Shipping and Logistics, 2014, 30(1): 1-9.
[14]	LEE C Y, LEE H L, ZHANG J. The impact of slow ocean steaming on delivery reliability and fuel consumption[J]. Transportation Research Part E, 2015, 76: 176-190.
[15]	MAILLIDIS I, IAKOVOU EDEKKER R, et al. The impact of slow steaming on the carriers’ and shippers’ costs: The case of a global logistics network[J]. Transportation Research Part E, 2018, 111: 18-39.
[16]	NORSTAD I, FAGERHOLT K, LAPORTE G. Tramp ship routing and scheduling with speed optimization[J]. Transportation Research Part C, 2011, 19: 853-865.
[17]	HVATTUM L M, NORSTAD I, FAGERHOLT K, et al. Analysis of an exact algorithm for the vessel speed optimization problem[J]. Networks, 2013, 62 (2): 132-135.
[18]	HARILAOS, PSARAFTIS, CHRISTOS. Ship speed optimization: Concepts, models and combined speed-routing scenarios[J]. Transportation Research Part C, 2014, 44: 52-69.
[19]	FAGERHOLT K, LAPORTE G, NORSTAD I. Reducing fuel emissions by optimizing speed on shipping routes[J]. Journal of the Operational Research Society, 2010, 61: 523-529.
[20]	唐磊，谢新连. 带时间窗约束的不定期船航速优化模型[J].物流技术，2014, 33(03): 132-135.
	TANG Lei, XIE Xinlian. Study on irregular vessel velocity optimization model with time window constraint[J]. Logistics Technology, 2014, 33(03): 132-135.
[21]	殷翔宇，张俊，谢新连. 不定期船最佳航速优化研究[J].中国航海，2012, 35(01): 94-97+118.
	YIN Xiangyu, ZHANG Jun, XIE Xinlian. Research on the optimal speed of tramp vessels[J]. Navigation of China, 2012, 35(01): 94-97+118.
[22]	李铮，潘晓萌. 船舶航速优化算法研究[J].舰船科学技术，2016, 38(12): 7-9.
	LI Zheng, PAN Xiaomeng. Research on optimization algorithm of ship speed[J]. Ship Science and Technology, 2016, 38(12): 7-9.
[23]	WEN M, PACINO D, KONTOVAS, et al. A multiple ship routing and speed optimization problem under time, cost and environmental objectives[J]. Transportation Research Part D, 2017, 52: 303-321.
[24]	WEN M, ROPKE S, PETERSEN H L, et al. Full-shipload tramp ship routing and scheduling with variable speeds[J]. Computers & Operations Research, 2016, 70: 1-8.
[25]	唐磊，谢新连，王成武. 基于集合划分的航速可变不定期船舶调度模型[J]. 上海交通大学学报，2013, 47(06): 909-915.
	TANG Lei, XIE Xinlian, WANG Chengwu. Model of tramp ship scheduling with variable speed based on set partition approach[J]. Journal of Shanghai Jiao Tong University, 2013, 47(06): 909-915.
[26]	俞超，王志华，高鹏. 考虑速遣费和滞期费的不定期船航速优化研究[J]. 交通运输系统工程与信息，2018, 18(03): 195-201.
	YU Chao, WANG Zhihua, GAO Peng. Speed optimization considering dispatch and demurrage of the tramp shipping[J]. Journal of Transportation Systems Engineering and Information Technology, 2018, 18(03): 195-201.
[27]	李晓君，谢新连. 重大件运输的货物分配与航速联合优化[J]. 西南交通大学学报，2015, 50(04): 747-754.
	LI Xiaojun, XIE Xinlian. Integrated optimization of cargo distribution and ship speed for heavy-cargo transportation[J]. Journal of Southwest Jiaotong University, 2015, 50(04): 747-754.
[28]	中华人民共和国国家质量监督检验检疫总局，中国国家标准化管理委员会．GB/T 7187.1-2010: 运输船舶燃油消耗量．第 1 部分：海洋船舶计算方法[S]．北京：中国标准出版社，2011.
	General Administration of Quality Supervision, Inspection and Quarantine of the People’s Republic of China, Standardization Administration of China.GB/T 7187.1-2010: Fuel oil consumption for transportation ships. Part 1: Calculation method for marine ships [S]. Beijing: China Standard Press, 2011.
[29]	HEMMATI A, HVATTUM L M, NORSTAD I, et al. Benchmark suite for industrial and tramp ship routing and scheduling problems[J]. Information Systems and Operational Research, 2014, 52(01): 28-38.
[30]	中华人民共和国交通部港口收费规则(外贸部分)(修正)．中华人民共和国交通部令第11号[S]．北京：交通运输部，2001.
	Rules of the Ministry of Transport of the People’s Republic of China on Port Charges (Foreign Trade section) (Amendment). Order of the Ministry of Transport of the People’s Republic of China No.11 [S]. Beijing: Ministry of Transport, 2001.

编号	最大载重量/t	初始位置	压载速度/kn		满载速度/kn		已航行时间/h
编号	最大载重量/t	初始位置	下限	上限	下限	上限	已航行时间/h
1	13 200	HAMBURG	11	16	11	15.5	80
2	16 500	MONTOIR DE BRETAGNE	12	17	12	16.5	116
3	24 000	VIGO	10	15	10	14.5	0
4	33 200	DUNKIRK	11.5	15.5	11.5	15	34
5	5 800	LA PALLICE	11.5	16	11.5	15.5	0
6	2 950	LA PALLICE	11	15.5	11	15	0
7	3 570	KLAIPEDA	11	15	11	14.5	0

编号	与货物不相适船舶	装货港	卸货港	装货港时间窗/h		卸货港时间窗/h		租船运输成本/美元
编号	与货物不相适船舶	装货港	卸货港	下限	上限	下限	上限	租船运输成本/美元
1	—	GDANSK	RAVENNA	364	436	364	1 017	464 619
2	—	CADIZ	VADO LIGURE	1 096	1 168	1 096	1 592	527 063
3	—	GDANSK	KLAIPEDA	891	963	891	1 292	345 828
4	—	ANTWERP	BRAKE	106	178	106	567	657 530
5	—	ANCONA	CADIZ	258	330	258	784	584 277
6	2，3	ALGECIRAS	ANCONA	72	144	72	572	416 260
7	—	TILBURY	ANTWERP	639	711	639	1 002	679 111
8	—	DUNKIRK	THISVI	1 454	1 526	1 454	2 060	938 250
9	—	VIGO	VADO LIGURE	852	924	852	1 344	552 843
10	—	TALLINN	MO I RANA	1 068	1 140	1 068	1 578	382 307
11	—	ZEEBRUGGE	LIVERPOOL	604	676	604	1 077	223 256
12	—	SINES	MO I RANA	535	607	535	1 038	513 859
13	—	GENOA	GDANSK	490	562	490	1 092	348 556
14	—	BILBAO	LA SPEZIA	932	1 004	932	1 446	299 760
15	2，3，4，5，6，7	GDANSK	TEESPORT	0	72	0	422	664 773
16	—	TEESPORT	HAMBURG	193	265	193	639	179 337
17	2，3	HUELVA	VADO LIGURE	52	124	52	574	653 627
18	—	HUELVA	THISVI	310	382	310	841	294 556
19	2，3，5	VIGO	THISVI	18	90	18	549	680 437
20	—	LAS PALMAS	MO I RANA	996	1 068	996	1 583	304 174
21	2，3，4，5，6，7	GDANSK	THISVI	0	72	0	637	998 137
22	—	CADIZ	KLAIPEDA	1 155	1 227	1 155	1 694	724 428
23	—	VLISSINGEN	DUNKIRK	386	458	386	780	179 492
24	—	CARTAGENA	VADO LIGURE	420	492	420	863	200 682
25	—	GDANSK	ROTTERDAM	322	394	322	834	512 956
26	—	GDANSK	ANCONA	880	952	880	1 496	584 238
27	—	ALGECIRAS	VADO LIGURE	391	463	391	839	256 818
28	—	ORESUND	LISBON	678	750	678	1 196	780 380
29	—	HUELVA	LA SPEZIA	892	964	892	1 369	606 120
30	—	MO I RANA	SINES	520	592	520	1 091	609 947

编号	装货港	卸货港	装货港时间窗/h		卸货港时间窗/h		租船运输成本/美元
编号	装货港	卸货港	下限	上限	下限	上限	租船运输成本/美元
1	SINES	MONTOIR DE BRETAGNE	289	361	289	722	316 519
2	TALLINN	ANTWERP	0	100	0	459	390 143
3	ZEEBRUGGE	CARTAGENA	36	108	36	527	414 361

算例	η_best	GA		VNGSA
算例	η_best	Z	ε/%	Z	ε/%
C8_V3_1	1 391 997	1 391 997	0.00	1 391 997	0.00
C8_V3_2	1 246 273	1 246 273	0.00	1 246 273	0.00
C8_V3_3	1 698 102	1 698 102	0.00	1 698 102	0.00
C8_V3_4	1 777 637	1 777 637	0.00	1 777 637	0.00
C8_V3_5	1 636 788	1 636 788	0.00	1 636 788	0.00
C16_V6_1	3 577 005	3 642 887	1.84	3 577 005	0.00
C16_V6_2	3 560 203	3 560 203	0.00	3 560 203	0.00
C16_V6_3	4 081 013	4 081 013	0.00	4 081 013	0.00
C16_V6_4	3 667 080	3 718 542	1.40	3 667 080	0.00
C16_V6_5	3 438 493	3 476 347	1.10	3 438 493	0.00
C35_V13_1	2 986 667	3 531 066	18.23	3 252 532	8.90
C35_V13_2	3 002 974	3 147 092	4.80	3 002 974	0.00
C35_V13_3	3 084 339	3 226 146	4.60	3 149 614	2.12
C35_V13_4	3 952 461	4 202 921	6.34	4 093 356	3.56
C35_V13_5	3 293 086	3 507 983	6.53	3 370 315	2.35
ε_ave	—	—	2.99	—	1.13

船号	船舶运输货物编号	航段采用速度/kn
1	21-13	[13.4，11.3]，[13.1，11.6]
2	4-1-9	[16.5，15.0]，[15.8，15.9]，[12.6，12.5]
3	16-24-29-2	[12.7，11.5]，[11.2，12.4]，[14.4，10.4], [11.7，10.6]
4	19-5-12-10	[14.7，12.6]，[15.3，14.1]，[15.4，11.9]，[13.0，13.9]
5	25-23-30-3-26	[13.6，11.6]，[15.3，12.4]，[12.8，13.4]，[12.3，13.8]，[15.1，13.3]
6	6-28-20-8	[12.2，11.3]，[14.9，13.0]，[13.7，11.3]，[14.9，12.0]
7	17-27-7-11-14-22	[13.3，13.3]，[12.3，14.4]，[11.2，13.6]，[13.5，11.5]，[12.5，12.6], [12.4，11.3]
租船	15-18	—
总成本/美元		4 735 125