Introduction

After the economic crisis in 2008, international seaborne trade grew continuously. World seaborne trade increased by 4 per cent in 2012, and even more in 2013. Container port throughput increased year-by-year, and the world fleet grew by 37 per cent in just 4 years since 2008. The world fleet has more than doubled since 2001, reaching 1.63 billion deadweight tons (dwt) in January 2013 (UNCTAD, 2012, 2013).

Freight volume increase presents a challenge to both container ports and shipping companies. A container port needs to run a tight schedule for berthing, and a container vessel has little time for berthing. Some costs for berthing such as port dues, berth hire and anchorage may increase when berthing time increases. These changes require a container vessel to arrive at and depart from a port on time in a cost-effective way.

Among transportation costs, fuel cost is the largest, accounting for about 35 per cent of the total freight rate (UNCTAD, 2012). A vessel traveling at a low speed accrues cost savings because fuel consumption is proportional to the cube of the vessel speed. Moreover, fuel prices fluctuate frequently. A reduction of fuel consumption also helps the environment because all vessels currently use fossil fuels.

Another issue related to vessel operations is vessel bunkering (that is, refueling). A vessel that serves an inter-region route, for example, Asia–Europe, often has to bunker at several ports on its journey. Moreover, fuel prices frequently change and are different at different ports. A shipping company has to decide at which port and how much the vessel will be bunkered.

In this article, we study a speed and bunkering problem of a vessel on a route, with the objective of minimizing fuel costs. The decision variables are the speeds of the vessel on route, the ports for bunkering and the bunkering amount at each port. The rest of the article is organized as follows: the next section reviews related studies in literature, then the problem description is presented in the following section. A numerical performance comparison is presented, and the last section provides our conclusions.

Literature Review

In recent decades, many researchers have studied maritime transportation including vessel routing. Christiansen and Nygreen (1998) studied a ship planning problem. They designed a set of routes for a heterogeneous fleet to minimize costs. Shintani et al (2007) considered a ship routing problem to maximize profit when picking up and delivering container cargoes. The problem was divided into two parts. The lower-problem determined the optimal calling sequence of ports for a specific group of ports. The upper-problem was a Knapsack problem to select the best set of calling ports based on the calling sequence determined in the lower-problem.

Another issue in ship routing is fuel conservation. Ronen (1982) considered a trade-off between fuel conservation through slow steaming and loss of revenue because of voyage extension. Ronen (2011) analyzed a trade-off between speed reduction and adding more vessels to a container line route, and proposed a simple procedure to determine the sailing speed and number of vessels to minimize the annual operating cost of the route. Brown et al (1987) solved a crude oil tanker scheduling problem, which takes into account all fleet cost components, including the opportunity cost of ship time, port and canal use, and fuel bunkering. The model determines optimal speeds of the ships and the best routing of ballast (empty) legs, as well as the cargoes to load on owned ships and on spot charters. Kim (2014) addressed a problem of determining ship speed and bunkering ports in a ship route, through a non-linear programming (NLP) mathematical model. While many papers consider the fuel consumption rate as a non-linear function of vessel speed, for simplification of analysis, Berling and Martinez-de-Albeniz (2011) used a piecewise linear function for the relationship between fuel consumption rate and vessel speed. Fagerholt et al (2010) considered a problem of reducing fuel consumption by optimizing the speed on a route where the time window at a port is considered. They divided the problem into three problems and solved them sequentially. Speed was the primary variable in the first problem, sailing time in the second problem and arrival time at a port in the third problem. Meyer et al (2012) considered the cost saving potential at lower speeds. Yao et al (2012) studied bunker fuel management strategy for bunkering port selection, bunkering amounts and ship speeds for a single liner shipping service.

In the literature on the relationship between vessel speed and fuel conservation, most people assume that vessel speed does not change from one port to the next during a journey, while a vessel may have to sail at different speeds from one port to another because of geographical features such as canal, channel and ocean currents. Also, to consider the non-linear relationship between fuel consumption and vessel speed, that is, fuel consumption is proportional to the cube of vessel speed (v 3) or it follows some non-linear empirical relationship, most people used NLP techniques in their mathematical modeling.

This article considers geographical features of a route and develops a linear mathematical model. The leg from one port to another is divided into several segments with different maximum speed limits based on geographical characteristics. A vessel has to arrive at a port within a pre-determined time window. The non-linear relationship between fuel consumption and vessel speed is substituted by a set of piecewise linear functions in an innovative way. The decision variables of the model include the vessel speed at each segment of a leg, the ports for bunkering and the bunkering amounts to minimize fuel cost while satisfying the time window constraint at each port. Also a heuristic approach to the problem is presented for simpler and quicker planning.

Problem Description and Mathematical Model Formulation

Problem description

We consider a single route served by one vessel. A route includes a set of ports the vessel has to visit. A leg is a part of a route from one port to the next. A leg has one or more segments depending on geographical features, each of which has its own allowed maximum speed. For example, a vessel has to sail slower when it passes a canal, or the ocean currents can affect the vessel speed. Also, some ports can be located in an area with many small islands requiring a vessel to reduce its speed. A vessel maintains a constant speed in each segment. A set of calling ports on the route, the sequence of calling ports, and the distance and maximum allowed speed of each segment are known. For example, on the route LP5 shown in Figure 1, a vessel visits these ports in this order: Gwangyang, Busan, Shanghai, Ningbo, Yantian, Shekou, Singapore, Rotterdam, Hamburg, Southampton, Singapore and Gwangyang. When visiting a port, a vessel loads and unloads containers within the allowed berthing time. Also, a vessel bunkers fuel for its journey. A port has its predetermined earliest and latest allowed arrival time, a time window, for a vessel. The berthing time is decided before the vessel arrives. Fuel prices are typically different at different ports. A vessel’s capacity for fuel storage is known. For safety, when a vessel departs from a port, the fuel carried by the vessel has to be at least 10 per cent more than the minimum amount required for the next leg of its route. To minimize the total cost of fuel bunkering, we determine the speed of a vessel at each segment of a leg, the bunkering ports and also the bunkering volumes.

Figure 1
figure 1

Vessel route Asia–Europe Loop 5 (LP5).

Source: Hyundai Merchant Marine Company – South Korea.

Full size image

Mathematical model

The problem can be formulated as follows. Notations are given first.

Subscript

i, i∈[1, …, P]:

subscripts of ports. Port 1 is the starting port

l, l∈[1, …, n i ]:

subscript of a segment of a leg between two ports in a route; n i is defined below

k, k∈[1, …, K]:

subscript of intervals of piecewise linear function that approximates the actual relation between speed and fuel consumption rate.

Parameter

e i , l i :

earliest and latest arrival time at port i

t i :

berth time at port i

p i :

unit fuel price at port i (USD/ton)

s k :

lower bound of the domain of the k-th piecewise linear function (interval k) used to approximate the fuel consumption (knot)

a k , b k :

slope and y-intercept of piecewise linear function of interval k

m :

fuel capacity of the vessel (ton)

q :

amount of fuel on the vessel at Port 1 (ton)

d i l :

distance of segment l on the leg from port i−1 to port i on the route

u i l :

maximum allowed speed on segment l on the leg from port i−1 to port i on the route

n i :

number of segments on the leg from port i−1 to port i

Decision variable

I i :

fuel level when the vessel arrives at port i (ton)

X i :

bunkering amount at port i (ton)

V i l :

vessel speed on segment l on the leg from port i−1 to port i on the route

A i :

arrival time at port i

Modeling

Let F=g(V) be the fuel consumption rate at speed V. Then g is a non-linear function, and the problem can be formulated as follows:

The objective function is to minimize the total bunkering cost. Constraints (1) and (2) are time flow constraints. The arrival time of the following port is the sum of the arrival time at the previous port, port time there and the time for the vessel to move from the previous port to the current port. Constraint (3) is a time window constraint. Constraint (4) is a non-linear relationship between speed and fuel consumption. Constraint (5) shows the inventory balance of fuel onboard, and constraint (6) presents the initial fuel level. The fuel level at the current port is the level at the previous port plus the purchased amount at that port minus the amount used to sail to the current port. Constraint (7) assures the fuel level does not exceed the capacity of the vessel. Constraint (8) guarantees the safety stock of fuel, which is 10 per cent of the amount of fuel required to move the vessel to its next port of call. Constraint (9) makes sure the vessel sails in the allowed range of speed at each segment.

This formulation is non-linear because of Constraint (4) and Constraints (1), (5) and (8), which have V i l in the denominator.

Solution Procedure

In this article, two solution approaches are proposed for problem (P1). In the first approach, the function F i l=g(V i l) and other non-linear constraints are linearized by a piecewise linear function, and (P1) is converted to a linear model. Here, differently from other linearization of the problem in the literature, these non-linear constraints are replaced by a set of linear constraints instead of a piecewise linear function. The performance of this new approach is compared with that of the existing piecewise linearization approach at the end of this section. In the second approach, a heuristic algorithm is developed for a simple and quick solution. While the heuristic procedure is faster, the linear programming (LP) modeling is flexible enough to consider additional diverse types of constraints not yet considered in the current problem.

Linearization of the fuel consumption rate curve

The function of the relationship between fuel consumption rate and vessel speed is replaced by a piecewise linear function as follows:

To build this function, we divide the practical speed range of a vessel, [v min, v max], into K intervals [v min=s 1, s 2], [s 2, s 3], …, [s K , v max]. In interval [s k , s k+1], a k is the average slope of the linear line, a k =(g(s k+1)−g(s k ))/(s k+1−s k ), and b k is chosen to make the piecewise linear line meet the actual curve at the boundaries of the segments, b k =g(s k )−a k s k . Note that the function g is convex, and so, for any x value under consideration, the piecewise linear function can be replaced by:

As an example, let us consider y=g(x)=0.01x 3+20, x∈[10, 40] (Figure 2). In the second interval, [20, 30], a 2 =(g(30)−g(20))/(30−20)=19, and b 2 =g(20)−19*20=280. If we denote the piecewise linear function in the k-th interval, g k (x), from Figure 2,

Figure 2
figure 2

Linear approximation of fuel consumption rate over vessel speed.

Full size image

With this linearization of the function F, Constraint (4) becomes:

Because we are to minimize total cost, Constraint (11) can be replaced by constraint (12).

For linearization of constraints with V i l in the denominator, we denote Z i l=((1)/(V i l)) and W i l=((F i l)/(V i l)); then we have V i l=((1)/(Z i l)) and F i l=((W i l)/(Z i l)), and now Constraints (1), (5), (8), (9) and (12) becomes as follows:

With this transform, the non-linear mathematical model (P1) can be reformulated as a linear model as follows:

Subject to

Constraints (13), (2a), (2b), (3), (14), (15), (6), (7), (16), and (17).

Compared with the model of Yao et al (2012), this approach brings some benefit. First, the new model (P2) can be solved by general LP software without the help of a built-in linearization function, which may not be available in all LP packages. Second, (P2) can be solved faster as shown in the numerical experiments section. Third, because (P2) is an LP, it allows a sensitivity analysis, which is not available from either the approach of Yao et al (2012) or from general NLP.

Heuristic procedure

Although the above formulation (P1) is flexible and can consider additional types of constraints that are not considered in the above formulation, it needs many additional constrains for linearization of the original formulation. This section proposes a simple heuristic procedure to solve the speed and bunkering problems. The proposed heuristic algorithm is divided in two main steps. In the first step, vessel speed on the segments of each leg is determined so as to satisfy the time window constraint. In the second step, the bunkering ports, as well as the bunkering amounts are determined.

Beam intersection procedure (BIP) to determine a vessel speed on a segment

This procedure determines the speed of a vessel in the segments of legs of its route when a segment possibly has a maximum speed limit and a port has a time window. For ease of discussion, we assume that berth time is 0 without loss of generalization.

Single segment in a leg without speed limit

We first consider when a leg does not have a speed limit. Figure 3 shows on the y-axis the distance to each port from the current port along the route, and time on the x-axis. In the graph, we show all ports of call within a planning time horizon, which may include any early part of a route or multiple complete routes of the vessel. Let Port 1 be the current port. Time 0 is the departure time from Port 1. In the graph, the slope is the speed of a vessel, which we want to determine. Three ports and their time windows are shown in the graph for discussion.

Figure 3
figure 3

Time–distance chart and BIP.

Full size image

As fuel consumption is proportional to the cube of speed, it is better to use the same speed as much as possible, instead of using a lower speed at one time and a higher speed at another one to save fuel costs (see the lemma below). This means that, in the graph, we want to have a straight speed line with the same slope, or close to a straight line, from the beginning to the final destination as much as we can.

Lemma:

  • If travel time on a leg (or any segment in a leg) is fixed, and the relationship between fuel consumption and speed, g(.), is convex, then the vessel travels at a constant speed to minimize its fuel consumption.

Proof: Let the distance between two ports be d and the travel time at a constant speed be t. Let the vessel sail at speeds V 1 and then V 2. Let the durations that the vessel sails with speed V 1 and V 2 be t 1 and t 2, respectively. We prove that:

where t=t 1 +t 2 , V=(d)/(t), and g(.) is convex.

Because g(V) is convex, we have, for all u ∈[0, 1],

Let us define u=t 1/t. Then u is in [0, 1], and 1−u=t 2/t. Then

If we multiply t into all terms, we get the first formula of the proof. The equality holds when V=V 1=V 2. □

To find the best speed lines in Figure 3, we introduce a Beam Intersection Procedure (BIP). Let us consider Window 2 of Port 2 in that figure. We can use any speed between the lines of 2 L and 2 R to arrive at the port within the time window. If we have a choice, we will use the speed corresponding to 2 R, the lowest speed, to reduce fuel consumption. If we consider Window 3 of Port 3, then the feasible beam range is that of 3 L and 3 R. If we consider Windows 2 and 3 together, the speed range that is an intersection of the ranges of Window 2 and Window 3 can be used without changing speed. In the figure, any speed in the range shown by the arrowed arc, the beam range of (3 L, 2 R), can be used.

Now, let us now consider Window 4 of Port 4. There are three possible cases. In the first case, the upper bound of the window is on the left side of the current feasible beam range (CFBR), which is labeled as (3 L, 2 R) in this example. In the second case, the lower bound of the window is on the right side of the CFBR. In the third case, a part of the window is in the CFBR.

The first case is shown by Window 4(1) in Figure 3. Here we notice that the beam range of Window 4(1) has no overlap with the CFBR of (3 L, 2 R) and is on the left side of it. In this case, it is clear that the vessel arrives at Port 3 at its earliest possible time (not at any later time). Also, it travels at a constant speed, the speed of 3 L, to Port 3. From the figure, we know the arrival time of Window 1 is the intersection of line 3 L and Window 2. For the rest of the route, we start this whole procedure again by using the earliest possible arrival time of Window 3 as a new origin.

The second case is shown by Window 4(2) in Figure 3. Here we notice that the beam range of Window 4(2) has no overlap with the CFBR of (3 L, 2 R) and is on the right side of it. In this case, it is clear that the vessel arrives at Port 2 at its latest possible time (not at any earlier time). Also, it travels at a constant speed, the speed of 2 R, to Port 2. For the rest of the route, we start this whole procedure again by using the latest possible arrival time of Window 2 as a new origin.

The third case is illustrated by Window 4(3) in Figure 3. In this case, the new time window, Window 4(3), has an overlapping range with the CFBR. If the lower bound of the time window is on the right side of the left bound of the CFBR, we change the left bound of the existing CFBR. For example, the new left bound of the CFBR is now 4 L. If the lower bound of the time window is on the left side of the left bound of the existing CFBR, we do not change the left bound of the existing CFBR. We perform a similar procedure for the upper bound of the time window. If the upper bound of the time window is on the left side of the right bound of the CFBR, we change the right bound of the CFBR. For example, the new right bound of the CFBR is now 4 R. If the upper bound of the new time window is on the right side of the right bound of the CFBR, we do not change the right bound of the CFBR.

After updating the existing CFBR, we consider the time window of the next port. If its next time window is the last window in the time horizon, we use the latest arrival time of the window to reduce fuel consumption.

Example 1:

  • In Table 1, the first three columns are scheduling raw data. On the basis of these, we make the speed windows of the time windows in the fourth column. (Note that the speed of the left label of the speed window is larger than that of the right label.) In the last column, the CFBR of Port 2 is the same as the first speed window. The CFBR of Port 3 is obtained by comparing the existing CFBR (Port 2) and the current speed window (Port 3). The new left bound is the minimum of the two left bounds, and the new right bound is the maximum of the two right bounds. Similarly, the CFBR of Port 4 is obtained by comparing the existing CFBR (Port 3) and the current speed window (Port 4). The left bound is the minimum of the two, and the right bound is the maximum of the two. We now consider Port 5. Because the left bound of its speed window is smaller than the right bound of the CFBR (Port 4), we stop the iteration. We determine that we use the right bound of the existing CFBR, which is currently 4 R=450, to go to Port 4 from Port 1.

Table 1 Vessel speed scheduling (numerical example)
Full size table
Multiple segments in a leg with speed limits

Some segments on a route can have speed limits for the reasons stated before. Sometimes, the maximum vessel speed can be a limiting factor. This section considers the speed limit of a vessel and the maximum allowed speeds in the segments.

A speed limit of a segment can be shown by a slope of lines in the segment area in a distance–time chart (sloped dashed lines in Figure 4). The maximum speed of a vessel is not shown in the figure. To conserve fuel, if possible, one wants to travel at a constant speed on the route, which may be too high in some segments. In the segments with speed limits, if needed, we will use their maximum allowed speeds.

Figure 4
figure 4

Vessel speed planning when there is a segment with a speed limit.

Full size image

When an arbitrary target arrival time at a port is given, one can think of different ways of arriving at the port at that time. In Figure 4, for illustration, we tentatively assume that a considered speed is higher than the maximum speed of the segment. To arrive at the next port at a given time, T, we can either use a speed, Slope 1, first, travel through the segment at the maximum allowed speed, and use another speed, Slope 3, or we can use a proper speed, Slope 2, go through the segment, and then use the same speed, Slope 2, again. Among these alternatives, we can minimize fuel consumption by using the same speed, Slope 2, outside of the segment. In this section, we find a plan that uses the same or similar slopes throughout the legs and segment as much as possible.

Before we discuss the general concept and procedure of planning, we present a calculation procedure to determine the ‘same speed’ to be used outside of the segments. In Figure 4, the distance and the target time for moving from the current port to the next are D and T, respectively. Let d and t be the length of the segment and time needed to pass through the segment at its allowed maximum speed. Let the maximum allowed speed of the segment and the maximum speed of the vessel be λ and Λ, respectively. We want to find the speed we will use outside of the segment, x. The best speed, x, is obtained this way:

Case (A) If x⩽λ, x=(D)/(T)

Case (B) If λ⩽x⩽Λ, x=(D−d)/(T−t)

In Case (A), the speed to be used in the segment is x. In Case (B), the vessel goes through the segment at its maximum allowed speed, m. Here we do not consider the case where a vessel cannot arrive at the next port in the allotted time window even at its maximum speed.

Example 2:

  • Let D=3000 nm, T=10 days, M=500 nm/day, d=500 nm, m=250 nm/day. Now, we get t=d/m=500/250=2 days. (Case A) When x⩽250, we have x=D/T=3000/10=300 nm/day. (Case B) When 250⩽x⩽500, we get x=(D−d)/(T−t)=(3000−500)/(10−2)=312.5 nm/day. From these two cases, we conclude that we travel at 312.5 nm/day outside of the segment. Inside the segment, we travel at the maximum speed of the segment, 200 nm/day. We spend 2 days in the segment, and 2500/312.5=8 days out of the segment.

When we have multiple segments in the leg under consideration, we divide the range of possible x value (speed) according to their maximum allowed speed, m i for segment i, that is, the ranges can be v min⩽x⩽m [1]; m [1]⩽x⩽m [2]; m [2]⩽x⩽m [3]; …;  m [L+1]⩽x⩽v max, where L is the number of segments with speed limits in the leg under consideration, and m [i] is the i-th smallest value of all speed limits of all segments in the leg.

Using the procedure exemplified in Cases (A) and (B) above, we can determine the speeds of the lower and upper bounds of each time window. Figure 5 shows the speeds of the time windows of Port 2 and Port 3. The 2 R speed is smaller than the speed limits of the segment, Seg 21, so the line is straight. For the other lines, the slopes in the segments are the maximum speed allowed. Outside the segments, each of the lines maintain a constant speed. Once we have the speed windows of the time windows of ports, (2 L, 2 R), (3 L, 3 R) and so on, we can use the procedure explained in the previous section and in Example 1. In Figure 5, the CFBR of Port 2 is (2 L, 2 R). The CFBR of Port 3 is (2 L, 3 R) because the speed of 3 L is larger than that of 2 L on the left side, and the speed of 3 R is larger than that of 2 R on the right side.

Figure 5
figure 5

Time–distance chart with speed limit.

Full size image

Fuel bunkering decision

When berthing, a vessel is given a chance to bunker. Because fuel costs are different at different ports, planning is needed to save on fuel costs. Here we decide whether and how much to bunker at the current port. We can make this decision at each port at the time of visit and this is done independently of how many containers the vessel has to load or unload.

Let SP c be a set of ports that can be reached with the current amount of fuel at the current port before bunkering. Let SP f be a set of ports that can be reached with full bunkers at the current port. SP f is the planning horizon at this decision point (Figure 6).

Figure 6
figure 6

Bunkering decision (P*: fuel price at the current port) (The parts of curves between ports are only for a visual presentation without meaning).

Full size image

Case (A): A port in SP c has a fuel price lower than P*.

In this case, the vessel does not need to bunker at the current port. Go to the port in SP c with the lowest fuel price (Port 3), and bunker there at a price lower than P*.

Case (B): No ports in SP c have fuel prices lower than P*. However, there is a port in SP f with lower fuel price than P*.

In this case, the vessel bunkers at the current port just enough to go to the first port with a lower fuel price than P* (Port 6). Until we get there, the fuel prices are all higher than P*.

Case (C): No ports in SP f have fuel prices lower than P*.

It is certain that the vessel needs bunkering at or before the last port in SP f (Port 7). However, because prices are all higher than P*, the vessel bunkers to its maximum at the current port.

In one case, if the set of SP c is empty, then we tentatively decide to buy just enough fuel to reach Port 2 and start the consideration of Cases A, B and C at the current port.

Numerical Performance Comparison

This section tests the performances of the newly proposed LP modeling approach and the heuristic procedure. These are tested on a PC with 2.8 GHz i7-CPU and 8 GB RAM.

Performance of the new linear modeling approach

We first test the performance of our approach for the LP modeling by comparing our approach with that of Yao et al (2012), who recently considered a similar problem. For fairness of comparison, we linearize the original non-linear formulation (Y1) of Yao et al (2012), instead of ours (P1) by using our linearization approach introduced above because of three main differences between them. Different from (Y1), (P1) considers multiple segments with different speed limits. Also (P1) does not consider the loss of revenue considered by (Y1) because (Y1) does not model the loss in enough detail for comparisons. (P1) does not consider quantity discount of fuel. Except for Yao et al (2012), this discount is not considered in the literature.

Because there are two non-linear terms, ((1)/(V i, i+1)) and V i, i+1 2, in (Y1), to remove one of the non-linear terms, they replace ((1)/(V i, i+1)) by W i, i+1. With this, they obtain another formulation (Y2) that is still non-linear because two constraints contain the term ((1)/(W n, n+1 2)). In order to solve this model, they replace the function (1)/(W i−1, i 2)) by a piecewise linear function by using the built-in linearization function of ILOG CPLEX.

Now, for the performance comparison, we apply our linearization approach, used to get (P2) from (P1), to (Y1). Here, the non-linear function F i, i+1=k 1 V i, i+1 3+k 2 is replaced by a piecewise linear function. By setting W i, i+1=((1)/(V i, i+1)) and Z i, i+1=((F i, i+1)/(V i, i+1)), (Y1) becomes:

Subject to

Constraints (1)–(9), (12)–(16), (20)–(23) in Yao et al (2012)

The main difference between the proposed model (P3) and that of Yao’s (Y2) is constraint (20), which linearizes the non-linear terms.

Now we compare the solutions of (P3) and (Y2). Remember that the solution of (Y2) needs the CPLEX’s linearization function, which not all LP/IP software provide. The input data for the experiments of Yao et al (2012) is shown in Table 2. The distances between two ports, which are not given by Yao, are obtained from www.portworld.com/map/. The other data such as r i, i+1 1, a i , r i, i+1 2 is set to 0. The mathematical models are formulated and solved by using ILOG OPL version 12.4.

Table 2 Input data of the performance comparison (Yao et al, 2012)
Full size table

For the comparison we use a 1000-interval piecewise linear function for (P3) and also a 1000-interval piecewise linear function for (Y2). The computation time of (Y2) is about 2 seconds while that of (P3) is 1.5 seconds. When a 500-interval piecewise linear function is used in (P3), the computation time goes down to 1.3 seconds. Total bunkering costs are almost the same for all these cases, around US$3 080 476 (Table 3). Experimenting on a larger size problem with 45 ports shows that the computation time to solve (Y1) with 1000 intervals, (P3) with 1000 intervals and (P3) with 500 intervals are approximately 16 min, 11 min and 3.5 min, respectively, while the objective function values are practically the same for these three cases. The reduction of computation time from (Y1) is about 30 per cent for 1000 intervals and 80 per cent for 500 intervals without sacrificing the operating cost.

Table 3 Comparison between Yao’s approach and the proposed approach
Full size table

Atlantic Pacific Express (APX) is an important service route, which connects 24 ports from East Asia, the United States and Europe. Table 4 is the data for the APX route. When a 1000-interval piecewise linear function is used for (P3) and (Y2), (P3) provides a solution faster than (Y2), with almost the same bunkering cost. When a 500-interval piecewise linear function is used for (P3), the objective function value is unchanged.

Table 4 Input data of the APX service route (Yao et al, 2012)
Full size table

These results show the proposed approach significantly reduces the computation time despite having approximately the same number of constraints and variables; (P3) has one more constraint and one more variable than (Y2) because a piecewise linear function is used during the solution process in (Y2). This shows the advantage of (P3), which is more significant for a larger problem.

Performance of heuristic procedure, BIP

The performance of BIP is compared with the results from (P2). The test data is similar to the above experiment. For the comparison, the data is modified by breaking a leg into several segments and this is shown in Table 5. In the table, the time window is adjusted to exclude the berth time for easiness in calculating the procedure. The results are shown in Table 6. The results also show that BIP can quickly support the manager to make decision for the bunkering problem considered in this article.

Table 5 Data for evaluating the heuristic algorithm, BIP
Full size table
Table 6 Comparison between using piecewise linear function and heuristic algorithm, BIP
Full size table

Conclusion

In this article, we consider the problem of optimizing the fuel management of a vessel by choosing vessel speed and bunkering quantity at each port. Specifically, we consider geographical features on a vessel’s route and the different maximum speeds over different segments of a leg.

This article first presented an LP modeling of the problem. Compared with an NLP modeling used in the literature, this LP modeling help the manager in quickly making decision on the mentioned problem without sacrificing the operating fuel cost. Because it is an LP, sensitivity analysis is possible, and can be done by any LP software, without requiring an additional linearization function of optimization software. Also, this article presented a heuristic algorithm, BIP, which is fast and can be easily implemented without requiring optimization software.

The problem can be extended by considering stochastic factors such as maximum vessel speed because of the effect of weather, port time and fuel prices. A methodology for online planning (making decisions about vessel speed, ports for bunkering and bunkering amount) can be developed in future research.