Overview
An internal tool for a real operational headache: 18 supervisors, 104 schools scattered across the country, and the question of who should be responsible for which. Doing it by eye produces the obvious absurdities -; someone in Denver assigned a school in New Jersey. This program assigns schools to supervisors to minimize total travel, and draws the result on a map so you can see whether the answer is sane.
Background
It's a multiple-traveling-salesman problem wearing an assignment problem's clothes. You're not just routing one person; you're partitioning the schools among many people and routing each, with fairness and drive-time limits in the mix. The pragmatic move is to split it: cluster the schools geographically first, then solve the assignment cleanly, rather than try to do everything at once.
How It Works
Addresses for both supervisors and schools are geocoded and the pairwise driving distances come from the Google Maps Distance Matrix API (cached to a JSON file, because that API isn't free and the matrix doesn't change). On top of the distance matrix, the program runs several assignment strategies and compares them:
- Geographic Clustering -; K-means on school coordinates, one cluster per supervisor.
- Hungarian Hybrid -; the Hungarian algorithm (via SciPy's
linear_sum_assignment) for optimal cost-minimizing assignment. - Balanced Greedy, Greedy Original, and Simulated Annealing as comparison baselines.
The Hungarian step is the heart of it -; it finds the assignment that minimizes the total cost over the supervisor×school cost matrix:
Output is a set of per-strategy assignment CSVs, a strategy-comparison table, and interactive Folium maps -; including a marker-clustered view for dense regions and a GIS shapefile export of the assignment routes for anyone working in QGIS.
Current Status
Archived. The optimizer runs end to end on the real roster -; geocoding, distance matrix, all five strategies, comparison, and map/shapefile export. It did its job for the assignment it was built for.
- 18 supervisors, 104 schools, real addresses.
- Five assignment strategies with a side-by-side comparison.
- Folium maps and QGIS-ready shapefile output.