Make travel time and edge weights independent

[emiltin]

i think it will be imporant to be able to set 'attractiveness' on ways depending on certain tags.

this should be separate from the speed, since it's still important to have the correct speeds for each sections, so that a estimated travel time can be computed.

for example, we want to prioritize streets with bike tracks over streets without, even though the speed might be the same, or slightly lower. the same goes for green routes, which people often prefer over a big road, even though the speed might be similar or lower.

one way it could be done simply is by hardcoding the tag combinations in osrm, but allowing the weight to be set in the speedprofile. something like:

if(accesTag=='bicycle' && cycleway=='track') attractiveness = w.keyVals.Find("bike_track_attractiveness"); //value set in speedprofile, say 1.4 else if(accesTag=='bicycle' && cycleway=='lane') attractiveness = w.keyVals.Find("bike_lane_attractiveness"); //value set in speedprofile, say 1.2 else if(accesTag=='bicycle' && route != nil) attractiveness = w.keyVals.Find("bike_route_attractiveness"); //value set in speedprofile, say 1.5 //other cases goes here.... else attractiveness = 1.0;

[DennisOSRM]

I have been entertaining the idea of designing some 'descriptive language' to allow users to specify more or less complex data extraction according to their needs. I am thinking of something a bit like the way cucumber specifies test scenarios. I need to think about that more.

[emiltin]

a simple way to get started would be to use specific parameters in specific situations, like i wrote above.

but a more flexible way to specify weights depending on tags would be even better, a long as it doesn't slow down preprocessing or routing too much. here's one idea:

 | tags                         | weight | note                                                       |
 | cycleway=track               | 1.3    | prefer cycle tracks, even though it might not be faster    |
 | cycleway=lane                | 1.2    | cycle tracks are also nice, although not as good as tracks |
 | highway=primary              | 0.7    | avoid primary roads without cycle track/lane               |
 | highway=secondary            | 0.8    | avoid secondary roads without cycle track/lane             |
 |                              |        |                                                            |
 | surface=[cobblestone,sand]   | 0.6    | it's not only, slow, it's also bumpy                       |
 |                              |        |                                                            |
 | highway=[footway,track,path] | 1.8    | it might be slow, but it's scenic                          |

the idea is to divide expression into blocks. in the example above, there's a block with 4 rows at the top, and two blocks with just one line. all blocks are evaluted from the top, but only one the first expression in each block that's true is used to adjust the weight.

i guess the goal is to find a good balance between flexibility and easy of use. c++ would be provide the ultimate flexibility, but be too hard to use. a simple list of highway=footway: 0.8, surface=cobblestone: 0.6 type of list might not be flexible enough.

anyways, just an input.

[DennisOSRM]

Thanks for the input. Very much appreciated.

[emiltin]

also might be worth looking at opentripplanner, i believe they're using xml files somehow

[emiltin]

in reality there might not be that many different parameters that people want to adjust. here's what i can think of right now for bike routing:

prefer bike tracks prefer bike lane prefer parks prefer bike routes prefer smaller streets prefer ways with streets lighting (at night) avoid cobblestones

i'm not saying they're not important - i think they are.

it's things that are not well handles by the speedprofile alone.

the logic of how these interact is probably fixed (it should follow common sense), so it's worth considering it's good enough to simply let people adjust a fixed set of parameters (like the list above) and use these values in the code according to some meaningful, but fixed scheme. much like the router handles oneways, etc.

[emmexx]

I wonder if there's any evolution on this issue. I'd like to be able to ad a weight based on surface and a custom tag to create a routing specific to bikes.

Thank you

maxx

[DennisOSRM]

Yes, the LUAEngine branch is under development right now and will deliver this feature.

[emiltin]

@emmexx hi, we're also working on bike routing. i would be curious to hear more about what you're working on :-)

[emmexx]

Il 06/14/2012 08:18 AM, Emil Tin scrisse:

@emmexx hi, we're also working in bike routing. i would be curious to hear more about what you're working on :-)

Hi Emil Tin,

I'm working on a project on bike routing in the city of Milan. I'm a member of a pro-bike association.

We made a survey of the streets of Milan to update osm data. We based the survey on:

• surface
• speed limit
• space for the cyclist, a new osm tag that we want to use

I'll start updating osm data in a few days.

Unfortunately I was suggested to use osrm but I didn't check the way it works until yesterday (the documentation of the project is a little bit lacking). I supposed that it'd be possible to change the edge weight and I was disappointed when I discovered that the current version of osrm uses only speed profiles.

We don't have much time spared, we'll present the project at the end of june. So I must make a decision in no time: to keep using osrm and wait for LUAEngine or to go with another routing program.

I don't know what is LUAEngine, I didn't find any info on github, I don't know LUA programming.

If there's already some working code, I can test it or work on it. But, as I said, I have to get some working result in the next 10 days.

If you can give me some additional info, you're welcome.

bye maxx

[kind3r]

In the meantime you can just add your customisations to DataStructures/ExtractorCallBacks.h around line 160 to adjust the speed limit depending on tags.

[emmexx]

Il 06/14/2012 09:26 AM, Emanuel Posescu scrisse:

In the meantime you can just add your customisations to DataStructures/ExtractorCallBacks.h around line 160 to adjust the speed limit depending on tags.

Yes, of course, but it's a pity to write code that will be thrown away in a few weeks... :-)

Anyway if I can be of any help with the LUAEngine, let me know.

Thank you maxx

[emiltin]

LUA is a language quite similar to javascript. the idea is to move all the tags parsing to small lua scripts, so it's easier to customize it depending on need.

we setup a prototype using osrm and a bicycle speedprofile at http://stormy-flower-5599.herokuapp.com/en. it incorporates turn penalties, as implemented with https://github.com/DennisOSRM/Project-OSRM/pull/240.

but we're also looking forward to a more flexible tag parsing and weight system.

can you tell more about the custom tag that want to use?

[emmexx]

Il 06/14/2012 09:42 AM, Emil Tin scrisse:

LUA is a language quite similar to javascript. the idea is to move all the tags parsing to small lua scripts, so it's easier to customize it depending on need.

I agree, this is important to customize the routing for different "vehicles".

we setup a prototype using osrm and a bicycle speedprofile at http://stormy-flower-5599.herokuapp.com/en. it incorporates turn penalties, as implemented with https://github.com/DennisOSRM/Project-OSRM/pull/240.

I'll check it asap.

but we're also looking forward to a more flexible tag parsing and weight system.

can you tell more about the custom tag that want to use?

I'm going to create a osm wiki page today or tomorrow. We're going to call this new tag "cycling_width". I know that osm fundamentalist will object that this is not a very good tag but our technical group (architects and engineers) think that this can be a good parameter, easy to survey and that can give good result in routing. cycling_width will have 3 values:

• critical
• sufficient
• good

cycling_width is the width that a cyclist has in order to ride in a secure way. It is defined as the space between the pavement or the parked cars and the running cars.

As soon as I write the wiki page, I'll send you a msg.

Thank you maxx

[emiltin]

note that the prototype doesn't work with internet explorer. click on the map to set start/end markers, then try dragging them around.

are you talking about the width of a painted cycle lane?

i think using an existing tag, like cycleway:width, will save you a lot of trouble. cycleway:width seems to have some use:

http://taginfo.openstreetmap.org/search?q=cycleway

also, subjective values like 'sufficient' and 'good' are hard for people to agree on, and use. meters are much better.

[emmexx]

Il 06/14/2012 10:13 AM, Emil Tin scrisse:

are you talking about the width of a painted cycle lane?

i think using an existing tag, like cycleway:width, will save you a lot of trouble. cycleway:width seems to have some use:

http://taginfo.openstreetmap.org/search?q=cycleway

also, subjective values like 'suffient' and 'good' are hard for people to agree on. meters are much better.

So you are one of the fundamentalists! :-)

No, I'm not referring to cycle lanes. We wanted a measure of the space in a road that can let a cyclist pedal more or less securely. The values critical, sufficient and good translate to a measure or a width but it is a little bit difficult to give a measure of a part of the road. Imagine that you are riding in a street. On some street the space between the right side and the left side of the cyclist is 3 meters, sometimes 2 meters, sometimes less. This translates to critical, etc. We can use meters instead of words. But the space for the cyclist is an interval, not a width. Something like: between 0 and 1 m: critical; between 1 m and 2 m: sufficient; more than 2m; good.

I'll try to be more precise in the wiki page

bye maxx

[emiltin]

nah, i'm practical. i still don't understand what width you're meassuring?

[emmexx]

Il 06/14/2012 12:42 PM, Emil Tin scrisse:

nah, i'm practical. i still don't understand what width you're meassuring?

In italy usally the road is shared by:

• cars in motion
• parked cars
• cyclists

In a 2 way road part of it is for parked cars. The space for a cyclist is the width of the road between the parked cars and the cars/buses/trucks driving on his left. The width of this space is an indicator of a more or less good street to ride.

The tag width is used for the total width of the road, so it is not useful.

bye maxx

[emiltin]

cycleway:width indicates the width of the bike track/lane only

[emmexx]

Il 06/14/2012 05:00 PM, Emil Tin scrisse:

cycleway:width indicates the width of the bike track/lane only

If you're referring to the "width" I wrote in my last msg, I was thinking about the width of the road:

http://wiki.openstreetmap.org/wiki/Key:width

bye maxx

[emmexx]

Now that Lua has met osrm I return to this thread to ask some question. As I already wrote, I'd like to differentiate between speed and weight. Is it possible with lua? Looking at the profile.lua file I don't understand what has changed. I mean, now I can write my rules inside profile.lua but the shortestpath function uses anyway the _Way.speed as a weight. What am I missing?

thanks maxx

[emiltin]

the branch https://github.com/DennisOSRM/Project-OSRM/compare/develop...feature/lua_weights allows you to set a weight in the lua way_function. the weight is multiplied with the speed to calculate the total impedance/cost of each segment.

this means you can prioritize ways depending on tags. for example, the testbot profile directly reads the 'weight' tag and uses it to set the weight:

  Scenario: Use weight to pick route, even when longer/slower # features/testbot/weight.feature:8
    Given the node map                                        # features/step_definitions/data.rb:9
      |   | s |   |
      | a |   | b |
    And the ways                                              # features/step_definitions/data.rb:50
      | nodes | weight |
      | ab    | 2      |
      | asb   | 1      |
    When I route I should get                                 # features/step_definitions/routing.rb:1
      | from | to | route | distance |
      | a    | b  | asb   | 282m +-1 |
      | b    | a  | asb   | 282m +-1 |

here, asb is chosen, even though both distance and travle time is longer than ab. this would be desirable when you want to prioritize bike routes, parks, etc.

speed and weight are stored for each edge, instead of just the weight.

what's missing: the total travel time should not be influenced by the weight, but it currently is. and parsing of relations in the lua script (ex bike routes). @prozessor13 demonstrated one way to parse bike relations over at https://github.com/DennisOSRM/Project-OSRM/issues/546.

some weight tests can be run using "cucumber -t @weight"

[emmexx]

Hi Emiltin, a couple of month ago I tried to test your code on my city but the results were not very good. It could be that I set the parameters wrong in the profile but, for most of the routes, there was no difference between the master and your code. I couldn't understand why.

For the travel time I found out that it is easier to use a fixed speed in the javascript code, adding a fixed time for every turn. The results are in good agreement with real travel times. That works for bike travel times on short distances, of course. For cars and long trips it's not possible to use that trick.

So now I'm using the travel time of osrm as weight and the results are good.

bye maxx

[emiltin]

hi emmexx, could you be confusing this with turn penalties? this branch handles custom weights on ways, not turn penalties. alos note that it doesn't yet implement anything in the car, bike or foot profile, only in the testbot profile.

regarding travel time for turns (not related to this branch) the purpose is to avoid trips with many turns not simply calculate the travel time.

[emmexx]

I was talking about weights. As you can see on my comments on this thread, I needed to prioritize certain ways depending on the value od some OSM tag (cycleway, surface and so on). I thought your code could solve the problem that osrm uses as "weight" travel times. But, as you know, travel times are not correct. And unfortunately I couldn't write a profile.lua that could force osrm to prioritize certain ways "my way". So I went back to osrm master and now I'm using travel times as weight, something like:

if surface="sett" then way.speed = way.speed * 0.8 elseif surface="concrete:plates" then way.speed = way.speed * 0.9 end

There's a misunderstanding about travel times and turn: since I can't get correct travel times from osrm (when using speed as weight) i ended up using a fixed speed on the client. If travel distance is 1280 meters, I compute travel time as travel distance / speed. And I get a better result when I add to that travel time a fixed time for each turn.

bye maxx

[emiltin]

the point of the branch is to allow you to set weight and speed independently. they're then multiplied to get the total cost of the segment.

without separating them, you cannot prioritize certain types of ways without getting the speed wrong. (but what's currently missing is getting the travel time correct. but it should be possible, since weight and speed are stored separately for each segment).

assuming the same average speed everywhere and recalculating the travel on the client end might be a workaround, but seems a bit rough. for example, in the features/lua_turn_penalty branch, the turn penalty is higher for sharper turns. also note the osrm can optionally add penalties for passing traffic_signals. if you work with elevation, it needs to be factored into travel time as well.

one factor we're considering adding on the client end is current/forecasted wind situation.

[emmexx]

Ok for weight and speed. I studied and debugged your code and made some modification to it to no avail. I even tried to understand how to correct the total travel time problem to no avail, again. Sorry.

As I already wrote, a fixed speed is rough but for short distances it is not much different than real times. As for turn penalties (in the client) you can use the infos returned by osrm and use a different penalty time for normal or sharp turns.

For different enviroments where you have to consider elevation or wind, a fixed speed isn't a good solution. But I had to go online with the service and, as the saying goes, perfect is the enemy of good! :-)

bye maxx

[MichalPP]

I would be extremely happy to be able to use a weight parameter (instead of speed) for bicycle routing. weight would a function of (speed, "safety", "comfort") (generally a non linear function) and speed would only calculate the route length.

a draft of safety is at http://wiki.freemap.sk/BicykelPreprocessing (the less the safer), comfort is based on surface, speed is either normal or slow/walking (or different, depending on incline)

incline: can I add a different speed to different direction of road? similar to oneway, in which one direction has speed of 0.

[karme]

i now calculate time myself => cost function can be anything (prefer cycleways, ...)

time calculation is done by adding a way list to the output (way id + direction) and looking up time in a db

[emiltin]

what's a workaround, but i think it would be better for osrm to handle it.

[stevage]

Just wondering what the latest status is on this? Do I understand there is a branch somewhere, but it hasn't been incorporated into main yet?

[ekimber]

I've been trying out bicycle profiles for routing in the UK and I'm finding the idea of a weight calculation for different profile types a lot more attractive than speed, which after all depends on the individual cyclist and should be adjustable in the client, depending on the cyclist's ability and target effort.

[emiltin]

Any news on this one? We're working on a green bike route type that prioritizes ways passing green areas. The only way to do this is currently to increase the speed, leading to very unrealistic travel times.

[eleu]

I'd ask the same question as @emiltin about any updates on this one, agreeing that this would be a very useful feature.

[emiltin]

+1

[emiltin]

hi @TheMarex, what are the plans for separating travel time and impedance? it's quite akward having to always modify travel time to prioritized certain ways over other.

for example, we're implemeting green routes for bikes, which follows parks, lakes etc. currently the only way to do that is to modify the travel time, resulting in weird travel times being returned by OSRM. this means we we need to fall back on hacks like ignoring what osrm provides and instead computing a generic travel time in the front-end as distance/average_bike_speed.

[TheMarex]

@emiltin This is certainly desirable, but would mean a lot higher memory usage. An idea would be to hold auxiliary data for each edge out of main memory (for example street name, OSM id, height difference) that would not get used for routing but could be returned with the response to augment the route.

[emiltin]

yes it would require more memory. but adding something like 8 bit for each edge might not be a huge increase compared to what's curently used?

not sure i see how storing auxilary data would solve the problem of speed and impedance not being separated, but maybe i misunderstand you?

[emiltin]

you mean only keep one value for each edge (essentially the impedance) in memory and have anything else, like travel time, stored on disk, and fetch that after the route has been found? that could work although i suppose the disk access would increase the reponse time significantly?

[emiltin]

any news on this?

[TheMarex]

This is a must-have feature for our bike routing. Just waiting for someone to free up to jump on this.

[emiltin]

ah great

[danpat]

In https://github.com/Project-OSRM/osrm-backend/issues/1844, @systemd found that capping line compression to values < 2^16 -1 (driven by the desire to use short instead of int) lead to only a surprisingly small increase in overall edge count after graph compression. It seems that the vast majority of edges compress to weight values that will fit in a short.

This hints that there are some bytes to be saved in the EdgeBasedNode, which we could re-purpose for time-independent weight, or perhaps just a scaling value (either a float, or a perhaps a https://en.wikipedia.org/wiki/Half-precision_floating-point_format).

It's possible that we could then implement this ticket with the only cost being a small number of additional edges.

Generating extra edges implies additional turn instructions being generated. We need to ensure that these are NO_TURN types so they don't emit an actual instruction.

[emiltin]

how many bits do you think would be available?

[MichalPP]

is it possible to store impedance on each edge and store speed where currently geometry is stored?

the drawback would be that time returned by table request would not be time (but distance would be distance).

the benefit would be possibility to store elevation profile, speed (or any extra info) separately, used only for post processing/display/text.

[TheMarex]

Congratulations @oxidase @jakepruitt and everyone that worked on #2399, we can now close this issue after 4 (in words FOUR) years of its creation.

EDIT: I actually it's 2017 now so 5 years. Wow.

[emiltin]

Hurray!

[jakepruitt]

Congrats everyone!

[danpat]

Anyone who has been watching this ticket - we've merge into master but feedback on this feature would be really helpful. Anyone who has the time to test it out, please do and open tickets with any problems/confusion you encounter.

[nocallaghan]

@danpat I encountered a problem extracting a pbf file using weight_name set to distance. I've opened an issue: https://github.com/Project-OSRM/osrm-backend/issues/3638

[nocallaghan]

@danpat after #3640 was merged to master, this feature is working well using british-isles-latest.pbf. In all test cases so far, the shortest route was used while maintaining accurate travel times.