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

AbstractAs 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