旅行商問題
A. 旅行商問題的變種問題
您好，您提的問題很實際。的確，在旅途過程中，乘坐怎樣的交通工具即省錢又省時這是個相當重要的問題，這個問題解決的好與壞直接影響到旅行的心情。
根據您提供的條件，可以知道您與同學以射線形出遊，即玩完每個景點都要回到小區。實際上，您如果採取這種出遊方式無論乘什麼交通工具，交通費用肯定會很高，原因之一就是您每次都要回到小區，之二就是不知道您要具體到哪些景點，因為即使是同一個景點，到達那裡多數也會有很多不同路線，交通費用當然也不一樣。
如果你計劃去的N個景點可以有幾個相連，即從小區先到A，從A再到B,玩完B又可以到C，這樣路費相對會節省些，同時也可以節省時間，但是對個人體力要求不叫高，當然也要看您的時間是否來得及。
您此次出行的目的是促進新生之間的交流，而不是真正的去旅行，所以我建議您，把N個景點拆分開，1-2個景點做為一周的活動內容，每周都有不同的景點，每到一個景點大家可以借景發揮，設計一些小游戲，聊聊談談，玩玩鬧鬧，也不至於為了趕景點那麼疲憊，同學之間也有充分的交流，等到下一周換其他景點，也能激起同學們的熱情。這樣比一下子都逛完好些。
在活動當中，主要組織者要特別熟悉交通線路，多找些相同景點的不同線路，以備應急只用；做好每次出行的費用記錄，回來後及時向大家公布；同時把途中能涉及到的問題羅列清楚，拆分任務，讓出行的每個同學都參與到旅行的計劃與實施中來，這也是一種很好的交流過程，一旦大家都積極的參與，每個人了解了旅行的意義，就會珍惜大家在一起的時光，而不是只有組織者忙前忙後，沒做周到的地方其他同學還埋怨。
旅行不僅僅只有快樂，很多時候煩惱也盡在其中，希望您和同學們能借旅行的機會好好交流，增進彼此的信任與理解，在歡樂與煩惱中慢慢成長。
B. 旅行商問題的解法思路
旅行推銷員的問題，我們稱之為巡行（Tour），此種問題屬於NP完全問題（NP-Complete），所以旅行商問題大多集中在啟發式解法。Bodin（1983）等人將旅行推銷員問題的啟發式解法分成三種： 從距離矩陣中產生一個近似最佳解的途徑，有以下幾種解法：如近鄰點法（Nearest Neighbor Procere）：一開始以尋找離場站最近的需求點為起始路線的第一個顧客，此後尋找離最後加入路線的顧客最近的需求點1、，直到最後。
2、節省法（Clark and Wright Saving）：以服務每一個節點為起始解，根據三角不等式兩邊之和大於第三邊之性質，其起始狀況為每服務一個顧客後便回場站，而後計算路線間合並節省量，將節省量以降序排序而依次合並路線，直到最後。
3、插入法（Insertion proceres）：如今插入法、最省插入法、隨意插入法、最遠插入法、最大角度插入法等。 先給定一個可行途程，然後進行改善，一直到不能改善為止。有以下幾種解法：
1、K-Opt(2/3 Opt)：把尚未加入路徑的K條節線暫時取代如今路徑中K條節線，並計算其成本（或距離），如果成本降低（距離減少），則取代之，直到無法改善為止，K通常為2或3。
2、Or-Opt：在相同路徑上相鄰的需求點，將之和本身或其它路徑交換且仍保持路徑方向性，合成啟發法
先由途程建構法產生起始途程，然後再使用途程改善法去尋求最佳解，又稱為兩段解法（two phase method）。有以下幾種解法：
1、起始解求解+2-Opt：以途程建構法建立一個起始的解，再用2-Opt的方式改善途程，直到不能改善為止。
2、起始解求解+3-Opt：以途程建構法建立一個起始的解，再用3-Opt的方式改善途程，直到不能改善為止。
C. 起始點已知的旅行商問題種群怎樣初始化
「旅行商問題」常被稱為「旅行推銷員問題」，是指一名推銷員要拜訪多個地點時，如何找到在拜訪每個地
TSP問題
點一次後再回到起點的最短路徑。規則雖然簡單，但在地點數目增多後求解卻極為復雜。以42個地點為例，如果要列舉所有路徑後再確定最佳行程，那麼總路徑數量之大，幾乎難以計算出來。多年來全球數學家絞盡腦汁，試圖找到一個高效的演算法TSP問題在物流中的描述是對應一個物流配送公司，欲將n個客戶的訂貨沿最短路線全部送到。如何確定最短路線。
TSP問題最簡單的求解方法是枚舉法。它的解是多維的、多局部極值的、趨於無窮大的復雜解的空間，搜索空間是n個點的所有排列的集合，大小為（n-1）！。可以形象地把解空間看成是一個無窮大的丘陵地帶，各山峰或山谷的高度即是問題的極值。求解TSP，則是在此不能窮盡的丘陵地帶中攀登以達到山頂或谷底的過程。
D. 多旅行商問題matlab程序
[code]function [R_best,L_best,L_ave,Shortest_Route,Shortest_Length]=ACATSP(C,NC_max,m,Alpha,Beta,Rho,Q)
%%=========================================================================
%% ACATSP.m
%% Ant Colony Algorithm for Traveling Salesman Problem
%% ChengAihua,PLA Information Engineering University,ZhengZhou,China
%% Email:[email protected]
%% All rights reserved
%%-------------------------------------------------------------------------
%% 主要符號說明
%% C n個城市的坐標，n×2的矩陣
%% NC_max 最大迭代次數
%% m 螞蟻個數
%% Alpha 表徵信息素重要程度的參數
%% Beta 表徵啟發式因子重要程度的參數
%% Rho 信息素蒸發系數
%% Q 信息素增加強度系數
%% R_best 各代最佳路線
%% L_best 各代最佳路線的長度
%%=========================================================================
%%第一步：變數初始化
n=size(C,1);%n表示問題的規模（城市個數）
D=zeros(n,n);%D表示完全圖的賦權鄰接矩陣
for i=1:n
for j=1:n
if i~=j
D(i,j)=((C(i,1)-C(j,1))^2+(C(i,2)-C(j,2))^2)^0.5;
else
D(i,j)=eps;
end
D(j,i)=D(i,j);
end
end
Eta=1./D;%Eta為啟發因子，這里設為距離的倒數
Tau=ones(n,n);%Tau為信息素矩陣
Tabu=zeros(m,n);%存儲並記錄路徑的生成
NC=1;%迭代計數器
R_best=zeros(NC_max,n);%各代最佳路線
L_best=inf.*ones(NC_max,1);%各代最佳路線的長度
L_ave=zeros(NC_max,1);%各代路線的平均長度
while NC<=NC_max%停止條件之一：達到最大迭代次數
%%第二步：將m只螞蟻放到n個城市上
Randpos=[];
for i=1:(ceil(m/n))
Randpos=[Randpos,randperm(n)];
end
Tabu(:,1)=(Randpos(1,1:m))';
%%第三步：m只螞蟻按概率函數選擇下一座城市，完成各自的周遊
for j=2:n
for i=1:m
visited=Tabu(i,1:(j-1));%已訪問的城市
J=zeros(1,(n-j+1));%待訪問的城市
P=J;%待訪問城市的選擇概率分布
Jc=1;
for k=1:n
if length(find(visited==k))==0
J(Jc)=k;
Jc=Jc+1;
end
end
%下面計算待選城市的概率分布
for k=1:length(J)
P(k)=(Tau(visited(end),J(k))^Alpha)*(Eta(visited(end),J(k))^Beta);
end
P=P/(sum(P));
%按概率原則選取下一個城市
Pcum=cumsum(P);
Select=find(Pcum>=rand);
to_visit=J(Select(1));
Tabu(i,j)=to_visit;
end
end
if NC>=2
Tabu(1,:)=R_best(NC-1,:);
end
%%第四步：記錄本次迭代最佳路線
L=zeros(m,1);
for i=1:m
R=Tabu(i,:);
for j=1:(n-1)
L(i)=L(i)+D(R(j),R(j+1));
end
L(i)=L(i)+D(R(1),R(n));
end
L_best(NC)=min(L);
pos=find(L==L_best(NC));
R_best(NC,:)=Tabu(pos(1),:);
L_ave(NC)=mean(L);
NC=NC+1
%%第五步：更新信息素
Delta_Tau=zeros(n,n);
for i=1:m
for j=1:(n-1)
Delta_Tau(Tabu(i,j),Tabu(i,j+1))=Delta_Tau(Tabu(i,j),Tabu(i,j+1))+Q/L(i);
end
Delta_Tau(Tabu(i,n),Tabu(i,1))=Delta_Tau(Tabu(i,n),Tabu(i,1))+Q/L(i);
end
Tau=(1-Rho).*Tau+Delta_Tau;
%%第六步：禁忌表清零
Tabu=zeros(m,n);
end
%%第七步：輸出結果
Pos=find(L_best==min(L_best));
Shortest_Route=R_best(Pos(1),:)
Shortest_Length=L_best(Pos(1))
subplot(1,2,1)
DrawRoute(C,Shortest_Route)
subplot(1,2,2)
plot(L_best)
hold on
plot(L_ave)
function DrawRoute(C,R)
%%=========================================================================
%% DrawRoute.m
%% 畫路線圖的子函數
%%-------------------------------------------------------------------------
%% C Coordinate 節點坐標，由一個N×2的矩陣存儲
%% R Route 路線
%%=========================================================================
N=length(R);
scatter(C(:,1),C(:,2));
hold on
plot([C(R(1),1),C(R(N),1)],[C(R(1),2),C(R(N),2)])
hold on
for ii=2:N
plot([C(R(ii-1),1),C(R(ii),1)],[C(R(ii-1),2),C(R(ii),2)])
hold on
end
設置初始參數如下：
m=31;Alpha=1;Beta=5;Rho=0.1;NC_max=200;Q=100;
31城市坐標為：
1304 2312
3639 1315
4177 2244
3712 1399
3488 1535
3326 1556
3238 1229
4196 1004
4312 790
4386 570
3007 1970
2562 1756
2788 1491
2381 1676
1332 695
3715 1678
3918 2179
4061 2370
3780 2212
3676 2578
4029 2838
4263 2931
3429 1908
3507 2367
3394 2643
3439 3201
2935 3240
3140 3550
2545 2357
2778 2826
2370 2975[/code]
運行後得到15602的巡遊路徑，路線圖和收斂曲線如下：
E. 旅行商問題的研究歷史
旅行商問題字面上的理解是：有一個推銷員，要到n個城市推銷商品，他專要找出一個屬包含所有n個城市的具有最短路程的環路。
TSP的歷史很久，最早的描述是1759年歐拉研究的騎士周遊問題，即對於國際象棋棋盤中的64個方格，走訪64個方格一次且僅一次，並且最終返回到起始點。
TSP由美國RAND公司於1948年引入，該公司的聲譽以及線性規劃這一新方法的出現使得TSP成為一個知名且流行的問題。
F. 旅行商問題 lingo 誰能幫我寫個程序！！！急！！！
這種tsp很簡單的，網上有很多例子，代碼考下來改下城市個數及相關的距離矩陣就可以了。。。
結果： 1-6-3-9-8-10-2-7-4-5-1
MODEL:
! Traveling Salesman Problem for the cities of
Atlanta, Chicago, Cincinnati, Houston, LA,
Montreal;
SETS:
CITY / 1..10 /: U; ! U( I) = sequence no. of city;
LINK( CITY, CITY):
DIST, ! The distance matrix;
X; ! X( I, J) = 1 if we use link I, J;
ENDSETS
DATA: !Distance matrix, it need not be symmetric;
DIST =
0 8 5 9 2 4 2 6 7 2
8 0 9 5 7 8 1 8 4 2
5 9 0 7 9 1 7 2 2 7
9 5 7 0 3 7 1 7 5 8
2 7 9 3 0 8 1 6 5 5
4 8 1 7 8 0 9 4 8 6
2 1 7 1 1 9 0 8 6 1
6 8 2 7 6 4 8 0 1 1
7 4 2 5 5 8 6 1 0 1
2 2 7 8 5 6 1 1 1 0;
ENDDATA
!The model:Ref. Desrochers & Laporte, OR Letters,
Feb. 91;
N = @SIZE( CITY);
MIN = @SUM( LINK: DIST * X);
@FOR( CITY( K):
! It must be entered;
@SUM( CITY( I)| I #NE# K: X( I, K)) = 1;
! It must be departed;
@SUM( CITY( J)| J #NE# K: X( K, J)) = 1;
! Weak form of the subtour breaking constraints;
! These are not very powerful for large problems;
@FOR( CITY( J)| J #GT# 1 #AND# J #NE# K:
U( J) >= U( K) + X ( K, J) -
( N - 2) * ( 1 - X( K, J)) +
( N - 3) * X( J, K)
);
);
! Make the X's 0/1;
@FOR( LINK: @BIN( X));
! For the first and last stop we know...;
@FOR( CITY( K)| K #GT# 1:
U( K) <= N - 1 - ( N - 2) * X( 1, K);
U( K) >= 1 + ( N - 2) * X( K, 1)
);
END
G. 非對稱旅行商問題是什麼意思
對稱就是說，任意兩個頂點a,b，從a到b的距離和從b到a是一樣的；非對稱就是這兩個距離不一定一樣。
H. 旅行商問題的線性規劃解法為什麼很少有相關資料
這是一個空間解析幾何代數化的問題。 你可以將三個小區的煤量 作為空間上的同一出發點的向量 而向量的夾角就是運輸量的飽和率。這樣可以首先確定一個幾何模型，在通過向量的結點分別計算同一平面上的內積空間可以得到第2個煤場的矢量。這樣求運輸量最小的方法就是要求A矢量和B矢量的形成的銳角的度數 ，角越大 運輸量越小
I. 旅行商問題C語言的求解
排序額外寫了一個字函數，結構清晰點。
Void change(int array[],int n) /*冒泡排序子函數，n是個數*/
{ int i, j, temp;
for(j=0;j<=(n-2);j++)
{ for(i=0;i<=(n-2-j);i++)
{ if (*(array+i)<*(array+i+1))
{temp=*array(i); /*指針操作，效率高*/
*array(i)=*(array+i+1) ;
*(array+i+1)=temp ;
}
}
}
} /* 排序函數結束*/
# include <stdio.h>
# define N 4
main ()
{ int a[N] , m ;
for(m=0 ; m<=N-1 ; m++)
{printf(「please give the a(%d) : 」, m ) ;
scanf(「%d」,(a+m)) ;
}
change (a, N ) ; //調用排序函數
printf(「 The array is OK : /n 」 ) ;
for (m=0 ; m<=N-1 ; m++) //由大到小排列
printf(「 %d 」, *(a+m) ) ;
} //主函數結束