I chilometri a vuoto
Spazzare le strade dell'Oltrarno significa percorrerle tutte. Il resto sono chilometri a vuoto: il giro ottimo ne fa un terzo di quelli che farebbe un giro ragionevole.
- Metodo
- Rural Postman Problem risolto all'ottimo con tagli di connettività
- Strumenti
- Python, Gurobi, HiGHS, OSMnx
- Fonte dati
- Comune di Firenze — pulizia strade (ordinanze di spazzamento, Alia) · OpenStreetMap — grafo stradale (ODbL)
- Risultato
- −68% — i chilometri a vuoto per spazzare le stesse strade
Quasi tutti i problemi di percorso che si incontrano sono di visita: passare da un elenco di punti — clienti, cassonetti, pazienti — spendendo il meno possibile. Spazzare le strade è un’altra cosa. La domanda non sta nei punti, sta sugli archi: la spazzatrice deve percorrere tutta la strada da pulire, non passarci vicino.
E questo cambia la natura dell’ottimizzazione. I chilometri produttivi — la lunghezza delle strade da spazzare — sono fissi, non si possono ridurre. Tutto quello che si può guadagnare sta nei chilometri a vuoto: quelli fatti per andare da una strada da pulire alla successiva, con la spazzola alzata. È il problema del postino rurale, e per una volta si può risolvere su strade vere, perché Firenze pubblica le ordinanze di spazzamento ricondotte al grafo stradale.
Nell'Oltrarno, il giovedì notte, ci sono 3,69 km di strade da spazzare. Quanti chilometri deve percorrere in tutto la spazzatrice, nel giro migliore possibile?
Prova a dire una distanza
4,74 km
Poco più di un chilometro a vuoto. Un giro organizzato in modo ragionevole ma non ottimo ne farebbe più del triplo.
01La sfida
Prendiamo una tessera da un chilometro di lato nell’Oltrarno — la zona di Palazzo Pitti, Santa Felicita, via de’ Bardi — e il calendario del giovedì notte: 27 tratti di strada da spazzare, che sul grafo stradale diventano 73 archi per 3,69 chilometri complessivi.
La spazzatrice deve percorrere ogni arco richiesto almeno una volta, può attraversare qualunque altra strada per spostarsi, e alla fine deve tornare al punto di partenza. Si minimizza la distanza totale: siccome i 3,69 km da spazzare sono incomprimibili, minimizzare il totale equivale esattamente a minimizzare i chilometri a vuoto.
Il metro di paragone è il giro che verrebbe naturale a chiunque: finita una strada, si va a spazzare quella non ancora fatta più vicina, e così via.
02Gli ingredienti
- Le ordinanze di spazzamento del Comune di Firenze, gestite da Alia: 1.802 tratti di strada, ognuno con il giorno della settimana, la fascia oraria, il lato pari o dispari. Sono già ricondotte al grafo stradale IterNET, ed è questo che rende il caso possibile.
- Il grafo stradale vero su cui la spazzatrice si muove: la rete di OpenStreetMap della zona, presa con OSMnx — 18,35 km di strade, 290 incroci, 401 archi. Nel centro storico si tengono anche i vicoli pedonali e le zone a traffico limitato, perché anche quelli si spazzano.
- L’aggancio fra le due cose è geometrico, non per nome: un tratto spazzato viene attribuito agli archi OSM che ricopre. I nomi delle strade fiorentine sono un campo minato — «Borgo San Iacopo» contro «San Jacopo», «via dei Bardi» contro «via de’ Bardi» — e la geometria non ha queste ambiguità.
03Il verdetto
Produttivo contro a vuoto
Chilometri percorsi per spazzare le stesse strade, nell'Oltrarno del giovedì
Vedi i dati in tabella (km)
| Giro a naso | Giro ottimo | |
|---|---|---|
| Distanza totale | 6,95 | 4,74 |
| Chilometri a vuoto | 3,26 | 1,05 |
I chilometri spazzati sono identici nei due casi: cambia solo lo spreco.
Elaborazione su ordinanze del Comune di Firenze e grafo OpenStreetMap
Il giro ottimo percorre 4,74 chilometri per spazzarne 3,69: appena 1,05 chilometri a vuoto, il 22 per cento del totale. Il giro fatto andando ogni volta alla strada più vicina ne percorre 6,95, di cui 3,26 a vuoto — quasi la metà del lavoro è spostamento improduttivo.
Ottimizzare il percorso taglia i chilometri a vuoto del 68 per cento, a parità assoluta di strade pulite. Detta diversamente: la differenza fra una flotta che passa un quinto del suo tempo a spostarsi e una che ne passa quasi la metà.
Nello spazzamento non si può pulire di meno. Si può solo smettere di girare a vuoto, ed è lì che sta tutto il margine.
Il perché è visibile sulla mappa del caso: le strade da spazzare del giovedì formano già un reticolo quasi connesso, e i tratti a vuoto servono solo a cucire i pochi pezzi staccati e a sistemare le parità degli incroci. Un giro miope, invece, si accorge troppo tardi delle strade lasciate indietro e le paga con lunghi ritorni.
Il modello, per chi vuole la matematica
È un Rural Postman Problem: dato un grafo e un sottoinsieme R di archi richiesti, trovare il ciclo chiuso più corto che li percorre tutti. La variabile xe conta quante volte si percorre l’arco e.
min Σe ℓe xe
xe ≥ 1 per ogni arco richiesto e ∈ R
Σe ∈ δ(v) xe = 2 zv per ogni incrocio v
Σe ∈ δ(S) xe ≥ 2 connettività
Il secondo vincolo impone che ogni incrocio abbia grado pari: è la condizione di Eulero, e garantisce che il multigrafo percorso si possa davvero chiudere in un unico giro. Il terzo impedisce che la soluzione si spezzi in circuiti separati, ed è l’unico scomodo, perché le famiglie di insiemi S sono esponenziali. Non serve però generarle tutte: si risolve, si guarda se il grafo percorso è connesso, e se non lo è si aggiunge il taglio per la componente isolata e si risolve di nuovo. Bastano poche iterazioni.
Il vantaggio pratico di questo schema è che non richiede callback dal solutore: è una sequenza di modelli interi risolti da capo. Così lo stesso identico modello gira su Gurobi e, quando supera il tetto della licenza gratuita, viene riscritto in MPS e passato a HiGHS, open source. Alla fine la soluzione x si trasforma nel giro vero con un circuito euleriano.
04Dove il gioco finisce
Le strade sono trattate come archi non orientati: i sensi unici non entrano nel modello, e nemmeno il fatto che un viale largo vada spazzato una volta per lato. Un modello orientato — il postino «ventoso» — alzerebbe entrambe le cifre, probabilmente senza cambiare il rapporto fra le due. La rete di percorrenza è quella di OpenStreetMap, che può discostarsi in qualche punto dal grafo IterNET usato dal gestore. L’attribuzione dei tratti spazzati agli archi OSM avviene per sovrapposizione geometrica sopra il cinquanta per cento della lunghezza, quindi qualche tratto corto può sfuggire o entrare di troppo. Le lunghezze sono quelle geometriche degli archi, non il percorso effettivo della spazzola lungo il marciapiede. E l’istanza è una sola notte in un solo quartiere, scelta apposta perché si potesse chiudere all’ottimo dimostrato: una città intera si affronta partizionandola in zone come questa. Il risultato però non è fragile — su strade vere, con ordinanze vere, due terzi dei chilometri a vuoto sono evitabili.