-
摘要: 为了提高集装箱港口内堆场的装卸作业效率, 建立了以压箱数最小为目标的出口集装箱箱位指派模型; 考虑铁路运输箱成批到达和公路运输箱到达存在随机性的不同特点以及配载计划的影响, 设计了基于预测方法的启发式算法; 根据公路运输箱的到达特点, 利用马尔科夫链预测公路运输箱的到达顺序; 考虑箱位指派模型的特点, 设计了箱位指派求解算法对铁路运输箱和公路运输箱进行箱位指派, 利用MATLAB软件仿真测试了提出的模型与算法; 通过小规模试验验证了模型和算法的可行性和有效性, 并进行了2组大规模对比试验, 一组对比试验为铁路运输箱和公路运输箱混合堆存模式与铁路运输箱和公路运输箱分开堆存模式, 另一组对比试验为提出的算法与传统堆存算法。分析结果表明: 混合堆存模式比分开堆存模式的压箱数少27.9%, 提出的算法比传统堆存算法的压箱数少37.7%;混合堆存模式可有效减少压箱数, 提出的算法不仅可以有效解决小规模集装箱堆存问题, 还可以解决大规模集装箱堆存问题, 有效提高了堆场的装卸效率, 为集装箱的装船作业提供了便利。Abstract: To enhance the handling efficiency of container yard in container terminal, a slot allocation model of outbound containers was set up to minimize the overlapping amount. Considering the different characteristics of arrival in batches of railway containers and random arrival of road containers and the influence of stowage plan, a heuristic algorithm based on the prediction approach was proposed. According to the arrival characteristics of road containers, the arrival sequence of road containers was predicted by the Markov chain. Considering the characteristics of slot allocation model, a slot allocation solving algorithm was proposed to allocate the railway and road containers. The software MATLAB was used to simulate and test the proposed model and algorithm. The small-scale experiments were conducted to verify the feasibilities and effectivenesses of the proposed model and algorithm, and two large-scale comparison experiments were carried out. One comparison experiment is between the mixed storage mode and the separate storage mode of railway and road containers. Another comparison experiment is between the proposed algorithm and the traditional storage algorithm. Analysis result indicates that the overlapping amount of mixed storage mode is 27.9% less than that of separate mode. The overlapping amount of the proposed algorithm is 37.7% less than that of the traditional storage algorithm. The mixed storage mode can effectively reduce the overlapping amount. The proposed algorithm can both effectively solve the small-scale and large-scale container allocation problems. It effectively enhances the handling efficiency of container yard and facilitates the loading operation of containers.
-
Key words:
- integrated transportation /
- slot allocation /
- heuristic algorithm /
- railway container /
- road container /
- stowage plan
-
表 1 到达顺序出现次数
Table 1. Occurrences of arrival orders
到达顺序 出现次数 到达顺序1 28 到达顺序2 4 到达顺序3 25 到达顺序4 29 到达顺序5 25 到达顺序6 30 到达顺序7 27 到达顺序8 25 表 2 状态转移次数
Table 2. Occurrences of state transition
到达顺序 出现次数 转移为到达顺序 次数 到达顺序1 7 1 2 2 1 3 3 4 1 到达顺序2 5 1 1 2 1 3 1 4 2 到达顺序3 6 1 1 2 2 3 2 4 1 到达顺序4 5 1 2 2 1 3 1 4 1 表 3 小规模试验结果对比
Table 3. Comparison of small-scale experiment result
计划时段 混合堆存压箱数 分开堆存压箱数 运输箱数 分开堆存与混合堆存压箱数相对差值/% 1 0 0 30 0.0 2 5 5 115 0.0 3 5 7 149 28.6 4 6 13 213 53.8 5 10 18 261 44.4 6 18 26 350 30.8 表 4 三个计划周期内2种堆存模式压箱数对比
Table 4. Comparison of overlapping amount between two storage modes in three planning cycles
计划时段 混合堆存压箱数 分开堆存压箱数 运输箱数 分开堆存与混合堆存压箱数相对差值/% 1 0 0 30 0.0 2 5 5 115 0.0 3 5 7 149 28.6 4 6 13 213 53.8 5 10 18 261 44.4 6 18 26 350 30.8 7 4 5 81 20.0 8 9 13 157 30.8 9 14 18 193 22.2 10 17 22 229 22.7 11 17 27 265 37.0 12 25 42 350 40.5 13 3 3 45 0.0 14 8 7 130 -14.3 15 9 10 174 10.0 16 9 20 219 55.0 17 12 28 304 57.1 18 13 35 350 62.9 表 5 两种方法对比
Table 5. Comparison of two methods
计划时段 启发式算法压箱数 随机堆存方法压箱数 运输箱数 随机堆存与启发式算法堆存压箱数相对差值/% 1 0 0 30 0.0 2 5 7 115 28.6 3 5 9 149 44.4 4 6 16 213 62.5 5 10 22 261 54.5 6 18 33 350 45.4 7 4 5 81 20.0 8 9 15 157 40.0 9 14 21 193 33.3 10 17 26 229 34.6 11 17 28 265 39.3 12 25 42 350 40.5 13 3 5 45 40.0 14 8 10 130 20.0 15 9 14 174 35.7 16 9 17 219 47.0 17 12 22 304 45.4 18 13 25 350 48.0 -
[1] KIM K H, PARK Y M, RYU K R. Deriving decision rules to locate export containers in container yards[J]. European Journal of Operational Research, 2000, 124(1): 89-101. doi: 10.1016/S0377-2217(99)00116-2 [2] ZHANG Chu-qian, LIU Ji-yin, WAN Y W, et al. Storage space allocation in container terminals[J]. Transportation Research Part B: Methodological, 2003, 37(10): 883-903. doi: 10.1016/S0191-2615(02)00089-9 [3] KOZAN E, PRESTON P. Mathematical modelling of container transfers and storage locations at seaport terminals[J]. OR Spectrum, 2006, 28(4): 519-537. doi: 10.1007/s00291-006-0048-1 [4] BAZZAZI M, SAFAEI N, JAVADIAN N. A genetic algorithm to solve the storage space allocation problem in a container terminal[J]. Computers and Industrial Engineering, 2009, 56(1): 44-52. doi: 10.1016/j.cie.2008.03.012 [5] SHARIF O, HUYNH N. Storage space allocation at marine container terminals using ant-based control[J]. Expert Systems with Applications, 2013, 40(6): 2323-2330. doi: 10.1016/j.eswa.2012.10.032 [6] JIANG Xin-jia, CHEW E P, LEE L H, et al. Short-term space allocation for storage yard management in a transshipment hub port[J]. OR Spectrum, 2014, 36(4): 879-901. doi: 10.1007/s00291-014-0366-7 [7] ZHANG Can-rong, WU Tao, ZHONG Ming, et al. Location assignment for outbound containers with adjusted weight proportion[J]. Computers and Operations Research, 2014, 52: 84-93. doi: 10.1016/j.cor.2014.06.012 [8] 周鹏飞, 赵金秋, 尚尔进. 混堆集装箱堆场的出口箱位优选干扰管理[J]. 哈尔滨工程大学学报, 2017, 38(6): 866-873, 938. https://www.cnki.com.cn/Article/CJFDTOTAL-HEBG201706009.htmZHOU Peng-fei, ZHAO Jin-qiu, SHANG Er-jin. Disruption management model and algorithm for export container slots optimization in container yards of mixture storage mode[J]. Journal of Harbin Engineering University, 2017, 38(6): 866-873, 938. (in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-HEBG201706009.htm [9] GHAREHGOZLI A, ZAERPOUR N. Stacking outbound barge containers in an automated deep-sea terminal[J]. European Journal of Operational Research, 2018, 267(3): 977-995. doi: 10.1016/j.ejor.2017.12.040 [10] MALDONADO S, GONZÁLEZ-RAMÍREZ R G, QUIJADA F, et al. Analytics meets port logistics: a decision support system for container stacking operations[J]. Decision Support Systems, 2019, 121: 84-93. doi: 10.1016/j.dss.2019.04.006 [11] JIN Bo, ZHU Wen-bin, LIM A. Solving the container relocation problem by an improved greedy look-ahead heuristic[J]. European Journal of Operational Research, 2015, 240(3): 837-847. doi: 10.1016/j.ejor.2014.07.038 [12] GALLE V, BARNHART C, JAILLET P. A new binary formulation of the restricted container relocation problem based on a binary encoding of configurations[J]. European Journal of Operational Research, 2018, 267(2): 467-477. doi: 10.1016/j.ejor.2017.11.053 [13] DA SILVA M D M, ERDOǦAN G, BATTARRA M, et al. The block retrieval problem[J]. European Journal of Operational Research, 2018, 265(3): 931-950. doi: 10.1016/j.ejor.2017.08.048 [14] JOVANOVIC R, TUBA M, VOß S. An efficient ant colony optimization algorithm for the blocks relocation problem[J]. European Journal of Operational Research, 2019, 274(1): 78-90. doi: 10.1016/j.ejor.2018.09.038 [15] WANG Ning, JIN Bo, LIM A. Target-guided algorithms for the container pre-marshalling problem[J]. Omega, 2015, 53: 67-77. doi: 10.1016/j.omega.2014.12.002 [16] WANG Ning, JIN Bo, ZHANG Zi-zhen, et al. A feasibility-based heuristic for the container pre-marshalling problem[J]. European Journal of Operational Research, 2017, 256(1): 90-101. doi: 10.1016/j.ejor.2016.05.061 [17] TANAKA S, TIERNEY K. Solving real-world sized container pre-marshalling problems with an iterative deepening branch-and-bound algorithm[J]. European Journal of Operational Research, 2018, 264(1): 165-180. doi: 10.1016/j.ejor.2017.05.046 [18] TANAKA S, TIERNEY K, PARREÑO-TORRES C, et al. A branch and bound approach for large pre-marshalling problems[J]. European Journal of Operational Research, 2019, 278(1): 211-225. doi: 10.1016/j.ejor.2019.04.005 [19] PARREÑO-TORRES C, ALVAREZ-VALDES R, RUIZ R. Integer programming models for the pre-marshalling problem[J]. European Journal of Operational Research, 2019, 274(1): 142-154. doi: 10.1016/j.ejor.2018.09.048 [20] HOTTUNG A, TANAKA S, TIERNEY K. Deep learning assisted heuristic tree search for the container pre-marshalling problem[J]. Computers and Operations Research, 2020, 113: 104781. doi: 10.1016/j.cor.2019.104781 [21] 段刚, 陈莉, 陈志忠, 等. 铁路集装箱堆场混堆区箱位分配优化模型与算法[J]. 铁道学报, 2011, 33(7): 1-7. doi: 10.3969/j.issn.1001-8360.2011.07.001DUAN Gang, CHEN Li, CHEN Zhi-zhong, et al. Model and algorithm for optimization of container storage allocation in mixed storage area of railway container yard[J]. Journal of the China Railway Society, 2011, 33(7): 1-7. (in Chinese). doi: 10.3969/j.issn.1001-8360.2011.07.001 [22] 王力, 朱晓宁, 闫伟, 等. 铁路集装箱中心站堆场混堆优化模型[J]. 交通运输系统工程与信息, 2013, 13(2): 172-178. doi: 10.3969/j.issn.1009-6744.2013.02.026WANG Li, ZHU Xiao-ning, YAN Wei, et al. Optimization model of mixed storage in railway container terminal yard[J]. Journal of Transportation Systems Engineering and Information Technology, 2013, 13(2): 172-178. (in Chinese). doi: 10.3969/j.issn.1009-6744.2013.02.026 [23] WANG Li, ZHU Xiao-ning, XIE Zheng-yu. Storage space allocation of inbound container in railway container[J]. Mathematical Problems in Engineering, 2014, 2014: 956536. [24] 计明军, 黄思佳, 郭文文. 海铁联运中心站堆场箱位指派优化[J]. 系统工程理论与实践, 2016, 36(6): 1555-1567. https://www.cnki.com.cn/Article/CJFDTOTAL-XTLL201606021.htmJI Ming-jun, HUANG Si-jia, GUO Wen-wen. Container allocation optimization of the center terminal yard under rail-sea intermodal transportation[J]. Systems Engineering—Theory and Practice, 2016, 36(6): 1555-1567. (in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-XTLL201606021.htm [25] WANG Li, ZHU Xiao-ning, XIE Zheng-yu. Container assignment optimization considering overlapping amount and operation distance in rail-road transshipment terminal[J]. Advances in Production Engineering and Management, 2017, 12(4): 363-374. doi: 10.14743/apem2017.4.264 [26] LI Yan-jing, ZHU Xiao-ning, WANG Li, et al. Stowage plan based slot optimal allocation in rail-water container terminal[J]. Journal of Control Science and Engineering, 2017, 2017: 5489597. [27] CHANG Yi-mei, ZHU Xiao-ning, HAGHANI A. The outbound container slot allocation based on the stowage plan in rail-water intermodal container terminals[J]. Measurement and Control, 2019, 52(5/6): 509-525. [28] CHANG Yi-mei, ZHU Xiao-ning. A novel two-stage heuristic for solving storage space allocation problems in rail-water intermodal container terminals[J]. Symmetry, 2019, 11(10): 1229. doi: 10.3390/sym11101229 [29] 常祎妹, 朱晓宁, 王力. 集装箱码头集成调度研究综述[J]. 交通运输工程学报, 2019, 19(1): 136-146. doi: 10.3969/j.issn.1671-1637.2019.01.014CHANG Yi-mei, ZHU Xiao-ning, WANG Li. Review on integrated scheduling of container terminal[J]. Journal of Traffic and Transportation Engineering, 2019, 19(1): 136-146. (in Chinese). doi: 10.3969/j.issn.1671-1637.2019.01.014 [30] 邵乾虔. 不确定条件下的集装箱码头堆场出口箱堆存优化研究[D]. 大连: 大连海事大学, 2013.SHAO Qian-qian. Storage optimization for export containers in container yard with delivery sequence uncertainties[D]. Dalian: Dalian Maritime University, 2013. (in Chinese). [31] CASERTA M, SCHWARZE S, VOß S. A mathematical formulation and complexity considerations for the blocks relocation problem[J]. European Journal of Operational Research, 2012, 219(1): 96-104. doi: 10.1016/j.ejor.2011.12.039