[pgrouting-dev] Building TRSP branch
Daniel Kastl
daniel at georepublic.de
Tue Jun 12 08:19:56 PDT 2012
Jay already wrote an "All-Pair-Shortest-Path" function which should exactly
do this.
Of course it's in a separate branch named "apsp" ;-)
https://github.com/pgRouting/pgrouting/tree/gsoc-tdsp/core/src
Also Kishore wrote an implementation for his mulitmodal routing as far as I
remember:
https://github.com/pgRouting/pgrouting/tree/apsp-johnson/core/src
Jay, Kishore, is it the same?
Daniel
On Tue, Jun 12, 2012 at 5:14 PM, Stephen Woodbridge <woodbri at swoodbridge.com
> wrote:
> On 6/12/2012 10:54 AM, Steve Horn wrote:
>
>> We have a function that performs anywhere between 10 and 800 shortest
>> paths at a time, and we are trying to speed that up.
>>
>
> What are these routes used for afterwards? TSP?
> When I built a TSP solver in routing engine I wrote, I ran Dijkstra once
> for each "city" and extracted ALL the costs to the other "cities" from this
> "city". This means if you have 10 nodes you only have to run 10 solutions,
> not 10*10 solutions.
>
> You can do this with a modified version of the driving distance code that
> allows you to extract the solved Dijkstra tree so you can extract all the
> needed routes from the start node to all the other "cities".
>
> The other potential performance boost would be to write a solver where you
> pass it the graph edges and a list of start and end nodes. Then you can
> build the graph once and solve it for each pair of start, stop nodes. This
> would eliminate the multiple graph builds assuming that are all in the same
> graph region to start with. I would return results like:
>
> route#, seq#, node#, edge#, cost
>
> where route# = 1..number_of_input_pairs
> seq# is just 1..n for the edges in that route's result
> and the rest are the same as the current solution sets.
>
> -Steve
>
>
>> Solving 86 shortest_paths:
>> Dijkstra (pgRouting shortest_path()): 27328 milliseconds
>> TRSP (pgRouting turn_restrict_shortest_path())**: 22405 milliseconds
>>
>> So it is somewhat faster, but I'm not getting the boost I was hoping for.
>>
>> As far as I know, both of the heuristic based algorithms are broken in
>> pgRouting (shooting star has the one-way bug, and a-star has a memory
>> management issue).
>>
>> A-Star will completely hose PostgreSQL if I run A-Star in combination
>> with any other pgRouting function in the same process ID (procpid from
>> pg_stat_activity).
>> Here is an output of PostgreSQL log when I run a-star:
>>
>> terminate called after throwing an instance of 'std::bad_alloc'
>> what(): std::bad_alloc
>> LOG: server process (PID 23497) was terminated by signal 6: Aborted
>> LOG: terminating any other active server processes
>> WARNING: terminating connection because of crash of another server
>> process
>> DETAIL: The postmaster has commanded this server process to roll back
>> the current transaction and exit, because another server process exited
>> abnormally and possibly corrupted shared memory.
>> HINT: In a moment you should be able to reconnect to the database and
>> repeat your command.
>> LOG: all server processes terminated; reinitializing
>> LOG: database system was interrupted; last known up at 2012-06-12
>> 10:57:51 EDT
>> LOG: database system was not properly shut down; automatic recovery in
>> progress
>> LOG: redo starts at E2/94CC82B0
>> LOG: record with zero length at E2/94CF7F90
>> LOG: redo done at E2/94CF7F40
>> LOG: database system is ready to accept connections
>> LOG: autovacuum launcher started
>>
>>
>> On Tue, Jun 12, 2012 at 10:33 AM, Stephen Woodbridge
>> <woodbri at swoodbridge.com <mailto:woodbri at swoodbridge.**com<woodbri at swoodbridge.com>>>
>> wrote:
>>
>> On 6/12/2012 9:17 AM, Steve Horn wrote:
>>
>> Was not able to find these libraries via package manager, but I
>> did get
>> pgRouting and dependencies installed manually.
>>
>> The "cannot find -lgmp" referred to a dependency of CGAL that
>> needed to
>> be installed ( http://gmplib.org/manual/ Installing-GMP.html#
>> Installing-GMP
>> <http://gmplib.org/manual/**Installing-GMP.html#**Installing-GMP<http://gmplib.org/manual/Installing-GMP.html#Installing-GMP>>
>> )
>>
>> Also of note is that CGAL needs a specific version of the Boost
>> libraries to work (1.41).
>> After successful pgRouting make/make install then I ran the
>> driving_distance function to test and got this:
>>
>> “Error while loading shared libraries:
>> libboost_thread.so.1.41.0: cannot
>> open shared object file: No such file or directory"
>>
>> Used the information in this blog to correct that error:
>> http://somethingididnotknow. wordpress.com/2012/02/17/fix-
>> the-error-while-loading- shared-libraries-libboost_
>> thread-so-1-48-0-cannot-open- shared-object-file-no-such-
>> file-or-directory-error/
>> <http://somethingididnotknow.**wordpress.com/2012/02/17/fix-**
>> the-error-while-loading-**shared-libraries-libboost_**
>> thread-so-1-48-0-cannot-open-**shared-object-file-no-such-**
>> file-or-directory-error/<http://somethingididnotknow.wordpress.com/2012/02/17/fix-the-error-while-loading-shared-libraries-libboost_thread-so-1-48-0-cannot-open-shared-object-file-no-such-file-or-directory-error/>
>> >
>>
>>
>> Hope this helps someone in the future.
>>
>> Steve: Haven't done a deep dive into the TRSP functionality -but
>> I am
>> impressed at the surface. Does it use an A Star algorithm at the
>> core?
>>
>>
>> I'm afraid I have not looked in detail at the exact algorithm but I
>> believe it uses a combination of Dijkstra that is node based and
>> then uses, edge based exploration to navigate around the turn
>> restrictions.
>>
>> A Star requires a heuristic so you pass the end points of the edges
>> which we do not pass in TRSP, so we are not doing that. That might
>> be an interesting future enhancement that could speed TRSP up even
>> faster. My rough timing tests showed that performance was a little
>> slower than Dijkstra without any restrictions, but about 5x faster
>> than our broken Shooting Star.
>>
>> Roni, If you have a chance it would be good if you could provide a
>> little more background information on how TRSP solves.
>>
>> Thanks,
>> -Steve W
>>
>> Thanks for your efforts on this!
>>
>> On Mon, Jun 11, 2012 at 8:26 PM, Stephen Woodbridge
>> <woodbri at swoodbridge.com <mailto:woodbri at swoodbridge.**com<woodbri at swoodbridge.com>
>> >
>> <mailto:woodbri at swoodbridge. com
>>
>> <mailto:woodbri at swoodbridge.**com <woodbri at swoodbridge.com>>>>
>> wrote:
>>
>> On 6/11/2012 7:58 PM, Steve Horn wrote:
>>
>> Trying to manually build and install the gmp dependency for
>> cgal..but
>> I'm curious how you can install it through yum. The
>> searches you
>> provided do not turn up anything.
>>
>>
>> You probably need to google "centos cgal" and then add an
>> appropriate repository to yum. I forget the exact way to do
>> that.
>>
>>
>> I'm more familiar with apt get and adding repositories.
>> Does yum
>> work
>> similarly? Just curious and trying to learn. Thanks!
>>
>>
>> Yes, yum is the CentOS equivalent to apt-get. They both work in
>> similar ways. There were some good yum howto or tutorials that
>> I
>> learned from when I needed to use it that I found via google.
>>
>> -Steve
>>
>> On Monday, June 11, 2012, Stephen Woodbridge wrote:
>>
>> On 6/11/2012 3:41 PM, Steve Horn wrote:
>>
>> Hello again :)
>>
>> Trying to build and install the trsp branch on
>> my CentOS
>> linux box.
>> (Using
>> https://github.com/pgRouting/ pgrouting/wiki/Developer---
>> Getting-Started
>> <https://github.com/pgRouting/ pgrouting/wiki/Developer---
>> Getting-Started
>> <https://github.com/pgRouting/ pgrouting/wiki/Developer---
>> Getting-Started
>> <https://github.com/pgRouting/**pgrouting/wiki/Developer---**
>> Getting-Started<https://github.com/pgRouting/pgrouting/wiki/Developer---Getting-Started>
>> >>>
>> as
>> a baseline)
>>
>> Here is where I'm at:
>> # git clone https://github.com/pgRouting/
>> pgrouting.git
>> <https://github.com/pgRouting/ pgrouting.git
>> <https://github.com/pgRouting/ pgrouting.git
>> <https://github.com/pgRouting/**pgrouting.git<https://github.com/pgRouting/pgrouting.git>
>> >>>
>> # cd pgrouting
>>
>> //Hack around installing GAUL
>>
>> # cmake -DWITH_TSP=ON -DWITH_DD=ON .
>> -- POSTGRESQL_EXECUTABLE is
>> POSTGRESQL_EXECUTABLE-NOTFOUND
>> -- Found PostgreSQL: /usr/include/postgresql/
>> include/server,
>> /usr/pgsql-9.1/lib/libpq.so
>> Boost headers were found here: /usr/include
>> Output directory for libraries is set to
>> /usr/pgsql-9.1/lib
>> Installation directory for libraries is set to
>> /usr/pgsql-9.1/lib and
>> for SQL files is set to /usr/share/pgrouting
>> Installation directory for libraries is set to
>> /usr/pgsql-9.1/lib
>> -- Configuring done
>> -- Generating done
>> -- Build files have been written to:
>> /home/shorn/pgrouting
>>
>> # make
>> Linking CXX shared library
>> ../../../lib/librouting_tsp.so
>> */usr/bin/ld: cannot find -lgmp //THIS APPEARS
>> TO BE
>> THE PROBLEM?*
>> collect2: ld returned 1 exit status
>> make[2]: *** [lib/librouting_tsp.so] Error 1
>> make[1]: *** [extra/tsp/src/CMakeFiles/
>> routing_tsp.dir/all] Error 2
>>
>> make: *** [all] Error 2
>>
>> Can anyone help me understand the error "Cannot
>> find -lgmp"?
>>
>>
>> For TSP you need to instal GUAL and for DD you need
>> the CGAL
>> libraries.
>>
>> Try:
>>
>> yum search libcgal
>> yum search cgal
>>
>> You probably need the dev package also.
>>
>> After you:
>>
>> cd pgrouting
>> git checkout trsp ## switch to trsp branch
>> git pull
>> cmake -DWITH_TRSP=ON -DWITH_TSP=ON -DWITH_DD=ON .
>>
>> -Steve
>>
>> ______________________________ _________________
>> pgrouting-dev mailing list
>> pgrouting-dev at lists.osgeo.org
>> <mailto:pgrouting-dev at lists.**osgeo.org<pgrouting-dev at lists.osgeo.org>
>> >
>> <mailto:pgrouting-dev at lists. osgeo.org
>>
>> <mailto:pgrouting-dev at lists.**osgeo.org<pgrouting-dev at lists.osgeo.org>
>> >>
>>
>> http://lists.osgeo.org/ mailman/listinfo/pgrouting-dev
>> <http://lists.osgeo.org/ mailman/listinfo/pgrouting-dev
>> <http://lists.osgeo.org/ mailman/listinfo/pgrouting-dev
>> <http://lists.osgeo.org/**mailman/listinfo/pgrouting-dev<http://lists.osgeo.org/mailman/listinfo/pgrouting-dev>
>> **> > >
>>
>>
>>
>> --
>> Steve Horn
>>
>>
>>
>> ______________________________ _________________
>> pgrouting-dev mailing list
>> pgrouting-dev at lists.osgeo.org
>> <mailto:pgrouting-dev at lists.**osgeo.org<pgrouting-dev at lists.osgeo.org>
>> >
>> <mailto:pgrouting-dev at lists. osgeo.org
>>
>> <mailto:pgrouting-dev at lists.**osgeo.org<pgrouting-dev at lists.osgeo.org>
>> >>
>>
>> http://lists.osgeo.org/ mailman/listinfo/pgrouting-dev
>> <http://lists.osgeo.org/ mailman/listinfo/pgrouting-dev
>> <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
>> <mailto:pgrouting-dev at lists.**osgeo.org<pgrouting-dev at lists.osgeo.org>
>> >
>> <mailto:pgrouting-dev at lists. osgeo.org
>>
>> <mailto:pgrouting-dev at lists.**osgeo.org<pgrouting-dev at lists.osgeo.org>
>> >>
>>
>> http://lists.osgeo.org/ mailman/listinfo/pgrouting-dev
>> <http://lists.osgeo.org/ mailman/listinfo/pgrouting-dev
>> <http://lists.osgeo.org/**mailman/listinfo/pgrouting-dev<http://lists.osgeo.org/mailman/listinfo/pgrouting-dev>
>> **> >
>>
>>
>>
>>
>> --
>> Steve Horn
>>
>>
>>
>> ______________________________ _________________
>> pgrouting-dev mailing list
>> pgrouting-dev at lists.osgeo.org <mailto:pgrouting-dev at lists.**
>> osgeo.org <pgrouting-dev at lists.osgeo.org>>
>> http://lists.osgeo.org/ mailman/listinfo/pgrouting-dev
>> <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 <mailto:pgrouting-dev at lists.**osgeo.org<pgrouting-dev at lists.osgeo.org>
>> >
>> http://lists.osgeo.org/ mailman/listinfo/pgrouting-dev
>> <http://lists.osgeo.org/**mailman/listinfo/pgrouting-dev<http://lists.osgeo.org/mailman/listinfo/pgrouting-dev>
>> **>
>>
>>
>>
>>
>> --
>> Steve Horn
>>
>>
>>
>> ______________________________**_________________
>> 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>
>
--
Georepublic UG & Georepublic Japan
eMail: daniel.kastl at georepublic.de
Web: http://georepublic.de
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/pgrouting-dev/attachments/20120612/9901203e/attachment-0001.html>
More information about the pgrouting-dev
mailing list