啟發式演算法解決旅行商問題

A. 急求 蟻群混合遺傳演算法在matlab上的實現以解決TSP旅行商的問題 小弟感激不盡

建立m文件
function [R_best,L_best,L_ave,Shortest_Route,Shortest_Length]=ACATSP(C,NC_max,m,Alpha,Beta,Rho,Q)

%%-------------------------------------------------------------------------

%% 主要符號說明

%% 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; %i=j時不計算，應該為0，但後面的啟發因子要取倒數，用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 %開始時置0

J(Jc)=k;

Jc=Jc+1; %訪問的城市個數自加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); %cumsum，元素累加即求和

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); %開始距離為0，m*1的列向量

for i=1:m

R=Tabu(i,:);

for j=1:(n-1)

L(i)=L(i)+D(R(j),R(j+1)); %原距離加上第j個城市到第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); %開始時信息素為n*n的0矩陣

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);

%此次循環在路徑（i，j）上的信息素增量

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)); %找到最佳路徑（非0為真）

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,'r')

title('平均距離和最短距離') %標題

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)],'g')

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)],'g')

hold on

end

title('旅行商問題優化結果 ')

建m文件
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)],'g')

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)],'g')

hold on

end

title('TSP問題優化結果 ')

命令窗口運行
C=[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
];
m=31;Alpha=1;Beta=5;Rho=0.1;NC_max=200;Q=100;
[R_best,L_best,L_ave,Shortest_Route,Shortest_Length]=ACATSP(C,NC_max,m,Alpha,Beta,Rho,Q)

B. 用遺傳演算法 解決旅行商問題，進化1000代，結果產生新解的代數一直都在剛開始幾代，而且不是最佳解，怎麼解

首先，遺傳演算法實際使用上並不能保證得到全局最優解。
出現這種情況說明遺傳演算法在開始前幾代已經達到並陷入一個局部解。而演算法的相關參數，例如交叉，變異概率等無法使演算法跳出局部解。因此可以嘗試改變遺傳演算法的參數。

C. 想問一下什麼是vrp問題，什麼是tsp問題

、旅行商問題（Traveling Salesman Problem, TSP）

這個問題字面上的理解是：有一個推銷員，要到n個城市推銷商品，他要找出一個包含所有n個城市的具有最短路程的環路。

TSP的歷史很久，最早的描述是1759年歐拉研究的騎士周遊問題，即對於國際象棋棋盤中的64個方格，走訪64個方格一次且僅一次，並且最終返回到起始點。

TSP由美國RAND公司於1948年引入，該公司的聲譽以及線性規劃這一新方法的出現使得TSP成為一個知名且流行的問題。

2、中國郵遞員問題（Chinese Postman Problem CPP）

同樣的問題，在中國還有另一個描述方法：一個郵遞員從郵局出發，到所轄街道投遞郵件，最後返回郵局，如果他必須走遍所轄的每條街道至少一次，那麼他應如何選擇投遞路線，使所走的路程最短？這個描述之所以稱為中國郵遞員問題， 因為是我國學者管梅古谷教授於1962年提出的這個問題並且給出了一個解法。

3、「一筆畫」問題（Drawing by one line）

還有一個用圖論語言的描述方式：平面上有n個點，用最短的線將全部的點連起來。稱為「一筆畫」問題。

4、配送路線問題（Route of Distribution）

TSP問題在物流中的描述是對應一個物流配送公司，欲將n個客戶的訂貨沿最短路線全部送到。如何確定最短路線。

TSP問題最簡單的求解方法是枚舉法。它的解是多維的、多局部極值的、趨於無窮大的復雜解的空間，搜索空間是n個點的所有排列的集合，大小為（n-1）！。可以形象地把解空間看成是一個無窮大的丘陵地帶，各山峰或山谷的高度即是問題的極值。求解TSP，則是在此不能窮盡的丘陵地帶中攀登以達到山頂或谷底的過程。

5、多迴路運輸問題（Vehicle Routing Problem, VRP）

多迴路運輸問題在物流中的解釋是對一系列客戶的需求點設計適當的路線，使車輛有序地通過它們，在滿足一定的約束條件下，如貨物需求量、發送量、交發貨時間、車輛載重量限制、行駛里程限制、時間限制等等，達到一定的優化目標，如里程最短、費用最少、時間最短，車隊規模最少、車輛利用率高。

VRP問題和TSP問題的區別在於：客戶群體的數量大，只有一輛車或一條路徑滿足不了客戶的需求，必須是多輛交通工具以及運輸工具的行車順序兩個問題的求解。相對於TSP問題，VRP問題更復雜，求解更困難，但也更接近實際情況。

6、多個旅行商問題（Multiple TSP）

由於限制條件的增加，TSP問題可以衍生出多個旅行商問題（MTSP），就是一個出發點，m個旅行商的TSP，即所訪問的客戶沒有需求，車輛沒有裝載的限制，優化目標就是要遍歷所有的客戶，達到總里程最短。

VRP問題是MTSP問題的普遍化，當客戶的需求不僅僅是被訪問，而是有一定容積和重量的商品的裝載和卸載，涉及到不同種類和型號或不同載重量車輛的調度策略時，MTSP問題轉換為VRP問題。

7、最近鄰點法（Nearest Neighbor）

這是一種用於解決TSP問題的啟發式演算法。方法簡單，但得到的解並不十分理想，可以作為進一步優化的初始解。求解的過程一共四步：首先從零點開始，作為整個迴路的起點，然後找到離剛剛加入到迴路的上一節點最近的一個節點，並將其加入到迴路中。重復上一步，直到所有的節點都加入到迴路中，最後，將最後一個加入的節點和起點連接起來，構成了一個TSP問題的解。

8、最近插入法（Nearest Insertion）

最近插入法是另一個TSP問題的求解方法。它的求解過程也是4步：首先從一個節點出發，找到一個最近的節點，形成一個往返式子迴路；在剩下的節點中，尋找一個離子迴路中某一節點最近的節點，再在子迴路中找到一個弧，使弧的兩端節點到剛尋找到的最近節點的距離之和減去弧長的值最小，實際上就是把新找到的節點加入子迴路以後使得增加的路程最短，就把這個節點增加到子迴路中。重復以上過程，直到所有的節點都加入到子迴路中。最近插入法比最近鄰點法復雜，但可以得到相對比較滿意的解。

9、節約里程法（Saving Algorithm）

節約演算法是用來解決運輸車輛數目不確定的VRP問題的最有名的啟發式演算法。它的核心思想是依次將運輸問題中的兩個迴路合並為一個迴路，每次使合並後的總運輸距離減小得幅度最大，直到達到一輛車的裝載限制時，再進行下一輛車的優化。優化過程分為並行方式和串列方式兩種。

10、掃描演算法（Sweep Algorithm）

它也是求解車輛數目不限制的VRP問題的啟發式演算法。求解過程同樣是4步：以起始點為原點建立極坐標系，然後從最小角度的兩個客戶開始建立一個組，按逆時針方向將客戶逐個加入到組中，直到客戶的需求總量超出了車輛的載重定額。然後建立一個新的組，繼續該過程，直到將全部客戶都加入到組中

D. 什麼是tsp問題，數學模型中的一種模型問題

Traveling Saleman Problem 旅行商問題
「旅行商問題」常被稱為「旅行推銷員問題」，是指一名推銷員要拜訪多個地點時，如何找到在拜訪每個地點一次後再回到起點的最短路徑。規則雖然簡單，但在地點數目增多後求解卻極為復雜。以42個地點為例，如果要列舉所有路徑後再確定最佳行程，那麼總路徑數量之大，幾乎難以計算出來。多年來全球數學家絞盡腦汁，試圖找到一個高效的演算法，近來在大型計算機的幫助下才取得了一些進展。 TSP問題在物流中的描述是對應一個物流配送公司，欲將n個客戶的訂貨沿最短路線全部送到。如何確定最短路線。 TSP問題最簡單的求解方法是枚舉法。它的解是多維的、多局部極值的、趨於無窮大的復雜解的空間，搜索空間是n個點的所有排列的集合，大小為（n-1）。可以形象地把解空間看成是一個無窮大的丘陵地帶，各山峰或山谷的高度即是問題的極值。求解TSP，則是在此不能窮盡的丘陵地帶中攀登以達到山頂或谷底的過程。

具體參見網路
http://ke..com/view/1162183.htm

多個旅行商同時出發的問題稱為MTSP問題。設立虛點轉化為TSP即可求解。
數學模型是可以用線性規劃來描述，但是在多項式求解時間內無解，所以才出現了各種啟發式演算法，什麼遺傳演算法，模擬退火，蟻群演算法之類的

E. 求最短路徑問題 送貨郎問題

最佳答案檢舉 模型一：利用「圖」的知識，將送貨點抽象為「圖」中是頂點，由於街道和坐標軸平行，即任意兩頂點之間都有路。在此模型中，將兩點之間的路線權值賦為這兩點橫縱坐標之和。如A（x1，y1），B（x2，y2）兩點，則權值為Q=|x2-x1|+|y2-y1|。並利用計算機程序對以上結果進行了校核。經典的Dijkstra演算法和 Floyd演算法思路清楚、 方法簡便,但隨著配送點數的增加,計算的復雜性以配送點數的平方增加,並具有一定的主觀性. 所以本研究在利用動態規劃法的基礎上引入撲食搜索法的原理,提高輛車的裝載率,從而減少車輛的需求,達到降低成本的目的.

模型二：根據題意（B題），建立動態規劃的數學模型。然後用動態規劃的知識求得最優化結果。

根據所建立的兩個數學模型，對滿足設計要求的送貨策略和費用最省策略進行了模擬，在有標尺的坐標系中得到了能夠反映運送最佳路線的模擬圖。最後，對設計規范的合理性進行了充分和必要的論證。

快遞公司送貨策略

1 問題的提出

在快遞公司送貨策略中，確定業務員人數和各自的行走路線是本題的關鍵。這個問題可以描述為:一中心倉庫(或配送調度中心) 擁有最大負重為25kg的業務員m人, 負責對30個客戶進行貨物分送工作, 客戶i 的貨物需求為以知 , 求滿足需求的路程

最短的人員行駛路徑,且使用盡量少的人數,並滿足以下條件:

1) 每條配送路徑上各個客戶的需求量之和不超過個人最大負重。

2) 每個客戶的需求必須滿足, 且只能由一個人送貨.

3）每個業務員每天平均工作時間不超過6小時，在每個送貨點停留的時間為10分鍾，途中速度為25km/h。

4）為了計算方便，我們將快件一律用重量來衡量，平均每天收到總重量為184.5千克。

處於實際情況的考慮, 本研究中對人的最大行程不加限制.本論文試圖從最優化的角度，建立起滿足設計要求的送貨的數學模型，藉助於計算機的高速運算與邏輯判斷能力，求出滿足題意（B題）要求的結果。

2 問題的分析

2. 1根據題意（B題）的要求，每個人的工作時間不超過6小時，且必須從早上9點鍾開始派送，到當天17點之前（即在8小時之內）派送完畢。

表一列出了題中任意兩配送點間的距離。

表一：任意兩點間的距離矩陣

因為距離是對稱的，即從送貨點i到送貨點j的距離等於從j到i的距離。記作：di,j.

表二給出了產品的需求，為了完成配送任務，每個人在工作時間范圍內，可以承擔兩條甚至更多的配送線路。表中給出了送貨點編號，快件量T，以及送貨點的直角坐標。

表二
對於上述的路線確定和費用優化問題，應用如下啟發
從公司總部配出一個人，到任意未配送的送貨點，然後將這個人配到最近的未服務的送貨點范圍之內的鄰居，並使送貨時間小於6小時，各送貨點總重量不超過25kg。

繼續上述指派，直到各點總重量超過25kg，或者送貨時間大於6小時。最後業務員返回總部，記錄得到的可行行程（即路線）。

對另一個業務員重復上述安排，直到沒有未服務的送貨點。對得到的可行的行程安排解中的每一條路徑，求解一個旅行商問題，決定訪問指派給每一條行程的業務員的順序，最小化運輸總距離。得到可行解的行程安排解後退出。

上面的方法通過以下兩種方法實現：

（1） 每一個行程的第一個送貨點是距離總部最近的未服務的送貨點。用這種方法，即可得到一組運行路線，總的運行公里數，以及總費用。

（2） 每一個行程的第一個送貨點是距離總部最遠的未服務的送貨點。然後以該點為基準，選擇距它最近的點，加上約束條件，也可得到一組數據。

然後比較兩組結果，通過函數擬合即可得到最優化結果。

3 模型假設

（1）假設每個人的送貨路線一旦確定，再不更改。

（2）送貨期間，每個人相互之間互不影響。

（3）如果到某一個點距離最近的點不至一個，就按下面的方法進行確定：考慮該點需求的快件量，將其從大到小依次排列，快件量需求大者優先，但路線中各點總重量加上該點的快件量超過25kg的上限時，該點捨去。如距離4最近的點有2，5，6，7四個點，其中，0-1-3-4路線易確定，且各點重量之和為 19.5kg，因此對於2，7兩點，直接捨去，選5最合適。

4 符號說明

A：所有配送點的集合，A={0，1，2，3，…….，n}，其中0代表配送中心

m: 業務員人數

C：任意一點到原點（總部）的距離

C總：表示一條路線所運行的總公里數

i,j: 表示送貨點，如i點，j點

K：表示K條路線

qi: 點i的需求量，q0=0，表示總部的需求量

B總K: K條路線的總運行費用

X：校核時的適應度

Xij: 業務員路線安排

5 模型的建立及求解

5.1 TSP模型的數學描述為：

其頂點集合為A

頂點間的距離為C={Cij| i,j∈N,1≤i,j≤n}

m n

min ∑ ∑ CijXij

i=1j=1

滿足

n

∑ Xij=1,ⅰi=1,2,⋯n

j=1

m

∑ Xij=1,j=1,2,⋯n

j=1

Xij∈{0,1}, i=1,2⋯n,j=1,2⋯n，而根據題意，任意兩點之間都有通路，即不存在Xij=0的情況。

根據上述所列的啟發式方法生成一個行程安排解。每一個行程的第一個送貨點是距離總部最近的未服務的送貨點。

第一條行程中訪問了節點0-1-3-4-5-0，是因為1距離原點最近，因此由1

出發，3是距離1點最近的點，而且兩處快件量之和為14kg，小於每個人最大負重量，可以繼續指配。接著，4是距離3最近的點，而且三處快件量之和為 19.5kg，仍小於25kg,還可以繼續指配。在剩下未服務送貨點中，5距離4最近（其實距離4最近的點有2，5，6，7四個點，然後考慮該點需求的快件量，將其從大到小依次排列，快件量需求大者優先，但超過25kg上限的點捨去。這里2，7被捨去，故選擇了5）總快件量之和為24kg。再繼續擴充，發現就會超出「25kg」這個上限，因此選擇返回，所以0-1-3-4-5就為第一條路線所含有的送貨點。

現在0-1-3-4-5這四個送貨點之間的最優訪問路徑安排就是一個典型的單迴路問題。可以通過單迴路運輸模型-TSP模型求解。一般而言，比較簡單的啟發式演算法求解TSP模型求解有最鄰近法和最近插入法兩種。由RosenkrantzStearns等人在1977年提出的最近插入法，能夠比最近鄰點法，取得更滿意的解。由於0-1-3-0 已經先構成了一個子迴路，現在要將節點4 插入，但是客戶4有三個位置可以插入，現在分析將客戶4插入到哪裡比較合適:

1.插入到（0，1）間，C總= 7+4+5+1+4+9=30。

2.插入到（1，3）間，C總=5+6+4+9=24。

3.插入到（3，0）間，C總=5+4+4+11=24。

比較上述三種情況的增量，插入到（3，0）間和（1，3）間增量最小，考慮到下一節點插入時路程最小問題，所以應當將4插入到送貨點3和總部0之間。接下來，用同樣的方法，將5插到4和0之間，能使該條路線總路程最小，該路線總路程為32km，歷時1.96667h。結果子迴路為T= {0-1-3-4-5-0}.因為街道平行於坐標軸方向，所以它就是最優化路線。

第二條行程這中，由於所剩下節點中，2距離0點最近，因此由2出發，就可以找到最近點13，接著是7，然後6.這樣，第二條優化路線0-2-13-7-6-0就確定了。用這種方法，依次可確定以下剩餘六條路線。

具體參看如下圖表三（一，二，三，……為路線編號；總重量為該路線所有

節點快件量之和）：

由啟發式方法得到的可行的行程安排解一：

表三

直觀的具體路線圖如下：

圖一

然後，根據所經歷的時間進行劃分，確定運送人數。在工作時間小於6小時的前提下，可作如下分類：

這樣，將確定的五種組合情況分別分配給五個業務員去送即可。

這個解是第一個中間最好解。在選擇可行解1每條行程中的第一個送貨點時，選擇了距離總部最近的未服務的點。接下去通過選擇距離倉庫最遠的未服務的點為每條行程的第一個客戶生成了可行解2。為了方便遺傳演算法的分析，編號將連續進行。如果繼續增加的新的標簽的行程和前面可行解1 中的重復，就是用原先的標簽號。

由啟發式方法得到的可行的行程安排解二：

表四

直觀的具體路線圖如下：

圖二

注意：通過上述方法，最後剩兩個點1，9還沒有被列入路線。於是問題就出來了，如何將這兩個點插入進這八條路線？

除第十條路線之外，其餘各條均能將9號點納入，而1號點沒有辦法納進去，只能作為第十七條路線出現。那麼，9號點應納入哪一條呢？顯然，納入第十六條比較合適，原因是他對總路程的大小沒影響，順便可以帶上。

由此可以看到，可行解2沒有替代中間最優解，以總路程518km,歷時25.72h高於492km和24.68h。

通過對上面的兩個可行解進行交叉操作。其中每個解的行程已經按照他們送每千克快件量在每一千米的路程范圍內的送貨成本的大小降序重新排列，這個參數是對每一行程質量的比較好的測度。本文以此作為適應值（X）。

在對兩個解中的行程進行交叉分析時，根據適應值計算的接受每條行程的概率附加到每條行程上。P(X)=Ke- λx ，然後通過設定參數對結果進行擬合。具體而言。如果一條行程的選擇概率P(select)值至少和exel相應行的隨機概率一樣大，那麼他就被選擇出來可能在交叉分析中被包括進去。

在本題中，根據上述要求，求出了兩種可行解，但是由於本題的特殊性（即街道和坐標軸平行），兩條路徑中沒有相同的運行路線，也就是說最終的擬合結果就是解一的結果。因此，可行解一就是本題中的最優解。

至此，B題中的第一問已經解決了。即需要5個業務員，每個業務員的運行線路如下：

第一個人：0-1-3-4-5-0和0-18-26-28-0；

第二個人：0-2-13-7-6-0和0-19-25-24-0；

第三個人：0-10-12-8-9-0和0-16-17-20-14-0；

第四個人：0-22-32-23-15-11-0；

第五個人：0-27-29-30-0.

總的運行公里數為：C總K=32+42+42+72+68+56+88+92=492km。

5．2 下面我們求解B題中的第二個問題：

根據上面設計的最優化路線，容易算出每條路線運行費用及運行第二時間（這里的第二時間指的是在問題2中的新速度的前提下算出的）。具體參看下錶五和表六：

表五

表六

從表五和表六的比較來看，解法二以總費用15241.3元和總時間27.36667h高於解一的12208.4元和26.26667h。因此我們選擇了解一的優化結果。

從上表（表五）很容易看出：B總K=12208.4元。然後根據第二時間的大小，我對運行路線和人員個數做以下調整，具體參看錶五。這樣，就需六個人就才能完成任務。考慮到人員工作時間不能一邊倒（即部分線路組合工作時間太長，部分太短）的情況，每個人的組合路線如下：

第一個人：0-1-3-4-5-0和0-19-25-24-0；

第二個人：0-2-13-7-6-0和0-10-12-8-9-0；

第三個人：0-16-17-20-14-0；

第四個人：0-22-32-23-15-11-0；

第五個人：0-18-26-28-0；

第六個人：0-27-29-30-0。

F. 採用准確優化技術和啟發式優化技術解決一個問題會存在什麼不同

採用准確優化技術和啟發式優化技術解決一個問題會存在的不同之處：

①確定性演算法和隨機性演算法是目前求解優化問題的方法。隨機性演算法一般是對社會行為和自然現象的模擬，具有對優化函數的解析性質要求低的特點，甚至對無顯示解析表達式的問題也可以求解，能較好解決優化中的雜訊、不可微、高維等問題。

②啟發式演算法作為隨機性演算法的一種，其良好的應用更加快了人們對各種優化方法的探索腳步。 近些年來不斷有學者將分形應用於優化中來，試圖運用分形思想來處理復雜的優化問題。

③其中，分形演算法通過對可行域的分形分割來尋優，是一種新穎的確定性演算法，但其局限性較大，只適用於低維簡單的問題，對於當今社會中高維復雜問題則幾乎無能為力，也使得該演算法的影響力微乎其微。

④啟發式技術是基於特徵值掃描技術上的升級,與傳統反病毒特徵值掃描技術相比,優點在於對未知病毒的防禦.是特徵值識別技術質的飛躍。

(6)啟發式演算法解決旅行商問題擴展閱讀

啟發式：簡化虛擬機和簡化行為判斷引擎的結合 Heuristic(啟發式技術=啟發式掃描+啟發式監控) 重點在於特徵值識別技術上的更新、解決單一特徵碼比對的缺陷.目的不在於檢測所有的未知病毒,只是對特徵值掃描技術的補充.主要針對：木馬、間諜、後門、下載者、已知病毒(PE病毒)的變種。

一、啟發式發展方向

現代啟發式演算法的研究,在理論方面還處於不斷發展中,新思想和新方法仍不斷出現。分析目前的現狀和發展方向,其發展方向有如下幾個方面:

①整理歸納分散的研究成果,建立統一的演算法體系結構。

②在現有的數學方法(模式定理、編碼策略、馬爾可夫鏈理論、維數分析理論、復制遺傳演算法理論、二次動力系統理論、傅立葉分析理論、分離函數理論、Walsh函數分析理論)的基礎上尋求新的數學工具。

③開發新的混合式演算法及開展現有演算法改進方面的研究。

④研究高效並行或分布式優化演算法。

二、啟發式演算法演算法機制特點

現代啟發式演算法在優化機制方面存在一定的差異,但在優化流程上卻具有較大的相似性,均是一種「鄰域搜索」結構。演算法都是從一個(一組)初始解出發,在演算法的關鍵參數的控制下通過鄰域函數產生若干鄰域解,按准則(確定性、概率性或混沌方式)更新當前狀態,而後按關鍵參數修改准則調整關鍵參數，一直優化到最優結果。

G. 想用動態規劃演算法解決旅行商（TSP）問題，麻煩指點下方法和思路，詳細點，謝謝1

http://hi..com/__%D2%E5__/blog/item/d6326f1fcbdb4eff1ad576d8.html
http://liouwei20051000285.blog.163.com/blog/static/25236742009112242726527/
以上都是動態規劃解決TSP問題的，但是個人覺得不是太好，建議你去了解一下遺傳演算法，很容易懂，網上有很詳細的講解。希望你學到知識

H. 旅行商問題的問題解法

旅行推銷員的問題，我們稱之為巡行（Tour），此種問題屬於NP-Complete的問題，所以旅行商問題大多集中在啟發式解法。Bodin（1983）等人將旅行推銷員問題的啟發式解法分成三種：
1、途程建構法（Tour Construction Proceres）
從距離矩陣中產生一個近似最佳解的途徑，有以下幾種解法：
1）最近鄰點法（Nearest Neighbor Procere）：一開始以尋找離場站最近的需求點為起始路線的第一個顧客，此後尋找離最後加入路線的顧客最近的需求點，直到最後。
2）節省法（Clark and Wright Saving）：以服務每一個節點為起始解，根據三角不等式兩邊之和大於第三邊之性質，其起始狀況為每服務一個顧客後便回場站，而後計算路線間合並節省量，將節省量以降序排序而依次合並路線，直到最後。
3）插入法（Insertion proceres）：如最近插入法、最省插入法、隨意插入法、最遠插入法、最大角度插入法等。
2、途程改善法（Tour Improvement Procere）
先給定一個可行途程，然後進行改善，一直到不能改善為止。有以下幾種解法：
1）K-Opt(2/3 Opt)：把尚未加入路徑的K條節線暫時取代目前路徑中K條節線，並計算其成本（或距離），如果成本降低（距離減少），則取代之，直到無法改善為止，K通常為2或3。
2）Or-Opt：在相同路徑上相鄰的需求點，將之和本身或其它路徑交換且仍保持路徑方向性，並計算其成本（或距離），如果成本降低（距離減少），則取代之，直到無法改善為止。
3、合成啟發法（Composite Procere）
先由途程建構法產生起始途程，然後再使用途程改善法去尋求最佳解，又稱為兩段解法（two phase method）。有以下幾種解法：
1）起始解求解+2-Opt：以途程建構法建立一個起始的解，再用2-Opt的方式改善途程，直到不能改善為止。
2）起始解求解+3-Opt：以途程建構法建立一個起始的解，再用3-Opt的方式改善途程，直到不能改善為止。

I. 想問一下什麼是vrp問題，什麼是tsp問題

、旅行商問題（TRAVELING SALESMAN PROBLEM, TSP） 這個問題字面上的理解是：有一個推銷員，要到N個城市推銷商品，他要找出一個包含所有N個城市的具有最短路程的環路。 TSP的歷史很久，最早的描述是1759年歐拉研究的騎士周遊問題，即對於國際象棋棋盤中的64個方格，走訪64個方格一次且僅一次，並且最終返回到起始點。 TSP由美國RAND公司於1948年引入，該公司的聲譽以及線性規劃這一新方法的出現使得TSP成為一個知名且流行的問題。 2、中國郵遞員問題（CHINESE POSTMAN PROBLEM CPP） 同樣的問題，在中國還有另一個描述方法：一個郵遞員從郵局出發，到所轄街道投遞郵件，最後返回郵局，如果他必須走遍所轄的每條街道至少一次，那麼他應如何選擇投遞路線，使所走的路程最短？這個描述之所以稱為中國郵遞員問題， 因為是 國學者管梅古谷教授於1962年提出的這個問題並且給出了一個解法。 3、「一筆畫」問題（DRAWING BY ONE LINE） 還有一個用圖論語言的描述方式：平面上有N個點，用最短的線將全部的點連起來。稱為「一筆畫」問題。 4、配送路線問題（ROUTE OF DISTRIBUTION） TSP問題在物流中的描述是對應一個物流配送公司，欲將N個客戶的訂貨沿最短路線全部送到。如何確定最短路線。 TSP問題最簡單的求解方法是枚舉法。它的解是多維的、多局部極值的、趨於無窮大的復雜解的空間，搜索空間是N個點的所有排列的集合，大小為（N-1）！。可以形象地把解空間看成是一個無窮大的丘陵地帶，各山峰或山谷的高度即是問題的極值。求解TSP，則是在此不能窮盡的丘陵地帶中攀登以達到山頂或谷底的過程。 5、多迴路運輸問題（VEHICLE ROUTING PROBLEM, VRP） 多迴路運輸問題在物流中的解釋是對一系列客戶的需求點設計適當的路線，使車輛有序地通過它們，在滿足一定的約束條件下，如貨物需求量、發送量、交發貨時間、車輛載重量限制、行駛里程限制、時間限制等等，達到一定的優化目標，如里程最短、費用最少、時間最短，車隊規模最少、車輛利用率高。 VRP問題和TSP問題的區別在於：客戶群體的數量大，只有一輛車或一條路徑滿足不了客戶的需求，必須是多輛交通工具以及運輸工具的行車順序兩個問題的求解。相對於TSP問題，VRP問題更復雜，求解更困難，但也更接近實際情況。 6、多個旅行商問題（MULTIPLE TSP） 由於限制條件的增加，TSP問題可以衍生出多個旅行商問題（MTSP），就是一個出發點，M個旅行商的TSP，即所訪問的客戶沒有需求，車輛沒有裝載的限制，優化目標就是要遍歷所有的客戶，達到總里程最短。 VRP問題是MTSP問題的普遍化，當客戶的需求不僅僅是被訪問，而是有一定容積和重量的商品的裝載和卸載，涉及到不同種類和型號或不同載重量車輛的調度策略時，MTSP問題轉換為VRP問題。 7、最近鄰點法（NEAREST NEIGHBOR） 這是一種用於解決TSP問題的啟發式演算法。方法簡單，但得到的解並不十分理想，可以作為進一步優化的初始解。求解的過程一共四步：首先從零點開始，作為整個迴路的起點，然後找到離剛剛加入到迴路的上一節點最近的一個節點，並將其加入到迴路中。重復上一步，直到所有的節點都加入到迴路中，最後，將最後一個加入的節點和起點連接起來，構成了一個TSP問題的解。 8、最近插入法（NEAREST INSERTION） 最近插入法是另一個TSP問題的求解方法。它的求解過程也是4步：首先從一個節點出發，找到一個最近的節點，形成一個往返式子迴路；在剩下的節點中，尋找一個離子迴路中某一節點最近的節點，再在子迴路中找到一個弧，使弧的兩端節點到剛尋找到的最近節點的距離之和減去弧長的值最小，實際上就是把新找到的節點加入子迴路以後使得增加的路程最短，就把這個節點增加到子迴路中。重復以上過程，直到所有的節點都加入到子迴路中。最近插入法比最近鄰點法復雜，但可以得到相對比較滿意的解。 9、節約里程法（SAVING ALGORITHM） 節約演算法是用來解決運輸車輛數目不確定的VRP問題的最有名的啟發式演算法。它的核心思想是依次將運輸問題中的兩個迴路合並為一個迴路，每次使合並後的總運輸距離減小得幅度最大，直到達到一輛車的裝載限制時，再進行下一輛車的優化。優化過程分為並行方式和串列方式兩種。 10、掃描演算法（SWEEP ALGORITHM） 它也是求解車輛數目不限制的VRP問題的啟發式演算法。求解過程同樣是4步：以起始點為原點建立極坐標系，然後從最小角度的兩個客戶開始建立一個組，按逆時針方向將客戶逐個加入到組中，直到客戶的需求總量超出了車輛的載重定額。然後建立一個新的組，繼續該過程，直到將全部客戶都加入到組中

記得採納啊