Improving container terminal efficiencynew models and algorithms for Premarshalling and Stowage Problems

Résumé

The development of containers has revolutionized maritime trade by making it possible to handle various types and sizes of cargo at a reduced cost, lowering the import cost of many products to such an extent that it is sometimes cheaper to transport goods to the other side of the world than to produce them locally. Nowadays, about 90 per cent of non-bulk cargo worldwide is carried on container ships with capacities exceeding 20,000 TEUs (Twenty-foot Equivalent Units). Container terminals have to cope with the increase in the volumes of cargo transported, the ever-larger ships, and the consolidation of shipping companies. In this context, they have to compete for fewer calls of larger ships. Since they cannot simply increase the number of cranes indefinitely, they have to improve efficiency by optimizing the available resources. This thesis studies two combinatorial optimization problems, the premarshalling problem and the stowage problem. These problems arise in the yard and the seaside of container terminals, before and during the loading and unloading operations of the ships, and make it possible to reduce the berthing time and thus to increase container terminal efficiency. The premarshalling problem prepares the container yard before the arrival of the ship, using the yard cranes when the workload at the terminal is at a minimum to rearrange the yard in order to avoid container relocations when the vessel arrives and to speed up the service times. The classic objective of this problem is to minimize the number of movements required to remove containers blocking the retrieval of others within a bay. Thus, the number of movements has been used as an indicator of crane time. However, this thesis shows that considering the real time that the crane takes to perform the movements as the target, the total time spent by the crane can be cut down up to 24 per cent. To solve both problems, premarshalling with the classic objective function and premarshalling with the new objective function, this thesis develops several mathematical models and branch and bound algorithms with new upper and lower bounds, dominance rules and heuristic algorithms integrated in the branching process. With regard to the stowage problem, the multi-port problem is addressed, seeking to obtain a stowage plan for the ship so as to minimize the total number of unproductive moves in the loading/unloading operations along the trade route of the ship. We start with a simplified problem, in which no size and weight constraints are considered, and progressively introduce more realistic constraints, developing mathematical models, metaheuristics, and matheuristics. These procedures are able to solve very large instances, corresponding to the largest ships in service.