Knapsack models applied to the solution of complex problems in transport planning
- Francisco Alonso Ortega Riejos Director
Defence university: Universidad de Sevilla
Fecha de defensa: 15 May 2023
Type: Thesis
Abstract
Esta tesis se ha elaborado durante el desarrollo de proyectos de investigaci´on competitivos que tienen en com´un la promoci´on del uso de modelos matem´aticos de optimizaci´on para la toma de decisiones en ´ambitos de gran complejidad por la concurrencia de intereses diversos y, a menudo, contrapuestos (como los de los usuarios, las empresas de transporte y la administraci´on), la existencia de m´ultiples condicionantes (debidos a una capacidad limitada, la obligada disponibilidad de ventanas temporales para poder realizar el servicio ofertado o la limitaciones de distancia para garantizar la cobertura del servicio) y, por ´ultimo, la consideraci´on de variables ex´ogenas (como el comportamiento no determinista del usuario en su toma de decisi´on, la ocurrencia de episodios de congesti´on del tr´afico en horas punta, la posibilidad de utilizar intermodalidad en los desplazamientos). Los problemas en la planificaci´on del transporte dentro de estos ´ambitos de gran complejidad requieren de formulaciones novedosas, si bien pueden estar basadas inicialmente (o al menos, inspiradas) en aquellas que en contextos similares han demostrado eficacia y eficiencia, tanto desde la perspectiva del uso de modelos exactos como la proporcionada por medio de los heur´ısticos (incluyendo metaheur´ısticas y matheur´ısticas). Los problemas de localizaci´on y los de transporte comparten en sus formulaciones un origen com´un procedente del ´ambito de la optimizaci´on matem´atica, caracterizado por el uso de variables de naturaleza diversa (continua, entera o binaria) para construir funciones objetivo compatibles, preferentemente, con un comportamiento lineal. La versatilidad que proporcionan las variables de decisi´on introducidas permiten representar mediante manipulaci´on algebraica las restricciones caracter´ısticas que est´an presentes en tales modelos de optimizaci´on. Adem´as de las restricciones, es posible describir, tambi´en mediante adecuadas expresiones algebraicas de dichas variables, las posibles estrategias a seguir por parte de los agentes intervinientes (usuarios individuales, administraci´on o empresas). Un modelo de optimizaci´on paradigm´atico por su versatilidad en poderse adaptar a un gran n´umero de contextos reales y por sus posibilidades de extensi´on (a˜nadiendo nuevas l´ıneas de restricci´on para la b´usqueda de soluciones, incorporando niveles complementarios de optimalidad y/o modificando la linealidad de las expresiones algebraicas) es el denominado problema mochila (KP). En la mayor´ıa de las soluciones propuestas a los problemas analizados en esta tesis, los problemas mochila han constituido una herramienta ´util para su formulaci´on. Esta es la raz´on por la que en la memoria de tesis se hace referencia a dicho problema de optimizaci´on combinatoria. En cuanto a los contextos reales analizados desde la perspectiva de la optimizaci´on matem´atica, hemos de admitir que el centro docente donde el doctorando se ha formado (Departamento de Matem´atica Aplicada de la Escuela T´ecnica Superior de Arquitectura de la Universidad de Sevilla) ha tenido una innegable influencia: - El dise˜no de l´ıneas de tr´ansito r´apido se ha planteado desde una novedosa perspectiva consistente en adquirir un mayor nivel de cohesi´on territorial, minimizando la necesidad de la movilidad debida a desplazamientos obligados por la existencia de desequilibrios territoriales. - La b´usqueda de soluciones para la localizaci´on efectiva de contenedores de residuos y el despliegue eficiente de rutas de recogida de car´acter selectivo se ha complementado con la consideraci´on adicional de un comportamiento solidario por parte del usuario que, convenientemente motivado, podr´ıa estar dispuesto a depositar su demanda de recogida de residuos en un punto diferente al m´as cercano. - La planificaci´on de servicios de recogida de residuos no habituales mediante contenedores itinerantes de m´ultiples compartimentos (ecopuntos) se ha analizado en un cap´ıtulo separado, donde se han formulado modelos de optimizaci´on para diferentes estrategias de resoluci´on que han sido comparadas en t´erminos de eficiencia. - El despliegue de electrolineras basado en la previa existencia de una red de gasolineras convencionales es otro de los problemas abordados en esta tesis y en el que se ha aportado como novedad la concurrencia de la perspectiva de la administraci´on gubernamental, que exige que el n´umero de puntos de recarga el´ectrica proporcione una cobertura reforzada a los usuarios que emprendan un viaje a lo largo del territorio, y los intereses empresariales, seleccionando las localizaciones m´as prometedoras debido al flujo de viajes que pasa por ellas. - Las restricciones de accesibilidad a los actuales centros urbanos en veh´ıculos motorizados de uso privado han sido tratadas en otro de los cap´ıtulos de la tesis, aport´andose un modelo de decisi´on para la elecci´on ´optima de una instalaci´on park-and-ride que combina criterios de distancia a destino, tiempos de viaje sometidos a la fluidez del tr´afico, posibilidad de uso de intermodalidad y disponibilidad de plazas libres de aparcamiento. - Finalmente, la gesti´on del tiempo de espera de los usuarios en los nodos de la red de transporte puede generar interesantes estrategias para la optimizaci´on de tiempos de viaje, tanto en t´erminos globales (reduciendo el n´umero de paradas intermedias para favorecer el tiempo de recorrido de la mayor´ıa de los pasajeros), como individuales (aguardando en un nodo que el arco que proporcione la salida del nodo pueda ser transitable en un tiempo sensiblemente menor).