question about traveling salesman problem

FAQ

Memberlist

Usergroups

Profile

Preferences

Forum index » Science and Technology » Math » Combinatorics

question about traveling salesman problem

Page 1 of 1 [5 Posts]

View previous topic :: View next topic

Author

Message

Joe
science forum beginner

Joined: 25 Jun 2005
Posts: 22

Posted: Sat Sep 24, 2005 3:53 pm Post subject: Note

question about traveling salesman problem

Hi to the group,

I have been reading (on the internet) about the traveling salesman problem.
I have a route that I have to run every day and make about 20 to 30 stops
(it varies from week to week). I was trying to figure out how to minimize my
fuel expenses in order to run this route.

I have a gps receiver with which I can record different routes and save the
routes, and the destinations (waypoints) and then transfer them to a map. I
am just not sure where to start with optimizing the solution.
I have some background in Math, Physics, and statistics, but I guess this is
a problem in combinatorial optimization, which I know next to nothing about.
I can do some coding (in compiled BASIC). I have also thought of using the
gps coordinates (not lat/lon, but UTM) and try to create something of a 2
dimensional graph to plot with, but I am just not sure how to start. The
destinations can change week to week also, so I would probably have to re
run this algorithm at least once a week. I am looking for the optimum, or
close to the optimum solution which will minimize my mileage (and, hence my
fuel expenses). Anyone know where I should start?

Thanks,
Joe

Proginoskes
science forum Guru

Joined: 29 Apr 2005
Posts: 2593

Posted: Tue Sep 27, 2005 5:33 am Post subject: Note

Re: question about traveling salesman problem

Joe wrote:

Quote:

(1) You need to go out and find some "code" that will input all of this
data and solve the TSP problem. (You probably haven't got enough
experience to code up the algorithm; I certainly don't. The only people
who have it are the ones who design algorithms and implement them for a
living.) Since you're using distances here, you're looking for some
code that will solve the "Euclidean" version of the problem, which was
discovered a few decades ago. (You don't need the full version of TSP,
because the TSP has no assumption about distances built into it.)
Google is very useful: You may want to start here:
http://www.google.com/search?hl=en&q=euclidean+%22traveling+salesman+problem%22&btnG=Google+Search
(I searched for euclidean and "traveling salesman problem". Variations
would include two l's in "traveling", or abbreviating the whole phrase
with "TSP".)

"Euclidean" means that the cost from i to j is proportional to the
distance between the points i and j. Since even the Euclidean TSP is
NP-complete, you may decide that an approximation algorithm would be
good enough. A generic TSP algorithm will also work, but it doesn't
assume anything "Euclidean" about the data.

Wikipedia has some links, so you could scroll down to the bottom of
http://www.answers.com/topic/traveling-salesman-problem to "External
links".

http://www.pcug.org.au/~dakin/tsp.htm has an .exe you can download. A
Java applet is available at
http://pcbunn.cacr.caltech.edu/Java/Genetic.html .

If you download ANYTHING, scan it for viruses before double-clicking on
it. (This applies to ANYTHING you install in your computer, of course.)

Once you find something that's useful and which you can work with,
download it and install it (and anything else you might need, like a
C++ compiler, for instance). If you can find something that runs online
(Java at a webpage), bookmark the page.

(2) Start off by listing your destinations; I'll call them D(1), D(2),
...., D(n).

(3) Now for every i and j, you need to determine the "cost" of driving
from D(i) to D(j). You can approximate this quite well by finding the
distance from D(i) to D(j). (Useful gadget: If you have a single map
with all of your destinations on it, you can buy a pen-like device
where you trace out a route, and it will tell you the total distance
you've traced in inches. This works just as well as the actual
mileage.)

You'll have to update (1) and (2) if you have new destinations and/or
you stop going to some of the old ones.

(4) Run your program, putting in the data you've calculated. (Check the
documentation you get with the program to see how to do this.) Then you
click a button, or the program runs by itself, and gives you the
answer.

That's my 15 minutes of web-searching. Cool

If you need more help, feel
free to ask.

--- Christopher Heckman

Joe
science forum beginner

Joined: 25 Jun 2005
Posts: 22

Posted: Tue Sep 27, 2005 10:31 pm Post subject: Note

Re: question about traveling salesman problem

"Proginoskes" <CCHeckman@gmail.com> wrote in message
news:1127806388.896172.40230@g14g2000cwa.googlegroups.com...

Quote:

Joe wrote:
Hi to the group,

I have been reading (on the internet) about the traveling salesman
problem.
I have a route that I have to run every day and make about 20 to 30 stops
(it varies from week to week). I was trying to figure out how to minimize
my
fuel expenses in order to run this route.

I have a gps receiver with which I can record different routes and save
the
routes, and the destinations (waypoints) and then transfer them to a map.
I
am just not sure where to start with optimizing the solution.
I have some background in Math, Physics, and statistics, but I guess this
is
a problem in combinatorial optimization, which I know next to nothing
about.
I can do some coding (in compiled BASIC). I have also thought of using
the
gps coordinates (not lat/lon, but UTM) and try to create something of a 2
dimensional graph to plot with, but I am just not sure how to start. The
destinations can change week to week also, so I would probably have to re
run this algorithm at least once a week. I am looking for the optimum, or
close to the optimum solution which will minimize my mileage (and, hence
my
fuel expenses). Anyone know where I should start?

(1) You need to go out and find some "code" that will input all of this
data and solve the TSP problem. (You probably haven't got enough
experience to code up the algorithm; I certainly don't. The only people
who have it are the ones who design algorithms and implement them for a
living.) Since you're using distances here, you're looking for some
code that will solve the "Euclidean" version of the problem, which was
discovered a few decades ago. (You don't need the full version of TSP,
because the TSP has no assumption about distances built into it.)
Google is very useful: You may want to start here:
http://www.google.com/search?hl=en&q=euclidean+%22traveling+salesman+problem%22&btnG=Google+Search
(I searched for euclidean and "traveling salesman problem". Variations
would include two l's in "traveling", or abbreviating the whole phrase
with "TSP".)

"Euclidean" means that the cost from i to j is proportional to the
distance between the points i and j. Since even the Euclidean TSP is
NP-complete, you may decide that an approximation algorithm would be
good enough. A generic TSP algorithm will also work, but it doesn't
assume anything "Euclidean" about the data.

Wikipedia has some links, so you could scroll down to the bottom of
http://www.answers.com/topic/traveling-salesman-problem to "External
links".

http://www.pcug.org.au/~dakin/tsp.htm has an .exe you can download. A
Java applet is available at
http://pcbunn.cacr.caltech.edu/Java/Genetic.html .

If you download ANYTHING, scan it for viruses before double-clicking on
it. (This applies to ANYTHING you install in your computer, of course.)

Once you find something that's useful and which you can work with,
download it and install it (and anything else you might need, like a
C++ compiler, for instance). If you can find something that runs online
(Java at a webpage), bookmark the page.

(2) Start off by listing your destinations; I'll call them D(1), D(2),
..., D(n).

(3) Now for every i and j, you need to determine the "cost" of driving
from D(i) to D(j). You can approximate this quite well by finding the
distance from D(i) to D(j). (Useful gadget: If you have a single map
with all of your destinations on it, you can buy a pen-like device
where you trace out a route, and it will tell you the total distance
you've traced in inches. This works just as well as the actual
mileage.)

You'll have to update (1) and (2) if you have new destinations and/or
you stop going to some of the old ones.

(4) Run your program, putting in the data you've calculated. (Check the
documentation you get with the program to see how to do this.) Then you
click a button, or the program runs by itself, and gives you the
answer.

That's my 15 minutes of web-searching. Cool

If you need more help, feel
free to ask.

--- Christopher Heckman

Hello Christopher,

Thank you for the information and links, I will check those out. I can tell
you what I have done so far. My gps will track the route in such a way that
it keeps a track log and saves the coordinates every time I change
direction, and I can mark waypoints by pressing 2 buttons. The waypoints are
my stops, the track log contains every turn and direction change the vehicle
makes. It also can compute euclidean distances between waypoints only. I
have a program called 'topo gps usa', which is pretty old, and probably is
not even available anymore. Using this program, I can overlay the track log
and/or the waypoints onto the map (it's also an old topo map, some of the
roads now were wilderness when the map was created). I can then trace
distances on the map with a stylus like pointer controlled by the mouse. Or
I can transfer them (the coordinates) directly to a spreadsheet and then
compute the distances with a formula.

I have a basic compiler already. Jbasic, it is free on the web. I have had
this for awhile, and I feel more comfortable using the basic language
anyway. With this language, it is possible for me to put a road map (.bmp)
file onto a graphics screen and from there, I am not sure if I can plot
points onto it, or how to do it...yet, I still have some reading to do. I
have had suggestions to use Taxicab geometry instead of euclidean (although
the gps uses euclidean) because the changes in direction are actually
recorded by the gps. I have been told that those points could be used as
'vertices' for my taxicab geometry analysis. In case you are not familiar
with this non euclidean geometry, it defines the distance between two
points, say, (x1,y1) and (x2,y2) as d=abs(x1-x2)+abs(y1-y2) instead of the
euclidean 'shortest distance between two points' where
d=sqrt((x1-x2)^2+(y2-y1)^2), where sqrt is the square root.

I have been experimenting the past few days with the route. There are only
so many ways to run it (because of time constraints and the fact that making
left turns are too time consuming in traffic). I thought it would be a good
idea for me to sharpen my skills by trying to minimize this route
mathematically. Sort of let the computer run the route before I do, and come
up with the final cost. You're right, I need an algorithm that I can code
up. I haven't been able to find one.

I have seen a lot of the information out there on genetic algorithms, though
no one seems to be too specific about the exact techniques, and also the
brute force method of just trying every possible route (which is on the
order of N!) with N being the number of stops.

So most of the suggestions you have given me can be implemented without too
much trouble, automatically almost. It sounds like I can try a few
deviations from my regular route and just measure the bottom line (the final
cost in miles)?

Also, what is your opinion of using taxicab distances (available on google)
instead of euclidean?

Joe

Proginoskes
science forum Guru

Joined: 29 Apr 2005
Posts: 2593

Posted: Wed Sep 28, 2005 4:15 am Post subject: Note

Re: question about traveling salesman problem

Joe wrote:

Quote:

[...]
Hello Christopher,

Thank you for the information and links, I will check those out. I can tell
you what I have done so far. My gps will track the route in such a way that
it keeps a track log and saves the coordinates every time I change
direction, and I can mark waypoints by pressing 2 buttons. The waypoints are
my stops, the track log contains every turn and direction change the vehicle
makes. It also can compute euclidean distances between waypoints only. I
have a program called 'topo gps usa', which is pretty old, and probably is
not even available anymore. Using this program, I can overlay the track log
and/or the waypoints onto the map (it's also an old topo map, some of the
roads now were wilderness when the map was created). I can then trace
distances on the map with a stylus like pointer controlled by the mouse. Or
I can transfer them (the coordinates) directly to a spreadsheet and then
compute the distances with a formula.

I have a basic compiler already. Jbasic, it is free on the web. I have had
this for awhile, and I feel more comfortable using the basic language
anyway. With this language, it is possible for me to put a road map (.bmp)
file onto a graphics screen and from there, I am not sure if I can plot
points onto it, or how to do it...yet, I still have some reading to do. I
have had suggestions to use Taxicab geometry instead of euclidean (although
the gps uses euclidean) because the changes in direction are actually
recorded by the gps. I have been told that those points could be used as
'vertices' for my taxicab geometry analysis. In case you are not familiar
with this non euclidean geometry, it defines the distance between two
points, say, (x1,y1) and (x2,y2) as d=abs(x1-x2)+abs(y1-y2) instead of the
euclidean 'shortest distance between two points' where
d=sqrt((x1-x2)^2+(y2-y1)^2), where sqrt is the square root.

The taxicab distance satisfies the triangle inequality, which puts this
TSP problem between general TSP and Euclidean TSP, and it's another
level of TSP that's been studied. (The triangle inequality states that
the distance from P to Q is less than or equal to the distance from P
to R plus the distance from Q to R.) So you may want to google for
"triangle" along with "TSP".

Quote:

I have been experimenting the past few days with the route. There are only
so many ways to run it (because of time constraints and the fact that making
left turns are too time consuming in traffic). I thought it would be a good
idea for me to sharpen my skills by trying to minimize this route
mathematically. Sort of let the computer run the route before I do, and come
up with the final cost. You're right, I need an algorithm that I can code
up. I haven't been able to find one.

These sort of things show up in math and computer science journals,
which usually aren't available to the general public. There's a search
engine called MathSciNet that search these journals, but you need
access to it to use it. (If you work at a university or a science-based
company, they've paid a fee to allow everyone there to use it. If you
don't work for a university, you can get personal access by paying a
big chunk of money. Then there's tracking down the articles themselves
....)

MathSciNet is at http://www.ams.org/mathscinet/search . I can take a
look at TSP with the triangle inequality tomorrow while I'm at Arizona
State.

Quote:

I have seen a lot of the information out there on genetic algorithms, though
no one seems to be too specific about the exact techniques, and also the
brute force method of just trying every possible route (which is on the
order of N!) with N being the number of stops.

Genetic algorithms involve randomly combining and splitting partial
solutions (taking a trip only from A to B to C, for instance), with
probabilities related to how well they handle the smaller problems, and
need lots of array space to operate. Brute force is the easiest to
code, but takes forever if you have more than 7 or 8 sites.

The TSP is an NP-complete problem, which means nobody thinks there is a
quick way to solve the problem. That is, nobody knows of an algorithm
whose running time is at most N^k for some constant k, where N is the
number of cities. The Euclidean version is also NP-complete, but you
have ways to attack the Euclidean problem which are not possible in the
most general case.

Quote:

So most of the suggestions you have given me can be implemented without too
much trouble, automatically almost. It sounds like I can try a few
deviations from my regular route and just measure the bottom line (the final
cost in miles)?

That's one way to see if you're at a "local minimum", where making
small changes will increase the total distance. Some randomized
algorithms, synthetic annealing (making small changes from the best
solution found so far), for instance, will get caught in a local
minimum.

Quote:

Also, what is your opinion of using taxicab distances (available on google)
instead of euclidean?

Like I mentioned above, if you're going to use taxicab distance, you'll
want to use "triangle" or "triangle inequality" in your search instead
of "euclidean", and there are results which you can use. Because there
are more problems at this level, you'll find that less is known. I'm
not aware of how big the gap is, though.

--- Christopher Heckman

Joe
science forum beginner

Joined: 25 Jun 2005
Posts: 22

Posted: Wed Sep 28, 2005 10:22 pm Post subject: Note

Re: question about traveling salesman problem

"Proginoskes" <CCHeckman@gmail.com> wrote in message
news:1127888129.790874.204740@o13g2000cwo.googlegroups.com...

Quote:

Joe wrote:
[...]
Hello Christopher,

Thank you for the information and links, I will check those out. I can
tell
you what I have done so far. My gps will track the route in such a way
that
it keeps a track log and saves the coordinates every time I change
direction, and I can mark waypoints by pressing 2 buttons. The waypoints
are
my stops, the track log contains every turn and direction change the
vehicle
makes. It also can compute euclidean distances between waypoints only. I
have a program called 'topo gps usa', which is pretty old, and probably
is
not even available anymore. Using this program, I can overlay the track
log
and/or the waypoints onto the map (it's also an old topo map, some of the
roads now were wilderness when the map was created). I can then trace
distances on the map with a stylus like pointer controlled by the mouse.
Or
I can transfer them (the coordinates) directly to a spreadsheet and then
compute the distances with a formula.

I have a basic compiler already. Jbasic, it is free on the web. I have
had
this for awhile, and I feel more comfortable using the basic language
anyway. With this language, it is possible for me to put a road map
(.bmp)
file onto a graphics screen and from there, I am not sure if I can plot
points onto it, or how to do it...yet, I still have some reading to do.
I
have had suggestions to use Taxicab geometry instead of euclidean
(although
the gps uses euclidean) because the changes in direction are actually
recorded by the gps. I have been told that those points could be used as
'vertices' for my taxicab geometry analysis. In case you are not familiar
with this non euclidean geometry, it defines the distance between two
points, say, (x1,y1) and (x2,y2) as d=abs(x1-x2)+abs(y1-y2) instead of
the
euclidean 'shortest distance between two points' where
d=sqrt((x1-x2)^2+(y2-y1)^2), where sqrt is the square root.

The taxicab distance satisfies the triangle inequality, which puts this
TSP problem between general TSP and Euclidean TSP, and it's another
level of TSP that's been studied. (The triangle inequality states that
the distance from P to Q is less than or equal to the distance from P
to R plus the distance from Q to R.) So you may want to google for
"triangle" along with "TSP".

I have been experimenting the past few days with the route. There are
only
so many ways to run it (because of time constraints and the fact that
making
left turns are too time consuming in traffic). I thought it would be a
good
idea for me to sharpen my skills by trying to minimize this route
mathematically. Sort of let the computer run the route before I do, and
come
up with the final cost. You're right, I need an algorithm that I can code
up. I haven't been able to find one.

These sort of things show up in math and computer science journals,
which usually aren't available to the general public. There's a search
engine called MathSciNet that search these journals, but you need
access to it to use it. (If you work at a university or a science-based
company, they've paid a fee to allow everyone there to use it. If you
don't work for a university, you can get personal access by paying a
big chunk of money. Then there's tracking down the articles themselves
...)

MathSciNet is at http://www.ams.org/mathscinet/search . I can take a
look at TSP with the triangle inequality tomorrow while I'm at Arizona
State.

I have seen a lot of the information out there on genetic algorithms,
though
no one seems to be too specific about the exact techniques, and also the
brute force method of just trying every possible route (which is on the
order of N!) with N being the number of stops.

Genetic algorithms involve randomly combining and splitting partial
solutions (taking a trip only from A to B to C, for instance), with
probabilities related to how well they handle the smaller problems, and
need lots of array space to operate. Brute force is the easiest to
code, but takes forever if you have more than 7 or 8 sites.

The TSP is an NP-complete problem, which means nobody thinks there is a
quick way to solve the problem. That is, nobody knows of an algorithm
whose running time is at most N^k for some constant k, where N is the
number of cities. The Euclidean version is also NP-complete, but you
have ways to attack the Euclidean problem which are not possible in the
most general case.

So most of the suggestions you have given me can be implemented without
too
much trouble, automatically almost. It sounds like I can try a few
deviations from my regular route and just measure the bottom line (the
final
cost in miles)?

That's one way to see if you're at a "local minimum", where making
small changes will increase the total distance. Some randomized
algorithms, synthetic annealing (making small changes from the best
solution found so far), for instance, will get caught in a local
minimum.

Also, what is your opinion of using taxicab distances (available on
google)
instead of euclidean?

Like I mentioned above, if you're going to use taxicab distance, you'll
want to use "triangle" or "triangle inequality" in your search instead
of "euclidean", and there are results which you can use. Because there
are more problems at this level, you'll find that less is known. I'm
not aware of how big the gap is, though.

--- Christopher Heckman

I searched for triangle tsp and other various combinations. I found a pretty
good site at :
http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/AproxAlgor/TSP/tsp.htm

At the bottom of the page, it has a section where you can put points on the
graph and watch the solution develop. it gives 3 solutions, which I still
have to study. There's other sites with these search words too, which I
haven't seen yet...

I am going to start out with a smaller number of points, and work my way up
as I learn how to code it and represent each point with a name or letter or
something. The devil is always in the details! Thank you again for getting
me started.

Joe

Google

Display posts from previous:

Page 1 of 1 [5 Posts]

View previous topic :: View next topic

The time now is Fri Jan 09, 2009 9:01 pm | All times are GMT

Forum index » Science and Technology » Math » Combinatorics

Jump to:

Topic		Author	Forum	Replies	Last Post
Similar Topics
	Question about Life.	socratus	Probability	0	Sun Jan 06, 2008 10:01 pm
	Traveling around Europe	gabrielj	Recreational	0	Tue Nov 28, 2006 8:03 pm
	Probability Question	dumont	Probability	0	Mon Oct 23, 2006 3:38 pm
	help on problem	brb003	Math	0	Mon Aug 28, 2006 3:31 am
	fraction problem	mikerule	Research	0	Thu Aug 24, 2006 5:10 am

Download movies | Debt Consolidation | Advertising | Unblock Myspace | Credit Cards

Other DeniX Solutions sites: Electronics forum | Medicine forum | Unix/Linux blog | Unix/Linux documentation | Unix/Linux forums

[ Time: 0.4771s ][ Queries: 16 (0.3450s) ][ GZIP on - Debug on ]