Fleet route selection prediction problem based on support vector machine

Abstract

Bulk shipping transport is an important part of ocean transportation. One of the most important aspects for bulk ship owners is to make choices about the ship’s operational area for the next planning period. In this article, based on the Baltic Supermax Index and historical decision data of different companies, the support vector machine model is used to predict the dry bulk carrier route selection, which provides a solution to this problem. The numerical results show that the model and the algorithm proposed in the paper can well work and can achieve good precision. Via comparative analysis, we prove that the model we proposed in this article has better performance than some other common methods in the research area. The proposed model would support dry bulk shipping company in route choice so as to balance the profit and potential opportunity when making choice for ships’ route selection.

Introduction

Dry bulk shipping market is a derivatives market of the global trade. It has a seasonal and cyclical fluctuations year by year. Figure 1 shows how dry bulk shipping market level changes in recent 1 year. For example, in North American continent, during grain harvest time, market is usually at a relatively high level. And during the Christmas and Chinese New Year time, as people usually reduce production and operation activities, market is then on a relatively low side. Some countries and regions that have fixed exports of bulk minerals, coal, grain, and imported commodities have formed some fixed routes for many years. In the absence of war, serious natural disasters, and other force majeure, the supply on some routes has remained cyclical throughout the year. Relative to the seasonal and periodic rules, the most basic normality of the market is volatility and uncertainty. Therefore, we believe that the development trend of dry bulk shipping market in a year may be a repeat of a similar situation in recent history. How to effectively combine the two characteristics of the shipping market, portray the mathematical model closest to the actual situation and optimize the operation of the fleet in the short term (3–6 months) in the future. Especially, for the uncertainties in the various links of a fleet’s short-term voyage task scheduling, how to accurately deal with the actual situation, to provide decision-makers with systematic optimization, decision-making scheme is the research focus of this article.

Figure 1.

Baltic Dry Index summary (data from tradingeconomics.com).

For a non-scheduled fleet of ships operated by a particular ship owner, generally in a short–medium term decision-making, the decision-makers will allocate the fleet resources to different operational areas at the end of the planning period and ensure the ships through subsequent selection of diversity. The team can have a relatively stable income level in the follow-up operations. The shipping market is affected by many uncertainties such as trade, shipping cycle, season, geographical environment, politics, and war. Therefore, most fleet operators will combine their own sources of supply, the operation experience, and judge the future market. Other factors will put capacity into the route with expected supply and high market returns. However, in order to balance operating income with market risk, it is also necessary to invest part of the ships in other sea areas with less temporary supply, or in the area that is conducive to subsequent voyage arrangements. This balanced allocation of ships can reduce the risk of potential loss by market prejudgment errors or market mutations. Also, it can make the fleet grow steadily. After determining the final specific location of each ship, the decision-makers will then perform voyage task scheduling on a case-by-case basis for each ship based on market information, forecast data, and operational experience.

This article mainly introduces how the ship owners will arrange their tonnage in the spot market and continue to operate. How to formulate the shipping routes of the fleet according to historical experience and current market level and what proportion of the ships they control will end at the planning period. It is configured to operate in different ocean areas.

For shipping companies, the choice of ship operation area is one of the most important aspects of fleet management, but various factors affecting decision-making are interrelated and difficult to analyze through general mathematical methods. In the route selection of historical ships, the route decisions of other shipping companies in the market are mostly correct and can bring profits to the shipping companies. Behind these long-term and large-scale historical decision-making results, there are actually potential rules. The decisions of most of the participants in the market are made based on huge historical data. There are many participants in the dry bulk market. In most cases, the ship owners will make the decision of most participants in the market at similar market levels in the recent period as a reference for their own choice. According to the characteristics of the decision-making process of the ship owner, the author collects the ship’s track data of the market for a period of time as a reference for the basic data of the forecast of the future ship operation area of the market participants under the current market level.

Literature review

The choice of ship operation route belongs to the research of fleet planning. In this field, Xie and colleageues^1,2 are equivalent to the late 1980s and early 1990s. A series of methods were proposed.^3–8 Yang et al. ⁹ introduced a new method in 2014. Some effective methods on route choice and operation area can be found in these literatures. Yao et al. ¹⁰ introduced an improved particle swarm optimization for a vehicle routing problem (VRP). Yu and colleagues^11–13 used ant colony model worked on some routing problems. The fleet planning method in complex environments, but the research on the selection of specific routes for ships is still relatively small. Bakkehaug et al. ¹⁴ proposed a new multi-stage stochastic programming formulation for strategic fleet renewal in shipping . The new formulation explicitly handles uncertainty in parameters such as future demand, freight rates, and vessel prices. The uncertain parameter is hard to predict which is quite similar as in our problem. Wang et al. ¹⁵ presented an operational network representation of a liner shipping network. Based on the network, an integer linear programming model is formulated to obtain container paths with minimum cost. Finally, they added constraints to the integer linear programming model, excluding those paths already obtained, so as to find all the container paths. Their paper shows an innovate method to solve fleet route selecting problem. MW Ng ¹⁶ visited a class of liner fleet deployment models. He pointed out an implicit (and unnecessary) assumption in the class of models that can lead to fleet deployment plans that employ more vessels than strictly necessary.

Accurate route selection prediction is difficult. Time series model, artificial neural network, and support vector machine (SVM) model are the most important predictive research methods. For the application of prediction methods, Stephanedes et al., ¹⁷ DeLurgio ¹⁸ respectively gave different directions for discussion. The time series model has obvious lag in prediction, and the similarity between future information and historical information is highly dependent. The change of historical average data will have a great impact on the prediction results. ¹⁹ And recent years, some literatures can be found the well prediction result basis short-term traffic condition.^20–22 Guan et al. ²³ also use SVM model to get well prediction result on shipping index. The neural network simulates the function of the human brain nervous system based on the neurons of the human brain. The ultimate goal is to develop an artificial system with intelligent information processing functions such as learning, association, and memory. Its advantage is its unique nonlinear adaptive information processing capability, but there are also problems of structure determination, over-learning, under-learning, and local convergence.^24–26 The main research method of SVM^27–30 is to extract the laws that cannot be obtained by principle analysis from the finite observation data (sample). And then use it to analyze objective objects, predict and judge unknown data or new phenomena that cannot be observed.^31–33 SVM is easy to balance the degree of fit and generalization, and the generalization ability is obviously superior to neural network. This is also the choice of SVM to predict the selection of bulk carrier routes.

According to the research of Lu and Chen ³⁴ and Chen and Zhao, ³⁵ it can be determined that the dry bulk shipping index has a clear guiding role for future market trends. In Lu and Chen’s paper, ³⁴ a null means stationary series is reached which matched autoregressive moving average auto regression moving average (ARMA) model after removing the long-term tendency, cyclical fluctuating, and seasonal fluctuating one by one from Baltic Freight Index. And in the papers of Lu et al. ³⁴ and Chen and Zhao, ³⁵ we clearly got that the Baltic Dry Index (BDI) number has effective information for market player to make decision. Ruan et al. ³⁶ examined cross-correlations between BDI and crude oil prices. Alizadeh et al. ³⁷ investigated the effect of vessel specific and market variables on the probability of scrapping dry bulk ships with an index dataset from 2012 to 2015. Some bilateral effects are found in Dai et al.’s paper, ³⁸ showing that lagged variances could affect the current variance in a counterpart market, regardless of the volatility transmission. All in all, from above, we can conclude that Bulk dry index has clear guiding role. In this article, a Supermax bulk carrier is taken as an example. The Baltic Supermax Index (BSI) of the four routes currently selected by the fleet is an input variable, and the final unloading of the ships at the end of the planning period corresponds to the beginning of the planning period. The position change is predicted for the output variable. This method provides a new perspective for the choice of ship operation area and also expands the application range of the SVM model.

Bulk ship fleet route selection prediction model

SVM model construction

The basic practical idea of SVM model prediction is to map sample data to high-dimensional space. The original problem is to solve the problem of regression hyperplane. SVM model transforms it into solving quadratic programming problem and solves complex nonlinearity problem with simpler linear regression method.

Given a sample with unknown relationship ( $x_1$ , $y_1$ ),…, ( $x_i$ , $y_i$ ) $(x_i\in X\subseteq R^n,y_i\in Y\subseteq R)$ . In this problem, the number of the four known indices is the result of the route selection corresponding to the fleet. The SVM model can be mapped to a high-dimensional feature space H by nonlinear mapping $\varphi$ and linearly approximated. The formula is described as

$$f\left(x\right)=\omega \times \phi (x)+b$$

(1)

$\omega$ is a hyperplane weight vector and b is Bias term.

In order to determine the regression coefficient $\omega$ and b, according to the statistical learning principle, the minimum regularized risk functional under certain constraints can be solved

$$min\frac{1}{2}\Vert \omega {\Vert }^2+C\frac{1}{l}\sum _{i=1}^l({\xi }_i+{\xi }_i^{*})$$

(2)

$\mathrm{st}:$

$$y_i-\omega \times \varphi \left(x_i\right)-b⩽\epsilon +{\xi }_i$$

(3)

$$\omega \times \phi \left(x_i\right)+b-y_i⩽\epsilon +{\xi }_i^{*},i=1,\dots ,l$$

(4)

$${\xi }_i,{\xi }_i^{*}⩾0$$

(5)

The first item of equation (2) is called a regagrangian operatoularization term, which makes the function flatter to improve generalization ability. The second term of equation (2) is the empirical risk functional, which is determined by different loss functions. Constraint C > 0 controls the degree of penalty for samples that exceed the error $\epsilon$ .

Equation (2) is a convex quadratic optimization problem that needs to be transformed into a dual problem

$$\begin{array}{c}\multicolumn{1}{c}{L=\frac{1}{2}\Vert \omega {\Vert }^2+C\sum _{i=1}^l({\xi }_i+{\xi }_i^{*})-\sum _{i=1}^l({\eta }_i{\xi }_i+{\eta }_i^{*}{\xi }_i^{*})}\\ \multicolumn{1}{c}{-\sum _{i=1}^l{a}_i(\epsilon +{\xi }_i-y_i)+\omega ·\phi (x)+b)}\\ \multicolumn{1}{c}{-\sum _{i=1}^i{a}_i^{*}(\epsilon +{\xi }_i^{*}-y_i-\omega ·\phi (x_i)+b)}\end{array}$$

(6)

L is Lagrangian operator, ${\eta }_i$ , ${\eta }_i*$ , $a_i$ , $a_i*$ are Lagrange multiplier, ${\eta }_i$ , ${\eta }_i*$ , $a_i$ , $a_i*⩾0$ ; derivation of the initial variable is as follows

$${\partial }_{b}L=\sum _{i=1}^l(a_i+a_i^{*})=0$$

(7)

$${\partial }_{\omega }L=\omega -\sum _{i=1}^l(a_i+a_i^{*})\phi (x_i)=0$$

(8)

$${\partial }_{{\xi }_i}L=C-a_i-\eta =0$$

(9)

Can be obtained after solving

$$\omega -\sum _{i=1}^l(a_i-a_i^{*})x_i=0$$

(10)

then

$$f(x)=\sum _{i=1}^l(a_i-a_i^{*})\phi (x_i)·\phi (x)+b$$

(11)

define $P(x_{i,}{x}_j)=\phi (x_i)·\phi (x_j)$ , then conclude

$$f(x)=\sum _{i=1}^l(a_i-a_i^{*})P(x_i,x)+b$$

(12)

$P(x_i,x_j)$ is the inner product of the vector $x_i$ and vector $x_j$ on the feature space, which is called kernel function. Kernel functions can be calculated directly on the input space without having to map to high-dimensional space. The kernel function is the core of the SVM, and different kernel functions can construct different SVMs.

Taking the Supermax dry bulk carrier as an example, the BDI is a very important reference for the shipping company to select the route. ³⁹ The specific index of the Supermax dry bulk carrier is the BSI. The main routes of the four Supermax dry bulk carriers constitute the comprehensive index of BSI according to their respective importance and proportion in the market, reflecting the actual price level of daily transactions in the market, which is important for the ship owner’s market decision-making behavior.

The basic idea of SVM model prediction is to map sample data to high-dimensional space. The original problem is to solve the problem of regression hyperplane. SVM model transforms it into solving quadratic programming problem and solves complex nonlinearity with simpler linear regression method problem. The SVM model is very suitable for solving some complex or nonlinear problems. The principle is to map the input data to a high-dimensional feature space through the kernel function. The route selection prediction problem proposed in this article is nonlinear. The SVM model in this article is used to map the relationship between the output of four routes and the input (four-route BSI index), so as to predict the decision making behavior of other participants in the market as the ship’s next fleet scheduling reference.

In this article, the average relative error (MAPE) is used to judge the validity of the model

$$MAPE=\frac{1}{n}\sum _{k=1}^n\frac{|S_{m,k}\left(t+1\right)-S_m\left(t+1\right)|}{S_m\left(t+1\right)}\times 100\%$$

(13)

n is the number of test samples, $S_m(t+1)$ is the number of actual ship routes selected on the $t+1$ day of the route m, and $S_{m,k}(t+1)$ is the number of predicted ship routes selected on the $t+1$ day of the route m.

MAPE is the most intuitive comparison of the prediction results and the true value deviation. The percentage of prediction error can be clearly stated. At the same time, the application of this indicator can also be used to measure the prediction results of different models based on the same input data. It enables the application of different methods in this field to clearly compare with each other.

Parameter calibration

The accuracy of the prediction model is determined by the selection of the kernel function and the calibration of the parameters. This article determines the parameters $C,\epsilon ,\delta$ of the radial basis kernel function by grid search. By step-by-step search, first fix one parameter (such as $\epsilon$ ), search for another parameter (such as C), and calculate the error $\mathrm{MS}{E}_i$ . Then, another parameter (such as C) is fixed to search for the parameter (such as $\epsilon$ ) and then calculate the error $\mathrm{MS}{E}_{i+1}$ . The criterion for stopping is that the two errors meet the previously set accuracy. After getting the parameter combination of this article is (0.125, 0.0625, 1.32).

Implementation and numerical results

Application of SVM to predict dry bulk fleet route selection

Figure 2 shows the structure of the SVM model presented in this article. There are four input variables: BSI value for the internal round-trip route of the Atlantic $(x_1)$ , BSI for the Atlantic to Pacific route $(x_2)$ , BSI for the internal round-trip route in the Pacific $(x_3)$ , and BSI for the Pacific to Atlantic route $(x_4)$ . $x_1,x_2,x_3\mathrm{and}{x}_4$ represent the four routes index of BSI which are $S1A,S2,S3,S4A$ separately. The exact number can be referred to Appendix 1. The output variable is the ratio of the four routes selected by the fleet $(y_1,y_2,y_3,y_4)$ .

Figure 2.

Prediction model of line choice.

As shown in Figure 3, a shipping company has two routes to choose from in the Pacific Ocean. You can choose the Pacific to Atlantic route, or choose the Pacific internal round-trip route. Similarly, ships in the Atlantic also have two routes to choose from, you can choose the Atlantic to Pacific route, or choose round-trip routes within the Atlantic Ocean. In the vast market, most dry bulk shipping players are very experienced and mature companies. The shipping company uses the BSI value as an important reference indicator when making decisions. When we made a decision, we knew what the decision of most ship owners is when it is similar to the current market index in a certain period of time. Then it can be used as a reference for decision-making.

Figure 3.

Four lines of Supermax bulk carriers.

As of the end of 2014, there were approximately 5200 Supermax dry bulk carriers being operated on the market, excluding some special-purpose vessels and old vessels. The operational data of more than 4000 vessels can be used as a database sample of the SVM model, with an average of voyages per vessel. The operation is 40–50 days of calculation, so that an average of 80–100 ships per day in the market will make decisions for the execution plan of the next voyage. In order to verify the validity of the model, we collected the BSI and ship navigation trajectory data from October 2014 to August 2015 for a total of 10 months. Using the above data, we can verify the effectiveness of the SVM model to predict the ship route selection model.

Assumptions

1. All ships only perform a single voyage mission. In actual operation, the ship owner’s ship may perform a single voyage, or a longer period until the long-term charter. Due to the complexity of the problem, this article only discusses the assumption that the market ships are all performing a single voyage mission.

2. Regardless of the ship’s need to perform a specific voyage for reshipment or docking (in the case calculation, the data are corrected according to the proportion of the ship obtained from the sample survey data).

3. Regardless of the ship’s execution of its own cargo (in the case calculation, the data are corrected according to the proportion of the ship obtained from the sample survey data).

4. For the sake of calculation, it is assumed that each voyage has a sailing period of 30 days (same ocean area) or 60 days (cross-ocean area).

5. Make a route selection decision 5–10 days before the ship sails.

Data collection

According to the name of the ship and the ship’s own deadweight tons, construction year, captain, and other attributes, the ship’s port record is collected in the sequence of natural dates, so as to obtain the ship’s driving track information. Import data were put into MAPINFO11.0 software to visually see the trajectory of each ship. Based on this information and the characteristics of the operation of the Supermax ships, the direction of execution of the ship’s voyage mission during a specific period of time is judged. Take Figure 4 as an example. A ship visited to eastern India on 26 December 2014. Then she called Australia on January 10 and returned to China at the end of January. Judging from this, the ship’s mission for the voyage should be decided around December 20, and the ship’s decision on the ship’s navigation will be left in the Pacific. Search for daily ship route selections and calculate the percentage of each route selection.

Figure 4.

Ports a vessel had called during end 2014 to early 2015.

We have collected actual observation of 320 ship sample results from June 2014 to August 2015. Also we have collected BSI data from June 2014 to August 2015.

Numerical results

When the shipping company makes a decision, there are two options for pre-empty ship routes in the Atlantic, that is, the round-trip route inside the Atlantic and the transit-trip route from the Atlantic to the Pacific. The situation is similar for the ships pre-empty in the Pacific Ocean. Therefore, it is assumed that the proportion of pre-empty ships on the Atlantic route choosing the internal round-trip routes of the Atlantic Ocean is q. Then the proportion of pre-empty ships choosing the internal transit-trip routes is $1-q$ . In this way, we only need to predict the proportion of the route selection for the round-trip route within the Atlantic and the round-trip route within the Pacific.

According to the actual observation of 320 ship sample results, a total of 62 ships made decisions in February 2015. There are a total of 25 ships in the Atlantic. 10 ships are unloaded in the Pacific region after 2–3 months, and 15 ships are unloaded in the Atlantic region after around 1 month. There are a total of 37 ships in the Pacific Ocean, of which 14 ships are unloading in the Atlantic region after 2–3 months, and 23 ships are unloading in the Pacific region after around 2–4 weeks. Using the SVM model, the 4 months BSI data before 1 February 2015 is used as the learning database, combined with the average BSI calculation within 10 days of the decision period in the case. We got 13 pre-empty ships in the Atlantic, 1–2 months after the final unloading of the port in the Atlantic. Eventually, twelve of them choose to be unloaded in the pacific and 25 ships would open the pacific ocean. After 2–4 weeks, the final port is unloaded in the Pacific Ocean. And few months later, 12 final ports are selected in the Atlantic.

Validity analysation

To verify the validity of the model, we compare the linear regression and K-nearest neighbor models with the SVM model. The results are shown in Table 1. We can see the numerical difference among the three methods according to the actual result. It is quite clear that the SVM model shows best accuracy comparing with the actual result.

Table 1.

Route choice results of the three models and actual result.

	Atl-Atl	Atl-Pac	Pac-Pac	Pac-Atl
Actual result	15	10	23	14
SVM	13	12	25	12
K-nearest neighbor	9	16	30	7
Liner regression	8	17	26	11

SVM: support vector machine.

From Figure 5, it can be seen that for SVM, the average relative error (MAPE) of route selection for pre-empty Atlantic and Pacific ships are 8.0% and 5.4%, respectively. For ships which are pre-empty in the Atlantic, the K-nearest neighbors’ prediction results are similar to those of the linear regression, which is much worse than the SVM results. For ships which are pre-empty in the Pacific Ocean, the SVM prediction results are similar to the linear regression prediction results, which are far superior to the K-nearest neighbors. Overall, the results on the data of SVM are slightly better than the linear regression and far better than K-nearest neighbor method.

Figure 5.

MAPE of SVM, K-nearest neighbor, and linear regression.

In order to test the prediction effect of the model under different input data volumes, we test the prediction accuracy of SVM with the learning database of the BSI of 3, 4, and 5 months before 1 February. The result is shown in Figures 6 and 7.

Figure 6.

Comparative analysis of different input data for ships staying in the Atlantic Ocean.

Figure 7.

Comparative analysis of different input data for ships staying in the Pacific Ocean.

Figures 6 and 7 shows the prediction error obtained from different input database training data. The results are shown when using the data of the last 4 months before the decision date as the input database training data to predict, the accuracy is relatively good. This may be because the data of the first 3 months of input, the amount of data is relatively small which may affect the accuracy. And the data of the first 5 months be entered are too far from the predicted time node, which may brings the model interference. Therefore, the accuracy is not as good as the prediction of the data we chose for 4 months. With 4 months of data support, the input data choosing is more appropriate.

Conclusion

Dry bulk ship owners have many factors to consider when making fleet operation decisions. One of the most important aspects is to make choices about the ship’s operational area for the next planning period. In this article, based on the BSI index (please refer to Appendix 1) and historical decision data of different companies in similar environments, the SVM model is used to predict the dry bulk carrier route selection, which provides a solution to this problem. The typical character of dry bulk shipping market is fluctuation and randomness. Therefore, it is quite hard for ship owners to make decision how to assign their ships in future. With the combination of historical BSI data and other market player’s actions in the model, we can conclude some reference idea for ship owners. In similar basis similar BSI situation, the other shipowner’s actions is of great help to decision makers in choosing ship routes. SVM does not require function form, its generalization ability is very strong, and it can also well map the relationship between input and output of nonlinear or time-varying systems. This article also proves the good prediction results of the model. Therefore, using the SVM model to construct an effective route selection model can provide reference for the shipping company’s route selection. After determining the proportion of the fleet in each route, the number of ships in each oceanic area at the end of the planning period can be obtained as a basis for how to schedule the tasks of each ship.