Optimization for parking space distribution in storage yard of automotive ro-ro wharf based on the strategy of gathered groups
-
摘要: 滚装汽车堆场车位分配的合理性直接影响到滚装运输过程中汽车装卸滚装船舶的周转率.为提升装卸作业效率, 研究了堆场车位最优分配问题;按照成组集中分配原则, 以提高堆场内成组汽车停放集中度为目标,建立了衡量成组汽车停放集中度的混合整数规划模型;进而设计了基于网格随机搜索的启发式算法对模型进行求解.通过数值实验与分支定界法作比,验证了模型的合理性及网格随机搜索算法的有效性,拓展了汽车滚装码头堆场车位分配管理的理论研究.Abstract: The rationality of parking space distribution of the ro-ro storage yard effects the loading and unloading of turnover rate in the process of ro-ro transportation. In order to improve the working efficiency, the article researched the problem of parking space optimal distribution. According to the principle of gathered groups distribution, focusing on improving concentration degree of batch automobiles, a mixed-integer programming model was proposed to measure concentration degree of batch automobiles. Then a heuristic algorithm of grids random search was designed to solve the model. Compared with branch and bound method through numerical experiments, the results proved that the proposed model and algorithm are reasonable and valid, generalizing the theory research for parking space distribution and managment of ro-ro wharf.
-
表 1 数值实验设计
Tab. 1 Numerical experiments design
实验待 作业汽车属性 初始堆场属性 场景 序号 汽车
组数每组汽
车数目布局
(行,列)已占车位率 已占车位坐标 一 1 3 2/2/3 (4,5) 0.25 (2,2)(2,5)(3,1)(3,3)(3,5) 2 3 4/2/3 (4,5) 0.25 (2,2)(2,5)(3,1)(3,3)(3,5) 3 3 4/3/4 (4,5) 0.25 (2,2)(2,5)(3,1)(3,3)(3,5) 二 1 4 3/2/4/3 (4,5) 0.25 (2,2)(2,5)(3,1)(3,3)(3,5) 2 5 2/4/1/3/2 (4,5) 0.25 (2,2)(2,5)(3,1)(3,3)(3,5) 3 6 1/2/3/2/1/3 (4,5) 0.25 (2,2)(2,5)(3,1)(3,3)(3,5) 三 1 3 4/3/5 (4,5) 0.25 (2,2)(2,5)(3,1)(3,3)(3,5) 2 3 4/3/5 (4,7) 0.25 (2,2)(2,4)(2,6)(2,7)(3,1)(3,3)(3,6) 3 3 4/3/5 (4,9) 0.25 (2,2)(2,4)(2,6)(3,3)(3,5)(3,7)(4,2)(4,4)(4,6) 四 1 3 4/3/5 (4,5) 0.30 (2,1)(2,3)(2,4)(3,2)(3,3)(3,5) 2 3 4/3/5 (4,5) 0.20 (2,1)(2,4)(3,3)(3,5) 3 3 4/3/5 (4,5) 0.10 (2,1)(3,5) 表 2 分支定界法与网格随机搜算法实验结果对比
Tab. 2 Results comparison between branch and bound method and grids random searchalgorithm
实验 分支定界法 基于网格随机搜索的启发式算法 场景 序号 目标值f CPU Time/s 目标值f CPU Time/s 误差/偏差* 一 1 3.0 46 3.0 17 0.00 2 3.0 458 3.3 10 0.10 3 3.3 1439 3.5 11 0.06 二 1 4.0 11931 4.7 8 0.18 2 5.0 32808 5.5 13 0.10 3 6.0 21214 6.3 7 0.05 三 1 3.2 2261 3.3 20 0.03 2 3.0 126076 3.7 26 0.23 3 3.2* 259200 3.0 19 1.00* 四 1 3.0 638 4.1 13 0.17 2 3.0 2303 3.5 20 0.20 3 3.5 11976 3.2 20 0.07 注: ① 分支定界法对应的f中上标*值为上界值,其下界值为 0,gap=1; 其余f均为最优解,gap=0.
② 误差计算公式: (b-a)/a,其中 a 为分支定界法对应的f值,b为网格随机搜索算法对应的f值.
③ 偏差计算公式: (b-a)/b,其中 a为分支定界法对应的下界值,b为网格随机搜索算法对应的
f值. -
[1] DIAS J C Q, CALADO J M F, MENDONCA M C. The role of European "ro-ro" port terminals in the automotivesupply [J]. Journal of Transport Geography, 2010, 18(1): 116-124. doi: 10.1016/j.jtrangeo.2008.10.009 [2] MENDONCA M C, DIAS J C Q. "postponement" in the logistical systems of new automobiles marketed in portugal: The brandsand quality [J]. Total Quality Management & Business Excellence, 2007, 18(6): 681-696. [3] CHEN I J, PAULRAJ A. Understanding supply chain management: Critical research and a theoretical framework [J]. International Journal of Production Research, 2004, 42(1): 131-163. doi: 10.1080/00207540310001602865 [4] FISCHER T, GEHRING H. Planning vehicle transhipment in a seaport automobile terminal using a multi-agent system [J]. European Journal of Operational Research, 2005, 166(3): 726-740. doi: 10.1016/j.ejor.2004.03.042 [5] BOSE F, WINDT K. Understanding Autonomous Cooperation and Control in Logistics [M]. Berlin: Springer, 2007: 351-363. [6] MATTFELD D C, ORTH H. The allocation of storage space for transshipmentin vehicle distribution [C]//linebreak Container Terminals and Cargo Systems. Berlin: Springer, 2007: 267-290. [7] MATTFELD D C, BIERWIRTH C. An efficient genetic algorithm for job shop scheduling with tardiness objectives [J]. European Journal of Operational Research, 2004, 155(3): 616-630. doi: 10.1016/S0377-2217(03)00016-X [8] MATTFELD D C, KOPFER H. Terminal operations management in vehicle transshipment [J]. Transportation Research Part A, 2003, 37(6): 435-452. [9] CORDEAU J F, MOCCIA G L. Optimizing yard assignment in an automotive transshipment terminal [J]. European Journal of Operational Research, 2011, 215(1): 149-160. doi: 10.1016/j.ejor.2011.06.008