IDEAS home Printed from https://ideas.repec.org/a/spr/joheur/v29y2023i1d10.1007_s10732-022-09506-3.html
   My bibliography  Save this article

A column generation-based heuristic to solve the integrated planning, scheduling, yard allocation and berth allocation problem in bulk ports

Author

Listed:
  • João Luiz Marques Andrade

    (Federal Center for Technological Education of Minas Gerais)

  • Gustavo Campos Menezes

    (Federal Center for Technological Education of Minas Gerais)

Abstract

The intelligent management of available resources is one of the greatest challenges of any organization. Find the balance between the size of the stock and the production and transport capacity and ensuring quality service to suppliers and customers. This type of challenge is also very common in port terminals. Ensuring efficient and effective operations is fundamental to reduce fines, avoid accidents, and build customer loyalty. This paper considers integrated planning, scheduling, yard allocation, and berth allocation problem in dry bulk port terminals. The integrated problem consists of planning and scheduling the flow of products between the supply and demand nodes, allocating the products to the storage yards, and determining the loading sequence and berth time and position of each vessel. A mixed-integer linear programming model is proposed, connecting the problems and generating an integrated solution. To solve the integrated problem more efficiently, we developed an algorithm that combines the column generation method with a diving heuristic with limited backtracking, a relax-and-fix heuristic, and an exact algorithm from a commercial solver. The mathematical formulation and the proposed algorithm are tested and validated with large-scale instances. Computational experiments show that the proposed solution approach outperform commercial solver and is very effective in finding strong bounds for large instances.

Suggested Citation

  • João Luiz Marques Andrade & Gustavo Campos Menezes, 2023. "A column generation-based heuristic to solve the integrated planning, scheduling, yard allocation and berth allocation problem in bulk ports," Journal of Heuristics, Springer, vol. 29(1), pages 39-76, February.
    • Handle: RePEc:spr:joheur:v:29:y:2023:i:1:d:10.1007_s10732-022-09506-3
    DOI: 10.1007/s10732-022-09506-3
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10732-022-09506-3
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10732-022-09506-3?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Lixin Tang & Defeng Sun & Jiyin Liu, 2016. "Integrated storage space allocation and ship scheduling problem in bulk cargo terminals," IISE Transactions, Taylor & Francis Journals, vol. 48(5), pages 428-439, May.
    2. Arijit De & Saurabh Pratap & Akhilesh Kumar & M. K. Tiwari, 2020. "A hybrid dynamic berth allocation planning problem with fuel costs considerations for container terminal port using chemical reaction optimization approach," Annals of Operations Research, Springer, vol. 290(1), pages 783-811, July.
    3. Andreas T. Ernst & Ceyda Oğuz & Gaurav Singh & Gita Taherkhani, 2017. "Mathematical models for the berth allocation problem in dry bulk terminals," Journal of Scheduling, Springer, vol. 20(5), pages 459-473, October.
    4. Yang, Weibo & Ke, Liangjun & Wang, David Z.W. & Lam, Jasmine Siu Lee, 2021. "A branch-price-and-cut algorithm for the vehicle routing problem with release and due dates," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 145(C).
    5. Daniel Oliveira & Artur Pessoa, 2020. "An Improved Branch-Cut-and-Price Algorithm for Parallel Machine Scheduling Problems," INFORMS Journal on Computing, INFORMS, vol. 32(1), pages 90-100, January.
    6. Lu Zhen & Qian Sun & Wei Zhang & Kai Wang & Wen Yi, 2021. "Column generation for low carbon berth allocation under uncertainty," Journal of the Operational Research Society, Taylor & Francis Journals, vol. 72(10), pages 2225-2240, October.
    7. Bierwirth, Christian & Meisel, Frank, 2010. "A survey of berth allocation and quay crane scheduling problems in container terminals," European Journal of Operational Research, Elsevier, vol. 202(3), pages 615-627, May.
    8. Shang, Xiao Ting & Cao, Jin Xin & Ren, Jie, 2016. "A robust optimization approach to the integrated berth allocation and quay crane assignment problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 94(C), pages 44-65.
    9. Rodrigues, Filipe & Agra, Agostinho, 2022. "Berth allocation and quay crane assignment/scheduling problem under uncertainty: A survey," European Journal of Operational Research, Elsevier, vol. 303(2), pages 501-524.
    10. Unsal, Ozgur & Oguz, Ceyda, 2019. "An exact algorithm for integrated planning of operations in dry bulk terminals," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 126(C), pages 103-121.
    11. George B. Dantzig & Philip Wolfe, 1960. "Decomposition Principle for Linear Programs," Operations Research, INFORMS, vol. 8(1), pages 101-111, February.
    12. Ruslan Sadykov & François Vanderbeck & Artur Pessoa & Issam Tahiri & Eduardo Uchoa, 2019. "Primal Heuristics for Branch and Price: The Assets of Diving Methods," INFORMS Journal on Computing, INFORMS, vol. 31(2), pages 251-267, April.
    13. Menezes, Gustavo Campos & Mateus, Geraldo Robson & Ravetti, Martín Gómez, 2017. "A branch and price algorithm to solve the integrated production planning and scheduling in bulk ports," European Journal of Operational Research, Elsevier, vol. 258(3), pages 926-937.
    14. Alan S. Manne, 1960. "On the Job-Shop Scheduling Problem," Operations Research, INFORMS, vol. 8(2), pages 219-223, April.
    15. Umang, Nitish & Bierlaire, Michel & Vacca, Ilaria, 2013. "Exact and heuristic methods to solve the berth allocation problem in bulk ports," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 54(C), pages 14-31.
    16. Ross Robinson, 2002. "Ports as elements in value-driven chain systems: the new paradigm," Maritime Policy & Management, Taylor & Francis Journals, vol. 29(3), pages 241-255.
    17. Robenek, Tomáš & Umang, Nitish & Bierlaire, Michel & Ropke, Stefan, 2014. "A branch-and-price algorithm to solve the integrated berth allocation and yard assignment problem in bulk ports," European Journal of Operational Research, Elsevier, vol. 235(2), pages 399-411.
    18. Alexandre M. Florio & Richard F. Hartl & Stefan Minner & Juan-José Salazar-González, 2021. "A Branch-and-Price Algorithm for the Vehicle Routing Problem with Stochastic Demands and Probabilistic Duration Constraints," Transportation Science, INFORMS, vol. 55(1), pages 122-138, 1-2.
    19. Ilaria Vacca & Matteo Salani & Michel Bierlaire, 2013. "An Exact Algorithm for the Integrated Planning of Berth Allocation and Quay Crane Assignment," Transportation Science, INFORMS, vol. 47(2), pages 148-161, May.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Unsal, Ozgur & Oguz, Ceyda, 2019. "An exact algorithm for integrated planning of operations in dry bulk terminals," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 126(C), pages 103-121.
    2. Zhen, Lu & Zhuge, Dan & Wang, Shuaian & Wang, Kai, 2022. "Integrated berth and yard space allocation under uncertainty," Transportation Research Part B: Methodological, Elsevier, vol. 162(C), pages 1-27.
    3. Sun, Defeng & Meng, Ying & Tang, Lixin & Liu, Jinyin & Huang, Baobin & Yang, Jiefu, 2020. "Storage space allocation problem at inland bulk material stockyard," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 134(C).
    4. Iris, Çağatay & Pacino, Dario & Ropke, Stefan & Larsen, Allan, 2015. "Integrated Berth Allocation and Quay Crane Assignment Problem: Set partitioning models and computational results," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 81(C), pages 75-97.
    5. Raeesi, Ramin & Sahebjamnia, Navid & Mansouri, S. Afshin, 2023. "The synergistic effect of operational research and big data analytics in greening container terminal operations: A review and future directions," European Journal of Operational Research, Elsevier, vol. 310(3), pages 943-973.
    6. Zhen, Lu, 2015. "Tactical berth allocation under uncertainty," European Journal of Operational Research, Elsevier, vol. 247(3), pages 928-944.
    7. Bouzekri, Hamza & Bara, Najat & Alpan, Gülgün & Giard, Vincent, 2022. "An integrated Decision Support System for planning production, storage and bulk port operations in a fertilizer supply chain," International Journal of Production Economics, Elsevier, vol. 252(C).
    8. Bierwirth, Christian & Meisel, Frank, 2015. "A follow-up survey of berth allocation and quay crane scheduling problems in container terminals," European Journal of Operational Research, Elsevier, vol. 244(3), pages 675-689.
    9. Liu, Baoli & Li, Zhi-Chun & Wang, Yadong, 2022. "A two-stage stochastic programming model for seaport berth and channel planning with uncertainties in ship arrival and handling times," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 167(C).
    10. Hamza Bouzekri & Gülgün Alpan & Vincent Giard, 2022. "Integrated Laycan and Berth Allocation Problem with ship stability and conveyor routing constraints in bulk ports," Working Papers hal-03431793, HAL.
    11. Liu, Baoli & Li, Zhi-Chun & Sheng, Dian & Wang, Yadong, 2021. "Integrated planning of berth allocation and vessel sequencing in a seaport with one-way navigation channel," Transportation Research Part B: Methodological, Elsevier, vol. 143(C), pages 23-47.
    12. Sung Won Cho & Hyun Ji Park & Chulung Lee, 2021. "An integrated method for berth allocation and quay crane assignment to allow for reassignment of vessels to other terminals," Maritime Economics & Logistics, Palgrave Macmillan;International Association of Maritime Economists (IAME), vol. 23(1), pages 123-153, March.
    13. Meixian Jiang & Jiajia Feng & Jian Zhou & Lin Zhou & Fangzheng Ma & Guanghua Wu & Yuqiu Zhang, 2023. "Multi-Terminal Berth and Quay Crane Joint Scheduling in Container Ports Considering Carbon Cost," Sustainability, MDPI, vol. 15(6), pages 1-20, March.
    14. Jia, Shuai & Li, Chung-Lun & Xu, Zhou, 2020. "A simulation optimization method for deep-sea vessel berth planning and feeder arrival scheduling at a container port," Transportation Research Part B: Methodological, Elsevier, vol. 142(C), pages 174-196.
    15. Cao, Zhen & Wang, Wenyuan & Jiang, Ying & Xu, Xinglu & Xu, Yunzhuo & Guo, Zijian, 2022. "Joint berth allocation and ship loader scheduling under the rotary loading mode in coal export terminals," Transportation Research Part B: Methodological, Elsevier, vol. 162(C), pages 229-260.
    16. Dafnomilis, I. & Duinkerken, M.B. & Junginger, M. & Lodewijks, G. & Schott, D.L., 2018. "Optimal equipment deployment for biomass terminal operations," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 115(C), pages 147-163.
    17. Kai Wang & Lu Zhen & Shuaian Wang, 2018. "Column Generation for the Integrated Berth Allocation, Quay Crane Assignment, and Yard Assignment Problem," Transportation Science, INFORMS, vol. 52(4), pages 812-834, August.
    18. Issam Krimi & Raca Todosijević & Rachid Benmansour & Mustapha Ratli & Abdessamad Ait Cadi & Afaf Aloullal, 2020. "Modelling and solving the multi-quays berth allocation and crane assignment problem with availability constraints," Journal of Global Optimization, Springer, vol. 78(2), pages 349-373, October.
    19. Bukchin, Yossi & Raviv, Tal & Zaides, Ilya, 2020. "The consecutive multiprocessor job scheduling problem," European Journal of Operational Research, Elsevier, vol. 284(2), pages 427-438.
    20. Correcher, Juan Francisco & Van den Bossche, Thomas & Alvarez-Valdes, Ramon & Vanden Berghe, Greet, 2019. "The berth allocation problem in terminals with irregular layouts," European Journal of Operational Research, Elsevier, vol. 272(3), pages 1096-1108.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:joheur:v:29:y:2023:i:1:d:10.1007_s10732-022-09506-3. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.