Solving the Traveling Salesman Problem Using Premium Solver Platform Software

摘要: The traveling salesman problem has been a very important topic of study for operations researchers and mathematicians decades. Computer hardware software advances in recent years have provided multiple alternative approaches to this classic combinatorial challenge. objective paper is present an approach the using Premium Solver Platform©, commercial add-in optimization tool Microsoft Excel©. illustrates solution which efficiently solves both small large scale Traveling Salesman Problems. Introduction Mathematicians research specialists researching writing about Problem (TSP) One earliest known papers on "On Hamiltonian Game (a problem)" by Robinson.1 Among most prolific early were Dantzig, Fulkerson Johnson. Their 1954 paper, "Solution Large-Scale Traveling-Salesman Problem", describes linear programming 49 city problem, considered field.2 An extensive TSP project supported Rice University, Rice's Information Technology Institute; Center Research Parallel Computation; Digital Equipment Corporation; Keck Foundation. A comprehensive web site includes found at http://www.iwr.uni-heidelberg.de/iwr/comopt/software/TSPLIB95. treatments Guided Tour Combinatorial Optimization.3 solving large-scale problems minimize total length tour, entering leaving each location once, while beginning ending lour with same location. In we will discuss small-scale can be solved Platform©. basic procedures are identical. used illustrate formulation problem. Table 1 summarizes road mileage first example. There seven cities It would However, manual algorithms developed over solve such combined high number feasible, but not optimal solutions, make difficult lengthy solve. Figure presents alternative, graphical view Platform available was written Frontline Systems. More powerful versions academic use. page maintained Systems provides product information, as well general information programming.4 version larger more complex than standard significant addition software, released 2000, inclusion "all different" constraint. This allows one specify that set variables integer values from N (the variables), all them different solution.5 feature dramatically simplified Problem, illustrated paper. Formulation step formulating Platform© develop direct distance matrix. Using 1, modified spreadsheet shown 2. …