Abstract
This paper considers the combination of berth and crane allocation problems in container terminals. We propose a novel approach based on constraint programming which is able to model many realistic operational constraints. The costs for berth allocation, crane allocation, time windows, breaks and transition times during gang movements are optimized simultaneously. The model is based on a resource view where gangs are consumed by vessel activities. Side constraints are added independently around this core model. The model is richer than the state of the art in the operations research community. Experiments show that the model produces solutions with a cost gap of 1/10 (7,8%) to 1/5 (18,8%) compared to an ideal operational setting where operational constraints are ignored.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Drewry Shipping Consultants Annual Container Market Review and Forecast 2007/08.A London, 250 p. (2007)
Drewry Shipping Consultants Container Forecaster 1Q08 London, 218 p. (2008)
Grossmann, H., Otto, A., Stiller, S., Wedemeier, J.: Growth Potential for Maritime Trade and Ports in Europe. Intereconomics, 226–232 (2007)
Bierwirth, C., Meisel, F.: A survey of berth allocation and quay crane scheduling problems in container terminals. European Journal of Operational Research 202, 615–627 (2010)
Moorthy, R., Teo, C.-P.: Berth management in container terminal: the template design problem. OR Spectrum 28, 495–518 (2006)
Raa, B., Dullaert, W., Van Schaeren, R.: An enriched model for the integrated berth allocation and quay crane assignment problem. Expert Systems with Applications 38(11), 14136–14147 (2011)
Zhang, C., Zheng, L., Zhang, Z., Shi, L., Armstrong, A.J.: The allocation of berths and quay cranes by using a sub-gradient optimization technique. Computers and Industrial Engineering 58, 40–50 (2010)
Achterberg, T., Berthold, T., Koch, T., Wolter, K.: Constraint Integer Programming: A New Approach to Integrate CP and MIP. In: Trick, M.A. (ed.) CPAIOR 2008. LNCS, vol. 5015, pp. 6–20. Springer, Heidelberg (2008)
Shaw, P.: Using constraint programming and local search methods to solve vehicle routing problems. In: Maher, M.J., Puget, J.-F. (eds.) CP 1998. LNCS, vol. 1520, pp. 417–431. Springer, Heidelberg (1998)
Daganzo, C.F.: The crane scheduling problem. Transportation Research Part B 23, 159–175 (1998)
Peterkofsky, R.I., Daganzo, C.F.: A branch and bound solution method for the crane scheduling problem. Transportation Research Part B 24, 159–172 (1990)
Liu, J., Wan, Y.-W., Wang, L.: Quay Crane Scheduling at Container Terminals To Minimize the Maximum Relative Tardiness of Vessel Departures. Naval Research Logistics 53, 60–74 (2006)
Yang, C., Wang, X., Li, Z.: An optimization approach for coupling problem of berth allocation and quay crane assignment in container terminal. Computers & Industrial Engineering 63, 243–253 (2012)
Song, L., Cherrett, T., Guan, W.: Study on berth planning problem in a container seaport: Using an integrated programming approach. Computers & Industrial Engineering 62, 119–128 (2012)
Han, X., Lu, Z., Xi, L.: A proactive approach for simultaneous berth and quay crane scheduling problem with stochastic arrival and handling time. European Journal of Operational Research 207, 1327–1340 (2010)
Chang, D., Jiang, Z., Yan, W., He, J.: Integrating berth allocation and quay crane assignments. Transportation Research Part E 46, 975–990 (2010)
Meisel, F., Bierwirth, C.: Heuristics for the integration of crane productivity in the berth allocation problem. Transportation Research Part E 45, 196–209 (2009)
Liang, C., Huang, Y., Yang, Y.: A quay crane dynamic scheduling problem by hybrid evolutionary algorithm for berth allocation planning. Computers & Industrial Engineering 56, 1021–1028 (2009)
Imai, A., Chen, H., Nishimura, E., Papadimitriou, S.: The simultaneous berth and quay crane allocation problem. Transportation Research Part E 44, 900–920 (2008)
Park, Y., Kim, K.: A scheduling method for Berth and Quay cranes. OR Spectrum 25, 1–23 (2003)
Zhang, C.Q., Liu, J.Y., Wan, Y.W., Murty, K.G.: Storage space allocation in container terminals. Transportation Research Part B 37, 883–903 (2003)
De Clercq, A., Petit, T., Beldiceanu, N., Jussien, N.: Filtering Algorithms for Discrete Cumulative Problems with Overloads of Resource. In: Lee, J. (ed.) CP 2011. LNCS, vol. 6876, pp. 240–255. Springer, Heidelberg (2011)
Zampelli, S., Vergados, Y., Van Schaeren, R., Dulleart, W., Birger, R.: The berth allocation and quay crane assignment problem using a CP approach Technical Report at Universiteit Antwerpen (2013), http://www.ua.ac.be/main.aspx?c=wout.dullaert&n=9300&ct=005748
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Zampelli, S., Vergados, Y., Van Schaeren, R., Dullaert, W., Raa, B. (2013). The Berth Allocation and Quay Crane Assignment Problem Using a CP Approach. In: Schulte, C. (eds) Principles and Practice of Constraint Programming. CP 2013. Lecture Notes in Computer Science, vol 8124. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-40627-0_64
Download citation
DOI: https://doi.org/10.1007/978-3-642-40627-0_64
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-40626-3
Online ISBN: 978-3-642-40627-0
eBook Packages: Computer ScienceComputer Science (R0)