<div dir="ltr">am i mistaken thinking that djikstra with negative cost (assuming no negative circles) should work? <div>(ideally using belman ford, but i can see its not implemented yet(or never will) )<br></div><div><br></div>
<div>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?</div></div><div class="gmail_extra"><br><br><div class="gmail_quote">On Mon, Jul 8, 2013 at 8:02 PM, Elijah Meeks <span dir="ltr"><<a href="mailto:emeeks@stanford.edu" target="_blank">emeeks@stanford.edu</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">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...<br>

<span class="HOEnZb"><font color="#888888"><br>
-Elijah<br>
</font></span><div class="HOEnZb"><div class="h5"><br>
----- Original Message -----<br>
From: "Yaron Lev" <<a href="mailto:yaron666@gmail.com">yaron666@gmail.com</a>><br>
To: "pgRouting users mailing list" <<a href="mailto:pgrouting-users@lists.osgeo.org">pgrouting-users@lists.osgeo.org</a>><br>
Sent: Monday, July 8, 2013 9:49:01 AM<br>
Subject: Re: [pgrouting-users] algo which allow negative cost<br>
<br>
<br>
<br>
Stephan i appreciate your help,<br>
<br>
<br>
this is not a game problem, this is a routing problem.<br>
<br>
<br>
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.<br>
<br>
<br>
if i just +1 other edges, nothing forces the algo, to go through those poi's.<br>
<br>
<br>
imagine the following where:<br>
F - poi<br>
E - end point<br>
S- start point<br>
<br>
<br>
<br>
<br>
FxxxxE<br>
xxxxxx<br>
xxxxxx<br>
xxxxxS<br>
<br>
<br>
using +1 technique the route will not pass through F, trust me i tried :)<br>
<br>
<br>
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.<br>
<br>
<br>
thanks.<br>
<br>
<br>
<br>
<br>
<br>
On Mon, Jul 8, 2013 at 7:25 PM, Stephen Woodbridge < <a href="mailto:woodbri@swoodbridge.com">woodbri@swoodbridge.com</a> > wrote:<br>
<br>
<br>
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?<br>
<br>
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.<br>

<br>
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.<br>

<br>
-Steve<br>
<br>
<br>
<br>
On 7/8/2013 12:19 PM, Yaron Lev wrote:<br>
<br>
<br>
<br>
<br>
Hi,<br>
<br>
i am wondering if there is any algo within pgrouting 2, which will allow<br>
edges to have negative costs (without negative circles)?<br>
<br>
i was not able to find such, and in this event, is there some clever<br>
way, to achieve a similar effect?<br>
<br>
in specific, i am trying to solve a pac-man like problem.<br>
<br>
trying to find best route, given graph, where on some edges there are<br>
"fruits" to collect, collecting fruits will have a positive effect.<br>
<br>
your goal to collect as many fruits as possible, fruit can have a -1<br>
cost for example while each edge has it length as a positive cost.<br>
<br>
the outcome should be a route, where at any distance(this is flexible,<br>
as long as it achieve a similar goal) from route, the outcome route will<br>
have the best score out of all other routes.<br>
<br>
i tried using shortest path algo, with out negative costs, but i am<br>
unable to come up with a solution which will indeed provide such or<br>
similar solution. (in specfic un able to come up with costs, which will<br>
indeed "force" the route to collect those "fruits")<br>
<br>
i will appreciate any insight or direction for solving this problem.<br>
<br>
<br>
* the fruits are actually poi, such as bus stations, museums etc.<br>
* if negative edge costs are allowed, the problem is solved.<br>
<br>
thanks for your help!<br>
<br>
<br>
______________________________ _________________<br>
Pgrouting-users mailing list<br>
Pgrouting-users@lists.osgeo. org<br>
<a href="http://lists.osgeo.org/" target="_blank">http://lists.osgeo.org/</a> mailman/listinfo/pgrouting- users<br>
<br>
<br>
______________________________ _________________<br>
Pgrouting-users mailing list<br>
Pgrouting-users@lists.osgeo. org<br>
<a href="http://lists.osgeo.org/" target="_blank">http://lists.osgeo.org/</a> mailman/listinfo/pgrouting- users<br>
<br>
<br>
_______________________________________________<br>
Pgrouting-users mailing list<br>
<a href="mailto:Pgrouting-users@lists.osgeo.org">Pgrouting-users@lists.osgeo.org</a><br>
<a href="http://lists.osgeo.org/mailman/listinfo/pgrouting-users" target="_blank">http://lists.osgeo.org/mailman/listinfo/pgrouting-users</a><br>
_______________________________________________<br>
Pgrouting-users mailing list<br>
<a href="mailto:Pgrouting-users@lists.osgeo.org">Pgrouting-users@lists.osgeo.org</a><br>
<a href="http://lists.osgeo.org/mailman/listinfo/pgrouting-users" target="_blank">http://lists.osgeo.org/mailman/listinfo/pgrouting-users</a><br>
</div></div></blockquote></div><br></div>