[pgrouting-users] algo which allow negative cost

[Yaron Lev]

yes i mistaken about the dijkstra's feel free to ignore the last msg...
sorry..


On Mon, Jul 8, 2013 at 8:21 PM, Yaron Lev <yaron666 at gmail.com> wrote:

> am i mistaken thinking that djikstra with negative cost (assuming no
> negative circles) should work?
> (ideally using belman ford, but i can see its not implemented yet(or never
> will) )
>
> if djikstra should work, im assuming it will not be very difficult to add
> that functionality even with my poor c knowledge, am i correct?
>
>
> On Mon, Jul 8, 2013 at 8:02 PM, Elijah Meeks <emeeks at stanford.edu> wrote:
>
>> TSP with a minimum number of nodes to visit or a maximum cost for the
>> entire trip could be achieved by cycling up through the array of sites to
>> visit, but it takes a while to process, so it's probably not best for
>> real-time. I wonder if there's a one-to-many like variation of TSP that
>> keeps the graph but cycles through permutations which would be more
>> efficient...
>>
>> -Elijah
>>
>> ----- Original Message -----
>> From: "Yaron Lev" <yaron666 at gmail.com>
>> To: "pgRouting users mailing list" <pgrouting-users at lists.osgeo.org>
>> Sent: Monday, July 8, 2013 9:49:01 AM
>> Subject: Re: [pgrouting-users] algo which allow negative cost
>>
>>
>>
>> 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 > 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
>> 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
>> _______________________________________________
>> Pgrouting-users mailing list
>> Pgrouting-users at lists.osgeo.org
>> http://lists.osgeo.org/mailman/listinfo/pgrouting-users
>>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/pgrouting-users/attachments/20130708/279746e8/attachment-0001.html>