Column Generation for the Micro-Transit Zoning Problem

Micro-transit services require carefully designed geo-fenced zones to operate effectively, but existing computational methods impose unrealistic constraints like fixed zone counts and suffer from scalability issues in larger cities. The innovation is applying Column Generation — a decomposition technique from operations research — to the zoning problem, which naturally handles the exponentially large space of candidate zones by generating only promising candidates guided by dual variables. This also enables a more realistic global budget formulation that reflects how transit agencies actually plan service areas.

This paper generalizes the Micro-Transit Zoning Problem to incorporate a global budget constraint on operational costs rather than a fixed limit on the number of zones. The work reformulates the problem into a Column Generation framework where candidate zones are generated iteratively through a pricing subproblem, and develops a scalable pricing heuristic that replaces exact integer programming with a greedy node-addition strategy. The approach is validated on real-world mobility data from five major U.S. cities including Chattanooga, where CARTA provided origin-destination trip data.

Experiments across Miami, Boston, Atlanta, Chattanooga, and Nashville demonstrate that the CG framework produces higher-quality solutions than the state-of-the-art two-phase enumeration approach while scaling more efficiently to larger cities. The pricing heuristic achieves near-optimal solution quality with dramatically reduced computation time, making the approach practical for real-world deployment. Additional analysis provides parameter tuning guidance for transit agencies adopting the method.