This technology provides a general mathematical model for real-time high-capacity ride-sharing that 1) scales to large numbers of passengers and trips, and 2) dynamically generates optimal routes with respect to online demand and vehicle locations. It can be used to analyze different transportation options for a city and to operate a dispatcher of shared vehicles, with real-time performance in applications including vehicle routing, multi-vehicle/task assignment, vehicle ride-sharing and package delivery.
This invention addresses the problem assigning a fleet of vehicles with varying passenger capacities to matched passengers and rebalancing the fleet to service demand. Previous approaches to this problem have focused on heuristic-based solutions that produce suboptimal results, or rely on an integer linear program (ILP) formulation to address multivehicle-routing and cannot scale to large problems. The Inventors present a reactive optimal algorithm that efficiently returns a valid assignment of travel requests to vehicles and then refines it over time, converging to an optimal solution. This technology has the capacity to handle large problem instances with small computation costs.
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.
runs in real-time and can continuously reroute based on requests or rebalance
idle vehicles to areas with high demand
is robust with respect to the density of requests and can be applied to many
is general enough to be applied to other multivehicle, multitask assignment