Tanner Jepsen
Professor Alexander Vaughan Ames
English Composition I
July 12, 2010
Assignment 4.4: The Travelling Salesman Problem
The Travelling Salesman Problem is a complex problem in Computer Science, however developing a computer algorithm to overcome the problem in the most efficient way possible is not an unmanageable or difficult task. The problem states that given a list of cities and the distances between each pair of cities, finding the shortest possible route that visits each city only once is computationally difficult. For Humans, you might say this is an easy problem. Just look at a map and visually find the shortest route. For computers, it is a far more complex problem. Imagine that the list of cities includes hundreds, thousands or even tens of thousands of destinations spread across a large geographical area. Perhaps it’s not cities at all, but countries or a list of coordinates. In the future it may even be planets, solar systems, galaxies etcetera. The problem can quickly become far too much for a Human to solve. Even for a computer, as the list grows larger it will take the computer longer and require more resources to find an efficient solution. The makers of a popular space game, Eve-Online by CCP, graciously make their entire game database available to the public which is perfect for exploring this problem.
The Eve-Online universe includes 5431 solar systems spread across 1109 constellations and 97 regions. The only way to travel between solar systems is by using jump gates that propel a space ship to faster than light speeds. Attempting to travel between solar systems without a jump gate would take several lifetimes and is simply unfeasible and so using the jump gates is considered to be a constraint. Constraints are a good thing because they limit the number of options the computer can take to travel, which means less for the computer to look at. Finding the quickest route between two solar systems is a fairly simple process using a breadth first search. That is, starting from solar system “A”, check to see if any of the connected solar systems is the final destination. If not, do the same thing with each connected solar system and continue the process until the destination solar system “B” is found. Throughout the process, the computer algorithm needs to keep track of where it has already been so that it doesn’t visit the same place twice. Depending on how many solar systems need to be travelled through to get to the destination, this search algorithm, although extremely simple, could take a very long time to find the destination and requires large amounts of computer memory to keep track of the solar systems that were already visited. There are a few heuristic measures that can be taken to minimize the amount of time it takes and the amount of memory required to find the quickest route.
The Eve-Online database does not directly provide the distance between two solar systems. It does, however, provide the x, y and z coordinates in 3D space of where all the solar systems lie. Using the x, y and z coordinates of two solar systems we can use Pythagorean’s Theorem to determine the distance between them which, in effect, is another constraint. Pythagorean’s Theorem states that the length of a hypotenuse on a right triangle is equal to the square root of the length of the adjacent squared plus the length of the opposite squared, or c = sqrt(a2 + b2). We can further this in 3D space so that the distance between two solar systems would be calculated thusly:
The original algorithm can now be modified to take into account the distance calculated between two solar systems. The algorithm can be programmed so that it does not travel through a solar system that takes it further away from the destination unless all other options have been exhausted. Although this is great, and the computer is finding the route faster, there is still more that can be done.
As previously explained, the Eve-Online database places each solar system into constellations and regions, just as cities are placed into counties and states. As the algorithm travels between solar systems it will cross constellational and regional boundaries, just as in real life, when a person travels between cities he will cross county and state lines to get to his destination. This is another constraint. Before finding the route between solar system “A” and solar system “B”, the algorithm can find the route between the constellations that each solar system lies within. Once it has the route between constellations “A” and “B”, the algorithm can then eliminate adjacent solar systems from the search path by determining if said solar system lies within one of the constellations that have already been found to be along the route. If it doesn’t, the solar system is ignored, potentially removing a very large chunk of search paths from the search algorithm. The same concept can be implemented for regions as well, however depending on the size of the universe, as in the Eve-Online example, it may not be beneficial.
At this point the algorithm is very fast and can be used in a production environment, but there are other constraints that can be added as a convenience to the user. The database includes a security status for each solar system. On a scale from 0.00, indicating no security, to 1.00, indicating complete security, this constraint can be added to the search algorithm so that the user may avoid low security solar systems, thereby avoiding pirates and certain death if the proper arrangements are not made to travel with a skilled security detail.
Exploring the Eve-Online game universe it has been found that the travelling salesman problem is not an unmanageable problem at all on today’s powerful computers. At the hands of a skillful computer programmer, using constraints to her advantage it is possible to minimize the amount of required processor and memory resources to quickly find a solution to the most common routing problems. Many search algorithms are in use today, perhaps some can be made more efficient, reducing operating costs for businesses such as UPS, FedEx, USPS, and DHL to the local courier service, airport shuttle service, and even the pizza delivery man.
Bibliography
CCP. “Eve Online | Data Export.” 1997-2007. Eve Online. 2010 <http://www.eveonline.com/community/toolkit.asp>.
Wikimedia Foundation, Inc. “Pythagorean theorem.” 8 July 2010. Wikipedia. 12 July 2010 <http://en.wikipedia.org/wiki/Pythagorean_theorem>.
—. “Travelling salesman problem.” 10 July 2010. Wikipedia. 12 July 2010 <http://en.wikipedia.org/wiki/Travelling_Salesman_Problem>.
