Abstract
Liner companies face a complex problem in determining the optimal routing and deployment of a fleet of container vessels. This paper presents a model and an algorithm to address the two problems jointly. The model captures the revenues and operating expenses of a global liner company, and allows for the representation of vessel types with different cost and operating properties, transhipment hubs and associated costs, port delays, regional trade imbalances and the possibility of rejecting transportation demand selectively. Benchmark tests demonstrate that the proposed algorithm achieves good solutions quickly. The proposed algorithm is applied in a case study with 120 ports of call distributed throughout the globe. The case study explores the sensitivity of optimal fleet deployment and routing to varying bunker costs.
Similar content being viewed by others
References
Abara, J. (1989) Applying integer linear programming to the fleet assignment problem. Interfaces 19: 20–28.
Agarwal, R. and Ergun, Ö. (2008) Ship scheduling and network design for cargo routing in liner shipping. Transportation Science 42 (2): 175–196.
Ahuja, R.K., Magnanti, T.L. and Orlin, J.B. (1993) Network Flows: Theory, Algorithms, and Applications. New Jersey: Prentice Hall.
Alderton, P. (2005) Reeds Sea Transport Operations and Economics, 5th edn. London: Adlard Coles Nautical.
Armacost, A.P., Barnhart, C., Ware, K.A. and Wilson, A.M. (2004) UPS optimizes its air network. Interfaces 34 (1): 15–25.
Bendall, H.B. and Stent, A.F. (2001) A scheduling model for a high speed containership service: A hub and spoke short-sea application. International Journal of Maritime Economics 3: 262–277.
Castro, J. (2003) Solving difficult multicommodity problems with a specialized interior-point algorithm. Annals of Operations Research 124: 35–48.
Cho, S.-C. and Perakis, A. (1996) Optimal liner fleet routing strategies. Maritime Policy and Management 23: 249–259.
Christiansen, M., Fagerholt, K., Nygreen, B. and Ronen, D. (2007) Maritime transportation. In: C. Barnhart and G. Laporte (eds.) Handbooks in OR & MS, Vol. 14. Elsevier B.V., pp. 189–284.
Christiansen, M., Fagerholt, K. and Ronen, D. (2004) Ship routing and scheduling: Status and perspectives. Transportation Science 38: 1–18.
Container Management Magazine. (2007) Container management magazine website, http://www.container-mag.com/top120.php?SID=, accessed December 2007.
Fagerholt, K. (1999) Optimal fleet design in a ship routing problem. International Transactions in Operational Research 6: 453–464.
Fagerholt, K. and Lindstad, H. (2000) Optimal policies for maintaining a supply service in the Norwegian Sea. Omega 28: 269–275.
Fagerholt, K. and Lindstad, H. (September 2007) Turborouter: An interactive optimisation-based decision support system for ship routing and scheduling. Maritime Economics & Logistics 9 (3): 214–233.
Fourer, R., Gay, D. and Kernighan, B. (2003) AMPL, A Modeling Language for Mathematical Programming, 2nd edn. Pacific Grove, CA: Thomson Brooks Cole.
Glover, F. and Laguna, M. (1997) Tabu Search. Boston: Kluwer Academic.
Gopalan, R. and Talluri, K. (1998) Mathematical models in airline schedule planning: A survey. Annals of Operations Research 76: 155–185.
ILOG S.A. (2008) ILOG CPLEX 11.1 Reference Manual. Mountain View, California: ILOG S.A.
Mason, R., McKenney, J., Carlson, W. and Copeland, D. (1997) Absolutely, positively operations research: The federal express story. Interfaces 27: 17–36.
NIMA. (2001) Distances Between Ports, 11th edn. Bethesda, Maryland: National Imagery and Mapping Agency.
Notteboom, T.E. (2006) The time factor in liner shipping services. Maritime Economics & Logistics 6: 19–39.
Powell, B.J. and Perakis, A. (1997) Fleet deployment optimization for liner shipping: An integer programming model. Maritime Policy and Management 24: 183–192.
Rana, K. and Vickson, R. (1991) Routing container ships using Lagrangean relaxation and decomposition. Transportation Science 25: 201–214.
Rushmeier, R. and Kontogiorgis, S. (1997) Advances in the optimization of airline fleet assignment. Transportation Science 31: 159–169.
Sherali, H. and Al-Yakoob, S. (2006) Determining an optimal fleet mix and schedules: Part I – single source and destination. In: J. Karloff (ed.) Integer Programming: Theory and Practice. Taylor & Francis, Chapter 6. pp. 137–166.
Sherali, H. and Maguire, L. (2000) Determining rail fleet sizes for shipping automobiles. Interfaces 30: 80–90.
Simchi-Levi, D., Chen, X. and Braca, J. (2005) The Logic of Logistics. New York: Springer.
Song, D. et al (January-March 2005) On cost-efficiency of the global container shipping network. Maritime Policy & Management 32 (1): 15–30.
Stopford, M. (1997) Maritime Economics, 2nd edn. New York: Routledge.
Vanderbeck, F. and Wolsey, L.A. (1996) An exact algorithm for IP column generation. Operations Research Letters 19: 151–159.
Acknowledgements
This research was partly funded by Agencia de Gestio d'Ajuts Universitaris i de Recerca (AGAUR), of the Government of Catalonia. An early version of this paper was presented at IAME 2008, and we are grateful for the feedback obtained from the audience on that occasion. We thank Professor Kjetil Fagerholt for several suggestions. Any remaining errors or omissions are our responsibility.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Álvarez, J. Joint Routing and Deployment of a Fleet of Container Vessels. Marit Econ Logist 11, 186–208 (2009). https://doi.org/10.1057/mel.2009.5
Published:
Issue Date:
DOI: https://doi.org/10.1057/mel.2009.5