Column Generation for the Micro-Transit Zoning Problem

• URL: http://arxiv.org/abs/2603.07821v1
• Date: Sun, 08 Mar 2026 21:42:29 GMT
• Title: Column Generation for the Micro-Transit Zoning Problem
• Abstract summary: On-demand micro-transit services can bridge the gap between fixed-line mass transit and single-request ride-hailing.<n>Effective operation of micro-transit services requires planning geo-fenced zones in advance.<n>This paper generalizes the Micro-Transit Zoning Problem (MZP) to allow a global budget rather than imposing a size limit for candidate zones.
• Score: 8.783715393635992
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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. Micro-transit adoption can have significant social impact. It improves urban sustainability, through lower energy consumption and reduced emissions, while enhancing equitable mobility access for disadvantaged communities, thanks to its lower vehicle miles per passenger, flexible schedules, and affordable pricing. 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 selects 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.

Related papers

• Public transit gains and spatially uneven travel demand changes after NYC congestion pricing [9.391171271059862]
  New York City implemented the nation's first cordon-based congestion pricing program in January 2025.<n>We use time series foundation models to generate probabilistic counterfactual demand forecasts with calibrated uncertainty.<n>We find that post-policy bus and subway ridership increased significantly relative to expected no-policy demand, while overall travel demand decreased modestly.
  arXiv  Detail & Related papers  (2026-06-16T05:14:23Z)
• Grid-Aware Charging and Operational Optimization for Mixed-Fleet Public Transit [11.618218411493478]
  Mixed transit fleets consisting of both electric and diesel buses pose significant operational challenges.<n>This paper presents a comprehensive mixed-integer linear programming (MILP) model to address these challenges.<n>We show that our approach can result in significant savings in the operating costs of the mixed transit fleets.
  arXiv  Detail & Related papers  (2026-01-13T17:30:25Z)
• TourPlanner: A Competitive Consensus Framework with Constraint-Gated Reinforcement Learning for Travel Planning [44.656702093210924]
  TourPlanner is a comprehensive framework featuring multi-path reasoning and constraint-gated reinforcement learning.<n>We show that TourPlanner achieves state-of-the-art performance, significantly surpassing existing methods in both feasibility and user-preference alignment.
  arXiv  Detail & Related papers  (2026-01-08T08:08:35Z)
• Resilient Charging Infrastructure via Decentralized Coordination of Electric Vehicles at Scale [37.56003520528009]
  Existing decentralized approaches struggle under severe contingencies, such as station outages or unexpected surges in charging requests.<n>We propose a novel collective learning-based coordination framework that allows EVs to balance individual comfort on their selections against system-wide efficiency.<n>In the framework, EVs are recommended for adaptive charging behaviors that shift priority between comfort and efficiency.
  arXiv  Detail & Related papers  (2025-11-26T00:32:23Z)
• Scalable Ride-Sourcing Vehicle Rebalancing with Service Accessibility Guarantee: A Constrained Mean-Field Reinforcement Learning Approach [42.070187224580344]
  We introduce continuous-state mean-field control (MFC) and mean-field reinforcement learning (MFRL) models that employ continuous vehicle repositioning actions.<n>MFC and MFRL offer scalable solutions by modeling each vehicle's behavior through interaction with the vehicle distribution, rather than with individual vehicles.<n>Our approach scales to tens of thousands of vehicles, with training times comparable to the decision time of a single linear programming rebalancing.
  arXiv  Detail & Related papers  (2025-03-31T15:00:11Z)
• Optimal Ground Station Selection for Low-Earth Orbiting Satellites [36.896695278624776]
  This paper presents a solution to the problem of optimal ground station selection for low-Earth orbiting (LEO) space missions.<n>It enables mission operators to precisely design their ground segment performance and costs.
  arXiv  Detail & Related papers  (2024-10-04T22:48:50Z)
• Designing Optimal Personalized Incentive for Traffic Routing using BIG Hype algorithm [3.7597202216941783]
  We study the problem of optimally routing plug-in electric and conventional fuel vehicles on a city level. In our model, commuters selfishly aim to minimize a local cost that combines travel time, and the monetary cost of using city facilities, parking or service stations. We formalize the problem of designing these monetary incentives optimally as a large-scale bilevel game.
  arXiv  Detail & Related papers  (2023-04-24T11:13:10Z)
• Equity Promotion in Public Transportation [18.057286025603055]
  We propose an optimization model to study how to integrate the two approaches together for equity-promotion purposes. We have designed a linear-programming (LP) based rounding algorithm, which proves to achieve an optimal approximation ratio of 1-1/e. Experimental results confirm our theoretical predictions and demonstrate the effectiveness of our LP-based strategy in promoting social equity.
  arXiv  Detail & Related papers  (2022-11-26T10:06:00Z)
• Transit facility allocation: Hybrid quantum-classical optimization [0.0]
  Transit facility consolidation is a cost-effective way to improve the quality of service. This paper develops an optimization framework that integrates GIS, decision-making analysis, and quantum technologies. We demonstrate the effectiveness of our framework by reducing the number of facilities by 40% while maintaining the same service accessibility.
  arXiv  Detail & Related papers  (2022-10-22T21:53:00Z)
• Real-time and Large-scale Fleet Allocation of Autonomous Taxis: A Case Study in New York Manhattan Island [14.501650948647324]
  Traditional models fail to efficiently allocate the available fleet to deal with the imbalance of supply (autonomous taxis) and demand (trips) We employ a Constrained Multi-agent Markov Decision Processes (CMMDP) to model fleet allocation decisions. We also leverage a Column Generation algorithm to guarantee the efficiency and optimality in a large scale.
  arXiv  Detail & Related papers  (2020-09-06T16:00:15Z)
• FlexPool: A Distributed Model-Free Deep Reinforcement Learning Algorithm for Joint Passengers & Goods Transportation [36.989179280016586]
  This paper considers combining passenger transportation with goods delivery to improve vehicle-based transportation. We propose FlexPool, a distributed model-free deep reinforcement learning algorithm that jointly serves passengers & goods workloads. We show that FlexPool achieves 30% higher fleet utilization and 35% higher fuel efficiency in comparison to model-free approaches.
  arXiv  Detail & Related papers  (2020-07-27T17:25:58Z)
• Polestar: An Intelligent, Efficient and National-Wide Public Transportation Routing Engine [43.09401975244128]
  We present Polestar, a data-driven engine for intelligent and efficient public transportation routing. Specifically, we first propose a novel Public Transportation Graph (PTG) to model public transportation system in terms of various travel costs. We then introduce a general route search algorithm coupled with an efficient station binding method for efficient route candidate generation. Experiments on two real-world data sets demonstrate the advantages of Polestar in terms of both efficiency and effectiveness.
  arXiv  Detail & Related papers  (2020-07-11T05:14:52Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.