Robust and sustainable full-shipload routing and scheduling problem considering variable speed: A real case study

Document Type : Article


1 School of Industrial Engineering, College of Engineering, University of Tehran, Tehran, Iran

2 School of Industrial Engineering, Iran University of Science & Technology, Tehran, Iran


This paper presents a sustainable multi objective routing and scheduling for maritime transportation considering ship variable speeds under uncertainty. The proposed model is aimed to satisfy three individual dimensions of sustainability including economic, environmental and social aspects simultaneously while it is finding the best routes and schedule for each ship. The first objective is placed to meet economic goal by minimizing shipping cost. The second objective goes to social respect of sustainability by maximizing job creation due to number of intransitive workers in ships and ports and, the third one is minimizing CO2 emission to cover environmental target. Several test problems are applied to validate the proposed model and sensitivity analysis is used to demonstrate effects of model’s parameters on objective function value. Augmented ɛ-constraint is implemented as a solution method to solve the multi-objective mathematical model. This is the first ship routing and scheduling paper which is considered three aspect of sustainability under uncertainty and solved by augmented ɛ-constraint. To solve the model in larger size, factual input data from a real case study is considered. Computational results show a significant positive managerial effects of this paper contributions.


Main Subjects

1. Agarwal, R. and Ergun, O. "Ship scheduling and network design for cargo routing in liner shipping", Transportation Science, 42(2), pp. 175-196 (2008).
2. UNCTAD. "Review of maritime transport", United Nations Conference on Trade and Development, New York and Geneva, United Nation (2013).
3. Lawrence, S.A., International Sea Transport: The Years Ahead, Lexington Books (1972).
4. Christiansen, M. and Nygreen, B. "Robust inventory ship routing by column generation", In Column Generation, pp. 197-224. Springer, Boston, MA (2005).
5. Buhaug, ., Corbett, J.J., Endresen, ., Eyring, V., Faber, J., Hanayama, S., Lee, D.S., et al. "Second imo ghg study", International Maritime Organization (IMO), London, UK 24 (2009).
6. Ryder, S.C. and Chappel, D., Optimal Speed and Ship Size for the Liner Trades, University of Liverpool, Marine Transport Centre (1979).
7. Ronen, D. "The effect of oil price on the optimal speed of ships", Journal of the Operational Research Society, 33(11), pp. 1035-1040 (1982).
8. Wen, M., Ropke, S., Petersen, H.L., Larsen, R., and Madsen, O.B. "Full-shipload tramp ship routing and scheduling with variable speeds", Computers & Operations Research, 70, pp. 1-8 (2017).
9. De, A., Mamanduru, V.K.R., Gunasekaran, A., Subramanian, N., and Tiwari, M.K. "Composite particle algorithm for sustainable integrated dynamic ship routing and scheduling optimization", Computers & Industrial Engineering, 96, pp. 201-215 (2016).
10. Jansen, L. "The challenge of sustainable development", Journal of Cleaner Production, 11(3), pp. 231- 245 (2003).
11. Vachon, S. and Mao, Z. "Linking supply chain strength to sustainable development: a country-level analysis", Journal of Cleaner Production, 16(15), pp. 1552-1560 (2008).
12. Cucek, L., Klemes, J.J., and Kravanja, Z. "A review of footprint analysis tools for monitoring impacts on sustainability", Journal of Cleaner Production, 34, pp. 9-20 (2012).
13. Ronen, D. "Cargo ships routing and scheduling: Survey of models and problems", European Journal of Operational Research, 12(2), pp. 119-126 (1999).
14. Ronen, D. "Marine inventory routing: Shipments planning", Journal of the Operational Research Society, 53(1), pp. 108-114 (2002).
15. Psaraftis, H.N. "Ship routing and scheduling: the cart before the horse conjecture", Maritime Economics & Logistics, 21(1), pp. 1-14 (2017).
16. Brnmo, G., Christiansen, M., and Nygreen, B. "Ship routing and scheduling with  flexible cargo sizes", Journal of the Operational Research Society, 58(9), pp. 1167-1177 (2007).
17. Christiansen, M. "Decomposition of a combined inventory and time constrained ship routing problem", Transportation Science, 33(1), pp. 3-16 (1999).
18. Ting, S.C. and Tzeng, G.H. "Ship scheduling and cost analysis for route planning in liner shipping", Maritime Economics & Logistics, 5(4), pp. 378-392 (2003).
19. Bendall, H.B. and Stent, A.F. "A scheduling model for a high speed containership service: A hub and spoke short-sea application", International Journal of Maritime Economics, 3(3), pp. 262-277 (2001).
20. Azaron, A. and Kianfar, F. "Dynamic shortest path in stochastic dynamic networks: Ship routing problem", European Journal of Operational Research, 144(1), pp. 138-156 (2003).
21. Hwang, S.J. "Inventory constrained maritime routing and scheduling for multi-commodity liquid bulk", PhD dissertation, Georgia Institute of Technology (2005).
22. Korsvik, J.E., Kjetil Fagerholt, K., and Laporte, G. "A large neighbourhood search heuristic for ship routing and scheduling with split loads", Computers & Operations Research, 38(2), pp. 474-483 (2011).
23. Fagerholt, K., Christiansen, M., Hvattum, L.M., Johnsen, T.A., and Vab., T.J. "A decision support methodology for strategic planning in maritime transportation", Omega, 38(6), pp. 465-474 (2010a).
24. Stalhane, M., Andersson, H., Christiansen, M., Cordeau, J.F., and Desaulniers, G. "A branch-priceand- cut method for a ship routing and scheduling problem with split loads", Computers & Operations Research, 39(12), pp. 3361-3375 (2012).
25. Agra, A., Christiansen, M., and Delgado, A. "Mixed integer formulations for a short sea fuel oil distribution problem", Transportation Science, 47(1), pp. 108-124 (2013).
26. Moon, I.K., Qiu, Z.B. and Wang, J.H. "A combined tramp ship routing,  fleet deployment, and network design problem", Maritime Policy & Management, 42(1), pp. 68-91 (2015).
27. Corbett, J.J. and Koehler, H.W. "Updated emissions from ocean shipping", Journal of Geophysical Research: Atmospheres., 108(D20) (2003).
28. Corbett, J.J., Haifeng Wang, and Winebrake, J.J. "The effectiveness and costs of speed reductions on emissions from international shipping", Transportation Research Part D: Transport and Environment, 14(8), pp.593-598 (2009).
29. Ronen, D. "The effect of oil price on containership speed and  fleet size", Journal of the Operational Research Society, 62(1), pp. 211-216 (2011).
30. Eyring, V., Kohler, H.W., Van Aardenne, J., and Lauer, A. "Emissions from international shipping: 1. The last 50 years", Journal of Geophysical Research: Atmospheres, 110, D17 (2005).
31. Endresen, ., Srgard, E., Behrens, H.L., Brett, P.O., and Isaksen, I.S. "A historical reconstruction of ships' fuel consumption and emissions", Journal of Geophysical Research: Atmospheres, 112, D12 (2007).
32. Yin, J., Fan, L. Yang, Z., and Li, K.X. "Slow steaming of liner trade: its economic and environmental impacts", Maritime Policy & Management, 41(2), pp. 149-158 (2014).
33. McKinnon, A. "The possible influence of the shipper on carbon emissions from deep-sea container supply chains: An empirical analysis", Maritime Economics & Logistics, 16(1), pp. 1-19 (2014).
34. Norstad, I., Fagerholt, K., and Laporte, G. "Tramp ship routing and scheduling with speed optimization", Transportation Research Part C: Emerging Technologies, 19(5), pp. 853-865 (2011).
35. Gatica, R.A. and Miranda, P.A. "Special issue on Latin-american research: a time based discretization approach for ship routing and scheduling with variable speed", Networks and Spatial Economics, 11(3), pp. 465-485 (2011).
36. Wang, S. and Meng, Q. "Sailing speed optimization for container ships in a liner shipping network", Transportation Research Part E: Logistics and Transportation Review, 48(3), pp. 701-714 (2012).
37. Psaraftis, H.N. and Christos A. Kontovas "Ship speed optimization: Concepts, models and combined speedrouting scenarios", Transportation Research Part C: Emerging Technologies, 44, pp. 52-69 (2014).
38. Andersson, H., Fagerholt, K., and Hobbesland, K. "Integrated maritime  fleet deployment and speed optimization: Case study from RoRo shipping", Computers & Operations Research, 55(5), pp. 233-240 (2015).
39. Dubois, D., Fargier, H., and Fortemps, Ph. "Fuzzy scheduling: Modelling  flexible constraints vs. coping with incomplete knowledge", European Journal of Operational Research, 147(2), pp. 231-252 (2003).
40. Bellman, R.E. and Zadeh, L.A. "Decision-making in a fuzzy environment", Management Science, 17(4), B- 141 (1970).
41. Mula, J., Poler, R., and Garcia, J.P. "MRP with flexible constraints: A fuzzy mathematical programming approach", Fuzzy Sets and Systems, 157(1), pp. 74-97 (2007).
42. Pishvaee, M.S. and Torabi, S.A. "A possibilistic programming approach for closed-loop supply chain network design under uncertainty", Fuzzy sets and Systems, 161(20), pp. 2668-2683 (2010).
43. Celik, M., Cebi, S., Kahraman, C., and Er, I.D. "Application of axiomatic design and TOPSIS methodologies under fuzzy environment for proposing competitive strategies on Turkish container ports in maritime transportation network", Expert Systems with Applications, 36(3), pp. 4541-4557 (2009).
44. Christiansen, M. and Fagerholt, K. "Robust ship scheduling with multiple time windows", Naval Research Logistics (NRL), 49(6), pp. 611-625 (2002).
45. Christiansen, M., Fagerholt, K., and Ronen, D. "Ship routing and scheduling: Status and perspectives", Transportation Science, 38(1), pp. 1-18 (2004).
46. Pishvaee, M.S. and Fazli Khalaf, M.R. "Novel robust fuzzy mathematical programming methods", Applied Mathematical Modelling, 40(1), pp. 407-418 (2016).
47. Chuang, T.N., Lin, C.T., Kung, J.Y., and Lin, M.D. "Planning the route of container ships: A fuzzy genetic approach", Expert Systems with Applications, 37(4), pp. 2948-2956 (2010).
48. Fagerholt, Kjetil, Laporte, G., and Inge Norstad "Reducing fuel emissions by optimizing speed on shipping routes", Journal of the Operational Research Society, 61(3), pp. 523-529 (2010).
49. Pishvaee, M.S., Razmi, J., and Torabi, S.A. "Robust possibilistic programming for socially responsible supply chain network design: A new approach", Fuzzy Sets and Systems, 206, pp. 1-20 (2012).
50. Greco, S., Figueira, J., and Ehrgott, M., Multiple Criteria Decision Analysis, Springer's International Series (2005).
51. Mavrotas, G. "Effective implementation of the "constraint method in multi-objective mathematical programming problems", Applied mathematics and Computation, 213(2), pp. 455-465 (2009).