Design, management, and simulation of mixed station-based and free-floating vehicle-sharing systems

Abstract

(English) This thesis provides tools, based on mathematical modelling, for the analysis, optimization and simulation, of vehicle-sharing systems. The thesis addresses various implementation levels of such systems, from their planning and design to their operational management. Specifically, the problems addressed can be grouped into two blocks. The first block focuses on the strategical design of vehicle-sharing systems. This is, the long-term planning and the sizing of the fundamental elements of the system, namely: the fleet size, the required infrastructure, and the personnel. The second block, analyzes the day-to-day operational problems of systems already in operation and whose main design characteristics are known. Specifically, the optimization problem in the repositioning task assignment, is addressed. The thesis develops solutions for the aforementioned problems trying to find an adequate balance between the mathematical complexity of the models and the level of detail and accuracy of the solutions. Parsimonious solutions are sought, aiming at facilitating its implementation in real systems with limited resources. Parsimonious models require modelling simplifications. This is the price to pay when modelling complex and advanced systems. This modelling philosophy has guided the most significant contribution of this thesis: the design and optimization models depicting mixed vehicle-sharing systems, with both free-floating and station-based layouts working simultaneously and complementing each other. The modelling of such systems represents an important milestone in the research on the strategical planning of vehicle-sharing systems. For the strategical design problem, simplification has been achieved by using the method of continuous approximations. This allows the estimation of the costs and the causal effects of the decision variables in the system, without the need to solve computationally costly models. This simplification has provided sufficiently accurate and robust results, and has also allowed the development of a hitherto unexplored model for mixed vehicle-sharing systems, in which free-floating and vehicles in stations are used indistinctly. The optimization of this model and its subsequent analysis of results tells us under which circumstances it is more convenient to opt for a free-floating configuration, for a station-based one, or for a mixed system. Regarding the day-to-day operational problems in the second block of the thesis, simplification is achieved by avoiding the common optimal routing solutions, based on mixed integer linear programming models. The proposed approach in the thesis is based on the optimal real-time pairwise matching of tasks to resources. The idea is to obtain a strategy less dependent on demand forecasts, since the assignment occurs in real time. This avoids the estimation of the future vehicle inventory level at stations. Results obtained by simulation show that the real-time optimal pairwise assignment strategy generally works better, unless the accuracy of the predictions is extremely high, which typically is unlikely. These results have been obtained thanks to the ad-hoc development of an agent-based simulator for vehicle-sharing systems, able to emulate the complex operation of mixed systems, with vehicles both free-floating and in stations, including the possibility of using electric vehicles. The simulator also allows to establish different priority levels for repositioning operations (e.g. recharging and relocation). The development of this simulator culminates the second block of the thesis. With all this, the thesis presents a complete framework of tools which will help in the optimal design and operation of mixed vehicle-sharing systems, being the first time that this kind of systems are addressed at this level in the academic literature.

(Català) Aquesta tesi proveeix d'eines, basades en la modelització matemàtica, per a l'anàlisi, optimització i simulació de sistemes de vehicles compartits. La tesi tracta diversos nivells d'implementació d'aquests sistemes, des de la seva fase de planificació i disseny fins a la seva gestió operativa. Concretament, els problemes tractats es poden agrupar en dos blocs. El primer bloc posa focus en el disseny estratègic de sistemes de vehicle compartit. És a dir, la planificació a llarg termini i dimensionament dels seus elements fonamentals: flota, infraestructura, i personal. El segon bloc considera els problemes operacionals del dia a dia de sistemes ja posats en funcionament i els principals elements del qual són coneguts. Específicament, es tracta el problema de l'assignació òptima de tasques de reposicionament. La tesi desenvolupa solucions per als problemes esmentats tractant de trobar un equilibri adequat entre la complexitat matemàtica del model i el nivell de detall i encert de les solucions. Per a trobar aquestes solucions, s'han utilitzat models parsimoniosos amb l'objectiu de facilitar la seva implementació en sistemes reals amb recursos limitats. Els models parsimoniosos requereixen simplificacions com a preu a pagar al modelitzar sistemes complexos i avançats. Però a canvi aquesta filosofia de modelització ha guiat cap a la contribució més significativa de la tesi: la introducció de models de disseny i optimització per a sistemes mixtos de vehicles compartits, en els quals es contemplen tant vehicles de flota lliure com en estacions i que funcionen indistintament i es complementen. La modelització d'aquests sistemes mixtos suposa un important assoliment en la recerca de la planificació estratègica de sistemes de vehicles compartits. Per al cas de l'optimització del disseny estratègic del sistema, la simplificació s'ha aconseguit implementant la metodologia de les aproximacions contínues. Això permet l'estimació del cost i efectes de les variables de decisió del sistema sense necessitat de resoldre models computacionalment costosos. Aquesta simplificació ha ofert resultats prou exactes i robustos, i a més ens ha permès desenvolupar un model de disseny fins ara inexplorat per a sistemes mixtos de vehicle compartit, en el qual vehicles de flota lliure i en estacions s'usen indistintament. L'optimització d'aquest model i la seva posterior anàlisi de resultats ens indica sota quines circumstàncies és més convenient optar per un sistema de flota lliure, amb estacions, o mixt. Respecte als problemes d'operativa diària del segon bloc de la tesi, la simplificació s'aconsegueix evitant les solucions comunes d'optimització de rutes basades en models de programació mixta lineal i sencera. La solució proposada en la tesi es basi en canvi en l'aparellament òptim en temps real de tasques i recursos. La idea és obtenir una estratègia menys dependent de les prediccions de demanda. Això evita la necessitat d'estimar el nivell d'inventari de les estacions a futur. Els resultats obtinguts mitjançant simulació mostren que l'estratègia d'aparellament òptim funciona millor per regla general, tret que l'encert de les prediccions sigui altíssim, la qual cosa és poc freqüent. Aquests resultats han estat obtinguts gràcies al desenvolupament ad hoc d'un simulador basat en agents de sistemes de vehicle compartit, capaç d'emular les operacions complexes dels sistemes mixtos, i incloent la possibilitat d'usar vehicles elèctrics. El simulador també ha permès establir diferents nivells de prioritat per a les operacions de reposicionament (p. ex. recàrrega i recol·locació). Aquest simulador culmina el segon bloc de la tesi. Amb tot això, aquesta tesi presenta un marc complet d'eines que ajudaran en l'optimització del disseny i operació de sistemes mixtos de vehicles compartits, sent la primera vegada que aquest tipus de sistemes són tractats a aquest nivell en la literatura acadèmica.

(Español) Esta tesis provee de herramientas, basadas en la modelización matemática, para el análisis, optimización y simulación de sistemas de vehículos compartidos. La tesis trata varios niveles de implementación de estos sistemas, desde su fase de planificación y diseño hasta su gestión operativa. Concretamente, los problemas tratados se pueden agrupar en dos bloques. El primer bloque pone foco en el diseño estratégico de sistemas de vehículo compartido. Es decir, la planificación a largo plazo y dimensionamiento de sus elementos fundamentales: flota, infraestructura, y personal. El segundo bloque considera los problemas operacionales del día a día de sistemas ya puestos en funcionamiento y cuyos principales elementos son conocidos. Específicamente, se trata el problema de la asignación óptima de tareas de reposicionamiento. La tesis desarrolla soluciones para los problemas mencionados tratando de encontrar un equilibrio adecuado entre la complejidad matemática del modelo y el nivel de detalle y acierto de las soluciones. Se han utilizado modelos parsimoniosos con el objetivo de facilitar su implementación en sistemas reales con recursos limitados. Los modelos parsimoniosos requieren simplificaciones como precio a pagar al modelizar sistemas complejos y avanzados. Pero a cambio esta filosofía de modelización ha guiado hacia la contribución más significativa de la tesis: la introducción de modelos de diseño y optimización para sistemas mixtos de vehículos compartidos, en los cuales se contemplan tanto vehículos de flota libre como en estaciones y que funcionan indistintamente y se complementan. La modelización de estos sistemas mixtos supone un importante logro en la investigación de la planificación estratégica de sistemas de vehículos compartidos. En cuanto al diseño estratégico del sistema, la simplificación se ha conseguido implementando la metodología de las aproximaciones continuas. Esto permite la estimación del coste y efectos de las variables de decisión del sistema sin necesidad de resolver modelos computacionalmente costosos. Esta simplificación ha ofrecido resultados suficientemente exactos y robustos, y además nos ha permitido desarrollar un modelo de diseño hasta ahora inexplorado para sistemas mixtos de vehículo compartido, en el que vehículos de flota libre y en estaciones se usan indistintamente. La optimización de ese modelo y su posterior análisis de resultados nos indica bajo qué circunstancias es más conveniente optar por un sistema de flota libre, con estaciones, o mixto. Con respecto a los problemas de operativa diaria del segundo bloque de la tesis, la simplificación se consigue evitando las soluciones comunes de optimización de rutas basadas en modelos de programación mixta lineal i entera. La solución propuesta en la tesis se basa en el emparejamiento óptimo en tiempo real de tareas y recursos. La idea es obtener una estrategia menos dependiente de las predicciones de demanda. Esto evita la estimación del nivel de inventario de las estaciones a futuro. Los resultados obtenidos mediante simulación muestran que la estrategia de emparejamiento óptimo funciona mejor por regla general, salvo que el acierto de las predicciones sea altísimo, lo cual es poco frecuente. Estos resultados han sido obtenidos gracias al desarrollo ad-hoc de un simulador basado en agentes de sistemas de vehículo compartido, capaz de emular las operaciones complejas de los sistemas mixtos, e incluyendo la posibilidad de usar vehículos eléctricos. El simulador también ha permitido establecer distintos niveles de prioridad para las operaciones de reposicionamiento (p.ej. recarga y recolocación). Este simulador culmina el segundo bloque de la tesis. Con todo esto, esta tesis presenta un marco completo de herramientas que ayudarán en la optimización del diseño y operación de sistemas mixtos de vehículos compartidos, siendo la primera vez que este tipo de sistemas son tratados a este nivel en la literatura académica.