旅行商
① 旅行商問題的簡介
「旅行商問題」常被稱為「旅行推銷員問題」，是指一名推銷員要拜訪多個地點時，如何找到在拜訪每個地點一次後再回到起點的最短路徑。規則雖然簡單，但在地點數目增多後求解卻極為復雜。以42個地點為例，如果要列舉所有路徑後再確定最佳行程，那麼總路徑數量之大，幾乎難以計算出來。多年來全球數學家絞盡腦汁，試圖找到一個高效的演算法TSP問題在物流中的描述是對應一個物流配送公司，欲將n個客戶的訂貨沿最短路線全部送到。如何確定最短路線。
TSP問題最簡單的求解方法是枚舉法。它的解是多維的、多局部極值的、趨於無窮大的復雜解的空間，搜索空間是n個點的所有排列的集合，大小為（n-1）！。可以形象地把解空間看成是一個無窮大的丘陵地帶，各山峰或山谷的高度即是問題的極值。求解TSP，則是在此不能窮盡的丘陵地帶中攀登以達到山頂或谷底的過程。
② 旅行商問題的解法思路
旅行推銷員的問題，我們稱之為巡行（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語言程序：旅行商求最短路徑問題
在無向完全圖中，對於任意兩個頂點vi和vj，我們可以在多項式時間內找到vi和vj這兩個頂點之間的所有路徑，選擇其中路程最短的一條，令S[i,j]表示vi和vj這兩個頂點之間最短距離的那條路徑。搜索路徑S[i,j]，找到vi到達的在S[i,j]上的第一個頂點，記該頂點為vk，將其記錄在數組中R[][]，遞歸查找vi到vk和vk到vj的最短路徑及其相應權值，最後將數組D[]中的頂點和權值之和列印出來即為所求，並用畫圖函數將行經過程畫出。
④ 在線旅行商有哪些經營模式，與傳統旅行社有哪些不同，各自的優劣勢
在線旅行優劣：
優勢：在線旅行掌握著非常好的資源，包括各方資本的投入和高端人才的招攬;同時，全國范圍的覆蓋面和客流量令其可以在供應商那裡能得到更好的優惠;另外，消費者有一種「網上東西更便宜」的固有認知，網路購物已經成為社會化的消費潮流。
劣勢：線上旅行經營競爭壓力大，旅遊品牌眾多，生存空間勢必會變得更小。
傳統旅行社優劣：
優勢：傳統旅行社基礎的在線旅遊其服務卻更加人性化，遊客在網上看中某一旅遊產品，可就近到門店進行具體咨詢和後續報名，獲得面對面的靈活服務，而不會出現每次打去客服電話，都遇到不同工號的客服人員的尷尬。
劣勢：傳統旅行社還需額外增添門店租金和日常管理所需資金，成本難免增加。
(4)旅行商擴展閱讀：
旅行社可實現線上線下管理與營銷同步發展
根據自身產品與用戶需求，清晰明確的個性主題設置、詳細的旅遊線路攻略，以及秒殺、拼團、砍價、優惠券等多種營銷玩法，讓用戶省去大量的時間與精力去網路各種路線攻略，不用再三猶豫，用戶只需刷刷小程序，就能省去很多干擾項，快速促進消費。
旅行社商家直接完成用戶數據的獲取，通過旅行社系統後台提供的產品、庫存、客戶、供應商、財務管理，以及微信小程序營銷推廣、線上交易和數據分析服務功能，可以多維度決策分析、深度數據研究，直觀展示數據，方便企業及時的調整營銷策略，製造出更加符合用戶需求的產品和內容。
⑤ 旅行商問題的研究歷史
旅行商問題字面上的理解是：有一個推銷員，要到n個城市推銷商品，他專要找出一個屬包含所有n個城市的具有最短路程的環路。
TSP的歷史很久，最早的描述是1759年歐拉研究的騎士周遊問題，即對於國際象棋棋盤中的64個方格，走訪64個方格一次且僅一次，並且最終返回到起始點。
TSP由美國RAND公司於1948年引入，該公司的聲譽以及線性規劃這一新方法的出現使得TSP成為一個知名且流行的問題。
⑥ 數學建模TSP問題（旅行商問題）與CPP問題（中國郵遞員問題）有什麼區別
旅行商問題，即TSP問題（Travelling Salesman Problem）又譯為旅行推銷員問題、貨郎擔問題，是數學領域中著名問題之一。假設有一個旅行商人要拜訪n個城市，他必須選擇所要走的路徑，路徑的限制是每個城市只能拜訪一次，而且最後要回到原來出發的城市。路徑的選擇目標是要求得的路徑路程為所有路徑之中的最小值。
中國郵遞員問題
著名圖論問題之一。郵遞員從郵局出發送信，要求對轄區內每條街，都至少通過一次，再回郵局。在此條件下，怎樣選擇一條最短路線？此問題由中國數學家管梅谷於1960年首先研究並給出演算法，故名。
⑦ 旅行商問題的線性規劃解法為什麼很少有相關資料
這是一個空間解析幾何代數化的問題。 你可以將三個小區的煤量 作為空間上的同一出發點的向量 而向量的夾角就是運輸量的飽和率。這樣可以首先確定一個幾何模型，在通過向量的結點分別計算同一平面上的內積空間可以得到第2個煤場的矢量。這樣求運輸量最小的方法就是要求A矢量和B矢量的形成的銳角的度數 ，角越大 運輸量越小
⑧ 多旅行商問題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的巡遊路徑，路線圖和收斂曲線如下：
⑨ 多旅行商python 代碼
寫的太簡單了，表示還不明白什麼是多旅行商