Optimization model of electric coal ship scheduling under considering ship storage and port congestion
-
摘要: 针对中国电煤水运系统的实际特点, 综合考虑了船舶封存与港口拥堵(压港)因素, 建立了混合整数规划优化模型, 对电煤船舶调度方案进行优化; 基于运输需求的硬时间窗、卸货港船舶排队等待时间与水路-铁路运输协同三因素之间的互动关系, 以运输系统总成本最小为目标, 协同优化水、铁电煤运输的货运分担率、水路运输任务指派和相应的船舶调度与封存/启用方案; 基于改进列生成算法, 提出了一种可精确求解实际规模电煤船舶调度问题的列生成算法, 利用Gurobi求解列生成的主模型, 使用动态规划标号法求解列生成的子模型; 利用中国南部某火力发电集团的实际数据, 对提出的算法进行了算例分析。计算结果表明: 在中等规模的算例中, 使用提出的改进算法获得最优解仅需73.61 s, 相比于使用基于运输任务运量排序的启发式求解方法(PHA), 求解效率提高了18.1%;在较大规模的算例中, 使用提出算法的计算时间仅为222.02 s, 同比PHA, 计算效率提高了19.1%;通过求解一个实际的调度问题可以发现, 利用提出的优化模型和算法能有效缩短船舶在卸货港的等待时长与船舶处于启用状态的时长, 使运输总成本下降17.13%, 实现了电煤稳定运输, 提升了企业运营效率, 降低了运营成本。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.
-
图 1 电煤装卸港口的空间分布与水运路径
Figure 1. Space distribution of loading and unloading ports and transportation paths for electric coal
图 2 水运航程时间变量的相互关系
Figure 2. Relationship among time variables in waterway transportation
表 1 集合、参数与变量
Table 1. Sets, parameters and variables
集合 I 水运航程集, 其元素记为i, 令和为虚拟节点) L 卸货港口集, 其元素记为l V 可用船舶集, 其元素记为v T 总观测期(单位: d)集, 其元素记为t, 表示观测期内的具体时刻(单位: d) P 单船可行方案集, 其元素记为p Q 船队可行调度方案, Q⊆P $\tilde{P}$ 拟生成新的可行单船调度方案构成的集合 $\tilde{I}$ 水运航程进行排序后形成的有序集, 其元素记为ik 参数 t 水运航程i的最早装货时刻 t 水运航程i的最晚装货时刻 t 水运航程i的最早卸货时刻 t 水运航程i的最晚卸货时刻 t 水运航程i的送货子航程的航行时间(单位: d) t 水运航程i的返航子航程的航行时间(单位: d) t 水运航程i的净装货时间(不包括因港口拥堵引起的延误时间, 单位: d) t 水运航程i的净卸货时间(不包括因港口拥堵引起的延误时间, 单位: d) t 船舶v在当前观测期内最早可以进行运营的时刻 wv 船舶v的舱容 di 水运航程i的运输量 nlb 港口l的泊位数量 cps 可行单船调度方案p的运营成本 cit 与水运航程i成互补关系的铁路陆程成本 cvr 观测期内因启用船舶v每日所需支付的运营成本 π 约束式(30)对应的影子价格 π 约束式(31)对应的影子价格 π 约束式(32)对应的影子价格 变量 tips 单船调度方案p中水运航程i的开始时刻 (tips) 向量, 表示单船调度方案p规定的开始作业时刻 t 单船调度方案p中水运航程i于装货港的等待时长 (t) 向量, 表示单船调度方案p规定的装货港等待时长 t 单船调度方案p中水运航程i于卸货港的等待时长 (t) 向量, 表示单船调度方案p规定的卸货港等待时长 uvp svp和xp线性化时的中间变量 mipt bipt和xp线性化时的中间变量 qip aip和xp线性化时的中间变量 指示变量 aip 若单船调度方案p需执行水运航程i则取1, 否则取0 (aip) 向量, 表示单船调度方案p下船舶执行了哪些水运航程 $\widetilde{a}_{i p v}$ 方案p是否使用了船舶v执行水运航程i, 是则取1, 否则取0 bipt t时刻(第t天)船舶是否在执行水运航程i且处于卸货状态, 是则取1, 否则取0 svp 若单船调度方案p由船舶v执行则取1, 否则取0 (svp) 向量, 表示单船调度方案p由那艘船舶执行 $\widetilde{X}_{i j p}$ 单船调度方案p下船舶是否依次执行了水运航程i与j, 是则取1, 否则取0 xp 是否选择可行单船调度方案p, 是为1, 否则取0 δil 港口l是否为水运航程i所靠泊的卸货港, 是则取1, 否则取0 γi 与水运航程i成互补关系的铁路陆程是否被使用, 使用取1, 否则取0 
下载: 导出CSV
表 2 各类船舶的详细参数
Table 2. Detailed parameters of various ships
ID 船名 最早可用时刻(第x天) 最早可退租时间/d 载重量/t 日成本/元 0 粤电1 9 40 6.9 2 771 1 粤电3 14 40 6.7 2 713 2 粤电4 0 40 7.0 2 799 3 粤电6 19 30 7.5 2 943 4 粤电7 10 40 7.5 2 943 5 粤电51 6 40 5.7 2 426 6 粤电54 17 40 5.7 2 426 7 粤电56 25 40 5.8 2 454 8 粤电57 15 30 5.8 2 454 9 粤电59 25 40 5.8 2 454 10 粤电103 34 50 8.7 3 288 11 新广州 1 30 6.5 2 656 12 新靖海 3 30 6.9 2 771 13 新宁江 5 40 4.7 2 138 14 毓骐海 3 30 6.4 2 627 15 毓麟海 9 30 7.5 2 943 16 广珠 7 40 8.8 3 317 17 广粤 10 40 6.9 2 771 18 广前 16 30 7.5 2 943 19 太行6 11 40 6.7 2 713 20 粤电52 38 0 5.7 2 426 21 粤电53 35 0 5.7 2 426 22 粤电58 21 0 5.6 2 397 23 粤电101 3 0 8.6 3 259 24 粤电102 17 0 8.6 3 259 25 新达江 25 0 4.2 1 995 26 广中 48 0 6.6 2 684 27 恩曜 9 0 2.2 1 391 28 拓展1 14 0 2.0 1 333 29 拓展2 44 0 2.0 1 305
下载: 导出CSV
表 3 效能分析结果对比
Table 3. Comparison of performance analysis results
测试方案 算法 ECSSA ESPA PHA SEC-ES/% SEC-PH/% TSM/s TMM/s TCG/s TEN/s TEGU/s TEG/s TPG/s P2S3T5D30 0.05 0.008 0.06 0.09 0.60 0.70 0.11 0 -2.8 P4S7T11D30 0.26 0.030 0.29 1.12 8.21 9.33 0.19 0 -6.2 P6S9T16D30 4.61 2.930 7.54 42.41 O 0.29 -9.6 P8S13T21D30 38.43 19.910 58.34 1 531.03 O 0.43 -13.2 P11S16T30D30 135.60 31.510 167.11 1.21 -10.8 P2S3T5D40 0.03 0.005 0.04 0.61 1.67 2.28 0.11 0 -14.2 P4S7T11D40 1.94 1.080 3.02 11.14 O 0.18 -11.6 P6S9T16D40 5.38 2.120 7.40 61.72 O 0.29 -16.7 P9S13T21D40 52.23 21.380 73.61 2 134.08 O 0.41 -18.1 P11S17T30D40 183.21 38.810 222.02 1.40 -19.1
下载: 导出CSV
表 4 优化方案与实际方案关键参数对比
Table 4. Comparison of key parameters between optimization scheme and actual scheme
船舶类型 OPR RPR E/% N/艘 GRT/d GWT/d R1 A/t R2 N/艘 GRT/d GWT/d R1 A/t R2 小型(载重小于2万吨) 3 61 16 0.24 1.82 0.91 3 63 18 0.29 1.83 0.92 -17.13 中型(载重2万~6万吨) 10 302 38 0.13 5.29 0.89 10 321 45 0.14 5.30 0.88 大型(载重6万~9万吨) 17 747 13 0.07 6.96 0.78 17 834 200 0.24 7.14 0.79
下载: 导出CSV
-
[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. doi: 10.1007/s40565-016-0199-2 [2] 陈洁, 吕靖, 梁晶. 沿海电煤运输管理决策支持系统的设计与实现[J]. 煤炭技术, 2011, 30(12): 265-266. https://www.cnki.com.cn/Article/CJFDTOTAL-MTJS201112130.htmCHEN 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). https://www.cnki.com.cn/Article/CJFDTOTAL-MTJS201112130.htm [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. doi: 10.1016/j.ejor.2012.12.002 [4] RONEN D. Cargo ships routing and scheduling: survey of models and problems[J]. European Journal of Operational Research, 1983, 12(2): 119-126. doi: 10.1016/0377-2217(83)90215-1 [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. doi: 10.1080/03088838700000014 [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. doi: 10.1287/trsc.1030.0036 [8] 陈相东. 多种运输方式的组合优化模型及其求解[J]. 天津理工大学学报, 2008, 24(4): 50-53. doi: 10.3969/j.issn.1673-095X.2008.04.014CHEN 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). doi: 10.3969/j.issn.1673-095X.2008.04.014 [9] BROWN G G, GRAVES G W, RONEN D. Scheduling ocean transportation of crude oil[J]. Management Science, 1987, 33(3): 335-346. doi: 10.1287/mnsc.33.3.335 [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. doi: 10.1080/03088839800000057 [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. doi: 10.1080/751248659 [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. https://www.cnki.com.cn/Article/CJFDTOTAL-DLHS200902010.htmLI 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). https://www.cnki.com.cn/Article/CJFDTOTAL-DLHS200902010.htm [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. doi: 10.1016/j.cor.2005.05.017 [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. doi: 10.1007/s13160-010-0008-7 [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. doi: 10.1007/s10479-011-0888-1 [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. doi: 10.1007/s10732-008-9092-0 [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. doi: 10.1016/j.trc.2010.05.001 [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. doi: 10.1016/j.ejor.2016.01.060 [20] 寿涌毅, 赖昌涛, 吕如福. 班轮船舶调度多目标优化模型与蚁群算法[J]. 交通运输工程学报, 2011, 11(4): 84-88. http://transport.chd.edu.cn/article/id/201104013SHOU 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). http://transport.chd.edu.cn/article/id/201104013 [21] 刘志军. 西南煤炭南下运输方案模糊评价方法研究[J]. 铁道运输与经济, 2010, 32(3): 91-94. https://www.cnki.com.cn/Article/CJFDTOTAL-TDYS201003031.htmLIU 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). https://www.cnki.com.cn/Article/CJFDTOTAL-TDYS201003031.htm [22] 董明望, 郑斐城. 基于WebServices的件杂货装卸效率优化系统研究[J]. 商品储运与养护, 2008, 30(8): 41-42. https://www.cnki.com.cn/Article/CJFDTOTAL-SPCY200808021.htmDONG 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). https://www.cnki.com.cn/Article/CJFDTOTAL-SPCY200808021.htm [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. doi: 10.1287/trsc.2013.0461 [24] 陈超, 张哲, 曾庆成. 集装箱码头混合交叉作业集成调度模型[J]. 交通运输工程学报, 2012, 12(3): 92-100. http://transport.chd.edu.cn/article/id/201203013CHEN 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). http://transport.chd.edu.cn/article/id/201203013 [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. http://transport.chd.edu.cn/article/id/200701006XIAO 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). http://transport.chd.edu.cn/article/id/200701006 [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. -
点击查看大图
图(4) / 表(4)
计量
- 文章访问数: 816
- HTML全文浏览量: 132
- PDF下载量: 548
- 被引次数: 0
