|Table of Contents|

Optimization model of electric coal ship scheduling under considering ship storage and port congestion(PDF)

《交通运输工程学报》[ISSN:1671-1637/CN:61-1369/U]

Issue:
2020年03期
Page:
178-191
Research Field:
交通运输规划与管理
Publishing date:

Info

Title:
Optimization model of electric coal ship scheduling under considering ship storage and port congestion
Author(s):
CHEN Kang1;  ZHAO Zi-zhou2;  WU Ming-hao2;  XIN Xu3;  CHEN Zi-gen2
(1. School of Maritime Economics and Management, Dalian Maritime University, Dalian 116026, Liaoning, China; 2. School of Transportation Engineering, Dalian Maritime University, Dalian 116026, Liaoning, China; 3. School of Economics and Management, Tongji University, Shanghai 200092, China)
Keywords:
transportation planning;  electric coal transportation;  ship scheduling;  ship storage;  column generation;  port congestion
PACS:
U692.4
DOI:
10.19818/j.cnki.1671-1637.2020.03.017
Abstract:
In view of the actual characteristics of Chinese electric coal water transportation system, the factors of ship storage and port congestion were comprehensively considered, and a mixed integer programming optimization model was established to optimize the scheduling scheme of electric coal ships. Based on the interactive relationship among hard time window of transportation demand, waiting time of ship in unloading port and waterway-railway transportation collaboration, the minimum total cost of the transportation system was taken as objective to collaboratively optimize the freight sharing rates of waterway-railway transportation of electric coal and the task assignment, ship scheduling and storage/commissioning scheme in waterway transportation. Based on the improved column generation algorithm, a column generation algorithm was proposed to accurately solve the actual ship scheduling problem of electric coal transportation. The Gurobi was used to solve the master model generated by the column, and the dynamic programming labeling algorithm was used to solve the sub-model generated by the column. Based on the actual data of a thermal power group in Southern China, an example aimed at the proposed algorithm was analyzed. Calculation result shows that when the proposed algorithm is used to solve the middle-scale example, it takes only 73.61 s to obtain the optimal solution. Compared with the heuristic solution method based on the sequencing of traffic volume in transportation task(PHA), the solution efficiency improves by 18.1%. In a larger-scale example, the calculation time of the proposed algorithm is only 222.02 s, and the computational efficiency increases 19.1% compared with the PHA. In solving an actual scheduling problem, it is found that the proposed optimization model and algorithm can effectively shorten the waiting time of the ship at the unloading port and the active state time of the ship, and reduce the total cost of transportation by 17.13%. Therefore, they can achieve stable transportation of electric coal, improve the operating efficiency of enterprise, and reduce operating cost. 4 tabs, 4 figs, 30 refs.

References:

[1] TAN Zhong-fu, CHEN Kang-ting, JU Li-wei, et al. Issues and solutions of China's generation resource utilization based on sustainable development[J]. Journal of Modern Power Systems and Clean Energy, 2016, 4(2): 147-160.
[2] 陈 洁,吕 靖,梁 晶.沿海电煤运输管理决策支持系统的设计与实现[J].煤炭技术,2011,30(12):265-266.
CHEN Jie, LYU Jing, LIANG Jing. Design and implementation of coastal thermal coal transportation management and decision support system[J]. Coal Technology, 2011, 30(12): 265-266.(in Chinese)
[3] CHRISTIANSEN M, FAGERHOLT K, NYGREEN B, et al. Ship routing and scheduling in the new millennium[J]. European Journal of Operational Research, 2013, 228(3): 467-483.
[4] RONEN D. Cargo ships routing and scheduling: survey of
models and problems[J]. European Journal of Operational Research, 1983, 12(2): 119-126.
[5] LANE D E, HEAVER T D, UYENO D. Planning and
scheduling for efficiency in liner shipping[J]. Maritime Policy and Management, 1987,14(2): 109-125.
[6] RONEN D. Ship scheduling: the last decade[J]. European
Journal of Operational Research, 2007, 71(3): 325-333.
[7] CHRISTIANSEN M, FAGERHOLT K, RONEN D. Ship
routing and scheduling: status and perspectives[J]. Transportation Science, 2004, 38(1): 1-18.
[8] 陈相东.多种运输方式的组合优化模型及其求解[J].天津理工大学学报,2008,24(4):50-53.
CHEN Xiang-dong. Combinatorial optimization model of multiple transportation and its algorithm[J]. Journal of Tianjin University of Technology, 2008, 24(4): 50-53.(in Chinese)
[9] BROWN G G, GRAVES G W, RONEN D. Scheduling ocean transportation of crude oil[J]. Management Science, 1987, 33(3): 335-346.
[10] BAUSCH D O, BROWN G G, RONEN D. Scheduling short-term marine transport of bulk products[J]. Maritime Policy and Management, 1998, 25(4): 335-348.
[11] 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.
[12] CHRISTIANSEN M, FAGERHOLT K. Robust ship scheduling with multiple time windows[J]. Naval Research Logistics, 2010, 49(6): 611-625.
[13] 李华文,吕 靖.电煤海运准时送达的可靠性研究[J].大连海事大学学报,2009,35(2):38-42.
LI Hua-wen, LYU Jing. Reliability study of seaborne transportation of coal on time for power plants[J]. Journal of Dalian Maritime University, 2009, 35(2): 38-42.(in Chinese)
[14] 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(3): 900-917.
[15] KOBAYASHI K, KUBO M. Optimization of oil tanker
schedules by decomposition, column generation, and time-space network techniques[J]. Japan Journal of Industrial and Applied Mathematics, 2010, 27(1): 161-173.
[16] FAGERHOLT K, HVATTUM L M, JOHNSEN T A V, et al. Routing and scheduling in project shipping[J]. Annals of Operations Research, 2013, 207: 67-81.
[17] 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.
[18] 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.
[19] HEMMATI A, HVATTUM L M, CHRISTIANSEN M, et al. An iterative two-phase hybrid matheuristic for a multi-product short sea inventory-routing problem[J]. European Journal of Operational Research, 2016, 252(3): 775-788.
[20] 寿涌毅,赖昌涛,吕如福.班轮船舶调度多目标优化模型与蚁群算法[J].交通运输工程学报,2011,11(4):84-88.
SHOU Yong-yi, LAI Chang-tao, LYU Ru-fu. Multi-objective optimization model and ant colony algorithm of liner ship scheduling [J]. Journal of Traffic and Transportation Engineering, 2011, 11(4): 84-88.(in Chinese)
[21] 刘志军.西南煤炭南下运输方案模糊评价方法研究[J].铁道运输与经济,2010,32(3):91-94.
LIU Zhi-jun. Research on fuzzy evaluation method of coal transport scheme from southwest China to south China[J]. Railway Transport and Economy, 2010, 32(3): 91-94.(in Chinese)
[22] 董明望,郑斐城.基于WebServices的件杂货装卸效率优化系统研究[J].商品储运与养护,2008,30(8):41-42.
DONG Ming-wang, ZHENG Fei-cheng. The efficiency optimization system research of loading and unloading in break bulk based on web services[J]. Storage Transportation and Preservation of Commodities, 2008, 30(8): 41-42.(in Chinese)
[23] MENG Qiang, WANG Shuai-an, ANDERSSON H, et al. Containership routing and scheduling in liner shipping: overview and future research directions[J]. Transportation Science, 2014, 48(2): 265-280.
[24] 陈 超,张 哲,曾庆成.集装箱码头混合交叉作业集成调度模型[J].交通运输工程学报,2012,12(3):92-100.
CHEN Chao, ZHANG Zhe, ZENG Qing-cheng. Integrated scheduling model of mixed cross-operation for container terminal[J]. Journal of Transportation Engineering, 2012, 12(3): 92-100.(in Chinese)
[25] GANSTERER M, KÜÇÜKTEPE M, HARTL R F. The
multi-vehicle profitable pickup and delivery problem[J]. OR Spectrum, 2016, DOI: 10.1007/s00291-016-0454-y.
[26] CUESTA E F, ANDERSSON H, FAGERHOLT K, et al. Vessel routing with pickups and deliveries: an application to the supply of offshore oil platforms[J]. Computers and Operations Research, 2016, DOI: 10.1016/j.cor.2016.10.014.
[27] SOPOT E, GRIBKOVSKAIA I. Routing of supply vessels to with deliveries and pickups of multiple commodities[J]. Procedia Computer Science, 2014, 31: 910-917.
[28] 肖恒辉,齐 欢,王小平,等.船舶调度闸外编排算法[J].交通运输工程学报,2007,7(1):26-29.
XIAO Heng-hui, QI Huan, WANG Xiao-ping,et al. Arrangement algorithm outside the ship lock during ship scheduling[J]. Journal of Traffic and Transportation Engineering, 2007, 17(1): 26-29.(in Chinese)
[29] FORD L R, FULKERSON D R. A suggested computation for maximal multi-commodity network flows[J]. Management Science, 1958, 50(12): 1778-1780.
[30] AGARWAL R, ERGUN O. Ship scheduling and network
design for cargo routing in liner shipping[J]. Transportation Science, 2008, 42(2): 175-196.

Memo

Memo:
-
Last Update: 2020-07-10