This paper presents a general mathematical model for real-time, high-capacity ride-sharing that scales to large numbers of passengers and trips. The model dynamically generates optimal routes based on online demand and vehicle locations, addressing three main problems: batch assignment, continuous assignment, and rebalancing. The algorithm starts with a greedy assignment and improves it via constrained optimization, providing good-quality solutions quickly and converging to the optimal assignment over time. The model is validated using approximately 3 million rides from the New York City taxicab dataset, considering rider capacities of up to ten passengers per vehicle. The framework is applicable to fleets of autonomous vehicles and includes rebalancing of idle vehicles to areas of high demand. The paper also discusses the theoretical guarantees of the method, including its optimality, correctness, and anytime optimality, and provides experimental results demonstrating its robustness to time window length, request density, and congestion.This paper presents a general mathematical model for real-time, high-capacity ride-sharing that scales to large numbers of passengers and trips. The model dynamically generates optimal routes based on online demand and vehicle locations, addressing three main problems: batch assignment, continuous assignment, and rebalancing. The algorithm starts with a greedy assignment and improves it via constrained optimization, providing good-quality solutions quickly and converging to the optimal assignment over time. The model is validated using approximately 3 million rides from the New York City taxicab dataset, considering rider capacities of up to ten passengers per vehicle. The framework is applicable to fleets of autonomous vehicles and includes rebalancing of idle vehicles to areas of high demand. The paper also discusses the theoretical guarantees of the method, including its optimality, correctness, and anytime optimality, and provides experimental results demonstrating its robustness to time window length, request density, and congestion.