Implementación de método de solución metaheurístico para un problema de selección de portafolio de proyectos

Abstract

Uno de los enfoques convencionales para la adjudicación de interventorías de obra pública supervisadas por el Instituto Nacional de Vías (INVIAS) en Colombia, son los Concursos de Méritos Abiertos (CMA’s). En esta modalidad, el postulante debe presentar un único portafolio de proyectos que le permita acreditar cuantitativamente ante la Entidad Estatal, su experiencia como interventor. Este problema de selección de portafolio de proyectos crece de manera factorial a medida que aumenta el número total de proyectos en la hoja de vida del participante y no existe un algoritmo determinístico que encuentre soluciones óptimas en tiempos polinomiales proporcionales a la instancia de trabajo, hecho que otorga al problema una complejidad computacional NP-Hard. Como alternativa al uso de enfoques de enumeración exhaustiva de bajo rendimiento formulados en Excel, se evaluaron las metaheurísticas GA, GRASP y dos reglas de validación heurísticas, para el caso de estudio de una Compañía con 207 contratos de trayectoria en el sector. Los resultados de evaluación ubicaron a la metaheurística GA como la alternativa de mejor desempeño para su implementación, dado que se validó su habilidad para encontrar hasta 10 portafolios con la máxima puntuación en menos de 9 minutos. Por otra parte, se encontró que el algoritmo GRASP es capaz de encontrar por lo menos un portafolio óptimo de postulación para distintas instancias, sin embargo, su capacidad para hallar más de una buena solución en las instancias de prueba utilizadas fue inferior a la del algoritmo GA. Para todos los casos de evaluación, el desempeño de las reglas de validación heurísticas fue inferior al alcanzado por las metaheurísticas propuestas.

A conventional approach to award public works audits supervised by the National Roads Institute in Colombia- INVIAS, is the open merits competitions (CMA’s). In this modality, the competitor must present a single portfolio of projects that allows him to quantitatively prove to the State Agency his experience. This project portfolio selection problem’s space grows in a factorial way, according to the increase in the total number of projects in participant’s work experience and there is no deterministic algorithm to find optimal solutions in polynomial times proportional to the instances which gives the problem a NP-Hard computational complexity. As an alternative to using exhaustive enumeration approaches with low performance formulated in Excel, the metaheuristics GA, GRASP and two heuristic validation rules were evaluated, for the case of study in a company with 207 experience career contracts. The evaluation results located the metaheuristic GA with the best performance’s alternative for its implementation, given its ability to find up to 10 portfolios with the highest score in less than 9 minutes. Moreover, the GRASP algorithm was able to find at least one optimal portfolio for different instances, while its ability to find more than one good solution in the test instances used, was lower than the one reached by the GA algorithm. For all the evaluation cases, the performance of heuristic validation rules was lower than that reached by the proposed metaheuristics.