Oil Platform Transport Problem (OPTP) is NP-hard

  • Ocotlán Díaz-Parra Universidad Autónoma del Estado de Hidalgo
  • Jorge Alberto Ruiz Vanoye
  • Alejandro Fuentes-Penna UAEH
  • Beatriz Bernabe Loranca BUAP
  • Joaquín Pérez-Ortega CENIDET
  • Ricardo A. Barrera-Cámara Universidad Autónoma del Carmen
  • Daniel Vélez-Díaz UAEH
  • Nubia B. Pérez-Olguin UAEH
Keywords: Oil Platform, Transport Problem, Split Delivery Vehicle Routing Problem

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.

Published
2018-01-09
How to Cite
Díaz-Parra, O., Ruiz Vanoye, J., Fuentes-Penna, A., Bernabe Loranca, B., Pérez-Ortega, J., Barrera-Cámara, R., Vélez-Díaz, D., & Pérez-Olguin, N. (2018). Oil Platform Transport Problem (OPTP) is NP-hard. International Journal of Combinatorial Optimization Problems and Informatics, 8(3), 2-19. Retrieved from https://www.ijcopi.org/index.php/ojs/article/view/14
Section
Articles