Metaheuristic approaches for the Berth Allocation Problem
DOI:
https://doi.org/10.2298/YJOR160518001KKeywords:
container terminal, assignment of vessels, heuristic optimization, high quality sub-optimal solutionsAbstract
Berth Allocation Problem incorporates some of the most important decisions that have to be made in order to achieve maximum efficiency in a port. Terminal manager of a port has to assign incoming vessels to the available berths, which need to be loaded/unloaded in such a way that some objective function is optimized. It is well known that even simpler variants of Berth Allocation Problem are NP-hard, and thus, metaheuristic approaches are more convenient than exact methods since they provide high quality solutions in reasonable computational time. Metaheuristics are general frameworks used to build heuristic algorithms for hard optimization problems. In this paper, an overview of promising and widely used metaheuristic methods in solving different variants of Berth Allocation Problem is presented.References
Arango, C., Cortés, P., Muñuzuri, J., and Onieva, L., “Berth allocation planning in Seville inland port by simulation and optimisation”, Advanced Engineering Informatics, 25 (3) (2011) 452–461.
Back, T., Fogel, D., and Michalewicz, Z., Handbook of Evolutionary Computation, IOP Publishing Ltd, Bristol, 1997.
Bäck, T., Fogel, D. B., and Michalewicz, Z., Evolutionary Computation 1: Basic Algorithms and Operators, Taylor & Francis Group, CRC Press, New York, 2000.
Bäck, T., Fogel, D. B., and Michalewicz, Z., Evolutionary Computation 2: Advanced Algorithms and Operators, Philadelphia: Institute of Physics Publishing, Bristol, 2000.
Bierwirth, C., and Meisel, F., “A survey of berth allocation and quay crane scheduling problems in container terminals”, European Journal of Operational Research, 202 (2010) 615–627.
Bierwirth, C., and Meisel, F., “A follow-up survey of berth allocation and quay crane scheduling problems in container terminals”, European Journal of Operational Research, 244 (3) (2015) 675–689.
Blum, C., and Roli, A., “Metaheuristics in combinatorial optimization: Overview and conceptual comparison”, ACM Computing Surveys (CSUR), 35 (3) (2003) 268–308.
Chang, D., Jiang, Z., Yan, W., and He, J., “Integrating berth allocation and quay crane assignments”, Transportation Research Part E, 46 (6) (2010) 975–990.
Chen, J. H., Lee, D.-H., and Cao, J. X., “A combinatorial Benders’ cuts algorithm for the quay side operation problem at container terminals”, Transportation Research Part E: Logistics and Transportation Review, 48 (1) (2012) 266–275.
Cheong, C., Lin, C., Tan, K., and Liu, D., “A multi-objective evolutionary algorithm for berth allocation in a container port”, Evolutionary Computation, 2007, CEC 2007, IEEE Congress on. IEEE, 2007, 927–934.
Cheong, C., and Tan, K., “A multi-objective multi-colony ant algorithm for solving the berth allocation problem”, Advances of Computational Intelligence in Industrial Systems, 2008, 333–350.
Cheong, C.Y., Tan, K.C., Liu, D.K., and Lin, C.J., “Multi-objective and prioritized berth allocation in container ports”, Annals of Operations Research, 180 (1) (2010) 63–103.
Colorni, A., Dorigo, M., and Maniezzo, V., “Distributed optimization by ant colonies”, in: Proceedings of the first European conference on artificial life, Vol. 142, Paris, France, 1991.
Cordeau, J.-F., Laporte, G., Legato, P., and Moccia, L., “Models and tabu search heuristics for the berth-allocation problem”, Transportation Science, 39 (4) (2005) 526–538.
Dai, J., Lin, W., Moorthy, R., and Teo, C.-P., “Berth allocation planning optimization in container terminals”, in: Supply Chain Analysis, 2008, 69–104.
Davidović, T., Kovač, N., and Stanimirović, Z., “VNS-based approach to minimum cost hybrid berth allocation problem”, Proc. XLII International Symposium on Operations Research, SYMOPIS 2015, Silver Lake, Serbia, 2015.
Davidović, T., Teodorović, D., and Selmić, M., “Bee colony optimization Part I: The algorithm overview”, Yugoslav Journal of Operational Research, 25 (1) (2015) 33–56.
DeOliveira, R. M., Mauri, G. R., and Lorena, L. A. N., “Clustering search for the berth allocation problem”, Expert Systems with Applications, 39 (5) (2012) 5499–5505.
Dorigo, M., and Stützle, T., “Ant colony optimization: overview and recent advances”, Technical Report, IRIDIA, Université Libre de Bruxelles, 2009.
Elwany, M., Ali, I., and Abouelseoud, Y., “A heuristics-based solution to the continuous berth allocation and crane assignment problem”, Alexandria Engineering Journal, 52 (4) (2013) 671–677.
Feo, T., and Resende, M., “A probabilistic heuristic for a computationally difficult set covering problem”, Operations Research Letters, 8 (2) (1989) 67–71.
Ganji, S., Babazadeh, A., and Arabshahi, N., “Analysis of the continuous berth allocation problem in container ports using a genetic algorithm”, Journal of Marine Science and Technology, 15 (4) (2010) 408–416.
Gendreau, M., An Introduction to Tabu Search, Springer, New York, 2003.
Giallombardo, G., Moccia, L., Salani, M., and Vacca, I., “Modeling and solving the tactical berth allocation problem”, Transportation Research Part B: Methodological, 44 (2) (2010) 232–245.
Glover, F., “Future paths for integer programming and links to artificial intelligence”, Computers & Operations Research, 13 (5) (1986) 533–549.
Golias, M., Boile, M., and Theofanis, S., “The berth allocation problem: a formulation reflecting time window service deadlines”, Proceedings of the 48th Transportation Research Forum Annual Meeting, Boston, 2006.
Golias, M., Boile, M., and Theofanis, S., “Berth scheduling by customer service differentiation: A multi-objective approach”, Transportation Research Part E: Logistics and Transportation Review, 45 (6) (2009) 878–892.
Golias, M., Boile, M., and Theofanis, S., “Alamda-optimal based heuristic for the berth scheduling problem”, Transportation Research Part C: Emerging Technologies, 18 (5) (2010) 794–806.
Golias, M., and Haralambides, H., “Berth scheduling with variable cost functions”, Maritime Economics and Logistics, 13 (2) (2011) 174–189.
Golias, M., Portal, I., Konur, D., Kaisar, E., and Kolomvos, G., “Robust berth scheduling at marine container terminals via hierarchical optimization”, Computers & Operations Research, 41 (2014) 412–422.
Golias, M., Saharidis, G., Boile, M., Theofanis, S., and Ierapetritou, M., “The berth allocation problem: Optimizing vessel arrival time”, Maritime Economics and Logistics, 11 (4) (2009) 358–377.
Günther, H.-O., and Kim, K. H., Container Terminals and Automated Transport Systems, Springer, New York, 2005.
Han, M., Li, P., and Sun, J., “The algorithm for berth scheduling problem by the hybrid optimization strategy gasa”, 9th Int. Conf. Control, Automation, Robotics and Vision, ICARCV’06, IEEE, 2006.
Han, X.-l., Lu, Z.-q., Xi, L.-f., et al., “A proactive approach for simultaneous berth and quay crane scheduling problem with stochastic arrival and handling time”, European Journal of Operational Research, 207 (3) (2010) 1327–1340.
Hansen, P., Mladenović, N., Brimberg, J., and Moreno Pérez, J. A., “Variable neighborhood search”, in: Gendreau, M., Potvin, J.-Y. (eds.), Handbook of Metaheuristics, Springer, New York Dordrecht Heidelberg London, 2010, 61–86.
Hansen, P., Oğuz, C., and Mladenović, N., “Variable neighborhood search for minimum cost berth allocation”, European Journal of Operational Research, 191 (3) (2008) 636–649.
Hendriks, M., Armbruster, D., Laumanns, M., Lefeber, E., and Udding, J., “Strategic allocation of cyclically calling vessels for multi-terminal container operators”, Flexible Services and Manufacturing Journal, 24 (3) (2012) 248–273.
Holland, J. H., Adaptation in Natural and Artificial Systems, The University of Michigan Press, Ann Arbor, 1975.
Hu, Q.-M., Hu, Z.-H., and Du, Y., “Berth and quay-crane allocation problem considering fuel consumption and emissions from vessels”, Computers & Industrial Engineering, 70 (2014) 1–10.
Imai, A., Nagaiwa, K., and Tat, C. W., “Efficient planning of berth allocation for container terminals in Asia”, Journal of Advanced Transportation, 31 (1) (1997) 75–94.
Imai, A., Nishimura, E., Hattori, M., and Papadimitriou, S., “Berth allocation at indented berths for mega-containerships”, European Journal of Operational Research, 179 (2) (2007) 579–593.
Imai, A., Zhang, J.-T., Nishimura, E., and Papadimitriou, S., “The berth allocation problem with service time and delay time objectives”, Maritime Economics & Logistics, 9 (4) (2007) 269–290.
Joslin, D., and Clements, D., “Squeaky wheel optimization”, Journal of Artificial Intelligence Research, (1999) 353–373.
Karafa, J., Golias, M., Ivey, S., Saharidis, G., and Leonardos, N., “The berth allocation problem with stochastic vessel handling times”, The International Journal of Advanced Manufacturing Technology, 65 (1-4) (2013) 473–484.
Kemme, N., Design and Operation of Automated Container Storage Systems, Springer Science & Business Media, New York, 2012.
Kennedy, J., and Eberhart, R., “Particle swarm optimization”, Proceedings of IEEE International Conference on Neural Networks IV, 1995, 1942–1948.
Kim, K. H., and Moon, K. C., “Berth scheduling by simulated annealing”, Transportation Research Part B, 37 (6) (2003) 541–560.
Kirkpatrick, S., Gelatt, C., and Vecchi, M., “Optimization by simulated annealing”, Science, New Series, 220 (4598) (1983) 671–680.
Kordić, S., Dragović, B., Davidović, T., and Kovač, N., “A combinatorial algorithm for berth allocation problem in container port”, The 2012 International Association of Maritime Economists Conference, IAME 2012, Taipei, 2012.
Kordić, S., Kovač, N., and Davidović, T., “Divide and conquer approach to discrete berth allocation problem”, XIII Balkan Conference on Operational Research (BALCOR, 2015), Constanta, Romania, 2015, 307–316.
Kovač, N., “Bee colony optimization algorithm for the minimum cost berth allocation problem”, XI Balkan Conference on Operational Research, BALCOR 2013, Beograd-Zlatibor, Serbia, 2013, 245–254.
Kovač, N., Davidović, T., and Stanimirović, Z., “Evolutionary algorithm for the minimum cost hybrid berth allocation problem”, in: 6th IEEE International Conference on Information, Intelligence, Systems and Applications (IISA 2015), Corfu, 2015.
Lalla-Ruiz, E., González-Velarde, J., Melían-Batista, B., and Moreno-Vega, J., “Biased random key genetic algorithm for the tactical berth allocation problem”, Applied Soft Computing, 22 (2014) 60–76.
Lalla-Ruiz, E., Melían-Batista, B., and Moreno-Vega, J., “Artificial intelligence hybrid heuristic based on tabu search for the dynamic berth allocation problem”, Engineering Applications of Artificial Intelligence, 25 (6) (2012) 1132–1141.
Lalla-Ruiz, E., and Voß, S., “Towards a matheuristic approach for the berth allocation problem”, In: Learning and Intelligent Optimization, Springer, Cham, 2014, 218–222.
Lee, D.-H., Chen, J., and Cao, J., “The continuous berth allocation problem: A greedy randomized adaptive search solution”, Transportation Research Part E: Logistics and Transportation Review, 46 (6) (2010) 1017–1029.
Lee, D.-H., and Jin, J., “Feeder vessel management at container transshipment terminals”, Transportation Research Part E: Logistics and Transportation Review, 49 (1) (2013) 201–216.
Lee, D.-H., Jin, J., and Chen, J., “Terminal and yard allocation problem for a container transshipment hub with multiple terminals”, Transportation Research Part E: Logistics and Transportation Review, 48 (2) (2012) 516–528.
Liang, C., Guo, J., and Yang, Y., “Multi-objective hybrid genetic algorithm for quay crane dynamic assignment in berth allocation planning”, Journal of Intelligent Manufacturing, 22 (3) (2011) 471–479.
Liang, C., Hwang, H., and Gen, M., “A berth allocation planning problem with direct transshipment consideration”, Journal of Intelligent Manufacturing, 23 (6) (2012) 2207–2214.
Lim, A., “The berth planning problem”, Operations Research Letters, 22 (2) (1998) 105–110.
Mauri, G., de Andrade, L., and Lorena, L., “A memetic algorithm for a continuous case of the berth allocation problem”, In: Proceedings of the International Conference on Evolutionary Computation Theory and Applications - Volume 1: ECTA, (IJCCI 2011), 2011, 105–113.
Meisel, F., and Bierwirth, C., “Heuristics for the integration of crane productivity in the berth allocation problem”, Transportation Research Part E, 45 (2009) 196–209.
Meisel, F., and Bierwirth, C., “A framework for integrated berth allocation and crane operations planning in seaport container terminals”, Transportation Science, 47 (2) (2013) 131–147.
Mladenović, N., and Hansen, P., “Variable neighborhood search”, Computers & Operations Research, 24 (11) (1997) 1097–1100.
Moscato, P., and Norman, M., “A competitive and cooperative approach to complex combinatorial search”, in: Proceedings of the 20th Informatics and Operations Research Meeting (20th Jornadas Argentinas de Informatica e Investigacion Operativa) (JAIIO 1991), Buenos Aires, Argentina, 1991, 3.15–3.29.
Neri, F., Cotta, C., and Moscato, P., Handbook of Memetic Algorithms, Springer-Verlag, Berlin, 2012.
Reeves, C. R., “Genetic algorithms”, in: Gendreau, M., Potvin, J.-Y. (eds.), Handbook of Metaheuristics, (second edition) Springer, New York, 2010, 109–139.
Resende, M. G. C., and Ribeiro, C. C., “Greedy randomized adaptive search procedures: Advances, hybridizations, and applications”, in: Gendreau, M., Potvin, J.-Y. (Eds.), Handbook of Metaheuristics, (second edition) Springer, New York, 2010, 283–319.
Robenek, T., Umang, N., Bierlaire, M., and Ropke, S., “A branch-and-price algorithm to solve the integrated berth allocation and yard assignment problem in bulk ports”, European Journal of Operational Research, 235 (2) (2014) 399–411.
Rodriguez-Molins, M., Ingolotti, L., Barber, F., Salido, M., Sierra, M., and Puente, J., “A genetic algorithm for robust berth allocation and quay crane assignment”, Progress in Artificial Intelligence, 2 (4) (2014) 177–192.
Rodriguez-Molins, M., Salido, M., and Barber, F., “A grasp-based metaheuristic for the berth allocation problem and the quay crane assignment problem by managing vessel cargo holds”, Applied Intelligence, 40 (2) (2014) 273–290.
Saharidis, G., Golias, M., Boile, M., Theofanis, S., and Ierapetritou, M., “The berth scheduling problem with customer differentiation: a new methodological approach based on hierarchical optimization”, The International Journal of Advanced Manufacturing Technology, 46 (1-4) (2010) 377–393.
Salido, M., Rodriguez-Molins, M., and Barber, F., “Integrated intelligent techniques for remars shaling and berthing in maritime terminals”, Advanced Engineering Informatics, 25 (3) (2011) 435–451.
Salido, M., Rodriguez-Molins, M., and Barber, F., “A decision support system for managing combinatorial problems in container terminals”, Knowledge-Based Systems, 29 (2012) 63–74.
Song, L., Cherrett, T., and Guan, W., “Study on berth planning problem in a container seaport: Using an integrated programming approach”, Computers & Industrial Engineering, 62 (1) (2012) 119–128.
Suman, B., and Kumar, P., “A survey of simulated annealing as a tool for single and multi-objective optimization”, Journal of the Operational Research Society, 57 (10) (2006) 1143–1160.
Taillard, É., and Voss, S., “POPMUSIC- Partial Optimization Metaheuristic Under Special Intensification Conditions”, Essays and Surveys in Metaheuristics, Springer, New York, 2002, 613–629.
Talbi, E.-G., Metaheuristics: From Design to Implementation, John Wiley & Sons, Inc., Hoboken, New Jersey, 2009.
Teodorović, D., Šelmić, M., and Davidović, T., “Bee colony optimization Part II: The application survey”, Yugoslav Journal of Operations Research, 25 (2) (2015) 185–219.
Theofanis, S., Boile, M., and Golias, M., “An optimization-based genetic algorithm heuristic for the berth allocation problem”, IEEE Congress on Evolutionary Computation, CEC 2007, Singapore, Singapore, 2007, 4439–4445.
Ting, C.-J., Wu, K.-C., and Chou, H., “Particle swarm optimization algorithm for the berth allocation problem”, Expert Systems with Applications, 41 (4) (2014) 1543–1550.
Umang, N., Bierlaire, M., and Vacca, I., “The berth allocation problem in bulk ports”, 11th Swiss Transport Research Conference, Monte Verita, Switzerland, No. EPFL-CONF-167446, 2011.
Umang, N., Bierlaire, M., and Vacca, I., “Exact and heuristic methods to solve the berth allocation problem in bulk ports”, Transportation Research Part E: Logistics and Transportation Review, 54 (2013) 14–31.
Ursavas, E., “Priority control of berth allocation problem in container terminals”, Annals of Operations Research, doi: 10.1007/s10479-015-1912-7, (2015) 1–20.
Vacca, I., Salani, M., and Bierlaire, M., “An exact algorithm for the integrated planning of berth allocation and quay crane assignment”, Transportation Science, 47 (2) (2013) 148–161.
Xu, Y., Chen, Q., and Quan, X., “Robust berth scheduling with uncertain vessel delay and handling time”, Annals of Operations Research, 192 (1) (2012) 123–140.
Yang, C., Wang, X., and Li, Z., “An optimization approach for coupling problem of berth allocation and quay crane assignment in container terminal”, Computers & Industrial Engineering, 63 (1) (2012) 243–253.
Yu, X., and Gen, M., Introduction to Evolutionary Algorithms, Springer Science & Business Media, London, 2010.
Zeng, Q., Hu, X., Wang, W., and Fang, Y., “Disruption management model and its algorithms for berth allocation problem in container terminals”, International Journal of Innovative Computing, Information and Control, 7 (5) (2011) 2130–2142.
Zhang, Y., Wang, S., and Ji, G., “A comprehensive survey on particle swarm optimization algorithm and its applications”, Mathematical Problems in Engineering, doi: 10.1155/2015/931256, (2015) 1–38.
Zhen, L., Chew, E., and Lee, L., “An integrated model for berth template and yard template planning in transshipment hubs”, Transportation Science, 45 (4) (2011) 483–504.
Zhen, L., Lee, L., and Chew, E., “A decision model for berth allocation under uncertainty”, European Journal of Operational Research, 212 (1) (2011) 54–68.
Zhou, P., and Kang, H., “Study on berth and quay-crane allocation under stochastic environments in container terminal”, Systems Engineering-Theory and Practice, 28 (1) (2008) 161–169.
Zhou, P., Kang, H., and Lin, L., “A dynamic berth allocation model based on stochastic consideration”, The Sixth World Congress on Intelligent Control and Automation, 2006. WCICA 2006, Dalian, China, Vol. 2, 2006, 7297–7301.
Downloads
Published
Issue
Section
License
Copyright (c) 2017 YUJOR
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
