A multi-agent reinforcement learning scheduling algorithm integrating state graph and task graph structural modeling for ride-sharing dispatching

Why smarter ride-sharing matters for city life

Anyone who has waited too long for a ride-hailing car, or watched empty vehicles cruise past busy corners, has seen how hard it is to coordinate urban transport in real time. This study introduces a new AI-based dispatching system designed to match passengers and ride-sharing vehicles more quickly and efficiently, cutting wasted mileage and shortening waits in dense, fast-changing city traffic.

From simple matches to tangled city traffic

Ride-hailing began with a simple idea: one driver, one passenger, one trip. Today’s city streets look very different. Platforms juggle thousands of vehicles and riders at once, often pooling several passengers into the same car and routing fleets across entire boroughs. Demand is uneven—downtown may be flooded with requests while another area is quiet—and everything changes minute by minute. Traditional rule-based dispatch rules or simple "closest car" strategies struggle in this setting, leading to long waits, low car utilization, and unnecessary detours. Figure

Two connected maps instead of one big blur

The authors propose a new framework called DualG-MARL that treats the dispatch problem as two overlapping maps. One map describes the vehicles: where they are, how many seats they have, and whether they are free or already carrying riders. The other map describes the ride requests: who wants to travel, from where, to where, and at what time. Each map is modeled as a graph, where dots represent cars or requests and lines connect those that are close in space and time. By keeping vehicle and passenger information in separate but linked graphs, the system preserves the structure of each side instead of mixing everything into a single, confusing picture.

How the AI learns to match riders and cars

On top of these twin graphs, the system uses a class of machine learning methods known as multi-agent reinforcement learning. Each vehicle is treated as an independent decision-maker, or "agent," that chooses among nearby requests. The agents share a common goal: reduce waiting times, avoid excessive detours, and keep cars productively occupied. The model scans both graphs to extract patterns, then uses an attention mechanism—an AI tool that highlights the most relevant connections—to link suitable cars and riders across the two maps. To keep decisions fast and stable, it does not consider every possible pair. Instead, it builds a shortlist of the top candidates for each vehicle (the Top-K set), filtered by hard rules like seat capacity, pickup delay, and acceptable detour length. A centralized learner evaluates how well the whole fleet is doing, while individual cars follow simple local rules during real-time operation. Figure

Testing the system on real New York City trips

The researchers tested DualG-MARL on large-scale trip data from New York City’s Taxi and Limousine Commission, focusing on Manhattan and Queens. They compared their method with a range of existing approaches, including hand-crafted rules, mathematical optimization, and advanced learning-based dispatchers such as CoopRide. Across both boroughs, the new system set fresh benchmarks on four key measures: it cut the average time passengers spent waiting for pickup, increased the fraction of ride requests successfully served, raised the share of time vehicles spent carrying customers, and slightly reduced the extra distance caused by sharing rides. Importantly, these gains came without blowing up computing costs: by limiting attention to a curated set of promising matches, the method stayed fast enough for real-time use.

What this means for everyday riders and cities

In plain terms, the study shows that representing a city’s ride-hailing system as two structured networks—one for vehicles and one for riders—and letting them interact through a carefully designed learning process can make pooling smarter and more responsive. For passengers, that means shorter waits and more reliable pickups; for drivers and platforms, it means better use of vehicles and less deadheading; and for cities, it hints at a future in which existing roads can move more people with fewer cars and less congestion. The authors suggest that similar graph-based, multi-agent ideas could eventually extend to other services, from autonomous taxi fleets to emergency response, providing a more orderly way to manage the complex, shifting flows of modern urban life.

Citation: Sha, J., Song, M., Sui, G. et al. A multi-agent reinforcement learning scheduling algorithm integrating state graph and task graph structural modeling for ride-sharing dispatching. Sci Rep 16, 5461 (2026). https://doi.org/10.1038/s41598-026-35004-8

Keywords: ride-sharing dispatch, multi-agent reinforcement learning, graph neural networks, urban mobility, dynamic matching