[OSRM-talk] OSRM-talk Digest, Vol 28, Issue 6

Francis francisrute at gmail.com
Mon Apr 13 15:14:35 UTC 2015


Hi Steve,

Indeed, the CH method is extremely fast for a static metric that will not
change and very sensible to dynamic changes in edge weights.

I see two main features to this OSRM alternative solver:
- The first one, include more static metrics on each edge. The user
preferences could be given a priori or a posteriori. A priori as a set of
goals, for example, and return the nondominated solutions that satisfy
those goals; or perform a multicriteria search to return the set of
nondominated solutions (or a subset of them) and apply the user preferences
a posteriori. I'd say the latter is a better option, since the regular user
would rather see the different solution paths before choosing one.
The idea is pre-process the graph and create shortcuts that take all
metrics into account . The search algorithm would need to change, since
Dijkstra's algorithm is mono-objective, and use a bi or multicriteria one.
Finally, instead of the optimum solution in a single metric, a list of
nondominated solution paths is returned.

- The second one, make the pre-process - prepare method more flexible to
dynamic metrics, as traffic, that will need to be updated regularly. Thus,
the query speed would be slower, but real time traffic information could be
included in the travel time returned.

All the best.

On Mon, Apr 13, 2015 at 2:02 AM, <osrm-talk-request at openstreetmap.org>
wrote:

> Send OSRM-talk mailing list submissions to
>         osrm-talk at openstreetmap.org
>
> To subscribe or unsubscribe via the World Wide Web, visit
>         https://lists.openstreetmap.org/listinfo/osrm-talk
> or, via email, send a message with subject or body 'help' to
>         osrm-talk-request at openstreetmap.org
>
> You can reach the person managing the list at
>         osrm-talk-owner at openstreetmap.org
>
> When replying, please edit your Subject line so it is more specific
> than "Re: Contents of OSRM-talk digest..."
>
>
> Today's Topics:
>
>    1. Re: OSRM-talk Digest, Vol 28, Issue 4 (Francis)
>    2. finds routes with arrivals from the right (Fernando Pacheco)
>    3. Re: OSRM-talk Digest, Vol 28, Issue 4 (Stephen Woodbridge)
>
>
> ----------------------------------------------------------------------
>
> Message: 3
> Date: Sun, 12 Apr 2015 19:55:43 -0400
> From: Stephen Woodbridge <woodbri at swoodbridge.com>
> To: osrm-talk at openstreetmap.org
> Subject: Re: [OSRM-talk] OSRM-talk Digest, Vol 28, Issue 4
> Message-ID: <552B05FF.6040805 at swoodbridge.com>
> Content-Type: text/plain; charset=utf-8; format=flowed
>
> Hi Francisco,
>
> I am a little confused by the concept of user preferences when taken in
> context of OSRM and CH (contraction hierarchy). Because of the extensive
> preprocessing required when using CH, there is not really an ability to
> offer user preferences at routing because the hierarchy would change
> based on user preferences. Everything is sort of pre-baked into the
> graph during osrm-prepare and there is little that you can do for
> preferences during routing.
>
> Maybe I'm confused and don't understand what you are try to accomplish.
> Are you proposing creating another routing engine that is not based on
> contraction hierarchy that would solve the bi- or multi-criteria
> problem? which would be cool to have an alternative solver as an option.
>
> Thanks,
>    -Steve
>
> On 4/12/2015 5:06 PM, Francis wrote:
> > -First of all, my apologies if you receive duplicated this message, I
> > sent it 2 days ago, but due to the length of the text it was sent to the
> > moderator of the list.-
> >
> > Hi Mohammed,
> >
> > I should have mentioned this option, the linear combination of criteria
> > is naturally the obvious solution when the multiobjective problem is
> > approached for the first time.
> >
> > To define a ranking procedure for the solutions can reduce the
> > multiobjective problem to a single objective problem, but it has many
> > drawbacks:
> > - An arbitrary vector of weights must be defined. Who should define that
> > weights? each user? the routing machine? How do you measure that travel
> > time is for example w_i more or less important than the economic cost,
> > or the CO2 emissions? In the majority of the cases these weights would
> > be totally arbitrary and will not reflect the user preferences.
> > - The linear combination function would add different measures, in our
> > case we are adding euros + minutes, or euros + meters + minutes, and the
> > resulting value would not have much sense.  Moreover, if you are adding
> > meters and euro cents for example, the first criterion (or metric) is
> > going to be several orders of magnitude greater than the second, i.e. if
> > you are adding a solution path with 150000 meters that costs you 900
> > euro cents (150km and 9 euros), when you add both magnitudes the second
> > one will become quite irrelevant, and solution paths that minimize the
> > distance are always preferred.
> > - To avoid the second problem, you can normalize all the criteria to be
> > expressed in a scale from 0 to 100, from the minimum value for that
> > criterion (optimum) to the worst possible one, but this would still be a
> > bad solution to model the user preferences.
> >
> > Thanks anyway for you answer Mohammed, it helped me to further develop
> > the purpose of multiobjective graph search algorithms.
> > In summary, routing on road maps with a single criterion have been
> > practically solved, it is enough to see that OSRM calculates an optimum
> > route in the order of milliseconds, and my guess is that other variants
> > like routing with multiple criteria or dynamic costs (like traffic
> > information) will be soon included in routing services. (if they are not
> > yet).
> >
> > Best regards,
> > Francisco J.
> >
> >
> >         Message: 2
> >         Date: Thu, 9 Apr 2015 19:16:18 +0100
> >         From: Mohammed Ayoub NEGGAZ <am_neggaz at esi.dz
> >         <mailto:am_neggaz at esi.dz>>
> >         To: Mailing list to discuss Project OSRM
> >         <osrm-talk at openstreetmap.org <mailto:osrm-talk at openstreetmap.org
> >>
> >         Subject: Re: [OSRM-talk] OSRM-talk Digest, Vol 27, Issue 12
> >         Message-ID:
> >
> >         <CAKxYid4dzUESz_a=
> vxvgRJgd7U0L9W7rs++2JZ7rzQri808ewQ at mail.gmail.com
> >         <mailto:vxvgRJgd7U0L9W7rs%2B%2B2JZ7rzQri808ewQ at mail.gmail.com>>
> >         Content-Type: text/plain; charset="utf-8"
> >
> >         Hi Francis,
> >
> >         I'm working on the dynamic case of the problem but I think I
> >         might help you.
> >
> >         What if you create a formula for your critera for example, for
> >         the costs
> >         that you gave you can define :
> >
> >         weight = (Travel Time * TT_Weight) + (Cost * C_Weight) where TT_
> and
> >         C_Weight are factors and weight will allways give a scalar.
> >
> >         If we are interrested in travel time we define TT_Weight = 2 <
> >         C_Weight = 4
> >         and then
> >
> >         A= (60 min, 30€) = 60*2 + 30*4 = 240
> >         B= (65 min, 25€) = 65*2 + 25*4 = 230
> >         C= (85 min, 20€) = 85*2 + 20*4 = 250
> >         D= (90 min, 15€) = 90*2 = 15*4 = 240
> >
> >         The algorithm can respond with B which (he thinks) the best
> >         route if we
> >         prefere spending less than arriving in time.
> >
> >         With this modelization, you need to define a static vector of
> >         weights (on
> >         for each property) and therefore you can use CH with Bi-Dijkstra
> >         provided
> >         by OSRM.
> >
> >         I wish this can help you.
> >
> >         Good luck in your work.
> >
> >         With respect,
> >
> >
> >         2015-04-09 17:28 GMT+01:00 Francis <francisrute at gmail.com
> >         <mailto:francisrute at gmail.com>>:
> >
> >          > Hi Romain,
> >          >
> >          > I would also be pretty interested in a bicriteria (or
> >         multicriteria) OSRM
> >          > version. What bicriteria algorithm would you like to use?
> >          > Let me first introduce myself. I'm involved in a SmartCities
> >         European
> >          > Project in my city and we would like to provide routes that
> >         consider the
> >          > minimization of multiple criteria simultaneously, like travel
> >         time,
> >          > economic cost or CO2 emissions. I'm about to finish my phD in
> >          > Multiobjective Shortest Path Problems and I'd love to apply
> >         some of the
> >          > algorithms I have developed to that project. I do believe
> >         OSRM may be a
> >          > great starting point for such a service.
> >          > I have started recently to inspect the source code. Let me
> >         point out some
> >          > of the issues concerning an OSRM service that minimizes
> >         simultaneously more
> >          > than one criterion:
> >          > - Multiple lua profiles could be necessary (one for each
> >         criterion).
> >          > - Edge weights are no longer a scalar value, but a vector of
> >         n dimensions
> >          > (n- number of criteria).
> >          > - The preprocessing of the input graph and the routing
> algorithm
> >          > (Contraction Hierarchies and bidirectional Dijkstra) must be
> >         adapted to the
> >          > Multicriteria case, specifically, the preprocessing process
> >         were shortcuts
> >          > are added as well as the search process were bidirectional
> >         Dijkstra's
> >          > algorithm is employed to find the shortest path.
> >          > - Since the concept of optimum does not apply to Bicriteria or
> >          > Multicriteria search, the new multiobjective algorithm would
> >         return a set
> >          > of solutions, typically the set of Pareto or non-dominated
> >         solutions.
> >          > - Unless the two considered criteria are highly correlated
> >         (like travel
> >          > time and distance, for example), the number of Pareto
> >         solutions is usually
> >          > big (hundreds, thounsands...), so in order to make it
> >         practical for the
> >          > user to choose one of the alternatives, something else from
> >         Multicriteria
> >          > Decision Making would be necessary (Goal Programming,
> >         Compromise Search,
> >          > tighten the concept of dominance...).
> >          > - The frontend receives and paints several routes.
> >          >
> >          > I'm not sure how this would be interesting for the rest of
> >         the community,
> >          > but I'd like to show an example of why this could be pretty
> >         useful.
> >          > Let me assume we are considering two criteria, travel time
> >         and the
> >          > economic cost of the route (gas + tolls), and there are four
> >         possible
> >          > routes:
> >          > A= (60 min, 30€)
> >          > B= (65 min, 25€)
> >          > C= (85 min, 20€)
> >          > D= (90 min, 15€)
> >          >  where (x,y) = (travel time, economic cost)
> >          >
> >          > With the current version of OSRM we obtain solution A, since
> >         it is the
> >          > fastest of all. If we load an economic cost profile in OSRM,
> >         that labels
> >          > each edge with the economic cost of traversing that edge, we
> >         obtain
> >          > solution D, since it is the cheapest. What about if the user
> >         wants a
> >          > solution with better trade-off? B and C would be good
> >         solutions too.
> >          > I think an OSRM version providing the extreme solutions for
> >         each criterion
> >          > (fastest-A and most-economical-D in this case) and a small
> >         set of solutions
> >          > with "good" trade-off between both criteria would be a very
> >         interesting
> >          > feature for the project, although I'm not sure how this could
> >         be included,
> >          > since it would involve many changes and the performance in
> >         continental maps
> >          > is unknown.
> >          >
> >          > Sorry for such a long mail.
> >          >
> >          > PS: If someone is interested these are some academic
> >         references of papers
> >          > dealing with this problem:
> >          > Preprocessing a multicriteria algorithm for routing:
> >          >
> >
> http://i11www.iti.uni-karlsruhe.de/extra/publications/dw-pps-09.pdf
> >          > Algorithm that extends A* to the Multiobjective case, keeping
> >         the same
> >          > theoretical properties than A*:
> >          > http://dl.acm.org/citation.cfm?doid=1754399.1754400
> >          > Parallelization of that algorithm:
> >          > http://algo2.iti.kit.edu/documents/Sanders%202013/ipdps.pdf
> >          >
> >          > Best regards,
> >          > Francisco J.
> >          >
> >          >>
> >          >> Subject: Digest Footer
> >          >>
> >          >> _______________________________________________
> >          >> OSRM-talk mailing list
> >          >> OSRM-talk at openstreetmap.org <mailto:
> OSRM-talk at openstreetmap.org>
> >          >> https://lists.openstreetmap.org/listinfo/osrm-talk
> >          >>
> >          >>
> >          >> ------------------------------
> >          >>
> >          >> End of OSRM-talk Digest, Vol 27, Issue 12
> >          >> *****************************************
> >          >>
> >          >
> >          >
> >          > _______________________________________________
> >          > OSRM-talk mailing list
> >          > OSRM-talk at openstreetmap.org <mailto:
> OSRM-talk at openstreetmap.org>
> >          > https://lists.openstreetmap.org/listinfo/osrm-talk
> >          >
> >          >
> >         -------------- next part --------------
> >         An HTML attachment was scrubbed...
> >         URL:
> >         <
> http://lists.openstreetmap.org/pipermail/osrm-talk/attachments/20150409/3824e0f7/attachment.html
> >
> >
> >         ------------------------------
> >
> >         Subject: Digest Footer
> >
> >         _______________________________________________
> >         OSRM-talk mailing list
> >         OSRM-talk at openstreetmap.org <mailto:OSRM-talk at openstreetmap.org>
> >         https://lists.openstreetmap.org/listinfo/osrm-talk
> >
> >
> >         ------------------------------
> >
> >         End of OSRM-talk Digest, Vol 28, Issue 4
> >         ****************************************
> >
> >
> >
> >
> >
> > _______________________________________________
> > OSRM-talk mailing list
> > OSRM-talk at openstreetmap.org
> > https://lists.openstreetmap.org/listinfo/osrm-talk
> >
>
>
> ---
> This email has been checked for viruses by Avast antivirus software.
> http://www.avast.com
>
>
>
>
> ------------------------------
>
> Subject: Digest Footer
>
> _______________________________________________
> OSRM-talk mailing list
> OSRM-talk at openstreetmap.org
> https://lists.openstreetmap.org/listinfo/osrm-talk
>
>
> ------------------------------
>
> End of OSRM-talk Digest, Vol 28, Issue 6
> ****************************************
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.openstreetmap.org/pipermail/osrm-talk/attachments/20150413/ffb174bd/attachment-0001.html>


More information about the OSRM-talk mailing list