Genetic Algorithm for Maritime Route Planning Projects with Improved Constraints

ITPM 2024: pp. 126 - 140

Authors:

  1. Natalia Bushuyeva
  2. Andrii Ivko
  3. Andriy Romanov
  4. Mykola Malaksiano
  5. Vadim Romanuke

1 Kyiv National University of Construction and Architecture, Povitroflotskyi av., 31, Kyiv, 03037, Ukraine

2 Kyiv National University of Construction and Architecture, Povitroflotskyi av., 31, Kyiv, 03037, Ukraine
3 Odessa National Maritime University, Mechnikova str, 34, Odesa, 65029, Ukraine

4 Odessa National Maritime University, Mechnikova str, 34, Odesa, 65029, Ukraine5 Vinnytsia Institute of Trade and Economics of State University of Trade and Economics City, Soborna str, 87,
Vinnytsia, 21050, Ukraine

Abstract 

The increasing competition in the shipping market entails a constant increase in requirements
for the efficiency of shipping companies. As practice shows, among the key means, that allow to
notable increase in maritime transportation efficiency, are the implementation of innovative
information technologies and project management methods. In this article, we introduce an
implementation of a genetic algorithm with improved tour constraints that allows to increase the
maritime route planning projects efficiency. We consider using genetic algorithms for maritime
cargo transportation planning projects with such constraints as feeder capacity, accumulation
intensity of cargo at the port and maximum route duration or time window. Such constraints are
based on the specificity and intensity of maritime operations and bring the multiple travelling
salesman problem for maritime cargo delivery closer to actual project conditions. Besides, the
introduced restrictions allow for improvement in the search for a solution compared to a genetic
algorithm that uses a maximum route length constraint and minimizes the number of involved
feeders. Our tests show that the algorithm with improved constraints allows us to obtain a
solution with real-world restrictions, which in turn increases the practical significance of the
research. During the implementation of the presented constraints, the data set required to run
the algorithm is enhanced, as well as a function that evaluates the results of the algorithm – the
fitness function. The result of the research is a genetic algorithm capable of increasing the
maritime route planning projects’ efficiency while adhering to specified constraints. In addition,
a comparison of the new algorithm with an algorithm that is designed to find the shortest routes
only is presented.

Keywords

genetic algorithm, decision support, project management, simulation, maritime transportation,
route optimization, feeder fleet operation

References

[1] T. R. Walker, O. Adebambo, M. C. Del Aguila Feijoo, E. Elhaimer, T. Hossain, S. J. Edwards,
C. E. Morrison, J. Romo, N. Sharma, S. Taylor, S. Zomorodi, Environmental Effects of
Marine Transportation, in World Seas: an Environmental Evaluation, Academic Press,
Cambridge, Massachusetts, USA, (2019), pp. 505–530. doi:10.1016/B978-0-12-
805052-1.00030-9.
[2] W. Li, R. Pundt, E. Miller-Hooks, An updatable and comprehensive global cargo
maritime network and strategic seaborne cargo routing model for global containerized
and bulk vessel flow estimation, Maritime Transport Research 2 (2021) 100038.
doi:10.1016/j.martra.2021.100038.
[3] S. Bushuyev, N. Bushuyeva, V. Bushuieva, D. Bushuiev, SMART intelligence models for
managing innovation projects, CEUR Workshop Proceedings 3171 (2022) 1463–1474.
[4] A. Shakhov, V. Piterska, V. Botsaniuk, O. Sherstiuk, Mechanisms for goal setting and risk
management of concession projects in seaports, International Scientific and Technical
Conference on Computer Sciences and Information Technologies 2 (2020) 185–189.
doi:10.1109/CSIT49958.2020.9321963.
[5] A. Bondar, N. Bushuyeva, S. Bushuyev, S. Onyshchenko, Modelling of creation
organisational energy-entropy, International Scientific and Technical Conference on
Computer Sciences and Information Technologies 2 (2020) 141–145.
doi:10.1109/CSIT49958.2020.9321997.
[6] S. Chernov, L. Chernova, L. Chernova, N. Kunanets, V. Piterska, The synergetic effect in
the management of active system with distributed control, International Scientific and
Technical Conference on Computer Sciences and Information Technologies (2023).
doi:10.1109/CSIT61576.2023.10324123.
[7] S. Bushuyev, S. Onyshchenko, N. Bushuyeva, A. Bondar, Modelling projects portfolio
structure dynamics of the organization development with a resistance of information
entropy, International Scientific and Technical Conference on Computer Sciences and
Information Technologies 2 (2021) 293–298. doi: 10.1109/CSIT52700.2021.9648713.
[8] O. Drozhzhyn, Y. Koskina, The model of container feeder line organization focused on
the nature and parameters of external container flows, Communications — Scientific
Letters of the University of Zilina 23 (2) (2021) A94–A102.
doi:10.26552/com.C.2021.2.A94-A102.
[9] S. Chernov, S. Titov, L. Chernova, V. Piterska, L. Chernova, N. Kunanets, Three-index
optimization transportation model, International Scientific and Technical Conference
on Computer Sciences and Information Technologies 2 (2021) 315–318.
doi:10.1109/CSIT52700.2021.9648807.
[10] Advantages of Maritime transport, 2024. URL:
https://blueoceanmag.com/advantages-of-maritime-shipping.
[11] O. Melnyk, S. Onyshchenko, O. Onishchenko, O. Lohinov, V. Ocheretna, Integral
approach to vulnerability assessment of ship’s critical equipment and systems,
Transactions on Maritime Science 12 (1) (2023). doi:10.7225/toms.v12.n01.002.
[12] S. Rudenko, T. Kovtun, T. Smokova, I. Finohenova, The genetic approach application and
creation of the project genetic model, International Scientific and Technical Conference
on Computer Sciences and Information Technologies (2022) 434–437.
doi:10.1109/CSIT56902.2022.10000822.
[13] S. Rudenko, T. Kovtun, V. Smrkovska, Devising a method for managing the configuration
of products within an eco-logistics system project, Eastern-European Journal of
Enterprise Technologies 4 (2022) 34–42. doi:10.15587/1729-4061.2022.261956.
[14] O. Melnyk, O. Onishchenko, S. Onyshchenko, V. Golikov, V. Sapiha, O. Shcherbina, V.
Andrievska, Study of environmental efficiency of ship operation in terms of freight
transportation effectiveness provision, International Journal on Marine Navigation and
Safety of Sea Transportation 16 (4) (2022) 723–729. doi:10.12716/1001.16.04.14.
[15] O. Melnyk, S. Onyshchenko, O. Onishchenko, Development measures to enhance the
ecological safety of ships and reduce operational pollution to the environment,
Scientific Journal of Silesian University of Technology. Series Transport 118 (2023)
195–206. doi:10.20858/sjsutst.2023.118.13.
[16] C. Archetti, L. Peirano, M. G. Speranza, Optimization in multimodal freight
transportation problems: A Survey, European Journal of Operational Research 299 (1)
(2022) 1–20. doi:10.1016/j.ejor.2021.07.031.
[17] P. A. Miranda, C. A. Blazquez, C. Obreque, J. Maturana-Ross, G. Gutierrez-Jarpa, The biobjective
insular traveling salesman problem with maritime and ground transportation
costs, European Journal of Operational Research 271 (3) (2018) 1014–1036.
doi:10.1016/j.ejor.2018.05.009.
[18] D.-Z. Du, P. M. Pardalos, Handbook of Combinatorial Optimization, Springer, New York,
NY, USA, 1998. doi:10.1007/978-1-4613-0303-9.
[19] A. Hertz, M. Widmer, Guidelines for the use of meta-heuristics in combinatorial
optimization, European Journal of Operational Research 151 (2) (2003) 247–252.
doi:10.1016/S0377-2217(02)00823-8.
[20] A. Colorni, M. Dorigo, F. Maffioli, V. Maniezzo, G. Righini, M. Trubian, Heuristics from
nature for hard combinatorial optimization problems, International Transactions in
Operational Research 3 (1) (1996) 1–21. doi:10.1016/0969-6016(96)00004-4.
[21] L. D. Chambers, The Practical Handbook of Genetic Algorithms, Chapman and Hall/CRC,
2000.
[22] R. L. Haupt, S. E. Haupt, Practical Genetic Algorithms, John Wiley & Sons, 2003.
doi:10.1002/0471671746.
[23] V. V. Romanuke, A. Y. Romanov, M. O. Malaksiano, A genetic algorithm improvement by
tour constraint violation penalty discount for maritime cargo delivery, System
Research and Information Technologies 2 (2023) 104–126. doi:10.20535/srit.2308-
8893.2023.2.08.
[24] V. V. Romanuke, A. Y. Romanov, M. O. Malaksiano, Crossover operators in a genetic
algorithm for maritime cargo delivery optimization, Journal of ETA Maritime Science
10 (4) (2022) 223–236. doi:10.4274/jems.2022.80958.
[25] V. V. Romanuke, A. Y. Romanov, M. O. Malaksiano, Pseudorandom number generator
influence on the genetic algorithm performance to minimize maritime cargo delivery
route length, Scientific Journal of Maritime Research 36 (2022) 249–262.
doi:10.31217/p.36.2.9.
[26] C. Thornton, F. Hutter, H. H. Hoos, K. Leyton-Brown, Auto-WEKA: Combined selection
and hyperparameter optimization of classification algorithms, in KDD’13: Proceedings
of the 19th ACM SIGKDD international conference on Knowledge discovery and data
mining, 2013, pp. 847–855.
[27] V. V. Romanuke, Optimal training parameters and hidden layer neurons number of
two-layer perceptron for generalized scaled objects classification problem,
Information Technology and Management Science 18 (2015) 42–48. doi:10.1515/itms-
2015-0007.
[28] E. Merhej, S. Schockaert, M. De Cock, Repairing inconsistent answer set programs using
rules of thumb: A gene regulatory networks case study, International Journal of
Approximate Reasoning 83 (2017) 243–264. doi:10.1016/j.ijar.2017.01.012.
[29] Y. Rocha, A. Subramanian, Hybrid genetic search for the traveling salesman problem
with hybrid electric vehicle and time windows, Computers & Operations Research 155
(2023) 106223. doi:10.1016/j.cor.2023.106223.

Full text

Powered By EmbedPress