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 <francisr...@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-requ...@openstreetmap.org> > wrote: > >> Send OSRM-talk mailing list submissions to >> osrm-t...@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-requ...@openstreetmap.org >> >> You can reach the person managing the list at >> osrm-talk-ow...@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.rn...@gmail.com> >> To: Mailing list to discuss Project OSRM <osrm-t...@openstreetmap.org> >> Subject: [OSRM-talk] alternative route >> Message-ID: >> <CAAwSghEqK-w+MQ+kdi3r9hPKvv6tuZ0FFT1Nq9cDH3t_wLOX= >> g...@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-t...@openstreetmap.org >> https://lists.openstreetmap.org/listinfo/osrm-talk >> >> >> ------------------------------ >> >> End of OSRM-talk Digest, Vol 27, Issue 12 >> ***************************************** >> > > > _______________________________________________ > OSRM-talk mailing list > osrm-t...@openstreetmap.org > https://lists.openstreetmap.org/listinfo/osrm-talk > >
_______________________________________________ OSRM-talk mailing list osrm-t...@openstreetmap.org https://lists.openstreetmap.org/listinfo/osrm-talk
