A Branch-and-Price Algorithm for the Integrated Berth Allocation and Quay Crane Assignment Problem

Fanrui Xie (), Tao Wu () and Canrong Zhang ()
Additional contact information
Fanrui Xie: Department of Industrial Engineering, Tsinghua University, Beijing 100084, China; Logistics Engineering and Simulation Laboratory, Graduate School at Shenzhen, Tsinghua University, Shenzhen 518055, China;
Tao Wu: Advanced Analytics Department, Dow, Midland, Michigan 48642
Canrong Zhang: Logistics Engineering and Simulation Laboratory, Graduate School at Shenzhen, Tsinghua University, Shenzhen 518055, China;

Transportation Science, 2019, vol. 53, issue 5, 1427-1454

Abstract: This paper integrates, from a tactical perspective, berth allocation and quay-crane assignment, two important, closely related decisions in container terminal operations in a single model. To obtain optimal solutions, a branch-and-price algorithm is sought in this paper under the framework of Dantzig–Wolfe decomposition. The algorithm decomposes the original problem to a master problem that links all vessels competing for the shared resources of berths and quay cranes and multiple per-vessel pricing subproblems that can be solved efficiently in polynomial time. Specifically, in the stage of generating promising initial feasible columns, three heuristics are adopted; during the column-updating stage, the subgradient-based Lagrangian relaxation is introduced to tackle the possibly encountered degeneracy phenomenon; the branching strategy is implemented in the pricing subproblem rather than in the master problem as reported in the literature with the benefit of avoiding incurring new dual prices, simplifying the branching process; and both breadth- and depth-first searching policies are tested to select the next node to explore. With real-life data, extensive numerical experiments are conducted to select the best choice for each stage with the strengths and drawbacks of each choice provided. And then the superiority of the branch-and-price algorithm configured with the selected combination of strategies is verified by comparing it with both CPLEX, a general-purpose solver, and a set-partitioning model, a dedicated algorithm reported in the literature. In addition, the decomposition by vessels adopted in this paper is also verified numerically by comparing it with the decomposition by berths reported in the literature, and the performance of the algorithm for other problem settings has also been tested. In conclusion, the numerical experiments show that our method outperforms the commercial solver and state-of-the-art solution methods reported in the literature in terms of both solution quality and computational time.

Keywords: berth allocation; quay crane assignment; branch and price; Lagrangian relaxation; subgradient optimization (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (12)

Downloads: (external link)
https://doi.org/10.1287/trsc.2019.0894 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:53:y:2019:i:5:p:1427-1454

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().