Optimisation Models in Bike Sharing Systems

Bike-sharing systems have become a central instrument of sustainable urban mobility, yet their service quality is persistently undermined by the spatial and temporal imbalance between bicycle supply and user demand: some stations run empty while others saturate, producing lost demand and avoidable operating cost. Correcting this imbalance---the Bike Rebalancing Problem (BRP)---is one of the most studied operational problems in shared mobility and lies at the intersection of vehicle routing and inventory management. This thesis develops Operations Research models and algorithms for the BRP and is organised around three studies that together span the field from a structured review to new static and dynamic formulations built around the notion of demand intervals. The first study is a review of the BRP from an Operations Research perspective. Starting from a screening of approximately 948 records, narrowed to 282 papers for full-text assessment and a final analytical corpus of 104 studies, it organises the literature through a unified six-tuple formalisation of the problem and a multi-dimensional taxonomy distinguishing planning horizon, demand representation, fleet structure, operational scope, and rebalancing paradigm. The synthesis shows that the static deterministic BRP is methodologically mature, whereas the dynamic, stochastic, and learning-based streams are more operationally relevant but remain fragmented by heterogeneous benchmarks and weak cross-paper comparability; it distils a focused research agenda that motivates the two methodological studies that follow. The second study addresses the Static Bike Rebalancing Problem with a single vehicle, station demand expressed as acceptability intervals, multiple visits to stations and to the depot, and a freely chosen initial vehicle load. Three rebalancing policies---non-split, without-preemption, and with-preemption---are captured within a single flow-based mixed-integer linear programming formulation. A structural equivalence theorem shows that, when the vehicle capacity is unbounded and the initial load is free, preemption yields no advantage, so its benefit is concentrated on capacity-tight instances. An Adaptive Iterated Granular Local Search metaheuristic, combining a nested dynamic programming routine with a Q($\lambda$)-guided perturbation, reproduces the exact optimum on all small random instances and scales to 200 stations within seconds, where the exact solver runs out of memory. The third study extends the interval-based perspective to the Dynamic Bike Rebalancing Problem. For each station and period, an inventory interval is derived from a continuous-time birth--death Markov model that bounds the combined risk of shortage and surplus, and these intervals are embedded in a multi-period mixed-integer program solved within a rolling-horizon scheme. Computational experiments on real data indicate that anticipating future demand over a longer look-ahead reduces realised lost demand relative to myopic single-period control, with diminishing returns as the horizon lengthens. Taken together, the three studies provide a coherent treatment of bike-sharing rebalancing in which demand intervals act as the unifying modelling device linking the static and dynamic settings, supported by scalable algorithms and validated on both real and synthetic data.

I sistemi di bike-sharing sono divenuti uno strumento centrale della mobilità urbana sostenibile; tuttavia, la qualità del servizio è costantemente compromessa dallo squilibrio spaziale e temporale tra l'offerta di biciclette e la domanda degli utenti: alcune stazioni si svuotano mentre altre si saturano, generando domanda persa e costi operativi evitabili. La correzione di tale squilibrio---il Bike Rebalancing Problem (BRP)---è uno dei problemi operativi più studiati nella mobilità condivisa e si colloca all'intersezione tra vehicle routing e inventory management. Questa tesi sviluppa modelli e algoritmi di Operations Research per il BRP ed è organizzata attorno a tre studi che, complessivamente, coprono il campo da una revisione strutturata a nuove formulazioni statiche e dinamiche basate sul concetto di intervalli di domanda. Il primo studio è una revisione del BRP da una prospettiva di Operations Research. A partire da uno screening di circa 948 record, ridotti a 282 articoli per la valutazione del full text e a un corpus analitico finale di 104 studi, la letteratura viene organizzata mediante una formalizzazione unificata del problema in sei elementi e una tassonomia multidimensionale che distingue orizzonte di pianificazione, rappresentazione della domanda, struttura della flotta, ambito operativo e paradigma di riequilibrio. La sintesi mostra che il BRP statico deterministico è metodologicamente maturo, mentre i filoni dinamico, stocastico e basato su apprendimento sono più rilevanti dal punto di vista operativo ma restano frammentati da benchmark eterogenei e da una scarsa comparabilità tra studi; ne emerge un'agenda di ricerca mirata che motiva i due studi metodologici successivi. Il secondo studio affronta lo Static Bike Rebalancing Problem con un singolo veicolo, domanda di stazione espressa tramite intervalli di accettabilità, visite multiple alle stazioni e al deposito, e un carico iniziale del veicolo liberamente scelto. Tre politiche di riequilibrio---non-split, without-preemption e with-preemption---sono rappresentate in un'unica formulazione di programmazione lineare intera mista basata su flussi. Un teorema di equivalenza strutturale mostra che, quando la capacità del veicolo è illimitata e il carico iniziale è libero, la preemption non apporta alcun vantaggio; il suo beneficio si concentra dunque sui casi con capacità vincolata. Un metaeuristico Adaptive Iterated Local Search, che combina una procedura di programmazione dinamica annidata con una perturbazione guidata da Q($\lambda$), riproduce l'ottimo esatto su tutte le istanze random di piccola dimensione e scala fino a 200 stazioni in pochi secondi, laddove il risolutore esatto esaurisce la memoria. Il terzo studio estende la prospettiva basata sugli intervalli al Dynamic Bike Rebalancing Problem. Per ciascuna stazione e per ogni periodo, viene derivato un intervallo di inventario da un modello markoviano continuo di nascita--morte che fornisce un limite congiunto al rischio di scarsità e di surplus; tali intervalli vengono poi incorporati in un programma intero misto multi-periodo risolto mediante uno schema a orizzonte mobile. Gli esperimenti computazionali su dati reali indicano che anticipare la domanda futura con un orizzonte di previsione più lungo riduce la domanda persa realizzata rispetto a un controllo miope a un solo periodo, con rendimenti decrescenti al crescere della lunghezza dell'orizzonte. Nel loro insieme, i tre studi offrono un trattamento coerente del riequilibrio nei sistemi di bike-sharing, in cui gli intervalli di domanda fungono da dispositivo modellistico unificante che collega i contesti statico e dinamico, sostenuto da algoritmi scalabili e validato su dati reali e sintetici.