Il giro del vetro
Ottantaquattro campane, quattro giri a settimana, troppi chilometri. La raccolta del vetro ripensata come un problema di rotte.
- Metodo
- Vehicle Routing Problem (VRP)
- Strumenti
- Python, OR-Tools, OpenStreetMap
- Fonte dati
- Open data comunali — posizione contenitori · OpenStreetMap
- Risultato
- −18% — chilometri percorsi ogni settimana
Ogni raccolta differenziata nasconde un problema di ottimizzazione combinatoria in piena regola. Il nostro primo numero parte da qui: un comune di circa quindicimila abitanti, 84 campane del vetro, un solo mezzo, quattro giri a settimana. I percorsi attuali sono nati per “zone storiche” — il centro il lunedì, la zona industriale il mercoledì — e nessuno li ha più rimessi in discussione.
01Il problema
Trovare, a parità di tutto il resto (stesso mezzo, stessa frequenza di svuotamento, stesso deposito di partenza), i quattro giri che minimizzano i chilometri totali. È un Vehicle Routing Problem: la generalizzazione del commesso viaggiatore in cui i punti da visitare vanno anche ripartiti fra i giri.
02I dati
Due fonti, entrambe aperte:
- il portale open data comunale pubblica l’elenco dei contenitori con le coordinate — è un dataset che ormai moltissimi comuni espongono;
- OpenStreetMap fornisce il grafo stradale, da cui calcoliamo la matrice delle distanze reali (non in linea d’aria) fra tutte le coppie di campane.
03Il modello
Ottantaquattro punti sono troppi per l’ottimo esatto in tempi umani, e va benissimo così: OR-Tools costruisce una soluzione iniziale golosa e la raffina con ricerca locale (2-opt e mosse di scambio fra giri), con un vincolo di capacità per giro.
from ortools.constraint_solver import pywrapcp, routing_enums_pb2
gestore = pywrapcp.RoutingIndexManager(len(distanze), 4, deposito)
rotte = pywrapcp.RoutingModel(gestore)
def costo(da, a):
return distanze[gestore.IndexToNode(da)][gestore.IndexToNode(a)]
rotte.SetArcCostEvaluatorOfAllVehicles(rotte.RegisterTransitCallback(costo))
parametri = pywrapcp.DefaultRoutingSearchParameters()
parametri.local_search_metaheuristic = (
routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH)
parametri.time_limit.FromSeconds(30)
soluzione = rotte.SolveWithParameters(parametri)
Trenta secondi di calcolo su un portatile.
04I risultati
Quattro giri, tutti più corti
Chilometri per giro settimanale, prima e dopo l'ottimizzazione
Vedi i dati in tabella (km)
| Percorsi storici | Percorsi ottimizzati | |
|---|---|---|
| Giro del lunedì | 58 | 47 |
| Giro del mercoledì | 55 | 46 |
| Giro del venerdì | 52 | 43 |
| Giro del sabato | 47 | 38 |
Stesse 84 campane, stesso mezzo, stessa frequenza di svuotamento.
Elaborazione su open data comunali e OpenStreetMap (caso esemplificativo)
La cosa interessante è dove il modello guadagna: quasi mai dentro i quartieri, quasi sempre ai confini. Le zone storiche tagliavano la città con linee amministrative; il solutore le ricuce lungo le strade vere, spostando una dozzina di campane “di frontiera” dal giro sbagliato a quello giusto.
I confini disegnati per abitudine sono il primo posto dove cercare chilometri sprecati.
05I limiti
Il conto è fatto a domanda costante: se le campane si riempiono a velocità molto diverse fra loro, il passo successivo è un modello con frequenze differenziate — che è poi il seguito naturale di questo caso. Circa duemila chilometri l’anno risparmiati valgono, a costi pieni di esercizio, qualche migliaio di euro: non cambia un bilancio comunale, ma è gratis, e la stessa ricetta si applica a spazzamento, verde pubblico, scuolabus.