Fleet deployment with time-chartered and voyage-chartered tankers for a refined oil shipping company

Abstract

With ongoing global industrialization, the demand for refined oil products, particularly in developing countries, is increasing significantly. Shipping companies typically transport refined oil from a primary refinery to multiple oil depots, addressing various demand tasks. To manage uncertain refined oil demand, shipping companies use both self-owned tankers and outsourced tankers, including time-chartered and voyage-chartered tankers. A time charter is a contract where the shipping company pays charter money for a specific period, while a voyage charter involves payments based on voyage frequency. This paper develops a nonlinear programming model to optimize fleet deployment, considering transportation costs and penalty costs for capacity loss during a planning period. Additionally, the model is extended to allow flexible charter types, meaning that time-chartered and voyage-chartered tankers are interchangeable based on shipping demands. A heuristic algorithm based on tabu search is designed to solve the proposed models, and four search operators are incorporated to enhance algorithm efficiency. The models and algorithms are validated using a real tanker fleet. Numerical experiments demonstrate the efficiency of the improved tabu search algorithm in obtaining exact solutions for small-scale instances. The case study indicates that the shipping company prefers waiting for tasks to avoid ship delay penalties and provide high-quality services. Moreover, the flexible charter strategy can reduce shipping costs by 16.34%. These findings offer management insights for determining charter contracts for ship fleets.

Graphical abstract

Keywords

fleet deployment / refined oil shipping / time-chartered / voyage-chartered / tabu search

1 Introduction

1.1 Research background

Economic industrialization heavily relies on energy sources, and refined oil, as the primary material, is essential for industrial development. In 1993, China transitioned from a net oil exporter to a net oil importer, and it is now the largest oil importer globally. The annual growth rate of refined oil consumption in China has remained at approximately 9.5% (He and Lin, 2023). Given the significant demand for refined oil and fluctuating freight rates, shipping companies have adopted a combination of transportation modes to effectively manage their transport capacity (Wang et al., 2021a). First, these shipping companies utilize their self-owned transport capacity by owning and operating their fleet of ships to meet a portion of their maritime transportation needs. This approach provides them with more control over the timing and efficiency of maritime transportation while also reducing transportation costs. Second, they opt to charter additional transport capacity for a specific period to fulfill their transportation requirements beyond their own fleet. This allows them the flexibility to adjust the number and types of chartered vessels as needed, with lower costs compared to bareboat chartering. Last, they collaborate with other shipping companies through voyage-chartered ships, thereby expanding their transport capacity to meet varying cargo transportation demands. This strategy promotes resource sharing, operational flexibility, and efficient utilization of maritime capacity while also mitigating operational risks through risk sharing.

Given the rapidly changing international situation, shipping companies are increasingly inclined to mitigate their risks through ship chartering. The ship chartering market is projected to reach a size of USD 14.79 billion in 2024 and is expected to grow to USD 27.97 billion by 2029, with a compound annual growth rate (CAGR) of 13.59% (Mordor Intelligence, 2024). By employing a combination of these transport capacity control methods, companies can ensure sufficient transport capacity, avoid resource wastage due to declining demand, enhance operational efficiency, reduce costs, improve operational flexibility, and increase resilience to risks (Lespier et al., 2019). This strategy has become the preferred choice for a growing number of domestic cargo owners in China as they navigate the evolving landscape.

In terms of cost, self-owned transport capacity has the lowest cost, followed by chartering transport capacity (where longer charter durations result in lower costs), and voyage-chartered ships have the highest cost. Therefore, expanding chartering transport capacity based on actual needs is an important measure for companies to reduce logistics costs, given a determined scale of self-owned transport capacity. The key focus of this study is to analyze demand and vessel supply data, determine the scale and vessel structure of chartering transport capacity, and allocate these data to the required routes in a manner that minimizes total transportation costs while ensuring optimal utilization of self-owned transport capacity.

On an annual basis, total transportation demand consists of several voyage tasks, including cargo volume, loading and unloading time, and route. The time required to complete a voyage task and return to the loading port for the next voyage can be determined based on the vessel speed and cargo handling time. In practical operations, suitable routes are identified first to meet the full-year route requirements of self-owned transport capacity, ensuring close connections and full-load operation between consecutive voyages. Then, the remaining cargo volume, which is the same for each route and meets the requirements for continuous turnover of transport capacity per vessel, is consolidated and analyzed for specific time periods. Continuous time periods exceeding three months of transportation demand are extracted to guide the chartering work for transport capacity. Self-owned capacity and time-chartered capacity are shared on different routes, characterized by tight connections and high efficiency.

This paper takes China Petroleum domestic coastal transportation as an example to explore the comprehensive analysis of annual transportation demand under multiple transport capacity control modes. The integration of vessels with different tonnages into reasonable continuous routes based on self-owned transport capacity is discussed. The remaining demand is then consolidated, and reasonable recommendations are provided for chartering transport capacity, including vessel types and lease start and end dates. Finally, guiding suggestions are presented for chartering transport capacity on the remaining routes to achieve the research objective of minimizing total transportation costs. Self-owned and time-leased people both participate in ship-sharing and ultimately achieve the lowest total transportation costs. The combination of these factors in this research is the first of its kind in the industry, demonstrating high research value and practical application significance.

1.2 Main contributions

This article makes a dual contribution. First, this paper presents a novel problem and develops a new model for transporting refined oil products using different types of ships. We consider various fleet types, including self-owned ships, time-chartered ships, and voyage-chartered ships. The qualities of these types of charters differ, including factors such as operation cost, ship capacity, and main engine power. The model is further extended by combining time-chartered ships and voyage-chartered ships into a single fleet, allowing flexible selection based on demand. Second, the article proposes a tabu search algorithm to efficiently solve the models presented, and numerical experiments using real data from China Petroleum confirm the effectiveness of the proposed models and algorithms.

2 Literature review

The literature on the problem of transporting refined oil can be categorized into three groups. The first group focuses on optimizing self-owned tanker fleets, including fleet deployment, ship networks, and sailing speed. In addition to self-owned fleets, shipping companies often charter ships through either long-term or short-term contracts to meet uncertain refined oil demands. The second group is concerned with optimizing tramp ship fleets using long-term contracts. The final group concentrates on short-term contracts for outsourcing services, including voyage-chartered and time-chartered tankers.

For traditional oil tanker fleets, previous studies have focused primarily on optimizing self-owned fleets. These include fleet deployment (Chen et al., 2024; Ronen, 2011; Zhen et al., 2019), shipping networks (Bellmore et al., 1971; Brown et al., 1987; Lespier et al., 2019), and emergency accident management (Wan et al., 2023; Wang et al., 2022). Koza et al. (2017) considered both onshore investments and tanker fleet deployment and proposed a nonlinear arc-based mathematical model to minimize long-term costs. They developed an exact algorithm to establish the fundamental decision rules. However, the transport of oil is subject to the influences of the oil supply and inventory usage, making the transport task highly dynamic. Ye et al. (2017) addressed this challenge by proposing time-slot and discrete-time modes, enabling complex scheduling and routing of refined oil tankers while considering the petroleum supply chain. As sustainable industrial development becomes a trend, the International Maritime Organization has set the goal of achieving a zero-carbon net by 2050. Xin et al. (2019) studied the optimal berthing order and green sailing speeds for shuttle tanker fleets to minimize operating costs and carbon taxes. They designed a fleet green scheduling algorithm based on column generation to solve this optimization problem. The aforementioned literature has focused mainly on optimizing self-owned ship fleets to reduce operational costs under specific scenarios. These studies have provided foundational models and algorithms for tanker fleet optimization. However, refined oil transportation now faces new challenges, such as dynamic demands and carbon emission limits. Therefore, exploring how to optimize fleet operation strategies considering these influencing factors opens up new directions for the study of refined oil transportation.

Due to the dynamic nature of the refined oil demand market, most oil shipping companies have insufficient capacity to meet the usual demand. Tramp ships, which have long-term contracts and a heterogeneous fleet, can fulfill uncertain demands. Unlike regular fleets, tramp ships are scheduled based on uncertain transport demand, similar to taxis in public transportation. There are various tramp ship problems under different conditions, including bunkering with different prices, cargo sizes dependent on load, voyage separation requirements, spatial and temporal shipping tasks, and uncertain demands (Li et al., 2022; Meng et al., 2015; Norstad et al., 2011; Wen et al., 2016; Zhao and Yang, 2018).

Fagerholt et al. (2013) investigated one-time basis cargo transport using tramp ships and developed a mathematical model that considers complex stowage requirements onboard ships and cargo coupling. They proposed a tabu search algorithm to find the optimal solution, significantly improving the efficiency of the shipping schedule. Lin and Liu (2011) presented a combined mathematical model that considers ship fleet development, freight assignment, and ship routing in tramp shipping. They developed a genetic algorithm to obtain the optimal solution for real-world problems.

The energy cost of the sailing speed is nonlinear due to the cubic relationship between fuel consumption and speed. Norstad et al. (2011) addressed sailing speed optimization along with the ship routing problem and designed a multi-start local search heuristic to solve it. Siddiqui and Verma (2017) investigated contract types between spot charters and time charters and found that a refined oil tanker fleet can reduce risks by combining charter contracts and investing in new ships. The above literature contributes to the exploration of long-term tramp ship fleet optimization by considering more realistic factors.

To mitigate the impact of spot freight rate fluctuations, refined oil transportation companies may consider utilizing outsourcing services through short-term contracts. Ship chartering involves a contractual arrangement between a lessor and a lessee, where the lessee outsources a ship for a specified period or voyage in exchange for charter payments. In this arrangement, the lessor (the owner or chartering company) grants the lessee (the operator or shipping company) possession and operational control of the ship for an agreed-upon duration. Effective risk management in the shipping industry can help reduce operating costs given the inherent volatility of the market. Short-term contracts can be divided into two categories: time-charter and voyage-charter contracts. A time-charter contract provides the carrier with the ability to avoid and hedge against freight rate risks during a designated time frame. On the other hand, a voyage-charter contract mandates that the ship completes a single journey from a predetermined origin to a destination. Time-charter contracts are suitable when stochastic parameters are known, whereas voyage-charter contracts are better adapted for uncertain scenarios. Kavussanos (1996) explored the dynamics of stochastic time-charter shipping contracts, comparing the time-varying measured risk between bulk carriers in spot and time-chartered markets. Similarly, Köhn and Thanopoulou (2011) focused on bulk carriers and observed how the delivery destination, charter period, forward time to delivery, vessel capacity, and energy consumption affected time-charter contracts. However, tankers, compared to other vessel types, face excessive or partially uninsurable risks, such as tanker accidents, resulting in higher charter costs. Zhang and Zeng (2015) studied the interconnectedness between time-chartered and spot freight rates, revealing a two-way lead–lag relationship. Wang and Xu (2015), in their examination of voyage-chartered shipping, considered optimizing sailing frequency and speed under carbon emission regulations and demurrage. Additionally, there have been studies that jointly analyze time-chartered and voyage-chartered contracts. Tsioumas and Papadimitriou (2015) developed a mathematical model to understand the equilibrium between time-chartered and voyage-chartered contracts and proposed an efficient strategy based on technical analysis to enhance shipping company revenues through charter combinations. Arslan and Papageorgiou (2017) devised a dynamic rolling-horizon fashion framework to solve the multistage stochastic programming model when selecting charters.

The focus of Wang et al.’s (2013) research lies in optimizing tanker chartering problems specific to refineries. They take into account the dynamics of spot freight rates and the uncertainty surrounding tanker arrivals. To solve the proposed model and achieve the optimal fleet chartering plan, they import an optimal stopping problem with geometric Brownian motion that considers spot freight rate dynamics. In contrast to Wang et al.’s (2013) study, our research expands upon the consideration of time-chartered and voyage-chartered ships to also include self-owned fleets. Additionally, we evaluate the service penalty based on the task implementation time. Santos and Guedes Soares (2024) examined the issue of transporting oil between terminals and deep-water oil production sites using shuttle tankers. They presented a nonlinear programming model aimed at minimizing voyage costs, chartering costs, and production loss costs. Their proposed model adopts a simulation optimization methodology that accounts for uncertainties in weather conditions and oil production. In contrast to Santos and Guedes Soares’ (2024) research, our paper focuses on the optimization of long-distance transport tanker fleet deployment, which involves larger tonnage and higher chartering costs than shuttle tankers. Furthermore, our study addresses the refined oil transportation problem, including self-owned fleets, time-chartered tankers, and voyage-chartered tankers. The core motivation behind this research is to efficiently optimize ship fleet deployment, including both self-owned and outsourced fleets, based on the demands of oil transportation. The shipping demand is divided into various tasks, including the origination port, destination port, and loading volume. Moreover, a penalty coefficient is introduced to penalize unfilled capacity and vacancy time for self-owned and time-chartered fleets. In reality, certain outsourcing companies exclusively offer time-chartered or voyage-chartered services, while others provide a combination of both. Therefore, we extend the model to consider these two scenarios accordingly.

3 Problem descriptions and assumptions

In the first half of 2023, northeast China accounted for approximately 21% of the country’s oil production (Chi, 2023). Dalian Port, the largest port in north-east China, achieved a container throughput of 2.3 million TEUs in the first half of 2023, a 20.8% increase (Liaoning Daily, 2023). The China Ocean Shipping Company (COSCO), one of the major players in refined oil shipping, offers refined oil transportation services from northeast China to south China, where the majority of oil refineries are concentrated around Dalian port. Therefore, it can be assumed that the supply port is located in Dalian. The refined oil transportation problem addressed in this paper focuses on the transportation of multiple types of refined oil (gasoline and diesel) to various customers (destinations) via a fleet of ships. The customers provide their oil demand for each oil type at the beginning of each month. In addition to self-owned ships, the shipping company also utilizes chartered ships, including both time-chartered and voyage-chartered tankers. These choices are made by the shipping company based on the requirements of each task and the desired order of implementation.

Consider a company providing refined oil shipping services from one oil refinery to oil depots during a planning period (typically, three months), represented by \hat{T}. Suppose that the oil demand can be divided into limited tasks and that each ship carries out only one task on each trip, which means that the ship must return to the oil refinery after finishing one task. We define shipping task set N by the quantity of oil measured in tons, the task received time, and the sailing time, namely, the triple \left(Q_i,a_i,d_i\right),i\in N. The sailing time d_i is the double sailing time from the oil refinery to the oil depot with an average speed v, typically 12 knots. The loading and unloading time at professional oil ports \tau is generally approximately two days or 48 h. Note that several tasks share the same depot. However, those tasks are required by different consignees. Therefore, we distinguished those tasks with quantity–time pairs. Furthermore, refined oil goods include products related to gasoline, diesel, and kerosene. Each product is associated with a density, which affects the loading capacity of a tanker. For convenience, the quantity Q_i is converted to the standard quantity. For example, gasoline, which has the lowest density, serves as the reference. When dealing with tasks involving diesel products, the standard quantity is obtained by multiplying the actual quantity by the ratio of the densities of diesel and gasoline. Keeping in mind the preferences of the customers, it is crucial that a shipping task is not divided into subtasks, and the delivery time remains unchanged.

Moreover, this research is based on the following assumptions. First, this paper considers the soft delay penalty rather than a hard restriction on the service time window. Second, each ship must return to the supply port after completing the task. However, the ship may visit multiple ports to reduce sailing costs. Furthermore, this paper assumes that various oil types are standardized into one type of oil. However, tankers usually have different tank farms to load different types of oils, such as gasoline and diesel. If different oil types are considered, tank farms may not be optimally utilized, and space allocation needs to be optimized to reduce operational costs.

The refined oil shipping company owns a tanker fleet, called a self-owned fleet, denoted by S_1. Correspondingly, there is a potential tanker fleet in the outer shipping market called the outsourcing fleet. A self-owned fleet is generally not enough to fulfill shipping tasks. Thus, the company can rent the outer ships through the outsourcing service. Two rental service types prevail in the shipping market: time-chartered and voyage-chartered, which are denoted by S_2 and S_3, respectively. For the time-chartered service, the company signs a fixed-period contract with the tanker owner and pays a period-based rent fee. In return, the time-chartered tanker is completely controlled by the company during the period. For the voyage-chartered service, the company rents a tanker from the outer shipping market for a specific task. It pays for a one-way voyage-based rent fee. The whole fleet set is defined as S=\{S_1,S_2,S_3\}, and the capacity of ship s is Y_s.

The cost of the self-owned tanker includes the operational cost and bunker consumption. The cost of the self-owned tanker is dependent on the operational time, denoting the hourly operational cost by c_s^1 (dollars/hour), s\in {\mathcal{S}}_0. For time-chartered tankers, the rent fee is related to the length of the rental period and the ship size. The corresponding period-based fee for rent period \hat{T} and tanker s is c_s^2 (dollar/month). For voyage-chartered tankers, the rent fee is related to the one-way sailing distance and tanker size. Suppose the marginal rent fee per nautical mile for tanker s is c_s^3 (dollar/nautical mile). The practice of the refined oil shipping service should be considered. A tanker serves only one depot with one type of oil product at a time. Therefore, the tanker must sail back and forth between the refinery and multiple depots if it belongs to a self-owned or outsourced fleet. The problem of the refined oil shipping company is to minimize the total shipping cost by jointly deploying the self-owned and outsourcing fleets and determining the time-chartered and voyage-chartered services. Due to the limited fleet, not every task can be fulfilled on time. Moreover, nonworking, self-owned tankers and time-chartered tankers are also sources of waste. The coefficient \beta (dollar/(month\timeston)) is imported to capture the penalty of the delayed task and nonworking tankers. We further assume that the cost of self-owned tankers is far lower than that of outsourcing services and that time-chartered tankers have a time-scale effect. Thus, the marginal cost of the same tanker is lower than that of the voyage-chartered tanker.

4 Model formulations of the tanker assignment problem with ship sharing

Based on the notation and assumptions described above, we propose a mathematical programming model to optimize fleet deployment in refined oil transportation. This problem can be framed as a tanker assignment or task-tanker matching problem that incorporates various types of outsourcing services. Unlike traditional liner services with fixed schedules and shipping lines, our company allows any tanker to serve any depot at any time. An outsourcing tanker is selected as a time-chartered service, which is determined endogenously using a global optimization method. As a result, multiple customers can share a tanker and multiple shipping lines, similar to the concept of car sharing in the taxi market.

To present the mathematical model, we first introduce the 0–1 variables x_{ij}^s to capture the task assignment scheme (Tan et al., 2023). x_{ij}^s equals one if task j is carried out after completing task i of tanker s; otherwise, it equals 0. Continuous variables t_i^s denote the task i execution time of ship s. V=\{0,N+1\}\cup N is a dummy task set used to construct a closed assignment scheme. Given a feasible assignment scheme, the total cost of a self-owned tanker s in S_1 includes the total operational cost and the total penalty cost of the capacity loss during the whole planning period, namely,

(1)\begin{array}{rl}{\Pi }_s^1=& \sum _{i,j\in V}{c}_s^1{x}_{ij}^s{d}_i+\frac{1}{30}\sum _{i,j\in V}\beta \left(Y_s-Q_i\right)\left(d_j+\tau \right)x_{ij}^s\\ & +\beta Y_s\left[\hat{T}-\frac{1}{30}\sum _{i,j\in V}\left(d_j+\tau \right)x_{ij}^s\right]\\ =& \sum _{i,j\in V}{c}_s^1{x}_{ij}^s{d}_i-\frac{1}{30}\sum _{i,j\in V}\beta Q_j\left(d_j+\tau \right)x_{ij}^s+\beta Y_s\hat{T}\end{array}.

The first item is the sailing cost for ship s to execute task j, and the second item is the penalty for the unfilled capacity of ship s during the task implementation. The last item is the capacity loss for the nonworking period of the ship s. Note that the penalty cost can reduce the inefficient utilization of a tanker. The sailing cost in this paper is expressed as a function of the sailing distance. In reality, the sailing cost consists of two components: fuel costs and time costs. The fuel cost is a function of the sailing speed, and the sailing time cost is proportional to the sailing time. The refined oil loading and unloading process will inevitably incur corresponding labor and equipment usage costs. The equipment usage cost is positively related to the ship size. The loading and unloading costs can be modeled as a linear function of the refined oil demand. Since the demand must be satisfied at each port, the loading and unloading costs are constant in the objective function, thus not affecting the structure of the optimal solution. Moreover, the transportation cost of refined oil products from refineries to supply ports is not considered in this research.

For the cost of tankers in the outsourcing fleet, if the company rents a tanker s in S_2 as time-chartered with contract period \hat{T}, the rent cost for the tanker is fixed c_s^2\hat{T}. Then, the problem for the company is how to utilize the tanker more efficiently during the determined period. The total cost of the tanker is the sum of the rent cost and the penalty cost of the capacity loss during the rent period.

(2)\begin{array}{rl}{\Pi }_s^2=& c_s^2\hat{T}+\frac{1}{30}\sum _{i,j\in V}\beta \left(Y_s-Q_i\right)\left(d_j+\tau \right)x_{ij}^s\\ & +\beta Y_s\left[\hat{T}-\frac{1}{30}\sum _{i,j\in V}\left(d_j+\tau \right)x_{ij}^s\right]\\ =& \left(c_s^2+\beta Y_s\right)\hat{T}-\frac{1}{30}\sum _{i,j\in V}\beta Q_j\left(d_j+\tau \right)x_{ij}^s\end{array}.

For a voyage-chartered tanker, the one-way rent cost can be calculated by multiplying the marginal rent fee and sailing distance for each assigned task, namely,

(3){\Pi }_s^3=\frac{1}{2}{c}_s^3\sum _{i,j\in V}{x}_{ij}^s{d}_{j}v.

With the above discussion, the task-tanker matching problem can be formulated as the following mixed integer programming model:

(4)\mathrm{m}\mathrm{i}\mathrm{n}\sum _{s\in S_1}{\mathrm{\Pi }}_s^1+\sum _{s\in S_2}{\mathrm{\Pi }}_s^2+\sum _{s\in S_3}{\mathrm{\Pi }}_s^3

subject to

(5)\sum _{s\in S}\sum _{j\in V}{x}_{ij}^s=1,\mathrm{\forall }i\in N,

(6)\sum _{i\in V}{x}_{ij}^s\le Y_s,\mathrm{\forall }s\in S,j\in N,

(7)t_i^s+d_{ij}+\tau -\left(1-x_{ij}^s\right)G\le t_j^s,\mathrm{\forall }s\in S,i,j\in V,

(8)t_j^s\ge \sum _{i\in V}{x}_{ij}^s{a}_j,\mathrm{\forall }s\in S,j\in N,

(9)t_i^s+\sum _{j\in V}{x}_{ij}^s\left(d_{ij}+\tau \right)\le \hat{T},\mathrm{\forall }s\in S,i\in N,

(10)\sum _{j\in V}{x}_{ij}^s\le 1,\mathrm{\forall }s\in S,i\in N,

(11)\sum _{i\in V}{x}_{ij}^s\le 1,\mathrm{\forall }s\in S,j\in N,

(12)\sum _{j\in V}{x}_{ij}^s=\sum _{j\in V}{x}_{ji}^s,\mathrm{\forall }i\in N,s\in S,

(13)\sum _{j\in N}{x}_{0j}^s=1,\mathrm{\forall }s\in S,

(14)\sum _{i\in N}{x}_{i,N+1}^s=1,\mathrm{\forall }s\in S,

(15)x_{ij}^s\in \{0,1\},\mathrm{\forall }s\in S,i,j\in V,

(16)t_i^s\ge 0,\mathrm{\forall }s\in S,i\in N.

Objective Function (4) aims to minimize the total costs of the self-owned fleet and the outsourcing fleet, which includes time-chartered tankers and voyage-chartered tankers. Constraint (5) states that each task must be assigned to only one tasker. Constraint (6) is the capacity constraint, which means that the assigned task cannot exceed the capacity of a tanker. Constraint (7) is defined to avoid task conflicts, ensuring that if two tasks are simultaneously assigned to a tanker, the time gap between the departure of the second task and the delivery of the first task must not be less than the sailing-back time of the first task. Constraint (8) stipulates that the task implementation time must be after the task received time. Constraint (9) indicates that the task completion time must be within the working period \hat{T}. Constraints (10) to (12) are the flow equilibria for the task scheme. Constraints (13) and (14) guarantee the closed cycle of task implementation order. Constraints (15) and (16) give the bounds of the decision variables.

In the model formulated by Constraints (4) to (16), the time-chartered and voyage-chartered tankers are fixed, which means that outsourcing ships cannot change their charter. However, in a real chartering company, all available tankers can be flexibly allocated as time-chartered or voyage-chartered tankers based on task demand. In other words, the tanker sets S_2 and S_3 are regarded as an entirety for outsourcing scheduling. Then, we consider extending the model to flexible charter allocation. The outsourcing company has M tankers, including the time-chartered and voyage-chartered tankers. S_2 is defined as the set of all outsourcing tankers with the time-chartered cost, and S_3 is set as a dummy set of S_2 when the rent type is voyage-chartered. Note that the properties of the tankers in sets S_2 and S_3 are the same, such as the capacity. Then, the following constraints are defined to bind S_2 and S_3:

(17)\sum _{j\in N}{x}_{0j}^s+\sum _{j\in N}{x}_{0j}^{s+M}\le 1,\mathrm{\forall }s\in S_2.

In this manner, two mixed integer programming models are presented to address the refined oil shipping problem. The first model considers fixed-time-chartered ships, while the second model allows the outsourced ships to choose their charter. Both models share a similar nature to the traditional vehicle routing problem, which is known to be NP-hard. Commercial solvers can handle small-scale problems and provide exact solutions. However, for larger problem sizes, solvers such as Gurobi and Cplex may fail to obtain an optimal solution within a reasonable computation time. As a result, a heuristic algorithm will be developed to enhance the efficiency of solving the proposed models.

5 Solution algorithm

The methods for solving NP-hard problems can be categorized into two groups. The first category, called exact algorithms, includes branch-and-bound algorithms, branch-and-cut algorithms, and branch-and-cut pricing algorithms (Huang et al., 2021; Huang and Liao, 2023). Exact algorithms can find the optimal solution to the problem, but they are time-consuming and not suitable for large-scale problems. The second category is heuristic algorithms, which use established search rules to find a satisfactory solution within a reasonable computation time. The advantage of heuristic algorithms is their speed, but they do not guarantee an optimal solution (Shang et al., 2023; Shao et al., 2022). Common heuristic algorithms include genetic algorithms, particle swarm algorithms, and tabu searches. Tabu search, one type of evolutionary algorithm, performs global optimization using neighborhood search operators, tabu tables, and amnesty criteria. This algorithm has been widely used in various applications, such as solving vehicle routing problems (Yao et al., 2023; Zhu et al., 2023). Tabu search is highly efficient because it uses a tabu table to prevent the search from becoming stuck in a local optimum and an amnesty criterion to ensure that the global optimum is not missed. Therefore, in this paper, a tabu search algorithm based on the neighborhood search operator is designed to solve this problem.

5.1 Search operators

Efficient search operators are crucial for heuristic algorithms to explore potential feasible solutions and escape local optima. Therefore, we incorporate four search operators, namely, one-point move, 2-exchange move, 2-opt, and point-arc exchange, into the tabu search algorithm (Wang et al., 2021b). In this paper, we define the tasks as points, and the task implementation process can be represented as a closed route. The operators modify the task route to search for neighboring solutions around the initial solutions. In the following sections, we will introduce each operator used in this study.

In traditional vehicle routing problems, the one-arc operator can be executed within one scheme or between two different schemes. However, searching within a scheme is inefficient for this problem because each task has a specific received time, and the execution order is based on the time sequence. If tasks within a scheme are swapped back and forth, the timing Constraint (7) would be violated, rendering the resulting scheme infeasible. Therefore, we only consider the execution of the one-arc operator between two schemes. Figure 1 gives a general description of the one-arc operator. A task arc \left(i,j\right) from one scheme and a task point k from another scheme are randomly selected. The task point k is removed from the second scheme, and it is removed into arc \left(i,j\right).

The two-opt operator can also be operated in one or two schemes. Similar to that of the one-arc operator, the efficiency of the two-opt operator inner scheme is also low due to the task timing Constraint (7). For two different schemes, the two-opt operator breaks the old implement chain from tasks a and c, as shown in Fig. 2. Then, tasks a and d are linked to construct a new scheme. Similarly, tasks c and b are linked to construct another new scheme. Compared to inner exchange with one scheme, the two-opt operator is more efficient for exploring neighborhood solutions.

The two-exchange operator occurs in two schemes. Typically, two tasks from two ships are randomly selected and exchanged to form two new schemes. Compared to the two-opt operator, the 2-exchange operator changes only one task in each ship scheme. Fig. 3 describes the 2-exchange operator. The first scheme has a task segment a\to b\to c, and the second scheme is ordered with i\to j\to k. Then, tasks b and j are exchanged, and two new schemes a\to j\to c and i\to b\to k are obtained.

Finally, the point-arc exchange operator is imported, as shown in Fig. 4. One task b is randomly selected in one scheme, and a task arc \left(i,j\right) is also selected from another scheme. Similar to the 2-exchange operator, the point-arc exchange operator exchanges the point with the arc in two schemes. Then, the newly generated schemes can be denoted as a\to i\to j\to c and h\to b\to k.

5.2 Improved Tabu search

The improved Tabu search algorithm consists of three components: the Tabu list, Tabu tenure, aspiration criterion, and search operator. The Tabu list is created to prevent the repeated search for local optimal solutions in each iteration. The tabu tenure refers to the length of the tabu list. When an element in the tabu list exceeds the tabu tenure, the list is shortened based on the first-come, first-leave strategy. A large tabu tenure would exclude a significant number of neighborhood solutions, while a small tabu tenure would result in repetitive searching. The aspiration criterion is activated when a new neighborhood solution can update the global optimal solution, even if the search operator is on the tabu list. The operator mentioned in the previous section is used to search for neighborhood solutions.

Algorithm 1 provides a concise overview of the algorithm framework. First, tasks are sorted based on their received times and assigned to ships with capacities greater than the task demands. If the completion time of the last task exceeds the specified working period, the ship will cease executing new tasks. This simple strategy ensures that a scheme satisfying the defined constraints in Formulas (5) to (16) is generated. Then, we initialize the programming parameters, including the iteration number H, tabu tenure L, and neighborhood size G. In each iteration, the proposed search operator is used to generate G neighborhood solutions based on the initial solution. Furthermore, the objective value of each feasible neighborhood solution is calculated and listed in ascending order. For the top of the ordered solution list, the corresponding search operator is added to the tabu list if it is not in the tabu list. Otherwise, the next solution would be substitution. The best solution is replaced once the tabu list is updated. Finally, the program terminates once the maximum iteration number is reached.

6 Case study

In this case study, we examine the actual task-tanker matching problem for China Petroleum, a company responsible for approximately 40% of China’s total refined oil products. It offers shipping services between an oil refinery in Liaoning Province and 36 depots in China’s coastal areas. Each year, the company handles more than 2,000 orders, including five types of refined oil products, totaling nearly 200 million tons. Given that all oil refineries are located at Dalian Port, we can simplify the shipping network to include a single refinery and 36 depots. Furthermore, the algorithm is implemented using the Python programming language. The experiments were conducted on a computer with 16 GB of RAM and an i7 14700 CPU. Additionally, the number of iterations, tabu tenure, and neighborhood solutions are set to 200, 10, and 50, respectively.

The company possesses a fleet of 16 self-owned tankers with capacities ranging from 5,400 tons to 50,000 tons. The number of outsourced tankers is dynamic and depends on the shipping market. To verify the proposed model and algorithm in terms of the optimal solution value and running time, ten instances are designed.

Table 1 presents an analysis of the demand-satisfied component of various types of tanks over a two-month period. The refined oil transport company operates both coastal shipping services and inland river businesses, specifically along the Yangtze River. The data demonstrate that the majority of demands are fulfilled using time-chartered tankers due to their lower charter prices. However, voyage-chartered tankers with low unit transport costs for long shipping distances are preferred for longer routes with high demand. For ports with moderate sailing distances, the shipping company considers utilizing a combination of self-owned, time-chartered, and voyage-chartered tankers.

To validate the effectiveness of the tabu search algorithm, we formulated a set of small-scale instances that can be solved by the solver. These instances include a range of 10 to 40 tasks and varying numbers of self-owned, time-chartered, and voyage-chartered tankers, ranging from 10 to 15, 6 to 8, and 4 to 20, respectively. Table 2 provides comprehensive information on the composition of the fleet for each instance, as well as the number of continuous variables, integer variables, and constraints in Model I.

The results obtained using both Gurobi and the tabu search for the small-scale instances are presented in Table 3. It should be noted that the computation results are based on Model I, which does not involve the sharing of time-chartered and voyage-chartered fleets. Table 3 displays the optimal solutions and running times for each instance, along with the discrepancy (gap) between the tabu search optimal solution and the solver’s optimal solution. The findings indicate that for very small instances, both Gurobi and the enhanced tabu search algorithm can identify the optimal solution, although the solver achieves shorter running times. However, as the instance size increases, the improved tabu search algorithm demonstrates greater efficiency by significantly reducing the running time compared to Gurobi. The discrepancy between the Gurobi and tabu searches remains within 1% of the optimal solution. Furthermore, as the problem size expands, the number of variables increases exponentially, causing the solver to be unable to find a feasible solution within 1,000 s when the number of tasks exceeds 40. Consequently, the improved tabu search algorithm becomes the only means of obtaining an optimal solution.

There are generally two shipping outsourcing companies in the shipping market: one operates time-chartered and one operates voyage-chartered tankers independently, while the other owns both types of tankers. In the second type of chartering company, customers have the flexibility to choose the type of chartering according to their demands. To examine the cost reduction proportion of flexible renting for customers, a set of large-scale instances is designed with the number of tasks ranging from 150 to 500 and the task received time ranging from one to three months. Table 4 presents the optimal solutions of Model I and Model II achieved through the tabu search algorithm under different fleet organizations. In Model II, fleets S_2 and S_3 do not differentiate between the types of renting, and they are considered outsourced tankers, allowing customers to make flexible selections. The results demonstrate that the flexible renting model significantly reduces costs for customers, ranging from 6.62% to 23.90%, with an average savings of 16.34%. Consequently, transportation companies can further mitigate customer transportation costs by integrating resources and enhancing the market competitiveness of shipping transportation. The shipping company in question provides services for 300 tasks, utilizing 12 self-owned ships, 8 time-chartered ships, and 15 voyage-chartered ships. The cost proportions for these three types of ships are 55.38%, 31.75%, and 12.87%, respectively. As the number of tasks increases to 400, the cost proportions shift to 49.45%, 28.54%, and 22.01%, respectively. Moreover, as the demand for tasks increases to 500, the cost proportions change to 48.75%, 28.03%, and 23.22%, respectively. Consequently, the shipping company must allocate more voyage-chartered ships as the number of tasks increases to minimize service delays. At the same time, as self-owned ships are operating at full capacity, the cost proportion for these ships decreases as the overall number of ships increases.

We investigated the task delay of the optimal solution over a two-month working period. In Fig. 5, the box plots indicate the gap between the task start implementation time and the ship calling origination port time. For instance, if the ship completes a period task at 7:00 a.m. but receives the next task at 3:00 p.m., there is an 8-h wait time before executing the task received. Conversely, if the ship recalls the origination port after completing the previous task later than the next task receiving time, there is a penalty cost for ship delay. In our proposed model, the delay incurs an additional penalty, as the refined oil company aims to fulfill customer demand as quickly as possible and fully utilize ship resources. The delay penalty is represented by the vacancy working time and capacity during the entire working period. As depicted in Fig. 5, most task delays exceed ship delays, indicating that the shipping company prioritizes providing efficient service to customers rather than solely maximizing ship utilization under the current optimization model.

The demand for refined oil at each depot depends on local consumption and market price fluctuations. In the transportation market, the price of ship chartering is influenced by international events. For example, the Red Sea incident led shipping companies to prefer risk reduction through ship chartering. To address uncertain demands and contract prices, a dynamic optimization method based on the time horizon can be employed. The given time period is divided into smaller time slots, allowing for re-optimization of fleet deployment based on the previous stage’s state, which includes ship location and remaining un-serviced tasks. By continually updating the ship fleet, the optimal solution for each sub-problem can be determined, leading to an approximate global optimal solution for the main problem. Furthermore, ship navigation is affected by various uncertain factors, such as ocean currents and wind speed. Uncertain weather conditions directly influence the sailing speed and time of self-owned and time-chartered ships. For voyage-chartered ships, uncertain factors may impact task execution efficiency, resulting in increased penalty costs. Through an investigation of uncertain data, the average sailing distance and time can be derived and expressed as a probability distribution, such as a normal or Poisson distribution. By utilizing the mean and variance of the probability distribution function, the proposed mathematical model can be reformulated as an expectation-based programming model.

The time-charter and voyage-charter costs are the primary factors influencing the optimal decision and cost. Therefore, Fig. 6 provides a sensitivity analysis of the optimal cost, showing how it is affected by the freight ratio of different charter types. In this analysis, the cost increases as the color changes from blue to red. It is evident that the optimal cost generally increases in relation to the costs of the time charter and voyage charter. It should be noted that as the rental price increases, the shipping company needs to reconsider the revenue generated from task orders. In the long-term, a shipping company may decide to invest more in self-owned tankers to manage fluctuations in the freight market.

7 Conclusions

With the overall growth of the industry, there has been a general increase in demand for refined oil products. These products are primarily provided through two aspects: import services, which are suitable for countries such as Japan and Republic of Korea, and domestic production. In China, both imported and domestically refined oil are available, with most domestic production originating from the north-east region of the country. The refined oil transport company possesses a self-owned fleet to cater to the demand for various destinations. However, the capacity of self-owned fleets is limited, prompting the need to consider renting additional ships to provide efficient service to customers. In the current outsourcing market, there are two types of rented ships: time-chartered ships and voyage-chartered ships. Time-chartered ships are rented for specific periods, such as two or three months, while voyage-chartered ships are rented for specific routes, with longer distances incurring higher unit rental costs.

This paper focuses on minimizing the total costs for a ship fleet that comprises both self-owned and rented ships while also meeting the given task demands. To achieve this, a heuristic algorithm based on tabu search is devised to obtain the optimal solution. The algorithm incorporates four search operators to efficiently explore the solution space. Through numerical experiments, we validate the performance of the proposed algorithm by comparing it with an exact algorithm in terms of the optimal solution and run time. Additionally, a sensitivity analysis of task implementation efficiency and rental costs is carried out. The results indicate that the self-owned fleet primarily serves long-distance routes, while shorter distances are allocated to rented ships. Furthermore, to avoid incurring extra penalty costs and to maintain the desired service levels, the shipping company typically chooses to delay tasks, allowing the ship to wait for its assigned task.

However, this paper has certain limitations that should be acknowledged. First, it is important to note that in reality, one ship usually calls multiple ports before returning to its origination point rather than just one port. This adds complexity to the problem as the size of the problem increases due to variations in ship route order and loading demands. Second, the current paper assumes that all ships depart from a single origin, typically an oil refinery. However, it is worth considering that oil supply companies are usually dispersed across a specific region, resulting in a distance gap compared to a single oil refinery. Considering the aforementioned limitations, we propose a more realistic refined oil transportation problem. This will involve jointly considering the factors mentioned above and devising heuristic or exact algorithms to effectively address them.

References

[1] Arslan A N, Papageorgiou D J, (2017). Bulk ship fleet renewal and deployment under uncertainty: A multi-stage stochastic programming approach. Transportation Research Part E, Logistics and Transportation Review, 97: 69–96

[2] Bellmore M, Bennington G, Lubore S, (1971). A multivehicle tanker scheduling problem. Transportation Science, 5( 1): 36–47

[3] Brown G G, Graves G W, Ronen D, (1987). Scheduling ocean transportation of crude oil. Management Science, 33( 3): 335–346

[4] Chen X, Lv S, Shang W L, Wu H, Xian J, Song C, (2024). Ship energy consumption analysis and carbon emission exploitation via spatial-temporal maritime data. Applied Energy, 360: 122886

[5] ChiF (2023). A high level of opening up will create good expectations for the all-round revitalization of northeast china. http://www.rmzxb.com.cn/c/2023-09-19/3411301.shtml, 2024-5-18 (in Chinese)

[6] Fagerholt K, Hvattum L M, Johnsen T A, Korsvik J E, (2013). Routing and scheduling in project shipping. Annals of Operations Research, 207( 1): 67–81

[7] He Y, Lin B, (2023). Is market power the cause of asymmetric pricing in china’s refined oil market. Energy Economics, 124: 106778

[8] Huang K, Liao F, (2023). A novel two-stage approach for energy-efficient timetabling for an urban rail transit network. Transportation Research Part E, Logistics and Transportation Review, 176: 103212

[9] Huang K, Wu J, Liao F, Sun H, He F, Gao Z, (2021). Incorporating multimodal coordination into timetabling optimization of the last trains in an urban railway network. Transportation Research Part C, Emerging Technologies, 124: 102889

[10] Kavussanos M G, (1996). Comparisons of volatility in the dry-cargo ship sector: Spot versus time charters, and smaller versus larger vessels. Journal of Transport Economics and Policy, 30: 67–82

[11] Köhn S, Thanopoulou H, (2011). A gam assessment of quality premia in the dry bulk time–charter market. Transportation Research Part E, Logistics and Transportation Review, 47( 5): 709–721

[12] Koza D F, Ropke S, Boleda Molas A, (2017). The liquefied natural gas infrastructure and tanker fleet sizing problem. Transportation Research Part E, Logistics and Transportation Review, 99: 96–114

[13] Li M, Fagerholt K, Schütz P, (2022). Stochastic tramp ship routing with speed optimization: Analyzing the impact of the northern sea route on CO₂ emissions. Annals of Operations Research, 08: 1–25

[14] LiaoningDaily (2023). Dalian has made every effort to promote the construction of northeast asia international shipping center and international logistics center. Avaible at the websife of the People’s Government of Liaoning Province (in Chinese)

[15] Lin D Y, Liu H Y, (2011). Combined ship allocation, routing and freight assignment in tramp shipping. Transportation Research Part E, Logistics and Transportation Review, 47( 4): 414–431

[16] Meng Q, Wang S, Lee C Y, (2015). A tailored branch-and-price approach for a joint tramp ship routing and bunkering problem. Transportation Research Part B: Methodological, 72: 1–19

[17] MordorIntelligence (2024). Market share of ship leasing industry source. Avaible at the websife of mordorintelligence

[18] Norstad I, Fagerholt K, Laporte G, (2011). Tramp ship routing and scheduling with speed optimization. Transportation Research Part C, Emerging Technologies, 19( 5): 853–865

[19] Pérez Lespier L, Long S, Shoberg T, Corns S, (2019). A model for the evaluation of environmental impact indicators for a sustainable maritime transportation systems. Frontiers of Engineering Management, 6( 3): 368–383

[20] Ronen D, (2011). The effect of oil price on containership speed and fleet size. Journal of the Operational Research Society, 62( 1): 211–216

[21] Santos A M P, Guedes Soares C, (2024). Cost optimization of shuttle tanker offloading operations. Ocean Engineering, 301: 117378

[22] Shang W L, Chen Y, Yu Q, Song X, Chen Y, Ma X, Chen X, Tan Z, Huang J, Ochieng W, (2023). Spatio-temporal analysis of carbon footprints for urban public transport systems based on smart card data. Applied Energy, 352: 121859

[23] Shao S, Tan Z, Liu Z, Shang W L, (2022). Balancing the GHG emissions and operational costs for a mixed fleet of electric buses and diesel buses. Applied Energy, 328: 120188

[24] Siddiqui A W, Verma M, (2017). A conditional value-at-risk based methodology to intermediate-term planning of crude oil tanker fleet. Computers & Industrial Engineering, 113: 405–418

[25] Tan Z, Shao S, Zhang X, Shang W L, (2023). Sustainable urban mobility: Flexible bus service network design in the post-pandemic era. Sustainable Cities and Society, 97: 104702

[26] Tsioumas V, Papadimitriou S, (2015). Excess returns in the spot market for bulk carriers. Maritime Economics & Logistics, 17( 4): 399–415

[27] Wan Z, Su Y, Li Z, Zhang X, Zhang Q, Chen J, (2023). Analysis of the impact of suez canal blockage on the global shipping network. Ocean and Coastal Management, 245: 106868

[28] Wang C, Xu C, (2015). Sailing speed optimization in voyage chartering ship considering different carbon emissions taxation. Computers & Industrial Engineering, 89: 108–115

[29] Wang H, Huang S, Liu Z, Zheng L, (2013). Optimal tanker chartering decisions with spot freight rate dynamics considerations. Transportation Research Part E, Logistics and Transportation Review, 51: 109–116

[30] Wang J, Zhou Y, Zhuang L, Shi L, Zhang S, (2022). Study on the critical factors and hot spots of crude oil tanker accidents. Ocean and Coastal Management, 217: 106010

[31] Wang S, Zhen L, Psaraftis H N, (2021a). Three potential benefits of the EU and IMO’s landmark efforts to monitor carbon dioxide emissions from shipping. Frontiers of Engineering Management, 8( 2): 310–311

[32] Wang X, Shao S, Tang J, (2021b). Iterative local-search heuristic for weighted vehicle routing problem. IEEE Transactions on Intelligent Transportation Systems, 22( 6): 3444–3454

[33] Wen M, Ropke S, Petersen H L, Larsen R, Madsen O B G, (2016). Full-shipload tramp ship routing and scheduling with variable speeds. Computers & Operations Research, 70: 1–8

[34] Xin X, Wang X, Tian X, Chen Z, Chen K, (2019). Green scheduling model of shuttle tanker fleet considering carbon tax and variable speed factor. Journal of Cleaner Production, 234: 1134–1143

[35] Yao F, Du Y, Li L, Xing L, Chen Y, (2023). General modeling and optimization technique for real-world earth observation satellite scheduling. Frontiers of Engineering Management, 10( 4): 695–709

[36] Ye Y, Liang S, Zhu Y, (2017). A mixed-integer linear programming-based scheduling model for refined-oil shipping. Computers & Chemical Engineering, 99: 106–116

[37] Zhang H, Zeng Q, (2015). A study of the relationships between the time charter and spot freight rates. Applied Economics, 47( 9): 955–965

[38] Zhao Y, Yang Z, (2018). Ship scheduling in the tramp spot market based on shipper’s choice behavior and the spatial and temporal shipping demand. Transportation Journal, 57( 3): 310–328

[39] Zhen L, Zhuge D, Murong L, Yan R, Wang S, (2019). Operation management of green ports and shipping networks: Overview and research opportunities. Frontiers of Engineering Management, 6( 2): 152–162

[40] Zhu W, Ao Z, Baldacci R, Qin H, Zhang Z, (2023). Enhanced solution representations for vehicle routing problems with split deliveries. Frontiers of Engineering Management, 10( 3): 483–498

RIGHTS & PERMISSIONS

Higher Education Press