Resumen de Knapsack models applied to the solution of complex problems in transport planning
- español
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).
- English
This thesis has been developed during the competitive research projects aimed at promoting the use of mathematical optimization models for decision-making in complex contexts where there are often conflicting interests (such as those of users, transportation companies, and administration), multiple constraints (due to limited capacity, required availability of time windows to perform the offered service, or distance limitations to ensure service coverage), and exogenous variables (such as the user’s non-deterministic behavior in decision-making, traffic congestion episodes during peak hours, and the possibility of using intermodality in travels). Planning transportation within such complex contexts requires innovative formulations, which may be initially based on those that have proven effective and efficient in similar contexts, using both exact and heuristic models (including metaheuristics and matheuristics).
Location and transportation problems share a common origin in mathematical optimization, characterized by the use of variables of different nature (continuous, integer, or binary) to construct compatible objective functions, preferably with linear behavior. The versatility provided by the introduced decision variables allows representing the characteristic constraints present in such optimization models through algebraic manipulation. In addition to constraints, possible strategies to be followed by the involved agents (individual users, administration, or companies) can also be described through suitable algebraic expressions of those variables.
A paradigmatic optimization model due to its versatility to adapt to a large number of real contexts and its possibilities of extension (by adding new lines of constraint for solution searching, incorporating complementary levels of optimality and/or modifying the linearity of algebraic expressions) is the so-called knapsack problem (KP). In most of the proposed solutions to the analyzed problems in this thesis, the knapsack problems have been a useful tool for their formulation. This is why the thesis references this combinatorial optimization problem.
Regarding the real contexts analyzed from the perspective of mathematical optimization, we must admit that the academic center where the Ph.D. student has been trained (Department of Applied Mathematics of the Technical School of Architecture at the University of Seville) has had an undeniable influence:
- The design of fast transit lines has been approached from a novel perspective of acquiring a higher level of territorial cohesion, minimizing the need for mobility due to forced displacements caused by territorial imbalances.
- The search for solutions for the effective location of waste containers and the efficient deployment of selective collection routes has been complemented by the additional consideration of solidarity behavior by the user who, suitably motivated, could be willing to deposit their waste collection demand at a point different from the nearest one.
- The planning of non-habitual waste collection services through itinerant containers with multiple compartments (ecopoints) has been analyzed in a separate chapter, where optimization models have been formulated for different resolution strategies that have been compared in terms of efficiency.
- The deployment of electric charging stations based on the prior existence of a network of conventional gas stations is another problem addressed in this thesis, in which the perspective of the government administration has been contributed as a novelty, which requires that the number of charging points provide reinforced coverage to users who undertake a journey throughout the territory, and the business interests, selecting the most promising locations due to the flow of travel that passes through them.
- The restrictions on accessibility to current urban centers in private motor vehicles have been dealt with in another chapter of the thesis, providing a decision model for the optimal choice of a park-and-ride facility that combines criteria of distance to destination, travel times subject to traffic flow, possibility of using intermodality, and availability of free parking spaces.
- Finally, the management of waiting time for users at transport network nodes can generate interesting strategies for optimizing travel times, both in global terms (reducing the number of intermediate stops to favor the travel time of most passengers), and individual terms (waiting at a node for the arc that provides the exit from the node to be passable in a significantly shorter time).
