• Editorial Board +
• For Contributors +
• Journal Search +
Journal Search Engine
ISSN : 1598-7248 (Print)
ISSN : 2234-6473 (Online)
Industrial Engineering & Management Systems Vol.20 No.4 pp.604-612
DOI : https://doi.org/10.7232/iems.2021.20.4.604

# Route Optimization of Container Ships Using Differential Evolution and Gray Wolf Optimization

Juhriyansyah Dalle*, Dr. Paitoon Chetthamrongchai, Gunawan Widjaja, Egor Dudukalov, A. Heri Iswanto, Elena Sergeevna Sergushina
Department of Information Technology, Universitas Lambung Mangkurat, Banjarmasin, Indonesia
Public Health Department, Faculty of Health Science, University of Pembangunan Nasional Veteran Jakarta, Indonesia
National Research Ogarev Mordovia State University, Republic of Mordovia, Saransk, Russia
*Corresponding Author, E-mail: j.dalle@ulm.ac.id
August 10, 2021 September 12, 2021 September 27, 2021

## ABSTRACT

Container ships carry most of the world's cargo volume. Hence, Maritime transportation forms the backbone of the world merchandise trade. Today, with the advancement of shipbuilding technology and the increasing frequency of maritime transport, determining the optimal route for container ships has become more and more important for shipping lines and port managers. Accordingly, in the present study, we intend to investigate the ship routing problem using a mixed integer linear mathematical programming model. In order to solve the proposed model, we have used the meta-heuristic algorithms of differential evolution and gray wolf optimization in MATLAB software. In the end, it was shown that the proposed mathematical model and solution approaches can assist ship operators and terminal managers in making reasonable optimization decisions.

## 1. INTRODUCTION

International trade largely depends on maritime transportation since ships are the most cost-effective means of transportation of a large volume of goods in long distances. Container ship routing has been one of the most important issues of transport companies and shipping lines, since, as mentioned, a significant volume of transportation includes sea transportation. In general, there are three types of maritime transportation (ship routing problem), which are presented below.

• 1) Industrial transportation: this type of transportation aims to minimize product transfer costs, and is often used to transfer petroleum and minerals. It is notable that the owner of the ship and the cargo is one person.

• 2) Irregular transportation: this type of transportation occurs with the goal of maximizing profits with no special rules and preset time. In addition, different ports are visited and their demands are met.

• 3) Regular transportation: in this type of transportation, which includes container ships, the goal is to maximize profits, in a way that the ship visits different ports in fixed routes at the same time intervals, and loading and unloading are carried out in each port. Regular transportation shipping companies provide services in the form of longterm, short-term, and spot contracts.

It is notable that the current research focused on regular transportation. The ship routing problem has been assessed in many studies, most of which can be considered as specific applications of the vehicle routing problem, where cargo is transferred between several loading and unloading ports. One of the most comprehensive studies in this area was conducted by Christiansen et al. in 2004 and 2013 (Christiansen et al., 2013). Moreover, while there are uncertainties in maritime transportation, the majority of studies in this field have evaluated the ship routing problem in a definitive environment. There are some interesting exceptions in ship routing and planning in studies performed by Iswanto (2019) and Kisialiou et al. (2019). In fact, these researchers focused on the topic of uncertain demand and changing climatic conditions at oil and gas platforms (Kisialiou et al., 2018, 2019). Korsvik and Fagerholt (2012) and Kosmas and Vlachos (2012) considered irregular ship routing problems along with other important decisions. Moreover, they developed several heuristic approaches to solve the proposed problem (Korsvik et al., 2010;Kosmas and Vlachos, 2012). Norstad et al. (2011) assessed the topic of ship speed and route optimization in an integrated manner (Wang et al., 2019). The foregoing research was expanded in 2019 by Wang et al., who evaluated the effects of measures taken to decrease pollutant emission on operational decisions of transportation companies, as well as their environmental and economic outcomes (Wu et al., 2021). Both of these studies applied the local search heuristic method with several start points. Wu et al. (2021) evaluated bulk carrier routing by selecting batched cargo. These scholars presented a combined problem of three sub-problems in irregular transportation (irregular ship routing problem) including: 1) fleet adjustment, 2) batched cargo selection, and 3) ship routing. In the end, a tailored branchand- price-and-cut algorithm was developed to solve the compact mixed-integer linear programming formulation. According to the results, the robust algorithm of the research led to the production of optimal or near-optimal solutions in a short computational time (logical) for real samples (Brønmo et al., 2010).

Brønmo et al. (2010) applied the “column generation algorithm” to solve the ship routing problem with flexible cargo sizes. In the end, the algorithm had a better performance, compared to the method in which all columns are generated from the beginning (Meng et al., 2015). Stålhane et al. (2012) proposed a branch-price-and-cut method to solve a ship routing problem, where cargos were picked up and delivered (Hwang et al., 2008). Meng et al. (2015) solved the fuel and ship routing problem using a branchand- price (B&P) approach (Homsi et al., 2020). Considering an unstable maritime market, Hwang et al. (2008) proposed a ship routing problem, in which profit difference was minimized. The model was solved using the B&P method (Tirado et al., 2013). Homsi et al. (2020) proposed an exact B&P algorithm to solve the ship routing problem. These scholars presented a set of acceleration techniques to optimize the algorithm. In the end, algorithm performance was tested using a set of small data, the results of which demonstrated the algorithm’s ability to solve larger-scale samples (Halvorsen-Weare et al., 2013).

Most studies in the field of ship routing have focused on definitive parameter tuning, a small number of authors and researchers have taken uncertainty into account. An example is a research by Hwang et al. (2008), who considered uncertainties in revenue from renting ships and transporting instant market cargo. They aimed to maximize the expected revenue of a shipping company under defined profit variance limits (Tirado et al., 2013). Tirado et al. (2013) addressed a dynamic ship routing problem, in which new cargos were randomly entered into the decision- making space. They adopted three heuristics to solve their proposed model (Agra et al., 2013). Halvorsen et al. (2013) investigated a ship routing and scheduling problem in liquefied natural gas (LNG) industry. In their proposed problem, LNG was transported from a single producer to a set of customers over a period of time (planning horizon). In this study, the researchers took uncertainties in travel time and the rate of daily LNG generation into account. They developed a simulation-optimization framework to solve the proposed model and presented several approaches to improve the results at the end (Huang and Han, 2021). Agra et al. (2013) considered uncertainty in travel time in a ship routing problem. In the end, a robust column-and-row generation optimization algorithm was introduced (Liu et al., 2020). Huang and Han (2021) optimized the route of containers in urban areas. They proposed a multi-objective mathematical model and ranked its solutions by the Topsis method (Li et al., 2020). Liu et al. (2020) scheduled the train route using an optimization mathematical model. They divided demand into several sections using a variable neighborhood search algorithm (Zorarpacı and Özel, 2016).

Today, the efficient solving of many hybrid optimization problems known as NP-hard problems is one of the main challenges of mathematicians, scientists, and engineers. In the present study, we aimed to evaluate one of these problems known as the container ship routing problem while assuming certain time windows and demands of destination porters. In the ship routing problem, the main focus was on scheduling and routing a fixed fleet of ships in order to transport a set of cargoes under certainty. Another innovation of the present study was using novel meta-heuristic methods (differential evolution and grey wolf algorithms) to solve the container ship routing problem. The remainder of the study is described as follows: section 2 presents the research problem, as well as the necessary definitions and assumptions related to the ship routing problem. Section 3 expresses the final mathematical model and symbols, and section 4 introduces the differential evolution and grey wolf algorithms. Section 5 shows the numerical results and model implementation using the mentioned algorithms, and section 5 concludes. Moreover, approaches are proposed for future studies in section 6.

## 2. STATEMENT OF THE PROBLEM AND KEY DEFINITIONS

It is better for the customers of a container terminal to minimize the returned time. In other words, the waiting time is minimized and container loading and unloading are carried out as fast as possible to save on terminal costs. To reduce the time spent on container ships, terminal officials place particular emphasis on allocating resources and docks to ships. In the maritime industry, container terminal managers know that customers will seek another port if they are dissatisfied with port performance. Therefore, many of them tend to decrease (minimize) the returned time of ships with the existing resources (incurring the lowest costs) (Wu et al., 2021). The following are definitions of the three essential terms used in this study:

• Ship routing problem: is one of the most important elements in the assessment of the performance of a shipping company. Finding the best route is one of the important issues in maritime transportation. However, the most suitable route is not necessarily the shortest route in this industry, and several other factors, including fuel consumption, demand of destination ports, and safety, are taken into account in decision-making with different degrees of importance.

• Main port: are ports that are on the international routes of container ships (intercontinental), and large container ships travel there with a large container volume. Main ports must have suitable equipment, draft, geographical location, and communication lines in order to attract customer satisfaction.

• Loading capacity of a ship: the difference between the amount of heavy handling and the amount of light handling is called cargo carrying capacity. The unit of container transport volume is TEU and represents a 20-foot container.

## 3. MATHEMATICAL MODELING

In this study, we proposed an optimization mathematical model to minimize the total variable shipping costs, including travel costs (fuel + personnel), toll fees, and port tariffs, while taking the limitations of delivery, carrying capacity, and time windows into account. The elements of the model are presented below:

(1)

(2)

$s i k ϕ + t i k ϕ + d i j × v e l k − s j k ϕ ≤ M ( 1 − x i j k ϕ ) ∀ i , j ∈ P , i ≠ j , ∀ k ∈ V , ∀ ϕ ∈ Φ$
(3)

$s i k ϕ γ ( i − 1 ) k ϕ α ≤ α α ∀ i ∈ P , i ≠ j , ∀ k ∈ V , ∀ ϕ ∈ Φ , ∀ α ∈ C$
(4)

$∑ α α m a x q α γ i k ϕ α ≤ Q k ∀ k ∈ V , ∀ ϕ ∈ Φ , ∀ i ∈ P$
(5)

$∑ k = 1 k m a x γ i k ϕ α = 1 ∃ i ∈ P , ∃ ϕ ∈ Φ , ∀ α ∈ C$
(6)

$∑ i = 1 p γ i k ϕ α x i j k ϕ ≥ 1 j = e α , ∀ k ∈ V , ∀ ϕ ∈ Φ , ∀ α ∈ C$
(7)

$S t a r t i ≤ s i k ϕ ≤ F i n i s h i ∀ k ∈ V , ∀ ϕ ∈ Φ , ∀ i ∈ P$
(8)

The input variables used in the above formula were:

Now, for each i, j ∈ P: i ≠ j, kV, ϕ ∈ Φ, and α ∈ C, we have:

• dij Length of the edge (I, j) corresponding to the distance from the i-th port to the j-th port in nautical miles

• velk Ship velocity (knot)

• Qk The capacity of the k-th ship

• aα Time of receiving the a-th container

• oα, eα The origin and destination ports of the a-th container

• fik Tariffs of the i-th port for the k-th ship

• ck Travel costs (fuel consumption in kilogallon) for the k-th ship in dollars per nautical mile

• $s i k ϕ$ When the k-th ship arrives at the ϕ-th port in the ith travel

• Starti Work start time of the i-th port

• Finishi Work finish time of the i-th port

• M A large fixed number

The model has two binary decision-making variables and seven constraints, as follows:

• $x i j k ϕ$ : 1, if the k-th ship travels from the i-th port to the j-th port in the i-th travel; otherwise, 0.

• $γ i k ϕ α$ : 1, if the k-th ship loads the a-th container after leaving the i-th port in the ϕ-th travel.

• Constraints 1: ensure that the ship will leave any port it enters and will travel to another port.

• Constraints 2: prevent the start of port operations before the arrival of the ship.

• Constraints 3: guarantee that the container delivery deadline does not exceed the determined time.

• Constraints 4: ensure that the total weight of containers loaded into the ship does not exceed the ship’s capacity.

• Constraints 5: guarantee that each container is delivered to the port by one and only one ship.

• Constraints 6: integrates ship routing problem and container loading problem with each other. For instance, if a container is loaded on a ship, then that ship must travel to the port of destination of the container.

• Constraints 7: is related to time windows of start and finish of the work in each port

## 4. IMPLEMENTATION AND PROBLEM-SOLVING

In this study, the differential evolution metaheuristic and grey wolf algorithms were used to solve the model. Before solving, a brief description was provided to learn about the algorithms, followed by the assessment and comparison of the efficiency of the two algorithms in solving ship routing problems using a numerical example.

### 4.1 Differential Evolution Algorithm

Differential evolution algorithm (DE) was first introduced by Storn and Price in 1995 (Zorarpacı and Özel, 2016). According to these scholars, the algorithm can properly optimize non-linear non-differentiable functions and can be used as a rapid and robust method to optimize problems in continuous spaces. The DE algorithm was presented to deal with the main problem of the genetic algorithm (GA), which is the lack of local search. In fact, the main difference between the GA and the DE algorithm is the selection operator. In the GA selection operator, the chance of choosing a solution as a parent depends on its level of competence. In DE algorithm, however, all solutions have an equal chance of being chosen. In other words, their chances of being selected do not depend on their degree of competence. After the generation of a new solution using a self-tuning mutation operator and a crossover operator, the new solution is replaced by the previous amount. Contrary to other algorithms, the crossover operator is used first in this algorithm, followed by the mutation algorithm in order to create a new generation. Moreover, no certain distribution is used to apply the mutation operator. In fact, the length of the mutation step is determined based on the distance between the current members. The evolution process of the algorithm is based on gradual and constant improvement in the initial guess (candid response), there is a need for a fitness function to compare the responses based on the principles of all evolutionary algorithms. Compared to other real equation solution methods (e.g., Newton method), one of the strengths of the DE algorithm is its lack of need for function gradients. Therefore, a relatively optimal response is hoped to be obtained for different irregular multidimensional continuous/non-continuous functions without any information about the type of function. Complementary information about the DE algorithm was provided by Li et al. (2020).

### 4.2 Grey Wolf Algorithm

Optimization is a vital part of humans’ lives. Therefore, various optimization algorithms with a metaheuristic approach have been introduced. The GWO is one of the most recent metaheuristic algorithms, presented by Mirjalili et al. in 2014 and generalized into a multiobjective one in 2016. This algorithm belongs to the group of collective intelligence algorithms and, similar to many other metaheuristic algorithms, is inspired by nature and is based on a hierarchical structure that models the social behavior of gray wolves during hunting. In the implementation of the GWO algorithm, four types of gray wolves of a tribe, such as alpha (α), beta (β), delta (δ) and omega (ω), are used to model the hierarchical leadership of gray wolves, the three main hunting steps of which include chasing, approaching, and tracking prey. The results of different benchmark functions indicate the optimal performance of the algorithm compared to similar algorithms.

As observed in Figure 1, wolves live in packs and have a precise and linear social hierarchy in their community. The first group is the Alpha wolves, which are the leaders of the wolf pack. Alpha wolves make decisions of the community such as choosing the prey, where to sleep, and habitat. However, Alpha wolves respect others’ decisions in some cases. The second level of the hierarchy includes beta wolves, which act as advisers to Alphas. They receive orders from Alpha wolves but they give orders to lower-ranking wolves. They take care of Alpha wolves’ orders and give feedback to them. The other group includes Delta wolves, which receive orders from Alpha and Beta wolves. Delta wolves are responsible for guarding and preying. Omega wolves have the lowest rank and surrender to the orders of other groups.

## 5. NUMERICAL RESULTS

### 5.1 Presentation of a Sample Problem

This section provides a numerical example to illustrate how the model works. In this routing example, 15 ships with different capacities and similar fuel consumption, as well as 45 ports with different demand and time windows were considered. Ships were in their ports of origin at the moment of zero. To quantify the parameters (tuning the parameters of the proposed algorithms), Taguchi method was used in Minitab software. Table 1 shows the level of parameter tuning in the presented algorithms.

### 5.2 Algorithm Performance Measurement

In order to measure the efficiency of the proposed algorithms, an example of the problem was presented and solved. Tables 2 and 3 show information about the sample. All calculations were performed in MATLAB software.

Tables 4 and 5 show the numerical results of 30 consecutive implementations of each algorithm. In addition, three important quantities were obtained for each algorithm. F shows the value of the objective function, T is time (seconds) and GAP is the percentage of difference in the response obtained by each algorithm with the best response. In fact, if F* is the optimal amount obtained from each algorithm, the value of GAP is obtained from $F * − F F *$. The fourth to eighteenth rows represent the optimal route for each ship, and the nineteenth and twentieth rows show the total distance traveled and the total container handled by each of the 15 existing ships. According to the output tables, the ED algorithm had a better performance since it presented the best solution in rational time. While the GWO was solved in a shorter time, the ED algorithm yielded a more optimal response, and this difference may increase at larger scales. In fact, the optimal solution in the ED algorithm led to a higher utility of carrying capacity (3954 TEU displacement in a distance of 4451 nautical miles).

## 6. CONCLUSION

The present study aimed to solve a ship routing problem while minimizing the total carrying costs, including travel costs (fuel + personnel), toll fees, and port ta-riffs, while taking the limitations of delivery, carrying capacity, and time windows into account. Given the complexity of the problem, we used two metaheuristic algorithms of ED and GWO. The results were indicative of proper performance of the two algorithms in terms of closeness to accurate response and short solution period. It is recommended that adding environmental target functions, analyzing the sensitivity of time windows in ship fuel consumption, comparing the solution approaches with other novel metaheuristic algorithms, integrating the proposed model with other problems of container terminals be taken into consideration in future studies.

## Figure

Schematic presentation of the social hierarchy of grey wolves.

## Table

Information related to ships

Information related to ports

Numerical results of DE

Numerical results of grey wolf algorithm

## REFERENCES

1. Agra, A. , Christiansen, M. , Figueiredo, R. , Hvattum, L. M. , Poss, M. , and Requejo, C. (2013), The robust vehicle routing problem with time windows, Computers & Operations Research, 40(3), 856-866.
2. Brønmo, G. , Nygreen, B. , and Lysgaard, J. (2010), Column generation approaches to ship scheduling with flexible cargo sizes, European Journal of Operational Research, 200(1), 139-150.
3. Christiansen, M. , Fagerholt, K. , Nygreen, B. , and Ronen, D. (2013), Ship routing and scheduling in the new millennium, European Journal of Operational Research, 228(3), 467-483.
4. Halvorsen-Weare, E. E. , Fagerholt, K. , and Rönnqvist, M. (2013), Vessel routing and scheduling under uncertainty in the liquefied natural gas business, Computers & Industrial Engineering, 64(1), 290-301.
5. Homsi, G. , Martinelli, R. , Vidal, T. , and Fagerholt, K. (2020), Industrial and tramp ship routing problems: Closing the gap for real-scale instances, European Journal of Operational Research, 283(3), 972-990.
6. Huang, D. and Han, M. (2021), An optimization route selection method of urban oversize cargo transportation, Applied Sciences, 11(5), 2213.
7. Hwang, H.-S. , Visoldilokpun, S. , and Rosenberger, J. M. (2008), A branch-and-price-and-cut method for ship scheduling with limited risk, Transportation Science, 42(3), pp. 336-351.
8. Iswanto, A. H. (2021), Impact of lean six sigma at pharmacy unit on hospital profitability before and during Covid-19 pandemic, International Journal of Lean Six Sigma, 12(4), 718-743.
9. Kisialiou, Y. , Gribkovskaia, I. , and Laporte, G. (2018), Robust supply vessel routing and scheduling, Transportation Research Part C: Emerging Technologies, 90, 366-378.
10. Kisialiou, Y. , Gribkovskaia, I. , and Laporte, G. (2019), Supply vessel routing and scheduling under uncertain demand, Transportation Research Part C: Emerging Technologies, 104, 305-316.
11. Korsvik, J. E. , Fagerholt, K. , and Laporte, G. (2010), A tabu search heuristic for ship routing and scheduling, Journal of the Operational Research Society, 61(4), 594-603.
12. Kosmas, O. T. and Vlachos, D. S. (2012), Simulated annealing for optimal ship routing, Computers & Operations Research, 39(3), 576-581.
13. Li, W. , Meng, X. , and Huang, Y. (2020), Fitness distance correlation and mixed search strategy for differential evolution, Neurocomputing, 458, 514-525.
14. Liu, J. , He, S. , and Zhang, M. (2020), Study on cargo products’ layout optimization of truck railway line, Mathematical Problems in Engineering, 2020, 99- 105,
15. Meng, Q. , Wang, S. , and Lee, C.-Y. (2015), A tailored branch-and-price approach for a joint tramp ship routing and bunkering problem, Transportation Research Part B: Methodological, 72, 1-19.
16. Mirjalili, S. , Mirjalili, S. M. , and Lewis, A. (2014), Grey wolf optimizer, Advances in Engineering Software, 69, 46-61.
17. Norstad, I. , Fagerholt, K. , and Laporte, G. (2011), Tramp ship routing and scheduling with speed optimization, Transportation Research Part C: Emerging Technologies, 19(5), 853-865.
18. Stålhane, M. , Andersson, H. , Christiansen, M. , Cordeau, J. F. , and Desaulniers, G. (2012), A branch-price-andcut method for a ship routing and scheduling problem with split loads, Computers & Operations Research, 39(12), 3361-3375.
19. Tirado, G. , Hvattum, L. M. , Fagerholt, K. , and Cordeau, J. F. (2013), Heuristics for dynamic and stochastic routing in industrial shipping, Computers & Operations Research, 40(1), 253-263.
20. Wang, X. , Norstad, I. , Fagerholt, K. , and Christiansen, M. (2019), Green tramp shipping routing and scheduling: Effects of market-based measures on CO2 reduction, In Sustainable Shipping, Springer, Cham, 285-305.
21. Wu, L. , Wang, S. , and Laporte, G. (2021), The robust bulk ship routing problem with batched cargo selection, Transportation Research Part B: Methodological, 143, 124-159.
22. Zorarpacı, E. and Özel, S. A. (2016), A hybrid approach of differential evolution and artificial bee colony for feature selection, Expert Systems with Applications, 62, 91-103.
 Do not open for a day Close