A Branch-and-Price Algorithm to Solve a Quay Crane Scheduling Problem

Nabil Kenan, Ali Diabat

Research output: Contribution to journalConference article

Abstract

As the maritime industry grows rapidly in size, more attention is being paid to to a wide range of aspects of problems faced at ports with respect to the efficient allocation of resources. A very important seaside planning problem that has received large attention in literature lately is the quay crane scheduling problem (QCSP). The problem involves the creation of a work schedule for the available quay cranes at the port to empty the containers from a vessel or given set of vessels. These optimization problems can be very complex and since they involve a large number of variables and constraints, the use of a commercial solver is impractical. In this paper, we reformulate a problem currently available in the literature to a Dantzig-Wolfe formulation that can be solved by column generation. We then develop a branch-and-price algorithm, which is an exact method, to effectively solve mixed integer programs with very large instances. The algorithm is first tested on a formulation currently available in literature with a small instance and will then be tested on large instances.

Original languageEnglish (US)
Pages (from-to)527-532
Number of pages6
JournalProcedia Computer Science
Volume61
DOIs
StatePublished - 2015
EventComplex Adaptive Systems, 2015 - San Jose, United States
Duration: Nov 2 2015Nov 4 2015

Keywords

  • branch-and-price
  • column generation
  • dantzig-wolfe
  • martime logistics
  • quay crane scheduling problem

ASJC Scopus subject areas

  • Computer Science(all)

Fingerprint Dive into the research topics of 'A Branch-and-Price Algorithm to Solve a Quay Crane Scheduling Problem'. Together they form a unique fingerprint.

  • Cite this