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

Our new SQL Server Forums are live! Come on over! We've restricted the ability to create new threads on these forums.

SQL Server Forums
Profile | Active Topics | Members | Search | Forum FAQ
Username:
Password:
Save Password
Forgot your Password?

 All Forums
 General SQL Server Forums
 Script Library
 Traveling Salesman Problem Algorithm
 Reply to Topic
 Printer Friendly
Author Previous Topic Topic Next Topic  

mynameispaulie
Starting Member

2 Posts

Posted - 03/06/2012 :  12:49:01  Show Profile  Reply with Quote
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. :-]

Edited by - mynameispaulie on 03/06/2012 13:15:48

tkizer
Almighty SQL Goddess

USA
38200 Posts

Posted - 03/06/2012 :  12:58:38  Show Profile  Visit tkizer's Homepage  Reply with Quote
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 - 03/06/2012 :  13:13:47  Show Profile  Reply with Quote
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! :-]

Edited by - mynameispaulie on 03/06/2012 13:16:48
Go to Top of Page

AnthonyNedu
Starting Member

USA
2 Posts

Posted - 10/23/2014 :  05:35:35  Show Profile  Reply with Quote
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

Sweden
30421 Posts

Posted - 10/26/2014 :  06:51:18  Show Profile  Visit SwePeso's Homepage  Reply with Quote
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

Sweden
30421 Posts

Posted - 10/26/2014 :  07:17:02  Show Profile  Visit SwePeso's Homepage  Reply with Quote
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

USA
2 Posts

Posted - 10/26/2014 :  19:08:35  Show Profile  Reply with Quote
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

USA
38200 Posts

Posted - 10/27/2014 :  11:47:05  Show Profile  Visit tkizer's Homepage  Reply with Quote
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
  Previous Topic Topic Next Topic  
 Reply to Topic
 Printer Friendly
Jump To:
SQL Server Forums © 2000-2009 SQLTeam Publishing, LLC Go To Top Of Page
This page was generated in 0.06 seconds. Powered By: Snitz Forums 2000