<div dir="ltr"><div style="font-size:12.8000001907349px"><div><div><div><div><div><div><div><span style="font-size:12.8000001907349px">-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.-</span><br></div><div><br></div><div>Hi Mohammed,</div><div><br></div>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. <br><br></div>To define a ranking procedure for the solutions can reduce the multiobjective problem to a single objective problem, but it has many drawbacks:<br></div>- 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.<br></div>- 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. <br></div>- 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.<br><br></div>Thanks anyway for you answer Mohammed, it helped me to further develop the purpose of multiobjective graph search algorithms. <br>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).<br><br></div>Best regards,<br></div><span style="font-size:12.8000001907349px">Francisco J.</span><div><span style="font-size:12.8000001907349px"><br></span><div class="gmail_extra"><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div dir="ltr"><div><div class="h5"><div><div><div class="gmail_extra"><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
<br>
Message: 2<br>
Date: Thu, 9 Apr 2015 19:16:18 +0100<br>
From: Mohammed Ayoub NEGGAZ <<a href="mailto:am_neggaz@esi.dz" target="_blank">am_neggaz@esi.dz</a>><br>
To: Mailing list to discuss Project OSRM <<a href="mailto:osrm-talk@openstreetmap.org" target="_blank">osrm-talk@openstreetmap.org</a>><br>
Subject: Re: [OSRM-talk] OSRM-talk Digest, Vol 27, Issue 12<br>
Message-ID:<br>
        <CAKxYid4dzUESz_a=<a href="mailto:vxvgRJgd7U0L9W7rs%2B%2B2JZ7rzQri808ewQ@mail.gmail.com" target="_blank">vxvgRJgd7U0L9W7rs++2JZ7rzQri808ewQ@mail.gmail.com</a>><br>
Content-Type: text/plain; charset="utf-8"<br>
<br>
Hi Francis,<br>
<br>
I'm working on the dynamic case of the problem but I think I might help you.<br>
<br>
What if you create a formula for your critera for example, for the costs<br>
that you gave you can define :<br>
<br>
weight = (Travel Time * TT_Weight) + (Cost * C_Weight) where TT_ and<br>
C_Weight are factors and weight will allways give a scalar.<br>
<br>
If we are interrested in travel time we define TT_Weight = 2 < C_Weight = 4<br>
and then<br>
<br>
A= (60 min, 30€) = 60*2 + 30*4 = 240<br>
B= (65 min, 25€) = 65*2 + 25*4 = 230<br>
C= (85 min, 20€) = 85*2 + 20*4 = 250<br>
D= (90 min, 15€) = 90*2 = 15*4 = 240<br>
<br>
The algorithm can respond with B which (he thinks) the best route if we<br>
prefere spending less than arriving in time.<br>
<br>
With this modelization, you need to define a static vector of weights (on<br>
for each property) and therefore you can use CH with Bi-Dijkstra provided<br>
by OSRM.<br>
<br>
I wish this can help you.<br>
<br>
Good luck in your work.<br>
<br>
With respect,<br>
<br>
<br>
2015-04-09 17:28 GMT+01:00 Francis <<a href="mailto:francisrute@gmail.com" target="_blank">francisrute@gmail.com</a>>:<br>
<br>
> Hi Romain,<br>
><br>
> I would also be pretty interested in a bicriteria (or multicriteria) OSRM<br>
> version. What bicriteria algorithm would you like to use?<br>
> Let me first introduce myself. I'm involved in a SmartCities European<br>
> Project in my city and we would like to provide routes that consider the<br>
> minimization of multiple criteria simultaneously, like travel time,<br>
> economic cost or CO2 emissions. I'm about to finish my phD in<br>
> Multiobjective Shortest Path Problems and I'd love to apply some of the<br>
> algorithms I have developed to that project. I do believe OSRM may be a<br>
> great starting point for such a service.<br>
> I have started recently to inspect the source code. Let me point out some<br>
> of the issues concerning an OSRM service that minimizes simultaneously more<br>
> than one criterion:<br>
> - Multiple lua profiles could be necessary (one for each criterion).<br>
> - Edge weights are no longer a scalar value, but a vector of n dimensions<br>
> (n- number of criteria).<br>
> - The preprocessing of the input graph and the routing algorithm<br>
> (Contraction Hierarchies and bidirectional Dijkstra) must be adapted to the<br>
> Multicriteria case, specifically, the preprocessing process were shortcuts<br>
> are added as well as the search process were bidirectional Dijkstra's<br>
> algorithm is employed to find the shortest path.<br>
> - Since the concept of optimum does not apply to Bicriteria or<br>
> Multicriteria search, the new multiobjective algorithm would return a set<br>
> of solutions, typically the set of Pareto or non-dominated solutions.<br>
> - Unless the two considered criteria are highly correlated (like travel<br>
> time and distance, for example), the number of Pareto solutions is usually<br>
> big (hundreds, thounsands...), so in order to make it practical for the<br>
> user to choose one of the alternatives, something else from Multicriteria<br>
> Decision Making would be necessary (Goal Programming, Compromise Search,<br>
> tighten the concept of dominance...).<br>
> - The frontend receives and paints several routes.<br>
><br>
> I'm not sure how this would be interesting for the rest of the community,<br>
> but I'd like to show an example of why this could be pretty useful.<br>
> Let me assume we are considering two criteria, travel time and the<br>
> economic cost of the route (gas + tolls), and there are four possible<br>
> routes:<br>
> A= (60 min, 30€)<br>
> B= (65 min, 25€)<br>
> C= (85 min, 20€)<br>
> D= (90 min, 15€)<br>
>  where (x,y) = (travel time, economic cost)<br>
><br>
> With the current version of OSRM we obtain solution A, since it is the<br>
> fastest of all. If we load an economic cost profile in OSRM, that labels<br>
> each edge with the economic cost of traversing that edge, we obtain<br>
> solution D, since it is the cheapest. What about if the user wants a<br>
> solution with better trade-off? B and C would be good solutions too.<br>
> I think an OSRM version providing the extreme solutions for each criterion<br>
> (fastest-A and most-economical-D in this case) and a small set of solutions<br>
> with "good" trade-off between both criteria would be a very interesting<br>
> feature for the project, although I'm not sure how this could be included,<br>
> since it would involve many changes and the performance in continental maps<br>
> is unknown.<br>
><br>
> Sorry for such a long mail.<br>
><br>
> PS: If someone is interested these are some academic references of papers<br>
> dealing with this problem:<br>
> Preprocessing a multicriteria algorithm for routing:<br>
> <a href="http://i11www.iti.uni-karlsruhe.de/extra/publications/dw-pps-09.pdf" target="_blank">http://i11www.iti.uni-karlsruhe.de/extra/publications/dw-pps-09.pdf</a><br>
> Algorithm that extends A* to the Multiobjective case, keeping the same<br>
> theoretical properties than A*:<br>
> <a href="http://dl.acm.org/citation.cfm?doid=1754399.1754400" target="_blank">http://dl.acm.org/citation.cfm?doid=1754399.1754400</a><br>
> Parallelization of that algorithm:<br>
> <a href="http://algo2.iti.kit.edu/documents/Sanders%202013/ipdps.pdf" target="_blank">http://algo2.iti.kit.edu/documents/Sanders%202013/ipdps.pdf</a><br>
><br>
> Best regards,<br>
> Francisco J.<br>
><br>
>><br>
>> Subject: Digest Footer<br>
>><br>
>> _______________________________________________<br>
>> OSRM-talk mailing list<br>
>> <a href="mailto:OSRM-talk@openstreetmap.org" target="_blank">OSRM-talk@openstreetmap.org</a><br>
>> <a href="https://lists.openstreetmap.org/listinfo/osrm-talk" target="_blank">https://lists.openstreetmap.org/listinfo/osrm-talk</a><br>
>><br>
>><br>
>> ------------------------------<br>
>><br>
>> End of OSRM-talk Digest, Vol 27, Issue 12<br>
>> *****************************************<br>
>><br>
><br>
><br>
> _______________________________________________<br>
> OSRM-talk mailing list<br>
> <a href="mailto:OSRM-talk@openstreetmap.org" target="_blank">OSRM-talk@openstreetmap.org</a><br>
> <a href="https://lists.openstreetmap.org/listinfo/osrm-talk" target="_blank">https://lists.openstreetmap.org/listinfo/osrm-talk</a><br>
><br>
><br>
-------------- next part --------------<br>
An HTML attachment was scrubbed...<br>
URL: <<a href="http://lists.openstreetmap.org/pipermail/osrm-talk/attachments/20150409/3824e0f7/attachment.html" target="_blank">http://lists.openstreetmap.org/pipermail/osrm-talk/attachments/20150409/3824e0f7/attachment.html</a>><br>
<br>
------------------------------<br>
<br>
Subject: Digest Footer<br>
<br>
_______________________________________________<br>
OSRM-talk mailing list<br>
<a href="mailto:OSRM-talk@openstreetmap.org" target="_blank">OSRM-talk@openstreetmap.org</a><br>
<a href="https://lists.openstreetmap.org/listinfo/osrm-talk" target="_blank">https://lists.openstreetmap.org/listinfo/osrm-talk</a><br>
<br>
<br>
------------------------------<br>
<br>
End of OSRM-talk Digest, Vol 28, Issue 4<br>
****************************************<br>
</blockquote></div><br></div></div></div></div></div></div>
</blockquote></div><br></div></div></div>