Can pareto optimality be used to solve the travelling salesman problem?

A city's co-ordinates are given by x (latitude) and y (longitude) and the shortest travel distance between many cities is given by the travelling salesman algorithm (FEX). How to find the route between different cities such that we get maximum x and minimum y?

[Alan Weiss]

Sorry, I don't understand your question. Can you write a formula to say what you mean, or else try to explain in different words? In particular, I do not understand what it means to find a route "between different cities such that we get maximum x and minimum y."

[Venky Suriyanarayanan]

Sorry about that Alan. I wanted to be brief with my words so did not elaborate a lot much. I am trying to apply the analogy of TSP in my research wherein I have 2 parameters (say A and B) and I study the effect of it on my system both individually as well as together.

When studying the two parameters individually, the TSP is essentially reduced to a 1 dimensional problem with number of points on a straight line.

For parameter A, eg x=ones(22,1) and y = -0.2 + (0.4)*rand(22,1). abc=[x,y]. After using the code travelling salesman algorithm (FEX) wherein userConfig = struct('xy',abc), the results can be seen by using plot(1:22,x(resultStruct.optroute),'-o r'). It can be seen that the arrangement is similar to sinusoidal arrangement (optimal solution for my system for parameter A).

In parameter B, eg x=ones(22,1) and z = 0.5*randi([1,5],22,1). I have changed the above open source code so that it now gives me the longest path. Using the same procedure as above, the arrangement is like a zigzag arrangement which is optimal solution for parameter B.

In the last case, I am trying to club the 2 parameters together. So x = -0.2 + (0.4)*rand(22,1) and y = 0.5*randi([1,5],22,1). If I use the TSP algorithm for distance maximisation, I see that both x and y is giving zigzag variation (which was expected). I would like to have y giving zigzag variation followed by a smoother variation of x which would be the true optimal of the problem.

How do we approach the problem? Since the two paramters individually have two conflicting optimal solution (Minimisation for A and Maximisation for B), is there a pareto optimal solution? Hope I am clear this time. If you require more details, please let me know. Thanks a lot for your time.

Answer 1

[Bruno Luong]

Just change the definition "distance" between 2 cities to, for example

d = sqrt((1/dx)^2 + dy^2) 

and feet it TSP algo.

Note that the classical eucidian distance is

d = sqrt(dx^2 + dy^2) 

[Venky Suriyanarayanan]

Hi Bruno. Thanks for your time. As per your suggestion, I did the following changes:

(1) Commented line number 127 in the original script i.e. %dmat = reshape(.....)

(2) Added the following lines below the commented line

aa1 = (xy(a,:)-xy(a',:));
aa2 = sqrt((1./aa1(:,1).^2) + aa1(:,2).^2);
dmat = reshape(aa2,npoints,npoints)

(3) If I add the line given by you, I get weird results. Or maybe I am making silly mistake in which case I would be glad if you could point out the mistake . Thanks again.

Edit: I am sorry, the code works well. It was a mistake by me that I did not get the correct results. Thanks a lot for your help. Have a good day

Regards,

Venky