Quay partitioning problem
Jakub Wawrzyniak
Institute of Computing Science, Poznań University of Technology, Piotrowo 2, Poznań, 60-965 Poland
Search for more papers by this authorCorresponding Author
Maciej Drozdowski
Institute of Computing Science, Poznań University of Technology, Piotrowo 2, Poznań, 60-965 Poland
Corresponding author.
Search for more papers by this authorÉric Sanlaville
Normandie Université, UNIHAVRE, UNIROUEN, INSA Rouen, LITIS, Le Havre, 76 600 France
Search for more papers by this authorYoann Pigné
Normandie Université, UNIHAVRE, UNIROUEN, INSA Rouen, LITIS, Le Havre, 76 600 France
Search for more papers by this authorFrederic Guinand
Normandie Université, UNIHAVRE, UNIROUEN, INSA Rouen, LITIS, Le Havre, 76 600 France
Search for more papers by this authorJakub Wawrzyniak
Institute of Computing Science, Poznań University of Technology, Piotrowo 2, Poznań, 60-965 Poland
Search for more papers by this authorCorresponding Author
Maciej Drozdowski
Institute of Computing Science, Poznań University of Technology, Piotrowo 2, Poznań, 60-965 Poland
Corresponding author.
Search for more papers by this authorÉric Sanlaville
Normandie Université, UNIHAVRE, UNIROUEN, INSA Rouen, LITIS, Le Havre, 76 600 France
Search for more papers by this authorYoann Pigné
Normandie Université, UNIHAVRE, UNIROUEN, INSA Rouen, LITIS, Le Havre, 76 600 France
Search for more papers by this authorFrederic Guinand
Normandie Université, UNIHAVRE, UNIROUEN, INSA Rouen, LITIS, Le Havre, 76 600 France
Search for more papers by this authorAbstract
In this paper, we introduce the quay partitioning problem (QPP), that is, a problem of partitioning quay length into berths for minimum ship waiting time. Such a problem arises when designing the terminal layout. Two schemes of quay layout are considered: with at most one ship in a berth and with at most two ships in a berth. Ship arrival times, service times, lengths, and weights are given. We show that QPP is NP-hard. The two versions of QPP are formulated as mixed integer linear programs (MIPs). Scalability of solving QPPs as MIPs is studied. We investigate, analytically and in computational experiments, features of the QPP solutions such as (i) changes in solution quality when one long berth length is used versus choosing various berth lengths flexibly, (ii) what lengths of berths are chosen when ship lengths mixture is changing, (iii) what is the impact of congestion on the chosen berth lengths, and (iv) how much is one quay layout scheme better than the other.
References
- Alcalde, E.M., Kim, K.H., Marchán, S.S., 2015. Optimal space for storage yard considering yard inventory forecasts and terminal performance. Transportation Research Part E: Logistics and Transportation Review 82, 101–128.
- Bierwirth, C., Meisel, F., 2010. A survey of berth allocation and quay crane scheduling problems in container terminals. European Journal of Operational Research 202, 3, 615–627.
- Bierwirth, C., Meisel, F., 2015. A follow-up survey of berth allocation and quay crane scheduling problems in container terminals. European Journal of Operational Research 244, 3, 675–689.
- Błądek, I., Drozdowski, M., Guinand, F., Schepler, X., 2015. On contiguous and non-contiguous parallel task scheduling. Journal of Scheduling 18, 5, 487–495.
- Bouzekri, H., Alpan, G., Giard, V., 2021. Integrated laycan and berth allocation and time-invariant quay crane assignment problem in tidal ports with multiple quays. European Journal of Operational Research 293, 3, 892–909.
- Buhrkal, K., Zuglian, S., Ropke, S., Larsen, J., Lusby, R., 2011. Models for the discrete berth allocation problem: a computational comparison. Transportation Research Part E: Logistics and Transportation Review 47, 4, 461–473.
- Camacho-Villalón, C.L., Dorigo, M., St utzle, T., 2023. Exposing the grey wolf, moth-flame, whale, firefly, bat, and antlion algorithms: six misleading optimization techniques inspired by bestial metaphors. International Transactions in Operational Research 30, 6, 2945–2971.
- Chen, D., Qi, Q., Li, X., Jin, Z., Wang, W., 2021. A method for studying the influence of different berth layout on port service level based on simulation. In 2021 6th International Conference on Transportation Information and Safety (ICTIS), IEEE, Piscataway, NJ, pp. 1315–1319.
10.1109/ICTIS54573.2021.9798485 Google Scholar
- Cordeau, J.F., Laporte, G., Legato, P., Moccia, L., 2005. Models and tabu search heuristics for the berth-allocation problem. Transportation Science 39, 4, 526–538.
- Cruz, R., Mendes, A.B., Bahiense, L., 2023. Schedule robustness in the periodic supply vessels planning problem with stochastic demand and travel time. International Transactions in Operational Research. https://doi.org/10.1111/itor.13241
- Gharehgozli, A., Zaerpour, N., de Koster, R., 2020. Container terminal layout design: transition and future. Maritime Economics & Logistics 22, 4, 610–639.
- Gupta, A., Roy, D., de Koster, R., Parhi, S., 2017. Optimal stack layout in a sea container terminal with automated lifting vehicles. International Journal of Production Research 55, 13, 3747–3765.
- Imai, A., Yamakawa, Y., Huang, K., 2014. The strategic berth template problem. Transportation Research Part E: Logistics and Transportation Review 72, 77–100.
- Jiang, X., Chew, E.P., Lee, L.H., 2015. Innovative container terminals to improve global container transport chains. In Handbook of Ocean Container Transport Logistics, Springer, Cham, pp. 3–41.
10.1007/978-3-319-11891-8_1 Google Scholar
- Kastner, M., Kämmerling, N., Jahn, C., Clausen, U., 2022. A method for studying the influence of different berth layout on port service level based on simulation. In C. Jahn, W. Kersten and C.M. Ringle (eds), Data Science in Maritime and City Logistics: Data-Driven Solutions for Logistics and Sustainability. Proceedings of the Hamburg International Conference of Logistics (HICL), Vol. 30, epubli, Berlin, pp. 485–519.
- Kho, F., 2013. Kalmar's proposal received a commendation award in the next generation container port challenge. Available at https://www.kalmarglobal.com/news–insights/press_releases/2013/kalmars-proposal-received-a-commendation-award-in-the-next-generation-container-port-challenge-/, (Accessed 11 September 2022).
- Kim, J., Morrison, J.R., 2012. Offshore port service concepts: classification and economic feasibility. Flexible Services and Manufacturing Journal 24, 3, 214–245.
- Lee, B.K., Lee, L.H., Chew, E.P., 2018. Analysis on high throughput layout of container yards. International Journal of Production Research 56, 16, 5345–5364.
- Lim, A., 1998. The berth planning problem. Operations Research Letters 22, 2, 105–110.
- Nam, K.C., Kwak, K.S., Yu, M.S., 2002. Simulation study of container terminal performance. Journal of Waterway, Port, Coastal, and Ocean Engineering 128, 3, 126–132.
- Petering, M.E., 2009. Effect of block width and storage yard layout on marine container terminal performance. Transportation Research Part E: Logistics and Transportation Review 45, 4, 591–610.
- Rodrigues, F., Agra, A., 2022. Berth allocation and quay crane assignment/scheduling problem under uncertainty: a survey. European Journal of Operational Research 303, 2, 501–524.
- Rodrigues, F., Agra, A., 2023. Handling uncertainty in the quay crane scheduling problem: a unified distributionally robust decision model. International Transactions in Operational Research 31, 2, 721–748.
10.1111/itor.13325 Google Scholar
- Schepler, X., Balev, S., Michel, S., Sanlaville, É., 2017. Global planning in a multi-terminal and multi-modal maritime container port. Transportation Research Part E: Logistics and Transportation Review 100, 38–62.
- Tan, Z., Zhang, Q., Yuan, Y., Jin, Y., 2022. A decision method on yard cranes transformation and deployment in green ports. International Transactions in Operational Research 29, 1, 323–346.
- Wawrzyniak, J., Drozdowski, M., Sanlaville, É., 2020. Selecting algorithms for large berth allocation problems. European Journal of Operational Research 283, 3, 844–862.
- Wawrzyniak, J., Drozdowski, M., Sanlaville, E., 2022a. A container ship traffic model for simulation studies. International Journal of Applied Mathematics and Computer Science 32, 4, 537–552.
- Wawrzyniak, J., Drozdowski, M., Sanlaville, É., 2022b. Quay partitioning problem—additional resources. Available at http://www.cs.put.poznan.pl/mdrozdowski/qpp/ (Accessed 25 July 2022).
- Wiese, J., Suhl, L., Kliewer, N., 2011. Planning container terminal layouts considering equipment types and storage block design. In Handbook of Terminal Planning, Springer, Berlin, pp. 219–245.
10.1007/978-1-4419-8408-1_12 Google Scholar
- Wikipedia, 2023a. Automatic identification system. Available at https://en.wikipedia.org/wiki/Automatic_identification_system (Accessed 9 March 2022).
- Wikipedia, 2023b. Big O notation. Available at https://en.wikipedia.org/wiki/Big_O_notation (Accessed 9 March 2022).
- Wikipedia, 2023c. Port of Singapore. Available at https://en.wikipedia.org/wiki/Port_of_Singapore (Accessed 9 March 2022).
- Wikipedia, 2023d. Yangshan port. Available at https://en.wikipedia.org/wiki/Yangshan_Port (Accessed 9 March 2022).
- Zhou, Y., Wang, W., Song, X., Guo, Z., 2016. Simulation-based optimization for yard design at mega container terminal under uncertainty. Mathematical Problems in Engineering 2016, 7467498.
