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

조회 수: 2 (최근 30일)
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?
  댓글 수: 2
Alan Weiss
Alan Weiss 2018년 12월 18일
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
Venky Suriyanarayanan 2018년 12월 18일
편집: Venky Suriyanarayanan 2018년 12월 18일
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.

댓글을 달려면 로그인하십시오.

채택된 답변

Bruno Luong
Bruno Luong 2018년 12월 18일
편집: Bruno Luong 2018년 12월 18일
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)
  댓글 수: 1
Venky Suriyanarayanan
Venky Suriyanarayanan 2018년 12월 19일
편집: Venky Suriyanarayanan 2018년 12월 19일
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

댓글을 달려면 로그인하십시오.

추가 답변 (0개)

카테고리

Help CenterFile Exchange에서 Genetic Algorithm에 대해 자세히 알아보기

제품


릴리스

R2017a

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by