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.
The cargo delivery market develops very rapidly, which requires the use of modern technologies to satisfy all market needs and maximize profits. The gross tonnage of container carriers since 1980 has increased from 11 up to 275 million metric tons [1, 2] and tends to further increase.
Great practical and theoretical interest is in the development of methods for organizing and managing maritime transportation systems, which can significantly increase the efficiency of cargo transportation, including the transportation of container cargo. Significant progress has now been achieved in this direction due to the development and implementation of modern information technologies and appropriate project management methods. Thus, SMART intelligence models for managing innovation projects and methods for goal setting and risk management in transport infrastructure development projects are proposed in works [3, 4]. Innovative models of project portfolio structure dynamics taking into account resistance of information entropy are proposed in [5, 6, 7]. Paper [8] proposes a project management model of container feeder line organization focused on the nature and parameters of external container flows. Paper [9] develops a mathematical approach to the optimization of transportation projects. It is worth mentioning that cargo transportation is one of the major sources of water and air pollution. As for the greenhouse effect, shipping represents 2.6 % of overall emissions [10]. Therefore, one of the current areas of research in the development of modern maritime transport infrastructure is the development of models for environmentally oriented project management and the development of methods to ensure their sustainability. Work [11] proposes an integral approach to vulnerability assessment for ship operation projects. Papers [12, 13] develop methods for managing the eco-logistics system project based on the genetic approach. Environmental Efficiency of Ship Operation projects and measures to enhance the ecological safety of ships and reduce operational pollution to the environment in Terms of Freight Transportation Effectiveness Provision are studied in [14, 15].
When implementing projects for organizing and managing the operation of a feeder fleet, complex issues often arise. Therefore, it is generally accepted that the efficient tour implies its minimally possible length for a scheduled delivery. It is important to note that planning delivery routes requires not only to follow the minimization of route length. There are additional factors to consider that are an integral part of water transportation: 1. The capacity of each feeder in the fleet operated by the company. 2. The amount of cargo that is accumulated at each port in one day. 3. Time windows that define the period when the feeder is expected to arrive at the port.
Minimizing the route length should be done by taking into account the above-listed factors. The route length minimization along with the introduced factors is a transportation optimization problem equivalent to the traveling salesman problem [16, 17]. In the case of maritime cargo delivery, the travelling salesman problem solves the task of routing efficient tours of feeders.
Our problem formulation is based on the complicated version of the travelling salesman problem, namely the multiple travelling salesman problem. Such a version of the problem is considered in this article, since companies, involved in maritime transportation, use more than one feeder. It is an NP-hard problem in combinatorial optimization, whose exact solution usually takes too long to be obtained because exact algorithms perform reasonably fast only for small-sized problems [18]. Heuristic algorithms perform far much faster producing approximated solutions and saving computational resources (which are equivalent to time and budget) [19, 20].
The genetic algorithm is one of the best heuristics allowing us to find tours whose length is practically close to the minimal length of the delivery [21, 22]. Sometimes the length found heuristically coincides with the length in the exact solution. There are various ways to improve the performance of a genetic algorithm. The algorithm assigns a penalty to routes that do not satisfy the algorithm's specified constraints. The impact of the penalty and a study on how it can be improved is presented in [23]. The basic mutation operation in a genetic algorithm is the crossover operation, which is also known as a two-point crossover. A variation of the algorithm with a modified three-point crossover is discussed in [24]. It is also worth mentioning the importance of the random number generator, which is present in the genetic algorithm at the stage of forming an initial population, as well as during the process of mutations. A study of the influence of the random number generator on the operation of the genetic algorithm can be found in the article [25].
When constructing the optimal route, the length of the route should be minimized while simultaneously adhering to restrictions on the capacity of feeders, the volume of accumulated cargo in ports and the timing of the feeder’s arrival at the port for unloading and loading cargo. Therefore, all these restrictions need to be implemented into the genetic algorithm, and we need to analyze how they will affect the route search in comparison with the algorithm without additional restrictions. To obtain the best-approximated solution, the adjustable inputs (like the population size, mutation operators, and others) should be optimally configured. The optimal configuration is a very tough task being itself an optimization problem (similar, e.g., to the optimization in AutoML [26, 27]). In this way, rules of thumb are widely accepted based on recent experience [28, 29]. Apart from that, to achieve maximum results, it is necessary to use studies devoted to improving the performance of the genetic algorithm [23, 24, 25].
The goal is to describe, implement, and justify the importance of using a genetic algorithm for maritime cargo delivery projects with improved constraints. Moreover, a comparison with a version of the genetic algorithm without enhanced restrictions should be presented. To achieve the goal, the following four tasks are to be fulfilled: 1. To substantiate the inclusion of the feeder capacity, accumulation intensity of cargo at the port, and maximum route duration constraints into the algorithm. 2. To show the advantage of the algorithm using improved constraints compared to the algorithm using only tour length constraints. 3. To discuss the significance and practical applicability of the suggested improvements in the genetic algorithm. 4. Make an unbiased conclusion on the contribution to the field of genetic algorithms used, in particular, to optimize maritime cargo delivery planning. An outlook of how the research should be extended and advanced is to be made as well
The travelling salesman problem is a classic problem in combinatorial optimization where the objective is to find the shortest possible route that visits each city exactly once and returns to the origin city. When applied to maritime cargo delivery, the travelling salesman problem model can be adapted to find the most efficient route for delivering cargo to multiple ports while minimizing costs such as time, fuel, and other resources. This formulation extends the single travelling salesman problem to handle multiple salesmen. The main goal remains the same — to minimize the total cost of the route. This cost can be defined as the sum of distances, time, fuel consumption, or any other relevant metric associated with maritime cargo delivery. As with the single travelling salesman problem, solving the multiple travelling salesman problem optimally can be computationally challenging for large instances, and approximation algorithms or heuristics may be utilized to find good solutions efficiently.
The following variables are used in a simplified maritime cargo delivery model [23, 24, 25]: the number of ports, 1 and 2 are the horizontal and vertical components of the position of the port , and the number of feeders available to accomplish the delivery. Every feeder starts its tour off port 1 and ends up returning to that port. We denote the current number of feeders by , so
≤ . (
It is important to note that a feeder can only visit a port on its route once, returning to the starting port, so each route is a closed loop. In this loop, we use flagging denoted by a set to distinguish visited and non-visited ports by the feeder (the flag is 1 if a port was visited; otherwise, it is 0).
In our previous works, we considered a model in which the feeder had a limitation on the maximum and minimum route lengths. The goal was to find routes that would not require re-fueling, allowing to save time and money. In this work, the restriction is removed because refuelling costs are considered acceptable for sea transportation. Instead of a route length limitation, new constraints have been added on: feeder capacity , accumulation intensity of cargo at port visited by the feeder , and maximum route duration . The tour duration of the feeder should be
≤ ∀ = 1, . (
⋂ =1 = {1}.
To optimize the maritime cargo delivery, the sum of all the tours of the feeders is to be
minimized. The respective objective function is
(
( , , )
for (
The genetic algorithm is a method for solving optimization problems that is based on natural selection. The genetic algorithm repeatedly modifies a population of individual solutions. At each step, the genetic algorithm selects individuals from the current population to be ancestors and uses them to produce the children for the next generation. Over successive generations, the population evolves toward an optimal solution. In the process of new population generation, mutations occur. The algorithm used in our article uses mutations such as flip, swap, slide, and crossover [21, 23]. Moreover, these mutations can be combined, which allows to creation of complex mutations. Each of these operations modifies the individual in its way, resulting in a quasioptimal solution [24].
After all mutations have been performed over the population, the evaluation and selection steps take place. All generated solutions are passed through a fitness function, which evaluates how close a given solution is to the optimal solution of the desired problem and checks whether the route satisfies all specified constraints. If any of the defined constraints are violated, then the solution is penalized, being made not feasible, which means that it may not take part in subsequent mutations. Solutions that do not score penalties or score less than others are marked as feasible solutions and will be used in subsequent mutations.
Our previous works [23, 24, 25] considered a genetic algorithm that searched for the shortest delivery route with a limitation on the maximum route length. The fitness function evaluated the length of the route of each feeder, and if it was longer than the defined constraint — the penalty was assigned. This restriction was used to allow the feeder to go through the cargo delivery route without refuelling. This would reduce fuel costs and avoid spending additional time on refuelling. This article discusses a new set of constraints, as well as an expanded set of input data to the algorithm. Besides, the maximum route length restriction is omitted, since refueling costs are considered allowable during the process of cargo delivery.
The genetic algorithm discussed in this article has been enhanced with restrictions such as feeder capacity, accumulation intensity of cargo at the port, and maximum route duration. These restrictions reflect the real processes that occur in maritime cargo delivery companies. The inclusion of these new concepts in the algorithm allows it to be used to build delivery routes taking into account all the complexities and specialties of the maritime delivery business.
Feeder capacity determines the maximum amount of cargo that can be transported on a single tour. By considering feeder capacity constraints in genetic algorithms, shipping companies can optimize the allocation of cargo to feeders, ensuring that each feeder is utilized to its maximum capacity. This leads to more efficient resource utilization and costeffective transportation operations. Optimizing feeder capacity allocation helps minimize shipping expenses by reducing the number of feeders required to transport the same volume of cargo. Operating feeders within their designed capacity limits is essential for ensuring safety and stability at sea. By adhering to feeder capacity limits, shipping companies can mitigate the risk of accidents, collisions, and other maritime incidents. Feeder capacity regulations, such as those related to load lines and stability criteria, must be adhered to for regulatory compliance and maritime safety. Genetic algorithms can be used to find an optimal combination of feeders and routes, taking into account feeder capacities, fuel consumption, port fees, and other relevant factors. This leads to overall cost savings for shipping companies. Considering feeder capacity constraints helps prevent the risk of feeder overloading, which can compromise stability and pose safety hazards. Overall, feeder capacity is a critical factor in maritime cargo delivery, and its consideration in genetic algorithms for route optimization is essential for achieving efficient, cost-effective, and safe transportation operations.
Cargo accumulation intensity refers to the maximum number of cargo that a port can accumulate within a given time frame. It encompasses various factors such as berth availability, crane capacity, storage facilities, and labour resources. Feeder capacity together with cargo accumulation intensity play critical roles in maritime cargo delivery by ensuring efficient resource utilization, reducing costs, and minimizing delays. Genetic algorithms offer a powerful optimization approach to address these challenges by dynamically allocating resources, optimizing scheduling decisions, and balancing competing objectives to achieve optimal solutions that maximize efficiency and performance in maritime logistics operations.
Time windows define specific time frames within which feeders must arrive or depart from ports, terminals, or other maritime facilities. In our formulation of the problem, this denotes the maximum duration of the route during which the feeder must visit all its ports. Adhering to these time windows ensures smooth and efficient operations by synchronizing feeder movements with port schedules, cargo handling activities, and other logistical processes. Time windows help manage berth availability and allocation at ports by regulating feeder arrivals and departures. By scheduling feeder arrivals within designated time windows, shipping companies can optimize berth utilization, minimize waiting times, and reduce congestion at port facilities. Time windows enable better integration and coordination across different segments of the supply chain, including shipping, logistics, and distribution. By aligning feeder schedules with downstream transportation modes, storage facilities, and customer requirements, time windows help streamline cargo flows and improve supply chain responsiveness. In the genetic algorithm, time windows are reflected as the maximum route duration and mean the number of days when the feeder is expected to arrive at the port.
The above-listed constraints are programmed into the genetic algorithm that is used to
construct maritime cargo delivery routes by (
In the scope of the testing section, the algorithms with tour length constraints and improved maritime constraints are compared. Further in the article, the algorithm with tour length constraint will be indicated as GA_1 and the algorithm with improved constraints will be referred to as GA_2. Each experiment is carried out under the same conditions — the same port map and the number of feeders pre-determined beforehand.
First of all, the comparison of algorithms for route planning utilizing a single feeder is performed. From the results presented in Figures 1 and 2, it is clear that there is no significant difference in the solutions obtained, although the GA_1 route is 1.32% shorter than the GA_2 route. This may be because different constraints are involved in the selection process. In general, we can claim that the new restrictions do not affect the construction of a route for one feeder. Such an experiment represents the classic travelling salesman problem. In such a formulation of the problem, there may be requirements for the order of visiting ports, but this case is not in the scope of this article. It is worth also noting that transport companies do not operate with one feeder, so we are not considering this case.
The following experiment tests the influence of the merging probability. Within the crossover operation, two chromosomes as tours of two different feeders may be merged into a single tour allowing to decrease the number of feeders used to deliver maritime cargo. This is done by using a merging probability value given at the input of the genetic algorithm.
Figures 3 and 4 show the influence of the merging probability on the operation of the algorithm when managing a static number of feeders. The solution without merging probability (Figure 3) has built a route for 4 feeders without violating the specified constraints on feeder capacity and the expected delivery window of 10 days. A solution where feeders are merged (Figure 4) results in a shorter route. After the appearance of the merged individual, the population is filled with solutions with merged routes and this is repeated at each subsequent iteration. As a result, a solution is reduced to the route of one feeder, which does not satisfy the algorithms' conditions, although it is rightly considered as the shortest route. In this regard, the use of the merging probability should be excluded in the current formulation of the problem. If too many feeders are used, it may turn out that they will run with a low load. At this point, to get out of this situation, the algorithm can be re-launched with fewer feeders. However, such an approach may not be considered optimal. One of the options is to reduce the speed of movement of feeders along the received routes. This will save on fuel, and increase the amount of cargo accumulated in ports, thereby increasing the fullness of feeders, and, as a result, they will move more filled. Another option for selecting the composition of the fleet could be a meta-algorithm that will sort through various combinations of the company’s fleet and run a genetic algorithm for each set of feeders — as a result, the optimal route with the lowest transportation costs will be found. Both of these options require further research and are out of the scope of this article.
The GA_1 algorithm takes into account the minimum number of visited ports and the
maximum length of feeders' routes. Therefore, Figure 5 displays that a feeder with the
shortest tour visits only two ports, and the feeder with the longest tour visits the majority
of ports on the map. In this case, the algorithm's limitations are not violated. As stated
earlier, the algorithm should not rely only on the length of the route. It should build
solutions considering the feeder capacity, accumulation intensity of cargo at the port, and
maximum route duration. With such conditions, the solution is not suitable, because the
duration of the feeder tour with the most visited ports (30 ports) does not fit the time
window of 10 days — the route duration is 13 days. GA_1 simply does not know about the
existence of such a restriction, that is constraint (
Figure 6 shows the route for three feeders that visit all ports in the specified time
windows, but one limitation is not met — on the route of the feeder with the most ports,
1490 containers are accumulated in 10 days, even though the feeder itself has a capacity of
500 containers. Herein, constraint (
Figure 7 shows a solution where one extra feeder is added to the fleet. In this solution, the restrictions are not violated — the longest route is completed in 7 days and 476 containers are accumulated at the ports. Figure 8 shows a solution that involves replacing one feeder with a larger capacity. The restrictions are not violated as well — on the longest route of 9 days, 999 containers are generated. Thus, there are two options for constructing a route for delivering cargo to this set of ports.
We have presented a genetic algorithm with improved constraints for maritime cargo delivery route planning projects formulated as a multiple travelling salesman problem. Feeder capacity, accumulation intensity of cargo at the port, and maximum route duration expand the capabilities of the genetic algorithm, which otherwise would search for the shortest route only. However, the need to use the simplified algorithm, without additional constraints, should not be completely excluded, because there may be conditions for the projects where route planning is needed for one feeder or feeders without restrictions on cargo flow or timing. Such cases may arise for small projects which involve just a few feeders and a moderate number of ports.
For projects dealing with a medium or large fleet with responsibilities for cargo delivery times, the proposed version of the genetic algorithm with improved constraints will have great practical importance. An improved algorithm expands the set of algorithm constraints, which in turn narrows the set of possible solutions.
Thus, the contribution to the development of algorithms for solving the problem of maritime cargo delivery is obvious. In comparison with other studies on this topic like improvement of 2-point crossovers, tour constraint penalties, and influence of pseudorandom number generators, one more way has been studied to improve the practical performance of the genetic algorithm, in particular, for multiple travelling salesman problems.
At the moment, there are two directions for possible further improvements of the
algorithm. First, when searching for the optimal delivery route, a new step of optimization
can be added after all tours are determined. This step will check the possibility of reducing
the speed of the feeder along the route. In the algorithm, described in this article, the speed
of the feeder is not taken into account. This step of speed analysis would allow us to reduce
the speed, thereby significantly reducing fuel consumption which may notably increase the
financial and ecological efficiency of the project. At the same time, it is important not to
violate the restrictions on the feeder capacity, accumulation intensity of cargo at the port,
and maximum route duration. Secondly, we should consider the possibility of implementing
a meta-algorithm on top of the genetic algorithm to select the optimal fleet composition.
Such a meta-algorithm would allow the selection of the optimal set of feeders and, together
with the speed analysis step, make a major contribution to the automation and optimization
of decision-making for maritime cargo delivery projects.
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 (
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 (
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 (
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.23088893.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 (