<div dir="ltr">Stephan, thanks again, the "VRP" reference was very illuminating.<div><br></div><div style>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).</div>
<div style><br></div><div style>the key difference, is how i pick the poi (i am still looking/thinking about better solutions),</div><div style><br></div><div style>for example in the "poi selection - naive approch" (picking the closest, repeat and rinse)</div>
<div style><br></div><div style>where S- start point, P - poi, end point - dont really have an end point (assuming 5 points)</div><div style><br></div><div style>BBxxxxxxxxxxxxxxA<br></div><div style>BBxxxxxxxxxxxxxxx</div>
<div style>BBxxxxxxxxxxxxxxx</div><div style>BxxxxxxxxxxxxxxxA</div><div style>Bxxxxxxxxxxxxxxxx</div><div style>xxxxxxxxxxAxxxxxx</div><div style>xxxxxxxxxxxxxxxxxx</div><div style>xxxxxSxxxxxxxxxxxx</div><div style><br>
</div><div style>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) </div><div style>because it will always start from the closest even if its a pitfall</div>
<div style><br></div><div style>to combat this initially i will try to cluster the poi's,</div><div style><br></div><div style>C - is array of poi, which holds the number of poi associated with this point.</div><div style>
Cx has threshold - which increase with number of poi it contains</div><div style>Cx has a score - each poi added</div><div style><br></div><div style>1. arrange them by distance from one another (not very efficient)</div>
<div style>2. then start clustering them - loop</div><div style>2.1 pick closest, Cx=pn (x=1,n=1)</div><div style>2.2 if dist(Cx,pn)<C (threshold then) add it to Cx, </div><div style>2.3 Cx(lat),Cx(lon) is the center of mass of P1....Pn, where n is the number of points on Cx</div>
<div style>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.</div><div style>2.5 increase C(score) - 1/dist (Cx,pn),</div>
<div style>2.5 else (from 2.2) continue to the next uncluttered P (n+1)(x+1)</div><div style>3. calc final score for C - Cx(final score) = Cscore*dist (Cx,S)</div><div style>4. arrange C by score, choose desired amount of C.</div>
<div style>5. flat C into D array (i.e putting it back to array of points)</div><div style>7. TSP on D</div><div style>8. connect D with shortest path</div><div style><br></div><div style>i am still not very happy with this, i would still appreciate ideas on how to improve this. (especially because its inefficient)</div>
<div style><br></div><div style><br></div><div style>thanks everyone for your help!</div><div style><br></div><div style><br></div></div><div class="gmail_extra"><br><br><div class="gmail_quote">On Tue, Jul 9, 2013 at 5:06 AM, Tao Romera Martinez <span dir="ltr"><<a href="mailto:taoromera@gmail.com" target="_blank">taoromera@gmail.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Yaron,<br>
<br>
I had to solve a similar problem for one of our iPhone apps (Sanpo).<br>
We had a set of POIs, each with a different "interest" value, and we<br>
had to create a route that went through the most interesting POIs<br>
within a specified time.<br>
<br>
In our case, start and end point were the same (the user comes back to<br>
the starting point after the stroll).<br>
Since TSP was not suitable and you can not set negative cost values in<br>
Dijkstra, I ended up solving it this way:<br>
<br>
1. Pick up a set of POIs from your POIs array (for example, 5 POIs among 10)<br>
2. From the starting point, find the closest POI (not using the length<br>
of the route to that point, but straight line distance). Since we use<br>
straight line distances, calculating this distance takes nothing.<br>
3. From the last POI, find the next closest POI we have still not<br>
visited. If no POIs left, find the distance from that POI to the end<br>
point.<br>
4. In a urban context, real walking distances are in the order of<br>
(straight line distance) x 1.3, so estimate the walking distance of<br>
your "tour" using this formula. If it exceeds the required time, go to<br>
1 and start over again.<br>
5. Once you have the set of POIs you want to include in your route,<br>
connect each of them using Dijkstra (you will need to call Dijkstra<br>
several times and join the route between each pair of POIs manually)<br>
<br>
Since you are working with estimates using the formula in 4, it may<br>
not work if you need very precise walking time constraints. But if you<br>
intend to use it to create walking routes for tourism, I doubt this<br>
will be a problem. After all, you don't know how long people are going<br>
to stay at each POI.<br>
<br>
Tao<br>
<br>
2013/7/9 Stephen Woodbridge <<a href="mailto:woodbri@swoodbridge.com">woodbri@swoodbridge.com</a>>:<br>
<div class="HOEnZb"><div class="h5">> Right, what you are describing is known as "VRP with profits". The idea is<br>
> that you have some number of locations that have a profit associated to them<br>
> and typically you have some other constraints like the maximum time for the<br>
> tour. Then you have to optimize the selection of locations based on the<br>
> maximum time and maximize profit for the tour.<br>
><br>
> This is not a simple shortest path algorithm. If you have no time<br>
> constraint, then you can just use TSP with the POI's that you want to visit.<br>
> Specify a start point and the list of POIs as a distance matrix and TSP will<br>
> optimize the order to visit the POIs based on making it the shortest tour<br>
> length. As you mention, this forces the use of all points.<br>
><br>
> Otherwise, we do not have anything like this yet. Dijkstra with a negative<br>
> cost does not solve this problem.<br>
><br>
> Thanks for taking the time to explain your needs. Feel free to add a ticket<br>
> for a future enhancement. Please refer to "VRP with profits" in the ticket<br>
> so we know what you are looking for.<br>
><br>
> Thanks,<br>
> -Steve<br>
><br>
><br>
> On 7/8/2013 12:49 PM, Yaron Lev wrote:<br>
>><br>
>> Stephan i appreciate your help,<br>
>><br>
>> this is not a game problem, this is a routing problem.<br>
>><br>
>> i have some poi, such museums etc. i want to offer a route to my users<br>
>> which will be the shortest, and will pass through as many poi's as<br>
>> possible.<br>
>><br>
>> if i just +1 other edges, nothing forces the algo, to go through those<br>
>> poi's.<br>
>><br>
>> imagine the following where:<br>
>> F - poi<br>
>> E - end point<br>
>> S- start point<br>
>><br>
>><br>
>> FxxxxE<br>
>> xxxxxx<br>
>> xxxxxx<br>
>> xxxxxS<br>
>><br>
>> using +1 technique the route will not pass through F, trust me i tried :)<br>
>><br>
>> using the TSP approach, which i also tried, it forces the user go<br>
>> through all of the poi, regardless of there distance, which might be<br>
>> counter productive.<br>
>><br>
>> thanks.<br>
>><br>
>><br>
>><br>
>> On Mon, Jul 8, 2013 at 7:25 PM, Stephen Woodbridge<br>
>> <<a href="mailto:woodbri@swoodbridge.com">woodbri@swoodbridge.com</a> <mailto:<a href="mailto:woodbri@swoodbridge.com">woodbri@swoodbridge.com</a>>> wrote:<br>
>><br>
>> Why not just add 1.0 to all you edge costs so you minimum edge cost<br>
>> 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<br>
>> capture but is your goal is to collect some number of POI in an<br>
>> area, than it might be better to get the location of all the POI and<br>
>> the cost to get from each POI to each of the other POI then you can<br>
>> build a distance matrix to compute TSP solution which is the minimum<br>
>> cost to hit every POI.<br>
>><br>
>> It is not clear to be what you want to achieve here. We do not have<br>
>> algorithms targeted at game theory or solving game like problems. So<br>
>> you have to re-map the problem into point to point shortest distance<br>
>> and multiple point order optimization problems.<br>
>><br>
>> -Steve<br>
>><br>
>><br>
>> On 7/8/2013 12:19 PM, Yaron Lev wrote:<br>
>><br>
>> Hi,<br>
>><br>
>> i am wondering if there is any algo within pgrouting 2, which<br>
>> 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<br>
>> 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<br>
>> there are<br>
>> "fruits" to collect, collecting fruits will have a positive<br>
>> effect.<br>
>><br>
>> your goal to collect as many fruits as possible, fruit can have a<br>
>> -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<br>
>> flexible,<br>
>> as long as it achieve a similar goal) from route, the outcome<br>
>> 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<br>
>> am<br>
>> unable to come up with a solution which will indeed provide such<br>
>> or<br>
>> similar solution. (in specfic un able to come up with costs,<br>
>> which will<br>
>> indeed "force" the route to collect those "fruits")<br>
>><br>
>> i will appreciate any insight or direction for solving this<br>
>> 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>
>> <mailto:<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>
>> <<a href="http://lists.osgeo.org/mailman/listinfo/pgrouting-users" target="_blank">http://lists.osgeo.org/mailman/listinfo/pgrouting-users</a>><br>
>><br>
>><br>
>> _________________________________________________<br>
>> Pgrouting-users mailing list<br>
>> Pgrouting-users@lists.osgeo.__org<br>
>> <mailto:<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>
>> <<a href="http://lists.osgeo.org/mailman/listinfo/pgrouting-users" target="_blank">http://lists.osgeo.org/mailman/listinfo/pgrouting-users</a>><br>
>><br>
>><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>
><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>
<br>
<br>
</div></div><span class="HOEnZb"><font color="#888888">--<br>
Tao Romera Martínez<br>
<br>
---------------------------------------------------------<br>
Tel: 080-6805-0945<br>
Address: Koganei-shi, Tokyo, Japan<br>
<br>
Look for me on Facebook and LinkedIn<br>
---------------------------------------------------------<br>
</font></span><div class="HOEnZb"><div class="h5">_______________________________________________<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>