[pgrouting-users] algo which allow negative cost
yaron666 at gmail.com
Mon Jul 8 09:49:01 PDT 2013
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
imagine the following where:
F - poi
E - end point
S- start point
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
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.
> On 7/8/2013 12:19 PM, Yaron Lev wrote:
>> 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>
> Pgrouting-users mailing list
> Pgrouting-users at lists.osgeo.**org <Pgrouting-users at lists.osgeo.org>
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Pgrouting-users