# Almost TSP!! : Travelling Salesman Problem Solution through PL/SQL

Posted on in Blogs

Hi!!!!

/* PROBLEM STATEMENT

Here, the salesman is given the distance chart by his/her manager based on which

(s)he has to cover all the cities in the distance chart but ensure that (s)he

covers the MINIMUM DISTANCE. For better text, read http://en.wikipedia.org/wiki/Travelling_salesman_problem.

*/

/

drop table salesmans_scrambled_dist_chart;

create table salesmans_scrambled_dist_chart

(

source      varchar2(5),

destination varchar2(5),

distance    number(5,0)

);

truncate table salesmans_scrambled_dist_chart;

insert into salesmans_scrambled_dist_chart values ('-AGR-','-DEL-',250);

insert into salesmans_scrambled_dist_chart values ('-AGR-','-PTN-',700);

insert into salesmans_scrambled_dist_chart values ('-AGR-','-GYA-',800);

insert into salesmans_scrambled_dist_chart values ('-AGR-','-ALD-',300);

insert into salesmans_scrambled_dist_chart values ('-GYA-','-ALD-',500);

insert into salesmans_scrambled_dist_chart values ('-ALD-','-PTN-',333);

insert into salesmans_scrambled_dist_chart values ('-ALD-','-DEL-',601);

insert into salesmans_scrambled_dist_chart values ('-GYA-','-PTN-',100);

insert into salesmans_scrambled_dist_chart values ('-PTN-','-DEL-',1050);

insert into salesmans_scrambled_dist_chart values ('-DEL-','-GYA-',1100);

commit;

create or replace view v_distance_chart as

select distinct

source,

destination,

distance

FROM

(

SELECT

source,

destination,

distance

FROM

salesmans_scrambled_dist_chart

UNION ALL

SELECT

destination AS source,

source  AS destination,

distance

FROM

salesmans_scrambled_dist_chart);

/

create or replace view v_all_cities as

select

city,

rownum as sno

from

(select distinct

source as city

from

v_distance_chart);

/

drop table all_cities;

create table all_cities

(

sno   number(2,0),

city  varchar2(5)

);

truncate table all_cities;

insert into all_cities(sno, city) select sno, city from v_all_cities;

commit;

/

create or replace package pkg_salesman_scramble is

procedure scramble_cities;

function get_sql_city_sequence return varchar2;

end pkg_salesman_scramble;

/

create or replace package body pkg_salesman_scramble is

procedure scramble_cities is

v_retval    number(2,0);

begin

dbms_output.put_line('uninplemented!!!');

end scramble_cities;

function get_sql_city_sequence return varchar2 is

v_sql_stmt        varchar2(4000);

v_sql_col1        varchar2(1000);

v_sql_col2        varchar2(1000);

v_sql_tbl         varchar2(500);

v_sql_where       varchar2(1500);

v_no_of_elements  number(2,0);

v_index                 number(2,0);

v_inner_index           number(2,0);

v_bool                  number(1,0);

v_pipe                  varchar2(4);

v_comma                 varchar2(3);

v_and             varchar2(5);

begin

v_bool := 0;

select count(*) into v_no_of_elements from all_cities;

v_pipe := '';

v_comma := '';

v_and := '';

for v_index in 1..v_no_of_elements

loop

--if v_index = v_no_of_elements

--then

--    v_index_X := 1;

--else

--    v_index_X := v_index + 1;

--end if;

v_sql_col1 := v_sql_col1 || v_pipe || 'nvl(t' || v_index || '.CITY,'''')';

if v_index > 1 then

v_sql_col2 := v_sql_col2 || v_add || 'distance_between_cities(t' ||  v_index || '.city, t' || to_char(v_index - 1) || '.city)';

else

v_sql_col2 := 0;

end if;

v_sql_tbl := v_sql_tbl || v_comma || 'all_cities t' || v_index;

v_inner_index := v_index + 1;

for v_inner_index in v_index + 1 .. v_no_of_elements

loop

if v_bool = 1 then

v_pipe := ' || ';

v_comma := ' , ';

v_and := ' AND ';

end if;

v_sql_where :=  v_sql_where || v_and || ' t'|| v_index ||'.SNO != t'|| v_inner_index ||'.SNO ';

v_bool := 1;

end loop;

end loop;

--v_sql_stmt := 'select CITY as combinations from scrambler_2011 where sno != 0 union all ';

v_sql_stmt :=  v_sql_stmt ||' select ' || v_sql_col1 ||' as route, ' || v_sql_col2 ||' as distance_to_be_covered FROM ' || v_sql_tbl || ' WHERE ' || v_sql_where || ' order by distance_to_be_covered';

return(v_sql_stmt);

end get_sql_city_sequence;

end pkg_salesman_scramble;

/

create or replace function distance_between_cities( v_city1 varchar, v_city2 varchar) return number is

v_retval    number(5,0);

begin

select

distance into v_retval

from v_distance_chart

where

source = v_city1

and   destination = v_city2;

return v_retval;

end distance_between_cities;

/

-- select pkg_salesman_scramble.get_sql_city_sequence() from dual; -- pick the output and execute the dynamic sql, say str_dyn_sql so generated.

-- execute str_dyn_sql