Dynamic determination of vessel speed and selection of bunkering ports for liner shipping under stochastic environment

Abstract

In this work, we study a liner shipping operational problem which considers how to dynamically determine the vessel speed and refueling decisions, for a single vessel in one service route. Our model is a multi-stage dynamic model, where the stochastic nature of the bunker prices is represented by a scenario tree structure. Also, we explicitly incorporate the uncertainty of bunker consumption rates into our model. As the model is a large-scale mixed integer programming model, we adopt a modified rolling horizon method to tackle the problem. Numerical results show that our framework provides a lower overall cost and more reliable schedule compared with the stationary model of a related work.

1 Introduction

In recent years the trend of increasing bunker prices has threatened the liner shipping companies’ accounting bottom line. To survive, companies need to identify ways to reduce the operating costs. For example, when the oil prices hit $145 a barrel in 2008, Maersk, the world’s biggest liner shipping company, spearheaded the strategy of slow steaming. Now over 200 shipping companies have reduced their vessel speeds, especially in those long-haul loops like Asia to Europe and North America. Empirical estimation has shown that when the vessel speed is reduced by 20 %, it could reduce the fuel consumption by 50 % (Ronen 1982). Although ship liners have to add one or two more vessels in certain routes to keep a weekly service, which results in an immediate increase of the capital cost as well as the administration and labor costs, the savings from fuel cost has the potential to outweigh those cost increases (Ronen 2011). Besides, the environmental benefits of less greenhouse gas emission from slow steaming are also significant. Maersk (2010) announced that on average they had successfully reduced the carbon dioxide emission by 14 % per vessel during 2008.

Besides increasing rapidly, bunker prices also manifest high volatility. It is a well-observed phenomenon that the crude oil prices fluctuate significantly on a daily basis. As a by-product of the crude oil, bunker prices fluctuate no lesser in the spot market. Figure 1 shows the monthly fluctuation of the bunker prices (380 CST grade) at several major ports and that of the crude oil prices from September 2002 to September 2009. Based on this figure, we can roughly say that there is a high correlation of the bunker prices and the crude oil prices and most of the time, the bunker prices are even more volatile than the crude oil prices. Last but not least, bunker prices at different ports around the world usually have significant differences. For example, on September 3, 2008, bunker fuel prices (380 CST) in Singapore were 677.5 US${\$}$/ton. On the same day, bunker prices in Rotterdam were 619 US${\$}$/ton and 650 US${\$}$/ton in Houston.

Fig. 1

Fluctuation of bunker fuel (380 CST) prices at major bunkering ports and world crude oil prices (2002–2009) (Data source Bloomberg 2009 and http://www.test.org/doe/)

The characteristic of the liner shipping is that it usually has a fixed number of port-calls in a cyclical route with a published schedule. While slow steaming would be the general trend when bunker prices are high, high fluctuation and regional differences of the bunker prices complicate the situation because simply reducing the vessel speed may miss out the opportunity of reaching the next port when bunker prices there are low. Thus, in this work, we study how to dynamically determine the vessel speed from the current port to the next one and how much fuel to bunker in the current port with all the bunker prices and bunker consumption information available so far. This is an operational problem when, on the planning level, fleet deployment, scheduling and routing have been decided. Also due to the service nature of the liner shipping, interaction between ships of the same service route and interaction between different service routes, if no transhipment is considered, is very low. Therefore, our study only need to consider a single vessel in one service route only because of the operational independence of ships and routes.

Most of the previous related works did not tackle the uncertain nature of this problem sufficiently. Ronen (1982) studied the trade off between the fuel savings from slow steaming and the loss of revenue from the extension of voyage. It approximated the daily bunker consumption as a third power of the ship speed and derived the optimal speed for ships under different operating scenarios, namely, income generating leg, positioning leg and mixed leg. Perakis and Papadakis (1987) studied the cost minimization problem that a fixed amount of cargo needs to be delivered within a specific period of time between one loading port and one unloading port by a fleet of ships under fixed contract prices. Total fleet operating costs were minimized by choosing the optimal full load and ballast vessel speeds. It modeled the all-purpose fuel (fuel that includes propulsion fuel and all that used during ship operation) rate as a quadratic function of the power of a vessel, which in return was expressed in a power function of the ship speed. In a subsequent study, Perakis and Papadakis (1987) extended the problem with multiple loading and unloading ports. Notteboom and Vernimmen (2009) studied how liner shipping, facing high bunker fuel prices, had adapted their liner service schedules. In this study, the authors provided real-world data about the relationship between the fuel consumption per day and the ship speed for different size of container ships. From the data shown, we can see that the fuel consumption rate against speed for different sizes of ships is actually different although the authors did not look into the details of this issue. Ronen (2011) investigated into the trade off between slow steaming and adding additional vessels in a container route. The objective was to minimize the annual operating cost of the route by deciding the optimal vessel speed and number of ships to deploy.

Yao et al. (2012) studied a problem similar in nature with ours, but in their study, the focus was put on the planning level problem, thus no uncertainty was addressed. On the relationship between the bunker consumption rate and the ship speed, they separated its analysis by the different sizes of ships. In addition, instead of assuming a single third-power relationship, they added a constant coefficient in the regression model, which they proved to be non-trivial by numerical experiments. In all of those above studies, bunker prices were either assumed to be constant or not explicitly considered.

Oh and Karimi (2010) presented a mixed-integer liner programming model that optimized the operation of a multiparcel tanker under uncertain bunker prices. However, only a small number of independent price scenarios were generated before solving the model. Therefore, it was a stationary model in essence. For two types of vessel, “liners” and “trampers”, Besbes and Savin (2009) constructed a dynamic profit maximization problem and derived the optimal refueling policies. In the liner scenario, the problem reduced to a refueling cost minimization problem subject to random bunker fuel prices and limited vessel fuel capacity. However, vessel sailing speed was given in the problem formulation and bunker consumption uncertainty was not considered. They modeled the bunker prices as a sum of three parts: spot crude oil prices with a global price adjustment factor, local supply correction factor for the bunker prices and geographical adjustments due to some other factors. The spot crude oil prices were forecasted using a AR(1) mean-reverting process and the local supply correction factor is described as a two states Markovian process.

To the best knowledge of authors, there is no published result that considers the bunker consumption uncertainty. However, wind force and direction, sea condition, engine efficiency and other factors could influence the bunker consumption in a significant basis. Only by considering the randomness of the consumption rate at any speed could we capture the real-world scenarios more precisely and provide more reliable operational level recommendations for liner shipping practitioners. Therefore, our work is the first attempt to tackle the speed determination and refueling decision simultaneously with the consideration of bunker prices and bunker fuel consumption rate uncertainties.

We will formulate our problem as a multi-stage dynamic model, where the bunker price uncertainty is represented by a scenario tree structure. As the model is a very large-scale mixed integer programming model, we adopt a modified rolling horizon method to tackle the problem.

The rest of the paper is organized as follows: in the following section, we will give a general description of our problem. The modeling for the uncertain bunker prices and daily consumption rate will be discussed. In Sects. 3 and 4, we present our dynamic model and modified rolling horizon solving approach. Two case studies will be conducted in Sect. 5. Finally, the conclusion and future research would be presented in Sect. 6.

2 Problem description

In this paper, we consider the operational level decision making for a single liner ship in one cyclical route (start from one port, travel through all other ports at least once and go back to the original port) with fixed number of port calls and time windows. Time window states the ship arrival and departure times at each port. Two uncertain factors considered in our work are the bunker fuel prices and the bunker fuel consumption rate. A more detailed discussion on how to capture the randomness of these two parts would be given later in this section.

Two key decisions to be made are where and how much to bunker. In the real practice, prior to the arrival of the next port, ship owners would ask the bunker suppliers for quotations, based on which, bunkering decision is made. Once determined, the quotations will rarely change until the ship reaches the port. Therefore, we can conveniently assume that bunkering only happen when a ship reaches one port. Bunkering decision depends on the bunker prices at each port which are usually different across those ports due to local supply–demand factors. The evolution of the bunker prices at each port can be modeled as a discrete-time Markovian process which describes all the possible states and transition matrix between those states. Without loss of generality, we assume that port calls are on a weekly basis and hence we only need to describe the bunker prices evolution on a weekly basis. While this is a drawback of our work, rolling horizon approach can help to mitigate this problem. This is so because we can always update the bunker price scenario tree based on timely real world situations.

Aside from bunkering, another important decision is the ship speed between each leg, which has been commonly assumed to be constant during each leg. How to reach each one port within the scheduled arriving time and save bunker consumption as much as possible through slow steaming is a question faced by most of the practitioners. Traditionally, ships are designed to sail at high speed. Speed that utilizes lower than 40 % of engine load is considered to be damaging to engines according to the recommendation of ship manufacturers. However, a recent experiment done by Maersk (2010), on its own fleet of 110 ships, showed that it is possible for vessels to slow down if necessary.

In our problem, the objective is to minimize the total operational cost in one service loop. The costs considered here are the bunker cost and inventory holding cost. Bunker cost mainly consists of two parts, fixed bunkering cost incurred each time a bunkering takes place and variable cost that depends on the bunkering amount and bunker prices at the time being. Inventory holding cost can be interpreted as a combination of the capital committed in the bunker purchase which could otherwise generate profits through some investment activities and a loss of revenue due to less capacity to carry revenue-generating cargo. As a simplification, we assume that the inventory carrying cost per metric ton (pmt) is constant. Because our study horizon is one service loop which is finite, inevitably, there would be bunker fuel left in the ship fuel tank at the end of voyage. For this amount of bunker fuel left, we deduct it from the total cost based on the bunker prices at the time being.

2.1 Model for bunker prices

To model the evolution of the bunker prices, we use the percentage changes in each leg of the voyage, but the difficulty is that the percentage change can take any continuous value within a reasonable range. Incorporating a random variable with continuous distribution into an optimization model would make solving the model extremely hard, if not impossible.

Therefore, we discretize the bunker price percentage changes and assume they follow a Markovian process, which means current bunker prices only depend on previous period price percentage changes. At first, we determine an interval within which the bunker price percentage changes between two subsequent periods can take place and then we divide this interval into several smaller sub-intervals. Transition matrix depicting the transition among those sub-intervals is constructed. In the end, one discrete point value is chosen to represent each sub-interval. We can either choose the mean of the sub-interval or generate it by random sampling.

For example, if we denote $P^i_t$ and $\theta ^i_t$ as the bunker prices and bunker price percentage changes at port $i$ and time period $t$, and $P^i_0$ as the baseline bunker prices at port $i$ and time $0$, then bunker prices at each port and time period $t$ are based on baseline bunker prices as well as all the percentage changes during previous periods. For example, $P^i_1=P^i_0\times \theta ^i_1$ and $P^i_k=P^i_{k-1}\times \theta ^i_k$. As mentioned, in our work, we approximate the port-by-port bunker price change evolution by the weekly bunker price change evolution.

2.2 Model for bunker consumption rate

In Yao et al. (2012), they assumed that the daily bunker consumption rate could be expressed as $F=k_1\cdot V^3+k_2$, within which $k_1$ and $k_2$ are two constants and they can be different for different vessel sizes, and $V$ is the ship speed (knot). Due to the reasons we mentioned earlier, a noise term is added to depict the uncertainty of bunker consumption. This means

$$\begin{aligned} F=k_1\cdot V^3+k_2+\varepsilon (V) \end{aligned}$$

Based on the data we obtained from a real liner company, we found that the noise $\varepsilon$ is a function of the ship speed and the noise term follows a normal distribution with zero mean and constant coefficient of variation under different ship speeds. Table 1 below shows the results of our analysis.

Table 1 Analysis of daily bunker consumption rate

We have grouped the original data according to the different speed intervals. Notice we have different intervals for different sizes of ships. This is simply because larger ships usually sail under a greater speed. However, this would not be an issue here because for ships of each size category, Table 1 shows that the coefficient of variation is approximately constant. This means that the standard deviation of the bunker consumption within a specific period of time is proportional to the mean consumption. Taking into account that wind and sea current are two of the main factors for the bunker consumption uncertainty and the fact that their influence increases with ship speed would not surprise us with such a conclusion. Also, for different sizes of ships, we state that the coefficient of variation actually decreases with ship size. The intuitive explanation is that bigger ships are usually equipped with more powerful engines, and thus wind and sea current impose relatively less influence on them.

In our dynamic model, we will use chance constraints to control the probability of a ship running out of bunker before reaching the next port to be less than one value.

3 Modeling

As discussed, we model the evolution of the bunker prices by a Markovian process.

In the financial engineering area, researchers use scenario tree models to formulate their problems in which the returns of financial products possess stochastic nature. Mulvey et al. (1997) reviewed the application of multi-stage stochastic optimization on asset/liability management. When it came to the tradeoff between realism and computational tractability, they listed several essential characteristics that a mathematical model for investment problem should possess to render useful application. One possible way that they claimed to be effective in covering all of those characteristics was a scenario tree model. Considering the similar nature of those financial products with bunker prices, here we use the scenario tree to model the randomness of bunker prices.

Bunker price uncertainty in the future times is modeled by a discrete stochastic process $\xi$ that is defined on a probability space of $(\varOmega ,\fancyscript{F},\fancyscript{P})$ with

$$\begin{aligned} \xi =\{{{\xi }}_{t}:= {{\theta }}^{i}_{t}\}_{{t}\in {T}}. \end{aligned}$$

$\theta ^i_t$ denotes the bunker prices percentage change at time period $t$ and port $i$. To make our multi-stage stochastic optimization problems computationally tractable, following assumptions on the property of $(\varOmega ,{\fancyscript{F}},{\fancyscript{P}})$ are made: first, $\varOmega$ is finite and $\varOmega =\{w_s\}_{s\in \fancyscript{S}}$ with ${\fancyscript{S}}=\{\mathbf{1},\ldots ,\fancyscript{S}\};\fancyscript{F}$ is the power set of $\varOmega ; \fancyscript{P}(\{w\})=p_s$ with $s \in \fancyscript{S}$. Second, $\{{\fancyscript{F}}_t\}_{t \in {\fancyscript{T}}}$ is the filtration induced by ${\xi }$ with $\fancyscript{F}_t\subseteq \fancyscript{F}$ as the $\sigma$-algebra generated by $\xi ^t$. At the beginning of every service loop, the most recent bunker price changes are known. This means $\xi _1$ is deterministic and $\fancyscript{F}_1=\{\emptyset , \varOmega \}$. For the future bunker price changes, we only know the discrete probability distribution. Bunkering and speed decisions at any stage do not depend on future realization of bunker price changes, but on the probability specification $(\varOmega , \fancyscript{F},\fancyscript{P})$. This is a non-anticipative constraint commonly used in many multi-stage stochastic optimization problems. When it comes to the end of the studying horizon, all the random information is realized and $\fancyscript{F}_t=\fancyscript{F}$. A series of realizations $(\xi ^\mathrm{s}_1,\ldots ,\xi ^\mathrm{s}_T)$ over the entire study horizon consist of a scenario. All the scenarios are combined into a scenario tree representation. Figure 2 above shows an example of a scenario tree.

Fig. 2

A simple example of scenario tree

3.1 Assumptions

Now, we summarize all the assumptions made in our paper:

• 1. We consider one ship in one service route with time windows. Port time (time one ship spends on entering, unloading and loading cargo, idling and exiting) at each port is deterministic and known.

• 2. Bunkering and ship speed decisions are made when ship reaches one port.

• 3. Relationship between the ship speed and the bunker consumption is established in Sect. 2.2.

• 4. Bunker prices at different ports are not necessarily the same. In addition, bunker price changes follow a discrete-time Markovian process.

• 5. Bunkering cost includes the fixed cost which is constant over time by assumption and the variable cost. Bunker inventory cost pmt is assumed to be constant and independent of bunker prices. Bunker left at the end of one service loop is refunded.

3.2 Notations

Following notations are used to express our dynamic stochastic problem:

Parameters

$S$ :

total number of price scenarios;

$\varPi ^s$ :

the probability that price scenario $s$ happens;

$n$ :

number of port of calls;

$d_{i,j}$ :

distance between port $i$ and port $j$ (nautical miles);

$t$ :

total cycle time (h);

$t_i$ :

port time (time one ship spends on entering, unloading and loading cargo, idling and exiting) at port $i$ (h);

$e_i$ :

earliest arrival time at port $i$;

$l_i$ :

latest arrival time at port $i$;

$C_i$ :

bunker fuel consumption when the ship is at port $i$;

$w$ :

bunker fuel capacity for a single ship;

$v_\mathrm{min}$ :

minimum ship sailing speed (nautical miles/h);

$v_\mathrm{max}$ :

maximum ship sailing speed (nautical miles/h);

$P^s_i$ :

bunker price for port $i$ under scenario $s$;

$f$ :

fixed bunkering cost;

$\gamma$ :

coefficient to control the service level;

$h$ :

inventory holding cost pmt for bunker;

$\eta$ :

coefficient of variation for daily bunker consumption rate

Decision variables

$V^s_{i,j}$ :

ship speed between port $i$ and $j$ under scenario $s$;

$R^s_i$ :

bunker fuel-up-to level for the ship at port $i$ under scenario $s$;

$B^s_i$ :

bunkering decision variable. =1 if bunkering at port $i$ under scenario $s$; =0, otherwise;

Dependent variables

$I^{s}_i$ :

bunker fuel inventory when the ship reaches port $i$ under price scenario $s$;

$\overline{F}^s_{i,j}$ :

mean of daily bunker consumption rate for a ship travels from port $i$ to $j$ under price scenario $s$;

$\delta ^s_{i,i+1}$ :

standard deviation of bunker fuel consumption between port $i$ and $i+1$ under price scenario $s$;

$D^s_i$ :

Standard deviation of ship bunker inventory when ship reaches port $i$ under price scenario $s$;

$A^s_i$ :

ship arrival time at port $i$ under scenario $s$;

 

3.3 Mathematical model

The major difference between our model and the one in Yao et al. (2012) is that ours can provide dynamic decision making. We included two uncertainties, which render our model more realistic, but make the solving extremely difficult. We will discuss the solving issues in the next section. There are some other minor modeling differences. For example, as our focus is on the operational level, we study the optimization problem for a finite horizon, while the model in Yao et al. (2012) is an infinite horizon problem. Compared with their model, we also add one variable which is the fixed bunkering cost and delete the maximum bunkering times constraint in their model. We believe that in this way our model better conforms to the reality.

We present a mathematical model to describe our problem.

$$\begin{aligned}&\min \sum _{s=1}^S\varPi ^s\cdot \left(\sum _{i=1}^n [(R^s_i-I^s_i)P^s_i+f\cdot B^s_i+(R^s_i-C^s_i)\cdot h] -I^s_{n+1}\cdot P^{s}_{n+1}\right)\quad \nonumber \\&I^{s}_{1}=0,\quad D^{s}_{1}=0\qquad \forall s \in S\end{aligned}$$

(1)

$$\begin{aligned}&I^{s}_{i}\!=\!R^{s}_{i-1}\!-\!C^s_{i-1}-{\overline{F}}^s_{i-1,i} \cdot d_{i-1,i}/24 \cdot V^s_{i-1,i}\quad \forall s\in S,\ i\in 2,3,\ldots ,n+1\end{aligned}$$

(2)

$$\begin{aligned}&R^{s}_{i}-I^{s}_{i} \le B^s_i \cdot w \quad \forall s \in S,\ i \in 1,2,\ldots ,n\end{aligned}$$

(3)

$$\begin{aligned}&R^{s}_{i} \le w \quad \forall s \in S,\ i \in 1,2,\ldots ,n \end{aligned}$$

(4)

$$\begin{aligned}&\delta ^s_{i-1,i}+(1-B^s_{i-1})\cdot D^s_{i-1}=D^s_i \quad \forall s \in S,\ i \in 2,3,\ldots ,n+1\end{aligned}$$

(5)

$$\begin{aligned}&{\overline{F}}^s_{i,i+1}=k_1(V^s_{i,i+1})^3+k_2 \quad \forall s \in S,\ i \in 1,2,\ldots ,n\end{aligned}$$

(6)

$$\begin{aligned}&\delta ^s_{i-1,i}=\eta \times {\overline{F}}^s_{i-1,i} \cdot d_{i-1,i}/24 \cdot V^s_{i-1,i}\quad \forall s \in S,\ i \in 2,3,\ldots ,n+1\end{aligned}$$

(7)

$$\begin{aligned}&I^s_i \ge \gamma \times D^s_i\quad \forall s \in S,\ i \in 2,3,\ldots ,n+1\end{aligned}$$

(8)

$$\begin{aligned}&v_\mathrm{min}\le V^s_{i,i+1} \le v_\mathrm{max}\quad \forall s \in S,\ i \in 1,2,\ldots ,n\end{aligned}$$

(9)

$$\begin{aligned}&A^s_i+t_i +d_{i,i+1}/V^s_{i,i+1}=A^s_{i+1}\quad \forall \in S,\ i \in 1,2,\ldots ,n\end{aligned}$$

(10)

$$\begin{aligned}&e_i \le A^s_i \le l_i \quad \forall s \in S,\ i \in 1,2,\ldots ,n\end{aligned}$$

(11)

$$\begin{aligned}&A^s_{n+1}=t \quad \forall s \in S\end{aligned}$$

(12)

$$\begin{aligned}&B^s_{i}=0 \text{ or} 1\quad \forall s \in S,\ i \in 1,2,\ldots ,n \end{aligned}$$

(13)

$$\begin{aligned}&V^s_{i,i+1}=V^{s\prime }_{i,i+1}\quad \forall (s, s^{\prime })\in S~\text{ identical} \text{ past} \text{ to} i \in 1,2,\ldots ,n\end{aligned}$$

(14)

$$\begin{aligned}&R^s_{i}=R^{s\prime }_{i}\quad \forall (s, s^{\prime }) \in S \text{ identical} \text{ past} \text{ to} i \in 1,2,\ldots ,n\end{aligned}$$

(15)

$$\begin{aligned}&B^s_{i}=B^{s\prime }_{i}\quad \forall (s, s^{\prime }) \in S \text{ identical} \text{ past} \text{ to} i \in 1,2,\ldots ,n\end{aligned}$$

(16)

$$\begin{aligned}&F_{n,n+1}=F_{n,1},\ d_{n,n+1}=d_{n,1},\ V^s_{n,n+1}=V^s_{n,1}\quad \forall s \in S \end{aligned}$$

(17)

The objective function is to minimize the expected total cost, which includes the fixed and variable bunkering cost and inventory holding cost. Bunker inventory left at the end of one service loop or beginning of a new loop is dealt as if we can sell it in the market at the prices of that time being. Constraint (1) sets the initial ship bunker inventory and standard deviation of it at zero. Constraint (2) is a flow conservation constraint. Constraint (3) and (4) ensure that the maximum bunkering amount and bunker-up-to level is less than the fuel tank capacity. Constraint (5) states that if the ship is bunkered at the previous port, then standard deviation of the ship bunker inventory at current port is equal to the standard deviation of bunker consumption from previous port to the current port. Otherwise, the standard deviation of ship bunker inventory at previous port should also be added. This is because, as discussed, standard deviation of bunker consumption is proportional to the total bunker consumption. Constraint (6) and (7) express the mean daily consumption rate at a certain speed and stand deviation of bunker consumption between ports $i$ and $i+1$. Constraint (8) is the deterministic equivalent for chance constraint $P\{I^s_i\ge D^s_i\}\ge \gamma ^*$, which ensures that the probability of bunker inventory being greater than a certain amount is greater than a pre-specified value. Constraint (9) is simply to limit the ship speed within a reasonable range, while Constraints (10)–(12) are about time window constraints. Constraint (13) is a binary constraint. Constraints (14)–(16) are non-anticipative constraints which ensure that scenarios that share the same history up to port $i$ should take the same action.

4 Solution method

There are two potential challenges in solving our problem. The first one is the non-linearity constraints related to the ship speed. We deal with this by following the method used in Yao et al. (2012), which applied a piece wise linear function to approximate the non-linear terms.

Another challenge is that when a scenario tree procedure is used to model the stochastic parameters in a multi-stage stochastic problem, solving the problem is usually difficult because of the large problem size. For example, in a case where there are 15 ports and for each period (ship reaches a new port) there are four price scenarios, the total number of scenarios in a scenario tree construction would be $4^{16}$ (because the ship needs to sail back to the first port after visiting all other ports).

Mulvey et al. (1997) reviewed several different solution algorithms for multi-period stochastic problem with discrete-time decisions. Their focus was on medium size of problems: problems with 1,000–3,000 scenarios and nonlinear objective functions. Direct solvers like OBI, MINOS, GRG, CPLEX, LOQO, etc., and decomposition algorithms like L-shaped proposal, progressive hedging algorithm and diagonal quadratic approximation were mentioned. Another possible way is to look at how to trim down the tree size. Growe-Kuska et al. (2003) proposed scenario reduction algorithms which select a subset of the initial scenarios and assign new probability to the remaining ones. Also the tree construction algorithms help to reduce the number of nodes through modifying the tree structure and bundling similar scenarios. Other interesting works in scenario reduction are Dupačová et al. (2003), Heitsch and Römisch (2003) and Heitsch and Römisch (2009). As scenario reduction approach is both theoretically and practically appealing, we implement it in our problem and compare it with our solving approach. For a detailed discussion, please refer to our “Appendix 2”.

In this work, however, because the problem size could be extremely large when the number of ports involved becomes large, all those direct solvers are not able to solve the problem. Also considering our problem nature, instead of trying decomposition algorithms or scenario reduction algorithms, we propose to use a slightly different method of generating scenario tree and combine it with a modified rolling horizon approach to solve a liner shipping operational level problem. The rationale behind this combination is first, bunker price forecasting which covers a long period of time, if not impossible, suffers greatly in terms of forecasting quality. Instead of making one-time forecast only at the very beginning for the whole horizon, constantly updating the forecast and resolving the optimization problem are beneficial; second, this successfully circumvents the trouble of solving a large-scale stochastic optimization problem.

4.1 A modified rolling horizon solving scheme

The essence of the standard rolling horizon planning scheme is that a problem with the study horizon shorter than the original one (to reduce the problem size) is solved and the first period decision is implemented. With newly available information, the problem is updated and resolved. Still the decision is only acted on for the imminent period. This process goes on and on until the end of the study horizon. For example, Baker (1977) implemented the standard rolling horizon approach in a production planning problem and numerical results in his work showed that rolling horizon approach produced results that were well within 10 % of optimality and if the model construction was well tailored for specific circumstance, the optimality gap could be further reduced within 1 %. In addition, he mentioned two key reasons (“uncertain information about the future” and “limited information about the future”) that legitimized the use of finite-horizon model for the purpose of decision making in infinite-horizon system.

In our case, we will use a non-standard rolling horizon approach. Unlike the standard one which solves a problem with a shorter horizon than the original problem, our non-standard approach still solves the problem with the whole study horizon. However, we assign a higher level of fidelity for the nearer periods than the later ones by modifying the way we generate the scenario tree. For the first few number of periods (could be 1, 2 or any number of periods depending on the problem), all the price change alternatives are generated as shown in Fig. 2, while a relatively small number of realizations (also problem specific) are randomly generated for all the remaining periods till the end. Therefore, an example of our modified version of scenario tree would look like Fig. 3, in which scenarios for periods after $i+2$ are randomly generated for each parent node. The validity of this non-standard variant is due to our problem nature and the diminishing tail-end effect. We will further show the suitability of using this non-standard solving horizon approach through our first numerical example.

Fig. 3

Scenario tree with randomly generated siblings

The modified rolling horizon solving procedure tailored for our problem is given below:

• 1. When the ship reaches the port $i (i=1,2\ldots , n)$, generate the price scenario tree which looks ahead $n^i_1$ periods and randomly generate $n^i_2$ scenarios for all the remaining periods and each parent node. The choices of $n^i_1$ and $n^i_2$ are problem specific.

• 2. Solve the dynamic optimization problem and get the optimal bunkering and speed decisions for the ship at port $i$.

• 3. When the ship reaches the port $i+1$, generate the price scenario tree again based on newly available information.

• 4. Repeat steps 2 and 3 until the ship reaches the destination port.

5 Case study

Here, we implement our model in two real-world service routes, Malaysia Service (MAS) and Asia-Europe Express (AEX), offered by a real liner. The MAS route consists of three port-of-calls; therefore, direct solving of the whole dynamic problem is possible and we will use this example to illustrate the effectiveness of our modified rolling horizon solving approach by testing its optimality gap. AEX route has 15 port-of-calls. We use the modified rolling horizon approach to solve it and compare the results provided by the stationary model in Yao et al. (2012).

However, we have modified their model to make a fair comparison. The main modification is about the ending bunker inventory. In their stationary model, because it is an infinite horizon problem, bunker inventory at the end of one service loop is the starting inventory of the next loop. However, in our comparison, we only consider one service loop; thus the ending bunker inventory in the stationary model will be refunded as in our dynamic model. Also, we have removed the maximum bunkering times constrain in the stationary model and redesigned the bunker cost to include fixed bunkering cost instead. Modified version of the stationary model will be presented in the “Appendix 1”.

We run all our numerical studies with CPLEX-11.2 on a 3 GHz Dual Core PC with 4 GB of RAM. Stationary model in Yao et al. (2012) can be solved by CPLEX in seconds.

5.1 Parameter setting for bunker price changes

Our model has no problem accommodating the case where every port has a different parameter setting for their bunker price scenario trees; in our numerical study here, for ease of illustration, we assume that the bunker price percentage changes for all the ports at each period will be the same .

One of the most commonly used methods in generating scenarios for continuous distribution function is the Discretization technique. For a general introduction and application of this method, please refer to Kotsiantis and Kanellopoulos (2006) and Dougherty et al. (1995). For example, based on the bunker prices in Singapore from August 7, 2002 to September 3, 2009, we discretize the weekly bunker price changes into four intervals with equal probability and Table 2 below lists the mean values of each interval. Since we model the evolution of bunker prices as an one-stage Markovian process, we also derive the conditional transition matrix among those intervals in Table 3. However, problems associated with the Discretization method in deriving bunker price percentage change scenarios based on historical data are that periods of highly volatile prices would be evened out by mild ones and it assumes that history will repeat. Our numerical experiments show that under this setting of bunker price percentage changes, dynamic model only has marginal benefits than the stationary model. Considering our work is more relevant in times when bunker prices are highly fluctuating (September 2008, for example, IFO380 averaged slightly over ${\$}$600 pmt in Singapore, however, it dropped to average ${\$}$410 in October), we construct three cases of weekly bunker price percentage changes as shown in Tables 4, 5, 6, 7, 8 and 9, which are more volatile.

Table 2 Weekly bunker price change alternatives: historical case

Table 3 Transition matrix of the weekly bunker price changes: historical case

Table 4 Weekly bunker price change alternatives: Case 1

Table 5 Transition matrix of the weekly bunker price changes: Case 1

Table 6 Weekly bunker price change alternatives: Case 2

Table 7 Transition matrix of the weekly bunker price changes: Case 2

Table 8 Weekly bunker price change alternatives: Case 3

Table 9 Transition matrix of the weekly bunker price changes: Case 3

5.2 MAS service route

5.2.1 Parameter setting

Parameters for the MAS route is provided in Table 10:

Table 10 Parameters for MAS service

5.2.2 Numerical results

With 3 ports, there are altogether 256 scenarios, so we can solve the whole dynamic problem with CPLEX. One scenario means a series of price percentage change realizations from the start till the end of the route. For example, if bunker prices increase $\theta _i~\%$ ($i=1,2,3$) when the ship reaches port $i$ ($\theta _i$ can be less than 0 which means it is actually a decrease of prices), and in the end when the ship sails back to port 1, bunker prices increase by another $\theta _0~\%$. Hence, we denote this scenario as $[\theta _1~\%,\theta _2~\%, \theta _3~\%, \theta _0~\%]$.

We obtain the speed and refueling decisions given by the stationary model, direct solving of the dynamic model and dynamic model solved by the modified rolling horizon approach, respectively, under all three cases of bunker price percentage changes. Comparison of the results from direct solving of the dynamic model and dynamic model solved by the modified rolling horizon approach is to test the effectiveness of the modified rolling horizon approach. For the modified rolling horizon approach, we look ahead one period for which we generate all four possible alternatives and for the remaining three periods (it is not two because, as mentioned, the ship needs to sail back to the first port), three bunker price change realizations are generated for each parent node. All those three bunker price change realizations belong to the same parent node should share the same decision. For the modified rolling horizon approach, it is based on which specific scenario happens to solve the problem. All 256 scenarios will be solved by our modified rolling horizon approach.

Under Case 1 of the bunker price changes setting, the optimal expected average cost of those 256 scenarios solved by the stationary model is ${\$}$123,637, the optimal expected average cost solved by the direct solving of the dynamic model is ${\$}$117,194 and the optimal expected average cost solved by the modified rolling horizon approach is ${\$}$118,779. The failure rate in these three models is controlled at the same level by setting the service level coefficients. We see that the optimality gap between the rolling horizon approach and the direct dynamic solving is only about 1.3 %. In terms of performance, direct solving of dynamic model is better than the dynamic model solved by the modified rolling horizon approach, which is better than the stationary approach. The cost saving of using the modified rolling horizon approach compared with the stationary model is 3.9 %.

Under Case 2 of the bunker price changes setting, the optimal expected average cost of those 256 scenarios solved by the stationary model is ${\$}$122,739, the optimal expected average cost solved by the direct solving of the dynamic model is ${\$}$113,422 and the optimal expected average cost solved by the modified rolling horizon approach is ${\$}$116,637. The failure rate in these three models is controlled at the same level by setting the service level coefficients. The optimality gap between the modified rolling horizon approach and the direct dynamic solving is only about 2.8 %. The cost saving of using the modified rolling horizon approach compared with the stationary model is 5.0 %.

Under Case 3 of the bunker price changes setting, the optimal expected average cost of those 256 scenarios solved by the stationary model is ${\$}$118,878, the optimal expected average cost solved by the direct solving of the dynamic model is ${\$}$95,580, and the optimal expected average cost solved by the modified rolling horizon approach is ${\$}$100,502. The failure rate in these three models is controlled at the same level by setting the service level coefficients. The optimality gap between the modified rolling horizon approach and the direct dynamic solving is only about 4.9 %. The cost saving of using the modified rolling horizon approach compared with the stationary model is 15.5 %.

Tables 11 and 12 summarize the results so far for three different solving methods under three different cases of bunker price percentage changes. $R$ denotes the modified rolling horizon solving approach, $D$ denotes the direct dynamic solving approach and $S$ denotes the solving of stationary model.

Table 11 Comparison between the modified rolling horizon approach and direct dynamic solving approach

Table 12 Comparison between the modified rolling horizon approach and the solving of stationary model

The above results show that the modified rolling horizon approach performs quite well compared with the direct solving of the dynamic model, though the optimality gap tends to be bigger when bunker prices become more volatile. Also, as price fluctuations increase, the cost saving of using the dynamic model, either solved directly or by the modified rolling horizon approach, increases as well.

Next we look into details of the optimal speed and refueling decisions given by the modified rolling horizon approach and the direct solving of the dynamic model. We take Case 3 setting of the bunker price percentage changes for example. Table 13 lists numerical results from both solving approaches under some illustrative scenarios. For some scenarios, our experiments show that the dynamic approach and the modified rolling horizon approach give the same or similar optimal solutions, scenarios 1–3 in Table 13, for example. We also find that, for both approaches, if there is a bunker prices increase when the ship reaches the port 2, it will bunker more. The bigger the increase, the more it bunkers. We can see this from the comparison between scenario 1 with scenario 2 for example. There is a 10 % prices increase in stage 2 at scenario 2 and $-20~\%$ decrease in scenario 1. Bunkering amount of the modified rolling horizon approach at port 2 in scenario 2 is 46.27 and it is 39.39 in scenario 1. Bunkering amount of the direct solving approach at port 2 in scenario 2 is 40.98 and it is 39.36 in scenario 1. Comparison between scenario 3 with scenario 4 shows the same conclusion. This is because there are altogether only three ports in one service loop. Port 2 is relatively more significant in the overall planning for the whole loop. When it spots a increase of bunker prices, it tends to bunker more in port 2.

Table 13 Comparison of the direct solving of dynamic model and the modified rolling horizon approach

One more finding is that when scenarios $[10~\%,20~\%,x~\%,x~\%],[20~\%,10~\%,x~\%,$ $x~\%]$ or $[20~\%,20~\%,x~\%,x~\%]$ ($x$ denotes either $-20,-20,10$ or $20$) happen, the modified rolling horizon approach will bunker up to the maximum capacity at port 2 while the direct solving approach never does this. This means the modified rolling horizon approach tends to be myopic compared with the direct solving approach because if in later stages, bunker prices actually decrease, then the modified rolling horizon approach results in much higher cost than the direct solving, as shown in scenario 5. However, if in later stages, bunker prices actually increase, as shown in scenario 6, the modified rolling horizon approach will outperform the direct solving approach (when all scenarios are considered, and on the expected average sense, the direct dynamic solving will still be better). In this sense, we can also say that direct solving approach is conservative compared with the modified rolling horizon approach.

Overall, we can say that the modified rolling horizon approach provides a quite good solving scheme for our dynamic programming problem. With this example in mind, we could have the confidence to implement our rolling horizon approach in a larger problem where direct solving of the dynamic model is practically impossible due to the computer memory restraint or extremely long solving time. Another example we are going to show belongs to this category.

5.3 AEX service route

AEX service route consists of 15 ports which means there are altogether $4^{16}$ scenarios and the parameter setting is given below. It is the same with that in Yao et al. (2012) for the purpose of fair comparison. In this example, we are going to solve the problem using the modified rolling horizon approach and then compare the results with the stationary model. Besides the three cases of bunker price percentage changes just given, we want to see another special case 0 of bunker prices uncertainty as represented by Tables 14 and 15. We set all four bunker price percentage changes to be 0. The purpose is to test the benefit of introducing bunker consumption uncertainty by controlling the bunker prices to be constant. In addition, we will study the effect of ship size difference on the overall operational decisions.

Table 14 Weekly bunker price change alternatives: Case 4

Table 15 Transition matrix of the weekly bunker price changes: Case 4

5.3.1 Parameter setting

Parameters for the AEX route are provided below in Table 16:

Table 16 Parameters for AEX service

5.3.2 Comparison between the dynamic model solved by the modified rolling horizon approach and the stationary model

Failure rate in both models is controlled to be 0.01. In the modified rolling horizon method of this example, we look ahead 3 periods for which we fully generate all the alternatives and for the remaining 13 periods, 8 price realizations are generated. In our comparison, 40 price scenarios have been generated.

Under Case 1 of the bunker price changes setting, average cost for the dynamic model solved by the modified rolling horizon approach is ${\$}3.66\times 10^6$ and average cost for the stationary model is ${\$}3.84\times 10^6$ which is about 4.9 % of cost saving. Under Case 2 of the bunker price changes setting, average cost for the dynamic model solved by the modified rolling horizon approach is ${\$}3.79\times 10^6$ and average cost for the stationary model is ${\$}4.07\times 10^6$ which is about 7.4 % of cost saving. Under Case 3 of the bunker price changes setting, average cost for the dynamic model solved by the modified rolling horizon approach is ${\$}3.82\times 10^6$ and average cost for the stationary model is ${\$}4.30\times 10^6$ which is about 12.6 % of cost saving.

From Case 1 to Case 3, as the bunker prices become more volatile, the cost saving of the dynamic model solved by modified rolling horizon approach compared with the stationary model increases from 4.9 to 12.6 %. Considering the huge amount of operational costs for a liner shipping company, this means a significant total cost reduction. Also this result does not surprise us because dynamic model should become more superior to stationary model when prices are more fluctuating.

Under Case 0 of the bunker price changes setting, the cost saving is 4.6 %. This is the cost saving by introducing bunker consumption uncertainty solely. Therefore, we can see, under Case 1 of bunker price changes setting, the benefit of introducing stochastic bunker prices is only about 0.3 %. However, under Cases 2 and 3, this increases to $(7.4-4.6)=2.8~\%$ and $(12.6-4.6)=8.0~\%$. This finding conforms with our intuition that the more volatile the bunker prices, the more benefits of considering the stochastic bunker prices.

Table 17 summarizes the results so far for AEX service example.

Table 17 Comparison between the modified rolling horizon approach and the solving of stationary model

Bunker inventory holding cost per ton in our problem is assumed to be constant and independent of the bunker prices. Thus we want to see how sensitive the result is to this parameter. In this AEX route example, bunker prices of all the ports at the initial stage are set around ${\$}$460 pmt with minimum ${\$}$456 and maximum ${\$}$471. Our previous results are based on bunker inventory holding cost being ${\$}$50 pmt. In our subsequent analysis, we want to see what will happen if we vary this parameter.

Take Case 1 of the bunker price changes setting for example, our numerical results show that when bunker inventory cost is ${\$}$100 pmt, dynamic model solved by the modified rolling horizon approach has 8.56 % of cost saving to the stationary model, compared with 4.9 % if bunker inventory cost is ${\$}$50 pmt. When inventory cost is ${\$}$150 pmt, this cost saving increases to 13.4 %. Or if we set inventory cost to be ${\$}$25 pmt, the cost saving is 3.48 %. This means generally when bunker inventory cost pmt increases, the dynamic model becomes even more superior to the stationary approach.

In addition, we can expect that the benefit of introducing bunker consumption uncertainty (Case 0 of the bunker price changes setting) increases with bunker inventory holding cost. If we set the bunker inventory holding cost to be ${\$}$25 pmt, the cost saving is 2.56 %. If it is ${\$}$100 pmt, the cost saving is 8.53 %, and if it is ${\$}$150 pmt, the cost saving increases to 11.2 %.

Therefore, the benefits of introducing these two uncertainties increase with the volatility of the bunker prices and the bunker inventory holding cost.

5.3.3 Effect of the ship size difference on the overall operational planning

In the end, we want to discuss the effect of using a different size of ship. For instance, what if the 3,000 TEU ship is used here in this AEX route. All other parameters for the AEX service route remain the same, except for these related to the ship size. Based on the bunker price scenarios generated in previous analysis under Case 1 setting of the percentage changes, and under ${\$}$50 pmt of the bunker inventory holding cost, the average cost for the dynamic model solved by the modified rolling horizon approach is ${\$}2.65\times 10^6$ and the average cost for the stationary model is ${\$}2.82\times 10^6$ which is about 6.0 % of cost saving (4.9 % for a 5,000-TEU ship). The average costs are lower compared with the case when a 5,000-TEU ship is used, because we can see from the bunker consumption rates in Tables 10 and 16 that smaller ships burn less bunker sailing under the same speed and distance. Also the dynamic model performs even better than the stationary model when one smaller ship is used. This is largely due to the fact that smaller ships have a higher coefficient of variation of the bunker consumption rate. However, we notice that the average cost (dynamic model solved by the modified rolling horizon approach) per TEU for the 3,000-TEU ship is $8.84 \times 10^2$ and that for the 5,000-TEU ship is $7.32 \times 10^2$. This means, cost per TEU wise, bigger ships are more efficient.

Next, we want to see the effect of ship size difference on the bunkering and refueling decisions. In the stationary model, we find that the bunkering ports selection and bunkering amount will be different. However, speed choice is the same because there are no bunker prices and consumption uncertainties. In the dynamic model solved by the modified rolling horizon approach, both bunkering and speed decisions can differ when different sizes of ships are deployed. For example, under scenario $[5~\%,10~\%,10~\%,-5~\%,-10~\%,10~\%,5~\%,5~\%,5~\%,10~\%,10~\%,-5~\%,$ $-5~\%,-5~\%,-5~\%,-10~\%]$ (randomly selected one), the modified rolling horizon approach suggests to bunker at port 12 when a 5,000-TEU ship is used, and not to bunker there if it is a 3,000-TEU ship. Bunkering amount at every port are significantly different too. As for the ship speed, Fig. 4 shows that during some legs, different sailing speeds are suggested for these two sizes of ships, although the difference is not very significant. However, under some scenarios, the difference can be larger as shown in Fig. 5 under scenario $[-5~\%,-5~\%,-5~\%,-5~\%,-5~\%,-5~\%,-10~\%,-5~\%,-10~\%,$ $-5~\%,-5~\%,-5~\%,-5~\%,-5~\%,-5~\%,-5~\%]$.

Fig. 4

Optimal speed decisions given by the modified rolling horizon approach 1

Fig. 5

Optimal speed decisions given by the modified rolling horizon approach 2

To conclude, we think ship size differences impose significant effect on the overall operational planning for the liner shipping companies.

6 Conclusion and future research

In this work, we study the problem of dynamic bunkering port selection and ship speed determination for a single vessel in one service route. While previous deterministic works focus more on the planning level of this problem, we aim at providing operational decision support by incorporating two major random factors into our model. Namely, the ship bunker consumption rate and the bunker prices at each port. Based on the bunker consumption model in Yao et al. (2012), we further established that the noise of daily bunker consumption follows a normal distribution with zero mean and constant coefficient of variation. For the stochastic nature of the bunker prices, we have modeled it through the scenario tree which is widely used in financial engineering area to depict the randomness of the financial product returns. While solving a whole large dynamic problem is computational challenging, we proposed a solving method that could help to significantly reduce the computer memory requirement and solving time. This method is a combination of scenario tree generation scheme and a non-standard rolling horizon approach. Another advantage about this solving method is that as much new information as possible is used and previous forecasting errors could be easily corrected during the whole study horizon. Our numerical examples based on real-world data have shown that the dynamic model improves significantly in terms of overall cost and service level (or failure rate) compared with the stationary model. With the reasonable solving time, we think our model could be implemented by liner shipping companies to give operational level decision support to lower the overall operation cost and provide more reliable service.

Some possible future research directions are first, we have noticed that though the number of scenarios would be very huge with just a few number of ports, many of them share the same optimal decision. This is a phenomenon determined by our problem nature. In our problem, time window determines the ship speed range during each leg, which determines the bunker consumption. In the end, how much bunker consumed determines how much needs to be bunkered. Also, a change of optimal decision in our problem usually means a change of bunkering ports. However, a change of bunkering ports would not happen unless bunker prices at one port become significantly attractive considering the bunker inventory holding cost. Therefore, the optimal decision is not very sensitive to the bunker price changes and we could look for ways to group those scenarios which give the same, or close, optimal solution. Second, in our current work, there is no policy. The bunkering decision and speed selection could always change along with external factors. As a future research, we want to propose a $(s, S)$ policy like that in the inventory management problem. When the ship bunker inventory drops below $s$, we bunker fuel up to the level of $S$. Careful readers will find our problem has a lot of similarities with inventory management problem. Bunker inventory is equivalent to product inventory, and bunker consumption is equivalent to product demand, running out of fuel before finishing a voyage leg is equivalent to an inventory being out of stock. Also, for the bunker fuel consumption, instead of using chance constraints, we could also use the sample average approximation method to model the uncertainty of bunker consumption. Last but not least, soft time windows associated with penalty cost and inventory holding cost depending on bunker price could be introduced into our model to render it more realistic.

Appendices

Appendix 1: Modified version of the stationary model

1.1 Notations

Following notations are used to express model 1:

Parameters

$n$ :

number of port of calls;

$d_{i,j}$ :

distance between port $i$ and port $j$ (nautical miles);

Parameters

$t$ :

total cycle time (h);

$t_i$ :

port time (time one ship spends on entering, unloading and loading cargo, idling and exiting) at port $i$ (h);

$e_i$ :

earliest arrival time at port $i$;

$l_i$ :

latest arrival time at port $i$;

$C_i$ :

bunker fuel consumption when the ship is at port i;

$w$ :

bunker fuel capacity for a single ship;

$v_\mathrm{min}$ :

minimum ship sailing speed (nautical miles/h);

$v_\mathrm{max}$ :

maximum ship sailing speed (nautical miles/h);

$k_1,k_2$ :

bunker fuel consumption coefficients;

$P_i$ :

bunker price for port $i$;

$f$ :

fixed bunkering cost;

$h$ :

inventory holding cost pmt for bunker;

$\gamma$ :

coefficient to control the service level;

Decision variables

$V_{i,j}$ :

ship speed between port $i$ and $j$;

$S_i$ :

bunker fuel-up-to level for the ship at port $i$;

$B_i$ :

bunkering decision variable. $=1$ if bunkering at port $i;\ =0$, otherwise;

Dependent variables

$I_i$ :

bunker fuel inventory when the ship reaches port $i$;

Dependent variables

$F_{i,j}$ :

daily bunker consumption rate for a ship travels from port $i$ to $j$;

$A_i$ :

ship arrival time at port $i$;

 

1.2 Model

 

$$\begin{aligned}&\min \sum _{i=1}^n[(S_i-I_i)P_i+f\cdot B_i+(S_i-C_i)\cdot h]-P_1\cdot I_{n+1} \nonumber \\&I_{1}=0; \end{aligned}$$

(18)

$$\begin{aligned}&I_{i}=R_{i-1}-a_{i-1}-F_{i-1,i}\cdot d_{i-1,i}/24 \cdot V_{i-1,i} \quad i \in 2,3,\ldots ,n+1 \end{aligned}$$

(19)

$$\begin{aligned}&R_{i}-I_{i} \le B_i \cdot w \quad i \in 1,2,\ldots ,n \end{aligned}$$

(20)

$$\begin{aligned}&R_{i} \le w \quad i \in 1,2,\ldots ,n \end{aligned}$$

(21)

$$\begin{aligned}&I_{i} \ge \gamma \cdot w \quad i \in 1,2,\ldots ,n \end{aligned}$$

(22)

$$\begin{aligned}&F_{i,i+1}=k_1(V_{i,i+1})^3+k_2 \quad i \in 1,2,\ldots ,n \end{aligned}$$

(23)

$$\begin{aligned}&v_\mathrm{min}\le V_{i,i+1}\le v_\mathrm{max}\quad i \in 1,2,\ldots ,n \end{aligned}$$

(24)

$$\begin{aligned}&A_i+t_i +d_{i,i+1}/V_{i,i+1}=A_{i+1}\quad i \in 1,2,\ldots ,n \end{aligned}$$

(25)

$$\begin{aligned}&e_i \le A_i \le l_i \quad i \in 1,2,\ldots ,n \end{aligned}$$

(26)

$$\begin{aligned}&A_{n+1}=t \end{aligned}$$

(27)

$$\begin{aligned}&B_{i}=0 \text{ or} 1 \quad i \in 1,2,\ldots ,n \end{aligned}$$

(28)

$$\begin{aligned}&F_{n,n+1}=F_{n,1},\quad d_{n,n+1}=d_{n,1},\quad V_{n,n+1}=V_{n,1} \end{aligned}$$

(29)

The objective function is to minimize the expected total cost, which includes the fixed and variable bunkering cost and inventory holding cost. Bunker left at the end of the service loop is refunded. Constraint (18) sets the initial inventory to be 0. Constraint (19) is a flow conservation constraint. Constraints (20) and (21) ensure that the maximum bunkering amount and bunker-up-to level are less than the bunker fuel capacity. Constraint (22) controls the minimum bunker inventory to be a fixed percentage of the total bunker capacity. Constraint (23) expresses the daily consumption rate at a certain speed between port $i$ and $i+1$. Constraint (24) is simply to limit the ship speed within a reasonable range, while constraint (25) to (27) are about time window constraints. Constraint (28) is a binary constraint.

Appendix 2: Comparison between the scenario reduction approach with the modified rolling horizon approach

We applied the fast forward selection algorithm in [1] to reduce the bunker price scenario tree size in our first case study, MAX service route, and compared the results with that of our modified rolling horizon approach. As mentioned, the size of the MAX service route allows us to solve the whole dynamic model by CPLEX directly, so we can easily derive the optimality gap of the scenario reduction method and our modified rolling horizon approach, respectively.

Table 18 shows the optimality gap of the scenario reduction method under different parameter settings. There are altogether 256 price scenarios initially and we still look at 3 different cases of bunker price fluctuation.“Number of scenarios” means the total number of scenarios retained after reduction and these percentage numbers in the table denote the optimality gap between the scenario reduction method and the direct solving of the dynamic model.

Table 18 Optimality gap of the scenario reduction method

Table 19 shows the optimality gap of our modified rolling horizon approach under three different cases of bunker price percentage change. Table 20 is a comparison of the solving time between these two methods under case 1.

Table 19 Optimality gap of the modified rolling horizon approach

Table 20 Solving time comparison of these two methods

Comparing the results in Tables 18, 19 and 20, we can see that the modified rolling horizon approach is a good approach to be used for our problem. Under all three cases, the modified rolling horizon approach is better than the scenario reduction method when the scenario reduction method retains less than 100 scenarios. Moreover, the solving time for the modified rolling horizon approach remains unchanged while the solving time for the scenario reduction method increases considerably with the number of scenarios. And under all these 3 cases, the optimality gap of our modified rolling horizon approach is under 5%, which is encouraging.

When it comes to our second case study where there are a total of 4$^{16}$ price scenarios, the implementation of the scenario reduction method becomes even harder. As CPLEX can only solve the problem with less than 500 price scenarios, this means only 5 out of 4$^{14}$ scenarios is retained. Not only will the scenario reduction algorithm take a long time to reduce the scenarios, but the optimality gap of the reduced tree might be big based on our study of the small size problem.

In summary, we feel that the scenario reduction technique might not work well in our problem. However, having said so, we still feel that there is a potential in this method to be applied to this type of the problem, but this will need an in-depth research work. As for our proposed method, it can be viewed as a special type of scenario reduction technique in the sense that all the branches in the near future are enumerated, but the branches far away from the decision point are not enumerated fully and so we have a reduction in scenarios. Moreover, by forcing it to solve at every decision point, we are able to obtain decisions using the most updated information.