<p>En el problema de transporte Dial-a-Ride Problem with Time Windows, se tiene un conjunto de solicitudes de transporte de personas desde un lugar de origen a un lugar de destino a través de una red de locaciones, bajo distintos tipos de restricciones, entre las que destacan principalmente las ventanas de tiempo y la capacidad limitada de los vehículos. La dificultad del problema (NP-Hard) ha impulsado la aplicación de heurísticas para su resolución. En este contexto, el uso de Algoritmos Genéticos en DARPTW no ha sido mayormente abordado, salvo estudios puntuales.</p><p>En el contexto de un DARPTW altamente restrictivo, en este trabajo se desarrollaron un par de modelos de GA: Uno está basado en la adaptación de un modelo genérico presentado en la literatura, llamado Linkage Learning Genetic Algorithm, mientras que el otro corresponde a una propuesta basada en operadores personalizados. De forma transversal a ambos modelos, se han aplicado técnicas de pre-procesamiento en los datos de entrada, con el fin de obtener información útil en lo que se refiere al manejo de restricciones del problema, y facilitando con ello la búsqueda de soluciones y utilización de operadores en un contexto factible. Los modelos fueron implementados, calibrados y testeados de forma adecuada al número de parámetros relevantes usados, junto con la utilización de pautas de comparación acorde a resultados presentados en otros estudios en la literatura.</p><p>Los resultados mostraron que el modelo basado en LLGA entrega mejoras interesantes en lo que se refiere al tiempo de ejecución del algoritmo, además que los dos modelos desarrollados en este estudio mejoraron en cierto nivel las prestancias de la calidad de servicio en las instancias testeadas. Estas comparaciones fueron hechas pensando en las diferencias respecto a los estudios comparados, ofreciendo nuevas alternativas de investigación: por un lado la posibilidad de tener más puntos de comparación en lo que se refiere a escenarios altamente restrictivos, y por otro la posibilidad de modificar los modelos de forma que las comparaciones puedan realizarse en un conjunto más homogéneo en lo que se refiere a las características del problema</p>
<p>On the Dial-a-Ride Problem with Time Windows, there are a set of requests from customers to be transported from a pickup point to a delivery point through a locations network, considering diverse constraints, including time windows and the limited vehicle capacity. The problem complexity (NP-Hard) has promoted the application of diverse heuristics to solve the problem. On this context, the use of Genetic Algorithms for DARPTW has not been largely considered, excepting for few researches.</p><p>On the context of a highly restricted DARPTW, two GA models have been developed for the problem: The first is adapted from a generic model presented in the literature: the Linkage Learning Genetic Algorithm. The second is based on a new set of proposed operators. Transversally to both models, a set of pre-processing techniques have been applied to the input data, to generate useful information in constraints manipulation, facilitating the solutions search and the application of the operators on a feasible context. The models were implemented, tuned and tested according to the relevant parameters considered, along with the use of evaluation patterns according to the results exposed on other researches from the literature.</p><p>The results reported that the LLGA based model offers interesting improvements in the execution times, also the two models developed in this research have improved the quality of service factors for the tested instances. Anyway, these comparisons consider the differences between the compared researches, offering new investigation approaches: on the one hand, a bigger comparison spectrum for highly restrictive instances of the problem, and on the other, the possibility of modifying the models to a more homogeneous approach in the problem characteristics</p>
last modification
Ingeniero de Ejecución en Informática
INGENIERIA DE EJECUCION INFORMATICA
<p>En el problema de transporte Dial-a-Ride Problem with Time Windows, se tiene un conjunto de solicitudes de transporte de personas desde un lugar de origen a un lugar de destino a través de una red de locaciones, bajo distintos tipos de restricciones, entre las que destacan principalmente las ventanas de tiempo y la capacidad limitada de los vehículos. La dificultad del problema (NP-Hard) ha impulsado la aplicación de heurísticas para su resolución. En este contexto, el uso de Algoritmos Genéticos en DARPTW no ha sido mayormente abordado, salvo estudios puntuales.</p><p>En el contexto de un DARPTW altamente restrictivo, en este trabajo se desarrollaron un par de modelos de GA: Uno está basado en la adaptación de un modelo genérico presentado en la literatura, llamado Linkage Learning Genetic Algorithm, mientras que el otro corresponde a una propuesta basada en operadores personalizados. De forma transversal a ambos modelos, se han aplicado técnicas de pre-procesamiento en los datos de entrada, con el fin de obtener información útil en lo que se refiere al manejo de restricciones del problema, y facilitando con ello la búsqueda de soluciones y utilización de operadores en un contexto factible. Los modelos fueron implementados, calibrados y testeados de forma adecuada al número de parámetros relevantes usados, junto con la utilización de pautas de comparación acorde a resultados presentados en otros estudios en la literatura.</p><p>Los resultados mostraron que el modelo basado en LLGA entrega mejoras interesantes en lo que se refiere al tiempo de ejecución del algoritmo, además que los dos modelos desarrollados en este estudio mejoraron en cierto nivel las prestancias de la calidad de servicio en las instancias testeadas. Estas comparaciones fueron hechas pensando en las diferencias respecto a los estudios comparados, ofreciendo nuevas alternativas de investigación: por un lado la posibilidad de tener más puntos de comparación en lo que se refiere a escenarios altamente restrictivos, y por otro la posibilidad de modificar los modelos de forma que las comparaciones puedan realizarse en un conjunto más homogéneo en lo que se refiere a las características del problema</p>
<p>On the Dial-a-Ride Problem with Time Windows, there are a set of requests from customers to be transported from a pickup point to a delivery point through a locations network, considering diverse constraints, including time windows and the limited vehicle capacity. The problem complexity (NP-Hard) has promoted the application of diverse heuristics to solve the problem. On this context, the use of Genetic Algorithms for DARPTW has not been largely considered, excepting for few researches.</p><p>On the context of a highly restricted DARPTW, two GA models have been developed for the problem: The first is adapted from a generic model presented in the literature: the Linkage Learning Genetic Algorithm. The second is based on a new set of proposed operators. Transversally to both models, a set of pre-processing techniques have been applied to the input data, to generate useful information in constraints manipulation, facilitating the solutions search and the application of the operators on a feasible context. The models were implemented, tuned and tested according to the relevant parameters considered, along with the use of evaluation patterns according to the results exposed on other researches from the literature.</p><p>The results reported that the LLGA based model offers interesting improvements in the execution times, also the two models developed in this research have improved the quality of service factors for the tested instances. Anyway, these comparisons consider the differences between the compared researches, offering new investigation approaches: on the one hand, a bigger comparison spectrum for highly restrictive instances of the problem, and on the other, the possibility of modifying the models to a more homogeneous approach in the problem characteristics</p>