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

Charlotte Vilhelmsen, Jesper Larsen, Richard Martin Lusby

    Research output: Book/ReportReportResearch

    453 Downloads (Pure)

    Abstract

    In bulk shipping, ships often have multiple tanks and carry multiple inhomogeneous products at a time. When operating such ships it is therefore a major challenge to decide how to best allocate cargoes to available tanks while taking into account tank capacity, safety restrictions, ship stability and strength as well as other operational constraints. The problem of finding a feasible solution to this tank allocation problem has been shown to be NP-Complete. We approach the problem on a tactical level where requirements for computation time are strict while solution quality is less important than simply finding a feasible solution. We have developed a heuristic that can efficiently find feasible cargo allocations. Computational results show that it can solve 99% of the considered instances within 0.4 seconds and all of them if allowed longer time. We have also modified an optimality based method from the literature. The heuristic is much faster than this modified method on the vast majority of considered instances. However, the heuristic struggles on two instances which are relatively quickly solved by the modified optimality based method. These two methods therefore complement each other nicely and so, we have created a hybrid method that first runs the heuristic and if the heuristic fails to solve the problem, then runs the modified optimality based method on the parts of the problem that the heuristic did not solve. This hybrid method cuts between 90% and 94% of the average running times compared to the other methods and consistently solves more instances than the other methods within any given time limit. In fact, this hybrid method is fast enough to be used in a tactical setting.
    Original languageEnglish
    PublisherDTU Management Engineering
    Number of pages22
    Publication statusPublished - 2014

    Bibliographical note

    Technical report

    Cite this