Column Generation for the Micro-Transit Zoning Problem
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Latent Zoning Network: A Unified Principle for Generative Modeling, Representation Learning, and Classification
Generative modeling, representation learning, and classification are three core problems in machine learning (ML), yet their state-of-the-art (SoTA) solutions remain largely disjoint. In this paper, we ask: Can a unified…
Conditional Image GenerationRepresentation LearningImplications of Zoning Ordinances for Rural Utility-Scale Solar Deployment and Power System Decarbonization in the Great Lakes Region
Local zoning ordinances across the United States have the impact of restricting development of energy infrastructure, including utility-scale solar photovoltaics. While these ordinances may be developed for legitimate pu…
Efficient Column Generation for Cell Detection and Segmentation
We study the problem of instance segmentation in biological images with crowded and compact cells. We formulate this task as an integer program where variables correspond to cells and constraints enforce that cells do no…
Cell DetectionInstance SegmentationSegmentationSemantic SegmentationOn an exact method for the constrained shortest path problem
The constrained shortest path (CSP) is a well known NP-Hard problem. Besides from its straightforward application as a network problem, the CSP is also used as a building block under column-generation solution methods fo…
SchedulingIncorporating Zoning Information into Argument Mining from Biomedical Literature
The goal of text zoning is to segment a text into zones (i.e., Background, Conclusion) that serve distinct functions. Argumentative zoning, a specific text zoning scheme for the scientific domain, is considered as the an…
Argument MiningSentence