A Heuristic and Hybrid Method for the Tank Allocation Problem in Maritime Bulk Shipping

摘要

Many bulk ships have multiple tanks and can thereby carry multiple inhomogeneous products at a time. A major challenge when operating such ships is how to best allocate cargoes to available tanks while taking tank capacity, safety restrictions, ship stability and strength as well as other operational constraints into account. The complexity of the allocation problem varies with the number of tanks and the number and type of dierent products transported at the same time, and the problem of nding a feasible solution has been shown to be NP-Complete. The Tank Allocation Problem (TAP) as described above is an operational planning problem but it also arises as a subproblem in tactical planning when routing bulk ship eets. For each considered route, the TAP must be solved to assess route feasibility with respect to stowage. If the routing problem is solved in a way that requires assessment of numerous routes, as for instance in column generation and local search based methods, the solution time for the entire procedure will only be acceptable if the TAP can be solved eciently. We consider the TAP from a tactical perspective where the main objective is to quickly assessfeasibility of a given ship route. We have developed a randomised heuristic for eciently nding feasible allocations and computational results show that it can solve 99% of the considered instances within 0.5 seconds and all of them if allowed longer time. The heuristic is designed to work as an ecient subproblem solver and in such a setting with running times below e.g. 5 seconds, the heuristic clearly outperforms an earlier method by consistently solving more instances and eectively cutting 84% of the average running time. Furthermore, we have combined our heuristic with a modied version of the earlier method to derive a hybrid method that can eciently solve all instances. Compared to the earlier method, this hybrid method cuts 93% of the average running times and consistently solves more instances than the other method within any given time limit.