Mixed Integer Linear Programming and Solution for the Multi-tank Train Stowage Planning Problem of Coils in Steel Industry

摘要

We consider a multi-tank train stowage planning problem of coil (TSPP) where the given coils are assigned into the tanks of the train. Different from stowage problems in previous studies, this problem has its characteristics such as the multi-tank transportation mode, the minimum load restriction of each tank and the rigorous balance constraints. We formulate the problem as a novel mixed integer linear programming model which objectives are to maximize the total weight of loaded coils and to minimize the differences of stack positions of the coils in each tank. The NP-hardness of the problem and intractableness of optimally solving the model motivate us to develop an improved tabu search algorithm to solve it approximately. The algorithm is initiated by a two-stage heuristic where a multi-exchange neighborhood is designed to further improve the initial solutions. And then K -cycle move is used regarded as a diversification strategy in tabu search. Computational results using real data from a specialty steel manufacturer show that for small problems, which can be solved optimally by the model, the proposed algorithm can generate close-to-optimal solutions. For large practical problems the algorithm can obtain good solutions within a shorter time compared with the upper bound.