[pgrouting-dev] Scheduled Routing Algorithm

Fri Aug 12 15:07:52 EDT 2011

Hi Kishore,

I read your report and saw the APSP_Johnson implementation. The prototype
is:

CREATE OR REPLACE FUNCTION apsp_johnson(sql text)
         RETURNS SETOF apsp_edge
         AS '$libdir/librouting'
         LANGUAGE 'C' IMMUTABLE STRICT;

I guess this serves the same function as the apsp algorithm we already
have[1].

I think for your application, you need APSP for all vertices in the database
table. So, if you use:

SELECT * from all_pairs_shortest_path
    ('SELECT gid as id,source::integer,target::integer,length::double
precision as cost
    from ways where source in (select distinct(source) from ways)'::TEXT
    ,false,false);

it will solve your query. Please correct me if I am wrong, or any additional
information is needed.

Also, Daniel, Steve -

Should we change my apsp implementation so that it gives option to use
either johnsons boost implementation or warshall boost implementation? That
would provide more options?

[1] https://github.com/pgRouting/pgrouting/wiki/APSP

On Wed, Aug 10, 2011 at 6:10 PM, Stephen Woodbridge <woodbri at swoodbridge.com
> wrote:

> Hi Kishore,
>
> Very nice diagram! This really helps me understand more of what you have
> been doing in this project and how the scheduled routing works.
>
> Thanks,
>  -Steve
>
>
> On 8/10/2011 8:27 AM, Kishore Kumar wrote:
>
>> Hi,
>> Prepared this diagram(attached) depicting the file structure and flow
>> of control of scheduled routing algorithm. Currently the code works
>> for GTFS Trips with fixed timetable(Eg:Train). To make it multi-modal,
>> it has to support GTFS Trips with only frequency information(Eg:Bus)
>> and private transit(Eg:Walk, Cycle). The existing scheduled routing
>> can be extended a little by also including trips which have frequency
>> information only. And, for walking to be private transit options,
>> since the speed of transit is going to be a constant, the straight
>> line distance from X to goal divided by constant velocity will give
>> the shortest time heuristic. Hence, I'll possibly finish it in a day
>> or two.
>>
>> Once that is finished, I'll start writing documentation, tests and
>> demo implementations at http://busroutemaps.in/ and of course, Code
>> cleanup and optimisations.
>>
>> Thanks,
>> J Kishore kumar.
>>
>> On Sat, Jul 9, 2011 at 8:47 PM, Kishore Kumar<justjkk at gmail.com>  wrote:
>>
>>> Hi,
>>>
>>> I commited the code[1] that implements the scheduled route using
>>> modified boost astar search and Implicit graph. And, I have an issue
>>> now:
>>> 1. The modified astar and breadth first search boost header files are
>>> copied from Boost Version 1.46.1. I intent to test it on earlier boost
>>> libraries. But, what is the best approach to handle this scenario?
>>> Should we notify boost developers about having a non-const version to
>>> support Implicit Graphs?
>>>
>>> Thanks,
>>> J Kishore kumar.
>>>
>>> [1] - https://github.com/pgRouting/**pgrouting/commit/**
>>> 3aa2b4e951c584fa3ae03235f7b2e0**6379cbb229<https://github.com/pgRouting/pgrouting/commit/3aa2b4e951c584fa3ae03235f7b2e06379cbb229>
>>>
>>> On Tue, Jun 28, 2011 at 3:36 AM, Stephen Woodbridge
>>> <woodbri at swoodbridge.com>  wrote:
>>>
>>>> Hi Kishore,
>>>>
>>>> I not sure I can improve on this algorithm as I'm do not think I have
>>>> followed all the details and issues in implementing it. But I do have
>>>> two
>>>> thoughts:
>>>>
>>>> 1. if you are not on the boost-users mailing list [1] them you should
>>>> subscribe to that list and ask questions about how to best tackle some
>>>> of
>>>> the boost problems you are facing. In the Subject: add the tag "[BGL]"
>>>> to
>>>> indicate this is a Boost Graph Library question and the developers are
>>>> very
>>>> helpful and responsive to question.
>>>>
>>>> 2. often I find that it is useful to transform my problem into another
>>>> problem that has a simpler or known solution. It seems like you should
>>>> be
>>>> able to do this with your problem. If I understand it correct (and I
>>>> confess
>>>> I might not), It seems that your frequency problem could be transformed
>>>> into
>>>> a straight scheduling problem if your transfer is just a waiting time at
>>>> a
>>>> transfer point. One simple way to represent these transfer times is to
>>>> add
>>>> an additional edge that has the cost of the transfer associated to it.
>>>>
>>>> So if we think about the route like, I start at a bus station at some
>>>> time
>>>> X, and there is some transfer cost representing the wait time W window.
>>>> so
>>>> I'm now on the the bus route at X+W+edge cost, and I continue
>>>> accumulating
>>>> wait times and edge costs as I trasfer between lines and travel the
>>>> network
>>>> to my destination. If this works, then this is just a straight time
>>>> dependent solution but the trick is to analyze the data and create a
>>>> network
>>>> suitable for this type of solution.
>>>>
>>>> [1] http://lists.boost.org/**mailman/listinfo.cgi/boost-**users<http://lists.boost.org/mailman/listinfo.cgi/boost-users>
>>>>
>>>> -Steve
>>>>
>>>>
>>>> On 6/27/2011 5:40 PM, Kishore Kumar wrote:
>>>>
>>>>>
>>>>> Hi,
>>>>>
>>>>> After reading on Contraction Hierarchies[1] and APSP algorithms, I
>>>>> came up with a plan to find the scheduled route. Here goes the plan:
>>>>>
>>>>> * Pre-compute Shortest Time Graph for Directly reachable pair of stops
>>>>> by going through every trip in a loop.
>>>>> * Find Shortest Time Graph from every stop to every other
>>>>> stop(Transitive closure) using APSP.
>>>>> * Use Boost astar_search_no_init[2] function passing an Implicit
>>>>> Graph[3] G with following definitions:
>>>>>      Vertex : (Stop, Time)
>>>>>      Edge : Trip
>>>>>      Edge weight : Travel Time + Waiting Time
>>>>>      Heuristic : Shortest Time from Trip destination to Target
>>>>> * As Every Vertex is expanded, new Vertices and Edges are generated
>>>>> for trips in the next 1 hour(or whatever is the Upper limit for
>>>>> Waiting time).
>>>>>
>>>>> I didn't find any examples using astar_search_no_init function. [4]
>>>>> solves 8-puzzle problem using Implicit Graph for astar_search
>>>>> function, but it uses astar_search function with a hacked BFS code.
>>>>> So, it is going to be a challenge to code this out using BGL.
>>>>>
>>>>> Please advise on ways to improve the algorithm.
>>>>>
>>>>> Thanks,
>>>>> J Kishore kumar.
>>>>>
>>>>> [1] - http://algo2.iti.kit.edu/**documents/routeplanning/**
>>>>> geisberger_dipl.pdf<http://algo2.iti.kit.edu/documents/routeplanning/geisberger_dipl.pdf>
>>>>> [2] -
>>>>> http://www.boost.org/doc/libs/**1_40_0/libs/graph/doc/astar_**
>>>>> search.html<http://www.boost.org/doc/libs/1_40_0/libs/graph/doc/astar_search.html>
>>>>> [3] - http://en.wikipedia.org/wiki/**Implicit_graph<http://en.wikipedia.org/wiki/Implicit_graph>
>>>>> [4] - http://www.cs.rpi.edu/~beevek/**research/astar_bgl04.pdf<http://www.cs.rpi.edu/%7Ebeevek/research/astar_bgl04.pdf>
>>>>> ______________________________**_________________
>>>>> pgrouting-dev mailing list
>>>>> pgrouting-dev at lists.osgeo.org
>>>>> http://lists.osgeo.org/**mailman/listinfo/pgrouting-dev<http://lists.osgeo.org/mailman/listinfo/pgrouting-dev>
>>>>>
>>>>
>>>> ______________________________**_________________
>>>> pgrouting-dev mailing list
>>>> pgrouting-dev at lists.osgeo.org
>>>> http://lists.osgeo.org/**mailman/listinfo/pgrouting-dev<http://lists.osgeo.org/mailman/listinfo/pgrouting-dev>
>>>>
>>>>
>>>
>>>
>>> ______________________________**_________________
>>> pgrouting-dev mailing list
>>> pgrouting-dev at lists.osgeo.org
>>> http://lists.osgeo.org/**mailman/listinfo/pgrouting-dev<http://lists.osgeo.org/mailman/listinfo/pgrouting-dev>
>>>
>>
> ______________________________**_________________
> pgrouting-dev mailing list
> pgrouting-dev at lists.osgeo.org
> http://lists.osgeo.org/**mailman/listinfo/pgrouting-dev<http://lists.osgeo.org/mailman/listinfo/pgrouting-dev>
>

-- 
Regards,
-Jay Mahadeokar
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.osgeo.org/pipermail/pgrouting-dev/attachments/20110813/6d729aa2/attachment.html