Traveling Salesman Problem in LINGO
Traveling Salesman Problem (TSP) is a type of problem where you want to visit several cities such that minimize the traveled distance.
Imagine that you are a salesman in one company and you need to go door-to-door to market your product. On one fine day, you need to visit, let’s say, 15 customers in different cities, or in a different neighborhood. Now, you are trapped in a traveling salesman problem. Traveling salesman is a widely known optimization problem where you want to visit a set of customers such that, the travel distance can be minimized. TSP is NP-hard by nature, so we can only solve small instances using LINGO.
Dataset
We will implement the dataset from bays29.tsp with 29 nodes and berlin52.tsp with 52 nodes. The known solution for these datasets is 2020 and 7542 respectively.
Mathematical Formulation
TSP can be defined on a directed/undirected graph G = (V,A), with V = {1..n} is a set of city. An arc set associated cost matrix d(i,j) and x(i,j) is a decision variable with a value of 1 if and only if the salesman goes from i to j, 0 otherwise. We then use Miller-Zemlin-Tucker for the subtour elimination constraint. Our model was based on (Miller & Tucker & Zemlin, 1960) shown on (Benhida & Mir, 2018). Here is the formulation:
LINGO Implementation
The implementation is divided into 3 parts: defining the sets, data, objective function, and the rest of the constraint.
The Sets
Define the set Vertex and Arc. Vertex will contain all our nodes and arc is the link between (vertex, vertex). For the vertex, we will have an attribute of U which defines the order each vertex is visited (to avoid subtour). For the Arc, we bind variables of d and x.
SETS:
VERTEX:U;
ARC(VERTEX, VERTEX):D, X;
ENDSETS
The Data
For the data, we just need actually to define the cost matrix denoted by d. We then assign n with the number of nodes in our model.
DATA:
N = [Number of nodes];
VERTEX = 1..N;
D = [Enter your cost matrix here];
ENDDATA
The Objective Function
Same with the model.
MIN = @SUM(ARC(I,J) | I#NE#J: D(I,J)*X(I,J));
The Constraint
The rest are the same as the model.
@FOR(VERTEX(I): @SUM(VERTEX(J)|J#NE#I: X(I,J)) = 1);
@FOR(VERTEX(J): @SUM(VERTEX(I)|I#NE#J: X(I,J)) = 1);
@FOR(ARC(I,J): @BIN(X(I,J)));
@FOR(ARC(I,J) | I#NE#1 #AND# J#NE#1: U(I) — U(J) + N*X(I,J) <= N-1);
@FOR(VERTEX(I) |I#NE#1: U(I) >= 1);
@FOR(VERTEX(I) |I#NE#1: U(I) <= N-1);
Solution
The solution from bays29 is 2020 which is the same as the best-known result from TSPLIB. The time taken for the model is about a minute.
The solution for the berlin52.tsp dataset is 7570 and the running time for the model is around 4 minutes. Why is the solution much different from the known solution? Because I round up the number for the distance matrix to become integer.
Full LINGO Code
SETS:
VERTEX:U;
ARC(VERTEX, VERTEX):D, X;
ENDSETS
DATA:
N = [number of nodes];
VERTEX = 1..N;
D = [enter your cost matrix];
ENDDATA
MIN = @SUM(ARC(I,J) | I#NE#J: D(I,J)*X(I,J));
@FOR(VERTEX(I): @SUM(VERTEX(J)|J#NE#I: X(I,J)) = 1);
@FOR(VERTEX(J): @SUM(VERTEX(I)|I#NE#J: X(I,J)) = 1);
@FOR(ARC(I,J): @BIN(X(I,J)));
@FOR(ARC(I,J) | I#NE#1 #AND# J#NE#1: U(I) — U(J) + N*X(I,J) <= N-1);
@FOR(VERTEX(I) |I#NE#1: U(I) >= 1);
@FOR(VERTEX(I) |I#NE#1: U(I) <= N-1);
Closing
Thanks for reading, if you have any questions or corrections, please reach me in a comment or contact me via email in the profile. Don’t forget to give it a clap, and follow me for more about optimization.
Reference:
Miller, C.E.; Tucker, A.W. & Zemlin, R.A.(1960). Integer programming formulation of traveling salesman problems. Journal of Association for Computing Machinery, Vol. 7, pp. 326–9.
Benhida, S.; Mir, A. (2018). Generating subtour elimination constraints for the Traveling Salesman Problem. IOSR Journal of Engineering, Vol. 08, pp. 17–21.
