GMPRO docs: Routing for Demand Responsive Transport

You can think of Demand Responsive Transport (DRT) as ride sharing on steroids - public transit that bends to fit your schedule instead of the other way around. Call it what you like - shared mobility, on demand transit, or microtransit - it’s the fastest growing mode of public transportation in North America. Cities and municipalities that have adopted demand responsive models are seeing real results: shorter wait times, higher seat and vehicle utilization, and lower operational costs.

This blog post walks you through how to model a demand responsive transportation scenario as a vehicle routing problem - and how to use the Google Maps Platform Route Optimization API (GMPRO) to build your very own demand responsive transport service. I’m usually agnostic about which route optimization API my clients choose, but in this case I strongly recommend GMPRO because it offers the most accurate real time traffic data of any commercial route optimization service. For demand responsive transit, real time traffic is essential. Unlike packages, real people are waiting for their rides or are already on board, so accurate ETAs that account for live traffic conditions are essential to delivering a good passenger experience

Part 1: GMPRO: Google Maps Platform route optimization API
Part 2: GMPRO TSP solver: Google Maps with more than 25 waypoints
Part 3: Google Maps route optimization: multi vehicle
Part 4: GMPRO fleet routing app - free route planner for multiple stops
Part 5: GMPRO docs: Fixed vehicle costs
Part 6: GMPRO docs: Territory optimization and route planning
Part 7: GMPRO docs: Solving the VRP with route clustering and soft constraints
Part 8: GMPRO docs: Driver load balancing with soft constraints
Part 9: GMPRO docs: Driver breaks
Part 10: GMPRO docs: Complete deliveries before pickups in cargo bike logistics
Part 11: GMPRO docs: Force stop sequences using precedence rules
Part 12: GMPRO docs: Cut cost / raise care with smart NEMT routing
Part 13: GMPRO docs: Routing for Demand Responsive Transport (this article)

What is Demand Responsive Transport (DRT)?

Demand Responsive Transport is a flexible form of transportation that sits between a taxi and a traditional bus service. Like a taxi, you can book a demand responsive transport ride through an app or call center, either on demand or in advance, to pick you up and take you to your destination. But like a bus, the ride is shared with other passengers heading in a similar direction. These services typically use passenger vans (8 - 15 seats) or small transit buses (20 - 30 seats), which strike a balance between flexibility, capacity, and cost efficiency.

For this blog post, we'll focus specifically on on demand scenarios - where passenger bookings are made in real time, and the vehicle dynamically picks up passengers along the way as it travels toward its final destination. Each booking is atomic, i.e. they come in one at a time and either completes fully (a passenger is assigned to a vehicle, picked up and dropped off at his destination) or fails completely (no vehicle available), with no partial state left behind.

Why is demand responsive transport needed?

In many cities and towns, traditional public transportation operates at a loss, sustained only through subsidies that keep fixed-route buses running - even when ridership is low. Yet for many, these services fail to meet everyday needs. Bus stops are often poorly located, schedules are inflexible, and the system lacks the convenience modern riders expect. As a result, people turn to personal vehicles or rideshare services like Uber and Lyft. This shift further erodes bus ridership, triggering a downward spiral: fewer riders mean less fare revenue, and without sufficient funding, transit agencies struggle to improve service quality or frequency, making the system even less attractive over time.

DRT is often promoted as a silver bullet for this problem. Running a passenger van is significantly cheaper than operating a full sized bus, and the flexibility to pick up and drop off riders anywhere - not just at fixed stops -makes the service more accessible. This approach is especially appealing to elderly passengers and individuals with mobility challenges, who may find traditional bus systems difficult to use.

What’s truly new today isn’t the concept of demand responsive transport - it’s the technology that powers it. Services like dial a ride and paratransit have existed for decades, but modern advances have transformed how they're delivered. Passengers can now track their ride in real time through an app, receive accurate ETAs based on live traffic, and benefit from intelligent algorithms that create efficient, shared routes for riders going in different directions.

This combination of real time data and smart routing is the real innovation driving today’s demand responsive transport systems. In this blog post, I’ll take you behind the scenes to show exactly how these smart routing algorithms work.

What are the different types of demand responsive transport?

It’s easy to think of fixed route buses as “conventional” transit and everything else as demand responsive - but the reality is more nuanced. DRT exists on a spectrum, with different modes offering varying levels of flexibility and structure.

It this article, we'll look at the three most popular types of demand responsive transport:

1. Deviated fixed route,
2. Hub to hub and,
3. Door to door

Deviated fixed routes are the most structured form of DRT. The vehicle follows a set path, like a regular bus, but can make short detours to pick up or drop off passengers slightly off the main route. This model is commonly used in employee transportation services for workplaces that are poorly served by public transit - for example, shuttles that pick up workers from residential neighborhoods and drop them off at an Amazon warehouse outside town.

Hub to hub services operate between designated points of interest, such as major transit stations, university campuses or city centers. In some cases, they can be adapted for more flexibility offering point to hub or hub to point options to better serve specific communities or geographic areas.

Door to door services are the most flexible form of DRT, providing passengers with direct, point to point rides between any pickup and dropoff within the service area. This is pretty much identical to how Uber Pool or Lyft Shared (since discontinued) operate.

In the next section, I’ll walk you through how to build a dispatch system (a systematic way to assign passengers to vehicles) for each demand responsive transportation mode by modeling it as a vehicle routing problem and using Google Maps Platform Route Optimization (GMPRO) to solve it. It’s important to understand that GMPRO is a stateless algorithm - it doesn’t keep track of real time vehicle locations, passenger counts, or elapsed travel time. If you're building a dispatch system with GMPRO, you’ll need to manage state yourself and ensure that each API request includes the most up to date information.

Here’s how the dispatch system works: when a passenger books a ride through the app, their real time location is sent to the dispatch system. The system combines this with live data on vehicle locations and current passenger loads, then calls GMPRO to find the best match. If GMPRO assigns the passenger to a vehicle, the booking is confirmed. The passenger receives an ETA and a notification that their driver is on the way, while the driver gets an alert on their app that a new pickup has been added to his route.

Deviated fixed route

First, let’s look at a simplified example: a single 6-seat passenger van traveling from Simon Fraser University campus in Burnaby to the downtown Vancouver campus on West Hastings Street. Along the way, the van can pick up passengers from three designated bus stops on East Hastings Street, or from anywhere along the way. In the specific example below, the van starts his route at 09:00 and must get to the downtown campus by 10:00. If there are no additional pickups, he gets there by 09:37, leaving 10:00 - 09:37 = 23 minutes to pick up on demand passengers along the route.

In a deviated fixed route model, you initialize the vehicle object with:

Vehicles

startLocation, the route starting location.

{
    "startLocation": {
        "latitude": 49.27908859999999,
        "longitude": -122.9201795
    }
}

endLocation, the route end.

{
    "endLocation": {
        "latitude": 49.28458939999999,
        "longitude": -123.11146
    }
}

startTimeWindows, a strict start time (e.g. 09:00) that the route should start.

{
    "startTimeWindows": [
        {
            "startTime": "2024-07-08T16:00:00Z"
        }
    ]
}

endTimeWindows, a single target time window (e.g. 10:00) by which a route should be completed or arrive at its final stop.

{
    "endTimeWindows": [
        {
            "endTime": "2024-07-08T17:00:00Z"
        }
    ]
}

This helps ensure the vehicle finishes its route within a specified time frame. The difference between endTimeWindows[0].endTime and startTimeWindows[0].startTime is the maximum allowable ride time.

loadLimits, the capacity of the van.

{
    "loadLimits": {
        "persons": {
            "maxLoad": 6
        }
    }
}

Shipments

There are two types of shipments: fixed bus stops along the route and passenger booking requests from anywhere within the service area. Whether a passenger can be picked up depends on two factors: the maximum allowable detour time (the difference between the actual and scheduled route completion times) and the maximum allowable wait time for the passenger.

Bus stops

Bus stops have fixed locations and service durations (e.g. 1 minute). They are ordered using precedence rules to ensure they’re visited in the correct sequence. This ordered sequence of stops defines a route, similar to how waypoints are ordered using the Google Routes API. Each stop is assigned a time window that matches the driver’s shift, allowing it to be visited at any point during the route - as long as the order is maintained.

{
    "shipments": [
        {
            "loadDemands": {
                "persons": {
                    "amount": 0
                }
            },
            "label": "bus-stop-a",
            "deliveries": [
                {
                    "arrivalLocation": {
                        "latitude": 49.28043143019272,
                        "longitude": -122.98180380288142
                    },
                    "timeWindows": [
                        {
                            "startTime": "2024-07-08T16:00:00Z",
                            "endTime": "2024-07-08T17:00:00Z"
                        }
                    ],
                    "duration": "60s"
                }
            ]
        }
    ],
    "precedenceRules": [
            {
                "firstIndex": 0,
                "secondIndex": 1,
                "firstIsDelivery": true,
                "secondIsDelivery": true
            },
            {
                "firstIndex": 1,
                "secondIndex": 2,
                "firstIsDelivery": true,
                "secondIsDelivery": true
            }
        ]
    },
}

Passenger booking requests

Passenger booking requests are modeled as pickup and delivery shipments, where the pickup location is the passenger’s current position and the dropoff location is the vehicle’s final destination. To ensure that passenger bookings don’t cause the vehicle to skip mandatory bus stops, we assign a small penaltyCost to each passenger request. In contrast, shipments without a specified penaltyCost, such as fixed bus stops, are treated as mandatory and incur a very large (effectively infinite) cost if missed. By assigning a low penalty cost to passenger bookings, GMPRO will reject requests that are too far off route or would cause the vehicle to miss a required stop or arrive late at its final destination. Each booking request must have:

loadDemands, the number of passengers included in the booking. This information is needed to ensure that the assigned vehicle has enough seats available to accommodate the group.

{
    "loadDemands": {
        "persons": {
            "amount": 1
        }
    }
}

For pickups, the booking request is defined using a VisitRequest object, which includes the arrivalLocation and timeWindows. The timeWindows.startTime is always set to the time the booking is made. The timeWindows.endTime is calculated by adding the maximum allowable wait time to the start time. For example, if a booking is made at 09:00, and company policy allows a maximum wait time of 15 minutes, then timeWindows.endTime would be 09:15. This ensures the vehicle is only assigned if it can pick up the passenger within the maximum allowable wait time.

{
    "pickups": [
        {
            "arrivalLocation": {
                "latitude": 49.27751815950839,
                "longitude": -122.96474579611838
            },
            "timeWindows": [
                {
                    "startTime": "2024-07-08T16:00:00Z",
                    "endTime": "2024-07-08T16:15:00Z"
                }
            ],
            "duration": "60s"
        }
    ]
}

The penaltyCost assigns a small penalty if a passenger booking request is skipped - meaning the passenger would receive a message like “no vehicles are available right now.” In contrast, mandatory bus stops carry a very high (effectively infinite) penalty if missed. This setup ensures the solver will only assign a booking to a vehicle if it’s confident the detour won’t cause the vehicle to miss a required stop or arrive late at its final destination.

{
    "penaltyCost": 5
}

When a new passenger booking is added to the GMPRO request, one of two things can happen:

If the booking request is accepted, its shipment is added to the route plan, and the estimated arrival times (ETAs) for all stops are updated accordingly.

If the booking request is rejected, it means that either the vehicle couldn’t reach the passenger within the maximum allowable wait time, or picking up the passenger would cause a significant detour that delays the driver’s arrival at the final destination.

As the driver progresses along the route, new booking requests use the driver’s real time location as the startLocation and the current number of available seats as the loadLimits. Any bus stops that have already been visited are removed from the optimization request.

Hub to hub

Now, let’s take the same 6-seat passenger van and use it to model a hub to hub DRT service between the two Simon Fraser University campuses in the earlier example. This model is similar to a deviated fixed-route service, but with one key difference: there are no fixed bus stops to visit. Instead, passenger pickups can occur anywhere within the service area. Whether a booking request is accepted depends, just like before, on two factors: the maximum allowable wait time for the passenger and the maximum allowable detour time for the vehicle. For example, if the vehicle is expected to arrive at the destination hub by 09:45, and the route has a hard end time of 10:00, then the available detour time is 15 minutes (10:00 – 09:45).

Vehicles

{
    "vehicles": [
        {
            "travelMode": "DRIVING",
            "startLocation": {
                "latitude": 49.27908859999999,
                "longitude": -122.9201795
            },
            "endLocation": {
                "latitude": 49.28458939999999,
                "longitude": -123.11146
            },
            "startTimeWindows": [
                {
                    "startTime": "2024-07-08T16:00:00Z"
                }
            ],
            "endTimeWindows": [
                {
                    "endTime": "2024-07-08T17:00:00Z"
                }
            ],
            "loadLimits": {
                "persons": {
                    "maxLoad": 6
                }
            },
            "label": "van-01",
            "costPerKilometer": 1,
            "fixedCost": 25
        }
    ]
}

Shipments

{
    "shipments": [
        {
            "loadDemands": {
                "persons": {
                    "amount": 1
                }
            },
            "label": "booking-001",
            "pickups": [
                {
                    "arrivalLocation": {
                        "latitude": 49.277514973376256,
                        "longitude": -122.96473683470182
                    },
                    "timeWindows": [
                        {
                            "startTime": "2024-07-08T16:00:00Z",
                            "endTime": "2024-07-08T16:15:00Z"
                        }
                    ],
                    "duration": "60s"
                }
            ],
            "deliveries": [
                {
                    "arrivalLocation": {
                        "latitude": 49.28458939999999,
                        "longitude": -123.11146
                    },
                    "timeWindows": [
                        {
                            "startTime": "2024-07-08T16:00:00Z",
                            "endTime": "2024-07-08T17:00:00Z"
                        }
                    ],
                    "duration": "60s"
                }
            ]
        }
    ]
}

Updating the state of the route in real time

Suppose our passenger van van-01 has just picked up booking-001 and is already scheduled to pick up booking-002 next. Now, a new request comes in for booking-003. How do we model this scenario as a vehicle routing problem?

1. First we reduce the current capacity of the vehicle by the number of passengers picked up in booking-001 (1 person).

{
    "label": "van-01",
    "loadLimits": {
        "persons": {
            "maxLoad": 5 // was 6
        }
    }
}

2. Next, we update the location of the vehicle to its current location at booking-001.

{
    "label": "van-01",
    "startLocation": { // New start location set to booking-001
        "latitude": 49.277514973376256,
        "longitude": -122.96473683470182
    }
}

3. Third, we update startTimeWindows[0].startTime to the current time. This will allow us to calculate accurate ETAs for booking-002 and booking-003. We do this not just for van-01 but all the shipments and vehicle objects too.

{
    "label": "van-01",
    "startTimeWindows": [
        {
            "startTime": "2024-07-08T16:08:00Z"
        }
    ]
}

4. In the shipments array, we remove the completed booking-001 and include booking-002 (pending pickup) and booking-003 (a new request waiting to be matched).

{
    "shipments": [
        // booking-001 removed
        {
            "label": "booking-002"
        },
        {
            "label": "booking-003"
        }
    ]
}

5. Since booking-002 has already been assigned to van-01, we use GMPRO's allowedVehicleIndices feature (docs) to bind this shipment to van-01 (the 0th vehicle object in the vehicles array).

{
    "label": "booking-002",
    "allowedVehicleIndices": [
        0
    ]
}

6. Finally, since booking-003 is still optional - it hasn’t been assigned to a vehicle yet - we assign it a penaltyCost. This tells the solver to try matching it to a vehicle, but only if doing so won’t delay the route. In other words, the extra driving time to pick up the passenger must not exceed the vehicle’s maximum allowable detour time.

{
    "label": "booking-003",
    "penaltyCost": 5
}

booking-003 has a maximum allowable wait time of 15 minutes (09:08 - 09:23), as defined in its timeWindows array.

{
    "label": "booking-003",
    "pickups": [
        {
            "timeWindows": [
                {
                    "startTime": "2024-07-08T16:08:00Z",
                    "endTime": "2024-07-08T16:23:00Z"
                }
            ]
        }
    ]
}

If van-01 can pick up the passenger within that 15-minute window and still reach the final stop before 10:00 (the driver shift end time), the booking will be successfully matched, which is exactly what happened.

Door to door

Door to door DRT is the simplest type to model as a vehicle routing problem. The vehicle operates like a shared taxi, with no fixed end location. It can pick up passengers from anywhere within the service area - as long as doing so doesn’t violate the maximum allowable wait time or maximum ride time constraints.

Vehicles

{
    "vehicles": [
        {
            "travelMode": "DRIVING",
            "startLocation": {
                "latitude": 49.27908859999999,
                "longitude": -122.9201795
            },
            "startTimeWindows": [
                {
                    "startTime": "2024-07-08T16:00:00Z"
                }
            ],
            "endTimeWindows": [
                {
                    "endTime": "2024-07-08T17:00:00Z"
                }
            ],
            "loadLimits": {
                "persons": {
                    "maxLoad": 6
                }
            },
            "label": "van-01",
            "costPerKilometer": 1,
            "fixedCost": 25
        }
    ]
}

Shipments

As with the first two demand responsive transit models, each shipment represents a passenger booking. Time windows enforce a maximum allowable wait time, ensuring the assigned vehicle arrives within, for example, 15 minutes of the booking request.

{
    "label": "booking-001",
    "pickups": [
        {
            "timeWindows": [
                {
                    "startTime": "2024-07-08T16:00:00Z",
                    "endTime": "2024-07-08T16:15:00Z"
                }
            ],
        }
    ]
}

In addition, we now include the pickupToDeliveryTimeLimit parameter (docs) to enforce a maximum ride time for each passenger. For example, if we set "pickupToDeliveryTimeLimit": "1800s" for booking-001, GMPRO will ensure that the passenger is dropped off within 30 minutes (1800 seconds) of being picked up. This prevents situations where one passenger is kept onboard for an unreasonably long time while others are picked up and dropped off more quickly.

{
    "label": "booking-001",
    "pickupToDeliveryTimeLimit": "1800s"
}

You can also use the pickupToDeliveryAbsoluteDetourLimit parameter to set the maximum allowable detour time compared to the shortest path from pickup to dropoff.

For example, if the most direct route between pickup and dropoff takes 15 minutes (or 900 seconds) and you set pickupToDeliveryAbsoluteDetourLimit: "600s", GMPRO will ensure the total trip time never exceeds 900 + 600 = 1500 seconds (or 25 minutes) - even with additional pickups or dropoffs along the way.

Handling real time updates for door to door demand responsive transport

Maintaining state in a door to door demand responsive transport scenario requires a bit more care. You can’t simply remove a booking from the optimization request once the passenger is picked up - you still need to keep their dropoff location in the request. That’s because their destination influences both the vehicle’s direction of travel and which future bookings it can accept along the way.

Let's modify the hub to hub example from earlier slightly to fit a door to door scenario. van-01 just picked up the passenger from booking-001 and is already scheduled to pick up booking-002 next. Now, two new requests come in - booking-003 in East Vancouver and booking-004 in Burnaby.

1. Again, we reduce the current capacity of the vehicle by the number of passengers picked up in booking-001 (1 person).

{
    "label": "van-01",
    "loadLimits": {
        "persons": {
            "maxLoad": 5 // was 6
        }
    }
}

2. As before, we update the location of the vehicle to its current location at booking-001.

{
    "label": "van-01",
    "startLocation": { // New start location set to booking-001
        "latitude": 49.277514973376256,
        "longitude": -122.96473683470182
    }
}

3. Third, we update startTimeWindows[0].startTime to the current time. This will allow us to calculate accurate ETAs for booking-002, booking-003 and booking-004. We do this not just for van-01 but all the shipments and vehicle objects too.
4. Fourth, we use the allowedVehicleIndices parameter to force assign booking-001 to van-01. This ensures the booking isn’t accidentally matched to a different vehicle—which wouldn’t make sense, since the passenger is already on board van-01.

{
    "label": "booking-001",
    "allowedVehicleIndices": [
        0
    ]
}

5. We also need to set the pickup duration for booking-001 to 0, since the pickup has already happened. This prevents the system from adding unnecessary service time, which could delay the ETAs for other upcoming pickups and dropoffs.

{
    "label": "booking-001",
    "pickups": [
        {
            "duration": "0s"
        }
    ]
}

6. Lastly, we assign a penaltyCost to the newly received bookings to indicate that they are optional. This tells GMPRO to try to include them in the route plan, but only if it can do so without violating any constraints.

{
  "shipments": [
		// other shipments
        {
            "label": "booking-003",
            "penaltyCost": 15
        },
        {
            "label": "booking-004",
            "penaltyCost": 15
        }
    ]
}

Here's what the resulting dispatch solution looks like:

Since van-01 was already scheduled to pick up booking-002, it began heading east and picked up booking-003 along the way. As a result, it moved outside the 15 minute maximum allowable wait time window for booking-004, which couldn’t be served. The passenger who made booking-004 would therefore receive a “No driver available” message in his app.

What's next for demand responsive transport?

Demand responsive transportation in the form of dial a ride services or paratransit has been around forever, but has struggled to gain widespread adoption. The main challenge has been cost - these services are typically expensive because they often involve single passenger trips over long distances. Unlike fixed route transit, they don’t benefit from economies of scale.

The biggest reason why adoption has been poor is because these services require advance bookings, often hours or days ahead. Today, smartphone apps powered by intelligent route optimization algorithms such as GMPRO have transformed the user experience - enabling passengers to easily request rides, view estimated arrival times, make payments, and receive real time notifications. This shift has made using on demand transit as easy as booking an Uber or Lyft.

This blog post showed how you can build your own demand responsive transport service using the Google Maps Platform Route Optimization API, but this is probably overkill for many transit organizations. Startups such as The Routing Company, Spare Labs and Swat Mobility have made demand responsive transportation accessible as a software as a service platform that any company can use. Even very conservative and traditional transit agencies such as the Singapore Land Transport Authority have started integrating on demand buses into the wider transit ecosystem.

Demand responsive transportation is finally gaining momentum, evolving from small scale pilot programs to a viable and scalable transit solution. If funding is available and integration with existing networks improved, it could soon become a core part of urban and regional transit systems. Whether it ultimately does so however, remains to be seen.

Afi Labs can help your organization integrate demand responsive transport into your existing bus or van network, or build a new one from the ground up. Get in touch - we’d love to help.

👋 As always, if you have any questions or suggestions for me, please reach out or say hello on LinkedIn.