Academic journal article International Journal of Management

Solving the Traveling Salesman Problem Using Premium Solver Platform Software

Academic journal article International Journal of Management

Solving the Traveling Salesman Problem Using Premium Solver Platform Software

Article excerpt

The traveling salesman problem has been a very important topic of study for operations researchers and mathematicians for decades. Computer hardware and software advances in recent years have provided multiple alternative approaches to this classic combinatorial challenge. The objective of this paper is to present an approach to the traveling salesman problem using Premium Solver Platform©, a commercial add-in optimization tool for Microsoft Excel©. The paper illustrates a solution approach which efficiently solves both small and large scale Traveling Salesman Problems.

Introduction

Mathematicians and operations research specialists have been researching and writing about the Traveling Salesman Problem (TSP) for decades. One of the earliest known papers on the topic is "On the Hamiltonian Game (a traveling salesman problem)" by Robinson.1 Among the most prolific early researchers were Dantzig, Fulkerson and Johnson. Their 1954 paper, "Solution of a Large-Scale Traveling-Salesman Problem", which describes a linear programming approach for a 49 city problem, is considered a classic in the field.2 An extensive TSP research project is supported by Rice University, Rice's Computer and Information Technology Institute; the Center for Research on Parallel Computation; Digital Equipment Corporation; and the Keck Foundation. A comprehensive web site which includes software and research papers is found at http://www.iwr.uni-heidelberg.de/iwr/comopt/software/TSPLIB95. One of the most comprehensive treatments is The Traveling Salesman Problem A Guided Tour of Combinatorial Optimization.3

The objective of this paper is to present an alternative approach to solving both small and large-scale traveling salesman problems using Premium Solver Platform©, which is an optimization add-in tool for Microsoft Excel©.

Traveling Salesman Problem

The objective in a Traveling Salesman Problem is to minimize the total length of a tour, entering and leaving each location once, while beginning and ending the lour with the same location. In this paper, we will discuss both small-scale and large-scale problems which can be solved using Premium Solver Platform©. The basic procedures are identical. The small-scale problem will be used to illustrate the formulation of the problem. Table 1 summarizes the road mileage for the first example.

There are seven cities in the TSP example. It would be considered a small-scale problem. However, the manual algorithms developed over the years to solve such a problem, combined with the high number of feasible, but not optimal solutions, make this a difficult and lengthy problem to solve. Figure 1 presents an alternative, graphical view of this problem.

Premium Solver Platform

Solver is an add-in optimization tool which is available with Microsoft Excel©. The software was written for Microsoft by Frontline Systems. More powerful versions of Solver are available for commercial and academic use. A web page maintained by Frontline Systems provides product information, as well as general information on optimization and linear programming.4 The version used for this paper is Premium Solver Platform©, which will solve larger and more complex problems than the version which is standard with Microsoft Excel©. A significant addition to this software, which was released in 2000, is the inclusion of the "all different" constraint. This allows one to specify that a set of variables will have integer values from 1 to N (the number of variables), all of them different at the solution.5 This powerful feature has dramatically simplified the formulation of the Traveling Salesman Problem, as will be illustrated in this paper.

Formulation of Traveling Salesman Problem

The first step in formulating the TSP problem using Premium Solver Platform© is to develop the direct distance matrix. Using the mileage values from Table 1, the modified spreadsheet is shown in Table 2. …

Search by... Author
Show... All Results Primary Sources Peer-reviewed

Oops!

An unknown error has occurred. Please click the button below to reload the page. If the problem persists, please try again in a little while.