I cassonetti di troppo
Nel Municipio I di Roma i contenitori per gli abiti usati sono novantadue. Cinquantasette coprirebbero esattamente lo stesso territorio — e chi li svuota potrebbe fare un quarto di strada in meno.
- Metodo
- Copertura massimale e set covering, più routing capacitato esatto
- Strumenti
- Python, Gurobi, HiGHS, OSRM
- Fonte dati
- Roma Capitale — contenitori per gli abiti usati georeferenziati (CC-BY) · OSRM — motore di calcolo percorsi su OpenStreetMap
- Risultato
- −28% — i chilometri per svuotare i contenitori, a parità di contenitori svuotati
Una rete di cassonetti stradali costa due volte. Costa quando la installi — e allora conta dove li metti, perché da lì dipende quanti metri deve fare il cittadino con la busta in mano. E costa ogni settimana, quando un mezzo passa a svuotarli: lì conta in che ordine li visiti, perché da lì dipendono i chilometri, il gasolio e le ore.
Sono due problemi classici della ricerca operativa — localizzazione e routing — e di solito restano teorici perché nessuno sa dove siano davvero i contenitori. Roma è un’eccezione: le coordinate dei 1.636 contenitori per gli abiti usati sono open data.
Nel Municipio I di Roma ci sono 92 contenitori per abiti usati. Quanti ne bastano per coprire esattamente lo stesso territorio, entro trecento metri a piedi?
Prova a dire un numero
57
Trentacinque contenitori, il 38% della rete, non aggiungono un metro quadro di copertura: stanno dentro il raggio di qualcun altro.
01La sfida
Prendiamo il Municipio I, il centro storico, e i suoi 92 contenitori. Due domande separate, due modelli.
La prima è di copertura: un residente è servito se ha un contenitore entro 300 metri a piedi. Con un budget di K contenitori scelti fra i siti esistenti, quanto territorio si copre al massimo? E, girando la domanda: qual è il numero minimo di contenitori che conserva tutta la copertura di oggi?
La seconda è di percorso: un mezzo con capacità limitata parte da un deposito, svuota i contenitori e torna indietro, tante volte quante servono. Qual è il giro più corto, sulle strade vere?
02Gli ingredienti
- I contenitori: 1.636 punti georeferenziati su quindici municipi, di cui 92 nel Municipio I. Il dato è del portale di Roma Capitale, con coordinate, via e municipio.
- Le distanze stradali fra deposito e contenitori, calcolate da OSRM sulla rete di OpenStreetMap: un mezzo non vola in linea d’aria, e nel centro di Roma i sensi unici pesano.
- La domanda di copertura è una griglia uniforme da 130 metri stesa sul territorio del municipio: misura la copertura territoriale, assumendo la popolazione distribuita in modo uniforme — un’ipotesi grossolana su cui torniamo alla fine.
03Il verdetto: dove metterli
La rete attuale copre il 46,8% del territorio del municipio entro trecento metri. Il numero sembra basso, e in parte lo è per un motivo tecnico — il perimetro considerato include il Tevere e le aree archeologiche, dove non abita nessuno e nessun cassonetto serve. Ma il risultato interessante non dipende da quel perimetro: cinquantasette contenitori conservano esattamente la stessa copertura, al metro. Gli altri trentacinque stanno dentro il raggio di trecento metri di un vicino, e potrebbero essere spostati dove oggi non c’è nulla senza che nessuno perda un servizio.
La curva della copertura
Territorio del Municipio I entro 300 metri da un contenitore, al crescere del numero di contenitori scelti in modo ottimo
Vedi i dati in tabella (%)
| Territorio coperto | |
|---|---|
| 5 | 7,9 |
| 10 | 15,4 |
| 15 | 22,4 |
| 20 | 29,1 |
| 30 | 38,6 |
| 40 | 44,0 |
| 60 | 46,8 |
| 92 (oggi) | 46,8 |
Quaranta contenitori ben piazzati raggiungono già il 94% di quello che ne coprono novantadue.
Elaborazione sui contenitori georeferenziati di Roma Capitale
La curva ha la forma tipica dei problemi di copertura: i primi contenitori valgono moltissimo, gli ultimi quasi nulla. Quaranta contenitori scelti bene arrivano al 94 per cento di quello che coprono tutti e novantadue. Da lì in poi si stanno pagando dei doppioni.
Una rete densa non è per forza una rete che copre. Trentotto cassonetti su cento, nel centro di Roma, coprono territorio che era già coperto.
04Il verdetto: come svuotarli
La seconda domanda è di percorso. Prendiamo un gruppo compatto di 30 contenitori, un mezzo che ne carica 12 per volta — quindi tre giri — e un deposito al margine della zona. Confrontiamo due modi di organizzare il lavoro: quello naturale, in cui si va sempre al contenitore non ancora svuotato più vicino, e quello ottimo.
Trenta contenitori, tre giri
Chilometri su strada reale: giro fatto a naso contro percorso ottimo
Vedi i dati in tabella (km)
| A naso (più vicino) | Ottimo (VRP) | |
|---|---|---|
| Distanza totale | 47,2 | 34,0 |
Tredici chilometri risparmiati su ogni tornata, a parità di contenitori svuotati.
Distanze stradali OSRM su OpenStreetMap
Il giro a naso fa 47,2 chilometri, il percorso ottimo 34: tredici chilometri in meno, il 28 per cento, per svuotare esattamente gli stessi trenta contenitori. L’euristica del «vado al più vicino» ha un difetto noto e visibile sulla mappa: parte benissimo e finisce malissimo, perché lascia indietro contenitori sparsi che poi obbligano a lunghi ritorni. L’ottimo, invece, taglia la zona in tre spicchi puliti.
Su una rete di 1.636 contenitori, svuotati più volte al mese, quel ventotto per cento non è un dettaglio: è gasolio, ore di lavoro e traffico in meno nel centro di una città.
I modelli, per chi vuole la matematica
La copertura è un Maximal Covering Location Problem: yj apre il contenitore j, zi segna il punto di domanda i come coperto,
max Σi zi t.c. zi ≤ Σj ∈ N(i) yj, Σj yj = K
dove N(i) sono i contenitori entro 300 metri. Il numero minimo che conserva la copertura attuale è invece un set covering: minimizzare Σ yj con Σj ∈ N(i) yj ≥ 1 per ogni punto oggi servito.
Il routing è un Capacitated Vehicle Routing Problem risolto all’ottimo dimostrato, non con un’euristica. Per restare compatto — e quindi risolvibile anche da un solutore open source — si usa la formulazione a flusso di singola merce (Gavish e Graves): oltre agli archi xij si introduce un flusso fij che cala di una unità a ogni contenitore visitato,
min Σij dij xij
Σi xij = 1, Σj xij = 1, Σj x0j = K
Σj fij − Σj fji = 1, fij ≤ Q · xij
Il flusso fa due lavori insieme: impone la capacità Q e impedisce i sottocicli, senza bisogno della famiglia esponenziale di tagli che rende il VRP ostico. Con 31 nodi il modello sta sotto il tetto della licenza Gurobi gratuita e si chiude in un attimo; le istanze più grandi passano in automatico a HiGHS.
05Dove il gioco finisce
La copertura è misurata su una griglia uniforme: dice quanto territorio è servito, non quante persone: nel centro di Roma la densità abitativa varia moltissimo, e il perimetro considerato include il fiume e le aree archeologiche, che abbassano la percentuale senza che nessuno ne soffra. Ogni contenitore è contato come un’unità di carico, perché i livelli di riempimento reali non sono pubblici: un modello pesato sul riempimento vero riordinerebbe i giri. Il deposito è convenzionale, messo al margine della zona. Le distanze OSRM sono a flusso libero e non modellano le soste né le manovre di svuotamento. E il gruppo di trenta contenitori è un singolo giro compatto, scelto perché il VRP si potesse chiudere all’ottimo dimostrato: una città intera si affronta spezzandola in zone come questa. Nulla di tutto ciò tocca i due numeri che contano: nel centro di Roma più di un terzo dei contenitori è ridondante, e chi li svuota guida un quarto di strada in più del necessario.