A Heuristic Approach to the Two-Dimensional Roll-on Roll-off Liner Shipping Stowage Problem
MetadataShow full item record
Roll-on/Roll-off (RoRo) ships represent the primary source for transporting vehicles and other types of rolling material over long distances. In this master thesis, we focus on operational decisions related to stowage of cargoes for a RoRo ship voyage visiting a given set of loading and unloading ports. Decisions, such as which cargoes to carry and how to stow the vehicles carried during the voyage, are considered. We focus on stowage of one single deck, which is an essential building block in solving the problem for multiple decks, i.e. for the whole ship. By focusing on stowage on one deck, this can be viewed as a special version of a 2-dimensional packing problem with a number of additional considerations. One important consideration is the placement of the vehicles, where one wants to place vehicles that belong to the same shipment close to each other to ease the loading and unloading. Another important consideration in this problem is shifting, which means temporarily moving some vehicles to make an entry/exit route for the vehicles that are to be loaded/unloaded at the given port. Our approach to solving the 2DRSSP splits the problem into two phases. First, we solve the stowage problem for a given deck. Then, the shifting evaluation problem is solved to evaluate the quality of the stowage plan with respect to shifting cost. Two mathematical models are made, describing these problems. In addition, a 2-phase heuristic is developed using components from the greedy randomized adaptive search procedure (GRASP) and the adaptive large neighborhood search (ALNS) procedure. The heuristic first determines which cargoes to carry, in order to maximize the revenue generated from carrying these cargoes, while ensuring a feasible stowage plan exists for the given cargoes. Then, vehicles are relocated in order to ease the loading and unloading. Several problem-specific destroy and repair operators are built in order to improve the heuristic s performance. Computational results show that the mixed integer programming (MIP) solver is able to solve small instances. The proposed heuristic provides close to optimal solutions to these same instances and is able to handle realistically sized problem instances.