Cammini minimi multiobiettivo in reti di trasporto pubblico: Modelli e Algoritmi

Developing indices to measure transportation poverty in public transit networks requires algorithms capable of handling massive queries and non-linear fare rules. This thesis addresses these challenges by extending the Raptor algorithm with two key advancements. Firstly, to reduce the computational costs of repeated recalculations for the Earliest Arrival Problem, a warm-start strategy is introduced. The model reuses pre-calculated optimal journeys by applying spatio-temporal translation logic and a topological lower bound to prune the search space. The implementation on the Milan transit network achieved an average computational saving of over 23%. Secondly, the research tackles the price-optimal routing problem by adopting Conditional Fare Networks (CFNs), a mathematical framework capable of representing complex real-world fare rules. The architecture was validated by modeling Milan’s STIBM fare system using the McRAP algorithm. By subsequently integrating the Tight-BMRAP and Range-McRAP extensions, the model effectively manages the combinatorial explosion, guaranteeing exact Pareto-optimal solutions while significantly reducing running times by filtering redundant alternatives. Finally, we extend our results on translation and reuse criteria to complex fare networks, formally demonstrating how the warm-start approach can be generalized to compute optimal paths within non-additive domains.

Lo sviluppo di indici per misurare la transportation poverty nelle reti di trasporto pubblico richiede algoritmi capaci di gestire interrogazioni massive e regole tariffarie non lineari. Questa tesi affronta tali sfide estendendo l’algoritmo Raptor attraverso due contributi principali. In primo luogo, per abbattere i costi computazionali del ricalcolo continuo per l’Earliest Arrival Problem, viene introdotta una strategia di warm-start. Il modello riutilizza i viaggi ottimi pre-calcolati sfruttando logiche di traslazione spazio-temporale e un limite inferiore topologico per potare lo spazio di ricerca. L’implementazione sulla rete di Milano ha registrato un risparmio computazionale medio superiore al 23%. In secondo luogo, la ricerca affronta il problema dell’instradamento a prezzo ottimo adottando le Conditional Fare Networks (CFN), un framework matematico in grado di rappresentare le complesse regole tariffarie del mondo reale. L’architettura è stata validata modellando il sistema tariffario STIBM di Milano tramite l’algoritmo McRAP. Integrando successivamente le estensioni Tight-BMRAP e Range-McRAP, il modello gestisce efficacemente l’esplosione combinatoria, garantendo soluzioni Pareto-ottime esatte e riducendo significativamente i tempi di esecuzione tramite il filtraggio delle alternative ridondanti. Infine, estendiamo i nostri risultati sui criteri di traslazione e riuso alle reti tariffarie complesse, dimostrando formalmente come l’approccio warm-start possa essere generalizzato per il calcolo dei percorsi ottimi all’interno di domini non additivi.