Header and Body 2

Problem Addressed

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.