[pgrouting-users] algo which allow negative cost

Dave Potts dave.potts at pinan.co.uk
Tue Jul 9 04:50:00 PDT 2013 

On 09/07/13 08:36, Tao Romera Martinez wrote:
If your thinking of using the TSP as solution, just remember that as far 
as it concerned the route A-> B is the same as the cost of the journey B->A.

Dave.
> Well, I guess you will have to find a way of classifying the POIs, to
> include those that are more relevant preferentially in your route.
> In our case, we were using Foursquare spots as POIs, and the number of
> checkins as the "relevance value". Then we picked a set of the most
> popular and run the algorithm I described in my previous message.
>
> Good luck with your case!
>
> Tao
>
> 2013/7/9 Yaron Lev <yaron666 at gmail.com>:
>> Stephan,  thanks again, the "VRP"  reference was very illuminating.
>>
>> Tao, thanks for sharing your solution, indeed i am using a similar approach
>> atm, (was the only feasible solution i was able to think of).
>>
>> the key difference, is how i pick the poi (i am still looking/thinking about
>> better solutions),
>>
>> for example in the "poi selection - naive approch" (picking the closest,
>> repeat and rinse)
>>
>> where S- start point, P - poi, end point - dont really have an end point
>> (assuming 5 points)
>>
>> BBxxxxxxxxxxxxxxA
>> BBxxxxxxxxxxxxxxx
>> BBxxxxxxxxxxxxxxx
>> BxxxxxxxxxxxxxxxA
>> Bxxxxxxxxxxxxxxxx
>> xxxxxxxxxxAxxxxxx
>> xxxxxxxxxxxxxxxxxx
>> xxxxxSxxxxxxxxxxxx
>>
>> the algo will choose the right side(A), even though B side is more
>> profitable (depends on how u calculate, but i reken the point is clear)
>> because it will always start from the closest even if its a pitfall
>>
>> to combat this initially i will try to cluster the poi's,
>>
>> C - is array of poi, which holds the number of poi associated with this
>> point.
>> Cx has threshold - which increase with number of poi it contains
>> Cx has a score - each poi added
>>
>> 1. arrange them by distance from one another (not very efficient)
>> 2. then start clustering them - loop
>> 2.1 pick closest, Cx=pn (x=1,n=1)
>> 2.2 if dist(Cx,pn)<C (threshold then) add it to Cx,
>> 2.3 Cx(lat),Cx(lon) is the center of mass of P1....Pn, where n is the number
>> of points on Cx
>> 2.4 increase C(threshold) -> so that Cx, with many poi's would be able to
>> "add points/poi" from a greater distance, thus giving advantage to Cx with
>> many points.
>> 2.5 increase C(score) - 1/dist (Cx,pn),
>> 2.5 else (from 2.2) continue to the next uncluttered P (n+1)(x+1)
>> 3. calc final score for C - Cx(final score) = Cscore*dist (Cx,S)
>> 4. arrange C by score, choose desired amount of C.
>> 5. flat C into D array (i.e putting it back to array of points)
>> 7. TSP on D
>> 8. connect D with shortest path
>>
>> i am still not very happy with this, i would still appreciate ideas on how
>> to improve this. (especially because its inefficient)
>>
>>
>> thanks everyone for your help!
>>
>>
>>
>>
>> On Tue, Jul 9, 2013 at 5:06 AM, Tao Romera Martinez <taoromera at gmail.com>
>> wrote:
>>> 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
>>> ---------------------------------------------------------
>>> _______________________________________________
>>> 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
>>
>
>

More information about the Pgrouting-users mailing list