[OSRM-talk] OSRM-talk Digest, Vol 27, Issue 12

Mohammed Ayoub NEGGAZ am_neggaz at esi.dz
Thu Apr 9 18:16:18 UTC 2015


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>:

> 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.
>
>
> On Tue, Mar 31, 2015 at 2:00 PM, <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. alternative route (Romain NKONGO)
>>
>>
>> ----------------------------------------------------------------------
>>
>> Message: 1
>> Date: Tue, 31 Mar 2015 11:10:14 +0200
>> From: Romain NKONGO <romain.rnk49 at gmail.com>
>> To: Mailing list to discuss Project OSRM <osrm-talk at openstreetmap.org>
>> Subject: [OSRM-talk] alternative route
>> Message-ID:
>>         <CAAwSghEqK-w+MQ+kdi3r9hPKvv6tuZ0FFT1Nq9cDH3t_wLOX=
>> g at mail.gmail.com>
>> Content-Type: text/plain; charset="utf-8"
>>
>> Hello everyone,
>>
>> I've succeeded to add a new criterion called cyclability to OSRM, which is
>> associated with each edge in the graph. It is created in bicycle.lua file
>> and I managed to bring it all through the processing phase and to make a
>> mean value on each segment of the shortest path. In the JSON, I now have a
>> 9th value for each element in route instructions and a mean value in route
>> summary.
>>
>> Now I intend to add a bicriteria algorithm to the routing phase (based on
>> Label Setting). Such an algorithm would return multiple paths as results
>> to
>> one viaroute query. The problem is the original implementation allows 2
>> routes at most to be returned.
>>
>> Has anyone tried to increase the limit of routes returned? If not, what is
>> the condition for an alternative route and is there at least a way to
>> force
>> OSRM to show an alternative route?
>>
>> Thanks in advance for the help.
>> Romain NKONGO.
>> -------------- next part --------------
>> An HTML attachment was scrubbed...
>> URL: <
>> http://lists.openstreetmap.org/pipermail/osrm-talk/attachments/20150331/1d449886/attachment-0001.html
>> >
>>
>> ------------------------------
>>
>> 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 27, Issue 12
>> *****************************************
>>
>
>
> _______________________________________________
> OSRM-talk mailing list
> 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-0001.html>


More information about the OSRM-talk mailing list