Date of Award

August 2020

Degree Type

Dissertation

Degree Name

Doctor of Philosophy

Department

Engineering

First Advisor

Matthew E. H. Petering

Committee Members

Jaejin Jang, Christine Cheng, Hamid K Seifoddini, Xiaohang Yue

Keywords

Container terminal, Dual-spreader crane, Integer programming, Maritime container shipping, Quay crane, Triple-spreader crane

Abstract

ABSTRACT

SEQUENCING MULTIPLE-SPREADER CRANE OPERATIONS:

MATHEMATICAL FORMULATIONS AND HEURISTIC ALGORITHMS

by

Shabnam Lashkari

The University of Wisconsin-Milwaukee, 2020

Under the Supervision of Professor Matthew E.H. Petering

Maritime container shipping is one the oldest industries and plays a key role in transporting freight all around the world. The International Maritime Organization (IMO) reports that more than 90% of international trade across the world is carried by sea. This method of transportation is by far the most cost-efficient among rail, road, air, and water transportation.

Today most overseas shipping of finished consumer goods is done via 20-, 40-, or 45-foot long steel containers aboard deep-sea container vessels. Every day, tens of thousands of containers are moved between different countries all around the world. In addition, the amount of meat, fish, fruit, vegetables, and general foodstuffs shipped in refrigerated containers continues to increase. As the volume of freight shipped via steel shipping containers grows, it is becoming increasingly important to improve the operational efficiency of the port facilities where containerships are unloaded and loaded.

In this research, we consider several new mathematical problems inspired by the unloading of a containership. These problems are inspired by the recent development of a new kind of quay crane—a multi-spreader quay crane—that can lift more than one 40-foot container from a containership at the same time. This new crane has an extra strong steel structure that allows heavier lifts to be performed. In contrast to traditional cranes, this new crane may deploy two or three spreaders simultaneously.

Multi-spreader quay cranes have the potential to significantly increase the productivity of seaport container terminals. However, due to a paucity of scheduling approaches for such cranes, this potential has not been fully realized. This motivates our research. In this dissertation, we define new mathematical problems that are inspired by the scheduling of double-spreader and triple-spreader quay cranes. These problems are called the dual-spreader crane and triple-spreader crane scheduling problem respectively.

We formulate the above problems as integer linear programs and develop fast methods for computing lower bounds on the optimal objective value in each case. In addition, we devise simulated annealing, genetic algorithm, and dynamic programming methods to produce high quality solutions for small, medium, large, and very large problem instances in a short amount of time. Experimental results show the effectiveness of our proposed methods in attacking these important logistics problems.

Chapter 1 starts with introducing container shipping history and how it has developed through the years. We then discuss how modern container shipping has dominated world trade and review some statistics to show how this industry affects the global transportation system. Finally, we discuss related academic and industrial literature.

In Chapter 2, we investigate the problem of scheduling a dual-spreader crane that can perform single container lifts and dual container lifts (in which the crane lifts two adjacent containers). This chapter presents a mathematical model of the dual-spreader crane scheduling problem (DSCSP) and describes a fast method for computing a lower bound on the optimal objective value. Then, we introduce a simulated annealing heuristic method that tries to find good solutions to instances of the DSCSP within a short time. Finally, we describe the experimental setup and discuss the experimental results for two solution methods—standard integer programming and the simulated annealing—on a set of 120 problem instances.

Chapter 3 discusses the triple-spreader crane scheduling problem (TSCSP). A triple-spreader crane can operate in three modes: single, double, and triple. When in (single, double, triple) spreader mode, the crane can lift (1, 2, 3) adjacent containers respectively. The TSCSP is formulated as an integer linear program. Later in the chapter, a method for calculating a lower bound on the optimal objective value is introduced, a genetic algorithm that uses two different gene generating subroutines is explained in detail, and the experimental setup and the experimental results for a set of 120 problem instances are discussed.

Finally, Chapter 4 discusses final conclusions and future work.

Download

Share

COinS