Mathematical models for the berth allocation problem in dry bulk terminals.

*(English)*Zbl 1391.90370Summary: Port terminals processing large cargo vessels play an important role in bulk material supply chains. This paper addresses the question of how to allocate vessels to a location on a berth and the sequence in which the vessels should be processed in order to minimize delays. An important consideration in the berth allocation is the presence of tidal constraints that limit the departure of fully loaded vessels from the terminal. We show how the berth allocation problem can be modeled as an integer program and discuss a number of ways to tighten the formulation in order to make it computationally tractable. In addition, a two-phase method is developed for solving these problems. Empirical computational results demonstrate an order of magnitude improvement in performance. The two new approaches can solve significantly larger instances, producing faster solutions for small instances and much tighter bounds for large instances.

##### MSC:

90B80 | Discrete location and assignment |

90B35 | Deterministic scheduling theory in operations research |

68M20 | Performance evaluation, queueing, and scheduling in the context of computer systems |

90C05 | Linear programming |

90C11 | Mixed integer programming |

PDF
BibTeX
XML
Cite

\textit{A. T. Ernst} et al., J. Sched. 20, No. 5, 459--473 (2017; Zbl 1391.90370)

Full Text:
DOI

##### References:

[1] | Abdekhodaee, A; Wirth, W, Off-line scheduling with forbidden zones, Computers & Operations Research, 40, 1034-1037, (2013) · Zbl 1349.90299 |

[2] | Arahori, Y; Imamichi, T; Nagamochi, H, An exact strip packing algorithm based on canonical forms, Computers & Operations Research, 39, 2991-3011, (2012) · Zbl 1349.90704 |

[3] | Barros, VH; Costa, TS; Oliveira, ACM; Lorena, LAN, Model and heuristic for berth allocation in tidal bulk ports with stock level constraints, Computers & Industrial Engineering, 60, 606-613, (2011) |

[4] | Castro, PM; Oliveira, JF, Scheduling inspired models for two-dimensional packing problems, European Journal of Operational Research, 215, 45-56, (2011) · Zbl 1242.90108 |

[5] | Cordeau, J.-F., Laporte, G., Legato, P., & Moccia, L. (2005). Models and tabu search heuristics for the berth-allocation problem. Transportation Science, 39, 526-538. |

[6] | Du, Y; Chen, Q; Lam, JSL; Xu, Y; Cao, JX, Modeling the impacts of tides and the virtual arrival policy in berth allocation, Transportation Science, 49, 939-956, (2015) |

[7] | Guan, Y; Cheung, RK, The berth allocation problem: models and solution methods, OR Spectrum, 26, 75-92, (2004) · Zbl 1161.90430 |

[8] | Guan, Y; Xiao, WQ; Cheung, RK; Li, CL, A multiprocessor task scheduling model for berth allocation: heuristic and worst case analysis, Operations Research Letters, 30, 343-350, (2002) · Zbl 1010.90026 |

[9] | Haouari, M; Kooli, A; Néron, E, Enhanced energetic reasoning-based lower bounds for the resource constrained project scheduling problem, Computers & Operations Research, 39, 1187-1194, (2012) · Zbl 1251.90152 |

[10] | Imai, A; Sun, X; Nishimura, E; Papadimitriou, S, Berth allocation in a container port: using a continuous location space approach, Transportation Research Part B, 39, 199-221, (2005) |

[11] | Kim, KH; Moon, KC, Berth scheduling by simulated annealing, Transportation Research Part B, 37, 541-560, (2003) |

[12] | Lee, D-H; Chen, JH; Cao, JX, The continuous berth allocation problem: A greedy randomized adaptive search solution, Transportation Research Part E, 46, 1017-1029, (2010) |

[13] | Li, CL; Cai, XQ; Lee, CY, Scheduling with multiple-job-on-one processor pattern, IIE Transactions, 30, 433-445, (1998) |

[14] | Lim, A, The berth planning problem, Operations Research Letters, 22, 105-110, (1998) · Zbl 0911.90283 |

[15] | Nishimura, E; Imai, A; Papadimitriou, S, Berth allocation planning in the public berth system by genetic algorithms, European Journal of Operational Research, 131, 282-292, (2001) · Zbl 0991.90074 |

[16] | Singh, G; Ernst, AT; Baxter, M; Sier, D, Rail schedule optimisation in the Hunter valley coal chain, RAIRO-Operationas Research, 49, 413-434, (2015) · Zbl 1310.90016 |

[17] | Singh, G; Sier, D; Ernst, AT; Gavriliouk, O; Oyston, R; Giles, T; Welgama, P, A mixed integer programming model for long term capacity expansion planning: A case study from the Hunter valley coal chain, European Journal of Operational Research, 220, 210-224, (2011) · Zbl 1253.90157 |

[18] | Umang, N; Bierlaire, M; Vacca, I, Exact and heuristic methods to solve the berth allocation problem in bulk ports, Transportation Research Part E, 54, 14-31, (2013) |

[19] | UNCTAD. (2015). Review of maritime transport. United Nations Conference on Trade and Development. http://unctad.org/en/PublicationsLibrary/rmt2015_en. · Zbl 1237.90136 |

[20] | Xu, D; Li, C-L; Leung, JY-T, Berth allocation with time-dependent physical limitations on vessels, European Journal of Operational Research, 216, 47-56, (2012) · Zbl 1237.90136 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.