A vehicle routing problem with two types of ships in container terminals

Document Type : Article


Department of Industrial Engineering, Faculty of Industrial and Mechanical Engineering, Qazvin Branch, Islamic Azad University, Qazvin, Iran


The Vehicle Routing Problem (VRP) is one of well-established and important topic in supply chain and logistic networks. The location-routing decision-making has a significant role to optimize the traveling cost per distance, total traveling time and the number of vehicles in the supply chain networks. One of recent advances in these systems refers to container terminals in the global trade centers. The new contributions of this model are to consider the routes of two types of ships (Tramp and Liner) with different properties and the time windows in order to minimize costs. The proposed is solved by an exact method (B&B) as well as because of inherent complexity of problem proposed in the real-world cases, the Genetic (GA) algorithm has been used to find an optimal/global solution in a reasonable time. Finally, an in-depth analysis and discussion is provided to conclude the main findings and practical implications of the results.


1. Dantzig, G.B. and Ramser, J.H. "The truck dispatching problem", Management Science, 6(1), pp. 80-91 (1959).
2. Clarke, G. and Wright, J.W. "Scheduling of vehicles from a central depot to a number of delivery points", Operations  Research, 12(4), pp. 568-581 (1964).
3. Toth, P. and Vigo, D., Eds., The Vehicle Routing Problem, Society for Industrial and Applied Mathematics, (2001).
4. Nasiri, M.M., Rahbari, A., Werner, F., and Karimi, R. "Incorporating supplier selection and order allocation into the vehicle routing and multi-cross-dock scheduling problem", International Journal of Production Research, 56(19), pp. 6527-6552 (2018).
5. Fathollahi-Fard, A.M., Govindan, K., Hajiaghaei-Keshteli, M., and Ahmadi, A. "A green home health care supply chain: New modified simulated annealing algorithms", Journal of Cleaner Production, 240, 118200 (2019).
6. Coelho, V.N., Grasas, A., Ramalhinho, H., Coelho, I.M., Souza, M.J.F., and Cruz, R.C. "An ILS-based algorithm to solve a large-scale real heterogeneous fleet VRP with multi-trips and docking constraints", European Journal of Operational Research, 250(2), pp. 367-376 (2016).
7. Perera, L.P. and Soares, C.G. "Weather routing and safe ship handling in the future of shipping", Ocean Engineering, 130, pp. 684-695 (2017).
8. Li, F., Golden, B., and Wasil, E. "The open vehicle routing problem: Algorithms, large-scale test problems, and computational results", Computers & Operations Research, 34(10), pp. 2918-2930 (2010).
9. Daganzo, C.F. "The crane scheduling problem", Transportation Research Part B: Methodological, 23(3), pp. 159-175 (1989).
10. Zhihong, J.I.N. and Na, L.I. "Optimization of quay crane dynamic scheduling based on berth schedules in container terminal", Journal of Transportation Systems Engineering and Information Technology, 11(3), pp. 58-64 (2011).
11. Chen, J.H., Lee, D.H., and Cao, J.X. "Heuristics for quay crane scheduling at indented berth", Transportation Research Part E: Logistics and Transportation Review, 47(6), pp. 1005-1020 (2011).
12. Legato, P., Trunfio, R., and Meisel, F. "Modeling and solving rich quay crane scheduling problems", Computers & Operations Research, 39(9), pp. 2063- 2078 (2012).
13. Chen, J.H., Lee, D.H., and Goh, M. "An effective mathematical formulation for the unidirectional cluster-based quay crane scheduling problem", European Journal of Operational Research, 232(1), pp. 198-208 (2014).
14. Imai, A., Yamakawa, Y., and Huang, K. "The strategic berth template problem", Transportation Research Part E: Logistics and Transportation Review, 72, pp. 77-100 (2014).
15. Al-Dhaheri, N. and Diabat, A. "The quay crane scheduling problem", Journal of Manufacturing Systems, 36, pp. 87-94 (2015).
16. Al-Dhaheri, N., Jebali, A., and Diabat, A. "The quay crane scheduling problem with nonzero crane repositioning time and vessel stability constraints", Computers & Industrial Engineering, 94, pp. 230-244 (2016).
17. Liu, C., Zheng, L., and Zhang, C. "Behavior perception-based disruption models for berth allocation and quay crane assignment problems", Computers & Industrial Engineering, 97, pp. 258-275 (2016).
18. Wu, L. and Ma, W. "Quay crane scheduling with draft and trim constraints", Transportation Research Part E: Logistics and Transportation Review, 97, pp. 38-68 (2017).
19. Agra, A. and Oliveira, M. "MIP approaches for the integrated berth allocation and quay crane assignment and scheduling problem", European Journal of Operational Research, 264(1), pp. 138-148 (2018).
20. Azevedo, A.T., de Salles Neto, L.L., Chaves, A.A., and Moretti, A.C. "Solving the 3D stowage planning problem integrated with the quay crane scheduling problem by representation by rules and genetic algorithm", Applied Soft Computing, 65, pp. 495-516 (2018).
21. Liang, C., Fan, L., Xu, D., Ding, Y., and Gen, M. "Research on coupling scheduling of quay crane dispatch and configuration in the container terminal", Computers & Industrial Engineering, 125, pp. 649-657 (2018).
22. Safaeian, M., Etebari, F., and Vahdani, B. "An integrated quay crane assignment and scheduling problem with several contractors in container terminals", Scientia Iranica, 28(2), pp. 1030-1048 (2021).
23. Fathollahi-Fard, A.M., Ranjbar-Bourani, M., Cheikhrouhou, N., and Hajiaghaei-Keshteli, M. "Novel modifications of social engineering optimizer to solve a truck scheduling problem in a cross-docking system", Computers & Industrial Engineering, 137, 106103 (2019).
24. Fatehi-Kivi, A., Mehdizadeh, E., and Tavakkoli- Moghaddam, R. "A new mathematical model for a multi-product supply chain network with a preventive maintenance policy", International Journal of Engineering, 32(10), pp. 1446-1453 (2019).
25. Fathollahi-Fard, A.M., Hajiaghaei-Keshteli, M., and Tavakkoli-Moghaddam, R. "A Lagrangian relaxationbased algorithm to solve a home health care routing problem", International Journal of Engineering, 31(10), pp. 1734-1740 (2018).
26. Mohammadzadeh, H., Sahebjamnia, N., Fathollahi-Fard, A M., and Hahiaghaei-Keshteli, M. "New Approaches in metaheuristics to solve the truck scheduling problem in a cross-docking center", International Journal of Engineering-Transactions B: Applications,31(8), pp. 1258-1266 (2018).
27. Liu, X., Tian, G., Fathollahi-Fard, A.M., and Mojtahedi, M. "Evaluation of ship's green degree using a novel hybrid approach combining group fuzzy entropy and cloud technique for the order of preference by similarity to the ideal solution theory", Clean Technologies and Environmental Policy, 22(2), pp. 493-512 (2020).