Simulation optimization based ant colony algorithm for the uncertain quay crane scheduling problem

Abstract: This work is devoted to the study of the Uncertain Quay Crane Scheduling Problem (QCSP), where the loading /unloading times of containers and travel time of quay cranes are considered uncertain. The problem is solved with a Simulation Optimization approach which takes advantage of the great possibilities offered by the simulation to model the real details of the problem and the capacity of the optimization to find solutions with good quality. An Ant Colony Optimization (ACO) meta-heuristic hybridized with a Variable Neighborhood Descent (VND) local search is proposed to determine the assignments of tasks to quay cranes and the sequences of executions of tasks on each crane. Simulation is used inside the optimization algorithm to generate scenarios in agreement with the probabilities of the distributions of the uncertain parameters, thus, we carry out stochastic evaluations of the solutions found by each ant. The proposed optimization algorithm is tested first for the deterministic case on several well-known benchmark instances. Then, in the stochastic case, since no other work studied exactly the same problem with the same assumptions, the Simulation Optimization approach is compared with the deterministic version. The experimental results show that the optimization algorithm is competitive as compared to the existing methods and that the solutions found by the Simulation Optimization approach are more robust than those found by the optimization algorithm.

How to cite this paper

 Rouky, N., Abourraja, M., Boukachour, J., Boudebous, D., Alaoui, A & Khoukhi, F. (2019). Simulation optimization based ant colony algorithm for the uncertain quay crane scheduling problem.International Journal of Industrial Engineering Computations , 10(1), 111-132.

Refrences

Abourraja, M. N., Oudani, M., Samiri, M. Y., Boudebous, D., El Fazziki, A., Najib, M., ... & Rouky, N. (2017). A multi-agent based simulation model for rail–rail transshipment: An engineering approach for gantry crane scheduling. IEEE Access, 5, 13142-13156.
Al-Dhaheri, N., Jebali, A., & Diabat, A. (2016). A simulation-based Genetic Algorithm approach for the quay crane scheduling under uncertainty. Simulation Modelling Practice and Theory, 66, 122-138.
Bencheikh, G., Boukachour, J., & Alaoui, A. E. H. (2016). A memetic algorithm to solve the dynamic multiple runway aircraft landing problem. Journal of King Saud University-Computer and Information Sciences, 28(1), 98-109.
Benghalia, A., Boukachour, J., & Boudebous, D. (2016). Gestion du transfert interne de conteneurs: le cas du port du Havre. Logistique & Management, 24(1), 57-69.
Better, M., Glover, F., Kochenberger, G., & Wang, H. (2008). Simulation optimization: Applications in risk management. International Journal of Information Technology & Decision Making, 7(04), 571-587.
Bierwirth, C., & Meisel, F. (2009). A fast heuristic for quay crane scheduling with interference constraints. Journal of Scheduling, 12(4), 345-360.
Bierwirth, C., & Meisel, F. (2010). A survey of berth allocation and quay crane scheduling problems in container terminals. European Journal of Operational Research, 202(3), 615-627.
Bierwirth, C., & Meisel, F. (2015). A follow-up survey of berth allocation and quay crane scheduling problems in container terminals. European Journal of Operational Research, 244(3), 675-689.
Boysen, N., Briskorn, D., & Meisel, F. (2017). A generalized classification scheme for crane scheduling with interference. European Journal of Operational Research, 258(1), 343-357.
Carlo, H. J., Vis, I. F., & Roodbergen, K. J. (2015). Seaside operations in container terminals: literature overview, trends, and research directions. Flexible Services and Manufacturing Journal, 27(2-3), 224-262.
Chen, J. H., Lee, D. H., & Goh, M. (2014). An effective mathematical formulation for the unidirectional cluster-based quay crane scheduling problem. European Journal of Operational Research, 232(1), 198-208.
Chung, S. H., & Choy, K. L. (2012). A modified genetic algorithm for quay crane scheduling operations. Expert Systems with Applications, 39(4), 4213-4221.
Daganzo, C. F. (1989). The crane scheduling problem. Transportation Research Part B: Methodological, 23(3), 159-175.
Dongarra, J. J. (2014). Performance of various computers using standard linear equations software. Electrical Engineering and Computer Science Department University of Tennessee, Knoxville.
Dorigo, M., & Di Caro, G. (1999). Ant colony optimization: a new meta-heuristic. In Evolutionary Computation, 1999. CEC 99. Proceedings of the 1999 Congress on (Vol. 2, pp. 1470-1477). IEEE.
El Khoukhi, F., Boukachour, J., & Alaoui, A. E. H. (2017). The “Dual-Ants Colony”: A novel hybrid approach for the flexible job shop scheduling problem with preventive maintenance. Computers & Industrial Engineering, 106, 236-255.
ExpóSito-Izquierdo, C., González-Velarde, J. L., Melián-Batista, B., & Moreno-Vega, J. M. (2013). Hybrid estimation of distribution algorithm for the quay crane scheduling problem. Applied Soft Computing, 13(10), 4063-4076.
Figueira, G., & Almada-Lobo, B. (2014). Hybrid simulation–optimization methods: A taxonomy and discussion. Simulation Modelling Practice and Theory, 46, 118-134.
Gabrel, V., Murat, C., & Thiele, A. (2014). Recent advances in robust optimization: An overview. European Journal of Operational Research, 235(3), 471-483.
Hansen, P., Mladenović, N., & Pérez, J. A. M. (2010). Variable neighbourhood search: methods and applications. Annals of Operations Research, 175(1), 367-407.
He, J., Zhang, W., Huang, Y., & Yan, W. (2013). A simulation optimization method for internal trucks sharing assignment among multiple container terminals. Advanced Engineering Informatics, 27(4), 598-614.
Herazo-Padilla, N., Montoya-Torres, J. R., Isaza, S. N., & Alvarado-Valencia, J. (2015). Simulation-optimization approach for the stochastic location-routing problem. Journal of Simulation, 9(4), 296-311.
Hirsch, P., Palfi, A., & Gronalt, M. (2012). Solving a time constrained two-crane routing problem for material handling with an ant colony optimisation approach: an application in the roof-tile industry. International Journal of Production Research, 50(20), 6005-6021.
Jung, J. Y., Blau, G., Pekny, J. F., Reklaitis, G. V., & Eversdyk, D. (2004). A simulation based optimization approach to supply chain management under demand uncertainty. Computers & Chemical Engineering, 28(10), 2087-2106.
Kaveshgar, N., Huynh, N., & Rahimian, S. K. (2012). An efficient genetic algorithm for solving the quay crane scheduling problem. Expert Systems with Applications, 39(18), 13108-13117.
Kelly, J. P. (2002). Simulation optimization is evolving. INFORMS Journal on Computing, 14(3), 223-225.
Kim, K. H., & Park, Y. M. (2004). A crane scheduling method for port container terminals. European Journal of Operational Research, 156(3), 752-768.
Legato, P., Mazza, R. M., & Trunfio, R. (2010). Simulation-based optimization for discharge/loading operations at a maritime container terminal. OR Spectrum, 32(3), 543-567.
Lee, D. H., Wang, H. Q., & Miao, L. (2008). Quay crane scheduling with non-interference constraints in port container terminals. Transportation Research Part E: Logistics and Transportation Review, 44(1), 124-135.
Lim, A., Rodrigues, B., & Xu, Z. (2007). A m-parallel crane scheduling problem with a non‐crossing constraint. Naval Research Logistics (NRL), 54(2), 115-127.
Lim, A., Rodrigues, B., Xiao, F., & Zhu, Y. (2004). Crane scheduling with spatial constraints. Naval Research Logistics (NRL), 51(3), 386-406.
Lim, S. J., Jeong, S. J., Kim, K. S., & Park, M. W. (2006). A simulation approach for production-distribution planning with consideration given to replenishment policies. The International Journal of Advanced Manufacturing Technology, 27(5), 593-603.
López-Ibáñez, M., Dubois-Lacoste, J., Cáceres, L. P., Birattari, M., & Stützle, T. (2016). The irace package: Iterated racing for automatic algorithm configuration. Operations Research Perspectives, 3, 43-58.
Lu, Z., Han, X., Xi, L., & Erera, A. L. (2012). A heuristic for the quay crane scheduling problem based on contiguous bay crane operations. Computers & Operations Research, 39(12), 2915-2928.
Meisel, F., & Bierwirth, C. (2011). A unified approach for the evaluation of quay crane scheduling models and algorithms. Computers & Operations Research, 38(3), 683-693.
Meisel, F. (2009). Seaside operations planning in container terminals. Berlin, Heidelberg: Physica-Verlag.
Michael, P. (1995). Scheduling, theory, algorithms, and systems. Englewood Cli s, New Jersey.
Moccia, L., Cordeau, J. F., Gaudioso, M., & Laporte, G. (2006). A branch-and-cut algorithm for the quay crane scheduling problem in a container terminal. Naval Research Logistics (NRL), 53(1), 45-59.
Monaco, M. F., & Sammarra, M. (2011). Quay crane scheduling with time windows, one-way and spatial constraints. International Journal of Shipping and Transport Logistics, 3(4), 454-474.
Multimethod Simulation Software and Solutions, accessed on, Nov. 22, 2015. [Online]. Available: http://www.anylogic.com/
Nguyen, S., Zhang, M., Johnston, M., & Tan, K. C. (2013). Hybrid evolutionary computation methods for quay crane scheduling problems. Computers & Operations Research, 40(8), 2083-2093.
Peterkofsky, R. I., & Daganzo, C. F. (1990). A branch and bound solution method for the crane scheduling problem. Transportation Research Part B: Methodological, 24(3), 159-172.
Rajendran, C., & Ziegler, H. (2004). Ant-colony algorithms for permutation flowshop scheduling to minimize makespan/total flowtime of jobs. European Journal of Operational Research, 155(2), 426-438.
Rouky, N., Boukachour, J., Alaoui, A.E.H, El Khoukhi, F., & Boudebous D. (2015). Un algorithme d’optimisation par colonie de fourmis pour l’ordonnancement des grues de quai. JD-JN- MACS, Bourges, France.
Sahinidis, N. V. (2004). Optimization under uncertainty: state-of-the-art and opportunities. Computers & Chemical Engineering, 28(6), 971-983.
Sammarra, M., Cordeau, J. F., Laporte, G., & Monaco, M. F. (2007). A tabu search heuristic for the quay crane scheduling problem. Journal of Scheduling, 10(4), 327-336.
Steenken, D., Winter, T., & Zimmermann, U. T. (2001). Stowage and transport optimization in ship planning. In Online optimization of large scale systems (pp. 731-745). Springer Berlin Heidelberg.
Thiruvady, D., Ernst, A. T., & Singh, G. (2016). Parallel ant colony optimization for resource constrained job scheduling. Annals of Operations Research, 242(2), 355-372.
Tongzon, J., & Heng, W. (2005). Port privatization, efficiency and competitiveness: Some empirical evidence from container ports (terminals). Transportation Research Part A: Policy and Practice, 39(5), 405-424.
Tréfond, S., Billionnet, A., Elloumi, S., Djellab, H., & Guyon, O. (2017). Optimization and simulation for robust railway rolling-stock planning. Journal of Rail Transport Planning & Management, 7(1-2), 33-49.
UNCTAD, WID. (2014). United nations conference on trade and development. Review of Maritime Transport.
UNCTAD, WID. (2016). United nations conference on trade and development. Review of Maritime Transport.
Unsal, O., & Oguz, C. (2013). Constraint programming approach to quay crane scheduling problem. Transportation Research Part E: Logistics and Transportation Review, 59, 108-122.
Wang, Y., & Kim, K. H. (2011). A quay crane scheduling algorithm considering the workload of yard cranes in a container yard. Journal of Intelligent Manufacturing, 22(3), 459-470..
Zhou, Y., Wang, W., Song, X., & Guo, Z. (2016). Simulation-based optimization for yard design at mega container terminal under uncertainty. Mathematical Problems in Engineering, Vol. 2016.
Zhu, Y., & Lim, A. (2006). Crane scheduling with non-crossing constraint. Journal of the Operational Research Society, 57(12), 1464-1471.