segmentation fault and non existant relation in tsp

[jcasanov]

I installed pgrouting 1.05 with tsp on a centos 5.5 machine with postgres 8.4.7 and postgis 1.3.6. When i tried to run this query:

SELECT *
FROM tsp_astar_directed('view_viasnodo','38151,38151,35604,35586,20948,39935,35457,40636,40242,35485,19143,40079,40335,40058,19058',38147,12000,false,false);

i get this message "ERROR: relation "tsp_test" does not exist at character 328" which is because the function tsp_astar_directed() in routing_tsp_wrappers.sql has an UNION ALL that takes values from that table (that obviously doesn't really exist)... i workaround that problem creating a dummy tsp_test table...

then when i try the same select i get "segmentation fault", this is the backtrace:

(gdb) bt
#0  0x00b02f7b in tsp_seed (pop=0x9430ee0, adam=0x9431090) at
/root/pgrouting-1.05/extra/tsp/src/tsp_solver.cpp:84
#1  0x00337b66 in gaul_population_fill (pop=0x9430ee0, num=88) at ga_core.c:823
#2  0x0034683f in ga_evolution (pop=0x9430ee0, max_generations=88) at
ga_optim.c:2415
#3  0x00b0315b in find_tsp_solution (num=22, dist=0xb04240,
p_ids=0xbfecb560, source=38147, fit=0xbfecb600, err_msg=0x0)
    at /root/pgrouting-1.05/extra/tsp/src/tsp_solver.cpp:296
#4  0x00b02b7c in solve_tsp (fcinfo=0xbfecb6c4) at
/root/pgrouting-1.05/extra/tsp/src/tsp.c:345
#5  tsp (fcinfo=0xbfecb6c4) at /root/pgrouting-1.05/extra/tsp/src/tsp.c:401
#6  0x08191002 in ExecMakeTableFunctionResult ()
#7  0x0819dbd4 in ?? ()
#8  0x081924bf in ExecScan ()
#9  0x0819db59 in ExecFunctionScan ()
#10 0x0818ad8f in ExecProcNode ()
#11 0x081888ab in standard_ExecutorRun ()
#12 0x0823917e in ?? ()
#13 0x08239f44 in PortalRunFetch ()
#14 0x081a56b0 in ?? ()
#15 0x00280253 in ?? () from /usr/lib/pgsql/plpgsql.so
#16 0x0027f1b1 in ?? () from /usr/lib/pgsql/plpgsql.so
#17 0x0027ecaf in ?? () from /usr/lib/pgsql/plpgsql.so
#18 0x002816ff in plpgsql_exec_function () from /usr/lib/pgsql/plpgsql.so
#19 0x00276028 in plpgsql_call_handler () from /usr/lib/pgsql/plpgsql.so
#20 0x08191002 in ExecMakeTableFunctionResult ()
#21 0x0819dbd4 in ?? ()
#22 0x08192584 in ExecScan ()
#23 0x0819db59 in ExecFunctionScan ()
#24 0x0818ad8f in ExecProcNode ()
#25 0x081888ab in standard_ExecutorRun ()
#26 0x0823917e in ?? ()
#27 0x0823a20b in PortalRun ()
#28 0x08235912 in ?? ()
#29 0x082367e1 in PostgresMain ()
#30 0x0820a0ea in ?? ()
#31 0x0820b112 in PostmasterMain ()
#32 0x081b5be0 in main ()

which points at this:

boolean tsp_seed(population *pop, entity *adam)
{
  int           i,s,tmp;
  int           *data;

  data = (int *)adam->chromosome[0];

  for (i=0; ilen_chromosomes; i++)
  {
    data[i] = i;
  }

  for (i=0; ilen_chromosomes; i++)
  {
    if(ids[data[i]] == source_id)
      s = i;
  }

  tmp = data[0];
  data[0] = data[s];      // this line is the one with the problem
  data[s] = tmp;

  return TRUE;
}

[Delawen]

I have also a segmentation fault on the tsp algorithm.

cat /etc/lsb-release DISTRIB_ID=Ubuntu DISTRIB_RELEASE=10.10 DISTRIB_CODENAME=maverick DISTRIB_DESCRIPTION="Ubuntu 10.10" dpkg -l | grep postgre ii postgresql 8.4.8-0ubuntu0.10.10 object-relational SQL database (supported version) ii postgresql-8.4 8.4.8-0ubuntu0.10.10 object-relational SQL database, version 8.4 server ii postgresql-8.4-pgrouting 1.05-1~maverick2 routing functionality support for PostgreSQL 8.4 ii postgresql-8.4-pgrouting-dd 1.05-1~maverick2 routing functionality support for PostgreSQL 8.4 ii postgresql-8.4-pgrouting-tsp 1.05-1~maverick2 routing functionality support for PostgreSQL 8.4 ii postgresql-8.4-postgis 1.5.1-5 geographic objects support for PostgreSQL 8.4 ii postgresql-client-8.4 8.4.8-0ubuntu0.10.10 front-end programs for PostgreSQL 8.4 ii postgresql-client-common 111 manager for multiple PostgreSQL client versions ii postgresql-common 111 PostgreSQL database-cluster manager dpkg -l | grep pgrou
ii osm2pgrouting 0.1-5 Tool to import OpenStreetMap data into a pgRouting database. ii postgresql-8.4-pgrouting 1.05-1~maverick2 routing functionality support for PostgreSQL 8.4 ii postgresql-8.4-pgrouting-dd 1.05-1~maverick2 routing functionality support for PostgreSQL 8.4 ii postgresql-8.4-pgrouting-tsp 1.05-1~maverick2 routing functionality support for PostgreSQL 8.4

Here is my log trying with a simple and stupid example: 2011-05-25 13:39:44 CEST STATEMENT: select * from tsp('select 1 as source_id, 2 as x, 3 as y', '1, 2, 3', 4); 2011-05-25 13:39:56 CEST LOG: server process (PID 14474) was terminated by signal 11: Segmentation fault 2011-05-25 13:39:56 CEST LOG: terminating any other active server processes 2011-05-25 13:39:56 CEST WARNING: terminating connection because of crash of another server process 2011-05-25 13:39:56 CEST 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. 2011-05-25 13:39:56 CEST HINT: In a moment you should be able to reconnect to the database and repeat your command. 2011-05-25 13:39:56 CEST LOG: all server processes terminated; reinitializing 2011-05-25 13:39:56 CEST LOG: database system was interrupted; last known up at 2011-05-25 13:39:19 CEST 2011-05-25 13:39:56 CEST LOG: database system was not properly shut down; automatic recovery in progress 2011-05-25 13:39:56 CEST LOG: redo starts at 0/1197648 2011-05-25 13:39:56 CEST LOG: record with zero length at 0/1387298 2011-05-25 13:39:56 CEST LOG: redo done at 0/1387268 2011-05-25 13:39:56 CEST LOG: last completed transaction was at log time 2011-05-25 13:39:56.285473+02 2011-05-25 13:39:56 CEST LOG: database system is ready to accept connections 2011-05-25 13:39:56 CEST LOG: autovacuum launcher started

[Delawen]

Looking at the code I think that the problem might be that s can be not initialized. I don't understand how does the genetic algorithm works, but probably we need a default choice in case the source_id is not on the cromosomes.

boolean tsp_seed(population *pop, entity *adam)
{
  int           i,s,tmp;
  int           *data;

  data = (int *)adam->chromosome[0];

  for (i=0; ilen_chromosomes; i++)
  {
    data[i] = i;
  }    
//Maybe s = 0 here?
  for (i=0; ilen_chromosomes; i++)
  {
    if(ids[data[i]] == source_id)
      s = i;
  }

  tmp = data[0];
  data[0] = data[s];      // this line is the one with the problem
  data[s] = tmp;

  return TRUE;
}

[Delawen]

In case someone else arrives here and needs a travelling salesman algorithm, I have written a simple script which can skip this problem. It is a brute-force travelling salesman implementation using dijkstra or shooting_star (see issue #31).

It is not very good, but can be handy for further implementations.

DROP FUNCTION IF EXISTS gofleet_tsp(TEXT, TEXT, TEXT, INTEGER);
DROP FUNCTION IF EXISTS gofleet_tsp_next(TEXT, TEXT, TEXT, INTEGER);
DROP TYPE IF EXISTS gofleet_tsp_res_table;
CREATE TYPE gofleet_tsp_res_table as (
              id BIGINT,
                          edge INTEGER,
              the_geom GEOMETRY,
                          cost DOUBLE PRECISION
);

CREATE FUNCTION gofleet_tsp_next(rtable TEXT, ptable TEXT, gid TEXT, source INTEGER)
RETURNS INTEGER AS 
$BODY$
DECLARE
    answer INTEGER;
    r RECORD;
        BEGIN
            RAISE INFO 'gofleet_tsp_next(%, %, %, %)', rtable, ptable, gid, source;  
        EXECUTE 'DROP TABLE IF EXISTS routing_next';
            EXECUTE 'CREATE TEMPORARY TABLE routing_next
            (
              id BIGSERIAL NOT NULL,
                          edge INTEGER NOT NULL,
                          cost DOUBLE PRECISION NOT NULL,
                          CONSTRAINT routing_next_pk PRIMARY KEY (id)
                        )';

        BEGIN
        FOR r IN EXECUTE 'SELECT DISTINCT id FROM ' || ptable || ' as p WHERE p.id <> ' || source ||
                ' AND NOT EXISTS (SELECT 1 FROM routing_res as re where p.id =re.edge)' LOOP
          RAISE DEBUG 'Calculado hacia %', r.id;
          BEGIN
            INSERT INTO routing_next
                (edge, "cost")
                (select r.id, sum(cost) from 
                    shortest_path_shooting_star('SELECT ' || gid || ' as id, 
                                source, 
                                target, 
                                st_length(the_geom) as cost, 
                                st_length(the_geom) as reverse_cost,
                                x1,
                                y1,
                                x2,
                                y2,
                                rule,
                                to_cost FROM ' || rtable, source, r.id :: integer, true, true));
          EXCEPTION 
                        WHEN internal_error THEN 
            RAISE WARNING 'Error calculating route from % to %', source, r.id;
          END;
          END LOOP;
        RAISE DEBUG 'Calculado para %', source;
        FOR r IN SELECT DISTINCT edge, cost FROM routing_next ORDER BY cost ASC LOOP
            RAISE DEBUG 'Resultados cost % edge %', r.cost, r.edge;
        END LOOP;
                SELECT edge INTO answer FROM routing_next WHERE edge <> -1 ORDER BY cost ASC LIMIT 1;
        RAISE INFO 'Going to EDGE %', answer;   

                EXCEPTION 
                        WHEN internal_error THEN 
                        RAISE WARNING 'Error calculating next from edge %',source;
                END;
                RETURN answer;      
        END;
$BODY$ 
LANGUAGE 'plpgsql';

--Routing table, Stops table, ID column name, ID source
--The points table contains IDs from the routing table 
--where we need to stop
--Routing table contains all the pgrouting data
CREATE FUNCTION gofleet_tsp(rtable TEXT, ptable TEXT, gid TEXT, source INTEGER)
RETURNS setof gofleet_tsp_res_table AS 
$BODY$
DECLARE
    target INTEGER;
    done INTEGER;
    max INTEGER;
    r RECORD;
        BEGIN
        RAISE INFO 'gofleet_tsp(%, %, %, %)', rtable, ptable, gid, source;
        EXECUTE 'DROP TABLE IF EXISTS routing_res';
            EXECUTE 'CREATE TEMPORARY TABLE routing_res
            (
              id BIGSERIAL NOT NULL,
                          edge INTEGER NOT NULL,
                          the_geom GEOMETRY,
                          cost DOUBLE PRECISION NOT NULL,
                          CONSTRAINT routing_res_pk PRIMARY KEY (id)
                        )';

            RAISE DEBUG 'Table routing_res created.';   
        BEGIN
        SELECT COUNT(1) INTO done FROM routing_res as re WHERE 
                    EXISTS (SELECT 1 FROM puntos p WHERE p.id = re.edge);

        SELECT COUNT(1) INTO max FROM puntos p;
        WHILE done < max LOOP
          SELECT * INTO target FROM gofleet_tsp_next(rtable, ptable, gid, source);
          INSERT INTO routing_res
                        (edge, "cost")
                        (select edge_id, cost from 
                shortest_path_shooting_star('SELECT ' || gid || ' as id, 
                                source, 
                                target, 
                                st_length(the_geom) as cost, 
                                st_length(the_geom) as reverse_cost,
                                x1,
                                y1,
                                x2,
                                y2,
                                rule,
                                to_cost FROM ' || rtable, source, target, true, true));
          SELECT target INTO source;
          SELECT COUNT(1) INTO done FROM routing_res as re WHERE 
                    EXISTS (SELECT 1 FROM puntos p WHERE p.id = re.edge);

          FOR r in SELECT * FROM routing_res LOOP
            RAISE INFO '%', r;
          END LOOP;

          END LOOP;
                EXCEPTION 
                        WHEN internal_error THEN 
                        RAISE WARNING 'Error calculating route from % to %',source, target;
                END;

                EXECUTE 'UPDATE routing_res SET the_geom = (SELECT the_geom from ways where routing_res.edge = ways.gid)';

        RETURN QUERY EXECUTE 'SELECT * FROM routing_res ORDER BY id ASC';
        END;
$BODY$ 
LANGUAGE 'plpgsql';

[jcasanov]

About the tsp_seed, it seems logical... not sure if is the right fix but it still fixes the problem. About the gofleet_tsp() function, is that doing the same as tsp_astar_directed()?

[Delawen]

I have changed the script because it failed on dijkstra and now I only use shooting_star. To use dijkstra you just have to change the function called (shortest_path...) and use vertex instead of edges.

And yes, it works more or less like a directed shooting star, but I cannot warrantee you that it will work well in all cases. The script begins on the source edge and looks for the nearest stop edge (where the salesman needs to stop). After calculating the nearest path to the nearest edge, it saves this path and goes to the next one, using the last stop edge as the new source edge.

I am using the length function as cost and reverse cost, but you can change the sql-texted-queries on the script to use cost and reverse cost columns.

A real application should look for the nearest edges of the points where the salesman needs to stop, put them on a table, and then call gofleet_tsp with the parameters described on the code.

And, again, this was a fast-written script, I wouldn't rely on it unless you yourself make some tests.

[jcasanov]

Cool! i will check it as soon as possible... thanks It could be terrific if some of the pgRouting developers look at this issue, if they don't fix it maybe they can incorporate your function (of course, if you agree and they prove it to be good)

[chinkuanyeh]

Hi Delawen,

This script seems to not compile in Postgres 8.4. Do you know how to modify it to work in Postgres 8.4 !? Thank you.

[Delawen]

I do not have a Postgres 8.4 here, what is the exact error?

Anyway, you may want to take a look at this: https://github.com/Emergya/GoFleetLSServer/tree/master/src/main/database

It contains an updated and evolutioned version of that script.

Maybe it is because of the "DROP......IF EXISTS" of the first lines? You can skip that lines if it causes you troubles.

[chinkuanyeh]

The updated script works in Postgres 8.4. Thank you.

[chinkuanyeh]

Dear Delawen,

The 'routingTable' parameter of function gls_tsp may be a subquery such as 'SELECT *,the_geom as geometry FROM roads'. But the script in 'gofleet_tsp.sql' seems not to take that into consideration. I tried to modify the script myself. Following is my modification for the script:

1. Line 42: to_cost FROM (' || routingTable || ') tmp', source, stopTable[i]:: integer, false, false) LOOP
2. Line 107: tocost FROM (' || routingTable || ') tmp', source, target, true, true) LOOP
3. Line 110: FOR g IN EXECUTE ('SELECT st_asText(geometry) as geometry FROM ('||routingTable|| ') tmp where '||r.edge||' = tmp.' || gid) LOOP

And another question. function 'gls_tsp' return 'text []' instead of 'table'. How can I convert 'text[]' to 'table' !? Thank you.

ps. sorry for my poor English

[gubuntu]

back to the original problem statement:

simply overwrite the wrapper function, replacing "tsp_test" with " ' || quote_ident(geom_table) || ' "

[Jaime2ndQuadrant]

thanks gubuntu for your comment. i did that and now i still see a crash, this is the initial backtrace:

Core was generated by `postgres: postgres db [local] SELECT '. Program terminated with signal 11, Segmentation fault.

0 0x00007f301738965d in find_tsp_solution (num=, dist=, p_ids=0x7fff89d10b40, source=,

fit=0x7fff89d10be8, err_msg=<value optimized out>) at /usr/src/debug/pgrouting-1.05/extra/tsp/src/tsp_solver.cpp:299

299 if(score < ga_get_entity_from_rank(pop,0)->fitness)

as you can see this is failing at tsp_solver line 299 which is an "if " statement and the only think i can see as a possible problem is the function ga_get_entity_from_rank() which comes from GAUL.

[Jaime2ndQuadrant]

just added a pull request with the simplest of the fixes, not sure if it's the right (tm) fix though

[dkastl]

Thanks for looking into that! Do you mean this Pull request: https://github.com/pgRouting/pgrouting/pull/84 ? (just to have a reference here)

[Jaime2ndQuadrant]

El 22/03/2013 10:36, "Daniel Kastl" notifications@github.com escribió:

Thanks for looking into that! Do you mean this Pull request: #84 ? (just to have a reference here)

exactly that. i'm not sure is THE solution but at least looks like a sensible check to avoid the crash

Jaime Casanova 2ndQuadrant: Your PostgreSQL partner

[woodbri]

Fixed this in sew-devel-2_0, leaving it tagged as 1.x

[woodbri]

Closing - Wont fix.