Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Modelling and solving the multi-quays berth allocation and crane assignment problem with availability constraints

  • Published:
Journal of Global Optimization Aims and scope Submit manuscript

Abstract

In this work, we are interested in the multi-quays berth allocation and crane assignment problem under availability restrictions. Availability restrictions may arise due weather conditions, or when, for example, cranes must undergo planned maintenance in order to stay in good performance. This problem was inspired by a real-case of a bulk port in Morocco. To solve the problem we propose at first a mixed-integer programming model. Then, in view of the limitations of the proposed model, we investigate a set of heuristics based on general variable neighborhood search with three variants of variable neighborhood descent as a local search. To validate the proposed model and the proposed heuristic approach, real-world instances are used. The computational results reveal that CPLEX MIP solver consumes a lot of CPU time to solve this model, even sometimes failing to guarantee the optimality of the provided solution. On the other hand, the proposed GVNS heuristic turns out to be very efficient in solving the considered problem.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Agra, A., Oliveira, M.: Mip approaches for the integrated berth allocation and quay crane assignment and scheduling problem. Eur. J. Oper. Res. 264(1), 138–148 (2018)

    Article  MathSciNet  MATH  Google Scholar 

  2. Barros, V.H., Costa, T.S., Oliveira, A.C., Lorena, L.A.: Model and heuristic for berth allocation in tidal bulk ports with stock level constraints. Comput. Ind. Eng. 60(4), 606–613 (2011)

    Article  Google Scholar 

  3. Becker, C., Scholl, A.: A survey on problems and methods in generalized assembly line balancing. Eur. J. Oper. Res. 168(3), 694–715 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  4. Bierwirth, C., Meisel, F.: A follow-up survey of berth allocation and quay crane scheduling problems in container terminals. Eur. J. Oper. Res. 244(3), 675–689 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  5. Blazewicz, J., Cheng, T.E., Machowiak, M., Oguz, C.: Berth and quay crane allocation: a moldable task scheduling model. J. Oper. Res. Soc. 62(7), 1189–1197 (2011)

    Article  Google Scholar 

  6. Chang, D., Jiang, Z., Yan, W., He, J.: Integrating berth allocation and quay crane assignments. Transp. Res. Part E: Logist Transp. Rev. 46(6), 975–990 (2010)

    Article  Google Scholar 

  7. Correcher, J.F., Alvarez-Valdes, R.: A biased random-key genetic algorithm for the time-invariant berth allocation and quay crane assignment problem. Expert Syst. Appl. 89, 112–128 (2017)

    Article  Google Scholar 

  8. Correcher, J.F., Alvarez-Valdes, R., Tamarit, J.M.: A New Mixed Integer Linear Model for the Berth Allocation and Quay Crane Assignment problem. Department of Statistics and Operations Research. University of Valencia, Valencia (2017)

    MATH  Google Scholar 

  9. Diabat, A., Theodorou, E.: An integrated quay crane assignment and scheduling problem. Comput. Ind. Eng. 73, 115–123 (2014)

    Article  Google Scholar 

  10. Ernst, A.T., Oğuz, C., Singh, G., Taherkhani, G.: Mathematical models for the berth allocation problem in dry bulk terminals. J. Sched. 20(5), 459–473 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  11. Fu, Y.M., Diabat, A.: A Lagrangian relaxation approach for solving the integrated quay crane assignment and scheduling problem. Appl. Math. Model. 39(3–4), 1194–1201 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  12. Giallombardo, G., Moccia, L., Salani, M., Vacca, I.: Modeling and solving the tactical berth allocation problem. Transp. Res. Part B: Methodol. 44(2), 232–245 (2010)

    Article  Google Scholar 

  13. Mladenović, N., Hansen, P.: Variable neighborhood search. Comput. Oper. Res. 24(11), 1097–1100 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  14. Hansen, P., Mladenović, N., Todosijević, R., Hanafi, S.: Variable neighborhood search: basics and variants. EURO J. Comput. Optim. 5(3), 423–454 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  15. Hansen, P., Oğuz, C., Mladenović, N.: Variable neighborhood search for minimum cost berth allocation. Eur. J. Oper. Res. 191(3), 636–649 (2008)

    Article  MATH  Google Scholar 

  16. Iris, Ç., Pacino, D., Ropke, S.: Improved formulations and an adaptive large neighborhood search heuristic for the integrated berth allocation and quay crane assignment problem. Transp. Res. Part E: Logist. Transp. Rev. 105, 123–147 (2017)

    Article  Google Scholar 

  17. Iris, Ç., Pacino, D., Ropke, S., Larsen, A.: Integrated berth allocation and quay crane assignment problem: set partitioning models and computational results. Transp. Res. Part E: Logist. Transp. Rev. 81, 75–97 (2015)

    Article  Google Scholar 

  18. Lalla-Ruiz, E., Expósito-Izquierdo, C., Melián-Batista, B., Moreno-Vega, J.M.: A set-partitioning-based model for the berth allocation problem under time-dependent limitations. Eur. J. Oper. Res. 250(3), 1001–1012 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  19. Liang, C., Huang, Y., Yang, Y.: A quay crane dynamic scheduling problem by hybrid evolutionary algorithm for berth allocation planning. Comput. Ind. Eng. 56(3), 1021–1028 (2009)

    Article  Google Scholar 

  20. Meisel, F., Bierwirth, C.: Heuristics for the integration of crane productivity in the berth allocation problem. Transp. Res. Part E: Logist. Transp. Rev. 45(1), 196–209 (2009)

    Article  Google Scholar 

  21. Mjirda, A., Todosijević, R., Hanafi, S., Hansen, P., Mladenović, N.: Sequential variable neighborhood descent variants: an empirical study on the traveling salesman problem. Int. Trans. Oper. Res. 24(3), 615–633 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  22. Park, Y.M., Kim, K.H.: A scheduling method for berth and quay cranes. In: Container Terminals and Automated Transport Systems, pp. 159–181. Springer (2005)

  23. Pratap, S., Nayak, A., Kumar, A., Cheikhrouhou, N., Tiwari, M.K.: An integrated decision support system for berth and ship unloader allocation in bulk material handling port. Comput. Ind. Eng 106, 386–399 (2017)

    Article  Google Scholar 

  24. Raa, B., Dullaert, W., Van Schaeren, R.: An enriched model for the integrated berth allocation and quay crane assignment problem. Expert Syst. Appl. 38(11), 14136–14147 (2011)

    Google Scholar 

  25. Rodriguez-Molins, M., Salido, M.A., Barber, F.: A grasp-based metaheuristic for the berth allocation problem and the quay crane assignment problem by managing vessel cargo holds. Appl. Intell 40(2), 273–290 (2014)

    Article  Google Scholar 

  26. Umang, N., Bierlaire, M., Vacca, I.: Exact and heuristic methods to solve the berth allocation problem in bulk ports. Transp. Res. Part E: Logist. Transp. Rev. 54, 14–31 (2013)

    Article  Google Scholar 

  27. Vacca, I., Salani, M., Bierlaire, M.: An exact algorithm for the integrated planning of berth allocation and quay crane assignment. Transp. Sci. 47(2), 148–161 (2013)

    Article  Google Scholar 

  28. Xu, D., Li, C.L., Leung, J.Y.T.: Berth allocation with time-dependent physical limitations on vessels. Eur. J. Oper. Res. 216(1), 47–56 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  29. Yang, C., Wang, X., Li, Z.: An optimization approach for coupling problem of berth allocation and quay crane assignment in container terminal. Comput. Ind. Eng. 63(1), 243–253 (2012)

    Article  Google Scholar 

  30. Yu, T., Qiang, Z., Benfei, Z.: A genetic algorithm based on spatiotemporal conflict between continuous berth-allocation and time-varying specific crane assignment. Eng. Optim. 51(3), 1–22 (2019)

    Article  MathSciNet  Google Scholar 

Download references

Acknowledgements

This work has been supported by ELSAT project, which is co-financed by the European Union with the European Regional Development Fund, the French state and the Hauts de France Region Council. We would like to thank the reviewers for their insightful comments on the paper.

Author information

Authors and Affiliations

  1. Situation Innovation, OCP Group, Jorf Lasfar, Morocco

    Issam Krimi

  2. Innovation Lab for Operations, Mohamed 6 Polytechnic University, Ben Guerir, Morocco

    Issam Krimi & Afaf Aloullal

  3. LAMIH UMR CNRS 8201, Université Polytechnique Hauts de France, Valenciennes, France

    Issam Krimi, Raca Todosijević, Rachid Benmansour, Mustapha Ratli & Abdessamad Ait El Cadi

  4. Mohammadia School of Engineers, Mohammed 5 University, Rabat, Morocco

    Issam Krimi

  5. SI2M Laboratory, INSEA, Rabat, Morocco

    Rachid Benmansour

Authors
  1. Issam Krimi
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Raca Todosijević
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Rachid Benmansour
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Mustapha Ratli
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Abdessamad Ait El Cadi
    View author publications

    You can also search for this author in PubMed Google Scholar

  6. Afaf Aloullal
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Raca Todosijević.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Appendices

Appendix A1

Here we present the procedure to construct a feasible planning for each vessel (see Fig. 1).

Fig. 1
figure 1

Constructive heuristic for generating a feasible planning

Full size image

Appendix A2

Here, we provide the detailed comparison of three different VNDs (basic sequential VND, pipe VND and cyclic VND) using different orders of neighborhood classes. We distinguish 6 different orders of neighborhood classes because we have three neighborhood classes. The distinguished orders are as follows:

  • order 1: inter-quay neighborhoods, intra-quay neighborhoods, and crane assignment neighborhood;

  • order 2: inter-quay neighborhoods, crane assignment neighborhood, and intra-quay neighborhoods;

  • order 3: intra-quay neighborhoods, inter-quay neighborhoods, and crane assignment neighborhood;

  • order 4: intra-quay neighborhoods, crane assignment neighborhood, and inter-quay neighborhoods;

  • order 5: crane assignment neighborhood, intra-quay neighborhoods, and inter-quay neighborhoods;

  • order 6: crane assignment neighborhood, inter-quay neighborhoods, and intra-quay neighborhoods;

As stated in Sect. 4, the order of neighborhoods within each class is set according to the increasing cardinality. In the intra-quay neighborhoods class the order is: Intra-quay insert, Intra-quay swap , Intra-quay reverse neighborhood; while in the inter-quay the order is Inter-quay insert and Inter-quay swap neighborhood.

Each variant is employed within the GVNS scheme (Algorithm 7) using 6 different orders. For testing purposes we used the set of largest instances with the number of vessels equal to 14. The summary results are provided in Table 4. For each variant and each order of neighborhood classes we report the average solution value and average CPU time consumption in minutes over the set of largest instances.

Table 4 Comparison of VNDs with different orders of neighborhoods
Full size table

From the presented results, we infer that the best order for the basic sequential VND is “order 6”, while for the others the best order is “order 2”. Among all tested variants, the best overall performance has been exhibited by pipe VND employing “order 2”.

Appendix A3

Detailed results for entire data set are presented in Tables 5, 6, 7, 8, 9, 10. The emphasized values in the tables represent solution values found by CPLEX, but which optimality were not proven within 2 h of computation time.

Table 5 Results on instances with \(n=6\)
Full size table
Table 6 Results on instances with \(n=7\)
Full size table
Table 7 Results on instances with \(n=8\)
Full size table
Table 8 Results on instances with \(n=10\)
Full size table
Table 9 Results on instances with \(n=12\)
Full size table
Table 10 Results on instances with \(n=14\)
Full size table

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Krimi, I., Todosijević, R., Benmansour, R. et al. Modelling and solving the multi-quays berth allocation and crane assignment problem with availability constraints. J Glob Optim 78, 349–373 (2020). https://doi.org/10.1007/s10898-020-00884-1

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10898-020-00884-1

Keywords

Search

Navigation