最小化集装箱运输成本的配载优化

doi:10.11896/j.issn.1002-137X.2019.06.036

摘要/Abstract

摘要： 随着长江沿岸港口集装箱运输的快速发展,配载计划的制定已成为制约集装箱运输发展的一个主要因素。以航行中最小化的翻箱费用和堆栈使用费用为优化目标,在船舶安全航行的前提下,以船舶装载稳定性作为约束条件建立混合整数规划模型。通过CPLEX、遗传算法和贪婪算法对长江沿岸中小型集装箱船舶配载进行实验对比分析,结果证明了所提模型的有效性。同时,应用两种算法对大规模集装箱配载情形进行对比求解,通过仿真实验证明了遗传算法的高效性,与实际运输经验操作相比,其将运输成本平均降低了24.73%。这说明本文所提出的模型对于降低航线运输成本和制定长江沿岸港口配载计划具有一定的指导意义。

关键词: 多港口, 混合整数规划, 配载优划, 贪婪算法, 遗传算法

Abstract: With the rapid development of container transportation along the Yangtze River,the stowage planning has become an important issue in the development of container transportation.Aiming at the minimum shifting cost and stack usage cost during the voyage,this paper established a mixed integer programming model that considers the ship safety and loading stability constraints.Then CPLEX,genetic algorithm and greedy algorithm were designed to analyze the stowage planning of small and medium sized container ships along the Yangtze River,and the validity of the proposed model was proved.Besides,the two proposed algorithms were applied to solve the large-scale container loading problem,and both of them can quickly get reasonable solutions.Compared with the industry experience,the experiments prove that the proposed model can reduce 24.73% on average for the transportation cost of the route and is of certain guiding significance to the container transportation along the Yangtze River.

Key words: Genetic algorithm, Greedy algorithm, Mixed integer programming, Multiple ports, Stowage optimization

中图分类号:

TP391.9

郑斐峰, 蒋娟, 梅启煌. 最小化集装箱运输成本的配载优化[J]. 计算机科学, 2019, 46(6): 239-245. https://doi.org/10.11896/j.issn.1002-137X.2019.06.036

ZHENG Fei-feng, JIANG Juan, MEI Qi-huang. Study on Stowage Optimization in Minimum Container Transportation Cost[J]. Computer Science, 2019, 46(6): 239-245. https://doi.org/10.11896/j.issn.1002-137X.2019.06.036

参考文献

[1]BAI Q H.The new ecology of international shipping:co-buil-ding,sharing and symbiosis－2016 International Maritime Conference Annual Review[J].Zhong Guo Shui Yun,2016,37(11):8-9.(in Chinese)
白庆虹.国际航运新生态:共建、共享、共生 ——2016国际海运年会观点扫描[J].中国水运,2016,37(11):8-9.
[2]PARRENO F,PACINO D,ALVAREZ-VALDES R.A GRASP algorithm for the container stowage slot planning problem[J].Transportation Research Part E Logistics & Transportation Review,2016,94:141-157.
[3]AVRIEL M,PENN M,SHPIRER N,et al.Stowage planning for container ships to reduce the number of shifts[J].Annals ofOpe-rations Research,1998,76:55-71.
[4]DING D,CHOU M C.Stowage planning for container ships:a heuristic algorithm to reduce the number of shifts [J].European Journal of Operational Research,2015,246(1):242-249.
[5]ZHANG W Y,LIN Y,JI Z S.A Model of Bay Layout for Containership Based on the Least Shifting[J].Journal of Shanghai Jiaotong University,2007,41(2):199-204.(in Chinese)
张维英,林焰,纪卓尚.集装箱船全航线Bay位排箱优化模型[J].上海交通大学学报,2007,41(2):199-204.
[6]IMAI A,SASAKI K,NISHIMURA E,et al.Multi-objective simultaneous stowage and load planning for a container ship with container rehandle in yard stacks[J].European Journal of Operational Research,2006,171(2):373-389.
[7]DELGADO A,JENSEN R M,JANSTRUP K,et al.A Con-straint Programming model for fast optimal stowage of containervessel bays[J].European Journal of Operational Research,2012,220(1):251-261.
[8]TIERNEY K,PACINO D,JENSEN R M.On the complexity of container stowage planning problems[J].Discrete Applied Mathematics,2014,169(2):225-230.
[9]AVRIEL M,PENN M,SHPIRER N.Container ship stowage problem:complexity and connection to the coloring of circle graphs[J].Discrete Applied Mathematics,2000,103(1-3):271-279.
[10]MONACO M F,SAMMARRA M,SORRENTINO G.The terminal-oriented ship stowage planning problem [J].European Journal of Operational Research,2014,239(1):256-265.
[11]AMBROSINO D,SCIOMACHEN A,TANFANI E.A decomposition heuristics for the container ship stowage problem[J].Journal of Heuristics,2006,12(3):211-233.
[12]AMBROSINO D,PAOLUCCI M,SCIOMACHEN A.Computational evaluation of a MIP model for multi-port stowage planning problems[J].Soft Computing,2015,21(7):1753-1763.
[13]PRESTON P,KOZAN E.An approach to determine storage locations of containers at seaport terminals [J].Computers & Ope-rations Research,2001,28(10):983-995.
[14]WILSON I D,ROACH P A.Container Stowage Planning:A Methodology for Generating Computerised Solutions[J].Journal of the Operational Research Society,2000,51(11):1248-1255.
[15]DING Z Y,JO G S,WANG Y,et al.The Relative Efficiency of Container Terminals in Small and Medium-Sized Ports in China[J].Asian Journal of Shipping & Logistics,2015,31(2):231-251.
[16]CHU X J.On Stowage Planning for Mult-port Container Transportation Based on Stability Constraint[J].LogisticsEnginee-ring and Management,2014,36(11):83-84.(in Chinese)
褚晓津.船舶稳定性的多港口集装箱配载问题[J].物流工程与管理,2014,36(11):83-84.
[17]DUAN C H,GUO X.A Stowage Planning Model for Single Bay and Multi-port Based on Integer Programming[J].Computer Aided Engineering,2004,13(3):9-13.(in Chinese)
段成华,郭旭.基于整数规划的单贝多港(SBMP)配载模型研究[J].计算机辅助工程,2004,13(3):9-13.
[18]YANG P,CHAI X Y,SUN J Q.Research on problem of yard crane cooperative schedule[J].Computer Engineering and Applications,2011,47(1):231-233.(in Chinese)
杨鹏,柴小燕,孙俊清.集装箱码头场桥协同调度研究[J].计算机工程与应用,2011,47(1):231-233.
[19]LIANG J,WU Y.Simultaneous berth and quay crane scheduling under uncertainty environments in container terminals[J].Computer Engineering and Applications,2017,53(7):212-219.(in Chinese)
梁承姬,吴宇.不确定环境下集装箱码头泊位与岸桥联合调度[J].计算机工程与应用,2017,53(7):212-219.
[20]AMBROSINO D,SCIOMACHEN A,TAFANI E.Stowing a containership:the master bay plan problem[J].Transportation Research Part A Policy & Practice,2004,38(2):81-99.

相关文章 15

[1]	杨浩雄, 高晶, 邵恩露. 考虑一单多品的外卖订单配送时间的带时间窗的车辆路径问题 Vehicle Routing Problem with Time Window of Takeaway Food ConsideringOne-order-multi-product Order Delivery 计算机科学, 2022, 49(6A): 191-198. https://doi.org/10.11896/jsjkx.210400005
[2]	沈彪, 沈立炜, 李弋. 空间众包任务的路径动态调度方法 Dynamic Task Scheduling Method for Space Crowdsourcing 计算机科学, 2022, 49(2): 231-240. https://doi.org/10.11896/jsjkx.210400249
[3]	吴善杰, 王新. 基于AGA-DBSCAN优化的RBF神经网络构造煤厚度预测方法 Prediction of Tectonic Coal Thickness Based on AGA-DBSCAN Optimized RBF Neural Networks 计算机科学, 2021, 48(7): 308-315. https://doi.org/10.11896/jsjkx.200800110
[4]	王金恒, 单志龙, 谭汉松, 王煜林. 基于遗传优化PNN神经网络的网络安全态势评估 Network Security Situation Assessment Based on Genetic Optimized PNN Neural Network 计算机科学, 2021, 48(6): 338-342. https://doi.org/10.11896/jsjkx.201200239
[5]	郑增乾, 王锟, 赵涛, 蒋维, 孟利民. 带宽和时延受限的流媒体服务器集群负载均衡机制 Load Balancing Mechanism for Bandwidth and Time-delay Constrained Streaming Media Server Cluster 计算机科学, 2021, 48(6): 261-267. https://doi.org/10.11896/jsjkx.200400131
[6]	左剑凯, 吴杰宏, 陈嘉彤, 刘泽源, 李忠智. 异构无人机编队防御及评估策略研究 Study on Heterogeneous UAV Formation Defense and Evaluation Strategy 计算机科学, 2021, 48(2): 55-63. https://doi.org/10.11896/jsjkx.191100053
[7]	姚泽玮, 林嘉雯, 胡俊钦, 陈星. 基于PSO-GA的多边缘负载均衡方法 PSO-GA Based Approach to Multi-edge Load Balancing 计算机科学, 2021, 48(11A): 456-463. https://doi.org/10.11896/jsjkx.210100191
[8]	高帅, 夏良斌, 盛亮, 杜宏亮, 袁媛, 韩和同. 基于投影圆度和遗传算法的空间圆柱面拟合方法 Spatial Cylinder Fitting Based on Projection Roundness and Genetic Algorithm 计算机科学, 2021, 48(11A): 166-169. https://doi.org/10.11896/jsjkx.201100057
[9]	高基旭, 王珺. 一种基于遗传算法的多边缘协同计算卸载方案 Multi-edge Collaborative Computing Unloading Scheme Based on Genetic Algorithm 计算机科学, 2021, 48(1): 72-80. https://doi.org/10.11896/jsjkx.200800088
[10]	吉顺慧, 张鹏程. 基于支配关系的数据流测试用例生成方法 Test Case Generation Approach for Data Flow Based on Dominance Relations 计算机科学, 2020, 47(9): 40-46. https://doi.org/10.11896/jsjkx.200700021
[11]	董明刚, 黄宇扬, 敬超. 基于遗传实例和特征选择的K近邻训练集优化方法 K-Nearest Neighbor Classification Training Set Optimization Method Based on Genetic Instance and Feature Selection 计算机科学, 2020, 47(8): 178-184. https://doi.org/10.11896/jsjkx.190700089
[12]	梁正友, 何景琳, 孙宇. 一种用于微表情自动识别的三维卷积神经网络进化方法 Three-dimensional Convolutional Neural Network Evolution Method for Facial Micro-expression Auto-recognition 计算机科学, 2020, 47(8): 227-232. https://doi.org/10.11896/jsjkx.190700009
[13]	杨德成, 李凤岐, 王祎, 王胜法, 殷慧殊. 智能3D打印路径规划算法 Intelligent 3D Printing Path Planning Algorithm 计算机科学, 2020, 47(8): 267-271. https://doi.org/10.11896/jsjkx.190700184
[14]	张红颖, 申荣苗, 罗谦. 基于混合整数规划的停机位优化调度研究 Study on Optimal Scheduling of Gate Based on Mixed Integer Programming 计算机科学, 2020, 47(8): 278-283. https://doi.org/10.11896/jsjkx.190400154
[15]	包振山, 郭俊南, 谢源, 张文博. 基于LSTM-GA的股票价格涨跌预测模型 Model for Stock Price Trend Prediction Based on LSTM and GA 计算机科学, 2020, 47(6A): 467-473. https://doi.org/10.11896/JsJkx.190900128

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed