Routing for Driving Pleasure
Little, Dan
Americans have miles and miles of open highways. Set the cruise and drive for hours in straight lines. Routing a user to find the fastest way from an origin to a destination is performed by any number of providers. But what if you're not interested in the shortest route? What if you're looking for the most scenic route? The most entertaining? This is a problem for planners of regularity rallies. Planners hope to provide challenging roads at legal speeds that avoid heavily residential and developed areas. OpenStreetMap, PostGIS, QGIS, and pgRouting to the rescue! Learn how to create alternative routing-cost structures to find and create new types of routes. An affinity for routing, driving, and/or gravel roads a plus. Dan "Ducky" Little
 Alright, so I'll start with a little bit more detailed introduction about myself. On the internet, I'm usually known as the Geomuse guy, an OSGeo web mapping platform. I work with another guy from Minnesota called David Bittner, and together we run DB Spatial. I also have a habit of doing reckless things with automobiles. The first example is when I crashed my first rally car upside down in the woods. You can't really tell because this was about one in the morning. I am from the great state of Minnesota. If you've been to the US and you've never been there, it's because it's the part of the country that's really, really cold and barren and I don't blame you. But it's where I'm from and how I party. As a matter of fact, I'm getting to GIS in a minute, but first I need to tell you more about other things I really enjoy. Rally, it's a little more popular here in Europe than it is in the US. Last time I gave this presentation, I really needed to explain. But there are two flavors. The first kind is the kind where you take a car, like the one I'm driving over here, and you try and not miss trees. You drive through the woods very, very quickly. On that particular day, my car got up to 100 miles an hour on gravel roads between trees. The Audi Quattro is a really popular example of that kind of a car. But there's another kind of rally called a tour rally or a time-speed distance rally. The idea is you want to arrive at a very specific location or a very specific set of locations at a very, very specific time. This is actually how rally competitions started. You travel on average about 150 miles and you want to check in to up to a dozen different checkpoints at exactly on a second or a half a second, depending on how it's being scored. Speeds average about 45 miles an hour. So you're doing roughly 70, 80 kilometers an hour and not missing a single second when you get to different places. If that doesn't sound too tricky for you, you're welcome to come out and try it. There are local clubs all over the world for this kind of stuff. All right, GIS. That's what you've all been promised, right? GIS work. It's not going to be me standing up here talking about cars. Though when I explained to my wife that I'd be talking about rally and then tomorrow or on Friday I get to talk about motorsport, she's like, what kind of conference are you going to? No, it is about GIS and here's what we'll get to it. Planning a rally can be very, very difficult. Finding interesting roads to drive on, making sure they're all interconnected and keeping everyone on time is actually a really, really tricky task just to set up. So I sort of thought about it and I thought, well, sounds like a problem a computer can solve. I've got lots of data. I've got curves. So it's all basically routing. But what do we do right now for routing? What is the classic routing use case? It is to take the least amount of time or to get to someplace the fastest. So you're minimizing distance and maximizing velocity. And really, that's kind of boring. Particularly if you've ever been to the US, you might be somewhat familiar with our interstate system and it is composed of these kinds of lines. It is a giant network where you set the cruise control at roughly 100 kilometers an hour and you hope that there's a decent radio station on within the next 100 miles. That gets kind of boring but it's also the fastest way to get from place to place. So whenever you enter directions into Google Maps, that's where it's going to take you. So the next question was what makes a road fun? How do we classify something as fun? Before we even get to the computer science part of it, how do you actually have fun in a car? So the ways you don't have fun are if it's really, really long. There's lots of traffic or there's people complaining when you drive past. If you go down a row of homes, someone's likely to call the polize. But if you're having fun, it's twisty, it's turny, you've got some speed but you don't feel completely dangerous and there's gravel. Now I know I'm completely subjective but I put a disclaimer in the slide so that you know that the gravel is disclaimed by the presenter. Which led us to math. This is actually something I got to learn about while trying to solve this problem and it's called tortuosity. And it is a way of relatively measuring how curvy a line is. And it's basically the distance of the line. So how long it is if you were to calculate it out. For those of us familiar with post just st length versus the distance between the starting and the end points. A boring example, a straight line has a tortuosity of one because the starting and the ending point that distance is equal to the measured distance of the line or the calculated distance of the line. This is a more fun example because there's a curve. And my artistic skills in present are very obvious here. If anyone needs to contract for a good looking hand drawn art presentation for half a circle I'm a guy to find. And you can see here we do all of the math and it's got a higher tortuosity value. Which means it's more fun. So what did I do to find some roads? I got the open street map data from Minnesota. Use post grass, post gs and pg routing. Which if you're new to the open source stack there's great documentation on how to install all of that stuff. But after you've installed it is where things can get a little awry. For example I found that even loading up the data can be problematic. There are a number of different ways to create topologies with the various open source tools. The two that I tried were osm to pg routing. But I got frustrated and went the easy way out which is osm to p o. It worked really well for these examples but I need to completely disclose that the license isn't particularly open. I tried to find the source and get some more clarity on it but it's not what I would consider a libre and free tool. So to open up the data all I had to do was figure out this very simple command. And if you were doing the same thing you'd have to go through and discover all of those command options yourself or like a good presenter all of my code is on github. So there's shell scripts that make everything easier. All right. So get all the data loaded calculate the tortuosity which is a really simple script again also available in github. And we finally get to the point where you can make a topology. This is where things can get a little risky because as I mentioned before I'm generally a developer I like to code things. And now I'm going to use a desktop GIS and I'm going to do it as a part of a live demo. So realistically folks be warned. All right. Here is right C I have it on the wrong screen. Basic computer use I have it down. All right. So this is the map that I got from those first few steps. This is where each one of these purple nodes is a node in the topology that was generated by OSM to PO. And each one of these lines is thematically mapped to measure the amount of fun. The darker the orange the more fun it is. For example down here there's a red road and there's a few others. This is only a medium road in terms of entertainment. But this was all generated by a bunch of SQL. And we can get my presentation back on board here. And so I had all of the data that I needed. So the next thing I wanted to do is be able to route. And route based on that fun calculation. So created a Python script that takes in two geometric points and it will create a route. Now to solve that route one of the best parts about these rallies that go for miles and miles and miles and you're paying attention to the road and your speed the entire time is that generally speaking in the morning you start with coffee. Then you do some stuff and step three is you end up beer. So in every one of my examples I'm giving you I picked a coffee house that was some distance away from a bar. So we're going to get from coffee to bar taking the most entertaining route possible. Now if you're going the reverse if you're going from the bar to coffee that should probably be a public transit route. That's not covered here. I don't think there's a way to find a more fun train. So back to QGIS for this. Which is conveniently already up on the big screen. So the first one is actually a rally that I have run. So this is you're seeing real data in action. And I'm going to turn off so you can see the difference in the lines. So the green line is the most direct route from a tequila bar that I like in Duluth, Minnesota to a bar that's basically in the middle of nowhere in a town of less than a thousand people. But it seats 300. Even for the third of the town in that bar. And that's the most direct way to get to it. On the other side what you'll see is the purple line which is the most fun way to get there. When I did some statistics on the route about 75% of that is gravel roads. Some of them I know for a fact are used for logging so they're barely wider than the car. And you can just go drive up there using those directions. The other example I have is one that's more by a populated area. This is in the Twin Cities which is near the largest population center in Minnesota. So again you start at coffee. You end at beer and you go roughly halfway across the state of Minnesota doing this. And again you can get a kind of contrast in the difference between routing for speed and routing for fun. And it's all about having those squiggly lines that would look like static if they were sound. All right so while I did this basically for trying to find fun roads to drive on for myself and my friends who are into that kind of a thing. You can really use this technique for any sort of routing where you have a very specific cost. Almost all of the tools can be recycled in order to do so. And I really hope that by checking this stuff out or using some of my code on GitHub it can actually save more people some time and headache when they're trying to figure out how to do these kind of projects. Also if you are inspired by trying to do some fun driving and want to meet some interesting people, you can always try rallying. Again there's clubs all over the world. That's my local club from back home. And thank you very much. So thank you very much Dan, so there are very few time for questions now because we have quite a session for three but we need to go and ask the fun of the project. Thank you very much. So, one of the things, so I can repeat the question. So, one of the problems with calculating tortuosity, which I also ran into, is that it is scale dependent. So, if you have, it's in a sense an average. So, the longer the line is, if you had a really curvy bit in the middle, but it was straight otherwise, you could get a misread on the tortuosity. So, one of the things I did when calculating it is I actually wrote some code, and you'll have to forgive me if it is not on GitHub, to actually break up the maximum allowable segment length. And I think I set that to somewhere around three or 400 meters, so that you were never calculating the tortuosity for a no-to-no connection that was more than three, 400 meters long. Because I ran into that exact same thing, which was because it's particularly frustrating where I'm from. Most of the roads are designed on a very grid layout, just because we have the space. So, you can have one road that is a node that is three miles long. So, you're kicking on five kilometers for a single segment in length, and end to end, it doesn't have a very high tortuosity, but somewhere in the middle, it runs through a forest. And at that point, they were going around ponds and ditches and logs and things, and then it'll have kind of a big deal. So, yeah, I ran into the same problem, but setting, gritting your data or just adding the extra nodes, let me calculate it more cleanly. So, thank you for the presentation. No, it's on. Thank you for the presentation. I was wondering maybe I missed it in routing. You generally minimize the costs, and in this case, you want to maximize the fun. How did you translate the fun into the costs? Select max from fun, and then invert the data set. So, then it would do the minimal. I use subtraction. So, I found the maximum fun level, and then inverted the column so that all of the PG routing algorithms work correctly. So, it thinks that, so there's two columns in the data set functionally. The first of which is the calculated fun, which goes from zero to much fun. And then there's a second column that does a little bit of math just to invert it so that the most fun roads have the least amount of cost. So, that way, when PG routing does it, it's still trying to minimize costs from A to B, but what it really ends up doing is picking the roads with the most fun. So, does the fun somehow correspond to the length of the road, or is it completely independent from the length? The fun rating corresponds to two factors. The first of which is the tortuosity, so how curvy it is. And that's a relative measure that is scale dependent, but it's a relative measure. And then the second is I added a multiplier to make it more fun if it was a gravel road. So, if OSM flagged it as the service type being gravel, it got like a double rating. Because really loose gravel roads in the US have the car going all like this at high speeds anyway, so it's more fun that way when you think you're going to crash. Thank you. Thank you. I had two comments. Would you consider bringing vertical curvature as well because a road that goes up and down should be more fun than a flat road? Yes, I did, and ran out of time. The other side of that is where I live, the elevation changes are not as substantial as they are in various parts of Europe. The highest differential of a road is maybe 300 meters. And another small comment, maybe bringing the amount of snow or ice that could increase the fun as well. It very much could. Luckily that can be done based on the latitude in Minnesota. But, frankly, from the bottom of the state as you get farther north there will be more snow and ice. Thank you for the presentation. The notion of fun is very specific in this case. I was just thinking, have you given some thought about Sennigkraut to provide a Sennigkraut to end user with some landmark attributes that will describe a point of view. So instead of taking just geometry, you have used some attributes like the gravel, applying the same model to a Sennigkraut for the best point of view if you add the data, like landmarks and a point of view or a nice church or whatever. So a lot of times when we're doing these types of events, you find yourselves out in pretty scenic places. But that's actually a suggestion someone else gave me while I was just spitballing this presentation, is how do you find the most scenic route someplace or the most beautiful or the most landmarked. And ostensibly if you had the data you could go from landmark to landmark as your waypoints and calculate times and things like that. So one last question. I just want to ask, I'm sure there are other measures for curveiness. For curveiness, as far as I know, so I don't remember everything, but I know that there are ones based on the scenus or closeness or something like this. Did you also consider those kind of curveiness? I went through a couple of different methods for calculating curveiness, but to make it computationally realistic without having to do a lot of, I found some of the others to be too slow. This was a very quick way for me to calculate the tortuosity and then classify it. Some of the other methods I found required doing integrals over the whole of the line. And I didn't really want to add another inset loop for calculating that integral, even if I worked out the algebra for it. This was easy to translate into SQL and was very, very fast. I have to dig it up, but I'm sure in cartographic generalization, this kind of measure is very important to make readable lines in the alps and things like this. So that's why I know a little bit that there must be some other. Thank you. Thank you for your presentation.
 Alright, so I'll start with a little bit more detailed introduction about myself.  On the internet, I'm usually known as the Geomuse guy, an OSGeo web mapping platform.  I work with another guy from Minnesota called David Bittner, and together we run DB Spatial.  I also have a habit of doing reckless things with automobiles.  The first example is when I crashed my first rally car upside down in the woods.  You can't really tell because this was about one in the morning.  I am from the great state of Minnesota.  If you've been to the US and you've never been there, it's because it's the part of  the country that's really, really cold and barren and I don't blame you.  But it's where I'm from and how I party.  As a matter of fact, I'm getting to GIS in a minute, but first I need to tell you more  about other things I really enjoy.  Rally, it's a little more popular here in Europe than it is in the US.  Last time I gave this presentation, I really needed to explain.  But there are two flavors.  The first kind is the kind where you take a car, like the one I'm driving over here,  and you try and not miss trees.  You drive through the woods very, very quickly.  On that particular day, my car got up to 100 miles an hour on gravel roads between trees.  The Audi Quattro is a really popular example of that kind of a car.  But there's another kind of rally called a tour rally or a time-speed distance rally.  The idea is you want to arrive at a very specific location or a very specific set of locations  at a very, very specific time.  This is actually how rally competitions started.  You travel on average about 150 miles and you want to check in to up to a dozen different  checkpoints at exactly on a second or a half a second, depending on how it's being scored.  Speeds average about 45 miles an hour.  So you're doing roughly 70, 80 kilometers an hour and not missing a single second when  you get to different places.  If that doesn't sound too tricky for you, you're welcome to come out and try it.  There are local clubs all over the world for this kind of stuff.  All right, GIS.  That's what you've all been promised, right?  GIS work.  It's not going to be me standing up here talking about cars.  Though when I explained to my wife that I'd be talking about rally and then tomorrow or  on Friday I get to talk about motorsport, she's like, what kind of conference are you  going to?  No, it is about GIS and here's what we'll get to it.  Planning a rally can be very, very difficult.  Finding interesting roads to drive on, making sure they're all interconnected and keeping  everyone on time is actually a really, really tricky task just to set up.  So I sort of thought about it and I thought, well, sounds like a problem a computer can  solve.  I've got lots of data.  I've got curves.  So it's all basically routing.  But what do we do right now for routing?  What is the classic routing use case?  It is to take the least amount of time or to get to someplace the fastest.  So you're minimizing distance and maximizing velocity.  And really, that's kind of boring.  Particularly if you've ever been to the US, you might be somewhat familiar with our interstate  system and it is composed of these kinds of lines.  It is a giant network where you set the cruise control at roughly 100 kilometers an hour  and you hope that there's a decent radio station on within the next 100 miles.  That gets kind of boring but it's also the fastest way to get from place to place.  So whenever you enter directions into Google Maps, that's where it's going to take you.  So the next question was what makes a road fun?  How do we classify something as fun?  Before we even get to the computer science part of it, how do you actually have fun in  a car?  So the ways you don't have fun are if it's really, really long.  There's lots of traffic or there's people complaining when you drive past.  If you go down a row of homes, someone's likely to call the polize.  But if you're having fun, it's twisty, it's turny, you've got some speed but you don't  feel completely dangerous and there's gravel.  Now I know I'm completely subjective but I put a disclaimer in the slide so that you  know that the gravel is disclaimed by the presenter.  Which led us to math.  This is actually something I got to learn about while trying to solve this problem and  it's called tortuosity.  And it is a way of relatively measuring how curvy a line is.  And it's basically the distance of the line.  So how long it is if you were to calculate it out.  For those of us familiar with post just st length versus the distance between the starting  and the end points.  A boring example, a straight line has a tortuosity of one because the starting and the ending  point that distance is equal to the measured distance of the line or the calculated distance  of the line.  This is a more fun example because there's a curve.  And my artistic skills in present are very obvious here.  If anyone needs to contract for a good looking hand drawn art presentation for half a circle  I'm a guy to find.  And you can see here we do all of the math and it's got a higher tortuosity value.  Which means it's more fun.  So what did I do to find some roads?  I got the open street map data from Minnesota.  Use post grass, post gs and pg routing.  Which if you're new to the open source stack there's great documentation on how to install  all of that stuff.  But after you've installed it is where things can get a little awry.  For example I found that even loading up the data can be problematic.  There are a number of different ways to create topologies with the various open source tools.  The two that I tried were osm to pg routing.  But I got frustrated and went the easy way out which is osm to p o.  It worked really well for these examples but I need to completely disclose that the license  isn't particularly open.  I tried to find the source and get some more clarity on it but it's not what I would consider  a libre and free tool.  So to open up the data all I had to do was figure out this very simple command.  And if you were doing the same thing you'd have to go through and discover all of those  command options yourself or like a good presenter all of my code is on github.  So there's shell scripts that make everything easier.  All right.  So get all the data loaded calculate the tortuosity which is a really simple script again also  available in github.  And we finally get to the point where you can make a topology.  This is where things can get a little risky because as I mentioned before I'm generally  a developer I like to code things.  And now I'm going to use a desktop GIS and I'm going to do it as a part of a live demo.  So realistically folks be warned.  All right.  Here is right C I have it on the wrong screen.  Basic computer use I have it down.  All right.  So this is the map that I got from those first few steps.  This is where each one of these purple nodes is a node in the topology that was generated  by OSM to PO.  And each one of these lines is thematically mapped to measure the amount of fun.  The darker the orange the more fun it is.  For example down here there's a red road and there's a few others.  This is only a medium road in terms of entertainment.  But this was all generated by a bunch of SQL.  And we can get my presentation back on board here.  And so I had all of the data that I needed.  So the next thing I wanted to do is be able to route.  And route based on that fun calculation.  So created a Python script that takes in two geometric points and it will create a route.  Now to solve that route one of the best parts about these rallies that go for miles and  miles and miles and you're paying attention to the road and your speed the entire time  is that generally speaking in the morning you start with coffee.  Then you do some stuff and step three is you end up beer.  So in every one of my examples I'm giving you I picked a coffee house that was some  distance away from a bar.  So we're going to get from coffee to bar taking the most entertaining route possible.  Now if you're going the reverse if you're going from the bar to coffee that should probably  be a public transit route.  That's not covered here.  I don't think there's a way to find a more fun train.  So back to QGIS for this.  Which is conveniently already up on the big screen.  So the first one is actually a rally that I have run.  So this is you're seeing real data in action.  And I'm going to turn off so you can see the difference in the lines.  So the green line is the most direct route from a tequila bar that I like in Duluth,  Minnesota to a bar that's basically in the middle of nowhere in a town of less than a  thousand people.  But it seats 300.  Even for the third of the town in that bar.  And that's the most direct way to get to it.  On the other side what you'll see is the purple line which is the most fun way to get there.  When I did some statistics on the route about 75% of that is gravel roads.  Some of them I know for a fact are used for logging so they're barely wider than the car.  And you can just go drive up there using those directions.  The other example I have is one that's more by a populated area.  This is in the Twin Cities which is near the largest population center in Minnesota.  So again you start at coffee.  You end at beer and you go roughly halfway across the state of Minnesota doing this.  And again you can get a kind of contrast in the difference between routing for speed and  routing for fun.  And it's all about having those squiggly lines that would look like static if they were sound.  All right so while I did this basically for trying to find fun roads to drive on for myself  and my friends who are into that kind of a thing.  You can really use this technique for any sort of routing where you have a very specific  cost.  Almost all of the tools can be recycled in order to do so.  And I really hope that by checking this stuff out or using some of my code on GitHub it  can actually save more people some time and headache when they're trying to figure out  how to do these kind of projects.  Also if you are inspired by trying to do some fun driving and want to meet some interesting  people, you can always try rallying.  Again there's clubs all over the world.  That's my local club from back home.  And thank you very much.  So thank you very much Dan, so there are very few time for questions now because we have  quite a session for three but we need to go and ask the fun of the project.  Thank you very much.  So, one of the things, so I can repeat the question.  So, one of the problems with calculating tortuosity, which I also ran into, is that it is scale dependent.  So, if you have, it's in a sense an average.  So, the longer the line is, if you had a really curvy bit in the middle, but it was straight otherwise,  you could get a misread on the tortuosity.  So, one of the things I did when calculating it is I actually wrote some code,  and you'll have to forgive me if it is not on GitHub, to actually break up the maximum allowable segment length.  And I think I set that to somewhere around three or 400 meters, so that you were never calculating the tortuosity  for a no-to-no connection that was more than three, 400 meters long.  Because I ran into that exact same thing, which was because it's particularly frustrating where I'm from.  Most of the roads are designed on a very grid layout, just because we have the space.  So, you can have one road that is a node that is three miles long.  So, you're kicking on five kilometers for a single segment in length,  and end to end, it doesn't have a very high tortuosity, but somewhere in the middle, it runs through a forest.  And at that point, they were going around ponds and ditches and logs and things, and then it'll have kind of a big deal.  So, yeah, I ran into the same problem, but setting, gritting your data or just adding the extra nodes,  let me calculate it more cleanly.  So, thank you for the presentation.  No, it's on. Thank you for the presentation.  I was wondering maybe I missed it in routing.  You generally minimize the costs, and in this case, you want to maximize the fun.  How did you translate the fun into the costs?  Select max from fun, and then invert the data set.  So, then it would do the minimal.  I use subtraction.  So, I found the maximum fun level, and then inverted the column so that all of the PG routing algorithms work correctly.  So, it thinks that, so there's two columns in the data set functionally.  The first of which is the calculated fun, which goes from zero to much fun.  And then there's a second column that does a little bit of math just to invert it so that the most fun roads have the least amount of cost.  So, that way, when PG routing does it, it's still trying to minimize costs from A to B, but what it really ends up doing is picking the roads with the most fun.  So, does the fun somehow correspond to the length of the road, or is it completely independent from the length?  The fun rating corresponds to two factors.  The first of which is the tortuosity, so how curvy it is.  And that's a relative measure that is scale dependent, but it's a relative measure.  And then the second is I added a multiplier to make it more fun if it was a gravel road.  So, if OSM flagged it as the service type being gravel, it got like a double rating.  Because really loose gravel roads in the US have the car going all like this at high speeds anyway, so it's more fun that way when you think you're going to crash.  Thank you.  Thank you.  I had two comments.  Would you consider bringing vertical curvature as well because a road that goes up and down should be more fun than a flat road?  Yes, I did, and ran out of time.  The other side of that is where I live, the elevation changes are not as substantial as they are in various parts of Europe.  The highest differential of a road is maybe 300 meters.  And another small comment, maybe bringing the amount of snow or ice that could increase the fun as well.  It very much could. Luckily that can be done based on the latitude in Minnesota.  But, frankly, from the bottom of the state as you get farther north there will be more snow and ice.  Thank you for the presentation.  The notion of fun is very specific in this case. I was just thinking, have you given some thought about Sennigkraut to provide a Sennigkraut to end user with some landmark attributes that will describe a point of view.  So instead of taking just geometry, you have used some attributes like the gravel, applying the same model to a Sennigkraut for the best point of view if you add the data, like landmarks and a point of view or a nice church or whatever.  So a lot of times when we're doing these types of events, you find yourselves out in pretty scenic places.  But that's actually a suggestion someone else gave me while I was just spitballing this presentation, is how do you find the most scenic route someplace or the most beautiful or the most landmarked.  And ostensibly if you had the data you could go from landmark to landmark as your waypoints and calculate times and things like that.  So one last question.  I just want to ask, I'm sure there are other measures for curveiness.  For curveiness, as far as I know, so I don't remember everything, but I know that there are ones based on the scenus or closeness or something like this. Did you also consider those kind of curveiness?  I went through a couple of different methods for calculating curveiness, but to make it computationally realistic without having to do a lot of, I found some of the others to be too slow.  This was a very quick way for me to calculate the tortuosity and then classify it.  Some of the other methods I found required doing integrals over the whole of the line.  And I didn't really want to add another inset loop for calculating that integral, even if I worked out the algebra for it.  This was easy to translate into SQL and was very, very fast.  I have to dig it up, but I'm sure in cartographic generalization, this kind of measure is very important to make readable lines in the alps and things like this.  So that's why I know a little bit that there must be some other.  Thank you.  Thank you for your presentation.
foss4g-2016-1064-routing_for_driving_pleasure-hd_0_227.png foss4g-2016-1064-routing_for_driving_pleasure-hd_228_10259.png foss4g-2016-1064-routing_for_driving_pleasure-hd_10260_10331.png foss4g-2016-1064-routing_for_driving_pleasure-hd_10332_10883.png foss4g-2016-1064-routing_for_driving_pleasure-hd_10884_11267.png foss4g-2016-1064-routing_for_driving_pleasure-hd_11268_11963.png foss4g-2016-1064-routing_for_driving_pleasure-hd_11964_12107.png foss4g-2016-1064-routing_for_driving_pleasure-hd_12108_13547.png foss4g-2016-1064-routing_for_driving_pleasure-hd_13548_15431.png foss4g-2016-1064-routing_for_driving_pleasure-hd_15432_18551.png foss4g-2016-1064-routing_for_driving_pleasure-hd_18552_18839.png foss4g-2016-1064-routing_for_driving_pleasure-hd_18840_22139.png foss4g-2016-1064-routing_for_driving_pleasure-hd_22140_24071.png foss4g-2016-1064-routing_for_driving_pleasure-hd_24072_24455.png foss4g-2016-1064-routing_for_driving_pleasure-hd_24456_24899.png foss4g-2016-1064-routing_for_driving_pleasure-hd_24900_25223.png foss4g-2016-1064-routing_for_driving_pleasure-hd_25224_25583.png foss4g-2016-1064-routing_for_driving_pleasure-hd_25584_26075.png foss4g-2016-1064-routing_for_driving_pleasure-hd_26076_26303.png foss4g-2016-1064-routing_for_driving_pleasure-hd_26304_27011.png foss4g-2016-1064-routing_for_driving_pleasure-hd_27012_28379.png foss4g-2016-1064-routing_for_driving_pleasure-hd_28380_29159.png foss4g-2016-1064-routing_for_driving_pleasure-hd_29160_29207.png foss4g-2016-1064-routing_for_driving_pleasure-hd_29208_29267.png foss4g-2016-1064-routing_for_driving_pleasure-hd_29268_30791.png foss4g-2016-1064-routing_for_driving_pleasure-hd_30792_30851.png foss4g-2016-1064-routing_for_driving_pleasure-hd_30852_31403.png foss4g-2016-1064-routing_for_driving_pleasure-hd_31404_31561.png
Alright, so I'll start with a little bit more detailed introduction about myself. On the internet, I'm usually known as the Geomuse guy, an OSGeo web mapping platform. I work with another guy from Minnesota called David Bittner, and together we run DB Spatial. I also have a habit of doing reckless things with automobiles. The first example is when I crashed my first rally car upside down in the woods. You can't really tell because this was about one in the morning. I am from the great state of Minnesota. If you've been to the US and you've never been there, it's because it's the part of the country that's really, really cold and barren and I don't blame you. But it's where I'm from and how I party. As a matter of fact, I'm getting to GIS in a minute, but first I need to tell you more about other things I really enjoy. Rally, it's a little more popular here in Europe than it is in the US. Last time I gave this presentation, I really needed to explain. But there are two flavors. The first kind is the kind where you take a car, like the one I'm driving over here, and you try and not miss trees. You drive through the woods very, very quickly. On that particular day, my car got up to 100 miles an hour on gravel roads between trees. The Audi Quattro is a really popular example of that kind of a car. But there's another kind of rally called a tour rally or a time-speed distance rally. The idea is you want to arrive at a very specific location or a very specific set of locations at a very, very specific time. This is actually how rally competitions started. You travel on average about 150 miles and you want to check in to up to a dozen different checkpoints at exactly on a second or a half a second, depending on how it's being scored. Speeds average about 45 miles an hour. So you're doing roughly 70, 80 kilometers an hour and not missing a single second when you get to different places. If that doesn't sound too tricky for you, you're welcome to come out and try it. There are local clubs all over the world for this kind of stuff. All right, GIS. That's what you've all been promised, right? GIS work. It's not going to be me standing up here talking about cars. Though when I explained to my wife that I'd be talking about rally and then tomorrow or on Friday I get to talk about motorsport, she's like, what kind of conference are you going to? No, it is about GIS and here's what we'll get to it. Planning a rally can be very, very difficult. Finding interesting roads to drive on, making sure they're all interconnected and keeping everyone on time is actually a really, really tricky task just to set up. So I sort of thought about it and I thought, well, sounds like a problem a computer can solve. I've got lots of data. I've got curves. So it's all basically routing. But what do we do right now for routing? What is the classic routing use case? It is to take the least amount of time or to get to someplace the fastest. So you're minimizing distance and maximizing velocity. And really, that's kind of boring. Particularly if you've ever been to the US, you might be somewhat familiar with our interstate system and it is composed of these kinds of lines. It is a giant network where you set the cruise control at roughly 100 kilometers an hour and you hope that there's a decent radio station on within the next 100 miles. That gets kind of boring but it's also the fastest way to get from place to place. So whenever you enter directions into Google Maps, that's where it's going to take you. So the next question was what makes a road fun? How do we classify something as fun? Before we even get to the computer science part of it, how do you actually have fun in a car? So the ways you don't have fun are if it's really, really long. There's lots of traffic or there's people complaining when you drive past. If you go down a row of homes, someone's likely to call the polize. But if you're having fun, it's twisty, it's turny, you've got some speed but you don't feel completely dangerous and there's gravel. Now I know I'm completely subjective but I put a disclaimer in the slide so that you know that the gravel is disclaimed by the presenter. Which led us to math. This is actually something I got to learn about while trying to solve this problem and it's called tortuosity. And it is a way of relatively measuring how curvy a line is. And it's basically the distance of the line. So how long it is if you were to calculate it out. For those of us familiar with post just st length versus the distance between the starting and the end points. A boring example, a straight line has a tortuosity of one because the starting and the ending point that distance is equal to the measured distance of the line or the calculated distance of the line. This is a more fun example because there's a curve. And my artistic skills in present are very obvious here. If anyone needs to contract for a good looking hand drawn art presentation for half a circle I'm a guy to find. And you can see here we do all of the math and it's got a higher tortuosity value. Which means it's more fun. So what did I do to find some roads? I got the open street map data from Minnesota. Use post grass, post gs and pg routing. Which if you're new to the open source stack there's great documentation on how to install all of that stuff. But after you've installed it is where things can get a little awry. For example I found that even loading up the data can be problematic. There are a number of different ways to create topologies with the various open source tools. The two that I tried were osm to pg routing. But I got frustrated and went the easy way out which is osm to p o. It worked really well for these examples but I need to completely disclose that the license isn't particularly open. I tried to find the source and get some more clarity on it but it's not what I would consider a libre and free tool. So to open up the data all I had to do was figure out this very simple command. And if you were doing the same thing you'd have to go through and discover all of those command options yourself or like a good presenter all of my code is on github. So there's shell scripts that make everything easier. All right. So get all the data loaded calculate the tortuosity which is a really simple script again also available in github. And we finally get to the point where you can make a topology. This is where things can get a little risky because as I mentioned before I'm generally a developer I like to code things. And now I'm going to use a desktop GIS and I'm going to do it as a part of a live demo. So realistically folks be warned. All right. Here is right C I have it on the wrong screen. Basic computer use I have it down. All right. So this is the map that I got from those first few steps. This is where each one of these purple nodes is a node in the topology that was generated by OSM to PO. And each one of these lines is thematically mapped to measure the amount of fun. The darker the orange the more fun it is. For example down here there's a red road and there's a few others. This is only a medium road in terms of entertainment. But this was all generated by a bunch of SQL. And we can get my presentation back on board here. And so I had all of the data that I needed. So the next thing I wanted to do is be able to route. And route based on that fun calculation. So created a Python script that takes in two geometric points and it will create a route. Now to solve that route one of the best parts about these rallies that go for miles and miles and miles and you're paying attention to the road and your speed the entire time is that generally speaking in the morning you start with coffee. Then you do some stuff and step three is you end up beer. So in every one of my examples I'm giving you I picked a coffee house that was some distance away from a bar. So we're going to get from coffee to bar taking the most entertaining route possible. Now if you're going the reverse if you're going from the bar to coffee that should probably be a public transit route. That's not covered here. I don't think there's a way to find a more fun train. So back to QGIS for this. Which is conveniently already up on the big screen. So the first one is actually a rally that I have run. So this is you're seeing real data in action. And I'm going to turn off so you can see the difference in the lines. So the green line is the most direct route from a tequila bar that I like in Duluth, Minnesota to a bar that's basically in the middle of nowhere in a town of less than a thousand people. But it seats 300. Even for the third of the town in that bar. And that's the most direct way to get to it. On the other side what you'll see is the purple line which is the most fun way to get there. When I did some statistics on the route about 75% of that is gravel roads. Some of them I know for a fact are used for logging so they're barely wider than the car. And you can just go drive up there using those directions. The other example I have is one that's more by a populated area. This is in the Twin Cities which is near the largest population center in Minnesota. So again you start at coffee. You end at beer and you go roughly halfway across the state of Minnesota doing this. And again you can get a kind of contrast in the difference between routing for speed and routing for fun. And it's all about having those squiggly lines that would look like static if they were sound. All right so while I did this basically for trying to find fun roads to drive on for myself and my friends who are into that kind of a thing. You can really use this technique for any sort of routing where you have a very specific cost. Almost all of the tools can be recycled in order to do so. And I really hope that by checking this stuff out or using some of my code on GitHub it can actually save more people some time and headache when they're trying to figure out how to do these kind of projects. Also if you are inspired by trying to do some fun driving and want to meet some interesting people, you can always try rallying. Again there's clubs all over the world. That's my local club from back home. And thank you very much. So thank you very much Dan, so there are very few time for questions now because we have quite a session for three but we need to go and ask the fun of the project. Thank you very much. So, one of the things, so I can repeat the question. So, one of the problems with calculating tortuosity, which I also ran into, is that it is scale dependent. So, if you have, it's in a sense an average. So, the longer the line is, if you had a really curvy bit in the middle, but it was straight otherwise, you could get a misread on the tortuosity. So, one of the things I did when calculating it is I actually wrote some code, and you'll have to forgive me if it is not on GitHub, to actually break up the maximum allowable segment length. And I think I set that to somewhere around three or 400 meters, so that you were never calculating the tortuosity for a no-to-no connection that was more than three, 400 meters long. Because I ran into that exact same thing, which was because it's particularly frustrating where I'm from. Most of the roads are designed on a very grid layout, just because we have the space. So, you can have one road that is a node that is three miles long. So, you're kicking on five kilometers for a single segment in length, and end to end, it doesn't have a very high tortuosity, but somewhere in the middle, it runs through a forest. And at that point, they were going around ponds and ditches and logs and things, and then it'll have kind of a big deal. So, yeah, I ran into the same problem, but setting, gritting your data or just adding the extra nodes, let me calculate it more cleanly. So, thank you for the presentation. No, it's on. Thank you for the presentation. I was wondering maybe I missed it in routing. You generally minimize the costs, and in this case, you want to maximize the fun. How did you translate the fun into the costs? Select max from fun, and then invert the data set. So, then it would do the minimal. I use subtraction. So, I found the maximum fun level, and then inverted the column so that all of the PG routing algorithms work correctly. So, it thinks that, so there's two columns in the data set functionally. The first of which is the calculated fun, which goes from zero to much fun. And then there's a second column that does a little bit of math just to invert it so that the most fun roads have the least amount of cost. So, that way, when PG routing does it, it's still trying to minimize costs from A to B, but what it really ends up doing is picking the roads with the most fun. So, does the fun somehow correspond to the length of the road, or is it completely independent from the length? The fun rating corresponds to two factors. The first of which is the tortuosity, so how curvy it is. And that's a relative measure that is scale dependent, but it's a relative measure. And then the second is I added a multiplier to make it more fun if it was a gravel road. So, if OSM flagged it as the service type being gravel, it got like a double rating. Because really loose gravel roads in the US have the car going all like this at high speeds anyway, so it's more fun that way when you think you're going to crash. Thank you. Thank you. I had two comments. Would you consider bringing vertical curvature as well because a road that goes up and down should be more fun than a flat road? Yes, I did, and ran out of time. The other side of that is where I live, the elevation changes are not as substantial as they are in various parts of Europe. The highest differential of a road is maybe 300 meters. And another small comment, maybe bringing the amount of snow or ice that could increase the fun as well. It very much could. Luckily that can be done based on the latitude in Minnesota. But, frankly, from the bottom of the state as you get farther north there will be more snow and ice. Thank you for the presentation. The notion of fun is very specific in this case. I was just thinking, have you given some thought about Sennigkraut to provide a Sennigkraut to end user with some landmark attributes that will describe a point of view. So instead of taking just geometry, you have used some attributes like the gravel, applying the same model to a Sennigkraut for the best point of view if you add the data, like landmarks and a point of view or a nice church or whatever. So a lot of times when we're doing these types of events, you find yourselves out in pretty scenic places. But that's actually a suggestion someone else gave me while I was just spitballing this presentation, is how do you find the most scenic route someplace or the most beautiful or the most landmarked. And ostensibly if you had the data you could go from landmark to landmark as your waypoints and calculate times and things like that. So one last question. I just want to ask, I'm sure there are other measures for curveiness. For curveiness, as far as I know, so I don't remember everything, but I know that there are ones based on the scenus or closeness or something like this. Did you also consider those kind of curveiness? I went through a couple of different methods for calculating curveiness, but to make it computationally realistic without having to do a lot of, I found some of the others to be too slow. This was a very quick way for me to calculate the tortuosity and then classify it. Some of the other methods I found required doing integrals over the whole of the line. And I didn't really want to add another inset loop for calculating that integral, even if I worked out the algebra for it. This was easy to translate into SQL and was very, very fast. I have to dig it up, but I'm sure in cartographic generalization, this kind of measure is very important to make readable lines in the alps and things like this. So that's why I know a little bit that there must be some other. Thank you. Thank you for your presentation.
all basically routing. But what do we do right now for routing? What is the classic routing use network where you set the cruise control at roughly 100 kilometers an hour and you hope that the fastest way to get from place to place. So distance of the line. This is a more fun example routing. Which if you're new to the open source stack there's great documentation on how to of different ways to create topologies with the that go for miles and miles and miles and you're taking the most entertaining route possible. Now for trying to find fun roads to drive on for are inspired by trying to do some fun driving and Because really loose gravel roads in the US have provide a Sennigkraut to end user with some applying the same model to a Sennigkraut for the the most scenic route someplace or the most