Gezgin satıcı problemi

Abstract

ÖZET Bir gezgin satıcı problemi, n adet şehir için başlangıç noktasından itibaren her bir şehre sadece bir defa uğrandıktan sonra tekrar başlangıç noktasına dönülmesini ve bu turun mümkün olan en kısa yolun izlenerek tamamlanmasını amaçlamaktadır. Bu çalışmada ilk olarak Gezgin Satıcı Problemi hakkında genel bir bilgi verilmiş ve formülasyonu yapılmıştır. Daha sonra Gezgin Satıcı Problemi' ne getirilmiş olan çözüm yaklaşımları, kesin ve sezgisel olmak üzere sınıflandırılarak incelenmişlerdir. Bu yaklaşımların birbirleri ile karşılaştırılması yoluyla da zayıf ve güçlü yönleri açıklanmıştır. Bunun yanısıra yeni arama teknikleri hakkında da bilgi verilmiştir. Dördüncü bölümde Gezgin Satıcı Problemi (GSP) 'nin bir uygulaması Erciyas Biracılık ve Malt San. A.Ş.'nin bir satış bölgesi üzerinde gerçekleştirilmiş, seçilen bölgeye ait bilgiler GSP için hazırlanmış olan `Travel` adındaki bir bilgisayar programına aktarılmış ve elde edilen sonuçlar değerlendirilmiştir. Çalışmanın son bölümünde ise kullanılan yöntemler ve uygulama hakkında bir değerlendirme yapılmıştır. vi

SUMMARY (TRAVELING SALESMAN PROBLEM) One of the classic problems in graph theory which still has no closed analytic, algorithmic solution is the traveling salesman problem. The Taveling Salesman Problem (TSP) has been a challenge that has attracted researchers who have wanted to derive an efficient solution method for the problem. The first use of the term `Traveling Salesman Problem` in mathematical circles may have been in 1931-1932. But in 1832, a book was printed in Germany (The Traveling Salesman, how he should be and what he should do to get commissions and to be successful in his business. By a veteran Traveling Salesman). Although devoted for the most parts to other issues, the book reaches the essence of the TSP in its last chapter. * It is not known who brought the name TSP in to mathemaatical circles, but there is no question that Merrill Flood is most responsible for publicizing within that community and the operations reseaarch fraternity as well. The TSP now had a name and - starting at least as early as the late 1940s - a persistent and effective herald in Merrill Flood. The TSP may be stated as follows: Given a road map showing the direct path between every pair of cities, what is the optimum route such that a salesman will visit every city only once and return home while keeping his or her mileage to a minimum. Surprising as it seems, there is no analytic expression in terms of the city coordinates for computing such an optimum route, and the most obvious computational algorithm is to generate-and-test all possible solutions and select the minimum distance. The combinatorial explosion makes this approach extremely time consuming for realistic problems. For instance, a 30 city problem requires examination of more than 1030 routes. Several heuristics have been developed to reduce the search space so that a near optimal route can be selected. Not only is this problem of considerable theoretical interest but it also has a very significant practical interest to such institutions as the post offices, any company with sizable sales and field representative force. The traveling salesman problem can be decomposed into two sub-problems: vm- Does a route exist which connects every city on the tour? This problem, when phrased in terms of a complete round trip visiting each city once and returning to the starting city, is known as the Hamilton Cycle Problem. - Which route minimizes the total distance? There is no solution to this problem except exhaustive search with a generate-and-test algorithm. The reason for popularity of the problem was its intimate connection with prominent topics in combinatorial problems arising in the new subject of linear programming, namely the assignment problem and more generally the transportation problem. Despite the fact that the traveling salesman model applies directly to a very useful- sounding situation, namely that of a salesman wishing to minimize his travel distance, most of the reported applications are quite different. That is seemingly unrelated problems are solved by formulating them as instances of the TSP. The applications described below are intended to show the versatility of the TSP model: By vehicle routing it means that the problem of determining for a fleet of vehicles which customers should be served by which vehicles, and in what order each vehicle visit its customers. Some algorithms for this problem use the TSP model for the subproblem of ordering each vehicle's customers. Another type of problem, computer wiring, occurs repeatedly in the design of computers and other digital systems. The TSP model is used for minimizing the total wire length in order to avoid signal cross-talk and to improve ease and neatness of wiring. Sequencing n jobs on a single machine by completing all of them in the shortest possible time, cutting n sheets from a single long role of paper by minimizing the total wastage, clustering data array are some application areas for TSP. Similar to the most of the other combinatorial optimization problems the TSP falls into a category which is well known as NP-Complete Problems. The letters NP stand for `Nondeterministic Polynomial`. The status of this category is uncertain in the sense that only exponantial algorithms are known for the NP-Complete problems. Neither an efficient algorithm for solving the problems has been developed, nor it has been proven that such algorithms do not exist. However NP-Complete problems have remarkable property. That is, each problem in this category is (i.e. in a polynomial time) reducible to another NP-Complete problem. Consequently, if any of them has an efficient algorithm then every NP-Complete problem can be solved efficiently. Not all situations to which the TSP is confined involve cost minimization. Instead of cost other measures of effectiveness may be subsituted according to their applications. The problem is known to have wide applications in frequently encountered problems arising in practical situations. The problem is formidable in the sense that the associated solution methods are quite difficult contrary to the simplicity of its statement. The importance of the TSP comes not from the wealth of applications (there are not many salesman clamoring for an IXalgoritm, and the number of other cases where the mathematical model of the TSP precisely fits an engineering or scientific situation have not to date been numerous), but from the fact that it is typical of other problems of its genre: Combinatorial Optimization. We are trying to minimize total distance, so the problem is one of optimization; bu we can not immediately employ the methods of differential calculus by setting derivatives to zero, because we are combinatorial situation: Our choice is not over a continuum but over the set of all tours. The TSP can be interpreted as a Vehicle Routing Model with one depot and with one vehicle whose capacity exceeds the total demand. This model can be extended by considering more vehicles, more depots, different vehicle capacities and additional route restrictions. Most Vehicle Routing Problems are variants and extentions of the TSP. The problem is to form a tour and the n nodes beginning and ending at the origin, node 1, which gives the minimum distance or cost. The solution procedures for TSP fall into two categories: - Techniques that are certain to find an optimum solution but at worst require an inordinate number of calculations (Exact Solution Methods). - Techniques that are not always certain to find an optimum solution but require a small number of calculations and there for less computational effort (Heuristic Methods). In most cases, a Branch and Bound Approach is the most efficient approach for solving a Traveling Salesman Problem. Several Branch and Bound Approaches have been developed for solving Traveling Salesman Problems but in this study, I define an approach which the subproblems reduce to assignment problems. If an optimal solution to the assignment problem is feasible for the Traveling Salesman Problem, the optimal solution to the assignment problem is also optimal for the Traveling Salesman Problem. For large Traveling Salesman Problems, the state space becomes very large, and the Branch and Bound Approach is much more efficient than the Dynamic Programming Approach. For example, for a 30 - city problem, suppose that we are at stage 16 (this means that 15 cities have been visited). Then it can be shown that there are over 1 billion possible states. This brings up a problem that limits the practical application of Dynamic Programming. In many problems the state space becomes so large that excessive computational time is required to solve the problem by Dynamic Programming. Even a powerful computer would have difficulty solving these kind of problems. When using Branch and Bound Methods to solve Traveling Salesman Poblems with many cities, large amounts of computer time may be required. For this reason heuristic methods or heuristics, which quickly lead to a good solution to a TSP, are often used.A heuristic is a method used to solve a problem by trial and error when an algorithmic is impractical. Heuristics often have an intuitive justification. To apply the Nearest Neighbour Heuristic (NNH), we begin at any city and then visit the nearest city. Then we go to the unvisited city closest to the city we have most recently visited. We will continue in this fashion until a tour is obtained. NNH need not yield an optimal tour. A popular heuristic is to apply the NNH beginning at each city and then take the best tour obtained. In the Cheapest Insertion Heuristic (CUT), we begin at any city and find its closest neighbour. Then we create a subtour joining two cities. Next, we replace an arc in the subtour by the combination of two arcs that will increase the lenght of the subtour by the smallest or the cheapest amount. In general the CIH, does not necessarly yields an optimal tour. The following three methods have been suggested for evaluating heuristics: - Performance Guarantees - Probabilistic Analysis - Empirical Analysis A performance guarantee for a heuristic gives a worst case bound on how far away from optimality a tour constructed by the heuristic can be. For the NNH, it can be shown that for any number `r`, a TSP can be contracted such that the NNH yields a tour that is r times as long as the optimal tour. Thus, in a worst case scenario, the NNH fares poorly. For a symmetric TSP satisfying the triangle inequality it has been shown that the lenght of the tour obtained by the CIH can not exceed twice the lenght of the optimal tour. In probabilistic analysis, a heuristic is evaluated by assuming that the location of cities follows some known probility distribution. For example, we might assume that the cities are independent random variables that are uniformly distributed on a cube of unit lenght, width and height. Then for each heuristic, we would compute the following ratio. Expected Lenght Of The Path Found By The Heuristic Expected Lenght Of An Optimal Tour The closer the ratio is to 1 the better the heuristic. For empirical analysis, heuristics are compared to the optimal solution for a number of problems for which the tour is known. XIMost heuristic algorithm attempts to solve the problems as one big problem, where as the Sweep Algoritm devides the locationss in to a number of routes and than operates individual routes until an optimum or near optimum solution is obtained. When the problem is broken into a number of smaller subproblems, the computation time involved increases somewhat in a linear rather than in an exponantial manner as more locations are added to a given problem, e.g. while the number of possible routes in a TSP is 1 / 2 n!, when the same problem is divided into m subproblems, the number decreases to about 1 / 2 (n / m)! * m and the computer time also decreases accordingly. This may give an idea why the time increases somewhat in a linear manner in the Sweep Algoritm when compared to other algorithms. Because of decreasing the computer time the Sweep Algorithm can handle larger problems. The Sweep Algorithm consists of two parts, a Forward Sweep and a Backward Sweep. In most cases, the two procedures produce different near optimum distances. The minimum of these two is the best approximate solution. The Clark and Wright's Algorithm is based on the idea of savings. In the beginning of the algorithm, is assumed that all the demand points are directly connected with the depot and then by looking at the savings of the demand points, they are paired. The demand points are connected with each other taking savings into the considerations. After the routes are formed, an iterative procedure is applied. This process continues until a specified number of successive suppressions yields no improvements in the solution or until all paires joined, have been suppresseed with no resulting improvements. This algorithm can handle vehicles with different capacities. In this study, part two presents the structure of Traveling Salesman Problem. The definition is made and then the formulation is given. Also the application areas of TSP are explained. In part three, the solution approaches to Traveling Salesman Problem, are presented. These approaches are Branch and Bound Approach, Dynamic Programming Approach, the Heuristics, searching techniques as Depth-First Search, Breadth-First Search and Hill-Climbing Heuristic and Neural Network Approach. All these above mentioned approaches and algorithms are defined and formulated in part three, and also the examples are given for each of them. An application for TSP was made in Erciyas Biracılık ve Malt Malt San. A.Ş.. One of the sales route was chosed. The data about the route are used as the inputs of a computer program named `Travel`. In part five the results of the application are compared and discussed. I hope this study will be helpful to the firms about improving their distribution systems. xn