Rehandling-aware stowage planning for RoRo ships using exclusive subgraph modeling and affinity-based cargo ordering

Roll-on/Roll-off (RoRo) ships are designed for direct loading and unloading of wheeled cargo without the use of cranes. During a voyage with sequential port calls, the path of cargo handled at a specific port may be blocked by other cargoes. This results in unnecessary operations, known as rehandling, which relocate other cargoes to reserve a path for the blocked cargoes. Minimizing rehandling significantly reduces cargo handling costs, and this problem is defined as the NP-hard RoRo Ship Stowage Problem (RSSP). This study proposes a backtracking-based algorithm to reduce rehandling in the RSSP effectively. The key components of the proposed method are as follows: (i) a ship structure model based on disjoint subgraphs that cargoes in conflict relationship can be assigned without rehandling, (ii) a cargo ordering strategy that accounts for inter-cargo relationships defined by handling ports and total volume of related cargoes, (iii) a backtracking-based Conflict Free Block (CFB) selection strategy capable of incorporating multiple evaluation metrics, and (iv) a post-processing strategy for partitioning rehandled cargo. Simulation results demonstrate that the proposed method reduces rehandling instances by up to 65% compared to existing methods under various loading scenarios. In practical terms, this can be interpreted as an approximate 18% reduction in the total number of cargo handling operations.