Solving the Traveling Salesman Problem
Bruno Guerrieri Florida A&M University bruno.guerrieri@famu.edu
Introduction
This worksheet demonstrates the use of Maple to solve the Traveling Salesman Problem and visualizes the solution.
The following Maple techniques are highlighted:
The Problem
The Traveling Salesman Problem (TSProblem) is a very interesting minimization problem in which a salesman wishes to visit N cities. He has to visit every city once and must return to the city of departure, attempting to minimize the overall distance traveled. For the symmetric problem where distance (cost) from city A to city B is the same as from B to A, the number of possible paths to consider is given by . The exhaustive search which leads to the best tour becomes very quickly impossible to conduct. Why? Because, assuming that your computer can evaluate the length of a billion tours per second, calculations would last 40 years in the case of twenty cities, and would jump to 800 years if you decided to add one city to the tour [1]. These numbers give meaning to the expression "combinatorial explosion". Consequently, it was decided that one would attempt to exchange accuracy for speed. We will settle for an optimal solution (a good tour but not necessarily the global minimum one) if we can find it fast. Algorithms offering this trade-off abound and are all extremely interesting. In this worksheet, we will consider a simple-minded one (nearest neighbor) and see how it fares against one of the best (Lin-Kernighan 2-opt).
Required Procedures used by all Algorithms
We will need certain standard procedures for an experiment of that sort. We decided to keep the program simple, consider the symmetric case, and let the computer randomly generate N city positions within a 1x1 square. So, the procedure "city_position" does just that.
Note: A new feature of Maple are "code edit" regions. These regions allow you to place many lines of code in a window that you can collapse into a button. To look at the code contained within any code region, right click on the code edit button and select Expand Code Edit Region.
#Define city_position
"mixup" is a procedure that randomly selects a particular tour. In general, this procedure is invoked at the beginning of the process so as to start with a given tour on which to improve i.e. incrementally evolving to a better tour by removing certain edges and adding others while maintaining the integrity of the tour . If the incoming parameter "val" is set to 1, then there is no rearranging in the initial order of the cities at the time of the call. Otherwise, there is.
#Define mixup
Procedure "tour_length" calculates the length of a given tour.
#Define tour_length
This procedure plots a given tour. The segment from first city to nearest city is in GREEN and the segment going back home to the city of departure is in RED. Hence, the city of departure is always between these two segments. (Courtesy of a student of mine, Mr. Frederick Biga)
#Define Plot_Tour
Procedure Used by the Nearest Neighbor Algorithm
Procedure " next_city" helps to determine the next city to be visited. The one selected is the nearest one. This is the central idea behind the nearest-neighbor algorithm (Concept from Dr. Rosalynn Williams).
#Define next_city
Procedure Used by The Lin-Kernighan Algorithm
This is the procedure "two_opt" which implements the Lin-Kernighan algorithm. The array "ptr" records the order of the random initial tour. The quantity "m" keeps track of the number of actual changes and becomes the number of frames in the animation. The quantity "dmax" measures the excess that one tour has over another. As long as dmax > 0, this means that shorter tours have been found. Please consult [2] for details.
#Define two_opt
Main
N represents the number of cities. We will randomly determine their position (x-coordinate and y-coordinate) and set up the Distance_Matrix which contains all possible distances. We will then select an initial random tour. In the case of the "Nearest Neighbor" this is really not necessary because all we have to do is select an initial city and then apply the Nearest neighbor algorithm. We will, however need an initial random tour in the case of the 2-opt algorithm.
We are now plotting an initial tour chosen at random.
Nearest Neighbor
We will now start from the first city and determine the path to follow, going from nearest city to nearest city. The array city_visited will keep the list of the cities already visited. At first we will start from the first city in city_list and apply the algorithm. Then we will repeat the process starting from city 2 and so on. The reason for that is that it could be that the best tour the algorithm will offer may be influenced by which city we decide to start from. We are doing an exhaustive search in that sense.
#Determine path to follow
Next, we will display an animation that shows the nearest neighbor results associated with each city in turn selected as a departure city. Then we will display the overall best as a single frame.
Lin-Kernighan two-opt Algorithm
The procedure "two_opt" finds an approximate solution (sub-optimal path) of the symmetric TSP with N nodes, given (the problem) as a NxN Distance_Matrix . It starts with the initial tour (specified by array "city_list") and improves repeatedly by exchanging two edges at a time following a specific algorithm (See Reference [2]).
Next, we will display an animation that shows the sequence of improvements from the Lin-Kernighan algorithm. Then we will display the overall best (the final tour) as a single frame.
References
[1] The Molecular Computer, Don Ploger, Lee Klingler, Consortium, The Newsletter of the Consortium for Mathematics and Its Applications, Number 58, Summer 1996.[2] Discrete Optimization Algorithms, Maciej M. Syslo, Narsingh Deo, Janusz S. Kowalik, Prentice-Hall, 1983.
Legal Notice: The copyright for this application is owned by the author(s). Neither Maplesoft nor the author are responsible for any errors contained within and are not liable for any damages resulting from the use of this material.. This application is intended for non-commercial, non-profit use only. Contact the author for permission if you wish to use this application in for-profit activities.
