关键词: 原料物流, 停泊计划, 拉格朗日松弛

Abstract: 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 properties 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.

Key words: raw material logistics, berth planning, Lagrangian relaxation