[OSRM-talk] OSRM-talk Digest, Vol 27, Issue 12
Romain NKONGO
romain.rnk49 at gmail.com
Sun Apr 12 11:51:48 UTC 2015
Hi Francis,
Thanks for considering my multicriteria problem on OSRM. I'm goign to
introduce myself too : I'm a final year student in Computer Engineering and
I'm about to finish my 5-year course at Polytech'Tours, in France. In our
final year, we must complete a project among several fields of computer
engineering. My project is to improve an already existing bicycle routing
platform, GeoVelo, which turns out to use OSRM.
The main goal of my project is to make the application multiriteria, by
adding one criteria and one bicriteria algorithm to OSRM. In addition to
the time criterion already present, we've decided to add a cyclability
criterion, which indicates the ability of a way to be accessed by bicycles.
The criterion is an index number from 1 to 5, 1 being hard cyclability and
5 being great, and an optimal solution would have the minimal sum of
cyclabilites of its segments.
As I said, we have succeeded to add this new criterion on the edges
structures of OSRM and add the sum of cyclabilities in the JSON response.
The next steps is to add an algorithm which would return the non-dominated
solutions regarding these 2 criteria. We really want to return all the
non-dominated solutions of a problem and not one solution that minimizes a
weighted sum, as Mohammed suggested, as it would be another kind of
monocriterion problem. In the example you considered we'd like to return
all 4 solutions.
The algorithm we'll use was implemented in C++ in a previous final year
project. It is an improved version of Label Setting algorithm, called LSAP,
with an approximation of the Pareto front before the actual routing
process. We approximate the Pareto front by setting lower and upper bounds
on each node to help eliminate dominated solutions (this is done by
Bi-Dijkstra on each criterion). A second way to approximate the Pareto
front is to create a graph of landmarks, which are the most used nodes of
the original graph, that will increase the speed of labels calculations in
routing.
I have 2 big steps to finish in my project, in the remaining month until
the end of the year :
1) Keep the CH on the time criterion only in OSRM and insert the algorithm
above in the routing part instead of the shortest_path function.
2) Take the monocriterion OSRM and make it routing on the cyclability
criterion instead of time
To run tests, I've implemented a JS script which takes multiple random
coordinates in a bounded OSM data map, pass the respective HTTP requests to
the server and get the returned response data into files.
Here is a summary of how we dealt with the issues you pointed out :
- Lua scripts : we've added a cyclability calculation function in the
already existing Lua script bicycle.lua, which check the OSM tags of ways
and return a cyclability number.
- For each edge structure, we've added a cyclability member which is of
unsigned char value.
- We kept the CH preprocessing of the graph with only time criterion, in
order to speed up the routing and reduce the number of solutions. We just
have to add the corresponding cyclability criterion to the created
shortcuts in order to take them into account in the search process with the
LSAP algorithm.
- Actually OSRM returns at most 2 solutions, the shortest path and a
potential alternative; with the bicriteria algorithm we will write the set
of non-dominated solutions to a formated result file.
- For now, we didn't implement the frontend part so the set of solutions
will not be printed on a map.
I'm still struggling with the code to complete some tasks :
- insert the sum of cyclabilities in the shortcut edges; which classes are
concerned with this?
- adjust the input of my algorithm to the input of OSRM search : my
algorithm takes 2 files in inputs (one for the directed edges with source,
target and the 2 criteria, oredered by source then target, and one for the
nodes with ID and coordinates)
- ignore restrictions completely because my algorithm doesn't take them
into account
Sorry for the long mail. I'm quite in a urge to finish my project so I'd be
really thankful for any help here.
Best regards.
Romain NKONGO.
2015-04-09 20:16 GMT+02:00 Mohammed Ayoub NEGGAZ <am_neggaz at esi.dz>:
> 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
>>
>>
>
> _______________________________________________
> 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/20150412/4318bbe1/attachment-0001.html>
More information about the OSRM-talk
mailing list