Please start any new threads on our new site at https://forums.sqlteam.com. We've got lots of great SQL Server experts to answer whatever question you can come up with.

 All Forums
 General SQL Server Forums
 Script Library
 Traveling Salesman Problem Algorithm

Author  Topic 

mynameispaulie
Starting Member

2 Posts

Posted - 2012-03-06 : 12:49:01
I created this brute force algorithm to solve the traveling salesman problem using T-SQL in a SQL Server database class I took some time ago and I was just wondering what the experts thought of it.

I believe it gives the correct solution although I don't know if anyone has a more complex comprehensive test. I also believe it works faster than similar algorithms implemented in other languages as it uses the speed of T-SQL.

NOTE: I understand that the brute force method is not an elegant solution for solving the traveling salesman problem and is impractical for anything over 8 cities (I will post my times) but the assignment was to create a brute force algorithm using T-SQL.

I received an A+ for my project but I still wondered what the real experts thought. I am fully prepared to get ripped to shreads. :-]




---Create tables
drop table ROUTES
go
drop table CITIES
go

create table CITIES (
NAME varchar(30) primary key
)
go

create table ROUTES (
FROM_CITY varchar(30) references CITIES,
TO_CITY varchar(30) references CITIES,
MILES float not null,
primary key (from_city, to_city)
)
go


---Create view to show all routes, because it is an undirected graph
drop view ALL_ROUTES
go
create view ALL_ROUTES (FROM_CITY, TO_CITY, MILES) as
select FROM_CITY, TO_CITY, MILES from ROUTES
union
select TO_CITY, FROM_CITY, MILES from ROUTES
go


---Procedure to rotate values in #array to create all permutations of the possible paths
--- using all cities except the startCity
drop procedure rotate
go
create procedure rotate @count int
as
---Declare temp variable
declare @temp varchar(30), @i int
---Save first value
set @temp = (select NAME from #array where id = 1)
set @i = 0

---Shift all values to the left
while (@i < @count) begin
update #array set ID = @i where ID = @i + 1
set @i = @i + 1
end

---Add temp value to the end
update #array set ID = @count where ID = 0
go


---Procedure to test and save permutation if it is a good route that exists
drop procedure savePerm
go
create procedure savePerm @count int, @startCity varchar(30)
as
---Allow for @startCity at beginning of route
set @count = @count + 1
---Declare and initialize needed variables
declare @i int, @value varchar(1000), @prevCity varchar(30),
@nextCity varchar(30), @totalMiles int, @currentMiles int, @goodRoute int, @numRoutes int
set @i = 1
set @value = @startCity
set @prevCity = @startCity
set @nextCity = (select NAME from #array where ID = 1)
set @totalMiles = 0
set @currentMiles = 0
set @goodRoute = 1

---Loop through permutation array
while (@i < @count) begin
set @i = @i + 1
---See if such a path exists in the routes table
set @numRoutes = (select COUNT(*) from ALL_ROUTES where FROM_CITY = @prevCity and TO_CITY = @nextCity)
---If a path exists
if @numRoutes > 0 begin
---Get the number of miles and add to total miles
set @currentMiles = (select MILES from ALL_ROUTES where FROM_CITY = @prevCity and TO_CITY = @nextCity)
set @totalMiles = @totalMiles + @currentMiles
---Store good route
set @value = @value + '->' + @nextCity
---Get next city in permutation array
set @prevCity = @nextCity
set @nextCity = (select NAME from #array where ID = @i)
end
---If no path exists
else begin
---This route is no good, set the exit condition to exit the loop
set @goodRoute = 0
set @i = @count
end
end

---One more time to add @startCity to end of route
set @numRoutes = (select COUNT(*) from ALL_ROUTES where FROM_CITY = @prevCity and TO_CITY = @startCity)
if @numRoutes > 0 begin
set @currentMiles = (select MILES from ALL_ROUTES where FROM_CITY = @prevCity and TO_CITY = @startCity)
set @totalMiles = @totalMiles + @currentMiles
set @value = @value + '->' + @startCity
end
else begin
set @goodRoute = 0
end

---If got this far and route is good, save to perms table
if @goodRoute = 1 begin
insert into #perms values(@value, @totalMiles)
end
go


---Recursive procedure to create all possible permutations of the possible paths
--- using all cities except the startCity
drop procedure permute
go
create procedure permute @size int, @n int, @startCity varchar(30), @val1 varchar(30), @val2 varchar(30)
as
---Declare and initialize neede variables
declare @i int, @permuteVar int, @rotateVar int, @val1pos int, @val2pos int, @max int
set @i = @size - @n

---If a permutation is ready for checking call savePerm
if @size = @n begin
---Limit to half of permutations,
--- only care about routes where arbitrary city 1 is before arbitrary city 2
set @val1pos = (select ID from #array where NAME = @val1)
set @val2pos = (select ID from #array where NAME = @val2)
if (@val1pos < @val2pos) begin
exec savePerm @size, @startCity
end
end
else begin
---Recursively call itself and then rotate values in array to generate all permutations
while (@i > 0) begin
set @permuteVar = @n + 1
exec permute @size, @permuteVar, @startCity, @val1, @val2
set @rotateVar = @size - @n
exec rotate @rotateVar
set @i = @i - 1
end
end
go


---Main procedure to get answer for TSP route
drop procedure getTSPRoute
go
create procedure getTSPRoute @startCity varchar(30)
as
---Create array of cities,
--- needs AUTO_ID and ID because rotate function wont work with IDENTITY column
create table #array (AUTO_ID int identity, ID int, NAME varchar(30))
insert into #array select 0, NAME FROM cities where NAME <> @startCity
update #array set ID = AUTO_ID

---Create table to store good permutations
create table #perms (ROUTE_PATH varchar(1000), MILES int)

---Get 2 arbitrary cities, so that only routes where city 1 is before city 2 will be looked at
declare @val1 varchar(30), @val2 varchar(30), @size int
set @val1 = (select top 1 NAME from CITIES where NAME <> @startCity order by name)
set @val2 = (select top 1 NAME from CITIES where NAME <> @startCity order by name desc)

---Get size of city array for number of cities
set @size = (select COUNT(*) from #array)

---Call recursive permute function to generate all possible permutations of the possible paths
--- using all cities except the startCity
exec permute @size, 0, @startCity, @val1, @val2

---When done select the shortest route from the perms table of good routes
select ROUTE_PATH, MIN(MILES) as MILES from #perms group by ROUTE_PATH having MIN(MILES) = (select MIN(miles) from #perms)
go





---**************************************************************************************************************************

--- Test attempt 1
--- 5 cities
--- Running time: 2 seconds

delete from routes
delete from cities
insert into cities values ('A')
insert into cities values ('B')
insert into cities values ('C')
insert into cities values ('D')
insert into cities values ('E')
insert into routes values ('A', 'B', 5)
insert into routes values ('A', 'C', 20)
insert into routes values ('A', 'D', 28.28)
insert into routes values ('A', 'E', 20)
insert into routes values ('B', 'C', 15)
insert into routes values ('B', 'D', 25)
insert into routes values ('B', 'E', 20.62)
insert into routes values ('C', 'D', 20)
insert into routes values ('C', 'E', 28.28)
insert into routes values ('D', 'E', 20)
go

exec getTSPRoute 'A'

---**************************************************************************************************************************

--- Test attempt 2
--- 8 cities
--- Running time: 5 seconds

delete from routes
delete from cities
insert into cities values ('A')
insert into cities values ('B')
insert into cities values ('C')
insert into cities values ('D')
insert into cities values ('E')
insert into cities values ('F')
insert into cities values ('G')
insert into cities values ('H')
insert into routes values ('A', 'B', 200)
insert into routes values ('B', 'C', 300)
insert into routes values ('C', 'D', 200)
insert into routes values ('D', 'E', 300)
insert into routes values ('E', 'F', 100)
insert into routes values ('F', 'G', 200)
insert into routes values ('G', 'H', 250)
insert into routes values ('H', 'A', 250)
insert into routes values ('D', 'F', 200)
insert into routes values ('E', 'G', 250)
insert into routes values ('A', 'E', 50)
insert into routes values ('B', 'E', 50)
go

exec getTSPRoute 'A'

---**************************************************************************************************************************

--- Test attempt 3
--- 9 cities
--- Running time: 41 seconds

delete from routes
delete from cities
insert into cities values ('New York')
insert into cities values ('Washington')
insert into cities values ('Chicago')
insert into cities values ('St. Louis')
insert into cities values ('Dallas')
insert into cities values ('Denver')
insert into cities values ('Phoenix')
insert into cities values ('Los Angeles')
insert into cities values ('San Francisco')
insert into routes values ('New York', 'Washington', 200)
insert into routes values ('New York', 'Chicago', 700)
insert into routes values ('St. Louis', 'Washington', 700)
insert into routes values ('St. Louis', 'Chicago', 250)
insert into routes values ('St. Louis', 'Dallas', 550)
insert into routes values ('St. Louis', 'Denver', 800)
insert into routes values ('Chicago', 'Denver', 900)
insert into routes values ('San Francisco', 'Denver', 950)
insert into routes values ('San Francisco', 'Los Angeles', 350)
insert into routes values ('Phoenix', 'Los Angeles', 350)
insert into routes values ('Phoenix', 'Dallas', 900)
go

exec getTSPRoute 'New York'

---**************************************************************************************************************************

--- Test attempt 4
--- 10 cities
--- Running time: 6 minutes 34 seconds

delete from routes
delete from cities
insert into cities values ('New York')
insert into cities values ('Washington')
insert into cities values ('Miami')
insert into cities values ('Chicago')
insert into cities values ('St. Louis')
insert into cities values ('Dallas')
insert into cities values ('Denver')
insert into cities values ('Phoenix')
insert into cities values ('Los Angeles')
insert into cities values ('San Francisco')
insert into routes values ('New York', 'Washington', 200)
insert into routes values ('New York', 'Chicago', 700)
insert into routes values ('Miami', 'Washington', 900)
insert into routes values ('St. Louis', 'Washington', 700)
insert into routes values ('St. Louis', 'Miami', 1050)
insert into routes values ('St. Louis', 'Chicago', 250)
insert into routes values ('St. Louis', 'Dallas', 550)
insert into routes values ('St. Louis', 'Denver', 800)
insert into routes values ('Chicago', 'Denver', 900)
insert into routes values ('San Francisco', 'Denver', 950)
insert into routes values ('San Francisco', 'Los Angeles', 350)
insert into routes values ('Phoenix', 'Los Angeles', 350)
insert into routes values ('Phoenix', 'Dallas', 900)
insert into routes values ('Miami', 'Dallas', 1100)
go

exec getTSPRoute 'New York'

---**************************************************************************************************************************

--- Test attempt 5
--- 11 cities
--- Running time: 1 hr 30 mins 43 seconds

delete from routes
delete from cities
insert into cities values ('New York')
insert into cities values ('Washington')
insert into cities values ('Miami')
insert into cities values ('Chicago')
insert into cities values ('St. Louis')
insert into cities values ('Dallas')
insert into cities values ('Denver')
insert into cities values ('Phoenix')
insert into cities values ('Los Angeles')
insert into cities values ('San Francisco')
insert into cities values ('Seattle')
insert into routes values ('New York', 'Washington', 200)
insert into routes values ('New York', 'Chicago', 700)
insert into routes values ('Miami', 'Washington', 900)
insert into routes values ('St. Louis', 'Washington', 700)
insert into routes values ('St. Louis', 'Miami', 1050)
insert into routes values ('St. Louis', 'Chicago', 250)
insert into routes values ('St. Louis', 'Dallas', 550)
insert into routes values ('St. Louis', 'Denver', 800)
insert into routes values ('Chicago', 'Denver', 900)
insert into routes values ('Seattle', 'Denver', 1000)
insert into routes values ('San Francisco', 'Denver', 950)
insert into routes values ('San Francisco', 'Seattle', 700)
insert into routes values ('San Francisco', 'Los Angeles', 350)
insert into routes values ('Phoenix', 'Los Angeles', 350)
insert into routes values ('Phoenix', 'Dallas', 900)
insert into routes values ('Miami', 'Dallas', 1100)
go

exec getTSPRoute 'New York'



Thanks for taking the time to look at it. Enjoy. :-]

tkizer
Almighty SQL Goddess

38200 Posts

Posted - 2012-03-06 : 12:58:38
Your code looks like T-SQL and not PL/SQL. Are you sure this was for Oracle and not Microsoft SQL Server? It makes a difference here since SQLTeam.com is for MSSQL.

Tara Kizer
Microsoft MVP for Windows Server System - SQL Server
http://weblogs.sqlteam.com/tarad/

Subscribe to my blog
Go to Top of Page

mynameispaulie
Starting Member

2 Posts

Posted - 2012-03-06 : 13:13:47
quote:
Originally posted by tkizer

Your code looks like T-SQL and not PL/SQL. Are you sure this was for Oracle and not Microsoft SQL Server? It makes a difference here since SQLTeam.com is for MSSQL.

Tara Kizer
Microsoft MVP for Windows Server System - SQL Server
http://weblogs.sqlteam.com/tarad/

Subscribe to my blog




My apologies. It appears I have the incorrect terminology. My code was written for and ran in SQL server. So I guess it is T-SQL and not PL/SQL. I have updated the post. I learned something already! :-]
Go to Top of Page

AnthonyNedu
Starting Member

2 Posts

Posted - 2014-10-23 : 05:35:35
Mynameispaulie, please can i contact you for details with the travel salesman problem I am faced with such question now.
Go to Top of Page

SwePeso
Patron Saint of Lost Yaks

30421 Posts

Posted - 2014-10-26 : 06:51:18
The Travelling Salesman problem is an np-complete problem and has to be solve with "brute force".


Microsoft SQL Server MVP, MCT, MCSE, MCSA, MCP, MCITP, MCTS, MCDBA
Go to Top of Page

SwePeso
Patron Saint of Lost Yaks

30421 Posts

Posted - 2014-10-26 : 07:17:02
11 cities in 150 ms
SET NOCOUNT ON;

-- Prepare sample data
CREATE TABLE #Nodes
(
Name VARCHAR(30) PRIMARY KEY CLUSTERED
);


INSERT #Nodes
(
Name
)
VALUES ('New York'),
('Washington'),
('Miami'),
('Chicago'),
('St. Louis'),
('Dallas'),
('Denver'),
('Phoenix'),
('Los Angeles'),
('San Francisco'),
('Seattle');

CREATE TABLE #Routes
(
FromNode VARCHAR(30) NOT NULL REFERENCES #Nodes(Name),
ToNode VARCHAR(30) NOT NULL REFERENCES #Nodes(Name),
Distance DECIMAL(28, 12) NOT NULL,
PRIMARY KEY CLUSTERED
(
FromNode,
ToNode
)
);

INSERT #Routes
(
FromNode,
ToNode,
Distance
)
OUTPUT inserted.ToNode AS FromNode,
inserted.FromNode AS ToNode,
inserted.Distance
INTO #Routes
(
FromNode,
ToNode,
Distance
)
VALUES ('New York', 'Washington', 200),
('New York', 'Chicago', 700),
('Miami', 'Washington', 900),
('St. Louis', 'Washington', 700),
('St. Louis', 'Miami', 1050),
('St. Louis', 'Chicago', 250),
('St. Louis', 'Dallas', 550),
('St. Louis', 'Denver', 800),
('Chicago', 'Denver', 900),
('Seattle', 'Denver', 1000),
('San Francisco', 'Denver', 950),
('San Francisco', 'Seattle', 700),
('San Francisco', 'Los Angeles', 350),
('Phoenix', 'Los Angeles', 350),
('Phoenix', 'Dallas', 900),
('Miami', 'Dallas', 1100);

-- Solution
DECLARE @Nodes INT = (SELECT COUNT(*) FROM #Nodes);

WITH cteMap(Nodes, LastNode, Distance, NodeMap)
AS (
SELECT 2 AS Nodes,
ToNode,
Distance,
CAST('\' + FromNode + '\' + ToNode + '\' AS VARCHAR(MAX)) AS NodeMap
FROM #Routes

UNION ALL

SELECT m.Nodes + 1 AS Nodes,
r.ToNode AS LastNode,
CAST(m.Distance + r.Distance AS DECIMAL(28, 12)) AS Distance,
CAST(m.NodeMap + r.ToNode + '\' AS VARCHAR(MAX)) AS NodeMap
FROM cteMap AS m
INNER JOIN #Routes AS r ON r.FromNode = m.LastNode
WHERE m.NodeMap NOT LIKE '\%' + r.ToNode + '%\'
)
SELECT TOP(1)
WITH TIES Distance,
NodeMap
FROM cteMap
WHERE Nodes = @Nodes
ORDER BY Distance DESC
OPTION (MAXRECURSION 0);

-- Clean up
DROP TABLE #Routes,
#Nodes;



Microsoft SQL Server MVP, MCT, MCSE, MCSA, MCP, MCITP, MCTS, MCDBA
Go to Top of Page

AnthonyNedu
Starting Member

2 Posts

Posted - 2014-10-26 : 19:08:35
Swepeso, please can you give me your email so that I can contact you concerning a travel salesman problem, or you can contact me on tzamanda@yahoo.com
Thanks
Go to Top of Page

tkizer
Almighty SQL Goddess

38200 Posts

Posted - 2014-10-27 : 11:47:05
quote:
Originally posted by AnthonyNedu

Swepeso, please can you give me your email so that I can contact you concerning a travel salesman problem, or you can contact me on tzamanda@yahoo.com
Thanks



Just start a new thread in one of our forums.

Tara Kizer
SQL Server MVP since 2007
http://weblogs.sqlteam.com/tarad/
Go to Top of Page
   

- Advertisement -