IDEAS home Printed from https://ideas.repec.org/a/eee/transe/v87y2016icp167-185.html
   My bibliography  Save this article

Evaluating the solution performance of IP and CP for berth allocation with time-varying water depth

Author

Listed:
  • Qin, Tianbao
  • Du, Yuquan
  • Sha, Mei

Abstract

This paper considers the berth allocation problem (BAP) with time-varying water depth at a tidal river port. Both integer programming (IP) and constraint programming (CP) models are developed. Numerical experiments find that CP tends to be superior to IP when the feasible domain is small (e.g. dynamic vessel arrivals), when the restriction of the objective towards decision variables is loose (e.g. makespan, departure delay), or when the size of IP models is too large due to fine time resolution. Meanwhile, CP’s incapability of proving optimality can be compensated by post-optimization with IP, by using a simple CP/IP hybrid procedure.

Suggested Citation

  • Qin, Tianbao & Du, Yuquan & Sha, Mei, 2016. "Evaluating the solution performance of IP and CP for berth allocation with time-varying water depth," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 87(C), pages 167-185.
    • Handle: RePEc:eee:transe:v:87:y:2016:i:c:p:167-185
    DOI: 10.1016/j.tre.2016.01.007
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S1366554516000077
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.tre.2016.01.007?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. Louis-Martin Rousseau & Michel Gendreau & Gilles Pesant & Filippo Focacci, 2004. "Solving VRPTWs with Constraint Programming Based Column Generation," Annals of Operations Research, Springer, vol. 130(1), pages 199-216, August.
    2. Jean-François Cordeau & Gilbert Laporte & Pasquale Legato & Luigi Moccia, 2005. "Models and Tabu Search Heuristics for the Berth-Allocation Problem," Transportation Science, INFORMS, vol. 39(4), pages 526-538, November.
    3. Meisel, Frank & Bierwirth, Christian, 2009. "Heuristics for the integration of crane productivity in the berth allocation problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 45(1), pages 196-209, January.
    4. 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.
    5. Zhen, Lu & Lee, Loo Hay & Chew, Ek Peng, 2011. "A decision model for berth allocation under uncertainty," European Journal of Operational Research, Elsevier, vol. 212(1), pages 54-68, July.
    6. Pedro M. Castro & Ignacio E. Grossmann & Louis-Martin Rousseau, 2011. "Decomposition Techniques for Hybrid MILP/CP Models applied to Scheduling and Routing Problems," Springer Optimization and Its Applications, in: Pascal van Hentenryck & Michela Milano (ed.), Hybrid Optimization, edition 1, pages 135-167, Springer.
    7. Vipul Jain & Ignacio E. Grossmann, 2001. "Algorithms for Hybrid MILP/CP Models for a Class of Optimization Problems," INFORMS Journal on Computing, INFORMS, vol. 13(4), pages 258-276, November.
    8. Lee, Der-Horng & Chen, Jiang Hang & Cao, Jin Xin, 2010. "The continuous Berth Allocation Problem: A Greedy Randomized Adaptive Search Solution," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 46(6), pages 1017-1029, November.
    9. Yongpei Guan & Kang-hung Yang, 2010. "Analysis of berth allocation and inspection operations in a container terminal," Maritime Economics & Logistics, Palgrave Macmillan;International Association of Maritime Economists (IAME), vol. 12(4), pages 347-369, December.
    10. Imai, Akio & Nishimura, Etsuko & Hattori, Masahiro & Papadimitriou, Stratos, 2007. "Berth allocation at indented berths for mega-containerships," European Journal of Operational Research, Elsevier, vol. 179(2), pages 579-593, June.
    11. Emde, Simon & Boysen, Nils & Briskorn, Dirk, 2014. "The berth allocation problem with mobile quay walls: problem definition, solution procedures, and extensions," Publications of Darmstadt Technical University, Institute for Business Studies (BWL) 79440, Darmstadt Technical University, Department of Business Administration, Economics and Law, Institute for Business Studies (BWL).
    12. Rasmussen, Rasmus V. & Trick, Michael A., 2007. "A Benders approach for the constrained minimum break problem," European Journal of Operational Research, Elsevier, vol. 177(1), pages 198-213, February.
    13. Han, Xiao-le & Lu, Zhi-qiang & Xi, Li-feng, 2010. "A proactive approach for simultaneous berth and quay crane scheduling problem with stochastic arrival and handling time," European Journal of Operational Research, Elsevier, vol. 207(3), pages 1327-1340, December.
    14. Kim, Kap Hwan & Moon, Kyung Chan, 2003. "Berth scheduling by simulated annealing," Transportation Research Part B: Methodological, Elsevier, vol. 37(6), pages 541-560, July.
    15. Xu, Dongsheng & Li, Chung-Lun & Leung, Joseph Y.-T., 2012. "Berth allocation with time-dependent physical limitations on vessels," European Journal of Operational Research, Elsevier, vol. 216(1), pages 47-56.
    16. J. N. Hooker, 2007. "Planning and Scheduling by Logic-Based Benders Decomposition," Operations Research, INFORMS, vol. 55(3), pages 588-602, June.
    17. Edis, Emrah B. & Oguz, Ceyda & Ozkarahan, Irem, 2013. "Parallel machine scheduling with additional resources: Notation, classification, models and solution methods," European Journal of Operational Research, Elsevier, vol. 230(3), pages 449-463.
    18. Imai, Akio & Nishimura, Etsuko & Papadimitriou, Stratos, 2001. "The dynamic berth allocation problem for a container port," Transportation Research Part B: Methodological, Elsevier, vol. 35(4), pages 401-417, May.
    19. 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.
    20. Nizar El Hachemi & Michel Gendreau & Louis-Martin Rousseau, 2011. "A hybrid constraint programming approach to the log-truck scheduling problem," Annals of Operations Research, Springer, vol. 184(1), pages 163-178, April.
    21. Imai, Akio & Yamakawa, Yukiko & Huang, Kuancheng, 2014. "The strategic berth template problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 72(C), pages 77-100.
    22. Tallys Yunes & Ionuţ D. Aron & J. N. Hooker, 2010. "An Integrated Solver for Optimization Problems," Operations Research, INFORMS, vol. 58(2), pages 342-356, April.
    23. Yuquan Du & Qiushuang Chen & Jasmine Siu Lee Lam & Ya Xu & Jin Xin Cao, 2015. "Modeling the Impacts of Tides and the Virtual Arrival Policy in Berth Allocation," Transportation Science, INFORMS, vol. 49(4), pages 939-956, November.
    24. Buhrkal, Katja & Zuglian, Sara & Ropke, Stefan & Larsen, Jesper & Lusby, Richard, 2011. "Models for the discrete berth allocation problem: A computational comparison," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 47(4), pages 461-473, July.
    25. John N. Hooker, 2012. "Integrated Methods for Optimization," International Series in Operations Research and Management Science, Springer, number 978-1-4614-1900-6, September.
    26. 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.
    27. Lee, Yusin & Chen, Chuen-Yih, 2009. "An optimization heuristic for the berth scheduling problem," European Journal of Operational Research, Elsevier, vol. 196(2), pages 500-508, July.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. David Sacramento & Christine Solnon & David Pisinger, 2020. "Constraint Programming and Local Search Heuristic: a Matheuristic Approach for Routing and Scheduling Feeder Vessels in Multi-terminal Ports," SN Operations Research Forum, Springer, vol. 1(4), pages 1-33, December.
    2. 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.
    3. Jaap-Jan Steeg & Menno Oudshoorn & Neil Yorke-Smith, 2023. "Berth planning and real-time disruption recovery: a simulation study for a tidal port," Flexible Services and Manufacturing Journal, Springer, vol. 35(1), pages 70-110, March.
    4. Liu, Baoli & Li, Zhi-Chun & Wang, Yadong, 2023. "A branch-and-price heuristic algorithm for the bunkering operation problem of a liquefied natural gas bunkering station in the inland waterways," Transportation Research Part B: Methodological, Elsevier, vol. 167(C), pages 145-170.
    5. Shuai Jia & Chung-Lun Li & Zhou Xu, 2019. "Managing Navigation Channel Traffic and Anchorage Area Utilization of a Container Port," Transportation Science, INFORMS, vol. 53(3), pages 728-745, May.
    6. 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.
    7. 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.
    8. Zhen, Lu & Liang, Zhe & Zhuge, Dan & Lee, Loo Hay & Chew, Ek Peng, 2017. "Daily berth planning in a tidal port with channel flow control," Transportation Research Part B: Methodological, Elsevier, vol. 106(C), pages 193-217.

    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. 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.
    2. Feng Li & Jiuh-Biing Sheu & Zi-You Gao, 2015. "Solving the Continuous Berth Allocation and Specific Quay Crane Assignment Problems with Quay Crane Coverage Range," Transportation Science, INFORMS, vol. 49(4), pages 968-989, November.
    3. Yuquan Du & Qiushuang Chen & Jasmine Siu Lee Lam & Ya Xu & Jin Xin Cao, 2015. "Modeling the Impacts of Tides and the Virtual Arrival Policy in Berth Allocation," Transportation Science, INFORMS, vol. 49(4), pages 939-956, November.
    4. Zhen, Lu, 2015. "Tactical berth allocation under uncertainty," European Journal of Operational Research, Elsevier, vol. 247(3), pages 928-944.
    5. Xiang, Xi & Liu, Changchun, 2021. "An expanded robust optimisation approach for the berth allocation problem considering uncertain operation time," Omega, Elsevier, vol. 103(C).
    6. Shangyao Yan & Chung-Cheng Lu & Jun-Hsiao Hsieh & Han-Chun Lin, 2019. "A Dynamic and Flexible Berth Allocation Model with Stochastic Vessel Arrival Times," Networks and Spatial Economics, Springer, vol. 19(3), pages 903-927, September.
    7. Guo, Liming & Zheng, Jianfeng & Liang, Jinpeng & Wang, Shuaian, 2023. "Column generation for the multi-port berth allocation problem with port cooperation stability," Transportation Research Part B: Methodological, Elsevier, vol. 171(C), pages 3-28.
    8. Zhen, Lu & Liang, Zhe & Zhuge, Dan & Lee, Loo Hay & Chew, Ek Peng, 2017. "Daily berth planning in a tidal port with channel flow control," Transportation Research Part B: Methodological, Elsevier, vol. 106(C), pages 193-217.
    9. 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.
    10. 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.
    11. Iris, Çağatay & Pacino, Dario & Ropke, Stefan, 2017. "Improved formulations and an Adaptive Large Neighborhood Search heuristic for the integrated berth allocation and quay crane assignment problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 105(C), pages 123-147.
    12. Fanrui Xie & Tao Wu & Canrong Zhang, 2019. "A Branch-and-Price Algorithm for the Integrated Berth Allocation and Quay Crane Assignment Problem," Transportation Science, INFORMS, vol. 53(5), pages 1427-1454, September.
    13. 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.
    14. Liu, Changchun, 2020. "Iterative heuristic for simultaneous allocations of berths, quay cranes, and yards under practical situations," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 133(C).
    15. Xu, Dongsheng & Li, Chung-Lun & Leung, Joseph Y.-T., 2012. "Berth allocation with time-dependent physical limitations on vessels," European Journal of Operational Research, Elsevier, vol. 216(1), pages 47-56.
    16. Ya Xu & Kelei Xue & Yuquan Du, 2018. "Berth Scheduling Problem Considering Traffic Limitations in the Navigation Channel," Sustainability, MDPI, vol. 10(12), pages 1-22, December.
    17. Giorgi Tadumadze & Simon Emde & Heiko Diefenbach, 2020. "Exact and heuristic algorithms for scheduling jobs with time windows on unrelated parallel machines," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 42(2), pages 461-497, June.
    18. Eduardo Lalla-Ruiz & Stefan Voß & Christopher Expósito-Izquierdo & Belén Melián-Batista & J. Marcos Moreno-Vega, 2017. "A POPMUSIC-based approach for the berth allocation problem under time-dependent limitations," Annals of Operations Research, Springer, vol. 253(2), pages 871-897, June.
    19. Changchun Liu & Xi Xiang & Li Zheng, 2020. "A two-stage robust optimization approach for the berth allocation problem under uncertainty," Flexible Services and Manufacturing Journal, Springer, vol. 32(2), pages 425-452, June.
    20. 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.

    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:eee:transe:v:87:y:2016:i:c:p:167-185. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/wps/find/journaldescription.cws_home/600244/description#description .

    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.