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

Charlotte Vilhelmsen, Jesper Larsen, Richard Martin Lusby

    Research output: Contribution to conferenceConference abstract for conferenceResearchpeer-review

    226 Downloads (Pure)

    Abstract

    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 assess
    feasibility 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.
    Original languageEnglish
    Publication date2014
    Publication statusPublished - 2014
    Event3rd International Symposium on Combinatorial Optimization - Lisbon, Portugal
    Duration: 4 Mar 20147 Mar 2014

    Conference

    Conference3rd International Symposium on Combinatorial Optimization
    CountryPortugal
    CityLisbon
    Period04/03/201407/03/2014

    Bibliographical note

    3rd International Symposium on Combinatorial Optimization (ISCO 2014), 5-7 March 2014, Lisbon, Portugal

    Fingerprint

    Dive into the research topics of 'A Heuristic and Hybrid Method for the Tank Allocation Problem in Maritime Bulk Shipping'. Together they form a unique fingerprint.

    Cite this