摘要
内河集装箱运输具有其独特性,船舶配载时更强调船舶舱容利用率.考虑特殊箱型影响,以最小化堆栈占用数量为目标,构建内河集装箱船舶配载决策的整数规划模型.为实现快速寻优,设计包含构造部分和优化部分的启发式算法求解.算法中,构造部分基于启发式规则快速构造初始解,优化部分基于邻域搜索策略实现初始解优化.算例研究表明,模型可实现内河集装箱船舶配载决策问题的有效求解,但随着算例规模增加所需求解时间大幅增加.与模型精确求解相比,启发式算法在求解时间方面表现要远优于模型,可在0.25 s内实现所有算例的高效求解,为内河集装箱船舶实际配载决策提供一定参考.
The inland container shipping has its particularity, and the higher ship capacity utilization is more emphasized during the stowage planning. Considering the special container types, the integer programming model for inland container ship stowage planning decision is proposed with the objective of minimizing the ship stack occupancy number. The heuristic algorithm comprising a construction part and an improvement part is designed for the fast optimization. The construction part can construct the initial solution quickly based on some heuristic rules. The improvement part can optimize the initial solution with some local search strategies. Numerical examples show the model can effectively solve the inland container ship stowage planning decision problem, but its solving time increases significantly with the increase of the problem's scale. Compared with the exact solution of the model, the heuristic algorithm outperforms the model in solving time greatly. It can efficiently optimize all the instances within 0.25 second and provide some suggestions for the actual inland container ship stowage planning decision.
引文
[1]李俊,张煜,计三有,等.不确定箱重下内河集装箱班轮航线配载决策[J].交通运输系统工程与信息,2018,18(2):208-215.[LI J,ZHANG Y,JI S Y,et al.Inland container liner route stowage planning decision with uncertain container weight[J].Journal of Transportation Systems Engineering and Information Technology,2018,18(2):208-215.]
[2]WILSON I D,ROACH P A.Container stowage planning:A methodology for generating computerized solutions[J].The Journal of the Operational Research Society,2000(51):1248-1255.
[3]PARRE?O F,PACINO D,ALVAREZ-VALDES R.AGRASP algorithm for the container stowage slot planning problem[J].Transportation Research Part ELogistics&Transportation Review,2016(94):141-157.
[4]祝慧灵,计明军.集装箱船舶全航线配载优化模型与改进遗传算法[J].交通运输工程学报,2014,14(5):59-67.[ZHU H L,JI M J.Optimal model and improved genetic algorithm of containership stowage on full route[J].Journal of Traffic and Transportation Engineering,2014,14(5):59-67.]
[5]AMBROSINO D,PAOLUCCI M,SCIOMACHEN A.AMIP Heuristic for multi-port stowage planning[J].Transportation Research Procedia,2015(10):725-734.
[6]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.
[7]AMBROSINO D,PAOLUCCI M,SCIOMACHENA A.Computational evaluation of a MIP model for multi-port stowage planning problems[J].Soft Computing,2017(21):1753-1763.