GMPRO docs: Force stop sequences using precedence rules

Use GMPRO's precedence rules feature to enforce stop sequences on a route.

GMPRO docs: Force stop sequences using precedence rules

As a rule, route optimization algorithms such as those used in the Google Maps Route optimization API (GMPRO), Google OR Tools or jsprit will automatically sequence stops to minimize total cost or travel time. This typically means stops are ordered based on proximity, starting with the ones closest to the driver’s starting point and progressing outward.

But there are many reasons why you'd want to order stops differently. Some customers might prefer their deliveries earlier rather than later e.g. a bakery delivering fresh bread to its top clients first. In other cases, a route might involve visiting stops in a specific order e.g. a technician collecting parts before heading to the repair location. And sometimes, routes need to follow a specific sequence simply because that’s how deliveries have always been run, and no one wants a new optimization system messing about with what's worked well so far.

Same route, but the one below uses precedence rules to force a different sequence of stops
Same route, but the one below uses precedence rules to force a different sequence of stops

In this blog post, I'll show you how to use GMPRO's precedenceRules feature to enforce stop sequences on a route. We’ll explore the official docs (link), work through several practical examples, and look at common reasons why precedence rules might fail.

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 (this article)

What are precedence rules?

A precedence rule makes sure that one stop happens before another e.g. it specifies that Stop A must be visited before Stop B, regardless of the optimized travel time or distance. In mathematical terms, you would say that precedence rules enforce a partial ordering of stops.

💡
A partial order is a binary relation on a set P that satisfies:
1. Reflexivity: For all a ∈ P, a ≤ a,
2. Antisymmetry: If a ≤ b and b ≤ a, then a = b
3. Transitivity: If a ≤ b and b ≤ c, then a ≤ c.
See MIT 6.042J Mathematics for Computer Science, Fall 2010

In GMPRO, precedence rules are set by adding a precedenceRules array to the ShipmentModel:

{
    "precedenceRules": [
        {
            "firstIndex": 0,
            "secondIndex": 1,
            "firstIsDelivery": true,
            "secondIsDelivery": true
        },
        {
            "firstIndex": 1,
            "secondIndex": 2,
            "offsetDuration": "300s",
            "firstIsDelivery": true,
            "secondIsDelivery": true
        }
    ]
}

In each precedenceRule object:

firstIndex is the shipment index of the "first" event, Stop A.

secondIndex is the shipment index of the "second" event, Stop B.

offsetDuration is the minimum time in seconds between the start of the first and second events e.g. if Stop A is started at 10 am and offsetDuration is "300s" (300 seconds or 5 minutes), Stop B can only start at 10:05 am.

firstIsDelivery and secondIsDelivery are booleans indicating if Stop A and B are deliveries.

👨‍💻
Screenshots in this blog post were taken with GMPRO-viewer , using data imported via GMPRO-json-converter. Both tools are free to use.

When to use precedence rules?

One common use case for precedence rules is when the routes returned by GMPRO don’t meet your needs and require manual adjustments. In the example below, I use the drag and drop feature in the Gantt chart to move the last stop to the beginning of the route, effectively reversing it.

0:00
/0:07

Precedence rules used to manually reverse an optimized route

The new route is far from optimal, so it has to be held "in place" using the ordering provided in the precedenceRules array.

Another common use case is adding last minute orders to an existing route while keeping the original stop sequence unchanged. This is a very common problem faced by last mile logistics companies that combine scheduled "next day" and on demand "same day" orders in a single route. The following example shows how I add a new stop to a route with three existing stops, without changing their original order.

0:00
/0:05

Precedence rules used to add new on demand stops to a scheduled route

You can see how stops 1, 2 and 3 retain their original sequence even after the new order is added to the route.

Precedence rules used in the recycling / waste management industry

The last use case is slightly more niche. In many real world logistics operations, stops must be completed in a specific order. One example is a waste management and recycling company in the Netherlands that supplies large containers for construction waste (see photo above). These containers are nested like Russian dolls, with smaller ones placed inside larger ones. When a truck collects empty containers, it must pick up the largest one first to fit the others inside. If the driver gets the sequence wrong, they may need to make an extra trip to collect the missed container - an inefficient and costly mistake.

Precedence rules alternatives

There are several better and simpler ways to express the "Do Stop A before Stop B" relationship without using precedence rules.

Time windows

The simplest way to ensure that one stop is started before another is to set a hard time window constraint like so:

{
    "shipments": [
        {
            "loadDemands": {
                "weight": {
                    "amount": 1
                }
            },
            "label": "stop_a",
            "deliveries": [
                {
                    "arrivalLocation": {
                        "latitude": 49.2808123,
                        "longitude": -123.1140999
                    },
                    "timeWindows": [
                        {
                            "startTime": "2024-07-08T16:00:00Z",
                            "endTime": "2024-07-08T17:00:00Z"
                        }
                    ],
                    "duration": "600s"
                }
            ]
        },
        {
            "loadDemands": {
                "weight": {
                    "amount": 1
                }
            },
            "label": "stop_b",
            "deliveries": [
                {
                    "arrivalLocation": {
                        "latitude": 49.26576319999999,
                        "longitude": -123.0821095
                    },
                    "timeWindows": [
                        {
                            "startTime": "2024-07-08T17:00:00Z",
                            "endTime": "2024-07-08T18:00:00Z"
                        }
                    ],
                    "duration": "600s"
                }
            ]
        }
    ]
}

In the JSON above, we've set non overlapping time windows, 4 pm - 5 pm UTC for stop_a and 5 pm - 6 pm UTC for stop_b, thereby guaranteeing that Stop A will be visited first.

Pickup and delivery

If your operations can be modeled as a pickup and delivery problem, you can simply mark certain stops as pickups linked to a corresponding delivery (or vice versa). For example, a field technician might need to pick up items at Stops A and B and deliver them to Stop C for final assembly:

{
    "shipments": [
        {
            "pickups": [
                {
                    "arrivalLocation": {
                        "latitude": 49.2474624,
                        "longitude": -123.1532338
                    },
                    "label": "stop_a"
                },
                {
                    "arrivalLocation": {
                        "latitude": 49.2382883,
                        "longitude": -123.1370127
                    },
                    "label": "stop_b"
                }
            ],
            "deliveries": [
                {
                    "arrivalLocation": {
                        "latitude": 49.227107,
                        "longitude": -123.1163085
                    },
                    "label": "stop_c"
                }
            ]
        }
    ]
}

GMPRO automatically enforces a hard constraint to ensure that every pickup in a shipment is completed before its corresponding delivery.

Routes API

If you already know the exact stop order and simply want real time, traffic adjusted ETAs for each one, you can use the Routes API with predefined (up to 25) waypoints. Just set "optimizeWaypointOrder": false to preserve the given sequence contained in the intermediates array.

{
    "origin": {
        "address": "555 W Hastings St, Vancouver, BC V6B 4N4, Canada"
    },
    "destination": {
        "address": "6706 Alberta St, Vancouver, BC V5X 4V8, Canada"
    },
    "intermediates": [
        {
            "address": "5251 Oak St, Vancouver, BC V6M 4H1, Canada"
        },
        {
            "address": "Queen Elizabeth Park, Vancouver, BC, Canada"
        }
    ],
    "travelMode": "DRIVE",
    "polylineQuality": "HIGH_QUALITY",
    "extraComputations": "TRAFFIC_ON_POLYLINE",
    "routingPreference": "TRAFFIC_AWARE",
    "departureTime": "2025-02-24T01:00:00Z",
    "optimizeWaypointOrder": "false"
}

GMPRO precedence rules example

Consider a simple example of one vehicle delivering pantry supplies to three big name tech companies in Vancouver - Amazon, Electronic Arts and Nintendo. Since the vehicle leaves from Burnaby, the optimal route to all three companies should go east to west - Nintendo, Electronic Arts and finally to Amazon in downtown Vancouver.

The optimal route returned by GMPRO going from east to west

Vehicles

mark-yvr starting from Capitol Hill neighborhood in Burnaby, BC (49.284, -122.989).

Shipments

index label company coordinates
0 amzn123 Amazon 49.265, -123.005
1 ea456 Electronic Arts 49.265, -123.082
2 ntdo789 Nintendo 49.280, -123.114

To switch thing up, we’ll add precedenceRules to our GMPRO API call to reverse the route - so it will now go from Amazon to Electronic Arts, and finally to Nintendo. We do this by defining a partial order on the shipment index i.e. 0 < 1 < 2 i.e. we tell GMPRO to deliver the shipment in position 0, then 1, and finally 2.

{
    "precedenceRules": [
        {
            "firstIndex": 0,
            "secondIndex": 1,
            "firstIsDelivery": true,
            "secondIsDelivery": true
        },
        {
            "firstIndex": 1,
            "secondIndex": 2,
            "firstIsDelivery": true,
            "secondIsDelivery": true
        }
    ]
}

Input

Output

Result (reversed route)

The reversed route fixed in place using the precedence rules feature of GMPRO

As we hoped, the route is now reversed and goes West to East. It starts at Amazon in downtown Vancouver and ends at Nintendo in Burnaby.

When might precedence rules fail?

There are two reasons why precedence rules might fail.

  1. Conflicting rules or circular dependencies. Be careful not to introduce contradictions into the partial ordering e.g. a < b and b > a. GMPRO will not be able to meet the constraints set out in the precedenceRules array and will optimize the route as usual.
{
    "precedenceRules": [
        {
            "firstIndex": 1,
            "secondIndex": 0,
            "firstIsDelivery": true,
            "secondIsDelivery": true
        },
        {
            "firstIndex": 0,
            "secondIndex": 1,
            "firstIsDelivery": true,
            "secondIsDelivery": true
        }
    ]
}
  1. GMPRO did not have enough time to find a valid solution. Adding constraints like precedence rules makes the optimization problem more complex and harder to solve quickly. If your request fails without an obvious reason, try setting "searchMode": "CONSUME_ALL_AVAILABLE_TIME" in your API call. This allows GMPRO to spend more time searching for a solution, increasing the likelihood of success.
{
    "model": {
        "shipments": [
            //... shipments array     
        ],
        "vehicles": [
            //... vehicles array
        ],
        "globalStartTime": "2024-10-02T00:00:00Z",
        "globalEndTime": "2024-10-03T00:00:00Z",
        "precedenceRules": [
            // ... precedence rules
        ]
    },
    "populatePolylines": true,
    "searchMode": "CONSUME_ALL_AVAILABLE_TIME"
}

Conclusion

In this blog post, you learned how to use precedence rules - a powerful but often overlooked feature in GMPRO that allows you to manually control the sequence of stops in a route. While GMPRO’s optimization usually produces strong results, it’s helpful to know you have the option to override the route solution when needed.

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