Knowledge

Keyword: exact methods

paper

The multi-port berth allocation problem with speed optimization: Exact methods and a cooperative game analysis

Bernardo Martin-Iradi, Dario Pacino, Stefan Ropke

We consider a variant of the berth allocation problem-i.e., the multi-port berth allocation problem-aimed at assigning berthing times and positions to vessels in container terminals. This variant involves optimizing vessel travel speeds between multiple ports, thereby exploiting the potentials of a collaboration between carriers (shipping lines) and terminal operators. Using a graph representation of the problem, we reformulate an existing mixed-integer problem into a generalized set partitioning problem, in which each variable refers to a sequence of feasible berths in the ports that the vessel visits. By integrating column generation and cut separation in a branch-and-cut-and-price procedure, our proposed method is able to outperform commercial solvers in a set of benchmark instances and adapt better to larger instances. In addition, we apply cooperative game theory methods to efficiently distribute the savings resulting from a potential collaboration and show that both carriers and terminal operators would benefit from collaborating.

Transportation Science / 2022
Go to paper
paper

A Decomposition Method for Finding Optimal Container Stowage Plans

Roberti, R; Pacino, Dario

In transportation of goods in large container ships, shipping industries need to minimize the time spent at ports to load/unload containers. An optimal stowage of containers on board minimizes unnecessary unloading/reloading movements, while satisfying many operational constraints. We address the basic container stowage planning problem (CSPP). Different heuristics and formulations have been proposed for the CSPP, but finding an optimal stowage plan remains an open problem even for small-sized instances. We introduce a novel formulation that decomposes CSPPs into two sets of decision variables: the first defining how single container stacks evolve over time and the second modeling port-dependent constraints. Its linear relaxation is solved through stabilized column generation and with different heuristic and exact pricing algorithms. The lower bound achieved is then used to find an optimal stowage plan by solving a mixed-integer programming model. The proposed solution method outperforms the methods from the literature and can solve to optimality instances with up to 10 ports and 5,000 containers in a few minutes of computing time.

Transportation Science 52 (6) 1444-1462 / 2018
Go to paper
paper

A Decomposition Method for Finding Optimal Container Stowage Plans

Roberti, Roberto and Mingozzi, Aristide

In transportation of goods in large container ships, shipping industries need to minimize the time spent at ports to load/unload containers. An optimal stowage of containers on board minimizes unnecessary unloading/reloading movements, while satisfying many operational constraints. We address the basic container stowage planning problem (CSPP). Different heuristics and formulations have been proposed for the CSPP, but finding an optimal stowage plan remains an open problem even for small-sized instances. We introduce a novel formulation that decomposes CSPPs into two sets of decision variables: the first defining how single container stacks evolve over time and the second modeling port-dependent constraints. Its linear relaxation is solved through stabilized column generation and with different heuristic and exact pricing algorithms. The lower bound achieved is then used to find an optimal stowage plan by solving a mixed-integer programming model. The proposed solution method outperforms the methods from the literature and can solve to optimality instances with up to 10 ports and 5,000 containers in a few minutes of computing time.

Transportation Science Vol. 52, No. 6: 1297-1588 / 2018
Go to paper