Travelling Salesman Problem

Discussion:

(too old to reply)

Robert Kozeluh

2004-10-28 17:08:02 UTC

Hey guys, I could really use some help on a problem I have. I have
been stuggling with it in Matlab for many hours now to no avail. Here
it is:

Question 5 Traveling salesman Location of 6 cities around UOIT is
given as follows. City X- coordinates Y-coordinates

Oshawa (UOIT) 0 0
Toronto -50 -10
Barrie -49 100
Ottawa 100 300
Brampton -100 5
Hamilton 130 -8

a. Locate these cities in a graph and use unique symbols to
distinguish them.
b. Using straight distance between cities, find out what is the best
sequence to visit all the cities with less fuel consumption and show
the best sequence on the previous graph.
c. Find what is the least amount of money in dollars the sales person
is going pay during his trip. (01 L of gas = 83 cents) and the time
he will be behind the wheel, assuming that sales person drives at a
constant speed of 110 Km/h.

If anyone can help me I would be very grateful! TIA!!!

Ken Davis

2004-10-28 18:28:28 UTC

Permalink

Post by Robert Kozeluh
Hey guys, I could really use some help on a problem I have. I have
been stuggling with it in Matlab for many hours now to no avail. Here
Question 5 - Traveling salesman Location of 6 cities around UOIT is
given as follows. City X- coordinates Y-coordinates
Oshawa (UOIT) 0 0
Toronto -50 -10
Barrie -49 100
Ottawa 100 300
Brampton -100 5
Hamilton 130 -8
a. Locate these cities in a graph and use unique symbols to
distinguish them.
b. Using straight distance between cities, find out what is the best
sequence to visit all the cities with less fuel consumption and show
the best sequence on the previous graph.
c. Find what is the least amount of money in dollars the sales person
is going pay during his trip. (01 L of gas = 83 cents) and the time
he will be behind the wheel, assuming that sales person drives at a
constant speed of 110 Km/h.
If anyone can help me I would be very grateful! TIA!!!

You have offered no evidence that you have been struggling. Please show us
some evidence--some code, some thoughts, etc.--and we'll be glad to help you
get unstuck.

Robert Kozeluh

2004-10-30 15:32:21 UTC

Permalink

Hi there Ken, I realize that it's difficult to feel sympathy for
someone that has not shown initiative, but I can assure you I have
already given myself high blood pressure over this Matlab assignment.
I didn't post any of my code because I am ony able to do the very
first part of this problem, which is plotting the points and
labelling them. I am terrible at Matlab and programming in general.
Anyways, here is what I have so far along with the question again:

Question 5 Traveling salesman Location of 6 cities around UOIT is
given as follows. City X- coordinates Y-coordinates

Oshawa (UOIT) 0 0
Toronto -50 -10
Barrie -49 100
Ottawa 100 300
Brampton -100 5
Hamilton 130 -8

a. Locate these cities in a graph and use unique symbols to
distinguish them.
b. Using straight distance between cities, find out what is the best
sequence to visit all the cities with less fuel consumption and show
the best sequence on the previous graph.
c. Find what is the least amount of money in dollars the sales person

is going pay during his trip. (01 L of gas = 83 cents) and the time
he will be behind the wheel, assuming that sales person drives at a
constant speed of 110 Km/h.

% ENGR 2140 Assignment #4
% Question #5 - Travelling Salesman
clc
clear

% Coordinates:
Oshawa=[0,0];
Toronto=[-50,-10];
Barrie=[-49,100];
Ottawa=[100,300];
Brampton=[-100,5];
Hamilton=[-130,-8];
Data=[Oshawa; Toronto; Barrie; Ottawa; Brampton; Hamilton];

scatterplot(Data), axis([-220, 170, -50, 330]), title('Travel
Map'),...
xlabel('Distance (km)'), ylabel('Distance (km)'),...
text(5,15,'Oshawa')
text(-75,5,'Toronto')
text(-70,115,'Barrie')
text(75,315,'Ottawa')
text(-155,20,'Brampton')
text(-200,0,'Hamilton')

counter1=1;
counter2=1;

for one=1:6
for two=1:6
if two~=one

dist(counter1,counter2)=abs(sqrt((Data(one,1)-Data(two,1))^2+(Data(one
,2)-Data(two,2))^2))
end
counter1=counter1+1;
end
end

%counter=1;
%tripdist=0;

%for n=1:6
% if n<=5
%
dist(n)=abs(sqrt((Data(n,1)-Data(n+1,1))^2+(Data(n,2)-Data(n+1,2))^2))

% tripdist=tripdist+dist(n);
% end
%end
%disthome=abs(sqrt((Data(1,1)-Data(n,1))^2+(Data(1,2)-Data(n,2))^2));
%totaldist=tripdist+disthome

As you can see, it's really not much. I know that a vector must be
made for each trip combination, and that must vector must be stored,
converted to a scalar value (total trip distance) and compared to
the next combination route; if smaller it would be kept, if larger it
would be replaced by the shorter (better) route. However, I have NO
clue how to do this in Matlab. Any help you could offer me would be
great.....I am not one to give up, but I have probably spent more
than twelve hours with this question in Matlab, scouring the net for
similar problems and searching my textbook for help. I only need help
with part b. after that I can struggle my way further. TIA!

Post by Robert Kozeluh
Hey guys, I could really use some help on a problem I have. I have
been stuggling with it in Matlab for many hours now to no avail. Here
Question 5 Traveling salesman Location of 6 cities around UOIT is
given as follows. City X- coordinates Y-coordinates
Oshawa (UOIT) 0 0
Toronto -50 -10
Barrie -49 100
Ottawa 100 300
Brampton -100 5
Hamilton 130 -8
a. Locate these cities in a graph and use unique symbols to
distinguish them.
b. Using straight distance between cities, find out what is the best
sequence to visit all the cities with less fuel consumption and show
the best sequence on the previous graph.
c. Find what is the least amount of money in dollars the sales
person
is going pay during his trip. (01 L of gas = 83 cents) and the time
he will be behind the wheel, assuming that sales person drives at a
constant speed of 110 Km/h.
If anyone can help me I would be very grateful! TIA!!!

Ken Davis

2004-10-30 18:40:54 UTC

Permalink

Post by Robert Kozeluh
Hi there Ken, I realize that it's difficult to feel sympathy for
someone that has not shown initiative, but I can assure you I have
already given myself high blood pressure over this Matlab assignment.
I didn't post any of my code because I am ony able to do the very
first part of this problem, which is plotting the points and
labelling them. I am terrible at Matlab and programming in general.
Question 5 - Traveling salesman Location of 6 cities around UOIT is
given as follows. City X- coordinates Y-coordinates
Oshawa (UOIT) 0 0
Toronto -50 -10
Barrie -49 100
Ottawa 100 300
Brampton -100 5
Hamilton 130 -8
a. Locate these cities in a graph and use unique symbols to
distinguish them.
b. Using straight distance between cities, find out what is the best
sequence to visit all the cities with less fuel consumption and show
the best sequence on the previous graph.
c. Find what is the least amount of money in dollars the sales person
is going pay during his trip. (01 L of gas = 83 cents) and the time
he will be behind the wheel, assuming that sales person drives at a
constant speed of 110 Km/h.
% ENGR 2140 Assignment #4
% Question #5 - Travelling Salesman
clc
clear
Oshawa=[0,0];
Toronto=[-50,-10];
Barrie=[-49,100];
Ottawa=[100,300];
Brampton=[-100,5];
Hamilton=[-130,-8];
Data=[Oshawa; Toronto; Barrie; Ottawa; Brampton; Hamilton];
scatterplot(Data), axis([-220, 170, -50, 330]), title('Travel
Map'),...
xlabel('Distance (km)'), ylabel('Distance (km)'),...
text(5,15,'Oshawa')
text(-75,5,'Toronto')
text(-70,115,'Barrie')
text(75,315,'Ottawa')
text(-155,20,'Brampton')
text(-200,0,'Hamilton')
counter1=1;
counter2=1;
for one=1:6
for two=1:6
if two~=one
dist(counter1,counter2)=abs(sqrt((Data(one,1)-Data(two,1))^2+(Data(one
,2)-Data(two,2))^2))
end
counter1=counter1+1;
end
end
%counter=1;
%tripdist=0;
%for n=1:6
% if n<=5
%
dist(n)=abs(sqrt((Data(n,1)-Data(n+1,1))^2+(Data(n,2)-Data(n+1,2))^2))
% tripdist=tripdist+dist(n);
% end
%end
%disthome=abs(sqrt((Data(1,1)-Data(n,1))^2+(Data(1,2)-Data(n,2))^2));
%totaldist=tripdist+disthome
As you can see, it's really not much. I know that a vector must be
made for each trip combination, and that must vector must be stored,
converted to a scalar value (total trip distance) and compared to
the next combination route; if smaller it would be kept, if larger it
would be replaced by the shorter (better) route. However, I have NO
clue how to do this in Matlab. Any help you could offer me would be
great.....I am not one to give up, but I have probably spent more
than twelve hours with this question in Matlab, scouring the net for
similar problems and searching my textbook for help. I only need help
with part b. after that I can struggle my way further. TIA!

First, just to clarify... My guess is that most people who respond to posts
here do so because it interests/pleases them to do so. Sympathy, or for that
matter, urgency, play little or no part. I think there is a feeling that we
don't want to just do other people's homework. For me, at least, that is
just contributing to deception and dishonesty... which I do not want to do.
That is the reason I like to see some evidence of effort.

Now... back to your problem...

There is probably a whole literature on this in the fields of algorithms or
graph theory, but for a simple (small) problem like this, I'd be inclined to
use brute force. This means enumerating all possible paths. I'm not certain,
but I suspect that it is only necessary to consider paths which visit each
city once so there are a total of n! (= 6! = 720) paths. They are indeed all
the permutations of the sequence, {1, 2, 3, 4, 5, 6}. Look at "help perms"
to generate that list.

Frequent Poster

2004-10-30 18:48:25 UTC

Permalink

Post by Ken Davis
First, just to clarify... My guess is that most people who respond to posts
here do so because it interests/pleases them to do so. Sympathy, or for that
matter, urgency, play little or no part. I think there is a feeling that we
don't want to just do other people's homework. For me, at least, that is
just contributing to deception and dishonesty... which I do not want to do.
That is the reason I like to see some evidence of effort.
Now... back to your problem...
There is probably a whole literature on this in the fields of
algorithms or
graph theory, but for a simple (small) problem like this, I'd be inclined to
use brute force. This means enumerating all possible paths. I'm not certain,
but I suspect that it is only necessary to consider paths which visit each
city once so there are a total of n! (= 6! = 720) paths. They are indeed all
the permutations of the sequence, {1, 2, 3, 4, 5, 6}. Look at "help perms"
to generate that list.

Ken (who's advice and experience is second to none, and always worth
reading) is about to blow! Stand back or be covered in blood and
guts. Joking aside, I'm always always impressed by the (trademark)
two-part answers:

1) Sod off!
2) Here's some help.

- fp

Marcus M. Edvall

2004-10-30 18:49:19 UTC

Permalink

Hi Robert,

Look in TOMLAB. There is a function in LDO (free) that will take care
of this.

See 'help salesman'

Best wishes, Marcus
Tomlab Optimization Inc.
<http://tomlab.biz>

frequent poster

2004-10-30 18:56:54 UTC

Permalink

Post by Marcus M. Edvall
Look in TOMLAB.

What is is with you tomlab/femlab/arselab people? CSSM is a sharing
place, not a market place. We (mainly sad people) are proud of our
(sometimes) clever answers to questions, not looking to profit from
them. Some of us waste hours of our own time trying to solve other
people's problems for them - for fun not money. Go advertise
somewhere else!

- Steve (yeah, me!)

Robert Kozeluh

2004-10-30 21:17:04 UTC

Permalink

Ken, thank you so much for your help. The perm() function was what I
was looking for. You must understand the frustration one goes through
when they are unaware of such functions.....basically what I was
trying to do is write this function myself....and from my very
limited skills, this was a futile effort!.....Thanks again!