Column Generation for the Micro-Transit Zoning Problem

Hins Hu, Rishav Sen, Jose Paolo Talusan, Abhishek Dubey, Aron Laszka, Samitha Samaranayake

Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence, IJCAI-26 2026

AI and Social Good

PDF DOI

Why This Matters

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.

What We Did

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.

Key Results

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.

Full Abstract

Cite This Paper

@inproceedings{hu2026columngenerationmicrotransitzoning,
  title = {Column Generation for the Micro-Transit Zoning Problem},
  author = {Hu, Hins and Sen, Rishav and Talusan, Jose Paolo and Dubey, Abhishek and Laszka, Aron and Samaranayake, Samitha},
  booktitle = {Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence, {IJCAI-26},
  publisher = {International Joint Conferences on Artificial Intelligence Organization},
  editor = {Calvanese, Diego},
  pages = {7219--7228},
  year = {2026},
  month = {aug},
  note = {AI and Social Good},
  doi = {10.24963/ijcai.2026/803},
  url = {https://doi.org/10.24963/ijcai.2026/803},
  eprint = {2603.07821},
  archiveprefix = {arXiv},
  primaryclass = {math.OC},
  abstract = {Along with the rapid development of new urban mobility options like ride-sharing over the past decade, on-demand micro-transit services stand out as a middle ground, bridging the gap between fixed-line mass transit and single-request ride-hailing, balancing ridership maximization and travel time minimization. However, effective operation of micro-transit services requires planning geo-fenced zones in advance, which involves solving a challenging combinatorial optimization problem. Existing approaches enumerate candidate zones first and select a fixed number of optimal zones in the second step. In this paper, we generalize the Micro-Transit Zoning Problem (MZP) to allow a global budget rather than imposing a size limit for candidate zones. We also design a Column Generation (CG) framework to solve the problem and several pricing heuristics to accelerate computation. Extensive numerical experiments across major U.S. cities demonstrate that our approach produces higher-quality solutions more efficiently and scales better in the generalized setting.},
  keywords = {micro-transit, zoning, column generation, combinatorial optimization, urban mobility, demand-responsive transit, public transportation},
  month_numeric = {8}
}
Quick Info
Year 2026
DOI 10.24963/ijcai.2026/803
Keywords
micro-transit zoning column generation combinatorial optimization urban mobility demand-responsive transit public transportation
Research Areas
transit planning
Search Tags

Column, Generation, Micro, Transit, Zoning, Problem, micro-transit, zoning, column generation, combinatorial optimization, urban mobility, demand-responsive transit, public transportation, transit, planning, 2026, Hu, Sen, Talusan, Dubey, Laszka, Samaranayake