[pgrouting-dev] Building TRSP branch
Stephen Woodbridge
woodbri at swoodbridge.com
Tue Jun 12 08:14:35 PDT 2012
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>> 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> )
>
> 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/>
>
>
> 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>
> <mailto:woodbri at swoodbridge. com
> <mailto: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>>>
> 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>>>
> # 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>
> <mailto:pgrouting-dev at lists. osgeo.org
> <mailto: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>
> <mailto:pgrouting-dev at lists. osgeo.org
> <mailto: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>
> <mailto:pgrouting-dev at lists. osgeo.org
> <mailto: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 <mailto: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 <mailto:pgrouting-dev at lists.osgeo.org>
> 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
More information about the pgrouting-dev
mailing list