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

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_add             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_add := '';                             

            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_add := ' + ';

                              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