[pgrouting-users] algo which allow negative cost

pgRouting pgrouting-users
1

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!

2

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@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-users

3

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 :slight_smile:

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@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@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-users

Pgrouting-users mailing list
Pgrouting-users@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-users

4

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@gmail.com>
To: "pgRouting users mailing list" <pgrouting-users@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 :slight_smile:

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@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@lists.osgeo. org
http://lists.osgeo.org/ mailman/listinfo/pgrouting- users

______________________________ _________________
Pgrouting-users mailing list
Pgrouting-users@lists.osgeo. org
http://lists.osgeo.org/ mailman/listinfo/pgrouting- users

_______________________________________________
Pgrouting-users mailing list
Pgrouting-users@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-users

5

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@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@gmail.com>
To: “pgRouting users mailing list” <pgrouting-users@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 :slight_smile:

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@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@lists.osgeo. org
http://lists.osgeo.org/ mailman/listinfo/pgrouting- users

Pgrouting-users mailing list
Pgrouting-users@lists.osgeo. org
http://lists.osgeo.org/ mailman/listinfo/pgrouting- users

Pgrouting-users mailing list
Pgrouting-users@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-users

Pgrouting-users mailing list
Pgrouting-users@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-users

6

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@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@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@gmail.com>
To: “pgRouting users mailing list” <pgrouting-users@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 :slight_smile:

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@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@lists.osgeo. org
http://lists.osgeo.org/ mailman/listinfo/pgrouting- users

Pgrouting-users mailing list
Pgrouting-users@lists.osgeo. org
http://lists.osgeo.org/ mailman/listinfo/pgrouting- users

Pgrouting-users mailing list
Pgrouting-users@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-users

Pgrouting-users mailing list
Pgrouting-users@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-users

7

Right, what you are describing is known as "VRP with profits". The idea is that you have some number of locations that have a profit associated to them and typically you have some other constraints like the maximum time for the tour. Then you have to optimize the selection of locations based on the maximum time and maximize profit for the tour.

This is not a simple shortest path algorithm. If you have no time constraint, then you can just use TSP with the POI's that you want to visit. Specify a start point and the list of POIs as a distance matrix and TSP will optimize the order to visit the POIs based on making it the shortest tour length. As you mention, this forces the use of all points.

Otherwise, we do not have anything like this yet. Dijkstra with a negative cost does not solve this problem.

Thanks for taking the time to explain your needs. Feel free to add a ticket for a future enhancement. Please refer to "VRP with profits" in the ticket so we know what you are looking for.

Thanks,
   -Steve

On 7/8/2013 12:49 PM, Yaron Lev wrote:

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
xxxxxS

using +1 technique the route will not pass through F, trust me i tried :slight_smile:

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@swoodbridge.com <mailto:woodbri@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@lists.osgeo.__org
        <mailto:Pgrouting-users@lists.osgeo.org>
        http://lists.osgeo.org/__mailman/listinfo/pgrouting-__users
        <http://lists.osgeo.org/mailman/listinfo/pgrouting-users&gt;

    _________________________________________________
    Pgrouting-users mailing list
    Pgrouting-users@lists.osgeo.__org
    <mailto:Pgrouting-users@lists.osgeo.org>
    http://lists.osgeo.org/__mailman/listinfo/pgrouting-__users
    <http://lists.osgeo.org/mailman/listinfo/pgrouting-users&gt;

_______________________________________________
Pgrouting-users mailing list
Pgrouting-users@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-users

8

Yaron,

I had to solve a similar problem for one of our iPhone apps (Sanpo).
We had a set of POIs, each with a different "interest" value, and we
had to create a route that went through the most interesting POIs
within a specified time.

In our case, start and end point were the same (the user comes back to
the starting point after the stroll).
Since TSP was not suitable and you can not set negative cost values in
Dijkstra, I ended up solving it this way:

1. Pick up a set of POIs from your POIs array (for example, 5 POIs among 10)
2. From the starting point, find the closest POI (not using the length
of the route to that point, but straight line distance). Since we use
straight line distances, calculating this distance takes nothing.
3. From the last POI, find the next closest POI we have still not
visited. If no POIs left, find the distance from that POI to the end
point.
4. In a urban context, real walking distances are in the order of
(straight line distance) x 1.3, so estimate the walking distance of
your "tour" using this formula. If it exceeds the required time, go to
1 and start over again.
5. Once you have the set of POIs you want to include in your route,
connect each of them using Dijkstra (you will need to call Dijkstra
several times and join the route between each pair of POIs manually)

Since you are working with estimates using the formula in 4, it may
not work if you need very precise walking time constraints. But if you
intend to use it to create walking routes for tourism, I doubt this
will be a problem. After all, you don't know how long people are going
to stay at each POI.

Tao

2013/7/9 Stephen Woodbridge <woodbri@swoodbridge.com>:

Right, what you are describing is known as "VRP with profits". The idea is
that you have some number of locations that have a profit associated to them
and typically you have some other constraints like the maximum time for the
tour. Then you have to optimize the selection of locations based on the
maximum time and maximize profit for the tour.

This is not a simple shortest path algorithm. If you have no time
constraint, then you can just use TSP with the POI's that you want to visit.
Specify a start point and the list of POIs as a distance matrix and TSP will
optimize the order to visit the POIs based on making it the shortest tour
length. As you mention, this forces the use of all points.

Otherwise, we do not have anything like this yet. Dijkstra with a negative
cost does not solve this problem.

Thanks for taking the time to explain your needs. Feel free to add a ticket
for a future enhancement. Please refer to "VRP with profits" in the ticket
so we know what you are looking for.

Thanks,
  -Steve

On 7/8/2013 12:49 PM, Yaron Lev wrote:

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 :slight_smile:

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@swoodbridge.com <mailto:woodbri@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@lists.osgeo.__org
        <mailto:Pgrouting-users@lists.osgeo.org>
        http://lists.osgeo.org/__mailman/listinfo/pgrouting-__users
        <http://lists.osgeo.org/mailman/listinfo/pgrouting-users&gt;

    _________________________________________________
    Pgrouting-users mailing list
    Pgrouting-users@lists.osgeo.__org
    <mailto:Pgrouting-users@lists.osgeo.org>
    http://lists.osgeo.org/__mailman/listinfo/pgrouting-__users

    <http://lists.osgeo.org/mailman/listinfo/pgrouting-users&gt;

_______________________________________________
Pgrouting-users mailing list
Pgrouting-users@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-users

_______________________________________________
Pgrouting-users mailing list
Pgrouting-users@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-users

--
Tao Romera Martínez

---------------------------------------------------------
Tel: 080-6805-0945
Address: Koganei-shi, Tokyo, Japan

Look for me on Facebook and LinkedIn
---------------------------------------------------------

9

Stephan, thanks again, the “VRP” reference was very illuminating.

Tao, thanks for sharing your solution, indeed i am using a similar approach atm, (was the only feasible solution i was able to think of).

the key difference, is how i pick the poi (i am still looking/thinking about better solutions),

for example in the “poi selection - naive approch” (picking the closest, repeat and rinse)

where S- start point, P - poi, end point - dont really have an end point (assuming 5 points)

BBxxxxxxxxxxxxxxA

BBxxxxxxxxxxxxxxx
BBxxxxxxxxxxxxxxx
BxxxxxxxxxxxxxxxA
Bxxxxxxxxxxxxxxxx
xxxxxxxxxxAxxxxxx
xxxxxxxxxxxxxxxxxx
xxxxxSxxxxxxxxxxxx

the algo will choose the right side(A), even though B side is more profitable (depends on how u calculate, but i reken the point is clear)
because it will always start from the closest even if its a pitfall

to combat this initially i will try to cluster the poi’s,

C - is array of poi, which holds the number of poi associated with this point.
Cx has threshold - which increase with number of poi it contains
Cx has a score - each poi added

  1. arrange them by distance from one another (not very efficient)
  2. then start clustering them - loop
    2.1 pick closest, Cx=pn (x=1,n=1)
    2.2 if dist(Cx,pn)<C (threshold then) add it to Cx,
    2.3 Cx(lat),Cx(lon) is the center of mass of P1…Pn, where n is the number of points on Cx
    2.4 increase C(threshold) → so that Cx, with many poi’s would be able to “add points/poi” from a greater distance, thus giving advantage to Cx with many points.
    2.5 increase C(score) - 1/dist (Cx,pn),
    2.5 else (from 2.2) continue to the next uncluttered P (n+1)(x+1)
  3. calc final score for C - Cx(final score) = Cscore*dist (Cx,S)
  4. arrange C by score, choose desired amount of C.
  5. flat C into D array (i.e putting it back to array of points)
  6. TSP on D
  7. connect D with shortest path

i am still not very happy with this, i would still appreciate ideas on how to improve this. (especially because its inefficient)

thanks everyone for your help!

···

On Tue, Jul 9, 2013 at 5:06 AM, Tao Romera Martinez <taoromera@gmail.com> wrote:

Yaron,

I had to solve a similar problem for one of our iPhone apps (Sanpo).
We had a set of POIs, each with a different “interest” value, and we
had to create a route that went through the most interesting POIs
within a specified time.

In our case, start and end point were the same (the user comes back to
the starting point after the stroll).
Since TSP was not suitable and you can not set negative cost values in
Dijkstra, I ended up solving it this way:

  1. Pick up a set of POIs from your POIs array (for example, 5 POIs among 10)
  2. From the starting point, find the closest POI (not using the length
    of the route to that point, but straight line distance). Since we use
    straight line distances, calculating this distance takes nothing.
  3. From the last POI, find the next closest POI we have still not
    visited. If no POIs left, find the distance from that POI to the end
    point.
  4. In a urban context, real walking distances are in the order of
    (straight line distance) x 1.3, so estimate the walking distance of
    your “tour” using this formula. If it exceeds the required time, go to
    1 and start over again.
  5. Once you have the set of POIs you want to include in your route,
    connect each of them using Dijkstra (you will need to call Dijkstra
    several times and join the route between each pair of POIs manually)

Since you are working with estimates using the formula in 4, it may
not work if you need very precise walking time constraints. But if you
intend to use it to create walking routes for tourism, I doubt this
will be a problem. After all, you don’t know how long people are going
to stay at each POI.

Tao

2013/7/9 Stephen Woodbridge <woodbri@swoodbridge.com>:

Right, what you are describing is known as “VRP with profits”. The idea is
that you have some number of locations that have a profit associated to them
and typically you have some other constraints like the maximum time for the
tour. Then you have to optimize the selection of locations based on the
maximum time and maximize profit for the tour.

This is not a simple shortest path algorithm. If you have no time
constraint, then you can just use TSP with the POI’s that you want to visit.
Specify a start point and the list of POIs as a distance matrix and TSP will
optimize the order to visit the POIs based on making it the shortest tour
length. As you mention, this forces the use of all points.

Otherwise, we do not have anything like this yet. Dijkstra with a negative
cost does not solve this problem.

Thanks for taking the time to explain your needs. Feel free to add a ticket
for a future enhancement. Please refer to “VRP with profits” in the ticket
so we know what you are looking for.

Thanks,
-Steve

On 7/8/2013 12:49 PM, Yaron Lev wrote:

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 :slight_smile:

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@swoodbridge.com mailto:[woodbri@swoodbridge.com](mailto:woodbri@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@lists.osgeo.__org
mailto:[Pgrouting-users@lists.osgeo.org](mailto:Pgrouting-users@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@lists.osgeo.__org
mailto:[Pgrouting-users@lists.osgeo.org](mailto:Pgrouting-users@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@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-users

Pgrouting-users mailing list
Pgrouting-users@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-users

–
Tao Romera Martínez

Tel: 080-6805-0945
Address: Koganei-shi, Tokyo, Japan

Look for me on Facebook and LinkedIn

Pgrouting-users mailing list
Pgrouting-users@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-users

10

Well, I guess you will have to find a way of classifying the POIs, to
include those that are more relevant preferentially in your route.
In our case, we were using Foursquare spots as POIs, and the number of
checkins as the "relevance value". Then we picked a set of the most
popular and run the algorithm I described in my previous message.

Good luck with your case!

Tao

2013/7/9 Yaron Lev <yaron666@gmail.com>:

Stephan, thanks again, the "VRP" reference was very illuminating.

Tao, thanks for sharing your solution, indeed i am using a similar approach
atm, (was the only feasible solution i was able to think of).

the key difference, is how i pick the poi (i am still looking/thinking about
better solutions),

for example in the "poi selection - naive approch" (picking the closest,
repeat and rinse)

where S- start point, P - poi, end point - dont really have an end point
(assuming 5 points)

BBxxxxxxxxxxxxxxA
BBxxxxxxxxxxxxxxx
BBxxxxxxxxxxxxxxx
BxxxxxxxxxxxxxxxA
Bxxxxxxxxxxxxxxxx
xxxxxxxxxxAxxxxxx
xxxxxxxxxxxxxxxxxx
xxxxxSxxxxxxxxxxxx

the algo will choose the right side(A), even though B side is more
profitable (depends on how u calculate, but i reken the point is clear)
because it will always start from the closest even if its a pitfall

to combat this initially i will try to cluster the poi's,

C - is array of poi, which holds the number of poi associated with this
point.
Cx has threshold - which increase with number of poi it contains
Cx has a score - each poi added

1. arrange them by distance from one another (not very efficient)
2. then start clustering them - loop
2.1 pick closest, Cx=pn (x=1,n=1)
2.2 if dist(Cx,pn)<C (threshold then) add it to Cx,
2.3 Cx(lat),Cx(lon) is the center of mass of P1....Pn, where n is the number
of points on Cx
2.4 increase C(threshold) -> so that Cx, with many poi's would be able to
"add points/poi" from a greater distance, thus giving advantage to Cx with
many points.
2.5 increase C(score) - 1/dist (Cx,pn),
2.5 else (from 2.2) continue to the next uncluttered P (n+1)(x+1)
3. calc final score for C - Cx(final score) = Cscore*dist (Cx,S)
4. arrange C by score, choose desired amount of C.
5. flat C into D array (i.e putting it back to array of points)
7. TSP on D
8. connect D with shortest path

i am still not very happy with this, i would still appreciate ideas on how
to improve this. (especially because its inefficient)

thanks everyone for your help!

On Tue, Jul 9, 2013 at 5:06 AM, Tao Romera Martinez <taoromera@gmail.com>
wrote:

Yaron,

I had to solve a similar problem for one of our iPhone apps (Sanpo).
We had a set of POIs, each with a different "interest" value, and we
had to create a route that went through the most interesting POIs
within a specified time.

In our case, start and end point were the same (the user comes back to
the starting point after the stroll).
Since TSP was not suitable and you can not set negative cost values in
Dijkstra, I ended up solving it this way:

1. Pick up a set of POIs from your POIs array (for example, 5 POIs among
10)
2. From the starting point, find the closest POI (not using the length
of the route to that point, but straight line distance). Since we use
straight line distances, calculating this distance takes nothing.
3. From the last POI, find the next closest POI we have still not
visited. If no POIs left, find the distance from that POI to the end
point.
4. In a urban context, real walking distances are in the order of
(straight line distance) x 1.3, so estimate the walking distance of
your "tour" using this formula. If it exceeds the required time, go to
1 and start over again.
5. Once you have the set of POIs you want to include in your route,
connect each of them using Dijkstra (you will need to call Dijkstra
several times and join the route between each pair of POIs manually)

Since you are working with estimates using the formula in 4, it may
not work if you need very precise walking time constraints. But if you
intend to use it to create walking routes for tourism, I doubt this
will be a problem. After all, you don't know how long people are going
to stay at each POI.

Tao

2013/7/9 Stephen Woodbridge <woodbri@swoodbridge.com>:
> Right, what you are describing is known as "VRP with profits". The idea
> is
> that you have some number of locations that have a profit associated to
> them
> and typically you have some other constraints like the maximum time for
> the
> tour. Then you have to optimize the selection of locations based on the
> maximum time and maximize profit for the tour.
>
> This is not a simple shortest path algorithm. If you have no time
> constraint, then you can just use TSP with the POI's that you want to
> visit.
> Specify a start point and the list of POIs as a distance matrix and TSP
> will
> optimize the order to visit the POIs based on making it the shortest
> tour
> length. As you mention, this forces the use of all points.
>
> Otherwise, we do not have anything like this yet. Dijkstra with a
> negative
> cost does not solve this problem.
>
> Thanks for taking the time to explain your needs. Feel free to add a
> ticket
> for a future enhancement. Please refer to "VRP with profits" in the
> ticket
> so we know what you are looking for.
>
> Thanks,
> -Steve
>
>
> On 7/8/2013 12:49 PM, Yaron Lev wrote:
>>
>> 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
>> :slight_smile:
>>
>> 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@swoodbridge.com <mailto:woodbri@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@lists.osgeo.__org
>> <mailto:Pgrouting-users@lists.osgeo.org>
>> http://lists.osgeo.org/__mailman/listinfo/pgrouting-__users
>> <http://lists.osgeo.org/mailman/listinfo/pgrouting-users&gt;
>>
>>
>> _________________________________________________
>> Pgrouting-users mailing list
>> Pgrouting-users@lists.osgeo.__org
>> <mailto:Pgrouting-users@lists.osgeo.org>
>> http://lists.osgeo.org/__mailman/listinfo/pgrouting-__users
>>
>> <http://lists.osgeo.org/mailman/listinfo/pgrouting-users&gt;
>>
>>
>>
>>
>> _______________________________________________
>> Pgrouting-users mailing list
>> Pgrouting-users@lists.osgeo.org
>> http://lists.osgeo.org/mailman/listinfo/pgrouting-users
>>
>
> _______________________________________________
> Pgrouting-users mailing list
> Pgrouting-users@lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/pgrouting-users

--
Tao Romera Martínez

---------------------------------------------------------
Tel: 080-6805-0945
Address: Koganei-shi, Tokyo, Japan

Look for me on Facebook and LinkedIn
---------------------------------------------------------
_______________________________________________
Pgrouting-users mailing list
Pgrouting-users@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-users

_______________________________________________
Pgrouting-users mailing list
Pgrouting-users@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-users

--
Tao Romera Martínez

---------------------------------------------------------
Tel: 080-6805-0945
Address: Koganei-shi, Tokyo, Japan

Look for me on Facebook and LinkedIn
---------------------------------------------------------

11

On 09/07/13 08:36, Tao Romera Martinez wrote:
If your thinking of using the TSP as solution, just remember that as far as it concerned the route A-> B is the same as the cost of the journey B->A.

Dave.

Well, I guess you will have to find a way of classifying the POIs, to
include those that are more relevant preferentially in your route.
In our case, we were using Foursquare spots as POIs, and the number of
checkins as the "relevance value". Then we picked a set of the most
popular and run the algorithm I described in my previous message.

Good luck with your case!

Tao

2013/7/9 Yaron Lev <yaron666@gmail.com>:

Stephan, thanks again, the "VRP" reference was very illuminating.

Tao, thanks for sharing your solution, indeed i am using a similar approach
atm, (was the only feasible solution i was able to think of).

the key difference, is how i pick the poi (i am still looking/thinking about
better solutions),

for example in the "poi selection - naive approch" (picking the closest,
repeat and rinse)

where S- start point, P - poi, end point - dont really have an end point
(assuming 5 points)

BBxxxxxxxxxxxxxxA
BBxxxxxxxxxxxxxxx
BxxxxxxxxxxxxxxxA
Bxxxxxxxxxxxxxxxx
xxxxxxxxxxAxxxxxx
xxxxxxxxxxxxxxxxxx
xxxxxSxxxxxxxxxxxx

the algo will choose the right side(A), even though B side is more
profitable (depends on how u calculate, but i reken the point is clear)
because it will always start from the closest even if its a pitfall

to combat this initially i will try to cluster the poi's,

C - is array of poi, which holds the number of poi associated with this
point.
Cx has threshold - which increase with number of poi it contains
Cx has a score - each poi added

1. arrange them by distance from one another (not very efficient)
2. then start clustering them - loop
2.1 pick closest, Cx=pn (x=1,n=1)
2.2 if dist(Cx,pn)<C (threshold then) add it to Cx,
2.3 Cx(lat),Cx(lon) is the center of mass of P1....Pn, where n is the number
of points on Cx
2.4 increase C(threshold) -> so that Cx, with many poi's would be able to
"add points/poi" from a greater distance, thus giving advantage to Cx with
many points.
2.5 increase C(score) - 1/dist (Cx,pn),
2.5 else (from 2.2) continue to the next uncluttered P (n+1)(x+1)
3. calc final score for C - Cx(final score) = Cscore*dist (Cx,S)
4. arrange C by score, choose desired amount of C.
5. flat C into D array (i.e putting it back to array of points)
7. TSP on D
8. connect D with shortest path

i am still not very happy with this, i would still appreciate ideas on how
to improve this. (especially because its inefficient)

thanks everyone for your help!

On Tue, Jul 9, 2013 at 5:06 AM, Tao Romera Martinez <taoromera@gmail.com>
wrote:

Yaron,

I had to solve a similar problem for one of our iPhone apps (Sanpo).
We had a set of POIs, each with a different "interest" value, and we
had to create a route that went through the most interesting POIs
within a specified time.

In our case, start and end point were the same (the user comes back to
the starting point after the stroll).
Since TSP was not suitable and you can not set negative cost values in
Dijkstra, I ended up solving it this way:

1. Pick up a set of POIs from your POIs array (for example, 5 POIs among
10)
2. From the starting point, find the closest POI (not using the length
of the route to that point, but straight line distance). Since we use
straight line distances, calculating this distance takes nothing.
3. From the last POI, find the next closest POI we have still not
visited. If no POIs left, find the distance from that POI to the end
point.
4. In a urban context, real walking distances are in the order of
(straight line distance) x 1.3, so estimate the walking distance of
your "tour" using this formula. If it exceeds the required time, go to
1 and start over again.
5. Once you have the set of POIs you want to include in your route,
connect each of them using Dijkstra (you will need to call Dijkstra
several times and join the route between each pair of POIs manually)

Since you are working with estimates using the formula in 4, it may
not work if you need very precise walking time constraints. But if you
intend to use it to create walking routes for tourism, I doubt this
will be a problem. After all, you don't know how long people are going
to stay at each POI.

Tao

2013/7/9 Stephen Woodbridge <woodbri@swoodbridge.com>:

Right, what you are describing is known as "VRP with profits". The idea
is
that you have some number of locations that have a profit associated to
them
and typically you have some other constraints like the maximum time for
the
tour. Then you have to optimize the selection of locations based on the
maximum time and maximize profit for the tour.

This is not a simple shortest path algorithm. If you have no time
constraint, then you can just use TSP with the POI's that you want to
visit.
Specify a start point and the list of POIs as a distance matrix and TSP
will
optimize the order to visit the POIs based on making it the shortest
tour
length. As you mention, this forces the use of all points.

Otherwise, we do not have anything like this yet. Dijkstra with a
negative
cost does not solve this problem.

Thanks for taking the time to explain your needs. Feel free to add a
ticket
for a future enhancement. Please refer to "VRP with profits" in the
ticket
so we know what you are looking for.

Thanks,
   -Steve

On 7/8/2013 12:49 PM, Yaron Lev wrote:

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
xxxxxS

using +1 technique the route will not pass through F, trust me i tried
:slight_smile:

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@swoodbridge.com <mailto:woodbri@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@lists.osgeo.__org
         <mailto:Pgrouting-users@lists.osgeo.org>
         http://lists.osgeo.org/__mailman/listinfo/pgrouting-__users
         <http://lists.osgeo.org/mailman/listinfo/pgrouting-users&gt;

     _________________________________________________
     Pgrouting-users mailing list
     Pgrouting-users@lists.osgeo.__org
     <mailto:Pgrouting-users@lists.osgeo.org>
     http://lists.osgeo.org/__mailman/listinfo/pgrouting-__users

     <http://lists.osgeo.org/mailman/listinfo/pgrouting-users&gt;

_______________________________________________
Pgrouting-users mailing list
Pgrouting-users@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-users

_______________________________________________
Pgrouting-users mailing list
Pgrouting-users@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-users

--
Tao Romera Martínez

---------------------------------------------------------
Tel: 080-6805-0945
Address: Koganei-shi, Tokyo, Japan

Look for me on Facebook and LinkedIn
---------------------------------------------------------
_______________________________________________
Pgrouting-users mailing list
Pgrouting-users@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-users

_______________________________________________
Pgrouting-users mailing list
Pgrouting-users@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-users