[pgrouting-users] algo which allow negative cost
Yaron Lev
yaron666 at gmail.com
Mon Jul 8 23:11:07 PDT 2013
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 at 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 at 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
> :)
> >>
> >> 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 <mailto: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
> >> <mailto: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
> >> <mailto: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
> >> 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
>
>
>
> --
> 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 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/20130709/3cda496d/attachment-0001.html>
More information about the Pgrouting-users
mailing list