Avoiding bridges, train tracks, and other pathways with route optimization

Avoiding pathways is a common routing consideration for many people doing route optimization — from flooded bike paths to collapsed tunnels, roadside rockslides, underpasses with high levels of crime, slowdowns when crossing train tracks, and beyond.

With Nextmv, we’re building a decision automation platform that seeks to treat decisions as code, meaning they look and feel like regular software and make it easier to build, test, adapt, and ship to production. When it comes to adapting to changes with pathways, the Nextmv SDK provides a consolidated experience for configuring a decision engine with the variables and constraints you need without a lot of extra fuss or work. 

This blog post will demonstrate how you can avoid certain pathways — in this case a set of train tracks — or discourage pathways by slowing down their maximum allowable speed so much that they will only be chosen if still beneficial.

Configuring your route optimization engine

For this example, we’re going to create routes in a favorite city of mine: Paderborn, Germany. If you were to ask someone in Paderborn which pathway they’d likely want to avoid, they’d probably mention crossing the train tracks.

We will start with the function that sets up our router engine, which allows you to solve single and multi vehicle routing problems. For this example, we’ll keep things simple with a single vehicle and two stops.

Let's start with our input file:

{
    "osm_file_path": "data/paderborn.osm.pbf",
    "vehicles": [
        {
            "id": "DreiHasenTaxi-1",
            "start": { "lon": 8.752861834112625, "lat": 51.71324226694882 },
            "end": { "lon": 8.752861834112625, "lat": 51.71324226694882 }
        }
    ],
    "stops": [
        {
            "id": "Musikschule",
            "position": { "lon": 8.760622776361267, "lat": 51.72146913009119 }
        },
        {
            "id": "Paderwiesen",
            "position": { "lon": 8.75043005112675, "lat": 51.72260571906219 }
        }
    ]
}

As you can see, our input file accounts for one vehicle and two stops. The vehicle has a start and an end location, and the stops each have an ID as well as a geographical location.

In the example below we are configuring a router instance to consume this input file. (I’ve excluded the extract method and definitions for brevity.)

func main() {
    f := func(i input, opt solve.Options) (solve.Solver, error) {
        stops, vehicles, starts, ends, points := i.extract()
        measures, err := i.measures(points)
        if err != nil {
            return nil, err
        }
 
        router, err := route.NewRouter(
            stops,
            vehicles,
            route.Starts(starts),
            route.Ends(ends),
            route.ValueFunctionMeasures(measures),
        )
        if err != nil {
            return nil, err
        }
 
        return router.Solver(opt)
    }
    cli.Run(f)
}
 
// measures returns routingkit measures for the vehicles reading the osm file
// specified under the path of the input.
func (i input) measures(points []measure.Point) (
    measures []measure.ByIndex,
    err error,
) {
    // set the snap radius (if a point is not exactly on the road network, we
    // snap to the nearest point within a radius of 1km)
    radius := float64(1000)
    // set the cache size of the measure to 1GB
    cacheSize := int64(1 << 30)
    // we use a haversine measure scaled by 0.1 (10 m/s) in case the routingkit
    // measure is unable to determine a duration (in case we couldn't snap)
    m := measure.ScaleByPoint(measure.HaversineByPoint(), 1./10.)
    rkByPoint, err := routingkit.DurationByPoint(
        i.OsmFilePath,
        radius,
        cacheSize,
        ProfileWithoutParticularWay(),
        m,
    )
    if err != nil {
        return nil, err
    }
    rkIndexed := measure.Indexed(rkByPoint, points)
    // each vehicle in our fleet uses the routingkit measure
    measures = make([]measure.ByIndex, len(i.Vehicles))
    for i := range measures {
        measures[i] = rkIndexed
    }
 
    return measures, nil
}

The measures method is the one that specifies how our router engine determines the cost of going from one location to another. We have multiple pre-built measures. In this example, we will use the RoutingKit measure. The RoutingKit measure allows us to account for real-road networks and profiles for vehicles such as cars, bikes, and pedestrians as we optimize our routes. 

Let me draw your attention to the vehicle profile that we have currently configured: goroutingkit.Car()

This is a prebuilt profile based on OpenStreetMap (OSM) data that knows which ways a car can use and at which speeds it typically travels.

Forbidding train track crossing with route optimization

OK, we’ve configured our input file to specify our vehicles, stops, and measure (with the car vehicle profile). Now, let’s run it through our model. We get the following solution.

There are two spots here where we have to cross train tracks. Crossing the tracks on the right side is usually pretty slow, so let’s see what the solution looks like when we forbid using that way. In order to do so, we head over to https://www.openstreetmap.org/ and find that way crossing the train tracks. We select that way and note down the way id (280764574):

Equipped with this way id, we can write a custom profile that forbids using this particular way.

func ProfileWithoutParticularWay() goroutingkit.Profile {
    return goroutingkit.NewProfile("CustomCar",
        goroutingkit.VehicleMode,
        false,
        false,
        CustomTagMapFilter,
        goroutingkit.CarSpeedMapper,
    )
}
 
func CustomTagMapFilter(id int, tags map[string]string) bool {
    if id == 280764574 {
        return false
    }
    return goroutingkit.CarTagMapFilter(id, tags)
}

A TagMapFilter specifies which OSM ways a vehicle is allowed to use. In this sample, we explicitly forbid usage of the way 280764574. For all other ways we let our standard CarTagMapFilter decide.

Here is what that solution looks like:

Note how we have successfully avoided crossing the train tracks.‍

Discouraging train track crossings with route optimization 

Now, what if we know that crossing our train tracks is pretty slow, but we don’t want to completely forbid using that way. Instead, we would prefer to avoid using it whenever it isn’t beneficial. We can do that to by influencing the speed at which we allow our vehicle to move along that way. Here is what that looks like:

func ProfileWithoutParticularWay() goroutingkit.Profile {
    return goroutingkit.NewProfile("CustomSpeedCar",
        goroutingkit.VehicleMode,
        false,
        false,
        goroutingkit.CarTagMapFilter,
        CustomSpeedMapper,
    )
}
 
func CustomSpeedMapper(id int, tags map[string]string) int {
    if id == 280764574 {
        return 1 // 1 km/h
    }
    return goroutingkit.CarSpeedMapper(id, tags)
    

We are setting the speed to 1 km/h on that way. This makes it possible to still use the way at the cost of being very slow when using it. And in fact when we run this, we are back to our original solution because the way that we slowed down is only a few meters long and being very slow for only a few meters does not change the optimal solution.

Conclusion

With only a few lines of code we have been able to forbid and slow down certain pathways. Of course you can imagine that it is possible to have the code read those ids from a file, so you never have to touch the code itself.

To get started with Nextmv, create a free Nextmv Cloud account to get familiar with our API. If you’d like to try this out with your own data, contact us to get started with our SDK.