travelling salesman linear programming

Traveling salesman problem

This web page is a duplicate of https://optimization.mccormick.northwestern.edu/index.php/Traveling_salesman_problems

Author: Jessica Yu (ChE 345 Spring 2014)

Steward: Dajun Yue, Fengqi You

The traveling salesman problem (TSP) is a widely studied combinatorial optimization problem, which, given a set of cities and a cost to travel from one city to another, seeks to identify the tour that will allow a salesman to visit each city only once, starting and ending in the same city, at the minimum cost. 1

• 2.1 Graph Theory
• 2.2 Classifications of the TSP
• 2.3 Variations of the TSP
• 3.1 aTSP ILP Formulation
• 3.2 sTSP ILP Formulation
• 4.1 Exact algorithms
• 4.2.1 Tour construction procedures
• 4.2.2 Tour improvement procedures
• 5 Applications
• 7 References

The origins of the traveling salesman problem are obscure; it is mentioned in an 1832 manual for traveling salesman, which included example tours of 45 German cities but gave no mathematical consideration. 2 W. R. Hamilton and Thomas Kirkman devised mathematical formulations of the problem in the 1800s. 2

It is believed that the general form was first studied by Karl Menger in Vienna and Harvard in the 1930s. 2,3

Hassler Whitney, who was working on his Ph.D. research at Harvard when Menger was a visiting lecturer, is believed to have posed the problem of finding the shortest route between the 48 states of the United States during either his 1931-1932 or 1934 seminar talks. 2 There is also uncertainty surrounding the individual who coined the name “traveling salesman problem” for Whitney’s problem. 2

The problem became increasingly popular in the 1950s and 1960s. Notably, George Dantzig, Delber R. Fulkerson, and Selmer M. Johnson at the RAND Corporation in Santa Monica, California solved the 48 state problem by formulating it as a linear programming problem. 2 The methods described in the paper set the foundation for future work in combinatorial optimization, especially highlighting the importance of cutting planes. 2,4

In the early 1970s, the concept of P vs. NP problems created buzz in the theoretical computer science community. In 1972, Richard Karp demonstrated that the Hamiltonian cycle problem was NP-complete, implying that the traveling salesman problem was NP-hard. 4

Increasingly sophisticated codes led to rapid increases in the sizes of the traveling salesman problems solved. Dantzig, Fulkerson, and Johnson had solved a 48 city instance of the problem in 1954. 5 Martin Grötechel more than doubled this 23 years later, solving a 120 city instance in 1977. 5 Enoch Crowder and Manfred W. Padberg again more than doubled this in just 3 years, with a 318 city solution. 5

In 1987, rapid improvements were made, culminating in a 2,392 city solution by Padberg and Giovanni Rinaldi. In the following two decades, David L. Appelgate, Robert E. Bixby, Vasek Chvátal, & William J. Cook led the cutting edge, solving a 7,397 city instance in 1994 up to the current largest solved problem of 24,978 cities in 2004. 5

Description

Graph theory.

In the context of the traveling salesman problem, the verticies correspond to cities and the edges correspond to the path between those cities. When modeled as a complete graph, paths that do not exist between cities can be modeled as edges of very large cost without loss of generality. 6 Minimizing the sum of the costs for Hamiltonian cycle is equivalent to identifying the shortest path in which each city is visiting only once.

Classifications of the TSP

The TRP can be divided into two classes depending on the nature of the cost matrix. 3,6

• Applies when the distance between cities is the same in both directions

• Applies when there are differences in distances (e.g. one-way streets)

An ATSP can be formulated as an STSP by doubling the number of nodes. 6

Variations of the TSP

Formulation

The objective function is then given by

To ensure that the result is a valid tour, several contraints must be added. 1,3

There are several other formulations for the subtour elimnation contraint, including circuit packing contraints, MTZ constraints, and network flow constraints.

aTSP ILP Formulation

The integer linear programming formulation for an aTSP is given by

sTSP ILP Formulation

The symmetric case is a special case of the asymmetric case and the above formulation is valid. 3, 6 The integer linear programming formulation for an sTSP is given by

Exact algorithms

Branch-and-bound algorithms are commonly used to find solutions for TSPs. 7 The ILP is first relaxed and solved as an LP using the Simplex method, then feasibility is regained by enumeration of the integer variables. 7

Other exact solution methods include the cutting plane method and branch-and-cut. 8

Heuristic algorithms

Given that the TSP is an NP-hard problem, heuristic algorithms are commonly used to give a approximate solutions that are good, though not necessarily optimal. The algorithms do not guarantee an optimal solution, but gives near-optimal solutions in reasonable computational time. 3 The Held-Karp lower bound can be calculated and used to judge the performance of a heuristic algorithm. 3

There are two general heuristic classifications 7 :

• Tour construction procedures where a solution is gradually built by adding a new vertex at each step
• Tour improvement procedures where a feasbile solution is improved upon by performing various exchanges

The best methods tend to be composite algorithms that combine these features. 7

Tour construction procedures

Tour improvement procedures

Applications

The importance of the traveling salesman problem is two fold. First its ubiquity as a platform for the study of general methods than can then be applied to a variety of other discrete optimization problems. 5 Second is its diverse range of applications, in fields including mathematics, computer science, genetics, and engineering. 5,6

Suppose a Northwestern student, who lives in Foster-Walker , has to accomplish the following tasks:

• Drop off a homework set at Tech
• Work out a SPAC
• Complete a group project at Annenberg

Distances between buildings can be found using Google Maps. Note that there is particularly strong western wind and walking east takes 1.5 times as long.

It is the middle of winter and the student wants to spend the least possible time walking. Determine the path the student should take in order to minimize walking time, starting and ending at Foster-Walker.

Start with the cost matrix (with altered distances taken into account):

Method 1: Complete Enumeration

All possible paths are considered and the path of least cost is the optimal solution. Note that this method is only feasible given the small size of the problem.

From inspection, we see that Path 4 is the shortest. So, the student should walk 2.28 miles in the following order: Foster-Walker → Annenberg → SPAC → Tech → Foster-Walker

Method 2: Nearest neighbor

Starting from Foster-Walker, the next building is simply the closest building that has not yet been visited. With only four nodes, this can be done by inspection:

• Smallest distance is from Foster-Walker is to Annenberg
• Smallest distance from Annenberg is to Tech
• Smallest distance from Tech is to Annenberg ( creates a subtour, therefore skip )
• Next smallest distance from Tech is to Foster-Walker ( creates a subtour, therefore skip )
• Next smallest distance from Tech is to SPAC
• Smallest distance from SPAC is to Annenberg ( creates a subtour, therefore skip )
• Next smallest distance from SPAC is to Tech ( creates a subtour, therefore skip )
• Next smallest distance from SPAC is to Foster-Walker

So, the student would walk 2.54 miles in the following order: Foster-Walker → Annenberg → Tech → SPAC → Foster-Walker

Method 3: Greedy

With this method, the shortest paths that do not create a subtour are selected until a complete tour is created.

• Smallest distance is Annenberg → Tech
• Next smallest is SPAC → Annenberg
• Next smallest is Tech → Annenberg ( creates a subtour, therefore skip )
• Next smallest is Anneberg → Foster-Walker ( creates a subtour, therefore skip )
• Next smallest is SPAC → Tech ( creates a subtour, therefore skip )
• Next smallest is Tech → Foster-Walker
• Next smallest is Annenberg → SPAC ( creates a subtour, therefore skip )
• Next smallest is Foster-Walker → Annenberg ( creates a subtour, therefore skip )
• Next smallest is Tech → SPAC ( creates a subtour, therefore skip )
• Next smallest is Foster-Walker → Tech ( creates a subtour, therefore skip )
• Next smallest is SPAC → Foster-Walker ( creates a subtour, therefore skip )
• Next smallest is Foster-Walker → SPAC

So, the student would walk 2.40 miles in the following order: Foster-Walker → SPAC → Annenberg → Tech → Foster-Walker

As we can see in the figure to the right, the heuristic methods did not give the optimal solution. That is not to say that heuristics can never give the optimal solution, just that it is not guaranteed.

Both the optimal and the nearest neighbor algorithms suggest that Annenberg is the optimal first building to visit. However, the optimal solution then goes to SPAC, while both heuristic methods suggest Tech. This is in part due to the large cost of SPAC → Foster-Walker. The heuristic algorithms cannot take this future cost into account, and therefore fall into that local optimum.

We note that the nearest neighbor and greedy algorithms give solutions that are 11.4% and 5.3%, respectively, above the optimal solution. In the scale of this problem, this corresponds to fractions of a mile. We also note that neither heuristic gave the worst case result, Foster-Walker → SPAC → Tech → Annenberg → Foster-Walker.

Only tour building heuristics were used. Combined with a tour improvement algorithm (such as 2-opt or simulated annealing), we imagine that we may be able to locate solutions that are closer to the optimum.

The exact algorithm used was complete enumeration, but we note that this is impractical even for 7 nodes (6! or 720 different possibilities). Commonly, the problem would be formulated and solved as an ILP to obtain exact solutions.

• Vanderbei, R. J. (2001). Linear programming: Foundations and extensions (2nd ed.). Boston: Kluwer Academic.
• Schrijver, A. (n.d.). On the history of combinatorial optimization (till 1960).
• Matai, R., Singh, S., & Lal, M. (2010). Traveling salesman problem: An overview of applications, formulations, and solution approaches. In D. Davendra (Ed.), Traveling Salesman Problem, Theory and Applications . InTech.
• Junger, M., Liebling, T., Naddef, D., Nemhauser, G., Pulleyblank, W., Reinelt, G., Rinaldi, G., & Wolsey, L. (Eds.). (2009). 50 years of integer programming, 1958-2008: The early years and state-of-the-art surveys . Heidelberg: Springer.
• Cook, W. (2007). History of the TSP. The Traveling Salesman Problem . Retrieved from http://www.math.uwaterloo.ca/tsp/history/index.htm
• Punnen, A. P. (2002). The traveling salesman problem: Applications, formulations and variations. In G. Gutin & A. P. Punnen (Eds.), The Traveling Salesman Problem and its Variations . Netherlands: Kluwer Academic Publishers.
• Laporte, G. (1992). The traveling salesman problem: An overview of exact and approximate algorithms. European Journal of Operational Research, 59 (2), 231–247.
• Goyal, S. (n.d.). A suvey on travlling salesman problem.

Navigation menu

Travelling Salesman Problem

Introduction

The classical travelling salesman problem (TSP) asks the following question: “Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?” It is a classical NP-hard problem in combinatorial optimization, important in theoretical computer science and operations research.

It turns out that it could be formulated as a linear programming problem . In this blog post, I would like to implement a linear programming solver for the TSP problem.

Miller-Tucker-Zemlin (MTZ) Integer Linear Programming Formulation

There are two notable TSP integer linear programming formulations, Miller-Tucker-Zemlin (MTZ) formulation and the Dantzig-Fulkerson-Johnson (DFJ) formulation. We will be focusing on the MTZ formulation, as it is easier to program using the existing integer linear programming library.

Suppose we have $n$ cities, from $1$ to $n$. We define a binary square matrix $X \in \{0,1\}^{n \times n}$, where

$$ x_{ij} = \begin{cases} 1 & \text{if the path goes from city $i$ to city $j$}\\ 0 & \text{otherwise}\\ \end{cases} \\ $$

and a distance square matrix $C \in \mathbb{R}^{n \times n}$, where $c_{ij}$ is the distance from city $i$ to city $j$.

It is trivial to construct the integer linear programming optimization problem with the following constraints for the TSP problem.

$$ \DeclareMathOperator*{\argmin}{argmin} \DeclareMathOperator*{\argmax}{argmax} \argmin_{x_{ij}, \forall i,j \in [1,n]} \sum_{i=1}^{n} \sum_{j \neq i, j=1}^{n} c_{ij} x_{ij} $$

$$ \begin{gather} x_{ij} \in {0,1} \quad \forall i,j \in [1,n] \\ \sum_{i=1, i \neq j}^{n} x_{ij} = 1 \quad \forall j \in [1,n] \\ \sum_{j=1, j \neq i}^{n} x_{ij} = 1 \quad \forall i \in [1,n] \\ \end{gather} $$

However, with these constraints, we will likely have subtours in our solution, which violates the TSP setting that the travelling salesman has to return to the original city. Subtours are just the incorrect TSP solution which contains several directed cycles. For example, suppose we have six cities, $1, 2, 3, 4, 5, 6$, without additional constraints, $x_{1,2}=1, x_{2,3}=1, x_{3,1}=1, x_{4,5}=1, x_{5,6}=1, x_{6,4}=1$ ($1 \rightarrow 2 \rightarrow 3 \rightarrow 1$, $4 \rightarrow 5 \rightarrow 6 \rightarrow 4$) are one of the valid solutions for optimization but they are incorrect for the TSP settings.

To prevent subtours, Miller, Tucker, and Zemlin introduces additional auxiliary integer variables $u_2, u_3, \cdots, u_n$ and additional constraints.

$$ \begin{gather} u_i \in \mathbb{Z} \quad \forall i \in [2,n] \\ 1 \leq u_i \leq n - 1 \quad 2 \leq i \leq n \\ u_i - u_j + n x_{ij} \leq n - 1 \quad 2 \leq i \neq j \leq n \\ \end{gather} $$

With the constraints, if there are more than one directed cycles, at least one cycle will not contain node $1$ and the inequality of the $u$ variables will not be satisfied. For the previous incorrect TSP solution, we will have $u_4 < u_5 < u_6 < u_4$.

Also notice that linear function is both convex and concave (please show a simple proof on your own), which implies that every local optimum for the linear function is a global optimum. This means that the optimum solution from linear programming solver for the TSP problem is global optimum.

Install Dependencies

We will install and use pulp and glpk linear programming solvers to solve the TSP problems.

TSP Integer Linear Programming Solver Python Implementation

We implemented a brute force TSP solver and an integer linear programming TSP solver, and verified the correctness of the two solvers on symmetric TSP problems. The two solvers could also be used for asymmetric TSP problems.

TSP Problem Solver Execution

Running the following program will print out the solution for the TSP problem in the terminal.

Although the linear programming solver is much faster ($100\times$) than the brute force solver for the TSP problems in Python when the number of nodes is small, the linear programming solver will still hang as the number of nodes becomes larger ($\geq 23$) because the number of variables and constraints grow dramatically.

• Travelling Salesman Problem - Wikipedia
• Teaching Integer Programming Formulations Using the Traveling Salesman Problem

https://leimao.github.io/blog/Travelling-Salesman-Problem/

Licensed under

Like this article support the author with.

• 1 Introduction
• 2.1 Miller-Tucker-Zemlin (MTZ) Integer Linear Programming Formulation
• 2.2 Install Dependencies
• 2.3 TSP Integer Linear Programming Solver Python Implementation
• 2.4 TSP Problem Solver Execution
• 3 Conclusion
• 4 Reference

Academia.edu no longer supports Internet Explorer.

To browse Academia.edu and the wider internet faster and more securely, please take a few seconds to  upgrade your browser .

Enter the email address you signed up with and we'll email you a reset link.

• We're Hiring!
• Help Center

The traveling salesman problem: A Linear programming formulation of

2006, Computing Research Repository

Related Papers

Radoslaw Hofman

]). Article refers not only to model itself, but also to ability of extension of proposed model to be correct.

farhan kamali

this paper about TSP

ACM SIGACT News

William Springer

Jérôme Monnot

Dinand Tampubolon

Elhammoumi Youssef

The multiple traveling salesman problem (mTSP) is a generalization of the well-known traveling salesman problem (TSP), where more than one salesman is allowed to be used in the solution. Moreover, the characteristics of the mTSP seem more appropriate for real-life applications, and it is also possible to extend the problem to a wide variety of vehicle routing problems (VRPs) by incorporating some additional side constraints. Although there exists a wide body of the literature for the TSP and the VRP, the mTSP has not received the same amount of attention. The purpose of this survey is to review the problem and its practical applications, to highlight some formulations and to describe exact and heuristic solution procedures proposed for this problem.

Bezalel Gavish

• Computer Science

Valeriu Ungureanu

RELATED PAPERS

바카라그림장〃〃ETE333。COM〃〃더클래스카지노

Human Organization

Lenore Manderson

María García Antuña

Antonietta Bagnardi

Tami Vaisman

Revista USP

Abilio Guerra

Sainsmat : Jurnal Ilmiah Ilmu Pengetahuan Alam

yunita putri

Mahadevappa Hunasikatti

Toxin Reviews

Acta Limnologica Brasiliensia

Maria Carmo Calijuri

Hommes & migrations

Khursheed Wadia

Hugo Trejo González

Crime Science

anna murovskaya

Hematological Oncology

Analytical Sciences

Ian McKinnon

Sosio e-Kons

nina Herlina

Journal of Pharmaceutical Policy and Practice

hanik badriyah hidayati

Biochemical and Biophysical Research Communications

Stephanie Hamilton

Nepalese Journal of Ophthalmology

Meenakshi Wadhwani

Daila Pombo

hcommons.org

Charles E . Peck Jr.

16th International Conference on Advanced Communication Technology

muhammad bilal

Shadows of War

See More Documents Like This

RELATED TOPICS

•   We're Hiring!
•   Help Center
• Find new research papers in:
• Health Sciences
• Earth Sciences
• Cognitive Science
• Mathematics
• Academia ©2024

Modeling and solving the Traveling Salesman Problem with Python and Pyomo

In this post 1 , we will go through one of the most famous Operations Research problem, the Traveling Salesman Problem (TSP). The problem asks the following question:

Given a set of cities and the distances between each pair of them, what is the shortest route (tour) that visits each one once and returns to the origin city?

An integer linear programming formulation

The TSP may be formulated as an integer linear programming (ILP) model. In the following, we develop the well known Miller-Tucker-Zemlin (MTZ) formulation . Although it is not the most computationally efficient, it is one of the easiest to code.

Label the cities as $1, …, n$, in which $n$ is the total number of cities and arbitrarily assume 1 as the origin. Define the decisions variables :

$$ x_{ij} = \begin{cases} & 1 \quad \text{ if the route includes a direct link between cities } i \text{ and } j, \\ & 0 \quad \text{ otherwise}. \end{cases} $$

In addition, for each city $i = 1, 2, …, n$, let $u_i \in \mathbb{R}^+$ be an auxiliary variable and let $c_{ij}$ be the distance between cities $i$ and $j$. Then, the MTZ formulation to the TSP is the following: $$ \begin{align} \text{min} \quad & \sum_{i = 1}^{n} \sum_{j = 1, j \neq i}^{n} c_{ij} x_{ij}, \\ \text{subject to} \\ & \sum_{i=1, i \neq j}^{n} x_{ij} = 1, \quad j=1,2,…,n,\\ & \sum_{j=1, j \neq i}^{n} x_{ij} = 1, \quad i=1,2,…,n,\\ & u_i - u_j + n x_{ij} \leq n-1, \quad 2 \leq i \neq j \leq n, \\ & x_{ij} \in \{0,1\} \quad i, j =1,2,…,n, \quad i \neq j, \\ & u_i \in \mathbb{R}^+ \quad i=1,2,…,n. \\ \end{align} $$

In the formulation above, notice that the first set of equalities requires that each city is arrived at from exactly one other city, and the second set of equalities requires that from each city there is a departure to exactly one next city. Notice that these constraints do not guarantee the formation of a single tour encompassing all cities , allowing the formation of subtours. In order to exclude subtour solutions, the third constraint set is needed. These are known as the MTZ subtour elimination constraints .

Introducing Pyomo

To solve the TSP we will make use of Pyomo, which is a Python-based open-source optimization modeling language . If you had experience with any programing language (especially Python), modeling and solving a problem with Pyomo will be a simple task.

Pyomo allows you to choose among a variety of integer linear programming solvers, both open-source and commercial. For this post, we will make use of the CPLEX IBM Solver, to solve the MTZ formulation of the TSP. Feel free to use any other solver for ILP.

Data reading

The first step is to enter the data. This means to provide a distance matrix (or cost matrix), which gives the pairwise distances between cities.

For pedagogical and pratical purposes, we will use a cost matrix for $n = 17$ cities ( click here to download the file ). The file can be read in Python in the following way:

The variables cost_matrix and n contain the cost matrix and the number of cities, respectively. Now we will be able to call these elements when defining constraints.

Model building

To use Pyomo and solve the problem we need to make a single import:

Now we can initialize the model:

• ConcreteModel() creates the model;
• RangeSet(n) creates an index from 1 to n;
• RangeSet(2,n) creates an index from 2 to n.

Decision variables

The decision variables are declared in the following way:

Var(model.N,model.M, within=pyEnv.Binary) creates $n$ binary decision variables of size $m$;

Var(model.N, within=pyEnv.NonNegativeIntegers,bounds=(0,n-1)) creates $n$ non-negative integer decision variables that can only assume values between 0 and $n-1$.

Cost matrix

Next, we must provide the model with the cost matrix:

in which Param(modelo.N, model.M,initialize=lambda model, i, j: cost_matrix[i-1][j-1]) provides a $n \times m$ parameter to the model using a lambda function.

Objective function

After defining all the variables and provide the parameters, we are able to declare the objective function:

First we create a Python function that returns our objective function. Notice that we used the list comprehension technique. If you’re not familiar with it, this page gives a pretty good tutorial.

Objective(rule=obj_func,sense=pyEnv.minimize) creates the objective function of the model and sets its optimization direction (maximize or minimize). In the TSP we want to minimize total cost, so that we set sense=pyEnv.minimize .

Constraints

Constraints are declared in a way very similar to the objective function. The first constraint set, which ensures that each city is arrived at from exactly one other city can be formulated in the following way:

in which Constraint(model.M,rule=rule_const1) creates $m$ constraints defined by rule_const1 .

The second constraint set, which ensures that from each city there is a departure to exactly one next city can be formulated by:

in which Constraint(model.N,rule=rule_const2) creates $n$ constraints defined by rule_const2 .

The third and last constraint set correspond to the MTZ subtour elimination constraints:

in which Constraint(model.U,Model.N,rule=rule_const3) creates $u \times n$ constraints defined by the rule_const3 .

A rule type function must provide a Pyomo object, so that’s why we had to write a weird else condition.

Finally, we can print the entire model in the screen by calling:

in which pprint() prints de entire model (it might not be a good idea if the model is too big). Alternatively, we can use pprint(filename=’file.txt’) to print the model in a specific file.

Solving the model

In order to solve the model, we must have a previously installed solver, since Pyomo is just a modeling language. We will use the widely known commercial solver IBM CPLEX , but you can use many other commercial and non-commercial solvers, such as Gurobi, GLPK, CBC, etc.

The following code creates an instance of the solver and then solves the model:

in which SolverFactory(‘cplex’) initializes the solver instance and solve(model, tee= False) solves the model. Setting tee = False disables the solver’s log messages. In order to enable it, just set tee= True . Figure below shows the results returned by the solver:

In order see the values of the decision variables, we can do as the following:

The figure below shows only the variables for which $x_{ij} = 1$.

Then, the optimal tour starting from city 1 is $$ \begin{align} & 1 \to 17 \to 8 \to 9 \to 4 \to 5 \to 15 \to 7 \to 16 \to 6 \to \\ & \to 13 \to 10 \to 11 \to 2 \to 14 \to 3 \to 12 \to 1 \end{align} $$

In practice

The TSP is a widely studied prototypical NP- hard problem. The number of possible tours increases as a factorial of the number of cities. The MTZ-based formulation cannot obtain optimal solutions to large instances in acceptable wall clock times, since its linear relaxation is very weak. There are alternative approaches which can obtain optimal or very good solutions to large instances. Concorde is an exact algorithm based on Dantzig's cutting plane method which has obtained an optimal tour for an instance with 85900 cities. Alternatively, very good tours may be obtained by using heuristics such as LKH or simulated annealing.

Therefore, the TSP is considered a solved problem in practice . However, the more general class of vehicle routing problems (VRP), which include other constraints absent in the classical TSP, is far from being satisfactorily solved. To name a few constraints found in real problems from the many possible: multiple vehicles with limited capacity, multiple depots, time windows, fractional loads, stochastic demands and heterougenous fleets. The combination of these constraints give rise to different problems with varying degrees of difficulty.

To find more examples of Pyomo you can go to their GitHub page. In addition, you can find a Pyomo manual in Portuguese in my own GitHub page.

This post is an adaptation of an article originally published in Medium. ↩︎

Claudemir Woche V. C.

Industrial mathematics.

Undergraduate in industrial mathematics. His interests include mathematical programming application and Python programming.

Help Center Help Center

• Help Center
• Trial Software
• Product Updates
• Documentation

Traveling Salesman Problem: Solver-Based

This example shows how to use binary integer programming to solve the classic traveling salesman problem. This problem involves finding the shortest closed tour (path) through a set of stops (cities). In this case there are 200 stops, but you can easily change the nStops variable to get a different problem size. You'll solve the initial problem and see that the solution has subtours. This means the optimal solution found doesn't give one continuous path through all the points, but instead has several disconnected loops. You'll then use an iterative process of determining the subtours, adding constraints, and rerunning the optimization until the subtours are eliminated.

For the problem-based approach, see Traveling Salesman Problem: Problem-Based .

Problem Formulation

Formulate the traveling salesman problem for integer linear programming as follows:

Generate all possible trips, meaning all distinct pairs of stops.

Calculate the distance for each trip.

The cost function to minimize is the sum of the trip distances for each trip in the tour.

The decision variables are binary, and associated with each trip, where each 1 represents a trip that exists on the tour, and each 0 represents a trip that is not on the tour.

To ensure that the tour includes every stop, include the linear constraint that each stop is on exactly two trips. This means one arrival and one departure from the stop.

Generate Stops

Generate random stops inside a crude polygonal representation of the continental U.S.

Calculate Distances Between Points

Because there are 200 stops, there are 19,900 trips, meaning 19,900 binary variables (# variables = 200 choose 2).

Generate all the trips, meaning all pairs of stops.

Calculate all the trip distances, assuming that the earth is flat in order to use the Pythagorean rule.

With this definition of the dist vector, the length of a tour is

dist'*x_tsp

where x_tsp is the binary solution vector. This is the distance of a tour that you try to minimize.

Create Graph and Draw Map

Represent the problem as a graph. Create a graph where the stops are nodes and the trips are edges.

Display the stops using a graph plot. Plot the nodes without the graph edges.

Constraints

Create the linear constraints that each stop has two associated trips, because there must be a trip to each stop and a trip departing each stop. This formulation works when the problem has at least three stops.

Binary Bounds

All decision variables are binary. Now, set the intcon argument to the number of decision variables, put a lower bound of 0 on each, and an upper bound of 1.

Optimize Using intlinprog

The problem is ready for solution. To suppress iterative output, turn off the default display.

Create a new graph with the solution trips as edges. To do so, round the solution in case some values are not exactly integers, and convert the resulting values to logical .

Visualize Solution

As can be seen on the map, the solution has several subtours. The constraints specified so far do not prevent these subtours from happening. In order to prevent any possible subtour from happening, you would need an incredibly large number of inequality constraints.

Subtour Constraints

Because you can't add all of the subtour constraints, take an iterative approach. Detect the subtours in the current solution, then add inequality constraints to prevent those particular subtours from happening. By doing this, you find a suitable tour in a few iterations.

Eliminate subtours with inequality constraints. An example of how this works is if you have five points in a subtour, then you have five lines connecting those points to create the subtour. Eliminate this subtour by implementing an inequality constraint to say there must be less than or equal to four lines between these five points.

Even more, find all lines between these five points, and constrain the solution not to have more than four of these lines present. This is a correct constraint because if five or more of the lines existed in a solution, then the solution would have a subtour (a graph with n nodes and n edges always contains a cycle).

Detect the subtours by identifying the connected components in Gsol , the graph built with the edges in the current solution. conncomp returns a vector with the number of the subtour to which each edge belongs.

Include the linear inequality constraints to eliminate subtours, and repeatedly call the solver, until just one subtour remains.

Solution Quality

The solution represents a feasible tour, because it is a single closed loop. But is it a minimal-cost tour? One way to find out is to examine the output structure.

The smallness of the absolute gap implies that the solution is either optimal or has a total length that is close to optimal.

Related Topics

• Traveling Salesman Problem: Problem-Based

MATLAB Command

You clicked a link that corresponds to this MATLAB command:

Run the command by entering it in the MATLAB Command Window. Web browsers do not support MATLAB commands.

Select a Web Site

Choose a web site to get translated content where available and see local events and offers. Based on your location, we recommend that you select: .

• Switzerland (English)
• Switzerland (Deutsch)
• Switzerland (Français)
• 中国 (English)

You can also select a web site from the following list:

How to Get Best Site Performance

Select the China site (in Chinese or English) for best site performance. Other MathWorks country sites are not optimized for visits from your location.

• América Latina (Español)
• Canada (English)
• United States (English)
• Belgium (English)
• Denmark (English)
• Deutschland (Deutsch)
• España (Español)
• Finland (English)
• France (Français)
• Ireland (English)
• Italia (Italiano)
• Luxembourg (English)
• Netherlands (English)
• Norway (English)
• Österreich (Deutsch)
• Portugal (English)
• Sweden (English)
• United Kingdom (English)

Asia Pacific

• Australia (English)
• India (English)
• New Zealand (English)

Contact your local office