Hi Kishore, <br><br>My reply inline:<br><br><div class="gmail_quote">On Wed, Jun 8, 2011 at 1:51 PM, Kishore Kumar <span dir="ltr"><<a href="mailto:justjkk@gmail.com">justjkk@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
Hi,<div><br></div><div>I was working on solving the Non-scheduled Routing problem. I made notes in the GSoC spiral book and attached them here.</div><div><br></div><div>Non-scheduled Routing - It is primarily to be used for public transport routing where the absolute timetable of trips is not available or when the vehicles themselves don't follow any schedule.</div>
<div><br></div><div>Type of Output:</div><div>There are two kinds of outputs I can imagine.</div><div>(a). List the Changeovers[1] that have maximum frequency and minimize the total travel time and then find Route numbers serving from one Changeover to another. Eg: <a href="http://busroutes.in/chennai/path/1859/1976/" target="_blank">http://busroutes.in/chennai/path/1859/1976/</a></div>
<div>(b). Find and return a single sequence of routes corresponding to least total travel time.</div><div><br></div><div>While output (a) gives more route numbers and calculates and dilutes the expected total travel time, output (b) gives more accurate total travel time.</div>
<div>The problem with output (b) is that it ignores any alternate routes serving any successive changeovers and only takes the one with least travel time.</div><div>Hence, I decided to go with output (a).</div><div><br></div>
<div>To get a list of changeovers, two graphs should be generated from GTFS input:</div><div>* Frequency Graph - effective frequency between any two stops</div><div>* Travel Time Graph - expected travel time between any two stops</div>
<div><br></div><div>And, the algorithm to find the changeovers:</div><div>* Initially, store the direct travel time from source to destination as cutoff.</div><div>* Explore the state-space of stops by exploring stops with small travel time first.</div>
<div>* Update cutoff value as the shortest travel time to destination.</div><div>* Prune the branches at cutoff.</div><div>* After all branches are pruned, return the path corresponding to the cutoff travel time as the sequence of changeovers.</div>
<div><br></div></blockquote><div><br>Let me rephrase the problem. Please tell me if I understood it correctly..<br><br>So, the input to your algorithm is a graph, where nodes are the stops, and edges are the travel times between stops. The edges can be only traversed (i.e they actually exist) at certain time instances. <br>
<br>Ex - If frequency of edge u-> v is 2 hours. One departure was at 12:00 PM. Then if you arrive at u at 12:30 PM, then your changeover time at u will be 1:30 mins. Since, next departure is only possible at 2 pm.<br>
<br>So, I think this can be again reduced to a variant time-dependent dijkstra algorithm.<br><br>The only difference being - your travel_time is now constant for each edge, But your change_over time depends on the time at which your dijkstra search starts. So, the algorithm should again take O(m + n log n) time. You need to modify dijkstra to suit your need.<br>
<br><br>I hope I am not missing any point here. Please correct me if I am wrong. Also any clarification needed?<br> </div><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
<div></div><div>After the sequence of changeovers is calculated, it is trivial to get the list of routes that serve between them.</div><div><br></div><div>Performance:</div><div>Let n be the number of stops and m be the number of trips,</div>
<div>* Generating Frequency Graph and Travel Time Graph from the GTFS input have an ϑ(n^2) space complexity and ϑ(n^2 * m) time complexity.</div><div>* Finding the list of changeovers has an O(n!) time complexity[worst case] and o(n) in the best case.</div>
<div><br></div><div>I am no algo expert and cannot think of a better performing algorithm. Thoughts on this?</div><div><br></div><div>Thanks & Regards,</div><div>J Kishore kumar.</div><div><br></div><div>[1] - Changeover is an intermediate stop where the passenger gets down from one vehicle and boards another vehicle bound to a different route.</div>
<br>_______________________________________________<br>
pgrouting-dev mailing list<br>
<a href="mailto:pgrouting-dev@lists.osgeo.org">pgrouting-dev@lists.osgeo.org</a><br>
<a href="http://lists.osgeo.org/mailman/listinfo/pgrouting-dev" target="_blank">http://lists.osgeo.org/mailman/listinfo/pgrouting-dev</a><br>
<br></blockquote></div><br><br clear="all"><br>-- <br>Regards,<br>-Jay Mahadeokar<br><br>