1. INTRODUCTION
Currently, crude oil and natural gas are the most valuable commodities for international trade. For governments of countries with access to the sea, there is a great incentive to discover the crude oil and natural gas reserves in their offshore areas. This has led to the development of offshore drilling, which has now become a thriving multibilliondollar industry in several areas of the world. However, offshore drilling is much more expensive compared to conventional drilling on land. This paper uses optimization techniques to reduce the cost of offshore drilling.
In offshore crude oil production, drilling is conducted with flow lines connected to processing platforms (Murty, 2014). Today we are not limited to drilling a well vertically all the way to the bottom, but we can drill in a horizontal direction. Therefore, it is not necessary to move the rig to each well location in order to drill. It is quite possible to group (cluster) a set of wells to be drilled into one group, and then drill all of them one after the other with one rig fixed in a central location. Selecting the locations of different drilling rigs, and determining the set (cluster) of wells to be drilled by each rig, are complex optimization decisions that significantly impact the total drilling cost for a given offshore field.
This paper introduces new models and solution algorithms to optimize the locations of rigs and the assignment of wells to different rigs. The problem addressed here is unique because the drilling cost rates per mile are not equal for the different rigs. Therefore, the drilling cost of each well depends on both the distance to the drilling rig and the cost rate of that particular rig. We first consider the case in which the locations of the rigs are fixed, and then the case in which these locations of the rigs are considered as decision variables. New integer programming (IP) models are formulated, and an effective heuristic solution method is proposed. Computational comparisons are performed to evaluate the performance of the proposed heuristic solution method.
The remaining sections of this paper are organized as follows. The relevant literature is reviewed in Section 2. The specific offshore drilling problem is described, and its background, costs, and parameters are presented in Section 3. Case 1, assuming known and fixed rig locations, is discussed in Section 4. Optimum and heuristic solutions for Case 2, assuming unknown and variable rig locations, are discussed in Section 5. Finally, conclusions and suggestions for future research are given in Section 6.
2. LITERATURE REVIEW
In this section, we focus on previous work relevant to the optimum locations of offshore platforms (rigs) and the optimum allocation of the wells in the field to the different platforms. Sahebi et al. (2014) provide a widerscope literature review of optimization models and applications in crude oil supply chains, including facility location problems in offshore oil fields.
Traditional models assume that the locations of the wells to be drilled are given. Devine and Lesso (1972) develop an iterative twostage algorithm to minimize the cost of developing offshore fields. First, the wells are assigned to different platforms, and then the optimum locations of these platforms are determined. Then, these platform locations are fixed, and the wells are optimally reassigned to the platforms. Hansen et al. (1992) present a model for the optimal location and well assignment of offshore drilling platforms in Brazil. To minimize the total cost, an exact mixedinteger programming (MIP) solution and an approximate Tabu Search solution are proposed. Rosing (1994) discusses the practicality of several assumptions in the model of Hansen et al. (1992). Applying clustering, integer programming and network flow models, Kabadi et al. (1996) propose a twostage iterative approach to minimize the total drilling cost. First, locations for the drilling platforms are determined, and then each well is assigned to a given fixedlocation platform.
In several papers, the locations of the wells to be drilled are not given, but must be determined together with the locations of the drilling platforms. García et al. (2012) determine the locations of the wells and platforms locations and also the connections between the wells and the platforms. Rodrigues et al. (2016) present a binary linear programming (LP) model for minimizing the development costs of an offshore oil field. The model is used to determine the number, location and capacities of the platforms; the number and locations of the wells; and the interconnections between the platforms and wells. Cunha et al. (2016) combine cellular genetic algorithms and MonteCarlo sampling to optimize well locations in oil and gas fields. KarkevandiTalkhooncheh et al. (2018) integrate neurofuzzy inference with particle swarm optimization and genetic algorithms to determine the optimum placement of wells for drilling.
Several studies consider a widerscope problem, involving not only drilling locations, but also the optimal planning and scheduling of offshore oil field development and operations. Iyer et al. (1998) formulate a mixedinteger programming (MIP) model for this problem, and use a sequential decomposition algorithm to solve it. Van Den Heever and Grossmann (2000) extend the model of Iyer et al. (1998) by including exact nonlinear functions instead of linear approximations. Carvalho and Pinto (2006) extend the work of Iyer et al. (1998) by adding investment constraints and the effect of reservoir pressure on well production and revenues.
Other variations of offshore oil field optimization problems have been considered. Rosa and Ferreira Filho (2012) optimize the location of offshore drilling rigs, assuming the distances between the wells and the rigs affect not only pipeline length and cost, but also the wells productivity, and hence revenue. Rosa et al. (2018) use a mixedinteger LP (MILP) model to determine the number and locations of the platforms and their well assignments, as well as the pipeline network layout and the pipeline diameters. Sahebi and Nickel (2014) develop an MIP model that determines platform locations, allocates wells to platforms, and optimizes transportation and pipeline planning decisions.
Next, we describe a new problem for locating offshore oil drilling platforms and assigning wells to each one. The unique feature of the problem is that the cost of drilling each well depends not only on its distance to the platform, but also on the choice of platform used.
3. CLUSTERING PROBLEMS IN OFFSHORE DRILLING OF CRUDE OIL WELLS
3.1 Problem Description and Background
Clustering problems and their applications are discussed by Kabadi et al. (1996). This paper presents an important application of clustering models in offshore oil field development. Given the number and locations of the production well targets in an offshore oil field that need to be developed, the problem is to partition the set of production well targets into clusters or groups ranging up to 25, where each group is to be drilled by a single drilling platform (rig). If the rig locations are not already fixed, we also have to determine the best location to position the different rigs in order to minimize the total cost of developing the field. This is a clustering problem involving huge sums of money. The cost of drilling a production well depends on the distance of the well from the position of the rig and several other factors. Arriving at an exact cost is very difficult, thus it has been estimated by using information from past drilling jobs.
This section is based on a case study for developing an offshore oil field located 60 miles off the Eastern coast of Saudi Arabia. The offshore oil field where this study was done covers a 15×8 mile area located off the east coast of Saudi Arabia, and it has 90 potential target locations to be drilled. Currently, there are four jackedup drilling platforms of different types assigned to this field. Initially, however, the project development plans will consider these four rigs and an interest area of 5×5 miles around the existing rigs. In this 5×5mile area, there are 36 target well locations to be drilled, which are all within drilling distance to at least one of the 4 rigs in their present position. These 36 target well locations are numbered 1 to 36.
3.2 Costs and Parameters
In order to make the right decisions, we need to estimate all the relevant costs. Given four rigs and 36 wells, let:

i= well number, i = 1 to 36:

j = rig number, j = 1 to 4

L_{ij} = length (distance in miles) between the well at target location i and rig in position j

c_{ij} = cost (in $) of drilling the well at ith target location by rig in position j

D = maximum distance between the well and the drilling rig = 5 miles

w_{j} = maximum number of wells that rig j can drill.

R_{j} = daily rate of rig j, i.e. rig cost ($ per day)

W = total number of wells

G = total number of rigs
Drilling cost c_{ij} is estimated for feasible (i, j) pairs, i.e. pairs in which the distance L_{ij} does not exceed the maximum feasible distance D. Using data from past drilling jobs around this field, there are several different cost components that contribute to the cost c_{ij}. All of these components can be estimated as linear functions of L_{ij}. Based on past drilling data from the same fields, these various components are listed below for a general well of length L_{ij} from a feasible (i, j) pair.
(i): Daily working rates paid to the drilling contractor: in crude oil production, the daily rate is the amount that a drilling contractor is paid by the oil company for operating each rig per day. In offshore drilling, the daily rates of drilling rigs vary by their capability, and the market availability at the time the contract for the rig is signed. The four rigs on location in this field belong to different service companies, and have different rates, R_{j}, as shown in Table 1.
The number of days required to drill a single well is directly proportional to the distance between the rig and the well. From the available well drilling history, the number of days required to drill a well from a distance of L_{ij} miles is estimated to be given by the following equation:
(ii): Cementing: cement is used to hold the casing in place and to prevent fluid migration between subsurface formations. The price of cementing jobs varies based on additives used in mixing, well depth, well geometry, and rock characteristics in the field.
(iii): Drilling Fluid: drilling fluids, also referred to as drilling mud, are added to the wellbore to facilitate the drilling process by controlling the pressure, stabilizing exposed rock, providing buoyancy, and both cooling and lubricating while drilling. Their cost also depends on the type of fluids used and the rock characteristics.
(iv): Transportation, overhead, and other services: these expenses refer to the transportation of equipment, tools and personnel to and off the rig, spare parts and iron tubes used to run the completion; and the company’s drilling overhead such as office, personnel, insurance, fuel, water, logistics, third party vendor services, etc. The bigger the operation, the higher the overhead coast which is incurred and the more third party vendors that are involved.
Adding all the costs of: (ii) cementing, (iii) drilling fluid, and (iv) transportation, overhead, and other services, the drilling cost as a function of the distance L_{ij} is approximated by the following equation:
The approximate total cost of drilling, as a function of the distance L_{ij} in miles, is obtained by adding equations (1) and (2) as shown below:
In the following sections, we will consider two cases for the optimal drilling of wells by rigs in the offshore oil field. In the first case, we assume that the rigs are fixed in their current locations, and we simply divide the wells into four groups (clusters) and assign each group to one of the four rigs. In the second case, we assume that the rig locations are not fixed, and we determine the optimum rig locations along with the optimum assignment of wells to rigs.
4. CASE 1: FIXED RIG LOCATIONS
Here we consider the problem of drilling all the wells that can be drilled by rigs in their present positions, without moving them, at minimum total cost.
We will refer to the pair: (well at ith target well location and the jth rig in its present position), as the (i, j)pair, and refer to this pair as a feasible pair if the distance between them is within the maximum, L_{ij} < D. The objective of Case 1 is to find the optimum allocation of target wells to rigs fixed in the field, in order to drill at minimum total cost.
In this case, all 4 rigs are fixed in their present positions, and there are 36 target locations where wells have to be drilled. We want to allocate each of these target well locations to one of the rigs used to drill, without moving any rig from its present position. We define the set of feasible pairs as:
F = {(i, j) : i = 1 to 36, j = 1 to 4, and (i, j)} is a feasible pair, i.e. L_{ij} < D}
The decision variables in the model for this case are: x_{ij} defined only for (i, j) ϵ F, where:
${x}_{ij}=\left\{\begin{array}{c}1,\hspace{0.33em}if\hspace{0.33em}well\hspace{0.33em}i\hspace{0.33em}is\hspace{0.33em}drilled\hspace{0.33em}by\hspace{0.33em}rig\hspace{0.33em}j,\hspace{0.33em}(i,j)\hspace{0.33em}\u03f5\hspace{0.33em}F\\ 0,\hspace{0.33em}otherwise\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\end{array}\right.$
Then the objective function for this problem in this case is:
The above objective function is subject to constraints (5)(7) below. Constraint (5) allocates each well to only one rig. Constraint (6) limits the number of wells that can be drilled by each rig. Finally, constraint (7) imposes the binary value restrictions on the decision variables.
The model has F decision variables, and it is a linear minimumcost bipartite networkflow problem. Therefore if the constraint (7) is replaced by x_{ij} ≥ 0 for all (i, j) ϵ F, every basic feasible solution of the resulting model will be a 01 solution. Hence the model can be optimally solved by any software program designed for minimumcost networkflows problems, or by any linear programming (LP) software program. In this paper, all the optimum LP solutions were obtained by OpenSolver for Excel (Mason, 2012).
The input data for case 1 is shown in the tables in Appendix A, where W = 36 and G = 4. Figure 1 shows the locations of the 36 wells and the current locations of the 4 rigs. Table A1 shows the distances in miles between the four rigs (in their current locations) and the 36 target wells. Since all the distances are within the limit D = 5 miles, then each of the 36 wells can be drilled from any of the four rigs, and the set F includes all 4×36 x_{ij} variables defined by the range i = 1,…, 36 and j = 1, …, 4. Since the distances in Table A1 are given in miles, then equation (3) and the rates in Table 1 are used to compute the drilling costs shown in Table A2.
Constraint (6) expresses the requirement that the total number of wells allocated to each rig cannot exceed the rig’s handling capability (w_{j}). Since offshore rigs can handle a big number of wells that may go up to 50 wells, two scenarios were considered. In the first scenario, the 36 target wells are equally divided among the four existing rigs. This means that each rig is allowed to work on 9 wells, i.e. w_{j} = 9. In the second scenario, the capacity for each rig is assumed to be unlimited. This means that a single rig is capable of drilling all the 36 wells, i.e. w_{j} = 36.
4.1 Case 1a: Equal Number of Wells Per Rig
This scenario is obtained by setting w_{j} = 9 in constraint (6). It is equivalent to a transportation problem in which the number of sources (wells) is 36, the number of destinations (rigs) is 4, the capacity of each source is 1, and the demand of each destination is 9. The optimal solution by OpenSolver is given in Table 2, and it has a total cost of $862,994,588. The sum of distances between wells and their respective drilling rigs is equal to 46.61 miles.
4.2 Case 1b. Unlimited Number of Wells Per Rig
In this case, we either set w_{j} = 36 in constraint (6) or remove (6) completely from the model. The optimal solution shown in Table 3 has a total cost of $773,468,103 and a total distance of 42.76 miles between rigs and their assigned wells. The number of wells assigned to each rig ranges from 4 to 18. This assignment leads to a highly uneven distribution of workload among the four rigs. However, this assignment reduces the total drilling cost by $89,526,485, amounting to a savings of 10% compared to assigning an equal number of wells.
5. CASE 2: OPTIMUM RIG LOCATIONS
Now, we assume that we have the freedom to move the available rigs and position them at any location within the area of interest. We will still consider the same four rigs used in Case 1, which are different in type, characteristics, and in daily cost. In this case, however, we need to also determine the optimum locations of the rigs. The aim is to determine the best locations for the rigs to be positioned, along with the optimum allocation (assignment) of the targeted wells to the four rigs. The objective of this problem is to minimize the overall cost of drilling all of the 36 wells.
If we move a rig to one of the well locations to be drilled, then that particular target location will need only vertical drilling, without any lateral portion, which is an advantage. For this reason, we only consider the 36 target well locations to be drilled as possible sites to position the rigs. As in Case 1, we will use the index i to denote a general well location to be drilled, and use the index j to denote the position of the rig. Therefore, the set of possible sites to locate the rigs is the same as the set of well locations, numbered in the same order j = 1 to 36. Therefore, when the indices i and j are equal to the same number (between 1 to 36), they denote the same site for both the well and the rig.
5.1 Case 2 Optimum Solution
The decision variables in the model for this case are listed below. Among these, for i, j = 1 to 36 and k = 1 to 4, the decision variable x_{ijk} is defined only if the distance between sites i and j is < D, as assumed in Case 1.
$\begin{array}{l}{x}_{ijk}=\left\{\begin{array}{c}1,\hspace{0.33em}if\hspace{0.33em}well\hspace{0.33em}i\hspace{0.33em}is\hspace{0.33em}drilled\hspace{0.33em}from\hspace{0.33em}location\hspace{0.33em}j\hspace{0.33em}by\hspace{0.33em}rig\hspace{0.33em}number\hspace{0.33em}k\\ 0,\hspace{0.33em}otherwise\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\end{array}\right.\\ {y}_{jk}=\left\{\begin{array}{c}1,\hspace{0.33em}if\hspace{0.33em}site\hspace{0.33em}j\hspace{0.33em}is\hspace{0.33em}a\hspace{0.33em}location\hspace{0.33em}for\hspace{0.33em}rig\hspace{0.33em}number\hspace{0.33em}k\\ 0,\hspace{0.33em}otherwise\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\end{array}\right.\end{array}$
The objective function of this problem is to minimize the overall cost of drilling for all of the 36 wells. This objective is expressed as follows:
where
The objective function (8) is subject to the constraints listed below. Constraint (10) ensures that one drilling rig is assigned to each well. Constraint (11) guarantees that a well is connected to a drilling site only if a rig is located in that site. In these logical constraints, wk is a value that specifies the maximum number of wells that can be assigned to a single rig of type k. Constraint (12) allows no more than one rig to be located in any given site. Constraint (13) makes sure that one and only one rig (type) is used to drill each well. Constraint (14) specifies the total number of rigs. Finally, constraint (15) restricts the decision variables to binary values.
Table A3 in Appendix A shows the distances in miles between each pair of the 36 target wells. All the distances are within the limit D = 5 miles, thus all 4×36×36 x_{ijk} variables defined by the range (i = 1 to 36, j = 1 to 36, and k = 1 to 4) are feasible. Equation (9) and Table 1 are used to calculate the drilling costs c_{ij}k used in the objective function (8).
As in Case 1, two scenarios were considered. First, an equal number of wells was assigned to each rig (w_{k} = 9), and then an unlimited number of wells was allowed per rig (w_{k} = 36). Optimum solutions obtained for the two scenarios by the OpenSolver are discussed below.
5.1.1 Case 2a: Optimum Solution with Equal Number of Wells Per Rig
Imposing an equal number of wells (w_{k} = 9), the optimum solution for Case 2 is shown in Table 4. Rig numbers 1, 2, 3, and 4 are located on the sites of well numbers 23, 20, 32, and 3, respectively. The total cost of drilling is Z = $474,538,097 and the sum of the distances from all of the wells to their corresponding drilling rigs is 23.63 miles. Compared to the solution of Case 1a, the Case 2a solution reduces the total cost by 45% and the total distance by 49%, This is due to the movement of rigs to the optimum locations determined by the model.
5.1.2 Case 2b: Optimum Solution with Unlimited Number of Wells Per Rig
Removing the limits on the number of wells per rig, by using the value w_{k} = 32 in constraint (11), we obtain the optimum solution for Case 2 shown in Table 5. Rigs number 1, 2, 3, and 4 are located on the sites of wells number 32, 10, 3, and 23, respectively. The number of wells assigned to each of the four rigs ranges from 8 to 14. The total cost of drilling is Z = $452,962,073 and the sum of the distances from all of the wells to their corresponding rigs is 22.9 miles. In comparison to the solution of the same scenario in Case 1b, this solution reduces the total cost by 41% and the total distance by 46%.
5.2 Case 2 Heuristic Solution
Case 2 model, defined by (8)(15), has G×W×Wx_{ijk} variables and G×Wy_{jk} variables. The total number of binary variables is G×W×(W + 1), which is equal to 5,328 for the case application having G = 4 and W = 36. Although the model is linear, larger problem instances are difficult to solve optimally. In order to facilitate the solution for Case 2, a heuristic solution method is proposed, which is based on initially ignoring the differences in the daily rates between the G rigs. The heuristic solution proceeds in two stages as described below.
5.2.1 Case 2 Heuristic Solution: Stage 1
Solve the following simplified model, in which the different daily rates of the four rigs are removed from the cost function (3).
$\begin{array}{l}{x}_{ij}=\left\{\begin{array}{c}1,\hspace{0.33em}if\hspace{0.33em}well\hspace{0.33em}i\hspace{0.33em}is\hspace{0.33em}drilled\hspace{0.33em}from\hspace{0.33em}a\hspace{0.33em}rig\hspace{0.33em}in\hspace{0.33em}location\hspace{0.33em}j\hspace{1em}i=\text{1},\hspace{0.33em}\dots ,\hspace{0.33em}W,\\ 0,\hspace{0.33em}otherwise\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}j=\text{1},\hspace{0.33em}\dots ,\hspace{0.33em}W,\end{array}\right.\\ {y}_{jk}=\left\{\begin{array}{c}1,\hspace{0.33em}if\hspace{0.33em}site\hspace{0.33em}j\hspace{0.33em}is\hspace{0.33em}a\hspace{0.33em}rig\hspace{0.33em}location\\ 0,\hspace{0.33em}otherwise\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\end{array}\right.\hspace{1em}\hspace{1em}\hspace{0.33em}\hspace{0.33em}j=\text{1},\hspace{0.33em}\dots ,\hspace{0.33em}W\end{array}$
Objective function:
where
Constraints:
Constraint (18) allocates one drilling rig to each well, and constraint (19) limits the number of wells per rig to w. Constraint (20) specifies the number of rigs as 4, while constraint (21) restricts the decision variables to binary values.
5.2.2 Case 2: Heuristic Solution: Stage 2
The simplified model has only 1,332 variables, which is only onefourth of the number of variables used in the optimal model. In general, the simplified heuristic model for Case 2 has 1/G the number of variables in the original model, where G is the number of rigs. The optimal solution of the simplified model, which is much easier to obtain, specifies the locations of the four rigs, and allocates the 36 wells among these rigs. For each rig in location j, the solution also specifies the number of wells (NW_{j}) assigned to the rig, and the total distance (TD_{j}) to these wells. For a rig located in site j, this total distance is given by:
Now, calculate the values of ${C}_{j}^{2}=\left(77.616T{D}_{j}+10.08N{W}_{j}\right)$ for all rig locations and rank them in increasing order. Next, assign the different rigs to these locations in reverse order of rig costs and ${C}_{j}^{2}$ values. This means that the most expensive rig is assigned to the location with the least ${C}_{j}^{2}$, and the least expensive rig is assigned to the location with the greatest ${C}_{j}^{2}$.
Finally, determine the total cost Z by adding the rigs’ daily costs to Z^{1} as follows:
Now, given the distances in Table A3 and the costs in Table 1, the heuristic method is applied to the two scenarios in Case 2.
5.2.3 Case 2a. Heuristic Solution with Equal Number of Wells Per Rig
In scenario 1, assuming an equal number of wells per rig, we set the value (w = 9) in constraint (19) and solve the simplified model defined by (16)(21). The optimal solution of the simplified model is obtained by OpenSolver. The selected rig locations are the sites of wells numbered (3, 20, 23, and 32), with corresponding distances (7.4, 5.75, 5.31, and 5.17 miles), respectively. Assigning rigs in the reverse order of distance to cost, rig numbers 1, 2, 3, and 4 are assigned to the sites of wells numbered 23, 20, 32, and 3, respectively. The partial cost of drilling is Z^{1} = $89,145,111, and the sum of the distances from all of the wells to their corresponding rigs is 23.63 miles. Using equation (23), the total drilling cost is Z = 474,538,097. The final solution of the heuristic method for scenario a is shown in Table 6. This is the same as the optimum solution obtained in section 5.1.1.
5.2.4 Case 2b: Heuristic Solution with Unlimited Number of Wells Per Rig
In scenario b, we remove the limits on the number of wells per rig and set the value (w = 36) in constraint (19). Solving the simplified model defined by (16)(21), the optimal solution selects the sites of wells numbered (3, 20, 23, and 32) as rig locations, with corresponding distances (7.25, 4.5, 7.13, and 4.01 miles), respectively. Assigning rigs in the reverse order of distance to cost, rig numbers 1, 2, 3, and 4 are assigned to the sites of wells numbered 20, 3, 32, and 23, respectively. The number of wells assigned to each of the four rigs ranges from 8 to 11.
The partial cost of drilling is Z^{1} = $86,885,062, and the sum of the distances from all of the wells to their corresponding rigs is 22.89 miles. Using equation (23), the total drilling cost is given by Z = 458,294,439. The final solution of the heuristic method is shown in Table 7. This is only a 1% increase in total cost above the optimum solution obtained in section 5.1.2, whose total cost is Z = $452,962,073.
5.2.5 Case 2: Evaluation of the 2Stage Heuristic Solution
In the drilling location case study presented above, the optimum solution was relatively easy to find due to the manageable problem size (36 wells, and 4 rigs, and 5328 variables). For larger reallife problems, optimum solutions are too difficult, making it necessary to use the proposed twostage heuristic procedure. In order to confidently apply this procedure, its performance must be thoroughly evaluated. Therefore, extensive numerical experiments were conducted to determine the quality of the heuristic solutions.
As shown in Table 8, 30 test problems were solved by two methods: the optimum (Opt.) solution, and the twostage heuristic (Heur.) solution. These problem are divided into 3 sizes: 40, 50, and 60 wells, respectively corresponding to 6,560, 12,750, and 21,960 binary variables. Each size has 5 typea problems with equal number of wells per rig, and 5 typeb problems with unlimited number of wells per rig. Different problem sizes also differ in the number of wells W, number of rigs G, and the oil field size. For each problem, uniform distributions were used to generate different rig daily rates and different well locations within the field.
Table 8 shows that the heuristic procedure has an impressive nearoptimal performance. The heuristic solution’s costs were optimal in 9 problems, and differed from optimal on average by 0.38% and at most by 1.92%. The heuristic’s performance is better for typea problems, with an average cost increase of 0.12% above optimum. However, its performance for typeb problems is still quite impressive, with an average cost increase of 0.64% above optimum. These results confirm that the heuristic procedure is a practical and effective solution technique for largesize reallife drilling location problems.
6. DISCUSSION & CONCLUSIONS
In this paper, two practical cases of allocating wells to drilling rigs in an offshore oil field have been considered. In Case 1 the rig locations are assumed to be fixed, while in Case 2 the rig locations are assumed to be decision variables to be optimally determined. For each case, two different scenarios were considered, one with and another without a limit on the number of wells assigned to each rig. The unique feature of the problem is the difference in drilling costs per mile among the available rigs. This makes the cost of drilling each well dependent on both the distance to the rig and the cost per mile of the specific rig used for drilling.
New integer programming models have been formulated to represent the two cases for this location and allocation problem. In addition to the optimum solution by integer programming, a heuristic method has been developed to handle larger model sizes, especially for Case 2, where the rig locations are decision variables. Based on the practical case study and numerical experiments with 30 test problems, the heuristic method has proved its ability to produce nearoptimum solutions for Case 2. The heuristic solution’s cost exactly matched the optimum solution in many problems, and was only 0.4% above optimum on average.
There are several interesting directions for extending the work presented in this paper, especially by integrating the offshore drilling problem with other relevant problem in offshore oil fields. For example, the problem considered here can be integrated with the offshore transportation problem (Sahebi and Nickel, 2014), or with the oil field employee scheduling problem (Alfares, 2014).