Oil Platform Transport Problem (OPTP) is NP-hard

Abstract

The Oil Platform Transport Problem is considered as a combination/interlink of the two well-studied NP-Hard/NP-Complete problems: the Helicopter Routing Problem-HRP (a generalization of the Split Delivery Vehicle Routing Problem) and the one-dimensional Bin Packing Problem (BPP-1). The Oil Platform Transport Problem consist of to minimize the cost of carry resources, goods or people from one location (airport/platform) to another location (airport/platform) using helicopters with some restrictions as capacity and time windows. We provide the proof that this problem is NP-Hard/NP-Complete Problem by the polynomial transformation using formal languages between the Vehicle Routing Problem and the Oil Platform Transport Problem. We propose a new mathematical model to the Oil Platform Transport problem, and we present the parameters or characterization of Oil Platform Transport Problem instances of Mexican state-owned petroleum company (PEMEX). We generated 5 instance set, each instance set has 50 cases of randomly generated instances and real instances (with GIS data) of PEMEX Oil Platforms. We use the CPLEX solver to find the optimal cost of carrier resources, goods or people contains in the Oil Platform Transport Problem.

 The Oil Platform Transport Problem is considered as a combination/interlink of the two well-studied NP-Hard/NP-Complete problems: the Helicopter Routing Problem-HRP (a generalization of the Split Delivery Vehicle Routing Problem) and the one-dimensional Bin Packing Problem (BPP-1). The Oil Platform Transport Problem consist of to minimize the cost of carry resources, goods or people from one location (airport/platform) to another location (airport/platform) using helicopters with some restrictions as capacity and time windows. We provide the proof that this problem is NP-Hard/NP-Complete Problem by the polynomial transformation using formal languages between the Vehicle Routing Problem and the Oil Platform Transport Problem. We propose a new mathematical model to the Oil Platform Transport problem, and we present the parameters or characterization of Oil Platform Transport Problem instances of Mexican state-owned petroleum company (PEMEX). We generated 5 instance set, each instance set has 50 cases of randomly generated instances and real instances (with GIS data) of PEMEX Oil Platforms. We use the CPLEX solver to find the optimal cost of carrier resources, goods or people contains in the Oil Platform Transport Problem.