pgRouting

Forum #22 - Topic #54 - Message List

Extend Tutorial for Traveling Sales Person?

I am curious if there are any plans to extend the online tutorial to include a Traveling Sales Person example.

If not, can anyone point me to example files for a TSP problem?

Thanks,

David.

davidfawcett
10/17/07 00:37:24
Tree View Flat View (newer first) Flat View (older first)
  • Message #201

    Hi David,

    You can download the sample application (http://files.orkney.jp/pgrouting/sample/pgRouting-sampleapp.tar.bz) and look inside tsp.phtml file.

    It is for version 1.0.0a, but TSP part didn't change so much.

    anton
    10/17/07 09:03:03
    • Message #295

      Anton,

      I am trying to get your sample application up and running on my local machine. I have the tsp.php page loading and mapscript is generating the initial map.

      When I select 5 different locations in the drop-downs and hit submit, I get several errors.

      I am using pgRouting 1.0.0b and PostGIS 1.3.1-3.

      Here is a dump of the relevent entries in apache2/error_log: [Mon Dec 10 12:43:08 2007] [error] [client 127.0.0.1] PHP Warning: Error?: msDrawMap(): Failed to draw layer named 'path'., referer: http://localhost/~david/routingdemo/tsp.php

      [Mon Dec 10 12:43:08 2007] [error] [client 127.0.0.1] in /Users/david/Sites/routingdemo/tsp.php on line 118, referer: http://localhost/~david/routingdemo/tsp.php

      [Mon Dec 10 12:43:08 2007] [error] [client 127.0.0.1] PHP Warning: Error?: msPOSTGISLayerWhichShapes(): Error executing POSTGIS SQL statement (in FETCH ALL): DECLARE mycursor BINARY CURSOR FOR SELECT asbinary(force_collection(force_2d(the_geom)),'NDR'),gid::text from (select gid, the_geom from tsp_astar_as_geometry_internal_id('kanagawa', '7731,6280,17838,76309,8165', 7731)) as g WHERE the_geom && setSRID('BOX3D(139.398227524746 35.2909916666667,139.730707753032 35.5629108333333)'::BOX3D, -1 ), referer: http://localhost/~david/routingdemo/tsp.php

      [Mon Dec 10 12:43:08 2007] [error] [client 127.0.0.1] -ERROR: operator does not exist: text boolean, referer: http://localhost/~david/routingdemo/tsp.php

      [Mon Dec 10 12:43:08 2007] [error] [client 127.0.0.1] LINE 1: ...( $9 ) ' , ' quote_literal( $10 ) ' , $11 '..., referer: http://localhost/~david/routingdemo/tsp.php

      [Mon Dec 10 12:43:08 2007] [error] [client 127.0.0.1] , referer: http://localhost/~david/routingdemo/tsp.php

      [Mon Dec 10 12:43:08 2007] [error] [client 127.0.0.1] HINT: No operator matches the given name and argument type(s). You may need to add explicit type casts., referer: http://localhost/~david/routingdemo/tsp.php

      [Mon Dec 10 12:43:08 2007] [error] [client 127.0.0.1] QUERY: SELECT $1 'FROM ' quote_ident( $2 ) ' where setSRID('BOX3D(' $3 - $4 ' ' $5 - $4 ',' $6 + $4 ' ' $7 + $4 ')'::BOX3D, ' $8 ') && the_geom, ' quote_literal( $9 ) ' , ' quote_literal( $10 ) ' , $11 , $12 in /Users/david/Sites/routingdemo/tsp.php on line 118, referer: http://localhost/~david/routingdemo/tsp.php

      [Mon Dec 10 12:43:08 2007] [error] [client 127.0.0.1] PHP Fatal error: Call to a member function saveWebImage() on a non-object in /Users/david/Sites/routingdemo/tsp.php on line 119, referer: http://localhost/~david/routingdemo/tsp.php

      If I dump the value of the $_GET array, I get: array(5) { start?=> string(4) "7731" next1?=> string(4) "6280" next2?=> string(5) "17838" next3?=> string(5) "76309" next4?=> string(4) "8165" }

      To me, it is obvious that MapScript? is failing because it isn't getting anything valid back from the db. What I am not sure about is why the PostGIS function is failing.

      Any help is appreciated.

      Thanks,

      David.

      davidfawcett
      12/11/07 03:56:01
      • Message #298

        Can you try the newer version of pgRouting?

        The problem is in PostgreSQL (I guess it is 8.2.x in your case) - they changed text to boolean conversion.

        If you don't want to recompile pgRouting, just use newer SQL functions.

        anton
        12/11/07 09:43:35
        • Message #300

          Thanks for the response. Yes, Postgres is at 2.5.2 I am using William Kyngesburye's OS X binaries, so don't have an easy way to upgrade pgRouting.

          What are the newer SQL functions that you are referring to?

          David.

          davidfawcett
          12/11/07 13:13:22
          • Message #302

            Ah, you are using OSX.

            Just download sources of 1.01 version from the main page. The functions you need are in src/core/sql

            anton
            12/11/07 14:08:48
            • Message #303

              So, just run the routing_core.sql and routing_core_wrappers.sql scripts and create/replace all of the existing pgRouting functions?

              davidfawcett
              12/11/07 14:24:29
              • Message #304

                Exactly!

                anton
                12/11/07 14:29:41
                • Message #358

                  OK, I am back running 1.0.1 and trying to get the tsp demo running.

                  I believe that I am further along than I was when running 1.0a, but still getting errors. I am not sure if it is incompatibility between the older demo and the newer version of Postgres and pgRouting.

                  Any help is appreciated.

                  David.

                  [Mon Jan 14 21:23:11 2008] [error] [client 127.0.0.1] PHP Warning: pg_fetch_row() expects parameter 1 to be resource, boolean given in /Users/david/Sites/routingdemo/tsp.php on line 140

                  [Mon Jan 14 21:23:12 2008] [error] [client 127.0.0.1] PHP Warning: Error?: msDrawMap(): Failed to draw layer named 'path'.

                  [Mon Jan 14 21:23:12 2008] [error] [client 127.0.0.1] in /Users/david/Sites/routingdemo/tsp.php on line 118

                  [Mon Jan 14 21:23:12 2008] [error] [client 127.0.0.1] PHP Warning: Error?: prepare_database(): Error executing POSTGIS DECLARE (the actual query) statement: 'DECLARE mycursor BINARY CURSOR FOR SELECT asbinary(force_collection(force_2d(the_geom)),'NDR'),gid::text from (select gid, the_geom from tsp_astar_as_geometry_internal_id('kanagawa', '7731,6280,17838,76309,124369', 7731)) as g WHERE the_geom && setSRID('BOX3D(139.038158611111 35.1478066724853,139.6584875 35.6551430497369)'::BOX3D, -1 )'

                  [Mon Jan 14 21:23:12 2008] [error] [client 127.0.0.1]

                  [Mon Jan 14 21:23:12 2008] [error] [client 127.0.0.1] Postgresql reports the error as 'ERROR: function tsp_astar_as_geometry_internal_id("unknown", "unknown", integer) does not exist

                  [Mon Jan 14 21:23:12 2008] [error] [client 127.0.0.1] LINE 1: ...,'NDR'),gid::text from (select gid, the_geom from tsp_astar_...

                  [Mon Jan 14 21:23:12 2008] [error] [client 127.0.0.1] [Mon Jan 14 21:23:12 2008] [error] [client 127.0.0.1] HINT: No function matches the given name and argument types. You may need to add explicit type casts.

                  [Mon Jan 14 21:23:12 2008] [error] [client 127.0.0.1] '

                  [Mon Jan 14 21:23:12 2008] [error] [client 127.0.0.1]

                  [Mon Jan 14 21:23:12 2008] [error] [client 127.0.0.1] More Help:

                  [Mon Jan 14 21:23:12 2008] [error] [client 127.0.0.1]

                  [Mon Jan 14 21:23:12 2008] [error] [client 127.0.0.1] Error with POSTGIS data variable. You specified 'check your .map file'.

                  [Mon Jan 14 21:23:12 2008] [error] [client 127.0.0.1] Standard ways of specifiying are :

                  [Mon Jan 14 21:23:12 2008] [error] [client 127.0.0.1] (1) 'geometry_column from geometry_table'

                  [Mon Jan 14 21:23:12 2008] [error] [client 127.0.0.1] (2) 'geometry_column from (sub query) as foo in /Users/david/Sites/routingdemo/tsp.php on line 118

                  [Mon Jan 14 21:23:12 2008] [error] [client 127.0.0.1] PHP Fatal error: Call to a member function saveWebImage() on a non-object in /Users/david/Sites/routingdemo/tsp.php on line 119 xydata:apache2 david$

                  davidfawcett
                  01/15/08 12:32:06
                  • Message #359

                    For 1.0.1 version you should use tsp_astar or tsp_astar_directed version.

                    anton
                    01/15/08 15:15:52
                    • Message #365

                      Can anyone verify that the tsp_astar() function works in 1.0.1?

                      When I call the tsp_astar() function, I am still getting an error that 'HINT: No function matches the given name and argument types'. This occurs at line 13 of tsp_astar(), where the tsp() function is called.

                      Could anyone supply a call to the tsp_astar() function that works with the kanagawa dataset? Just a simple revision of the below call?

                      select vertex_id from tsp_astar('select distinct source::integer as source_id,x(startpoint(the_geom)) as x, y(startpoint(the_geom)) as y from kanagawa where source in (7731,6280,17838,76309,124369)','7731,6280,17838,76309,124369',7731);

                      Thanks,

                      David.

                      davidfawcett
                      01/16/08 13:37:12
                      • Message #366

                        Hi David,

                        The tsp_astar is a wrapper function, so you need to call it like this:

                        select * from tsp_astar('kanagawa', '7731,6280,17838,76309,124369',7731);

                        and you'll get 903 rows as a result.

                        Of course, you need x1, y1, x2, y2 columns for A* shortest path calculation between points.

                        anton
                        01/16/08 14:06:48
                        • Message #431

                          Anton,

                          I have the first query working and I can get a route drawn, I am now working on the points.

                          In the demo, there is the function solveTsp(). I am trying to get a static example of that query working. I know that the demo that I am using is old, so the function used in the below query may not be the appropriate one.

                          Here is where I am at, but I am getting an error:

                          select vertex_id from tsp('select distinct source::integer as source_id, x(startpoint(the_geom)) as x, y(startpoint(the_geom) as y from kanagawa where source in (7731,6280,17838,76309,69902)','7731,6280,17838,76309,69902',7731)

                          Here is the error that I am getting:

                          ERROR: syntax error at or near "as" LINE 1: ...tartpoint(the_geom)) as x, y(startpoint(the_geom) as y from ...

                          QUERY: select distinct source::integer as source_id, x(startpoint(the_geom)) as x, y(startpoint(the_geom) as y from kanagawa where source in (7731,6280,17838,76309,69902)

                          ********** Error **********

                          ERROR: syntax error at or near "as" SQL state: 42601

                          I think that if I can get a static version of this query running, I can tweak the php script to get get it working.

                          Can anyone help me get this query working?

                          thanks,

                          David.

                          davidfawcett
                          02/23/08 14:37:36
                          • Message #432

                            There should be 'y(startpoint(the_geom)) as y' instead of 'y(startpoint(the_geom) as y' - you miss the ')' before 'as'. This query is workin for me.

                            anton
                            02/25/08 09:56:23
                            • Message #434

                              Thanks again Anton.

                              The query is now working and the application is working. The one issue that I see is that the points are returned in the order that they exist in the table. In other words, the points are in the correct locations, but they are not ordered/numbered properly.

                              Here is the code that builds the SQL:

                              $sql = "select distinct source::integer as source_id, x(startpoint(the_geom)) as x, y(startpoint(the_geom)) as y from kanagawa where source in (".$ids.")";

                              I assume that I need to apply one of the routing methods to this to get the points ordered.

                              Any suggestions?

                              Thanks,

                              David.

                              davidfawcett
                              02/26/08 23:46:36
                              • Message #435

                                To answer my own question:

                                $sql = "select vertex_id from tsp('select distinct source::integer as source_id, x(startpoint(the_geom)) as x, y(startpoint(the_geom)) as y from kanagawa where source in (".$ids.")','".$ids."',".$start.")";

                                This works for me.

                                Once I get my page cleaned up, I will post my revised tsp demo page somewhere where it can be found.

                                Now, on to my own data...

                                Thanks for all of your help.

                                David.

                                davidfawcett
                                02/27/08 03:51:42
                                • Message #436

                                  Hooray!

                                  anton
                                  02/27/08 16:56:25
                                • Message #444

                                  I apologize for taking so long. I had to modify the tsp.phtml file that came with the demo to get it to work with pgRouting version 1.0.

                                  You can find it at: http://www.flatlandmaps.com/lab/tsp.phtml.txt

                                  David.

                                  davidfawcett
                                  04/10/08 11:51:42
                    • Message #364

                      Does anyone out there have a demo that works out-of-the-box with pgRouting 1.0.1?

                      Thanks,

                      David.

                      davidfawcett
                      01/15/08 23:34:21
Tree View Flat View (newer first) Flat View (older first)