<div dir="ltr">Hi Francis,<div><br></div><div>I'm working on the dynamic case of the problem but I think I might help you.</div><div><br></div><div>What if you create a formula for your critera for example, for the costs that you gave you can define :</div><div><br></div><div>weight = (Travel Time * TT_Weight) + (Cost * C_Weight) where TT_ and C_Weight are factors and weight will allways give a scalar.</div><div><br></div><div>If we are interrested in travel time we define TT_Weight = 2 < C_Weight = 4 and then</div><div><br></div><div><span style="color:rgb(0,0,0);font-size:13px">A= (60 min, 30€) = 60*2 + 30*4 = 240</span><br style="color:rgb(0,0,0);font-size:13px"><div style="color:rgb(0,0,0);font-size:13px">B= (65 min, 25€) = 65*2 + 25*4 = 230<br></div><div style="color:rgb(0,0,0);font-size:13px">C= (85 min, 20€) = 85*2 + 20*4 = 250<br></div><div style="color:rgb(0,0,0);font-size:13px">D= (90 min, 15€) = 90*2 = 15*4 = 240</div></div><div style="color:rgb(0,0,0);font-size:13px"><br></div><div style="color:rgb(0,0,0);font-size:13px">The algorithm can respond with B which (he thinks) the best route if we prefere spending less than arriving in time.</div><div style="color:rgb(0,0,0);font-size:13px"><br></div><div style="color:rgb(0,0,0);font-size:13px">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.</div><div style="color:rgb(0,0,0);font-size:13px"><br></div><div style="color:rgb(0,0,0);font-size:13px">I wish this can help you.</div><div style="color:rgb(0,0,0);font-size:13px"><br></div><div style="color:rgb(0,0,0);font-size:13px">Good luck in your work.</div><div style="color:rgb(0,0,0);font-size:13px"><br></div><div style="color:rgb(0,0,0);font-size:13px">With respect,</div><div style="color:rgb(0,0,0);font-size:13px"><br></div></div><div class="gmail_extra"><br><div class="gmail_quote">2015-04-09 17:28 GMT+01:00 Francis <span dir="ltr"><<a href="mailto:francisrute@gmail.com" target="_blank">francisrute@gmail.com</a>></span>:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div><div><div><div><div><div><div><div><div>Hi Romain,<br><br></div>I would also be pretty interested in a 
bicriteria (or multicriteria) OSRM version. What bicriteria algorithm would you like to use? <br>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. <br></div>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:<br></div>- Multiple lua profiles could be necessary (one for each criterion).<br></div><div>- Edge weights are no longer a scalar value, but a vector of n dimensions (n- number of criteria).<br></div>- 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.<br></div>- 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. <br></div>- 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...).<br></div><div>- The frontend receives and paints several routes.<br></div><div><br></div>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.<br></div>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:<br></div>A= (60 min, 30€)<br><div>B= (65 min, 25€)<br></div><div>C= (85 min, 20€)<br></div><div>D= (90 min, 15€)<br></div><div><div><div><div> where (x,y) = (travel time, economic cost)<br><br></div><div>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.<br></div><div>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. <br><br></div><div>Sorry for such a long mail.<br><br></div><div>PS: If someone is interested these are some academic references of papers 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></div><div>Algorithm that extends A* to the Multiobjective case, keeping the same 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></div><div>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></div><div>Best regards,<br></div><div>Francisco J.<br></div><div><br></div></div></div></div></div><div class="gmail_extra"><br><div class="gmail_quote">On Tue, Mar 31, 2015 at 2:00 PM,  <span dir="ltr"><<a href="mailto:osrm-talk-request@openstreetmap.org" target="_blank">osrm-talk-request@openstreetmap.org</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Send OSRM-talk mailing list submissions to<br>
        <a href="mailto:osrm-talk@openstreetmap.org" target="_blank">osrm-talk@openstreetmap.org</a><br>
<br>
To subscribe or unsubscribe via the World Wide Web, visit<br>
        <a href="https://lists.openstreetmap.org/listinfo/osrm-talk" target="_blank">https://lists.openstreetmap.org/listinfo/osrm-talk</a><br>
or, via email, send a message with subject or body 'help' to<br>
        <a href="mailto:osrm-talk-request@openstreetmap.org" target="_blank">osrm-talk-request@openstreetmap.org</a><br>
<br>
You can reach the person managing the list at<br>
        <a href="mailto:osrm-talk-owner@openstreetmap.org" target="_blank">osrm-talk-owner@openstreetmap.org</a><br>
<br>
When replying, please edit your Subject line so it is more specific<br>
than "Re: Contents of OSRM-talk digest..."<br>
<br>
<br>
Today's Topics:<br>
<br>
   1. alternative route (Romain NKONGO)<br>
<br>
<br>
----------------------------------------------------------------------<br>
<br>
Message: 1<br>
Date: Tue, 31 Mar 2015 11:10:14 +0200<br>
From: Romain NKONGO <<a href="mailto:romain.rnk49@gmail.com" target="_blank">romain.rnk49@gmail.com</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: [OSRM-talk] alternative route<br>
Message-ID:<br>
        <CAAwSghEqK-w+MQ+kdi3r9hPKvv6tuZ0FFT1Nq9cDH3t_wLOX=<a href="mailto:g@mail.gmail.com" target="_blank">g@mail.gmail.com</a>><br>
Content-Type: text/plain; charset="utf-8"<br>
<br>
Hello everyone,<br>
<br>
I've succeeded to add a new criterion called cyclability to OSRM, which is<br>
associated with each edge in the graph. It is created in bicycle.lua file<br>
and I managed to bring it all through the processing phase and to make a<br>
mean value on each segment of the shortest path. In the JSON, I now have a<br>
9th value for each element in route instructions and a mean value in route<br>
summary.<br>
<br>
Now I intend to add a bicriteria algorithm to the routing phase (based on<br>
Label Setting). Such an algorithm would return multiple paths as results to<br>
one viaroute query. The problem is the original implementation allows 2<br>
routes at most to be returned.<br>
<br>
Has anyone tried to increase the limit of routes returned? If not, what is<br>
the condition for an alternative route and is there at least a way to force<br>
OSRM to show an alternative route?<br>
<br>
Thanks in advance for the help.<br>
Romain NKONGO.<br>
-------------- next part --------------<br>
An HTML attachment was scrubbed...<br>
URL: <<a href="http://lists.openstreetmap.org/pipermail/osrm-talk/attachments/20150331/1d449886/attachment-0001.html" target="_blank">http://lists.openstreetmap.org/pipermail/osrm-talk/attachments/20150331/1d449886/attachment-0001.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 27, Issue 12<br>
*****************************************<br>
</blockquote></div><br></div>
<br>_______________________________________________<br>
OSRM-talk mailing list<br>
<a href="mailto:OSRM-talk@openstreetmap.org">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></blockquote></div><br></div>