Realización de un método de generación de columnas para resolver un problema operacional integrado de producción y distribución aplicado al proceso de quimioterapias a domicilio

Abstract

Este informe presenta una descripción del trabajo conjunto realizado con el centro de investigación INRIA en Lille, Francia bajo la supervisión de Maxime Ogier y Diego Cattaruzza. Dado que el cáncer representa una de las principales causas de muerte tanto en Francia como en Chile, se plantea avanzar en el desarrollo de una herramienta de ayuda a la toma de decisión en la realización de quimioterapias a domicilio. Debido a la alta perención de los medicamentos utilizados en dicho proceso, se plantea el desafío de integrar la producción de dichos medicamentos con el problema de trazado de rutas de vehículos. Dicho problema corresponde a un Problema Operacional Integrado (POI). Luego de una revisión bibliográfica del estado del arte de la resolución de POIs, se describe e implementa una metodología de Branch-and-Price basada en el paradigma de generación de columnas para la resolución del problema de distribución. Posteriormente, se describe el problema de producción de los medicamentos utilizados por los tratamientos de quimioterapia y se propone un modelo integrado en el cual se resuelven ambos problemas de forma conjunta. Las columnas que deben ser generadas para la resolución del POI, corresponden, por un lado a rutas de distribución realizadas por los enfermeros, los cuales visitan a los pacientes y, por otro lado a programas de producción que deben realizar los químico farmacéuticos, a los cuales se les asignan tareas de producción de medicamentos. Con el objetivo de evaluar la calidad de la solución propuesta, se proponen algoritmos de etiquetado para generar columnas acordes al nuevo modelo planteado y se generan resultados numéricos a partir de las instancias de Solomon. Ambos algoritmos son resueltos de forma heurística limitando la cantidad de etiquetas por nodo y se resuelven de forma exacta al final del método de generación de columnas. Para el caso del algoritmo de generación de rutas, 18 de las 29 instancias de 100 nodos cada una fueron resueltas de forma exacta dentro de 300 segundos. El algoritmo de generación de programas de producción, en 300 segundos, sólo fue capaz de resolver 4 de 29 instancias constituidas de los 15 primeros nodos de cada una de las instancias de Solomon. Debido a lo anterior, el POI fue resuelto tomando en cuanto solamente los 15 primeros nodos. De las 29 instancias probadas, 17 pudieron ser resueltas dentro de un tiempo límite de 3600 segundos. El algoritmo de etiquetado modificado para el trazado de rutas dentro de un contexto integrado resulta eficiente y es posible utilizarlo para instancias grandes. No obstante, el bajo rendimiento del algoritmo de pricing de programas utilizado durante el método de generación de columnas, resulta una limitación para la resolución del POI. Otros enfoques para resolver el problema de generación de programas deben ser estudiados para entregar una solución apta para un caso real.

The current dissertation presents the work performed in INRIA research centre located in Lille, France under the supervision of professors Maxime Ogier and Diego Cattaruzza. Since cancer is one of the main causes of death in France as well as in Chile, the development of a decision support model for the at-home chemotherapy process is described in this report. Due to short life constraints of the drugs used for this purpose, it is suggested the integration of the production process of these drugs with the vehicle routing problem. This problem corresponds to an Integrated Operational Problem (IOP). After a literature review of the state of the art for solving IOPs, a Branch-and-Price methodology based on the column generation paradigm is described and implemented for solving the distribution problem. Subsequently, the problem of drug production used by chemotherapy treatments is described and an integrated model is proposed in which both problems are solved simultaneously. The columns generated during the resolution of the IOP, correspond, on the one hand, to distribution routes performed by the nurses who visit the patients and, on the other hand, to production schedules that must be assigned to the pharmacists, to whom are assigned the tasks of drug production. In order to evaluate the quality of the proposed solution, two labelling algorithms are proposed to generate columns according to the new model. Numerical results are generated from Solomon instances. Both algorithms are solved limiting the quantity of labels per node making it a heuristic method. They are both solved exactly at the end of the column generation method. In the case of the route generation algorithm, 18 of the 29 instances of 100 nodes each were solved within 300 seconds. The production schedule generation algorithm, within 300 seconds, was only able to solve 4 of 29 instances of 15 nodes. Due to the above, the IOP was solved considering only the first 15 nodes. Among the 29 tested instances, 17 of them were solved within a time limit of 3600 seconds. The modified labelling algorithm for route generation within an integrated context resulted very efficient and may be used for large instances. However, the low performance of the pricing algorithm for scheduling used during the column generation method is a limitation for the resolution of the IOP. Different approaches to solve the scheduling problem should be studied to deliver a suitable solution for a real case.