求解动态停泊计划问题的拉格朗日松弛算法

Lagrangian relaxation algorithm for dynamic berth planning problem

研究钢铁企业原料码头动态停泊计划问题,其动态特征主要体现在原料船动态到达并有两个或两个以上连续泊位且在停泊计划开始执行时每一泊位上仅有部分泊位长度可利用。针对这个问题,建立了一个数学模型并设计了改进拉格朗日算法在很短的时间内求得了近优解。在改进算法中使用了所提出的四个性质来分别加速求解子问题、乘子更新和获得可行解的过程。通过包含50个实际规模问题的算法性能实验表明改进的拉格朗日松弛算法相比未改进算法减少了80%的运行时间。

A dynamic berth planning problem encountered in the iron and steel industry is investigated. The dynamic features reflect that the docks have two or more berths with continuous berth sections and the berth sections on the same berth are not simultaneously available at the planning start time period. This problem is formulated as a 0-1 hybrid mathematical model. An improved Lagrangian relaxation algorithm is presented for the solution in a reasonable running time by introducing four proper- ties to speed up the procedures of solving the sub-problems, updating Lagrangian multipliers and obtaining feasible solutions, respectively. Computational results including 50 real-size problems show that the improved algorithm can reduce more than 80% of the running time of unimproved heuristics.