# A Synchronous Optimization Model for Multiship Shuttle Tanker Fleet Design and Scheduling Considering Hard Time Window Constraint

Authors: Zhenfeng Jiang; Dongxu Chen; Zhongzhen Yang
Journal: Journal of Advanced Transportation
 (2018)

---

## Abstract

A Synchronous Optimization for Multiship Shuttle Tanker Fleet Design and Scheduling is solved in the context of development of floating production storage and offloading device (FPSO). In this paper, the shuttle tanker fleet scheduling problem is considered as a vehicle routing problem with hard time window constraints. A mixed integer programming model aiming at minimizing total transportation cost is proposed to model this problem. To solve this model, we propose an exact algorithm based on the column generation and perform numerical experiments. The experiment results show that the proposed model and algorithm can effectively solve the problem.


---

## Body

## 1. Introduction

The offshore crude oil collecting and distributing system is an important transitional transportation system connecting crude oil mining platforms (including drilling platforms and subsea oil production equipment) and land-based crude oil storage ports (“ports” for short), which is usually composed of several special oil tankers (called “shuttle oil tanker"). These oil tankers are responsible for transporting the crude oil produced by the mining platform to certain ports according to predesignated routes. In recent years, with the continuous increase in the crude oil exploitation at sea, the system is undergoing a profound transformation. The traditional “point-to-point, axle-and-spoke transportation” model is gradually shifting to the “multipoint berthing, cooperative transportation” model under the coordination of the floating production storage and offloading device (FPSO) and the shuttle tanker fleet. FPSO is a new type of offshore floating device integrating the functions of crude oil primary processing, storing, loading, and unloading. After being mined from the mining platform, crude oil will be transported to the FPSO via submarine pipelines; after being preliminary dehydrated and desalinated by FPSO, crude oil will be temporarily stored in its cargo tanks for shipment; then, it is necessary for the oil extractors to arrange the shuttle tankers to berth and unload crude oil before the oil tanks of FPSO are full and to transport crude oil to certain ports.The emergence of the FPSO not only enables the offshore crude oil production system to store crude oil within a certain capacity but also makes it possible to use larger shuttle tankers and berth multiply ports. But at the same time it makes the management and the use of the shuttle tanker fleet more complicated. At present, it is essential for crude oil extractors to carefully consider the design of the shuttle tanker fleet and the scheduling of the tankers when designing crude oil collecting and distributing system. It is necessary to reasonably determine the type and number of tankers that make up the fleet based on the transportation demand of each relevant FPSO and propose a reasonable berthing schedule for each tanker. If the design of the shuttle tanker fleet and the ship scheduling scheme are unreasonable, the operating costs will increase and the transportation efficiency will decline, and the FPSO's cargo tanks may be caused to be full, which will force the mining platform to stop production and lead to huge economic losses. Therefore, it has become an urgent problem for crude oil extractors to design the shuttle tanker fleet scientifically and allocate the transportation resources reasonably to minimize the total cost of crude oil transportation.In essence, the shuttle tanker fleet design and allocation problem should be categorized as the problem of ship scheduling. At present, the mainstream researches related to this issue can be roughly divided into three categories: the first category of researches is related to the optimization of ship scheduling problems, among which Jin et al. [1] established a dispatching model for feeder container ships to minimize total sailing cost of ships based on the traditional “axis and spokes" transport structure and also solved the model using the particle swarm algorithm. Jin et al. [2] established a container ship feeder transport scheduling model with the objective of maximizing the average loading rate to reasonably assign the ships that are used to carry out various voyage transportation tasks; Tang et al. [3] established a scheduling model for tramp ships based on changes in ship speed to maximize operating revenue. Yang [4] established an optimizing and dispatching model for feeder container ships to minimize the total transport costs considering the ship capacity constraints and liner time constraints, and solved the model using particle swarm algorithm. Tan et al. [5] proposed a joint ship schedule design and sailing speed optimization problem for a single inland shipping service by incorporating the effects of nonidentical stream flow speed and the uncertain dam transit time. They proposed a biobjective programming model for the proposed problem to simultaneously minimize the total bunker consumption and the ship round-trip time with service level constraints and analytically derived the Pareto optimal solutions of the ship sailing speeds and schedule by introducing the term of bulker times.The second category of researches is related to the optimization of ship dispatching in ports, among which Sun et al. [6] established a two-stage bilateral matching optimization model considering the match among supply, demand, and number of ships to propose a reasonable ship transportation scheduling scheme. Zhang et al. [7] established the optimal dispatching model to minimize total waiting time of ships on ports and proposed a simulated annealing multipopulation genetic algorithm for solving the model. He [8] established a multiobjective ship scheduling optimization model to optimize the density of ships entering and leaving ports.The third category of researches is related to fleet and route design and freight shipment, among which Jones and Zydiak [9] proposed a fleet design problem which considering replacement costs and maintenance costs, which is the first formal models for determining optimal steady-state fleet designs and gave a well-defined and consistent definition of optimality for steady-state fleet designs. They characterized optimal steady-state fleet designs by showing that all replacement groups must be equally sized. Fagerholt [10] studied the problem of deciding an optimal feet based on a three-phase solution method. Taylor et al. [11] discussed the design and development of regional truckload delivery fleets in support of random over-the-road delivery networks of continental scale and they proposed a detailed set of simulation models to evaluate various possible configurations of regional driving fleets. Zeng and Yang [12] proposed an integrated optimization model to improve the efficiency of coal shipping and designed an algorithm based on two-phase tabu search to solve the mode. Wiseman and Giat [13] considered load time by assuming that each leg in a route requires a day for loading and unloading freight while studying freight shipment.It can be found that most of the existing related researches assume that the fleet is homogenous (namely, the fleet consists of the same type of ships), and few researches consider the impact of transport time window constraints on the fleet design. However, in the problem proposed in this paper, first, the shuttle tanker fleet has a significant characteristic of nonhomogeneity, and the composition of the fleet has a direct and close relationship with the plan-making of each tanker transportation plan; second, the crude oil departure time of the FPSO has a hard time window constraint, and this constraint will influence the design of the fleet through the intrinsic link between the ship transportation plan and the fleet design. Therefore, the problem proposed in this paper will be more complex than the traditional ship scheduling problem and deserves further study.Based on the researches above, this paper abstracts the Shuttle Tanker Fleet Design and Scheduling Problem (SDSP) into a vehicle routing problem (VRP) considering different types of vehicles with hard time window constraints. Besides, this paper proposes an optimization model and solves the model by designing algorithm based on the column generation. The result of the solution can provide decision basis for crude oil extractors to design and dispatch shuttle tanker fleet.


## 2. Model Establishment

### 2.1. Problem Description

Compared with the traditional scheduling problems, the SDSP proposed in this paper has two key features:The first is the heterogeneity of the tankers. In SDSP, due to differences in the production and storage capabilities of each FPSO, it is obviously problematic to use the same type of oil tankers to build a fleet. The composition of the fleet should be determined according to the demand of the FPSO; besides, in practice, fleet of shuttle tankers has a wide source of tankers; it is not realistic to unity the type of these tankers. Therefore, in this paper, we assume that crude oil extractors can select suitable types and number of tankers from the alternative fleet to build a fleet and complete multivoyage transportation tasks.The second is the hard time window constraints. As mentioned above, due to the limited capacity of FPSO cargo tanks, once FPSO cargo tank is fully loaded, all mining platforms will stop production, which causes huge and unnecessary economic losses. Therefore, in this paper the shuttle tankers must berth and unload before the FPSO is fully loaded.In this paper, we assume that the observation period, the transport demand, and transport time windows of each FPSO are known. The SDSPM is proposed to optimize synchronously the types of shuttle tanker in the fleet, the number of shuttle tankers of each type, and the sailing path of each tanker during the observation period with the aim of minimizing operating cost of the shuttle tanker fleet and considering the FPSO transport hard time window constraint.


### 2.2. Model Assumptions

In SDSP, the following assumptions are made:( 1 ) During the observation period, the basic unit of the shuttle tanker's transport task is voyage, and 1 voyage refers to the process of an oil tanker starting from the port, berthing a number of FPSOs to extract crude oil, and finally returning to the port and unloading oil.( 2 ) During the observation period, each FPSO can only be berthed by one shuttle tanker, but one shuttle tanker can berth multiple FPSOs in succession.( 3 ) When the shuttle tanker berths one FPSO, the entire oil reserve of the shuttle tanker will be unloaded.( 4 ) The operating time (including loading time and unloading time) of each shuttle tanker on the same FPSO is the same [13].


### 2.3. Variables and Symbols Definitions

0: land-based crude oil storage port, which is the starting and ending point of each voyage.V -: set of nodes consisting of FPSO platforms.V = V - ∪ 0.S: set of shuttle tankers, the elements of S are denoted by s.K: set of voyages, the elements of K are denoted by k.T: the length of the observation period.M: a great positive number.t i j s: the sailing time of the tanker s fromi toj (∀i,j∈V).c s: the sailing cost of an oil tanker s per hour.z k s = { 1 , k   v o y a g e   i s   c o m p l e t e d   b y   t a n k e r   s; 0,otherwise}.x i j k = { 1 , v i s i t   i   a n d   j   a r e   v i s i t e d   s u c c e s s i v e l y i n  voyageki,j∈V;0,otherwise}.a i k: the moment when voyage k berths FPSO platform i.d i: the storage volume of oil of FPSO platformi.q s: Capacity of oil tanker s.l b i , u b i: the transport time window of the FPSO i, among which ubi and lbi are the earliest and the latest time of berthing FPSO, respectively.s i: operating time of shuttle tankers on FPSOi.


### 2.4. Optimization Model

According to the previous analysis of SDSP, the SDSPM (Shuttle tanker fleet Design and Scheduling Problem Model) proposed in this paper is shown as follows:(1)min:Z=∑i∈V∑j∈V∑s∈Stcszksijs∑k∈Kxijk(2)S.T.:∑j∈V-x0jk=1∀k∈K(3)∑i∈V-xi0k=1∀k∈K(4)∑i∈V-xijk=∑i∈V-xjik∀j∈V,k∈K(5)∑j∈V∑k∈Kxijk≥1∀i∈V(6)∑s∈Szks=1∀k∈K(7)∑i∈Vdi∑j∈Vxijk≤∑s∈Sqszks∀k∈K(8)aik+si+∑s∈Stijszks-ajk≤M1-xijk∀i,j∈V,k∈K(9)aik+si+ti0s×zks-a0k′≤M3-xi0k-zks-zk′s∀i∈V,k<k′∈V,s∈S(10)aik+si+∑s∈Sti0s×zks≤T∀i∈V,k∈K(11)lbi≤aik≤ubi∀i∈V,k∈K(12)xijk∈0,1∀i,j∈V,k∈K(13)zks∈0,1∀s∈S,k∈K(14)aik≥0∀i∈V,k∈KIn SDSPM, (1) is an objective function, aiming at minimizing the total operating costs of the shuttle tanker fleet. Equation (2) to (14) are constraints, among which (2) and (3) represent that each tanker must start from the port and return to the port during the observation period; (4) is flow constraint that guarantees that the flows are conservative; (5) represents that each FPSO should be berthed at least once in the observation period; (6) represents that each voyage needs one tanker to complete the transport task; (7) represents that the total amount of crude oil loaded on each voyage cannot exceed capacity of the tanker; (8) represents that if an oil tanker berths two FPSOs consecutively in the same voyage, the time of berthing must be continuous; (9) represents the time constraint of berthing each FPSO when the same tanker completes different voyage transport tasks; (10) represents that the tanker must return to the port within the observation period; (11) represents that when the tanker berths each FPSO, hard time window constrain should be met; (12) and (13) are 0-1 variable constraints; (14) represents that the time of berthing should be larger than or equal to 0.


## 2.1. Problem Description

Compared with the traditional scheduling problems, the SDSP proposed in this paper has two key features:The first is the heterogeneity of the tankers. In SDSP, due to differences in the production and storage capabilities of each FPSO, it is obviously problematic to use the same type of oil tankers to build a fleet. The composition of the fleet should be determined according to the demand of the FPSO; besides, in practice, fleet of shuttle tankers has a wide source of tankers; it is not realistic to unity the type of these tankers. Therefore, in this paper, we assume that crude oil extractors can select suitable types and number of tankers from the alternative fleet to build a fleet and complete multivoyage transportation tasks.The second is the hard time window constraints. As mentioned above, due to the limited capacity of FPSO cargo tanks, once FPSO cargo tank is fully loaded, all mining platforms will stop production, which causes huge and unnecessary economic losses. Therefore, in this paper the shuttle tankers must berth and unload before the FPSO is fully loaded.In this paper, we assume that the observation period, the transport demand, and transport time windows of each FPSO are known. The SDSPM is proposed to optimize synchronously the types of shuttle tanker in the fleet, the number of shuttle tankers of each type, and the sailing path of each tanker during the observation period with the aim of minimizing operating cost of the shuttle tanker fleet and considering the FPSO transport hard time window constraint.


## 2.2. Model Assumptions

In SDSP, the following assumptions are made:( 1 ) During the observation period, the basic unit of the shuttle tanker's transport task is voyage, and 1 voyage refers to the process of an oil tanker starting from the port, berthing a number of FPSOs to extract crude oil, and finally returning to the port and unloading oil.( 2 ) During the observation period, each FPSO can only be berthed by one shuttle tanker, but one shuttle tanker can berth multiple FPSOs in succession.( 3 ) When the shuttle tanker berths one FPSO, the entire oil reserve of the shuttle tanker will be unloaded.( 4 ) The operating time (including loading time and unloading time) of each shuttle tanker on the same FPSO is the same [13].


## 2.3. Variables and Symbols Definitions

0: land-based crude oil storage port, which is the starting and ending point of each voyage.V -: set of nodes consisting of FPSO platforms.V = V - ∪ 0.S: set of shuttle tankers, the elements of S are denoted by s.K: set of voyages, the elements of K are denoted by k.T: the length of the observation period.M: a great positive number.t i j s: the sailing time of the tanker s fromi toj (∀i,j∈V).c s: the sailing cost of an oil tanker s per hour.z k s = { 1 , k   v o y a g e   i s   c o m p l e t e d   b y   t a n k e r   s; 0,otherwise}.x i j k = { 1 , v i s i t   i   a n d   j   a r e   v i s i t e d   s u c c e s s i v e l y i n  voyageki,j∈V;0,otherwise}.a i k: the moment when voyage k berths FPSO platform i.d i: the storage volume of oil of FPSO platformi.q s: Capacity of oil tanker s.l b i , u b i: the transport time window of the FPSO i, among which ubi and lbi are the earliest and the latest time of berthing FPSO, respectively.s i: operating time of shuttle tankers on FPSOi.


## 2.4. Optimization Model

According to the previous analysis of SDSP, the SDSPM (Shuttle tanker fleet Design and Scheduling Problem Model) proposed in this paper is shown as follows:(1)min:Z=∑i∈V∑j∈V∑s∈Stcszksijs∑k∈Kxijk(2)S.T.:∑j∈V-x0jk=1∀k∈K(3)∑i∈V-xi0k=1∀k∈K(4)∑i∈V-xijk=∑i∈V-xjik∀j∈V,k∈K(5)∑j∈V∑k∈Kxijk≥1∀i∈V(6)∑s∈Szks=1∀k∈K(7)∑i∈Vdi∑j∈Vxijk≤∑s∈Sqszks∀k∈K(8)aik+si+∑s∈Stijszks-ajk≤M1-xijk∀i,j∈V,k∈K(9)aik+si+ti0s×zks-a0k′≤M3-xi0k-zks-zk′s∀i∈V,k<k′∈V,s∈S(10)aik+si+∑s∈Sti0s×zks≤T∀i∈V,k∈K(11)lbi≤aik≤ubi∀i∈V,k∈K(12)xijk∈0,1∀i,j∈V,k∈K(13)zks∈0,1∀s∈S,k∈K(14)aik≥0∀i∈V,k∈KIn SDSPM, (1) is an objective function, aiming at minimizing the total operating costs of the shuttle tanker fleet. Equation (2) to (14) are constraints, among which (2) and (3) represent that each tanker must start from the port and return to the port during the observation period; (4) is flow constraint that guarantees that the flows are conservative; (5) represents that each FPSO should be berthed at least once in the observation period; (6) represents that each voyage needs one tanker to complete the transport task; (7) represents that the total amount of crude oil loaded on each voyage cannot exceed capacity of the tanker; (8) represents that if an oil tanker berths two FPSOs consecutively in the same voyage, the time of berthing must be continuous; (9) represents the time constraint of berthing each FPSO when the same tanker completes different voyage transport tasks; (10) represents that the tanker must return to the port within the observation period; (11) represents that when the tanker berths each FPSO, hard time window constrain should be met; (12) and (13) are 0-1 variable constraints; (14) represents that the time of berthing should be larger than or equal to 0.


## 3. Algorithm Design

### 3.1. Basic Concepts and Processes

The SDSPM above is a large-scale nonlinear quadratic mixed integer programming model, which is proposed based on the classic VRP model considering vehicles of multiple types and hard time window constraints. However, in SDSPM we not only consider “the path optimization of each vehicle" (i.e., the sailing path of each shuttle tanker) but also consider the design of the fleet.At present, the following three methods are commonly used to solve this kind of models: the first is the traditional branch-and-bound method. This method has low efficiency and is incapable of solving many complex problems. The second is the heuristic algorithm based on evolutionary framework. The computational efficiency of this kind of algorithm is relatively high, but it cannot guarantee the global optimal solution. The robustness of this kind of algorithm is poor and the calculating result is unstable. The third is the column generation algorithm which has been widely concerned in recent years. The earliest column generation algorithm is proposed by Ford and Fulkerson [14] in the 1950s and the column generation algorithm has achieved great development in the last 10 years. Because the column generation algorithm has high computational efficiency and in theory can solve complicated models exactly, it is an ideal tool for solving large-scale nonlinear quadratic mixed integer programming. Therefore, this paper attempts to solve the SDSPM using the column generation algorithm.The key to using of column generation algorithms is the rational definition of “columns". The term “column" in this paper refers to a feasible sailing path for a shuttle tanker during the observation period, which may include multiple voyages. All voyages must berth the relevant FPSO under the conditions of meeting the time window constraints, but the total amount of crude oil carried by each voyage cannot exceed the capacity of the tanker. The process of generating “columns” refers to the process of creating a feasible sailing path for an oil tanker during the observation period. In the calculation process, the algorithm will create several such feasible “columns” in turn, and they will gradually construct a limited-scale solution space containing the optimal fleet scheduling scheme (including the fleet design scheme and the tanker sailing path), so as to compact scale of problem and solve the model exactly. In order to successfully apply the column generation algorithm, we also need to create two key models, the main model (MM) and the submodel (SM). The basic concepts and functions of the above two models can refer to Agarwal and Ergun [15], no more details here.In summary, this paper proposes a Shuttle Tanker Fleet Design and Scheduling Algorithm (SDSA) based on the idea of column generation to solve SDSPM. The basic calculation process is shown in Table1. Next, we will introduce the core steps of the algorithm in detail, namely, the main model and the submodel.Table 1
Basic process of SDSA.
Step 1 Initialize, create a feasible shuttle tank sailing pathp0 during one observation period, and create a set P={p0};  Step 2 Based on theP obtained in Step 1, solve the main model of the column generation algorithm and obtain the shadow price of each constraint in the main model.  Step 3 Based on the shadow price obtained inStep 2, solve the sub-model of the column generation algorithm, obtain a new feasible shuttle tank sailing path pi, and calculate the objective function value of the sub model. If the objective function value is negative, then add pito P and return toStep 1; if the objective function value is positive, then the solution of the main model is the optimal solution, and the algorithm terminates.


### 3.2. Main Model and Submodel

In the main model, the set of feasible sailing paths for shuttle tanker is denoted asP′, and its elements (i.e., the feasible sailing path for a single shuttle tanker; “single tanker feasible path” in short) are denoted asp. The decision variable of the main model is xp: if the schemep is used, xp=1; otherwise, xp=0. For the main model, this paper introduces the following variables and considers them as known. The rest of the symbols are the same as before:d p s = { 1 , s c h e m e   p   u s e s   t a n k e r   s ; 0 , o t h e r w i s e }.d p s = 1 , s c h e m e   p   r e q u i r e s   t a n k e r s   t o   b e r t h   F P S O  p l a t f o r m   i ; 0 , o t h e r w i s e.t p: total sailing time for schemep.The mathematical equation of the main model (SDSA-MM) is shown in (15)-(18). (15)min:Z1=∑p∈P′∑s∈Scsdpstpxp(16)S.T.:∑p∈P′aipxp≥1∀i∈V(17)∑p∈P′dpsxp≤1∀s∈S(18)xp∈0,1∀p∈P′Equation (15) is the objective function, the aim of which is the same as that of (1) aiming at minimizing the total operating costs of the shuttle tanker fleet. Equations (16)-(18) are constraints, among which (16) is used to ensure that every FPSO is will be berthed at least once during the observation period; (17) is used to ensure that each shuttle tanker can only be allocated to a single feasible path. SDSA-MM is a linear integer programming model that can be directly solved using CPLEX.The function of the submodel is generating a new “column" based on the gradient information given by the main model and at the same time determining whether the SDSA meets the termination condition, that is, whether the objective function value of the submodel is positive or not. If the termination condition is not met, the newly generated columns are added to setP′ and the main model is solved again. For the submodel, in this paper the following variables are introduced and considered as known, and the rest of the symbols are the same as before:z s = { 1 , t a n k e r   s   c a r r y   o u t   t r a n s p o r t   p l a n ; 0 , o t h e r w i s e }.D P i 16: the shadow price of (16).D P s 17: the shadow price of (17).The mathematical equation of submodel (SDSA-SM) is shown in (19)-(25).[SDSA-SM]:(19)min:Z2=∑i,j∈Vtijscszs∑k∈Kxijk-DPi16∑j∈Vk∈Kxijk-DPs17zs(20)S.T.:∑szs=1(21)∑i∈Vdi∑i∈Vxijk≤∑s∈Sqszs∀k∈K(22)aik+si+∑s∈Stijszs-ajk≤M1-xijk∀i,j∈V,k∈K(23)aik+si+∑s∈Sti0szs-a0k′≤M1-xi0k∀i∈V,k<k′∈K(24)aik+si+∑s∈Sti0szs≤T∀i∈V,k<k′∈K(25)zs∈0,1∀s∈SThe constraints of SDSA-SM are similar to that of SDSPM, only deleting or rewriting the content related to multiple shuttle tankers. Specifically, SDSA-SM deletes the constraint that each FPSO must be berthed, which is (5). Equations (6)-(10) are changed into (20)-(24), and zks was replaced by zs.Equation (19) is the testing number of feasible path of a single ship's in SDSA-MM. The definition of (20)-(24) is basically the same as that of (6)-(10), only adjusting the constraint range from the previous fleet to the single shuttle tanker in order to ensure the feasibility of the feasible path of the single ship. Equation (25) is a (0-1) variable constraint. Because SDSA-SM is the same as the path planning problem proposed by Kobayashi and Kubo [16], the dynamic programming labeling method proposed by them can be used to solve the problem efficiently.


## 3.1. Basic Concepts and Processes

The SDSPM above is a large-scale nonlinear quadratic mixed integer programming model, which is proposed based on the classic VRP model considering vehicles of multiple types and hard time window constraints. However, in SDSPM we not only consider “the path optimization of each vehicle" (i.e., the sailing path of each shuttle tanker) but also consider the design of the fleet.At present, the following three methods are commonly used to solve this kind of models: the first is the traditional branch-and-bound method. This method has low efficiency and is incapable of solving many complex problems. The second is the heuristic algorithm based on evolutionary framework. The computational efficiency of this kind of algorithm is relatively high, but it cannot guarantee the global optimal solution. The robustness of this kind of algorithm is poor and the calculating result is unstable. The third is the column generation algorithm which has been widely concerned in recent years. The earliest column generation algorithm is proposed by Ford and Fulkerson [14] in the 1950s and the column generation algorithm has achieved great development in the last 10 years. Because the column generation algorithm has high computational efficiency and in theory can solve complicated models exactly, it is an ideal tool for solving large-scale nonlinear quadratic mixed integer programming. Therefore, this paper attempts to solve the SDSPM using the column generation algorithm.The key to using of column generation algorithms is the rational definition of “columns". The term “column" in this paper refers to a feasible sailing path for a shuttle tanker during the observation period, which may include multiple voyages. All voyages must berth the relevant FPSO under the conditions of meeting the time window constraints, but the total amount of crude oil carried by each voyage cannot exceed the capacity of the tanker. The process of generating “columns” refers to the process of creating a feasible sailing path for an oil tanker during the observation period. In the calculation process, the algorithm will create several such feasible “columns” in turn, and they will gradually construct a limited-scale solution space containing the optimal fleet scheduling scheme (including the fleet design scheme and the tanker sailing path), so as to compact scale of problem and solve the model exactly. In order to successfully apply the column generation algorithm, we also need to create two key models, the main model (MM) and the submodel (SM). The basic concepts and functions of the above two models can refer to Agarwal and Ergun [15], no more details here.In summary, this paper proposes a Shuttle Tanker Fleet Design and Scheduling Algorithm (SDSA) based on the idea of column generation to solve SDSPM. The basic calculation process is shown in Table1. Next, we will introduce the core steps of the algorithm in detail, namely, the main model and the submodel.Table 1
Basic process of SDSA.
Step 1 Initialize, create a feasible shuttle tank sailing pathp0 during one observation period, and create a set P={p0};  Step 2 Based on theP obtained in Step 1, solve the main model of the column generation algorithm and obtain the shadow price of each constraint in the main model.  Step 3 Based on the shadow price obtained inStep 2, solve the sub-model of the column generation algorithm, obtain a new feasible shuttle tank sailing path pi, and calculate the objective function value of the sub model. If the objective function value is negative, then add pito P and return toStep 1; if the objective function value is positive, then the solution of the main model is the optimal solution, and the algorithm terminates.


## 3.2. Main Model and Submodel

In the main model, the set of feasible sailing paths for shuttle tanker is denoted asP′, and its elements (i.e., the feasible sailing path for a single shuttle tanker; “single tanker feasible path” in short) are denoted asp. The decision variable of the main model is xp: if the schemep is used, xp=1; otherwise, xp=0. For the main model, this paper introduces the following variables and considers them as known. The rest of the symbols are the same as before:d p s = { 1 , s c h e m e   p   u s e s   t a n k e r   s ; 0 , o t h e r w i s e }.d p s = 1 , s c h e m e   p   r e q u i r e s   t a n k e r s   t o   b e r t h   F P S O  p l a t f o r m   i ; 0 , o t h e r w i s e.t p: total sailing time for schemep.The mathematical equation of the main model (SDSA-MM) is shown in (15)-(18). (15)min:Z1=∑p∈P′∑s∈Scsdpstpxp(16)S.T.:∑p∈P′aipxp≥1∀i∈V(17)∑p∈P′dpsxp≤1∀s∈S(18)xp∈0,1∀p∈P′Equation (15) is the objective function, the aim of which is the same as that of (1) aiming at minimizing the total operating costs of the shuttle tanker fleet. Equations (16)-(18) are constraints, among which (16) is used to ensure that every FPSO is will be berthed at least once during the observation period; (17) is used to ensure that each shuttle tanker can only be allocated to a single feasible path. SDSA-MM is a linear integer programming model that can be directly solved using CPLEX.The function of the submodel is generating a new “column" based on the gradient information given by the main model and at the same time determining whether the SDSA meets the termination condition, that is, whether the objective function value of the submodel is positive or not. If the termination condition is not met, the newly generated columns are added to setP′ and the main model is solved again. For the submodel, in this paper the following variables are introduced and considered as known, and the rest of the symbols are the same as before:z s = { 1 , t a n k e r   s   c a r r y   o u t   t r a n s p o r t   p l a n ; 0 , o t h e r w i s e }.D P i 16: the shadow price of (16).D P s 17: the shadow price of (17).The mathematical equation of submodel (SDSA-SM) is shown in (19)-(25).[SDSA-SM]:(19)min:Z2=∑i,j∈Vtijscszs∑k∈Kxijk-DPi16∑j∈Vk∈Kxijk-DPs17zs(20)S.T.:∑szs=1(21)∑i∈Vdi∑i∈Vxijk≤∑s∈Sqszs∀k∈K(22)aik+si+∑s∈Stijszs-ajk≤M1-xijk∀i,j∈V,k∈K(23)aik+si+∑s∈Sti0szs-a0k′≤M1-xi0k∀i∈V,k<k′∈K(24)aik+si+∑s∈Sti0szs≤T∀i∈V,k<k′∈K(25)zs∈0,1∀s∈SThe constraints of SDSA-SM are similar to that of SDSPM, only deleting or rewriting the content related to multiple shuttle tankers. Specifically, SDSA-SM deletes the constraint that each FPSO must be berthed, which is (5). Equations (6)-(10) are changed into (20)-(24), and zks was replaced by zs.Equation (19) is the testing number of feasible path of a single ship's in SDSA-MM. The definition of (20)-(24) is basically the same as that of (6)-(10), only adjusting the constraint range from the previous fleet to the single shuttle tanker in order to ensure the feasibility of the feasible path of the single ship. Equation (25) is a (0-1) variable constraint. Because SDSA-SM is the same as the path planning problem proposed by Kobayashi and Kubo [16], the dynamic programming labeling method proposed by them can be used to solve the problem efficiently.


## 4. Case Study

Based on the public data of a certain oil company, the results are calculated using C#.net and CPLEX. The numerical experiment consists of two parts: the first part focuses on the effectiveness of SDSA; the second part solves a practical problem to verify the rationality of SDSPM and SDSA.


### 4.1. Needed Data

Thanks to the prosperity of ship charter market, a large amount of ship information is public. Therefore, we can directly search the needed data related to the oil storage capacity of FPSO cargo tank, crude oil production speed, and the tank capacity, speed, operating cost, and rent of the shuttle tankers in the relevant websites [17]. Based on the data above, this paper designs experimental cases by generating the position information of each FPSO randomly. The sailing distance between the FPSOs is generated randomly between the minimum value, which is Euclidean distance, and the maximum value, which is the maximal distance meets the triangular inequality constrain. This is because sea sailing paths cannot be not entirely straight; sometimes it is necessary to consider the channels, ocean currents, and other practical conditions. Additionally, we set the length of the observation period as 30 days.


### 4.2. Analysis of Algorithm Efficiency

In this paper, two methods are used to solve SDSPM. First, CPLEX is used to solve the problem directly [18]. CPLEX is working based on branch and cut algorithm when computing. While calculating, in order to help CPLEX solve SDSPM more efficiently, the great positive number M should be set as a tight value. To get a tight M, we substitute different value of each 0-1 variables xi0k,zks,zk′s,xijk into (8) and (9) and discuss the possible value of M that can ensure both (8) and (9) are valid. Finally, the tight M is set to the length of the observation period in this paper, which is 30; second, SDSA is proposed to solve the problem. In order to clearly explain the efficiency of SDSA, we collect data of each calculation process, including the times of integer branches, time of solving the main model using CPLEX, the cycles of generating columns, the time of solving the submodel using the dynamic programming (namely, the pricing problem), and so on. The results of comparing the 2 methods mentioned above are shown in Table 2.Table 2
Information of algorithm substep efficiency.
Number of FPSO CPLEX SDSA Number of branches Average time Cycles MM SM Total of columns time time 15 4 0.53s 3 0.06s 0.02s 22 20 8 4.81s 9 0.08s 0.48s 68 25 13 7.52s 26 0.09s 1.16s 113 30 21 9.23s 48 0.11s 1.64s 264 35 26 18.80s 74 0.12s 2.19s 684 40 32 38.78s 92 0.14s 2.83s 1079 50 47 320.42s 146 0.19s 4.78s 1233 100 98 >1h 300 0.34s 12.6s 2563According to Table2, it can be found that, compared with the traditional branch-and-bound algorithm, SDSA can effectively solve the hybrid integer programming model SDSPM proposed for solving the shuttle tanker scheduling problem. Additionally, in the process of calculating SDSA, the calculating time increases with the increase of the problem scale, especially the calculating time of solving submodels increases fastest with of increase of the problem scale..


### 4.3. Solution Analysis

In the study case, this paper refers to the data in the Bohai Sea area of one offshore oil company and randomly generates the positions of the FPSOs and the existing volume of oil in the Bohai Sea area. It is assumed that the company has one port and seven FPSOs in the Bohai Sea area. The distribution of ports and FPSOs are shown in Figure1.Figure 1
The distribution of ports and FPSOs in the research area.This paper assumes that there are four types of alternative shuttle tankers (including A, B, C, and D), and the number of each type of shuttle tankers is sufficient to meet the demand of forming the fleet. The basic operating parameters of all types of shuttle tankers are shown in Table3.Table 3
Basic operating parameters of shuttle tankers.
Types of Shuttle tankers Sailing speed(knot) Rated capacity(wm 3 ) Sailing cost(USD/NM) A 17 2 280 B 16 5 374 C 15 7 444 D 14 9 483In terms of experimental design, to demonstrate the validity of the model, this paper compares and analyzes the operating costs of the two schemes.Scheme 1 is the traditional “point-to-point, hub-and-spoke" shuttle tanker scheduling scheme, which is the scheme that the companies currently adopt; namely, the company should allocate one shuttle tanker for each FPSO, and the tanker should meet needs of the FPSO be responsible for the oil transportation and oil storage of the FPSO; Scheme 2 is the “multipoint berthing” shuttle tanker scheduling scheme proposed in this paper; namely, the company is responsible for forming the shuttle tanker fleet and proposing transportation plan of each tanker, in which each shuttle tanker can berth several FPSOs. The operating results of the above two schemes are shown as follows.The fleet design and operating plan in Scheme 1 are shown in Table4. Under this scheme. suitable ship types, sailing path and the number of voyages during the observation period are designed for each FPSO according to the transportation demand. The calculating result shows that the total operating cost of the fleet during the observation period is 8.01×105 USD.Table 4
Transportation schedule of scheme 1.
FPSO NO. Tanker types Shuttle tanker sailing path Voyages within observation period 1 B 0-1-0 1 2 B 0-2-0 1 3 B 0-3-0 1 4 A 0-4-0 1 5 A 0-5-0 1 6 A 0-6-0 1 7 B 0-7-0 1The fleet design and operating plan in Scheme 2 are shown in Table5. According to the calculating results, the company needs to configure 3 large tankers, of which 2 are tankers of C-type and 1 is tanker of D-type. The total operating costs of fleet during the observation period for Scheme 2 is 5.56×105 USD.Table 5
Transportation schedule of Scheme 2.
Ship No. Selected Ship Type Voyage Sailing Path 1 C 1 0-1-2-0 2 0-1-2-0 3 0-1-2-0  2 C 1 0-3-4-5-0 2 0-3-4-5-0  3 D 1 0-6-7-0 2 0-6-7-0 3 0-3-4-5-6-7-0By comparing Scheme 1 and Scheme 2, it can be found that the operating cost of Scheme 2 is lower. This is because although the tankers used in Scheme 1 are relatively smaller, the number of tankers used is relatively larger, and the idleness of the tankers in Scheme 1 is more serious during the observation period. The sailing time for some tankers is less than 60% of the total time of the observation period. In contrast, Scheme 2 adopts a small number of large tankers and the use of ships is more reasonable. Therefore, the idle time of ships is relatively short and the overall operating cost is lower. The calculating results above are consistent with our expectations. The results show that the SDSPM and SDSA proposed in this paper are effective in optimizing the allocation of transportation resources and improving the service level of shuttle tankers.


## 4.1. Needed Data

Thanks to the prosperity of ship charter market, a large amount of ship information is public. Therefore, we can directly search the needed data related to the oil storage capacity of FPSO cargo tank, crude oil production speed, and the tank capacity, speed, operating cost, and rent of the shuttle tankers in the relevant websites [17]. Based on the data above, this paper designs experimental cases by generating the position information of each FPSO randomly. The sailing distance between the FPSOs is generated randomly between the minimum value, which is Euclidean distance, and the maximum value, which is the maximal distance meets the triangular inequality constrain. This is because sea sailing paths cannot be not entirely straight; sometimes it is necessary to consider the channels, ocean currents, and other practical conditions. Additionally, we set the length of the observation period as 30 days.


## 4.2. Analysis of Algorithm Efficiency

In this paper, two methods are used to solve SDSPM. First, CPLEX is used to solve the problem directly [18]. CPLEX is working based on branch and cut algorithm when computing. While calculating, in order to help CPLEX solve SDSPM more efficiently, the great positive number M should be set as a tight value. To get a tight M, we substitute different value of each 0-1 variables xi0k,zks,zk′s,xijk into (8) and (9) and discuss the possible value of M that can ensure both (8) and (9) are valid. Finally, the tight M is set to the length of the observation period in this paper, which is 30; second, SDSA is proposed to solve the problem. In order to clearly explain the efficiency of SDSA, we collect data of each calculation process, including the times of integer branches, time of solving the main model using CPLEX, the cycles of generating columns, the time of solving the submodel using the dynamic programming (namely, the pricing problem), and so on. The results of comparing the 2 methods mentioned above are shown in Table 2.Table 2
Information of algorithm substep efficiency.
Number of FPSO CPLEX SDSA Number of branches Average time Cycles MM SM Total of columns time time 15 4 0.53s 3 0.06s 0.02s 22 20 8 4.81s 9 0.08s 0.48s 68 25 13 7.52s 26 0.09s 1.16s 113 30 21 9.23s 48 0.11s 1.64s 264 35 26 18.80s 74 0.12s 2.19s 684 40 32 38.78s 92 0.14s 2.83s 1079 50 47 320.42s 146 0.19s 4.78s 1233 100 98 >1h 300 0.34s 12.6s 2563According to Table2, it can be found that, compared with the traditional branch-and-bound algorithm, SDSA can effectively solve the hybrid integer programming model SDSPM proposed for solving the shuttle tanker scheduling problem. Additionally, in the process of calculating SDSA, the calculating time increases with the increase of the problem scale, especially the calculating time of solving submodels increases fastest with of increase of the problem scale..


## 4.3. Solution Analysis

In the study case, this paper refers to the data in the Bohai Sea area of one offshore oil company and randomly generates the positions of the FPSOs and the existing volume of oil in the Bohai Sea area. It is assumed that the company has one port and seven FPSOs in the Bohai Sea area. The distribution of ports and FPSOs are shown in Figure1.Figure 1
The distribution of ports and FPSOs in the research area.This paper assumes that there are four types of alternative shuttle tankers (including A, B, C, and D), and the number of each type of shuttle tankers is sufficient to meet the demand of forming the fleet. The basic operating parameters of all types of shuttle tankers are shown in Table3.Table 3
Basic operating parameters of shuttle tankers.
Types of Shuttle tankers Sailing speed(knot) Rated capacity(wm 3 ) Sailing cost(USD/NM) A 17 2 280 B 16 5 374 C 15 7 444 D 14 9 483In terms of experimental design, to demonstrate the validity of the model, this paper compares and analyzes the operating costs of the two schemes.Scheme 1 is the traditional “point-to-point, hub-and-spoke" shuttle tanker scheduling scheme, which is the scheme that the companies currently adopt; namely, the company should allocate one shuttle tanker for each FPSO, and the tanker should meet needs of the FPSO be responsible for the oil transportation and oil storage of the FPSO; Scheme 2 is the “multipoint berthing” shuttle tanker scheduling scheme proposed in this paper; namely, the company is responsible for forming the shuttle tanker fleet and proposing transportation plan of each tanker, in which each shuttle tanker can berth several FPSOs. The operating results of the above two schemes are shown as follows.The fleet design and operating plan in Scheme 1 are shown in Table4. Under this scheme. suitable ship types, sailing path and the number of voyages during the observation period are designed for each FPSO according to the transportation demand. The calculating result shows that the total operating cost of the fleet during the observation period is 8.01×105 USD.Table 4
Transportation schedule of scheme 1.
FPSO NO. Tanker types Shuttle tanker sailing path Voyages within observation period 1 B 0-1-0 1 2 B 0-2-0 1 3 B 0-3-0 1 4 A 0-4-0 1 5 A 0-5-0 1 6 A 0-6-0 1 7 B 0-7-0 1The fleet design and operating plan in Scheme 2 are shown in Table5. According to the calculating results, the company needs to configure 3 large tankers, of which 2 are tankers of C-type and 1 is tanker of D-type. The total operating costs of fleet during the observation period for Scheme 2 is 5.56×105 USD.Table 5
Transportation schedule of Scheme 2.
Ship No. Selected Ship Type Voyage Sailing Path 1 C 1 0-1-2-0 2 0-1-2-0 3 0-1-2-0  2 C 1 0-3-4-5-0 2 0-3-4-5-0  3 D 1 0-6-7-0 2 0-6-7-0 3 0-3-4-5-6-7-0By comparing Scheme 1 and Scheme 2, it can be found that the operating cost of Scheme 2 is lower. This is because although the tankers used in Scheme 1 are relatively smaller, the number of tankers used is relatively larger, and the idleness of the tankers in Scheme 1 is more serious during the observation period. The sailing time for some tankers is less than 60% of the total time of the observation period. In contrast, Scheme 2 adopts a small number of large tankers and the use of ships is more reasonable. Therefore, the idle time of ships is relatively short and the overall operating cost is lower. The calculating results above are consistent with our expectations. The results show that the SDSPM and SDSA proposed in this paper are effective in optimizing the allocation of transportation resources and improving the service level of shuttle tankers.


## 5. Conclusion

This paper studied the offshore shuttle tanker fleets design and scheduling problem and proposed a nonlinear quadratic mixed integer programming model. To solve the model, we designed an exact solution algorithm based on the idea of column generation algorithm. In the numerical experiment, first we analyzed the reliability of the algorithm and the results show that the algorithm proposed in this paper is superior to CPLEX in terms of computational efficiency. Next, we solved a practical shuttle tanker fleet design and scheduling optimization problem using the model and algorithm proposed in this paper. The results are consistent with our expectations. In addition, we have to admit that there is still much room for further improvement in this paper. For example, we assume the operating time of each shuttle tanker on the same FPSO is the same and we have not considered the operating efficiency and capacity of different tankers, which can be one of the directions for further research.



---

*Source: 1904340-2018-11-04.xml*