googlemaps

GMPRO docs: What to look for in NEMT routing software

What route optimization features are needed in Non Emergency Medical Transportation (NEMT) use cases.

Afian Anwar

• 5 min read
GMPRO docs: What to look for in NEMT routing software

Continuing our series on niche topics in route optimization, we dive into what matters most when selecting route optimization software for Non Emergency Medical Transportation (NEMT) services. I explain what NEMT services are, discuss the unique routing challenges they present, and show you how the Google Maps Route Optimization API (GMPRO) can effectively address them.

Note: Many commercial and open source route optimization solvers work just as well as GMPRO. This blog posts highlights the specific features you need to ensure your solution can support to meet the complex demands of NEMT operations. Whether you choose GMPRO or an alternative (and probably more cost effective) option, is up to you.

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: What to look for in NEMT routing software (this article)

What is NEMT?

Non Emergency Medical Transportation (NEMT) is a specialized service designed for individuals who are unable to use regular public transit or drive due to mobility or medical access needs. Unlike ambulances, which are reserved for emergencies and urgent medical situations, NEMT provides scheduled, non emergency transport for routine appointments and daily activities.

In the US, NEMT services are usually run by private transportation companies that contract with health insurance providers and hospitals. Almost of all of them use commercial routing and scheduling software to handle bookings, schedule drivers and plan routes.

Who is this article on NEMT routing software for?

This article explores the routing technology behind NEMT routing software and how it efficiently schedules trips to boost on-time performance and cut fuel costs. It does not review or compare specific NEMT software providers. This blog post is for you if you operate an NEMT service and are evaluating routing software to meet your operational needs, or if you're a software provider seeking a route optimization API that can support the specific demands of NEMT clients.

How are NEMT rides scheduled?

Rides are scheduled in advance, often 1 - 2 days ahead. The process begins when a patient, caregiver, or healthcare provider submits a request - usually by phone, but increasingly through a website or mobile app. These requests include essential details such as pickup and dropoff locations, appointment time, mobility needs (e.g. wheelchair or stretcher access), and whether a return trip or caregiver accompaniment is required. NEMT routing software will then use a route optimization solver to batch rides efficiently, assigning vehicles based on capacity and accessibility, while respecting time windows, service durations, and other operational constraints.

How does NEMT routing software work?

NEMT routing falls under a class of operations research challenges known as the Dial a Ride Problem (DARP) - so called because in the past passengers would literally "dial" a phone number to request a ride (they still do). At its most basic, the Dial a Ride Problem involves:

  • A set of customer requests (bookings) each with:
    • a pickup location,
    • a dropoff location,
    • the number of passengers e.g. 2 if there's a patient and a caregiver,
    • time windows for pickup and/or drop-off,
    • and a maximum allowable ride time.
  • A fleet of vehicles (drivers) with limited capacity, typically starting and ending at a depot.

NEMT routing software will collect all this data and then call a route optimization solver to produce a cost-effective route plan that minimizes total mileage, fuel use, and driver hours while:

    • satisfying all customer requests,
    • respecting vehicle capacities,
    • adhering to time windows and ride time constraints,

Additionally, good NEMT routing software must account for wheelchair users and other passengers with special needs. These riders often require vehicles with specific equipment - such as wheelchair lifts or extra space, and may need more time for boarding and disembarking. Failing to consider these factors can lead to missed appointments, overloaded vehicles, and non-compliance with regulations like the Americans with Disabilities Act.

Converting the Dial a Ride Problem to a route optimization problem

In GMPRO, we would model the dial a ride problem as a capacitated vehicle routing problem with time windows. Each customer request (booking) and vehicle (driver) is added to the optimization model as a shipment and vehicle object with these attributes:

Bookings (shipment)

GMPRO
Pickup Location 
{
    {
    "pickups": [
        {
            "arrivalLocation": {
                "latitude": 49.2688067,
                "longitude": -123.2099986
            }
        }
    ]
}
}
Dropoff Location 
{
    {
    "deliveries": [
        {
            "arrivalLocation": {
                "latitude": 49.2728387,
                "longitude": -123.1603492
            }
        }
    ]
}
}
No. of Passengers 
{
    "loadDemands": {
        "persons": {
            "amount": 2
        }
    }
}
Pickup Time Windows 
{
    "timeWindows": [
        {
            "startTime": "2024-07-08T16:00:00Z",
            "endTime": "2024-07-08T18:00:00Z"
        }
    ]
}
Dropoff Time Windows 
{
    "timeWindows": [
        {
            "startTime": "2024-07-08T16:00:00Z",
            "endTime": "2024-07-08T18:00:00Z"
        }
    ]
}
Max Allowable Ride Time 
"pickupToDeliveryTimeLimit": "1800s"

NEMT routing software requirements

pickup and dropoff locations

Sed ut perspiciatis unde omnis iste natus error sit voluptatem accusantium doloremque laudantium, totam rem aperiam, eaque ipsa quae ab illo inventore veritatis et quasi architecto beatae vitae dicta sunt explicabo. Nemo enim ipsam voluptatem quia voluptas sit aspernatur aut odit aut fugit, sed quia consequuntur magni dolores eos qui ratione voluptatem sequi nesciunt.

The Dial-a-Ride Problem (DARP) in operations research is a type of pickup and delivery problem with time windows, often used to model demand-responsive transportation services such as paratransit, ride-hailing, or shared taxi systems.

Formal Definition:

The Dial-a-Ride Problem involves:

  • A set of customer requests, each with:
    • a pickup location,
    • a drop-off location,
    • time windows for pickup and/or drop-off,
    • and a maximum allowable ride time.
  • A fleet of vehicles with limited capacity, typically starting and ending at a depot.
  • The objective is to design vehicle routes that:
    • satisfy all customer requests,
    • respect vehicle capacities,
    • adhere to time windows and ride time constraints,
    • and optimize a given cost function (e.g., total travel time, total distance, number of vehicles used).

Mathematical Formulation (Simplified):

Minimize:

  • Total route cost (distance, time, or number of vehicles)

Subject to:

  • Each request is served exactly once by one vehicle
  • Vehicle capacity is not exceeded
  • Pickups occur before drop-offs
  • Time windows for service are respected
  • Maximum ride time for each customer is not exceeded

Static DARP:

  • All requests are known in advance before routing begins.
  • There is a clear cutoff time before the planning period starts, after which no new requests are accepted.
  • Typical for scheduled services like paratransit or shuttle services with bookings made the day before.

NEMT refers to transportation services provided to individuals who need medical care but do not require emergency services (like an ambulance). It's commonly used by:

  • Elderly patients
  • People with disabilities
  • Medicaid recipients
  • Patients attending routine checkups, dialysis, physical therapy, etc.

🚐 Typical Modes of Transport:

  • Wheelchair-accessible vans
  • Sedans or taxis
  • Specialized shuttles
  • Ride-hailing partnerships (e.g. Uber Health, Lyft Healthcare)