ICT-UNPA-30-2011 ISSN:1852-4516 Aprobado por resoluci´on N◦ 0686/11-R-UNPA

HERRAMIENTA EVOLUTIVA PARA LA PLANIFICACION DEL MANTENIMIENTO DE LOCACIONES PETROLERAS Mar´ıa A. Cossio y Mg. Andrea Villagra UNPA - Unidad Acad´emica Caleta Olivia may [email protected], [email protected] 2011

Resumen El prop´osito de este documento es la presentaci´on de una herramienta (PAE, Planificaci´on basada en un Algoritmo Evolutivo) que utiliza un algoritmo evolutivo generador de m´ultiples soluciones para la planificaci´on din´amica del mantenimiento preventivo de locaciones petroleras. La explotaci´on y el transporte de petr´oleo son actividades muy importantes para el desarrollo econ´omico de la sociedad industrial moderna. Sin embargo, estas actividades son generadoras de riesgos que se traducen en contaminaciones accidentales o cr´onicas que afectan directamente al ecosistema. Es importante que las empresas petroleras realicen un correcto mantenimiento de sus locaciones. PAE es capaz de brindar en forma oportuna la planificaci´on del recorrido. El beneficio debe observarse desde dos aspectos. Primero, una planificaci´on es mejor que otra, si para un mismo n´umero de locaciones a visitar el costo de recorrido e intervenci´on planificada es menor. Segundo, si con un mismo tiempo de intervenci´on es posible realizar el mantenimiento a m´as locaciones, reduciendo la probabilidad de ca´ıda al incrementar la cantidad de locaciones recorridas. Se han incorporado eventos externos que provocan la replanificaci´on y restricciones al momento de la planificaci´on, en estos casos los resultados obtenidos han sido satisfactorios ya que minimizan el tiempo total de una planificaci´on y maximizan la cantidad de locaciones visitadas. Esta herramienta ha sido dise˜nada para operar a un bajo costo de desarrollo tanto desde el punto de vista de la tecnolog´ıa hardware como la tecnolog´ıa de software que la soporta, desarrollada por el Laboratorio de Tecnolog´ıas Emergentes de la Universidad Nacional de la Patagonia Austral Unidad Acad´emica Caleta Olivia, utiliza un algoritmo evolutivo que es el generador de m´ultiples soluciones al problema. Palabras claves: Locaciones petroleras, algoritmo evolutivo, restricciones, replanificaci´on.

63

ICT-UNPA-30-2011 ISSN:1852-4516 Aprobado por resoluci´on N◦ 0686/11-R-UNPA

1.

INTRODUCCION

El petr´oleo, recurso natural de gran importancia para el desarrollo de la humanidad, y el empleo de la tecnolog´ıa, como instrumento de apropiaci´on y de transformaci´on de los recursos naturales, ha generado en el mundo impactos ambientales negativos, significativos por las graves consecuencias provocadas en el medio. Este recurso se ha convertido en una preocupaci´on ambiental seria, dado que su extracci´on y uso como fuente de energ´ıa por los seres humanos, ha conducido a su distribuci´on amplia en la biosfera. Esta situaci´on ha provocado que las Empresas dedicadas a la explotaci´on, producci´on y transporte del petr´oleo, se dediquen con m´as empe˜no a la implementaci´on de medidas de prevenci´on a fin de evitar y / o minimizar los da˜nos ocasionados al medio ambiente, personas y bienes materiales. Los incidentes normalmente se producen por fallas de equipos o material y fallas humanas. Para prevenir los primeros se deben realizar inspecciones peri´odicas y un mantenimiento adecuado. En cuanto a los incidentes provocados por fallas humanas, se subsanan mediante la instrucci´on y el entrenamiento del personal en forma permanente. Por esta raz´on es importante, para las empresas petroleras y para el entorno que las rodea, un correcto mantenimiento de sus locaciones. PAE es una herramienta para realizar la planificaci´on y se basa en un algoritmo evolutivo para dar una soluci´on al problema de mantenimiento de las locaciones petroleras. Los Algoritmos Evolutivos (AEs) son metaheur´ısticas que emplean modelos computacionales del proceso evolutivo. Existen una gran variedad de AEs, los principales incluyen: Estrategias de Evolutivas (Schwefel H. 1981), Programaci´on Evolutiva (Fogel L. 1966) y Algoritmos Gen´eticos (Holland J., 1975). Todos estos algoritmos comparten un concepto base com´un que es simular a la evoluci´on de los individuos que forman la poblaci´on usando un conjunto de operadores predefinidos. Com´unmente se usan dos tipos de operadores: de selecci´on y de b´usqueda. Los operadores de b´usqueda m´as usados son la mutaci´on y la recombinaci´on. Tendencias actuales en AEs hacen uso de enfoques con multirecombinaci´on y m´ultiples padres. Para la resoluci´on de diversos tipos de problemas de planificaci´on tales como scheduling o routing estos enfoques han resultado ser estrategias exitosas. Particularmente en problemas de scheduling, introduciendo al enfoque de multirecombinaci´on una nueva variante conocida como MCMP-SRI (Stud and Random Inmigrates) El documento est´a organizado de la siguiente manera: Una secci´on Marco Te´orico donde, en la primer subsecci´on, se describe el dominio y el problema que se tratar´a, en la subsecci´on Algoritmos Evolutivos se presentan los conceptos te´oricos principales sobre Algoritmos Evolutivos, luego en la siguiente subsecci´on se formula el problema y en la subsecci´on Algoritmo Evolutivo Propuesto se explica c´omo se propone solucionar el problema con un Algoritmo Evolutivo. En la secci´on Resultados se detallan los resultados de la implementaci´on del algoritmo en distintas situaciones.

2. 2.1.

MARCO TEORICO Dominio y Descripcion del Problema

Una actividad fundamental que realizan las empresas petroleras son las visitas de mantenimiento a las locaciones petroleras (pozos productores, inyectores, bater´ıas y colectores). Un yacimiento petrolero est´a formado por bloques y un bloque, a su vez, por bater´ıas. Cada bater´ıa est´a formada por, en promedio, entre 15 y 20 pozos de producci´on. El nivel de producci´on es diferente en cada pozo, es conocido a priori y var´ıa en el tiempo. La producci´on del pozo define 64

ICT-UNPA-30-2011 ISSN:1852-4516 Aprobado por resoluci´on N◦ 0686/11-R-UNPA

la categor´ıa y la cantidad de veces que debe visitarse al mes. Los pozos no pueden ser visitados m´as de una vez al d´ıa y dependiendo del tipo de pozo, existen ciertas tareas que se deben realizar. Cada tarea tiene asignado un determinado equipamiento necesario, una frecuencia de realizaci´on y un tiempo aproximado de su duraci´on. En la Tabla 1 se muestran ejemplos de algunas tareas realizadas en una locaci´on, en este caso, tareas en pozos productores y bater´ıas. Actualmente, el recorrido que realizan los encargados de las locaciones, se planifica en base a la experiencia de los mismos. La jornada laboral comienza a la ma˜nana y se visitan las locaciones en dos turnos de tres horas. Luego de finalizado cada turno el responsable debe regresar a la base de operaciones, realizar determinadas actividades administrativas y luego comenzar con el siguiente turno. El tiempo demandado en cada locaci´on depender´a del tipo de la misma. Existen contingencias aleatorias que hacen que el plan de mantenimiento de un turno no se cumpla seg´un lo planificado, produciendo la necesidad de replanificar las visitas. Adem´as puede ocurrir que en el momento de replanificaci´on, por determinados motivos, se debe incorporar la visita obligatoria a ciertas locaciones en el pr´oximo turno, provocando esto un conjunto de restricciones en la replanificaci´on. Cuando ocurre esto, cada responsable redefine el nuevo itinerario utilizando su experiencia. En la Figura 1 se muestra una distribuci´on de locaciones petroleras del yacimiento explotado en la zona norte de la provincia de Santa Cruz, Argentina. Descripci´on de la tarea Cant. Equipos Frecuencia/d´ıas Tiempo/Min. Verificaci´on r´egimen de bombeo 78 7 2 Extracci´on muestra boca de pozo (por pozo) 105 15 5 Medici´on de gas de entreca˜nos 5 30 10 Puesta de ensayos en auxiliares y Estaci´on 12 1 10 Medici´on y cierre de Tks en estaciones 6 1 10 Verificaci´on de recirculado 3 1 5 Verificaci´on de bombas de bater´ıas y Stock 4 7 5 Verificaci´on de inyecci´on de qu´ımica Bat y pozos 15 1 5 Estado de puente de producci´on 105 1 5 Programa semanal de Dinam´ometro y nivel 78 7 20 Tabla 1: Descripci´on de Tareas en una locaci´on

2.2.

Metaheur´ısticas y Algoritmos Evolutivos

En esta secci´on se efect´ua, a modo de introducci´on, una descripci´on breve de las t´ecnicas metaheur´ısticas de optimizaci´on m´as populares, tal como se clasifican en Crainic y Toulouse (2003). Luego, se describe con m´as detalle un tipo concreto de estas t´ecnicas metaheur´ısticas, que son los Algoritmos Evolutivos. La optimizaci´on en el sentido de encontrar la mejor soluci´on, o al menos una soluci´on lo suficientemente buena para un problema es un campo de vital importancia en la vida real. Cuando el problema es muy grande y complejo se hace necesario el uso de computadoras para su resoluci´on. Debido a la gran importancia de los problemas de optimizaci´on, a lo largo de la historia de la Inform´atica se han desarrollado m´ultiples m´etodos para tratar de resolverlos. Una clasificaci´on muy simple de estos m´etodos se muestra en la Figura 2. Las t´ecnicas se pueden clasificar en exactas (o enumerativas, exhaustivas, etc.) y t´ecnicas aproximadas. Las t´ecnicas aproximadas est´an recibiendo una atenci´on cada vez mayor por parte de la comunidad internacional a lo largo de los u´ ltimos 30 a˜nos. Estos m´etodos priorizan la importancia de encontrar una “buena” soluci´on en un tiempo “razonable”. 65

ICT-UNPA-30-2011 ISSN:1852-4516 Aprobado por resoluci´on N◦ 0686/11-R-UNPA

Figura 1: Plano de caminos y distribuciones

Figura 2: Clasificacion de las t´ecnicas de optimizaci´on

66

ICT-UNPA-30-2011 ISSN:1852-4516 Aprobado por resoluci´on N◦ 0686/11-R-UNPA

Figura 3: Clasificacion de las metaheur´ısticas Dentro de los algoritmos aproximados se pueden encontrar tres tipos: - Los heur´ısticos constructivos: generan una soluci´on partiendo de una vac´ıa a la que se le van a˜nadiendo componentes hasta tener una soluci´on completa, que es el resultado del algoritmo. ´ - Los m´etodos de busqueda local: parten de una soluci´on ya completa junto con el uso del concepto de vecindario, recorren parte del espacio de b´usqueda, su vecindario, y eligen el mejor vecino continuando el proceso hasta que encuentran un o´ ptimo local. - Las metaheur´ısticas: son estrategias de alto nivel que usan diferentes m´etodos para explorar el espacio de b´usqueda. En otras palabras, una metaheur´ıstica es una plantilla general no determinista que debe ser rellenada con datos espec´ıficos del problema (representaci´on de las soluciones, operadores para manipularlas, etc.) y que permite abordar problemas con espacios de b´usqueda de gran tama˜no (por ejemplo 21000 posibles soluciones). Por lo tanto es de especial inter´es el correcto equilibrio (generalmente din´amico) que haya entre diversificaci´on e intensificaci´on. De acuerdo a si en cada paso manipulan un u´ nico punto del espacio de b´usqueda o trabajan sobre un conjunto (poblaci´on) de ellos, las metaheur´ısticas se clasifican en basadas en trayectoria y basadas en poblaci´on. Esta clasificaci´on es ampliamente utilizada en la comunidad cient´ıfica y se muestra de forma gr´afica en la Figura 3 en la que se pueden observar las principales metaheur´ısticas. Las siglas de la figura se corresponden de la siguiente manera: Enfriamiento Simulado o Simulated Annealing (SA), B´usqueda Tabu o Tabu Search (TS), Procedimiento de B´usqueda Miope Aleatorizado y Adaptativo o Greedy Randomized Adaptive Search Procedure (GRASP), B´usqueda en Vecindario Variable o Variable Neighborhood Search (VNS), Busqueda Local Iterada o Iterated Local Search (ILS) Algoritmos Evolutivos o Evolutionary Algorithms (EA), Algoritmos Basados en C´umulos de Part´ıculas o Particle Swarm Optimization (PSO), Evoluci´on Diferencial o Diferencial Evolution (DE), B´usqueda Dispersa o Scatter Search (SS), Colonia de Hormigas o Ant Colony Optimization (ACO). Metaheur´ısticas Basadas en Trayectoria. La principal caracter´ıstica de estos m´etodos es que parten de un punto y mediante la exploraci´on del vecindario van actualizando la soluci´on actual, formando una trayectoria. Metaheur´ısticas Basadas en Poblaci´on. Los m´etodos basados en poblaci´on se caracterizan por trabajar con un conjunto de soluciones (poblaci´on) en cada iteraci´on, a diferencia de los m´etodos anteriores que u´ nicamente utilizan un punto del espacio de b´usqueda por iteraci´on. El 67

ICT-UNPA-30-2011 ISSN:1852-4516 Aprobado por resoluci´on N◦ 0686/11-R-UNPA

resultado final proporcionado por este tipo de algoritmos depende fuertemente de la forma en que manipula la poblaci´on. Este trabajo est´a centrado en los Algoritmos Evolutivos, por lo que esta t´ecnica se describe con m´as detalle a continuaci´on. Los Algoritmos Evolutivos son t´ecnicas de optimizaci´on estoc´astica basadas en la simulaci´on del proceso evolutivo natural de los seres humanos. Son t´ecnicas de b´usqueda basadas en el mecanismo de selecci´on natural y gen´etica natural. Los algoritmos gen´eticos, a diferencia de las t´ecnicas de b´usqueda convencionales, comienzan con un conjunto inicial de soluciones aleatorias llamada poblaci´on. Cada individuo en la poblaci´on es llamado cromosoma, representando una soluci´on al problema que se est´a tratando de resolver. Los cromosomas evolucionan a trav´es de sucesivas iteraciones, llamadas generaciones. Durante cada generaci´on, los cromosomas son evaluadas, usando algunas medidas de aptitud. Para crear la siguiente generaci´on, los cromosomas nuevos, llamados descendientes, est´an formados por cualquiera de los dos: a) la combinaci´on de dos cromosomas de la generaci´on actual usando un operador de cruzamiento o b) modificando un cromosoma usando un operador de mutaci´on. Una nueva generaci´on se forma a) seleccionando, de acuerdo a los valores de aptitud, alguno de los padres y descendientes y b) rechazando otras a fin de mantener el tama˜no de la poblaci´on constante. Los cromosomas con ”buenos”valores de aptitud tienen probabilidades m´as altas de ser seleccionados. Despu´es de varias generaciones, los algoritmos convergen al mejor cromosoma, el cual se espera que represente la o´ ptima o sub´optima soluci´on al problema. Una cuesti´on importante a ser considerada en el dise˜no de un cromosoma como representaci´on de soluciones a un problema es la implementaci´on de restricciones en las soluciones (problema espec´ıfico de conocimiento) (Michalewicz Z., 1994) ”Las restricciones que no pueden ser violadas pueden ser implementadas a trav´es de la imposici´on de penalidades fuertes a los individuos que las violan, a trav´es de la imposici´on de penalidades moderadas o a trav´es de la creaci´on de decodificadores de la representaci´on que eviten la creaci´on de individuos que violan la restricci´on.”(Davis L. y Steenstrup M., 1987) Todas las instancias b´asicas de Algoritmos Evolutivos comparten varias propiedades comunes, dado que emanan del modelo de la evoluci´on org´anica: - Los AEs utilizan el proceso de aprendizaje colectivo de una poblaci´on de individuos. Usualmente un individuo representa (codifica) un punto de b´usqueda en el espacio de posibles soluciones de un problema. Adem´as los individuos pueden incorporar informaci´on adicional: por ejemplo, par´ametros para la estrategia de los AEs. - Los descendientes de los individuos se generan por procesos aleatorios que intentan modelar la mutaci´on y la recombinaci´on. La mutaci´on corresponde a una err´onea autoreplicaci´on de individuos: t´ıpicamente peque˜nas modificaciones. La recombinaci´on intercambia informaci´on entre dos o m´as individuos. - A cada individuo se le asigna una medida de su calidad o aptitud evalu´andolo en su ambiente. Como requerimiento m´ınimo es posible realizar una comparaci´on de su calidad, 68

ICT-UNPA-30-2011 ISSN:1852-4516 Aprobado por resoluci´on N◦ 0686/11-R-UNPA

Figura 4: Proceso de PAE lo que nos conduce a una decisi´on binaria: mejor o peor. Acorde con esta medida de adaptabilidad, el proceso de selecci´on favorece a los mejores individuos a fin de que se reproduzcan m´as frecuentemente que aquellos relativamente peores. Estas son las propiedades m´as generales de los AEs y sus distintas instancias usan estas componentes en variadas formas. 2.3.

Algoritmo Evolutivo Propuesto

Para resolver el problema de planificaci´on de recorrido de las locaciones petroleras se utiliz´o un algoritmo evolutivo. Para codificar adecuadamente las visitas a las locaciones petroleras, que representan una posible soluci´on, se utiliz´o una permutaci´on. Donde cada permutaci´on p = (p1, p2, ..., pn) es un cromosoma en el cual pi representa la locaci´on i que debe ser visitada y n representa la cantidad de locaciones a visitar. En la figura 4 se muestra la resoluci´on del problema utilizando un algoritmo gen´etico. El cromosoma representa el orden en que ser´an visitadas las locaciones (gen del cromosoma) dentro de la planificaci´on. Se implement´o un proceso de m´ultiple recombinaci´on y m´ultiples padres donde los nuevos individuos se generan a partir de un pool de m´ultiples padres, conformado por un individuo ´ semental y por individuos generados aleatoriamente (inmigrantes aleatorios). Este proceso es ´ m´etollamado MCMP-SRI y es una variante de multirecombinaci´on (Pandolfi et al., 2002). Este do fue aplicado en diferentes problemas de planificaci´on de m´aquina u´ nica para casos est´aticos y casos din´amicos y los resultados obtenidos fueron satisfactorios. En el Algoritmo 1 se presenta un esquema general de EA-MCMP-SRI, que se utiliza para resolver nuestro problema y se explica a continuaci´on. El proceso para crear descendientes es el siguiente: de la vieja poblaci´on de individuos, se selecciona un individuo, el semental, a trav´es de selecci´on proporcional. Se genera un pool de apareamiento con n2 padres generados aleatoriamente. El semental se aparea con cada padre del pool de apareamiento y las parejas se someten a operaciones de recombinaci´on y generan 2 ∗ n2 descendientes. El mejor de los 2 ∗ n2 descendientes, se almacena en un pool de hijos temporal. Esta operaci´on de recombinaci´on se repite n1 veces, para diferentes puntos de corte cada vez, hasta que el pool de hijos se complete. Finalmente, el mejor descendiente creado de n2 padres y n1 operaciones de recombinaci´on, se 69

ICT-UNPA-30-2011 ISSN:1852-4516 Aprobado por resoluci´on N◦ 0686/11-R-UNPA Algoritmo 1 EA-MCMP-SRI 1: t = 0 {generaci´on actual} 2: inicializar Stud(t) 3: evalua Stud(t) 4: mientras not max evaluaciones hacer 5: pool apareamiento = Genera Inmigrantes Aleatorios ∪ Selecciona (Stud(t)) 6: mientras not max padres hacer 7: mientras max recombinaciones hacer 8: evoluciona (pool apareamiento){recombinaci´on y mutaci´on} 9: fin mientras 10: fin mientras 11: evalua (pool apareamiento) 12: Stud(t+1) = selec. nueva poblaci´on del pool apareamiento 13: t=t+1 14: fin mientras inserta en la nueva poblaci´on. El m´etodo de recombinaci´on utilizado fue PMX (Partial Mapped Crossover): que puede verse como una extensi´on del cruzamiento de dos puntos para representaciones basadas en permutaciones. La selecci´on de individuos fue a trav´es de selecci´on proporcional. El cromosoma establece el orden de la secuencia a seguir para visitar cada locaci´on. Adem´as, se tiene en cuenta que existen locaciones que deben ser visitadas m´as de una vez lo cual implica incorporar restricciones a este problema. Para ello se definieron dos tipos de restricciones: - Restricci´on dura: toda soluci´on obtenida que no cumpla con este tipo de restricci´on es considerada no factible y por lo tanto debe ser reparada o eliminada. Para este caso, las locaciones que deben ser visitadas m´as de una vez no pueden ser planificadas en el mismo turno. - Restricci´on blanda: la soluci´on es factible (es decir, cumple con la restricci´on dura) pero sin embargo no cumple con la diferencia de tiempo entre una visita y otra. Por ejemplo, la soluci´on planifica las dos visitas a una locaci´on en turnos diferentes, pero el tiempo transcurrido entre ambas visitas no es el establecido en la restricci´on (ocho horas). 2.4.

Formulaci´on del Problema

El problema se puede definir como (Pinedo M.,1995): 1 | sjk | Cmax . Denota un problema de scheduling de m´aquina u´ nica con n tareas sujetas a tiempos de preparaci´on dependientes de la secuencia. Donde las tareas a planificar son el servicio de mantenimiento (o intervenci´on) en cada una de las locaciones petroleras. Adem´as, existe un tiempo de traslado entre cada una de las locaciones al que se denomina sjk , que representa el costo en tiempo de ir de la locaci´on j a la locaci´on k. La funci´on objetivo es minimizar el makespan (Cmax ) sujeto a los tiempos de preparaci´on dependientes de la secuencia. Este problema es equivalente al denominado Traveling Salesman Problem (TSP). El makespan puede ser calculado como: 70

ICT-UNPA-30-2011 ISSN:1852-4516 Aprobado por resoluci´on N◦ 0686/11-R-UNPA

n X

(Sjk + tk )

k=1

Donde Sjk representa el costo (en tiempo) de trasladarse desde la locaci´on petrolera j hasta la locaci´on petrolera k, tk se refiere al tiempo de mantenimiento en la locaci´on k, y n es el n´umero total de locaciones petroleras en el yacimiento. Al incorporarse restricciones se necesita redefinir la funci´on objetivo (Cmax ) debido a que al makespan se le adicionan las penalidades de todas aquellas restricciones que no se cumplan: (Cmax ) +

m X

Pi

i−1

donde m es el n´umero de restricciones y Pi es el valor de la penalidad asignada a esa soluci´on.

3.

RESULTADOS En esta secci´on se muestran los resultados obtenidos con el algoritmo propuesto.

3.1.

˜ de Experimentos Preparaci´on de los datos y Diseno

Para resolver el problema fue necesario preparar los datos de entrada ya que originalmente las distancias entre las locaciones petroleras no estaban procesadas. Se realiz´o el c´alculo de las distancias entre las locaciones petroleras basados en el plano de caminos y distribuci´on del yacimiento. Matem´aticamente, es sabido que la distancia entre dos puntos que se encuentran en cualquier lugar del sistema de coordenadas, est´a determinada por la relaci´on denominada distancia eucl´ıdea. No obstante, en este problema solo se puede calcular la distancia entre dos puntos, teniendo en cuenta el camino que existe para llegar a ellos. Por esta raz´on se utiliz´o el plano de las ubicaciones de las locaciones y se escalaron las distancias entre las mismas. Para realizar los experimentos se establecieron las siguientes suposiciones y restricciones al problema. Para la evaluaci´on de la aplicaci´on se trabaj´o con 110 locaciones petroleras correspondientes a un bloque de la zona de explotaci´on. La velocidad de recorrido se estableci´o en 12 segundos cada 100 metros y se fij´o el mismo tiempo de intervenci´on para cada locaci´on en el proceso de mantenimiento preventivo. Para el algoritmo evolutivo propuesto se utiliz´o un tama˜no de poblaci´on de 15 individuos. La poblaci´on inicial se gener´o aleatoriamente. Se estableci´o la probabilidad de mutaci´on en 0,05 y la probabilidad de recombinaci´on en 0,65. El n´umero n1 (n´umero de operaciones de recombinaci´on) y n2 (n´umero de padres), se estableci´o en 16 y 18 respectivamente. El n´umero n1 de recombinaciones y n2 de padres fueron fijados en 16 y 18, respectivamente. El n´umero m´aximo de evaluaciones por generaci´on se ha calculo como n1 × (n2 − 1)×Tama˜no poblaci´on. Los par´ametros (tama˜no de la poblaci´on, criterio de parada, probabilidades, etc.) se seleccionaron en base a la experimentaci´on de los valores previamente usados con e´ xito. La Tabla 2 resume los par´ametros utilizados en todas las corridas. A continuaci´on se describen cuatro experimentos distintos realizados con el objetivo de analizar la eficiencia del algoritmo en diferentes situaciones. El primer experimento se realiz´o para determinar la eficiencia del algoritmo para la planificaci´on del total de locaciones en el bloque norte del a´ rea de explotaci´on (110 pozos) (Villagra A.a et al, 2007). Se realizaron 20 corridas independientes usando los valores de los par´ametros que est´an en la Tabla 2. 71

ICT-UNPA-30-2011 ISSN:1852-4516 Aprobado por resoluci´on N◦ 0686/11-R-UNPA Tama˜no poblaci´on 15 Tama˜no cromosoma (cantidad de locaciones) 110 Criterio parada (generaci´on) 500 Recombinaci´on PMX Mutaci´on SW Probabilidad Recombinaci´on 0,65 Probabilidad Mutaci´on 0,05 ◦ N de recombinaci´on (n1 ) 16 ◦ N de padres (n2 ) 18 Tabla 2: Par´ametros del algoritmo evolutivo La Tabla 3 resume los resultados obtenidos en cada una de las corridas. La primera columna representa el n´umero de corrida, la segunda columna indica la cantidad de turnos planificados, la tercera columna muestra los kil´ometros recorridos en esa planificaci´on, la cuarta columna muestra los minutos totales correspondientes a la planificaci´on y finalmente la u´ ltima columna detalla el tiempo total en horas. Las dos u´ ltimas filas muestran los valores m´ınimos y m´aximos obtenidos. Se pudo observar lo siguiente: Cantidad de turnos planificados: 4 o´ 5 para cada una de las corridas Tiempo total planificado para realizar las visitas a las 110 locaciones: oscila desde 12 a 12.30 horas. Tiempo m´ınimo para una planificaci´on: se encontr´o en la corrida n´umero 18 donde los 110 pozos fueron visitados en 717 minutos (11 horas, 57 minutos y 28 segundos) y fueron cubiertos 86,458 km . Tiempo m´aximo planificado: se encontr´o en la corrida n´umero 1 donde los 110 pozos fueron visitados en 753 minutos (12 horas, 33 minutos y 4 segundos) y fueron cubiertos 104,041 km. La Tabla 4 compara el resumen de una planificaci´on espec´ıfica para 110 pozos de la Empresa Petrolera y la planificaci´on obtenida por PAE para el mismo n´umero de pozos. Se puede observar que PAE reduce en un 30 % el tiempo total de planificaci´on y visita en todos los turnos m´as cantidad de locaciones que las visitadas por la empresa petrolera. En general, mientras una planificaci´on original demanda un tiempo total de 18 horas 24 minutos, la mejor planificaci´on provista por PAE demanda 12 horas 37 minutos, logrando un ahorro de aproximadamente 6 horas. El tiempo de procesamiento de una planificaci´on t´ıpica (110 pozos) trabajando con una PC Pentium 4 a 2.8 Ghz y 512 Mb de RAM, fue en promedio de 11 minutos. Se realiz´o un segundo experimento (Villagra A.b et al, 2007), considerando la ocurrencia de un evento externo, que puede resultar en la complicaci´on de la planificaci´on original, en este caso, se analiza el rendimiento del algoritmo en el proceso de replanificar un subconjunto de los 110 pozos. En el segundo experimento se uso cada planificaci´on obtenida en el experimento anterior y para cada una se gener´o una interrupci´on aleatoria. Luego se analizaron los resultados de replanificaci´on despu´es de la ocurrencia de un evento externo (interrupci´on/contingencia) siguiendo estas acciones: - Acci´on 1: Aquellos pozos que no fueron visitados en un turno interrumpido se replanificaron al final de la planificaci´on original. - Acci´on 2: Los turnos son replanificados siguiendo el orden de la secuencia original restante. 72

ICT-UNPA-30-2011 ISSN:1852-4516 Aprobado por resoluci´on N◦ 0686/11-R-UNPA N◦ Turno 1 5 2 4 3 5 4 5 5 5 6 5 7 5 8 5 9 5 10 5 11 5 12 5 13 5 14 5 15 4 16 5 17 5 18 4 19 5 20 4 M´ınimo M´aximo

Km Minutos Tpo. Total 104,041 753 12:33:04 91,676 728 12:08:22 99,344 743 12:23:33 102,011 748 12:28:32 97,393 737 12:17:22 97,607 740 12:20:13 95,699 735 12:15:13 94,515 734 12:14:01 99,695 743 12:23:24 100,98 746 12:26:55 93,293 729 12:09:54 98,636 742 12:22:04 99,162 743 12:23:02 103,313 750 12:30:21 92,4 729 12:09:47 97,564 740 12:20:15 101,354 747 12:27:22 86,458 717 11:57:28 97,803 740 12:20:32 89,289 721 12:01:49 86,458 717 104,041 753

Tabla 3: Resultados Obtenidos por PAE - Acci´on 3: A partir del pozo interrumpido, se usa el algoritmo propuesto para generar una nueva planificaci´on con los pozos restantes. Los resultados obtenidos fueron comparados con informaci´on hist´orica dada por la Empresa Petrolera para una planificaci´on est´andar. La Tabla 5 resume los resultados obtenidos por PAE en el segundo experimento. Los aspectos m´as relevantes mostrados en la comparaci´on son los siguientes: el n´umero de pozos visitados antes de que ocurra una interrupci´on (columna NBC), el n´umero de pozos a ser visitados despu´es de que ocurra la interrupci´on (columna NAC), tiempo total planificado en la planificaci´on original (columna Planificaci´on Original), tiempo total planificado cuando ocurre una interrupci´on y el algoritmo replanifica de acuerdo a la acci´on 1 (columna Acci´on 1), replanifica de acuerdo a la acci´on 2 (columna Acci´on 2), y replanifica de acuerdo a la acci´on 3 (columna Acci´on 3). Se puede observar que las replanificaciones var´ıan entre un m´ınimo de 11 locaciones a 89 locaciones. La acci´on 1 es la menos favorable de las tres y la acci´on 2, que es la aplicada por el equipo de mantenimiento, si bien mejora a la anterior no lo hace para la acci´on de planificaci´on con el algoritmo multirecombinativo. El m´aximo tiempo para una planificaci´on realizando la acci´on 2, fue de 12 horas y 24 minutos, el m´ınimo tiempo fue de 11 horas y 54 minutos. Adem´as en la mayor´ıa de las corridas (19 de 20), la u´ ltima acci´on mejora los resultados obtenidos en la planificaci´on original. La raz´on de esta mejora est´a basada en el uso de un algoritmo espec´ıfico para la replanificaci´on (EA-MCMP-SRI) para un tama˜no de problema menor a 110 locaciones. En el tercer experimento, (Villagra A.a et al, 2007) se modific´o u´ nicamente el tama˜no de 73

ICT-UNPA-30-2011 ISSN:1852-4516 Aprobado por resoluci´on N◦ 0686/11-R-UNPA Planificaci´on Empresa Petrolera Planificaci´on con PAE D´ıa Turno Pozos Tiempo D´ıa Turno Pozos Tiempo 1 1 18 181,50 1 1 24 178,67 2 16 176,23 2 27 182,02 2 3 18 184,20 2 3 26 177,95 4 20 182,20 4 27 178,97 3 5 19 181,90 3 5 6 39,72 6 19 198,60 110 757,16 110 1104,63 12:37:19 18:24:38 Tabla 4: Comparaci´on Empresa Petrolera y PAE las locaciones a visitar, y los valores restantes se mantuvieron. A continuaci´on se describe cada uno de los experimentos con replanificaci´on: - Se tomaron 110 locaciones a visitar, con 2, 3, 4 y 5 visitas obligatorias en un turno. - Se tomaron 80 locaciones a visitar, con 2, 3, 4 y 5 visitas obligatorias en un turno. - Se tomaron 55 locaciones a visitar, con 2, 3, 4 y 5 visitas obligatorias en un turno. En la Tabla 6 se muestran los resultados obtenidos por PAE en cada uno de los experimentos descriptos anteriormente donde se realiza replanificaci´on y se incorporan restricciones. La primera columna corresponde a la cantidad de locaciones a visitar en el momento de la replanificaci´on. La segunda columna corresponde a la cantidad de locaciones que obligatoriamente se deben visitar en el pr´oximo turno. La tercera columna corresponde a los kil´ometros recorridos en esa replanificaci´on. La cuarta columna corresponde a la cantidad de turnos a realizar y finalmente la u´ ltima columna corresponde al tiempo total de esa replanificaci´on, en horas. Se puede observar que la incorporaci´on de restricciones al momento de la replanificaci´on, ya sean 2, 3, 4 o´ 5 locaciones, no degrada la eficiencia de los resultados obtenidos pues en todos los casos el algoritmo contin´ua mejorando las planificaciones realizadas por la empresa petrolera. El cuarto experimento (Villagra A.c et al, 2007) muestra el comportamiento del algoritmo al incrementar el n´umero de restricciones en uno. En un primer paso el algoritmo se ejecuta sin restricciones. En el segundo paso, se incorpora una restricci´on en la cual la locaci´on i debe visitarse dos veces y se mantiene la restricci´on anterior. As´ı sucesivamente se incorporan restricciones hasta llegar a un total de cinco. Las locaciones utilizadas como restricciones fueron elegidas uniformemente del conjunto total de locaciones a planificar. En la Tabla 7 se muestra como PAE satisface las restricciones y minimiza el costo de penalidad (0 penalidad). La primera columna muestra la cantidad de restricciones, las restantes columnas representan los turnos a los cuales se asignaron las locaciones con restricciones. Se puede observar como el algoritmo distribuye las visitas de las locaciones a fin de satisfacer las restricciones. Por ejemplo, cuando trabaja con dos restricciones, la primera visita de la locaci´on 104 es en el primer turno (columna T1) y la segunda visita es en el turno cuatro (columna T4), la primera visita de la locaci´on 2 es en el segundo turno y la segunda visita es en el turno 5. En la Tabla 8 se muestran los valores promedio obtenidos por PAE incrementando el n´umero de restricciones. La primera columna representa la cantidad de restricciones agregadas a la planificaci´on. La segunda y tercera columna corresponde a la cantidad m´ınima y a la cantidad m´axima de turnos planificados en cada corrida. La cuarta columna corresponde al promedio de 74

ICT-UNPA-30-2011 ISSN:1852-4516 Aprobado por resoluci´on N◦ 0686/11-R-UNPA N◦ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

NBC NAC 91 19 21 89 36 74 33 77 25 85 70 40 56 54 34 76 99 11 44 66 55 55 58 52 76 34 51 59 32 78 55 55 79 31 51 59 39 71 35 75

Planificacion Original Acci´on 1 Acci´on 2 12:33:04 12:38:.35 12:27:17 12:08:22 12:11:18 12:15:54 12:23:33 12:20:56 12:20:56 12:28:32 12:31:33 12:26:03 12:17:22 12:19:25 12:14:20 12:20:13 12:19:02 12:14:40 12:15:13 12:14:39 12:13:34 12:14:01 12:16:20 12:06:54 12:23:24 12:20:06 12:20:11 12:26:55 12:25:03 12:19:28 12:09:54 12:07:58 12:15:30 12:22:04 12:18:51 12:25:48 12:23:02 12:22:15 12:14:40 12:30:21 12:27:03 12:26:54 12:09:47 12:11:13 12:16:25 12:20:15 12:19:34 12:11:55 12:27:22 12:26:06 12:28:00 11:57:28 11:53:13 12:06:48 12:20:32 12:22:15 12:23:12 12:01:49 12:03:41 12:06:50

Acci´on 3 12:07:22 12:04:41 12:14:51 12:09:37 11:58:37 12:04:53 12:04:57 12:01:46 12:15:17 12:12:50 11:54:00 12:02:40 12:07:49 12:21:24 12:08:40 12:11:28 12:24:51 12:00:44 12:05:16 11:58:48

Tabla 5: Resultados obtenidos por PAE en la replanificaci´on km. recorridos en cada planificaci´on y la u´ ltima columna representa el tiempo promedio total requerido para visitar todas las 110 locaciones teniendo en cuenta las restricciones correspondientes. Podemos observar que independientemente de la cantidad de restricciones incorporadas, la cantidad de turnos m´ınimos y m´aximos es la misma e igual a 5. El tiempo promedio total que se tarda en realizar una planificaci´on va increment´andose a medida que se incorporan restricciones, pero este incremento no es significativo comparado con el resultado promedio observado sin restricciones que es de 13 horas 5 minutos y con cinco restricciones es de 13 horas 45 minutos.

4.

CONCLUSIONES

La aplicaci´on PAE fue construida a fin de brindar una herramienta eficaz que facilite la planificaci´on y replanificaci´on din´amica del mantenimiento de locaciones petroleras. Del an´alisis y las comparaciones realizadas con los planes de mantenimiento ejecutados, podemos concluir que PAE ofrece las siguientes ventajas comparativas: - En cuanto a la calidad de las soluciones, PAE presenta planificaciones que mejoran el plan de mantenimiento producido por expertos, reduciendo el tiempo total, con la correspondiente reducci´on de costos. Sin embargo, este beneficio puede tambi´en analizarse desde otra perspectiva, ya que reduciendo el tiempo total de intervenci´on se pueden realizar m´as cantidad de visitas mensuales en las locaciones. Con ello se logra disminuir la probabilidad de ca´ıda de la producci´on y por lo tanto maximizar la producci´on total. - Los AEs son algoritmos estoc´asticos (no determin´ısticos) que producen m´ultiples so75

ICT-UNPA-30-2011 ISSN:1852-4516 Aprobado por resoluci´on N◦ 0686/11-R-UNPA Locaciones Visitas Obligatorias 110 2 3 4 5 80 2 3 4 5 55 2 3 4 5

Km 124,333 120,888 129,147 126,681 89,379 83,511 87,821 82,802 58,044 54,360 51,465 53,560

Turnos Tpo.Total 5 13:17:41 5 13:10:47 5 13:27:19 5 13:22:23 4 9:37:16 4 9:24:28 4 9:34:39 4 9:23:07 3 6:29:53 3 6:22:10 3 6:15:19 3 6:10:07

Tabla 6: Replanificaci´on con restricciones N◦ Res T1 T2 1 2 2 104 2 3 104-1342 2 2 4 104 1342 1275 2 5 104 1342 1275 1154

T3

T4 104 2-1342

104

T5 2 2 104

1342 1275

2

104 1342

2 1275 1154

Tabla 7: Distribuci´on de locaciones en los turnos luciones en diferentes corridas independientes. A menudo una soluci´on mejor (plan de mantenimiento) no puede ejecutarse por determinadas condiciones operativas, por lo tanto es necesario seleccionar otra que si bien puede no ser tan buena como la otra es factible de ejecutarse. - Otro aspecto, que suele ser muy importante es la flexibilidad de producci´on de planes de mantenimiento, ya que muy a menudo se producen cambios, incorporando o eliminando locaciones en la producci´on del yacimiento. Para ello PAE facilita un ambiente flexible que permite incorporar cambios en la planificaci´on sin que ello represente la intervenci´on de expertos. - En la ejecuci´on de un plan de mantenimiento suelen ocurrir ciertas contingencias que impiden la ejecuci´on planificada, como por ejemplo encontrarse con problemas en la intervenci´on de un pozo. En estos casos, u otras situaciones similares el plan no puede seguir ejecut´andose, por ello es necesario la replanificaci´on del proceso de mantenimiento, es decir una nueva planificaci´on. PAE puede re-planificar el resto de las locaciones como si fuera un problema distinto en lugar de continuar con la planificaci´on original, 76

ICT-UNPA-30-2011 ISSN:1852-4516 Aprobado por resoluci´on N◦ 0686/11-R-UNPA N◦ Res Min Turno Max Turno Km. Recorridos Tiempo Total 0 5 5 118,325 13:05:39 1 5 5 120.255 13:14:30 2 5 5 124.468 13:27:55 3 5 5 125.628 13:35:15 4 5 5 124.495 13:37:59 5 5 5 125.752 13:45:29 Tabla 8: PAE con restricciones que suele ser ineficiente bajo estas nuevas condiciones. - Por u´ ltimo, frente a la incorporaci´on de restricciones en las visitas de mantenimieno, PAE no presenta degradaci´on de la soluci´on; generando planificaciones que satisfacen las restricciones y mantienen la calidad de los resultados.

5.

AGRADECIMIENTOS

Agradecemos a la Universidad Nacional de la Patagonia Austral por su apoyo al grupo de investigaci´on y adem´as, la cooperaci´on de los integrantes del proyecto que continuamente proveen de nuevas ideas y cr´ıticas constructivas.

6.

Referencias

CRAINIC T. y TOULOUSE M. 2003. Handbook of Metaheuristics, chapter Parallel Strategies. Kluwer Academic Publishers. DAVIS L. Y STEENSTRUP M. 1987. Genetic Algorithms and Simulated Annealing, Morgan Kaufmann Publishers, Los Altos, CA. FOGEL L., 1966. Artificial Intelligence through Simulated Evolution. JohnWesley, New York. GALLARD R. 1997. APUNTES DEL CURSO: COMPUTACION EVOLUTIVA: Conceptos y Aplicaciones. III Congreso Argentino de Ciencias de la Computaci´on I Escuela Internacional de Inform´atica CACIC , La Plata 29-9-97 al 4-10-97. HOLLAND J. 1975, Adaptation in Natural and Artificial Systems. Ann Harbor: University of Michigan Press. MICHALEWICZ Z. 1994. Genetic Algorithms + Data Structures = Evolution Programs. Second, Extended Edition Departament of Computer Science University of North Carolina Charlotte, NC 28223, USA. PANDOLFI D., DE SAN PEDRO M., VILLAGRA A., VILANOVA G., GALLARD R. 2002. Studs Mating Immigrants in Evolutionary Algorithm to Solve the Earliness-Tardiness Scheduling Problem . Cybernetics and Systems of Taylor and Francis Journal, (U.K.), pp 391-

77

ICT-UNPA-30-2011 ISSN:1852-4516 Aprobado por resoluci´on N◦ 0686/11-R-UNPA

400. PINEDO M. 1995. Scheduling: Theory, Algorithms and System. First edition Prentice Hall. SCHWEFEL H. 1981. Numerical Optimization of Computer Models. John Wiley and Sons, Great Britain. VILLAGRA A.a , MONTENEGRO C., DE SAN PEDRO E., LASSO Marta, PANDOLFI D. 2007. Restricciones en la replanificaci´on del mantenimiento de locaciones petroleras. CACIC. VILLAGRA A.b , DE SAN PEDRO M., LASSO M., MONTENEGRO C., PANDOLFI D. 2007. Evolutionary Algorithm for the oil fields preventive maintenance scheduling. WMSCI Orlando VILLAGRA A.c , MONTENEGRO C., DE SAN PEDRO E., LASSO M., PANDOLFI D. 2007 Planificacion con restricciones del mantenimiento de locaciones petroleras. RPIC R´ıo Gallegos.

78