[pgrouting-users] algo which allow negative cost

[Yaron Lev]

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/b6e6d82e/attachment.html>