On-demand high-capacity ride-sharing via dynamic trip-vehicle assignment

Area of Science:

• Operations Research
• Urban Planning
• Computer Science

Background:

• Ride-sharing services offer significant potential for improving urban mobility and reducing environmental impact.
• Existing mathematical models for ride-sharing often lack the capacity and dynamic routing capabilities needed for large-scale, real-time operations.
• Previous studies on carpooling were limited in scope, typically focusing on static routes and low passenger capacities.

Purpose of the Study:

• To develop a general mathematical model for real-time, high-capacity ride-sharing.
• To dynamically generate optimal routes considering real-time passenger demand and vehicle locations.
• To analyze the trade-offs between fleet size, vehicle capacity, waiting times, travel delays, and operational costs.

Main Methods:

• A novel algorithm combining greedy assignment with constrained optimization for efficient solution generation.
• Experimental validation using approximately 3 million rides from the New York City taxicab public dataset.
• Simulation of ride-sharing scenarios with vehicle capacities up to 10 simultaneous passengers.

Main Results:

• The algorithm efficiently provides high-quality solutions, converging to optimal assignments over time.
• Quantified trade-offs between key operational parameters like fleet size, capacity, and costs.
• Demonstrated the model's effectiveness in handling dynamic demand and vehicle rebalancing for autonomous fleets.

Conclusions:

• The developed mathematical model offers a scalable and dynamic solution for high-capacity ride-sharing.
• The framework provides valuable insights for optimizing ride-sharing operations, reducing costs, and enhancing urban mobility.
• The model's generalizability extends to various real-time multi-vehicle, multi-task assignment problems.