Abstract
Consideration is given to a ship routing problem (SRP) where a container-ship fleet performs pickups and deliveries of containers between a hub and a set of spoke ports. SRPs are a type of vehicle routing problem (VRP) in maritime environments where vehicles are vessels or ships and the customers to be served are ports. Given the inherent complexity of this class of problems, heuristic methods seem to offer the most promise for practical size problem instances. After describing SRP as a capacitated VRP on a graph with pickups, deliveries, and time window constraints, we present a new population heuristic for its solution. Computational experiments for a variety of operating environments show the effectiveness of the developed approach. The results demonstrate very satisfactory performance in terms of both solution time and quality.
Similar content being viewed by others
Data Availability
Data can be sent after request.
References
Kjeldsen K (2011) Classification of ship routing and scheduling problems in liner shipping, INFOR: Inform Syst and Oper Res 49:2:139–152
Ronen D (1983) Cargo ships routing and scheduling: survey of models and problems. Eur J Oper Res 12:119–126
Ronen D (1993) Ship scheduling: the last decade. Eur J Oper Res 71:325–333
Christiansen M, Fagerholt K, Nygreen B, Ronen D (2013) Ship routing and scheduling in the new millennium. Eur J Oper Res 228:467–483
Christiansen M, Fagerholt K, Ronen D (2004) Ship routing and scheduling: status and perspective. Transp Sci 38(1):1–18
Stahlbock R, Voss S (2008) Operations research at container terminals: a literature update. OR Spectrum 30:1–52
Boffey TB, Edmond ED, Hinxman AI, Pursglove CJ (1979) Two approaches to scheduling container ships with an application to the north Atlantic route. Journal of the Operational Research Society 30:413–425
Rana K, Vickson RG (1991) Routing container ships using Lagrangean relaxation and decomposition. Transp Sci 25(3):201–214
Cho S-C, Perakis AN (1996) Optimal liner fleet routing strategies. Marit Policy Manag 23(3):249–259
Fagerholt K (1999) Optimal fleet design in a ship routing problem. International Transactions in Operations Research 6(5):453–464
Fagerholt K (2001) Ship scheduling with soft time windows: an optimization based approach. Eur J Oper Res 131(3):559–571
Sambracos E, Paravantis JA, Tarantilis CD, Kiranoudis CT (2004) Dispatching of small containers via coastal freight lines: the case of the Aegean Sea. Eur J Oper Res 152:365–381
Shintani K, Imai A, Nishimura E, Papadimitriou S (2007) The container shipping network design problem with empty container repositioning. Transp Res Part E 43:39–59
Karlaftis M, Kepaptsoglou K, Sambracos E (2009) Containership routing with time deadlines and simultaneous deliveries and pick-ups. Transp Res Part E 45:210–221
Wang S, Meng Q (2011) Schedule design and container routing in liner shipping. Transport Res Record 2222:25–33
Wang S, Meng Q (2012) Liner ship route schedule design with sea contingency time and port time uncertainty. Transport Res Part B 46(5):615–633
Wang S, Alharbi A, Davy P (2015), Ship route schedule based interactions between shipping lines and port operators. In: Lee CY, Meng Q (Eds.), Ocean container transport logistics making global supply chain effective. Elsevier, Amsterdam
Castillo-Villar KK, González-Ramírez RG, González PM, Smith NR (2014) A heuristic procedure for a ship routing and scheduling problem with variable speed and discretized time windows, Mathematical Problems in Engineering, Article ID 750232. https://doi.org/10.1155/2014/750232.
Wang S, Alharbi A, Davy P (2014) Liner ship route schedule design with port time windows. Transp Res Part C 41:1–17
Solomon MM (1987) Algorithms for vehicle routing and scheduling problems with time window constraints. Oper Res 35(2):254–265
Christiansen M, Fagerholt K (2014) Ship routing and scheduling in industrial and tramp shipping, in Vehicle Routing: problems, methods and applications (edited by Toth P. and Vigo D.), MOS-SIAM Series on Optimization, pp. 381–403.
Holland JH (1975) Adaption in natural and artificial systems. University of Michigan Press, Ann Arbor, MI
Michalewicz Z, Fogel DB (2000) How to solve it: modern heuristics. Springer-Verlag, Berlin
Nearchou AC (2004) The effect of various operators on the genetic search for large scheduling problems. Int J Prod Econ 88(2):191–203
Goldberg DE (1989) Sizing populations for serial and parallel genetic algorithms, in Proc. 3rd Int. Conf. Genetic Algorithms (ICGA 89), pp. 70–79
Desrochers M, Desrochers J, Solomon M (1992) A new optimization algorithm for the vehicle routing problem with time windows. Oper Res 40(2):342–354
Iliopoulou C, Kepaptsoglou K, Karlaftis M (2015) Route planning for a seaplane service: The case of the Greek Islands. Comput Oper Res Elsevier 59:66–77
Ghani NEA, Shariff SSR, Zahari SM (2016) An alternative algorithm for vehicle routing problem with time windows for daily deliveries. Advances in Pure Mathematics 6:342–350
Kumar SN, Panneerselvam R (2017) Development of an efficient genetic algorithm for the time dependent vehicle routing problem with time windows. Am J Oper Res 7:1–25
Wijayaningrum VN, Mahmudy WF (2016) Optimization of ship’s route scheduling using genetic algorithm, Indonesian Journal of Electrical Engineering and Computer. J Electr Eng Comput Sci 2(1):180–186
Thangiah S (1995) Vehicle routing with time windows using genetic algorithms. Application handbook of genetic algorithms: new frontiers, 2. CRC Press, Boca Raton, pp 253–277
MahmoudZadeh S, Powers DMW, Yazdani AM et al (2018) Efficient AUV path planning in time-variant underwater environment using differential evolution algorithm. J Marine Sci Appl 17:585–591
Sakaki A, Ghassemi H, Keyvani S (2019) Evaluation of the hydrodynamic performance of planning boat with trim tab and interceptor and its optimization using genetic algorithm. J Marine Sci Appl 18:131–141
Author information
Authors and Affiliations
Corresponding author
Ethics declarations
Conflict of Interest
The authors declare no conflicts of interest.
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Charalambopoulos, N., Nearchou, A.C. Ship Routing Using Genetic Algorithms. SN Oper. Res. Forum 2, 45 (2021). https://doi.org/10.1007/s43069-021-00093-w
Received:
Accepted:
Published:
DOI: https://doi.org/10.1007/s43069-021-00093-w