Advanced Cycling & Running Route Generation through Mutation (Live prototype tech Demo)!

run

I’m a passionate runner, cyclist, triathlete, and programmer. In my free time, as a side project, I’ve been working to build the most advanced route generator possible.

I have a live demo up and running directly from my workstation:

https://demo.sherpa-map.com

I can’t guarantee it will stay up, as it’s a super-early prototype with all sorts of experimental features (it’s not super stable). It currently supports the entire USA, with more countries on the way. It also supports cycling, with car/vehicle support coming soon. Unlike other route generators, this doesn’t have a distance limit and runs real mutation algorithms under the hood to solve for what is probably the best route given your input criteria.

large

Note: If making extremely long routes, in the upper right corner, press settings, and lower the “iterations” and “refinements” in the performance tab. This is a custom C++ highly concurrent engine, but it only has 62 worker threads dedicated to the routing, and it will time out a generation that lasts longer than 45 seconds.

It is also capable of point-to-point routes with desired distance and characteristics that aren’t just the shortest path between, with multiple POIs equally spaced as well:

multi_new

Additionally, this lies on top of some pretty extreme datasets I’ve been building, like this, the most comprehensive paved/unpaved road surface dataset:
https://demo.sherpa-map.com/road_surface.html

As well as this “traffic” dataset built by running 1 billion point-to-point shortest path routes between population centers to determine which roads are used the most. This helps drive the “traffic calmness.” These are a few of many, many more datapoints used in this.
https://demo.sherpa-map.com/traffic.html

I also have a “scenic roads” dataset coming soon, but it’s still a few days out from finishing processing.

In any case, hope you like the demo, any feedback is appreciated, it’s been a long time in the making and probably consumed too many beautiful days just to fix one more bug…

5 Likes

I assume you’ve already explored, but Strava heat maps probably has value in something like this, to gather the tribal knowledge of the locals. I’m guessing they won’t let you leverage their data though (not that it’s their’s anyways).

Can’t touch Strava’s heatmaps with a 10 foot pole, but the truth is, it isn’t necessarily something I’d want to or seemingly need to incorporate anyway.

I already added a vast amount of data, from ones I manufactured with satellite imagery and other data points to ones gathered from OpenStreetMap and other areas. So, shoulder info, speed limit, bicycle infrastructure, etc. have been accounted for to the best ability I could.

Given this, in many cases it creates routes that follow the heatmaps, but, as it tries so many possibilities, it tends to even find and add deviations through little known paths to hop from one area of great roads to another that Strava would typically avoid, because of the untraveled nature of some of these tiny connectors.

In addition, say in cycling, I built a special weight called “flow” that actually runs a full 3D physics sim on each iterative route, scoring how well the route flows you down one hill and up another, has arcing turns, and no jackknife left handers into stop signs on a nice downhill.

I have a similar “flow” for running that’s tuned to find long uninterrupted paths/quiet roads, and so much more.

As this is using extremely powerful mutation techniques, typically seen in biomedical research, materials research, etc., and not just a quick shortest path algorithm run between 2 or 3 points arbitrarily placed out from your start location to form a loop (how most ‘route generators’ work), it tends to create routes that are, well, surprising! In a good way…

Very cool, I hope you develop this and deploy it as a product! Does it currently attempt to steer cyclists away from busy roads?

I think you need the scenic roads and urban vs rural up to make this useful. Live in a relatively small town, can be out on country roads within 5-20 minutes no matter what direction I head. I asked it to create me a 45 mile loop and it looped me all through the city. I route I would never ever in a million years do when the riding is so much better outside the city.

Yep! As a core dataset underneath it’s reasoning, I ran 1 Billion point to point routes between population centers to aggregate “likely higher trafficed roads” here’s a demo of that dataset Traffic Overlay Viewer

That, plus speed limit info, road type, and more, are integrated into every part and can be attenuated with the “road calmness” weight near the bottom.

1 Like

I actually have both of those on the way, the scenic one I’m building by walking every road and “looking” (raycasting) from cyclist head height around in typical directions, to see how many “scenic” details can be seen, from old growth forests, to lakes, to ridges, to mansions, and histoical buildings and more.

If unattractive buildings or vegetation block view, that is accounted for, as you might imagine, it’s quite computationally expensive to walk millions of miles of roads and run this, so it will still be a few days before finishing, here’s an example of that visualized:

i also have a “urban” and “rural” dataset I’m working on adding, see the picture where I overlaid a portion on a map, so those specifically are on their way and will be SUPER comprehensive.

I’ve been dreaming of an application like this. Thank you.

Feedback from 15 minutes of noodling:

  • I need the ability to save (without downloading) to compare various routes that it generates
  • I’m unable to take a generated route I really liked and modify a few filters or drag route sections within app to something i’m more familiar with
  • Reduce likelihood of ending up on major roads. I live in Seattle and there are various highways that turn to ‘roads’ but are basically still highways and you’d need a deathwish to pedal on them. There are however, perfectly amazing bike paths directly alongside (400meters away) that i struggled to get the software to use.
  • Steepness preference is quite vague. I’d love the ability to swap this to ‘max grade’ and have some smoothing to get rid of the 30% spikes that most climbs end up having.
  • Missing “l” in “Reset Al” at the top of the panel selector
  • Route surface shown either on map or elevation profile. I’m familiar with my area, and i had the paved bias nearly all the way to ‘paved’ and it still tried to put me on 8 miles of gravel.
  • Ability to drop out to street view to review the 360 view of an area.
  • Re-roll function doesnt work very intuitively (or lacks explanation about what its actually doing)
  • Let me re-order my profile selections to suggest the ‘rank’ that I care about:
    • I’ve attempted to create a route that is as flat as possible, on paths, with straight roads, that keep me moving (high flow), that also have as few uturns or backtracks possible.
    • I got an out and back that is 90% covering the same ground and the only route i’ve got with a uturn.

You have a real product here and im sure RWGPS and Strava have engineers deep into the same work.

1 Like

Well.. I may have done something terribly wrong.

40 mile cycling route, paved.. gives me 72.1 miles on lots of gravel, mtb, and hiking trails. Nonstarter. Is there a way to mandate only paved roads?

1 Like

Great points, and happy to clarify a few details. It should be “Reset All” but it may be getting cut off on some screens. My speciality is backend systems, not frontend, so I’m working on those little GUI bugs, as best as I can…

The slider for “road calmness” is specifically designed for keeping you off major roads.

That being said, and similar to paved/unpaved slider, none of these values are “hard stops” so to speak. As in, this program is a type of “solver”. I you put road calmness and target distance weight to the same amount, 3, it tries equally to balance them, so it might put you on a busier road because that’s the only way to get close to that target distance if it absolutely must.

Same with paved/unpaved, if you weigh it the same as another value, it will have the same “pull”, so, the best way to put it, with the type of route you are trying to make, say, calm roads, path preference and road calmnss prefeence should be upped quite a bit, the others should stay much lower, as they are additive and can easiliy water down each other.

The climby ones are two-fold and, true, not that intuitive explanation-wise. One of them scores the route on cumulative climb, the other scores the route on road steepness.

The best way to put it is, you can use this to make a super climby route that avoids walls, or a punch flat route, or a super flat route, or a really mean wall-seeking elevation gain-seeking, route.

Similar to curvyness, one is for overall route curvyness, the other is for road-specific curvyness.

Route surface, saving routes, and all of that aren’t really shown or present for a few reasons. The major one is that this is a demo, not like “try for a limited time and put your credit card here” demo, but a live prototype “tech” demo. I like to work in iterations and have feedback guide what I put more effort into, or what features to work on, so I often make prototypes live before they’re remotely done and integrated.

I have my own cycling route creation site (doesn’t make me any money or anything, I just made it a few years ago and keep adding to it), it has all of that stuff and this will be integrated to replace my current auto route generation as it gets closer to completion: https://sherpa-map.com

The reroll function actually changes the “seed” value that is used to seed/generate the random starting positions of the route that then gets mutated and scored. If it doesn’t auto-reroll, you’d get the same route for the same settings and same location every time, which might be preferred, or might not, but as you can see, it’s kind of a mouthful to explain, and I’m still unsure what it should be called…

Overlap and Out and back weights can push the solver to really try hard not to use the same roads, or even very nearby parallel ones. For high flow, it may to an extent, because there are only some roads that even have decent flow, so if it’s weighted really highly, it may still converge on that overlap.

Some updates I’m already adding: make a checkbox that kills any possibility of unpaved, for the roadies, so it isn’t even an option and the rest of the settings can be messed with.

Genetic evolution algorithm to find the best route to the criteria in the area… and more that I’ve mentioned in the post.

Additionally, the tech behind this is extreme; I cannot stress that enough. This a fully custom engine I built from the ground up that does things that most fleet routing software can’t do, simply for the purpose of making cool routes. It’s not AI (yet), it functions in a way that doesn’t think like a human, and often makes routes that really make me curious. I can’t wait to see the type of routes it will make when I add that scenic data…

I almost got a job as a Senior Backend Rust programmer at RideWithGPS, because of the process, I know they just tooled up the same backend routing engine that I use on my Sherpa site, Graphhopper. Fine engine, but it’s large, written in Java, and not specifically intended for bikes.

Everything about the engine behind this is actually pretty ridiculous, from Strava to Komoot, there is nothing like it. The algorithms at the core of this process are normally used in protein folding sims and scientific things lof that nature, definitely not to make fun cycling routes.

I just happen to be decent at programming, but, lack a degree and which has made it hard to really step there professionally, but it hasn’t stopped me from making all sorts of random projects. Just wait until I make this generate routes with the most tailwind (accounting for buildings and other “blockers”), or add a chatbot LLM interface… I have so many fun ideas.

3 Likes

It’s a solver, so if you weight the things the SAME as target distance weight, it may not prioritize the exact distance as much. There is a slider for preferring paved and unpaved, but I’m going to also implement a checkbox that will make it completely ignore unpaved if desired.

2 Likes

Commenting to follow, initial look it will be too complicated for the average user/person.

I generated a couple of scenarios and I have to say what it plotted intrigued me and logically/theory speaking although I avoid some of the roads like a plague - temporary riding on them for a few minutes may actually net something very interesting. I have been exploring and riding in my area for 10+ years.

I am going to keep playing with it, keep up the good work!

Defaulted to dark when it’s light here. Needs to have an auto setting for local time. Clicked on start location, clicked on loop, and it got a socket error and nothing happened.

Unless I am missing it, it seems to be missing a very important factor for me. Wind direction. This is the first thing I check when planning a route.

And it is fun to play with, but I can’t get it to produce a truly usable route. It’s putting me on roads that literally no one would use to ride a bike on when there are alternatives that get you to the same place.

It appears to be a random line generator for me.

Reiterating some key points:

  • Definitely needs a hard “paved” option: if I’m looking for a new road ride, getting a route with lots of Bay Area dirt isn’t useful
  • Right now, the route marking completely covers the road / street names

UI Issue: at least for me on my Mac using Firefox, the right hand side with the map / elevation profile doesn’t scroll, so I can’t see the elevation profile