C++ Neural Networks and Fuzzy Logic: Preface

The TSP in a Nutshell

For n cities to visit, let X

ij

 be the variable that has value 1 if the salesperson goes from city i to city j and value

0 if the salesperson does not go from city i to city j. Let d

ij

 be the distance from city i to city j. The traveling

salesperson problem (TSP) is stated as follows:

Minimize the linear objective function: 

subject to:

 for each j=1, …, n (linear constraint)

C++ Neural Networks and Fuzzy Logic:Preface

Traveling Salesperson Problem

334

---

 for each i=1, …, n (linear constraint)

wX

ij

 for 1 for all i and j (integer constraint)

This is a 0−1 integer linear programming problem.

Solution via Neural Network

This section shows how the linear and integer constraints of the TSP are absorbed into an objective function

that is nonlinear for solution via Neural network.

The first consideration in the formulation of an optimization problem is the identification of the underlying

variables and the type of values they can have. In a traveling salesperson problem, each city has to be visited

once and only once, except the city started from. Suppose you take it for granted that the last leg of the tour is

the travel between the last city visited and the city from which the tour starts, so that this part of the tour need

not be explicitly included in the formulation. Then with n cities to be visited, the only information needed for

any city is the position of that city in the order of visiting cities in the tour. This suggests that an ordered

n−tuple is associated with each city with some element equal to 1, and the rest of the n – 1 elements equal to

0. In a neural network representation, this requires n neurons associated with one city. Only one of these n

neurons corresponding to the position of the city, in the order of cities in the tour, fires or has output 1. Since

there are n cities to be visited, you need n

2

 neurons in the network. If these neurons are all arranged in a

square array, you need a single 1 in each row and in each column of this array to indicate that each city is

visited but only once.

Let x

ij

 be the variable to denote the fact that city i is the jth city visited in a tour. Then x

ij

 is the output of the

jth neuron in the array of neurons corresponding to the ith city. You have n

2

 such variables, and their values

are binary, 0 or 1. In addition, only n of these variables should have value 1 in the solution. Furthermore,

exactly one of the x’s with the same first subscript (value of i) should have value 1. It is because a given city

can occupy only one position in the order of the tour. Similarly, exactly one of the x’s with the same second

subscript (value of j) should have value 1. It is because a given position in the tour can be only occupied by

one city. These are the constraints in the problem. How do you then describe the tour? We take as the starting

city for the tour to be city 1 in the array of cities. A tour can be given by the sequence 1, a, b, c, …, q,

indicating that the cities visited in the tour in order starting at 1 are, a, b, c, …, q and back to 1. Note that the

sequence of subscripts a, b, …, q is a permutation of 2, 3, … n – 1, x

a1

=1, x

b2

=1, etc.

Having frozen city 1 as the first city of the tour, and noting that distances are symmetric, the distinct number

of tours that satisfy the constraints is not n!, when there are n cities in the tour as given earlier. It is much less,

namely, n!/2n. Thus when n is 10, the number of distinct feasible tours is 10!/20, which is 181,440. If n is 15,

it is still over 43 billion, and it exceeds a trillion with 17 cities in the tour. Yet for practical purposes there is

not much comfort knowing that for the case of 13 cities, 13! is over 6.2 billion and 13!/26 is only 239.5

million—it is still a tough combinatorial problem.

Previous Table of Contents Next

Copyright ©

 IDG Books Worldwide, Inc.

C++ Neural Networks and Fuzzy Logic:Preface

Solution via Neural Network

335

---