Journal Search Engine

ISSN : 2005-0461(Print)
ISSN : 2287-7975(Online)

Journal of Society of Korea Industrial and Systems Engineering Vol.39 No.2 pp.19-27
DOI : https://doi.org/10.11627/jkise.2016.39.2.019

A Heuristic Algorithm for a Ship Speed and Bunkering Decision Problem

Hwa-Joong Kim^*

, Jae-Gon Kim^**†

^*Asia Pacific School of Logistics, Inha University
^**Department of Industrial and Management Engineering, Incheon National University

Corresponding Author : jaegkim@inu.ac.kr

Received April 4, 2016 Finally Revised April 21, 2016 Accepted April 22, 2016

Abstract

Maritime transport is now regarded as one of the main contributors to global climate change by virtue of its CO2 emissions. Meanwhile, slow steaming, i.e., slower ship speed, has become a common practice in the maritime industry so as to lower CO2 emissions and reduce bunker fuel consumption. The practice raised various operational decision issues in terms of shipping companies: how much ship speed is, how much to bunker the fuel, and at which port to bunker. In this context, this study addresses an operation problem in a shipping companies, which is the problem of determining the ship speed, bunkering ports, and bunkering amount at the ports over a given ship route to minimize the bunker fuel and ship time costs as well as the carbon tax which is a regulatory measure aiming at reducing CO2 emissions. The ship time cost is included in the problem because slow steaming increases transit times, which implies increased in-transit inventory costs in terms of shippers. We formulate the problem as a nonlinear lot-sizing model and suggest a Lagrangian heuristic to solve the problem. The performance of the heuristic algorithm is evaluated using the data obtained from reliable sources. Although the problem is an operational problem, the heuristic algorithm is used to address various strategic issues facing shipping companies, including the effects of bunker prices, carbon taxes, and ship time costs on the ship speed, bunkering amount and number of bunkering ports. For this, we conduct sensitivity analyses of these factors and finally discuss study findings.

Key Words : Ship Speed , Bunkering , Nonlinear Program , Heuristics

선박속력 및 급유결정 문제에 대한 휴리스틱 알고리즘

김 화중^*, 김 재곤^**†

^*인하대학교 아태물류학부
^**인천대학교 산업경영공학과

초록

키워드 :

This article has been cited by 0 article in crossref

Cited-By

Funding:

National Research Foundation
Ministry of Education, Science and Technology
No. 2012R1A1A2004257

1Introduction

Slow steaming, i.e., slower ship speed, has now become a common practice in the maritime industry to save bunker cost, which is the largest among transportation costs occupying about 35 per cent of the total freight rate [15]. It is estimated that ocean carriers can save $3 billion per year through slow steaming [9]. Slow steaming can also change bunkering ports due to reduced bunker consumption and fluctuating bunker prices, and it can lower CO₂ emissions due to lowered consumption of the bunker, which is a fossil fuel. On the contrary, slow steaming increases transit times, which implies increased in-transit inventory costs in terms of shippers. Hahm [3] demonstrated the relationship between CO₂ emis sions and effective operation of a system.

In this context, the current paper aims to contribute the practice by investigating the joint ship speed and bunkering decision (JSB) problem. Here, bunkering is the storage of bunker fuels in the fuel tank in a ship, i.e., refueling the ship. A number of studies have recently considered ship speed optimization problems, among which research on the JSB problem is very recently receiving a lot of interests from the academia after Kim et al. [6]’s study. See Wang et al. [16] and Kim and Kim [4] for the ship speed optimization problem.

To the best of our knowledge, Kim et al. [6] first introduced the JSB problem by assuming same speed during a voyage, formulated it as a nonlinear programming model and suggested an epsilon-optimal algorithm. Yao et al. [17] considered a more general JSB problem by taking into account time window restrictions and suggested a heuristic based on linearization of the nonlinear model. Kim [5] considered a type of JSB problem by relaxing the same speed assumption made in Kim et al. [6] and suggested a Lagrangian heuristic algorithm. Sheng et al. [13] considered a JSB problem with both bunker prices and consumption uncertainties, formulated it as a robust optimization model, and suggested a heuristic algorithm by modifying Yao et al. [17]’s heuristic algorithm. Nielsen et al. [8] revisited Yao et al. [17]’s problem and modified Yao et al. [17]’s heuristic algorithm. Sheng et al. [12] suggested a (s, S) policy-inventory control model for a JSB problem with both bunker prices and consumption uncertainties. Meng et al. [7] dealt with a type of JSB problem for a tramp ship considering the ship routing and suggested a branch-and-price algorithm.

Our paper extends the work of Kim [5] who assumed all the bunker fuel from the immediately previous bunkering port to be exhausted as soon as the ship arrives at the bunkering port. Our paper relaxes the assumption made in Kim [5] and formulates the problem as a lot-sizing model. Our paper suggests a Lagrangian heuristic to solve the problem and the applicability of the heuristic is evaluated by a case study with the data from the literature and a shipping Korean company.

The remainder of this paper is organized as follows. The next section describes the JSB problem considered in our paper and presents a nonlinear programming model. Section 3 presents a Lagrangian heuristic algorithm and Section 4 evaluates the performance of the heuristic and analyzes the effects of bunker prices, ship time costs, and carbon taxes. Section 5 concludes the paper with a short summary and discussions on possible extensions.

2Problem Description

In this section, we define the JSB problem considered in our paper by formulating it as a nonlinear programming model. The JSB problem considered in this paper is to determine the ship speed, bunkering ports, and the bunkering amount through ports along a given route. Here, bunkering port is the port at which the ship is refueled (bunkered) and bunkering amount is the amount of bunker fuels refueled in the fuel tank in the ship. There is a ship navigating a shipping route, which is assumed to be known in advance. The ship makes a round trip, i.e., the first calling port of the ship and the last calling port are identical. When the ship arrives at a port, the bunker remaining at the fuel tank is the bunker just after departing the immediately previous port along the route minus the bunker amount consumed during a voyage from the previous port to the current port. There is a limit on the remaining bunker amount due to the capacity of the fuel tank in the ship, i.e., the remaining bunker cannot exceed the capacity. The ship speed should be within a range from a minimum speed υ_min to a maximum speed υ_max. We assume without loss of generality that the ship spends no time at any port although it makes port calls.

The objective of the JSB problem considered in our paper is to minimize the bunker purchase cost, ship time cost, and the carbon tax associated with the ship’s CO₂ emissions. For a clear definition of the costs and the nonlinear programming model, we summarize the notations as follows. In the notations, tCO₂ stands for a ton of CO₂ emissions.

Parameters

c daily ship time cost [US$/day]
e unit CO₂ emissions by fuel consumption of the ship [tCO₂/bunker ton]
f daily bunker fuel consumption rate at a given speed of the ship [bunker ton/day]
l_i nautical distance from port i to i+1 [nautical mile]
n number of ports on a ship route
p_i unit bunker purchase cost at port i [US$/ton]
q_max capacity of bunker tank of the ship [ton]
tax unit carbon tax on CO₂ emissions [US$/tCO₂]
υ given speed of the ship [knot]
υ_min minimum speed of the ship [knot]
υ_max maximum speed of the ship [knot]

Decision variables

I_i remaining bunker amount in the fuel tank just after arriving at port i [ton]
V_i speed of the ship from port i to i+1 [knot]
X_i bunkering amount at port i [ton]

The bunker purchase cost is the cost of buying bunker fuel at port i which is expressed as its unit cost multiplied by the amount of bunker fuel purchased, p_i X_i . The carbon tax is an environmental tax, which is implemented by taxing the amount of CO₂ emissions from fuel consumption for the purpose of reducing CO₂ emissions. The tax is calculated by considering a unit carbon tax and the amount of CO₂ emissions generated from bunker fuel consumed while sailing from port i to i+1. To obtain the bunker consumption, we adopt a well-known function for the bunker consumption and speed relationship [10, 11], $F_{i} = f / υ^{3} \cdot V_{i}^{3}$ [ton/day]. As a result, the carbon tax for the bunker consumption while sailing from port i to i+1 is $t a x \cdot e \cdot f / 24 υ^{3} l_{i} V_{i}^{2}$ . The ship time cost used in the model includes the cost of chartering the ship, the ship operating cost, and the time cost of containers on the ship. The ship operating cost is maintenance costs, and crew wages, among others, while the time cost of containers is the time value of cargoes loaded in the ship. The daily ship time cost during a voyage is represented by the unit time cost of ship multiplied by the sailing time, $c \cdot l_{i} / (24 V_{i})$ .

Based on the above problem definition and cost function, we formulate the JSB problem as a nonlinear programming model as follows.

[P1] Minimize $\sum_{i = 1}^{n - 1} p_{i} X_{i} + \sum_{i = 1}^{n - 1} t a x \cdot e \frac{f}{24 υ^{3}} l_{i} V_{i}^{2} + \sum_{i = 1}^{n - 1} c \frac{l_{i}}{24 V_{i}}$

subject to

\begin{array}{l} I_{i + 1} = I_{i} + X_{i} - \frac{f}{24 υ^{3}} l_{i} V_{i}^{2} & for i = 1, 2, \dots, n - 1 \end{array}

(1)

\begin{array}{l} I_{i} + X_{i} \leq q_{max} & for i = 1, 2, \dots, n - 1 \end{array}

(2)

\begin{array}{l} υ_{min} \leq V_{i} \leq υ_{max} & for i = 1, 2, \dots, n - 1 \end{array}

(3)

\begin{array}{l} I_{i}, X_{i} \geq 0 & for i = 1, 2, \dots, n - 1 \end{array}

(4)

The objective function to be minimized is the sum of bunker fuel purchase cost, the carbon tax imposed on CO₂ emissions, and the time cost of a ship. Constraint (1) represents the flow conservation of the bunker amount remaining at the fuel tank of the ship. Constraint (2) represents that the bunkering amount at a port plus the remaining at the fuel tank cannot exceed the fuel tank capacity of the ship. Constraint (3) guarantees that the ship speed should range between the minimum and maximum speeds. Constraint (4) is restrictions on the decision variables.

3Solution Algorithm

The solution approach to problem [P1] employs a Langrangian relaxation method, which is commonly used to convert a hard combinatorial problem into a relatively easy problem by dualizing (relaxing) sets of complicated constraints. First, the original model [P1] is reformulated as another nonlinear program so that the Lagrangian relaxation method can be applied more effectively. Second, a Lagrangian lower bounding and upper bounding schemes are presented based on the reformulation and lastly the Lagrangian relaxation heuristic algorithm is suggested.

The original model [P1] is reformulated as another model by adding

\begin{array}{l} Y_{i} = \frac{f}{24 υ^{3}} l_{i} V_{i}^{2} & for i = 1, 2, \dots, n - 1 \end{array}

(5)

Then, the objective function and constraint (1) respectively become

\sum_{i = 1}^{n - 1} p_{i} X_{i} + \sum_{i = 1}^{n - 1} t a x \cdot e Y_{i} + \sum_{i = 1}^{n - 1} c \frac{l_{i}}{24 V_{i}}

\begin{array}{l} I_{i + 1} = I_{i} + X_{i} - Y_{i} & for i = 1, 2, \dots, n - 1 \end{array}

(1.1)

In addition, to obtain a better lower bound, we add the following constraints

\begin{array}{l} I_{i + 1} \leq I_{i} + X_{i} - \frac{f}{24 υ^{3}} l_{i} υ_{min}^{2} & for i = 1, 2, \dots, n - 1 \end{array}

(1.2)

\begin{array}{l} I_{i + 1} \geq I_{i} + X_{i} - \frac{f}{24 υ^{3}} l_{i} υ_{max}^{2} & for i = 1, 2, \dots, n - 1 \end{array}

(1.3)

Adding the above constraints (1.2) and (1.3) does not affect the optimal solution since :

I_{i} + X_{i} - \frac{f}{24 υ^{3}} l_{i} υ_{max}^{2} \leq I_{i + 1} = I_{i} + X_{i} - \frac{f}{24 υ^{3}} l_{i} V_{i}^{2}

I_{i + 1} = I_{i} + X_{i} - \frac{f}{24 υ^{3}} l_{i} V_{i}^{2} \leq I_{i} + X_{i} - \frac{f}{24 υ^{3}} l_{i} υ_{min}^{2}

due to constraint (3). As a result, the integer program [P1] can be reformulated as follows.

[P2] Minimize $\sum_{i = 1}^{n - 1} p_{i} X_{i} + \sum_{i = 1}^{n - 1} t a x \cdot e Y_{i} + \sum_{i = 1}^{n - 1} c \frac{l_{i}}{24 V_{i}}$

subject to (1.1), (1.2), (1.3), (2), (3), (5), and

\begin{array}{l} I_{i}, X_{i}, Y_{i} \geq 0 & for i = 1, 2, \dots, n - 1 \end{array}

(4.1)

The Lagrangian relaxation approach used in this paper is based on the dualization of constraint (5) in the reformulation [P2] with Lagrangian multiplier α_i ≥ 0. Then, the resulting relaxed problem becomes

[LR] Minimize

\sum_{i = 1}^{n - 1} p_{i} X_{i} + \sum_{i = 1}^{n - 1} (t a x \cdot e - α_{i}) Y_{i} + \sum_{i = 1}^{n - 1} α_{i} \frac{f}{24 υ^{3}} l_{i} V_{i}^{2} + \sum_{i = 1}^{n - 1} c \frac{l_{i}}{24 V_{i}}

subject to (1.1), (1.2), (1.3), (2), (3), (4.1) and

\begin{array}{l} α \geq 0 & for i = 1, 2, \dots, n - 1 \end{array}

(6)

The relaxed model can be decomposed into two independent subproblems as follows :

[SP1] Minimize $\sum_{i = 1}^{n - 1} p_{i} X_{i} + \sum_{i = 1}^{n - 1} (t a x \cdot e - α_{i}) Y_{i}$

subject to (1.1), (1.2), (1.3), (2), (4.1), and (6)

[SP2] Minimize $\sum_{i = 1}^{n - 1} α_{i} \frac{f}{24 υ^{3}} l_{i} V_{i}^{2} + \sum_{i = 1}^{n - 1} c \frac{l_{i}}{24 V_{i}}$

subject to (3) and (6)

Subproblem [SP1] is a linear program and hence it can be easily solved using a commercial optimization tool such as CPLEX. On the other hand, it is not difficult to know that subproblem [SP2] can be decomposed into mutually independent n−1 subproblems [SP2_i] for i = 1, 2, …, n−1. The optimal solution of [SP2_i] can be obtained using the following property.

Property 1.There is the optimal speed for [SP2_i] defined as

\begin{array}{l} V_{i}^{*} = {\begin{array}{l} υ_{min} if {V^{'}}_{i} < υ_{min} \\ \begin{array}{l} {V^{'}}_{i} if υ_{min} \leq {V^{'}}_{i} \leq υ_{max} & for i=1, 2, \dots, n-1 \end{array} \\ υ_{max} if {V^{'}}_{i} > υ_{max} \end{array} \\ w h e r e {V^{'}}_{i} = \sqrt[3]{c \cdot υ^{3} / (2 α_{i} f)} \end{array}

(7)

Proof. Let Z_i be the objective function of [SP2_i]. The first-order derivative of Z_i with respect to V_i becomes

\frac{d Z_{i}}{d V_{i}} = α_{i} \frac{f}{12 υ^{3}} l_{i} V_{i} - \frac{c \cdot l_{i}}{24 V_{i}^{2}} = 0

which results in the speed giving the minimum value of Z_i as

{V^{'}}_{i} = \sqrt[3]{\frac{c \cdot υ^{3}}{2 α_{i} f}}

The objective function of Z_i is convex because

\frac{d^{2} Z_{i}}{d V_{i}^{2}} = α_{i} \frac{f}{12 υ^{3}} l_{i} + c \frac{l_{i}}{8 V_{i}^{3}} \geq 0

(A7)

Then, we can obtain equation (7) because the optimum speed should satisfy constraint (3). ■

To find a better lower bound, we need to find better values for Lagrangian multiplier α_i . In the following, we present a solution method for the following Lagrangian dual problem [LD] to find the best multiplier.

[LD] Maximize L (α) subject to (6)

where L (α) is an optimal solution value of [LR] and α denotes the vector for the Lagrangian multiplier.

The Lagrangian multiplier is updated using the subgradient optimization algorithm. Subgradient optimization algorithm generates a sequence of the Lagrangian multiplier using the following rule :

α_{i}^{[m + 1]} = max {a_{i}^{[m]} + θ^{[m]} β_{i}^{[m]}, 0} for i = 1, 2, \dots, n - 1

where $α_{i}^{[m]}$ denotes the value of the Lagrangian multiplier at iteration m. At iteration m, subgradient $β_{i}^{[m]}$ for Lagrangian multiplier α_i is determined by

\begin{array}{l} β_{i}^{[m]} = \frac{f}{24 υ^{3}} l_{i} V_{i}^{[m] 2} - Y_{i}^{[m]} & for i = 1, 2, \dots, n - 1 \end{array}

where $V_{i}^{[m]}$ and $Y_{i}^{[m]}$ are the optimal solution of [LR] problem obtained at iteration m. A positive scalar step size θ^[m] at iteration m is

θ^{[m]} = φ^{[m]} \frac{B^{*} - L (α^{[m]})}{{‖ β^{[m]} ‖}^{2}}

where φ^[m] ≤ 2 is a positive scalar, B^* is the best feasible solution value of problem [P] and ǁ•ǁ denotes the norm of vector •. The value for φ^[m] is set to be equal to 2 initially and is halved if the lower bound has not been improved in a predetermined number of iterations T.

In the upper bounding procedure, [SP1] is resolved after setting

\begin{array}{l} Y_{i}^{[m]} = \frac{f}{24 υ^{3}} l_{i} V_{i}^{[m] 2} & for i=1, 2, \dots, n-1 \end{array}

so at to obtain a feasible solution with respect to constraint (5).

We now present the Lagrangian heuristic proposed in this paper, which is terminated when iteration count m reaches a predetermined limit M.

Procedure 1 : (Lagrangian heuristic algorithm)

Step 1 : Set m = 1 and α_i = 0 for i = 1, 2, …, n−1. Let the best upper and best lower bounds be an arbitrary large number and 0, respectively.
Step 2 : Obtain the solution of [LR] by solving [SP1] and [SP2] using the methods described above.
Step 3 : Obtain a new lower bound by computing the objective function value using the solution of [LR]. Update the best lower bound and its solution once the new lower bound is greater than the best lower bound.
Step 4 : Obtain a new upper bound using the method described earlier and update the best upper bound and its solution once the obtained upper bound is less than the best upper bound. Stop if the best upper bound equals the best lower bound.
Step 5 : Set m = m+1, If m > M, stop. Otherwise, update the multiplier using the subgradient method described earlier and go to Step 2.

4Numerical Studies

We applied the proposed Lagrangian heuristic to applications taken from various reliable sources. We considered a shipping route in <Figure 1> taken from the website of Hyundai Merchant Marine (http://www.hmm21.com/), which is the route with the most calling ports in the company. In the route, the port of Hong Kong was the first as well as the last port, i.e., the sequence of the voyage was as follows: Hong Kong $\underset{353}{\to}$ Kaohsiung $\underset{925}{\to}$ Busan $\underset{363}{\to}$ Kobe $\underset{372}{\to}$ Tokyo $\underset{7723}{\to}$ Balboa $\underset{19}{\to}$ Panama Canal $\underset{53}{\to}$ Manzanillo $\underset{3007}{\to}$ Miami $\underset{342}{\to}$ Jacksonville $\underset{152}{\to}$ Savannah $\underset{97}{\to}$ Charleston $\underset{652}{\to}$ New York $\underset{3409}{\to}$ Rotterdam $\underset{262}{\to}$ Bremerhaven $\underset{308}{\to}$ Felixstowe $\underset{3347}{\to}$ New York $\underset{309}{\to}$ Norfolk $\underset{469}{\to}$ Charleston $\underset{3348}{\to}$ Manzanillo $\underset{53}{\to}$ Panama Canal $\underset{19}{\to}$ Balboa $\underset{2942}{\to}$ Los Angeles $\underset{384}{\to}$ Oakland $\underset{4534}{\to}$ Tokyo $\underset{372}{\to}$ Kobe $\underset{1406}{\to}$ Chiwan $\underset{19}{\to}$ Hong Kong. They are numbered as 1, 2, …, 28, respectively and the numbers under the arrows are nautical mile between ports, taken from the website of Dataloy (http://www.dataloy.com/).

Bunker fuel prices (US$ per ton) for Hong Kong, Kaohsiung, Busan, Tokyo, Balboa, Panama Canal, Miami, Jacksonville, Savannah, Charleston, New York, Rotterdam, Bremerhaven, Norfolk, Los Angeles, and Oakland were obtained from the website of Netpas (http://www.Netpas.net/) and found to be 201, 213.5, 202, 209, 173.5, 173.5, 239, 251.75, 239, 235, 178, 157, 207.5, 198, 169, and 337 for the respective ports. Those for the other ports could not be found from the website and hence were set at an arbitrarily big number by conjecturing that bunkering at the ports is not commonly taken place in real practice.

The carrying capacity of the ship used in this test K was 10,000 TEU with fuel tank capacity 10,329.9 ton adopted from 10,900 m³, the tank size of 9,178 TEU ship, 1.053 bunker ton/m³, and the advice of an operator in a shipping company that 90% of the capacity is bunkered in real practice. The daily bunker consumption rate was set to f = 0.0392K + 5.582 and the given speed was set to υ = 5.4178 K^0.1746 according to Tran [14]. The minimum and maximum speeds were set at 16 knots and 30 knots, respectively. Following Corbett et al. [1], CO₂ emissions were set at 3.17 tCO₂ per bunker ton. The daily ship time cost was obtained by adding the daily charter rate, the ship operating cost, and the time of containers on the ship. The vessel charter rate was set at 108.05 K^0.6257 according to Tran [14], the vessel operating cost was set at 0.7748 K + 4780.2642, which is an equation of a simple linear regression of the data in Gkonis and Psaraftis [2], the time cost of a container is US$ 40 per day and 3,000 TEU containers are on the ship in average.

The Lagrangian heuristic requires specific values for several parameters. After a preliminary experiment, the parameters in these experiments are set as follows : the iteration limits M and T were set to 1,000 and 50, respectively. The initial remaining bunker amount in the tank was set to zero without loss of generality. The subproblem [SP1] was solved using CPLEX version 12.6.1 and the algorithm tested in this paper is coded in C and run on a PC with a Pentium processor operating at 1.73GHz. The evaluation of the Lagrangian heuristic’s performance and scenario analyses are made under variable bunker prices, container time values, and carbon taxes. In the test, the bunker price was varied by multiplying the bunker prices in the case data by the bunker price multiplier ranging from 0.5 to 2.5, the container time value was varied from 25$ per TEU to 125, and the carbon tax was varied from zero to 400$ per tCO₂.

We evaluate the performance of the Lagrangian heuristic summarized in <Table 1>. We can see from <Table 1> that the heuristic can solve quickly all problem instances within 0.5 seconds. The gap between LB (lower bound) and UB (upper bound) is 0% for many cases and less than 0.06% for the others. It can be found that the gap slightly becomes bigger along with the bunker price and the CPU time also slightly becomes reduced as the carbon tax and container time value increase, but these effects on the performance are negligible. Therefore, it can be argued that the heuristic is a viable tool for determining the ship speed and bunkering ports in shipping firms.

We next study the effect of variable bunker price, which is summarized in <Table 2>. We can see from <Table 2> that different bunker prices can lead to different bunkering amount and slightly different bunkering ports, i.e., the bunkering amount and the number of bunkering ports decrease as the bunker price increases. This is because the ship speed is reduced to save the bunkering cost (fuel cost), which can be found from <Table 2> that the ship speed decreases as the bunker price increases. The speed reduction due to high bunker prices supports the slow steaming practice, and however, these speeds are much faster than the ships navigating around 16 knot due to the slow steaming practice in the current maritime industry. This may be because the slow steaming practice has become prevalent in the maritime industry in years when the oil price has been very high and after then, maritime companies did not increase their ship speed since the maritime industry was taking a serious turn for the worse.

Following, we study the effect of the container time value on the bunkering amount, the number of bunkering ports, and the ship speed. <Table 3> shows that the bunkering amount, the number of bunkering ports, and the ship speed increases along with the container time value. This is because cargos with high value require for quick delivery, i.e., high ship speed that results in increase of the bunkering amount and the number of bunkering ports since the bunker in the fuel tank is quickly consumed in case of a high ship speed. This implies that ships should speed up and bunker more when transporting high value products such as IT products.

Finally, we study the effect of the carbon tax summarized in <Table 4>, where zero carbon tax implies that no carbon tax is applied. The bunkering amount is 24,019.5 ton in case of zero carbon tax and it reduces to 7,547.6 ton in case of 400$ in order to save the bunker consumption contributing to CO₂ emissions. The same result is obtained in terms of the number of bunkering ports and the ship speed. This is because reducing the ship speed reduces the bunkering amount and the number of bunkering ports and as a result it lowers carbon tax charged to shipping companies. This implies that if a carbon tax regulation is realized in the shipping industry, shipping companies slower their ships’ speed and reduces the bunkering amount and number of bunkering ports.

5Concluding Remarks

In this study, we considered the problem of determining the ship speed, bunkering ports, and bunkering amount at the ports with the objective of minimizing the total cost of bunker purchase and ship time, and carbon tax. We formulated the problem as a nonlinear lot-sizing model. To solve the problem, we suggested a Lagrangian heuristic by deriving a property for the relaxed problem. A case study was performed by taking the data from reliable sources and the test result showed that the heuristic is a viable tool regarding the gap from the lower bound and computation time. In addition, we analyzed the effects of bunker prices, carbon taxes, and ship time costs on the ship speed and number of bunkering ports.

This research can be extended in several directions. First of all, global shipping firms proactively not only slow their ship speed in order to lower cope with operating costs caused by higher bunker price but also charter in additional ships in order to keep published weekly container services. Therefore, the problem with the number of ships to be deployed is a meaningful future research topic. Second, this research considered the carbon tax for CO₂ emission restriction and hence, the emission trading scheme, which is another option for the reduction is worthwhile to be considered in future research. Finally, the ship routing is also a very important decision issue for shipping companies and hence one may have to consider the ship routing, ship speed, and bunkering decision problem.

Acknowledgement

This research was supported by Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education, Science and Technology (No. 2012R1A1A2004257).

Figure

<Figure 1> .

A Shipping Route with the Most Calling Ports in Hyundai Merchant Marine

Table

<Table 1>.

Performance of the Lagrangian Heuristic

*(UB-LB)/LB·100(%).

	LB	UB	Gap(%)*	CPU second
(a) Bunker price multiplier
0.5	10480051.83	10480051.83	0.00	0.05
1.0	12748712.76	12749739.47	0.01	0.25
1.5	14555105.53	14560290.83	0.04	0.31
2.0	16020070.53	16026809.11	0.04	0.28
2.5	17256359.96	17265761.44	0.05	0.25
(b) Container time value
0	12748712.76	12749739.47	0.01	0.26
100	18017701.17	18021639.38	0.02	0.29
200	21282176.30	21285696.77	0.02	0.23
300	23799578.71	23799578.71	0.00	0.03
400	26192174.69	26192174.69	0.00	0.03
(c) Carbon tax (US$/tCO2)
25	10315601.41	10317741.24	0.02	0.28
50	14253789.57	14254154.08	0.00	0.23
75	17929663.31	17929663.31	0.00	0.03
100	21600392.48	21600392.48	0.00	0.03
125	25271121.65	25271121.65	0.00	0.03

<Table 2>.

Best Bunkering and Ship Speed Strategies at Different Bunker Prices

<Table 3>.

Best Bunkering and Ship Speed Strategies at Different Container Time Values

<Table 4>.

Best Bunkering and Ship Speed Strategies at Different Carbon Taxes

Reference

Corbett JJ , Wang H , Winebrake JJ (2009) The Effectiveness and Costs of Speed Reductions on Emissions from International Shipping , Transportation Research Part D, Vol.14 (8) ; pp.593-598
Gkonis KG , Psaraftis HN (2009) Some Key Variables Affecting Liner Shipping Costs , Working Paper, National Technical University of Athens,
Hahm HJ (2014) Overall Equipment Effectiveness as a Methodology for Green House Gas Emission Reduction , Journal of the Korean Institute of Plant Engineering, Vol.19 ; pp.63-74
Kim H-J , Kim J-G (2011) Determining Economic Ship Speeds and Fleet Sizes Considering Greenhouse Gas Emissions , Journal of the Society of Korea Industrial and Systems Engineering, Vol.34 (2) ; pp.49-59
Kim H-J (2014) A Lagrangian Heuristic for Determining the Speed and Bunkering Port of a Ship , Journal of the Operational Research Society, Vol.65 (5) ; pp.747-754
Kim H-J , Chang Y-T , Kim K-T , Kim H-J (2012) An Epsilon-Optimal Algorithm Considering Greenhouse Gas Emissions for the Management of a Ship’s Bunker Fuel , Transportation Research Part D, Vol.17 (2) ; pp.97-103
Meng Q , Wang S , Lee C-Y (2015) A Tailored Branchand- Price Approach for a Joint Tramp Ship Routing and Bunkering Problem , Transportation Research Part B, Vol.72 ; pp.1-19
Nielsen IE , Do NAD , Jang J , Bocewicz G (2015) Planning of Vessel Speed and Fuel Bunkering over a Route with Speed Limits , Maritime Economics and Logistics, Advance Online Publication
Page P (2011) Time, Money , The Journal of Commerce Online, http://www.joc.com/commentary/time-money
Ronen D (2011) The Effect of Oil Price on Containership Speed and Fleet Size , Journal of the Operational Research Society, Vol.62 (1) ; pp.211-216
Ronen D (1982) The Effect of Oil Price on the Optimal Speed of Ships , Journal of the Operational Research Society Research, Vol.33 (11) ; pp.1035-1040
Sheng X , Chew EP , Lee LH (2015) (s, S) Policy Model for Liner Shipping Refueling and Sailing Speed Optimization Problem , Transportation Research Part E, Vol.76 ; pp.76-92
Sheng X , Lee LH , Chew EP (2014) Dynamic Determination of Vessel Speed and Selection of Bunkering Ports for Liner Shipping under Stochastic Environment , OR Spectrum, Vol.36 (2) ; pp.455-480
Tran NK (2011) Studying Port Selection on Liner Routes : An Approach from Logistics Perspective , Research in Transportation Economics, Vol.32 (1) ; pp.39-53
UNCTAD (2012) Review of Maritime Transport 2012 (UNCTAD/RMT/2012) , United Nations Conference on Trade and Development, United Nations Publication, http://unctad.org/en/PublicationsLibrary/rmt2012_en.pdf
Wang S , Meng Q , Liu Z (2013) Bunker Consumption Optimization Methods in Shipping : A Critical Review and Extensions , Transportation Research Part E, Vol.53 ; pp.49-62
Yao Z , Ng SH , Lee LH (2012) A Study on Bunker Fuel Management for the Shipping Liner Services , Computers and Operations Research, Vol.39 (5) ; pp.1160-1172

Bunker price multiplier	Bunkering amount (1,000 ton)					Ship speed (knots)
Bunker price multiplier	0.5	1.0	1.5	2.0	2.5	0.5	1.0	1.5	2.0	2.5
Hong Kong	7.3	6.1	4.6	3.9	3.3	30.0	27.4	24.0	21.8	20.2
Kaohsiung
Busan
Kobe
Tokyo								23.8
Balboa	5.8	5.4	4.0	3.4	2.9		28.8	25.5	27.3	28.1
Panama								25.2	22.9	22.4
Manzanillo								25.0		21.2
Miami								25.2
Jacksonville
Savannah
Charleston								25.1
New York								25.0
Rotterdam	10.3	10.3	10.1	8.3	7.2		29.1	26.0	23.7	22.0
Bremerhaven							29.1	26.0
Felixstowe							29.0	25.8
New York							29.1	26.0
Norfolk							29.1	26.0
Charleston							29.0	26.2
Manzanillo							29.1	26.0		22.4
Panama							29.1	26.0	27.3	28.1
Balboa							28.9	26.1	23.7	22.0
Los Angeles	3.1	2.2					29.1	26.0
Oakland							29.1	26.0
Tokyo							29.0	25.9
Kobe							29.0	26.0
Chiwan							29.1	26.0	27.3	28.1
Total bunkering amount	26.5	24.0	18.7	15.6	13.4

Carbon tax ($/tCO2)	Bunkering amount (1,000 ton)					Ship speed (knots)
Carbon tax ($/tCO2)	0	100	200	300	400	0	100	200	300	400
Hong Kong	6.1	3.3	2.4	2.1	2.1	27.4	20.0	17.1	16.0	16.0
Kaohsiung
Busan
Kobe
Tokyo
Balboa	5.4	2.7	1.9	1.7	1.7	28.8	24.4	20.2
Panama								17.6
Manzanillo								17.3
Miami
Jacksonville
Savannah
Charleston
New York
Rotterdam	10.3	6.3	4.5	3.8	3.8	29.1	20.6	17.4
Bremerhaven						29.1
Felixstowe						29.0
New York						29.1
Norfolk						29.1
Charleston						29.0
Manzanillo						29.1		17.6
Panama						29.1	24.4	20.2
Balboa						28.9	20.6	17.4
Los Angeles	2.2					29.1
Oakland						29.1
Tokyo						29.0
Kobe						29.0
Chiwan						29.1	24.4	20.2
Total bunkering amount	24.0	12.3	8.8	7.5	7.5

Container time value ($/day/TEU)	Bunkering amount (1,000 ton)					Ship speed (knots)
Container time value ($/day/TEU)	25	50	75	100	125	25	50	75	100	125
Hong Kong	5.0	6.9	7.3	7.3	7.3	24.7	29.0	30	30	30
Kaohsiung
Busan
Kobe
Tokyo						24.8
Balboa	4.4	5.8	5.8	5.8	5.8	28.7	30
Panama						26.0
Manzanillo
Miami
Jacksonville
Savannah
Charleston
New York						25.9
Rotterdam	10.3	10.3	10.3	10.3	10.3	26.4
Bremerhaven						26.5
Felixstowe						26.4
New York						26.5
Norfolk						26.4
Charleston						26.3
Manzanillo						26.5
Panama						28.7
Balboa						26.3
Los Angeles		3.1	3.1	3.1	3.1	26.4
Oakland						26.3
Tokyo						26.4
Kobe						26.3
Chiwan						28.7
Total bunkering amount	19.7	26.1	26.5	26.5	26.5