[pgrouting-users] algo which allow negative cost
Tao Romera Martinez
taoromera at gmail.com
Mon Jul 8 19:06:13 PDT 2013
Yaron,
I had to solve a similar problem for one of our iPhone apps (Sanpo).
We had a set of POIs, each with a different "interest" value, and we
had to create a route that went through the most interesting POIs
within a specified time.
In our case, start and end point were the same (the user comes back to
the starting point after the stroll).
Since TSP was not suitable and you can not set negative cost values in
Dijkstra, I ended up solving it this way:
1. Pick up a set of POIs from your POIs array (for example, 5 POIs among 10)
2. From the starting point, find the closest POI (not using the length
of the route to that point, but straight line distance). Since we use
straight line distances, calculating this distance takes nothing.
3. From the last POI, find the next closest POI we have still not
visited. If no POIs left, find the distance from that POI to the end
point.
4. In a urban context, real walking distances are in the order of
(straight line distance) x 1.3, so estimate the walking distance of
your "tour" using this formula. If it exceeds the required time, go to
1 and start over again.
5. Once you have the set of POIs you want to include in your route,
connect each of them using Dijkstra (you will need to call Dijkstra
several times and join the route between each pair of POIs manually)
Since you are working with estimates using the formula in 4, it may
not work if you need very precise walking time constraints. But if you
intend to use it to create walking routes for tourism, I doubt this
will be a problem. After all, you don't know how long people are going
to stay at each POI.
Tao
2013/7/9 Stephen Woodbridge <woodbri at swoodbridge.com>:
> Right, what you are describing is known as "VRP with profits". The idea is
> that you have some number of locations that have a profit associated to them
> and typically you have some other constraints like the maximum time for the
> tour. Then you have to optimize the selection of locations based on the
> maximum time and maximize profit for the tour.
>
> This is not a simple shortest path algorithm. If you have no time
> constraint, then you can just use TSP with the POI's that you want to visit.
> Specify a start point and the list of POIs as a distance matrix and TSP will
> optimize the order to visit the POIs based on making it the shortest tour
> length. As you mention, this forces the use of all points.
>
> Otherwise, we do not have anything like this yet. Dijkstra with a negative
> cost does not solve this problem.
>
> Thanks for taking the time to explain your needs. Feel free to add a ticket
> for a future enhancement. Please refer to "VRP with profits" in the ticket
> so we know what you are looking for.
>
> Thanks,
> -Steve
>
>
> On 7/8/2013 12:49 PM, Yaron Lev wrote:
>>
>> Stephan i appreciate your help,
>>
>> this is not a game problem, this is a routing problem.
>>
>> i have some poi, such museums etc. i want to offer a route to my users
>> which will be the shortest, and will pass through as many poi's as
>> possible.
>>
>> if i just +1 other edges, nothing forces the algo, to go through those
>> poi's.
>>
>> imagine the following where:
>> F - poi
>> E - end point
>> S- start point
>>
>>
>> FxxxxE
>> xxxxxx
>> xxxxxx
>> xxxxxS
>>
>> using +1 technique the route will not pass through F, trust me i tried :)
>>
>> using the TSP approach, which i also tried, it forces the user go
>> through all of the poi, regardless of there distance, which might be
>> counter productive.
>>
>> thanks.
>>
>>
>>
>> On Mon, Jul 8, 2013 at 7:25 PM, Stephen Woodbridge
>> <woodbri at swoodbridge.com <mailto:woodbri at swoodbridge.com>> wrote:
>>
>> Why not just add 1.0 to all you edge costs so you minimum edge cost
>> is 0 for fruits and 1+ for all other edges?
>>
>> I assume that a -1 cost just means that the edge is desirable to
>> capture but is your goal is to collect some number of POI in an
>> area, than it might be better to get the location of all the POI and
>> the cost to get from each POI to each of the other POI then you can
>> build a distance matrix to compute TSP solution which is the minimum
>> cost to hit every POI.
>>
>> It is not clear to be what you want to achieve here. We do not have
>> algorithms targeted at game theory or solving game like problems. So
>> you have to re-map the problem into point to point shortest distance
>> and multiple point order optimization problems.
>>
>> -Steve
>>
>>
>> On 7/8/2013 12:19 PM, Yaron Lev wrote:
>>
>> Hi,
>>
>> i am wondering if there is any algo within pgrouting 2, which
>> will allow
>> edges to have negative costs (without negative circles)?
>>
>> i was not able to find such, and in this event, is there some
>> clever
>> way, to achieve a similar effect?
>>
>> in specific, i am trying to solve a pac-man like problem.
>>
>> trying to find best route, given graph, where on some edges
>> there are
>> "fruits" to collect, collecting fruits will have a positive
>> effect.
>>
>> your goal to collect as many fruits as possible, fruit can have a
>> -1
>> cost for example while each edge has it length as a positive cost.
>>
>> the outcome should be a route, where at any distance(this is
>> flexible,
>> as long as it achieve a similar goal) from route, the outcome
>> route will
>> have the best score out of all other routes.
>>
>> i tried using shortest path algo, with out negative costs, but i
>> am
>> unable to come up with a solution which will indeed provide such
>> or
>> similar solution. (in specfic un able to come up with costs,
>> which will
>> indeed "force" the route to collect those "fruits")
>>
>> i will appreciate any insight or direction for solving this
>> problem.
>>
>>
>> * the fruits are actually poi, such as bus stations, museums etc.
>> * if negative edge costs are allowed, the problem is solved.
>>
>> thanks for your help!
>>
>>
>> _________________________________________________
>> Pgrouting-users mailing list
>> Pgrouting-users at lists.osgeo.__org
>> <mailto:Pgrouting-users at lists.osgeo.org>
>> http://lists.osgeo.org/__mailman/listinfo/pgrouting-__users
>> <http://lists.osgeo.org/mailman/listinfo/pgrouting-users>
>>
>>
>> _________________________________________________
>> Pgrouting-users mailing list
>> Pgrouting-users at lists.osgeo.__org
>> <mailto:Pgrouting-users at lists.osgeo.org>
>> http://lists.osgeo.org/__mailman/listinfo/pgrouting-__users
>>
>> <http://lists.osgeo.org/mailman/listinfo/pgrouting-users>
>>
>>
>>
>>
>> _______________________________________________
>> Pgrouting-users mailing list
>> Pgrouting-users at lists.osgeo.org
>> http://lists.osgeo.org/mailman/listinfo/pgrouting-users
>>
>
> _______________________________________________
> Pgrouting-users mailing list
> Pgrouting-users at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/pgrouting-users
--
Tao Romera Martínez
---------------------------------------------------------
Tel: 080-6805-0945
Address: Koganei-shi, Tokyo, Japan
Look for me on Facebook and LinkedIn
---------------------------------------------------------
More information about the Pgrouting-users
mailing list