Un'analisi comparativa dei crossover negli algoritmi genetici per l'ottimizzazione dei percorsi: casi di studio da Astana e Shymkent, Kazakistan

Perché le linee degli autobus più intelligenti sono importanti

Chiunque abbia aspettato troppo a una fermata dell'autobus o abbia fatto i conti con molte coincidenze sa che attraversare una città non riguarda solo la distanza. Due luoghi possono sembrare vicini su una mappa ma essere difficili da raggiungere se le linee giuste non li collegano. Questo articolo esplora come una classe di metodi di ricerca ispirati all'evoluzione — gli algoritmi genetici — possa essere sintonizzata per progettare percorsi di autobus migliori che rispettino le reti di trasporto reale in città come Astana e Shymkent in Kazakistan. Il lavoro si concentra su un ingrediente cruciale di questi algoritmi, chiamato fase di crossover, e mostra come una scelta oculata possa fare la differenza tra viaggi macchinosi e lunghi e percorsi rapidi e realistici.

Dalle mappe cittadine disordinate alla ricerca intelligente

I pianificatori di percorso tradizionali spesso trattano le città come se i viaggiatori potessero muoversi liberamente tra qualsiasi due punti, interessandosi solo alla distanza fisica. I sistemi reali degli autobus non funzionano così: si può andare solo dove effettivamente passano le linee, e ogni collegamento mancante o deviazione obbligata costa tempo e denaro. Gli autori modellano questa realtà rappresentando i luoghi importanti della città come punti, le strade e i collegamenti degli autobus come connessioni, e un viaggio completo come un percorso che visita ogni punto esattamente una volta. Stabilicono quindi un obiettivo in due parti: prima, evitare passi "illegali" dove non esiste un autobus diretto; secondo, tra i percorsi legali, scegliere quello con la distanza totale minore. Questo crea un puzzle difficile con molte possibili soluzioni, in cui valutare ogni opzione diventa rapidamente impossibile con l'aumentare della città.

Come l'evoluzione aiuta a trovare percorsi migliori

Gli algoritmi genetici affrontano questi problemi imitando la selezione naturale. Invece di provare un percorso alla volta, mantengono un'intera popolazione di percorsi candidati. In ogni generazione, i percorsi migliori sono favoriti e ne nascono di nuovi combinando e modificando leggermente quelli esistenti. Il passo chiave di mescolamento — il crossover — decide come i pezzi di due percorsi genitori vengono combinati in un nuovo percorso figlio. Per la pianificazione degli autobus questo passaggio è critico: ben fatto, trasmette schemi utili di fermate collegate; fatto male, può spezzare collegamenti e produrre percorsi che ignorano la rete di autobus. Gli autori testano nove diversi stili di crossover che variano nel modo in cui preservano l'ordine delle fermate, le posizioni esatte delle fermate o i collegamenti effettivi tra le fermate.

Testare molti modi di mescolare i percorsi

Per capire quali stili di crossover funzionano meglio, il team esegue una vasta batteria di esperimenti su dati di trasporto reale da Konya (una città di riferimento da lavori precedenti) e da Astana e Shymkent. Per ciascuna città selezionano 14 destinazioni importanti, le collegano alle fermate vicine e costruiscono tre tabelle dati chiave: distanze tra le località, quali coppie hanno un autobus diretto e penalità per tentare di viaggiare dove non passa alcun autobus. Esplorano quindi centinaia di impostazioni, variando la dimensione della popolazione, la frequenza con cui viene usato il crossover e quanto spesso si applicano piccole modifiche casuali (mutazioni). Per ogni configurazione ripetono l'algoritmo molte volte per tenere conto della casualità e misurano non solo quanto sono brevi i percorsi finali, ma anche quanto spesso il metodo trova qualsiasi percorso legale e con quale rapidità lo raggiunge.

La strategia vincente per viaggi realistici

In tutte e tre le città emerge uno stile di crossover in particolare: la ricombinazione degli archi (edge recombination). Diversamente dai metodi che si concentrano principalmente sull'ordine delle fermate, la ricombinazione degli archi presta attenzione a quali fermate sono direttamente collegate e cerca di preservare questi collegamenti quando costruisce nuovi percorsi. Lo studio mostra che questo approccio focalizzato sugli archi è molto più propenso a produrre viaggi percorribili in autobus, riscopre più spesso i percorsi realmente migliori conosciuti e di solito lo fa in poche generazioni. Un secondo stile, chiamato crossover basato sull'ordine, si comporta anch'esso bene ed è più veloce da calcolare, offrendo un buon compromesso quando sono necessari un grande numero di esecuzioni. Altri crossover comuni che riorganizzano le fermate in modo più aggressivo tendono a incontrare difficoltà, richiedendo più tempo e fornendo meno percorsi di alta qualità.

Cosa significa per gli spostamenti quotidiani

Per un lettore non specialista, il risultato è che la "ricetta" usata all'interno di un algoritmo genetico può avere un grande impatto su quanto bene progetta percorsi di autobus reali. Favorendo regole di crossover che mantengono intatti i collegamenti realistici pur esplorando nuove combinazioni, i pianificatori possono generare percorsi che rispettano la rete esistente e mantengono bassa la distanza totale di viaggio. Nei test su istantanee cittadine piccole ma realistiche, l'algoritmo genetico meglio sintonizzato non solo ha eguagliato percorsi trovati da metodi matematici esatti, ma lo ha fatto in modo rapido e affidabile. Questo suggerisce che, man mano che le città diventano più complesse e ricche di dati, una ricerca evolutiva attentamente progettata può aiutare le agenzie di trasporto a pianificare percorsi che si percepiscono più diretti, richiedono meno coincidenze scomode e sfruttano meglio veicoli e carburante.

Citazione: Kazbek, R., Sergaziyev, M., Kenzhe, D. et al. A comparative analysis of crossovers in genetic algorithms for route optimization: case studies from Astana and Shymkent, Kazakhstan. Sci Rep 16, 13816 (2026). https://doi.org/10.1038/s41598-026-43898-7

Parole chiave: instradamento del trasporto pubblico, algoritmi genetici, mobilità urbana, ottimizzazione dei percorsi, pianificazione di città intelligenti