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

Posted by 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_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



Comments

Check out more tips and tricks in this development video: