The algorithm starts from a greedy assignment and improves it through a constrained optimization, quickly returning solutions of good quality and converging to the optimal assignment over time. If enough computational resources are available, the optimal assignment for the current requests and time is found; otherwise, the best solution found is returned. The algorithm experimentally quantifies the tradeoff between fleet size, capacity, waiting time, travel delay, and operational costs for low-capacity, medium-capacity and high-capacity vehicles, such as taxis, van shuttles or mini-buses. It applies to fleets of autonomous vehicles and also incorporates rebalancing of idling vehicles to areas of high demand.
The Inventors also rely on ILP formulation, but do not explicitly model the edges of the road network to ensure it scales to large problem instances. Their approach breaks down the problem by first computing feasible trips from a pairwise shareability graph and then assigning trips to vehicles in an ILP of reduced dimensionality. This framework allows for flexibility in terms of prescribing constraints including maximum user waiting times and maximum additional delays due to sharing a ride. The method can extend to proactively rebalance the vehicle fleet by moving idle vehicles to areas of high demand and can solve real-time ride-pooling problems with an arbitrary number of passengers and trips to return optimal rider allocation.