Intro to Routing Constraints

Puzzle For The Reader

Under what circumstances would a fleet operator want their vehicles to follow routes that are not the fastest way to their destination?

Routing Constraints

Many fleet operators want their vehicles to follow the fastest route to their destination that respects certain constraints. These constraints sometimes prevent vehicles taking the overall fastest route to the destination.

There are many potential cases for constrained routing. For example:

• Autonomous vehicles (AVs) with limited capabilities may need to avoid roads with certain properties (e.g. high speed limits)
• AVs may also need to avoid certain maneuvers through intersections (e.g. turns which yield to oncoming traffic)
• Local regulations may restrict the operations of certain businesses on some roads
• Physical safety concerns may motivate routing around high risk areas

For any of these cases, traditional routing engines are insufficient, and a routing engine with constraints is necessary. This is where rideOS comes to the rescue, with flexible Routing Constraints integrated at every level of our tech stack, including the Ridehail API, the Fleet Planner API, and the Routing API.

AV Case Study

Let’s suppose that an AV company called RoboTaxiCab is deploying a fleet in downtown San Francisco, using rideOS as the platform for its routing, dispatch, and fleet management needs.

In order to keep their vehicles inside downtown San Francisco, RoboTaxiCab first defines an Operational Area constraint around the desired city area. This constraint will ensure that all routes stay inside the downtown area.

Operational Area drawn around downtown San Francisco

However, with RoboTaxiCab vehicles still in development, it’s not possible for them to drive every road in this area. RoboTaxiCab vehicles don’t drive well in narrow alleys, so they want to keep their cars out of those conditions. To enforce this, RoboTaxiCab defines some Avoid Path constraints which will ensure that all routes stay out of the roads along those paths.

Avoid Paths drawn on alleys and small roads that shouldn’t be driven

Additionally, RoboTaxiCab wishes to avoid taking very risky turns, like unprotected lefts which must yield to oncoming traffic. To avoid these maneuvers, RoboTaxiCab defines Avoid Turn constraints on each turn of this type.

Avoid Turn drawn on unprotected left from Sansome St to California St

With all of these constraints defined, RoboTaxiCab can now deploy their fleet confidently. Their vehicles can service arbitrary trips and tasks in downtown San Francisco while honoring the constraints at every step of the way.

RoboTaxiCab simulated fleet serving riders downtown with routing constraints

Creating Routing Constraints

You can create constraints either through the web user interface (UI) or through the Constraint Data API. Using the UI is as simple as drawing simple geometry on top of the map. A simple polygon (as shown below) or a simple path are enough to define the constraints.

Drawing an Operational Area polygon in the web interface

When done, the UI will update to show the final geometry of the constraint. Whether the user chose to use the UI or the API, the results can be viewed online. A company like RoboTaxiCab could automatically export internal geometries to the Constraint Data API, then check the result visually in the UI.

Viewing the completed Operational Area polygon

Assigning Routing Constraints

Creating routing constraints is only the first step. By default, constraints created through the Ridehail API are not enforced for any routes. After creation, the API allows you to flexibly assign any combination of constraints to individual vehicles or your entire fleet.

Let’s imagine that RoboTaxiCab has been operating downtown long enough that they’ve decided to expand to another area of San Francisco. They create new constraints for the Mission District and assign these constraints to half of their fleet. They can now separately serve trips within downtown and trips within the Mission District.

RoboTaxiCab simulated fleets serving riders both downtown and in the Mission District

Note: In the API Playground, all new constraints are automatically assigned to the whole fleet. Currently, you can only make custom assignments through the Ridehail API. Future development will enable this in the UI as well.

How Do Routing Constraints Work?

Under the hood, the rideOS platform performs two steps to enable routing constraints:

1. Evaluation: Identify which graph edges should be affected
2. Enforcement: Update routing decisions for the affected graph edges

In my next two blog posts, I will explore each of these steps in more detail. I’ll show how they work, then consider the implications on how to use the corresponding APIs effectively.