[pgrouting-users] algo which allow negative cost

[Yaron Lev]

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 <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 <Pgrouting-users at lists.osgeo.org>
> http://lists.osgeo.org/**mailman/listinfo/pgrouting-**users<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/9eb3e042/attachment-0001.html>