校內(nèi)培訓(xùn)競賽2問題三修改

：然后選出1~30號貨物所送達的頂點間的最短路徑以及距離，再用二邊逐次修對Hamilton圈進30：228.18TSP問題，根據(jù)線路規(guī)劃的特點，基于過程中自動淘汰。經(jīng)過多次迭代求出其中耗時最短的路線即為所需結(jié)果，最終路線：228.18案進行路線的分劃，并根據(jù)最終求得結(jié)果的比較，得出前者方案更優(yōu)，因此選用第案送貨?？倳r間為：394.3分。背企業(yè)互不相通的單一方式以及郵政普遍服務(wù)那種保證送達，但時間長、問50124公里/小時，33分鐘交接計算等條件，要求合理模型假條件假假設(shè) 假設(shè)送貨員的送貨路線一旦確定就不在改變假設(shè)假設(shè) 假設(shè)送貨員到某送貨點后必須把該送貨點的快件送完假設(shè) 假設(shè)每個送貨點的貨物一次被送到，不會出現(xiàn)分批送到的情況假設(shè)假設(shè) 24公里/假設(shè)5 假設(shè) 假設(shè)同一地點有多件貨物也簡單按照每件3分鐘交接計算假設(shè) 假設(shè)送貨員只能按已知的連通線路行走，而不能走其它任何路線假設(shè) 假設(shè)送貨員在送貨的過程中互不影響假設(shè) 假設(shè)每一個送貨點由同一個送貨員送貨符 變量意xij

0-1 tntntWiW3

節(jié)點s和節(jié)點e之間的最短距離問題二中第n問題二中第n問題i的總路程(i1,2,3)問題3第i階段的總路程問題i的總時間(i1,2,3) 問題分的送貨行程最短。此即圖論中最佳路徑問題。而送貨路線問題可以理解為：已知起點和終圈（H圈。從而得出送貨員的最佳送貨方案。模型準問題一的基本算法及其相關(guān)概念Floyd算法的基本思想GV,E，V為頂點集合，En(n1)個頂V1,…,Vn。FloydViVj(1ijn)Vk(k1n)，并計算出只任取初始H圈

C0v1,v2,...vi,...vj,..vn,對所有的ij，1i1jn，若w(vivjw(vi1,vj1w(vivi1w(vjvj1,在C0中刪去邊(vivi1和(vjvj1而加入邊(vi,Cv1,v2,...,vi,vj,vj1,...,vi1,vj1,...,

和(vi1,j

，形成新的H圈C（２相關(guān)概念完備圖令G=(V,E)為一個無向圖，其中V=｜v1,v2,……，vn｜為頂點集合，E為Gew(e)w(e)為該邊的權(quán)。若任意兩點均有邊相連，則G為完備圖。哈圖設(shè)G=(V,E)是連通無向圖，經(jīng)過G的每個頂點正好一次的圈，稱為G的一條哈圈，簡稱H圈；含H圈的圖成為哈圖或H圖。最佳H圈在圖G=(V，E)中，權(quán)最小的哈圈稱為最佳H圈判定一個圖G=(V，E)是否存在哈圈是一個NP問題而它的完備圖G'=(V,E（E'中的每條邊（x,y）xyG中最短路徑的權(quán)）中一定存在哈圈所以在完備圖G'=(V,E')中尋找最佳H圈該過程采用二邊逐次修 在一個矩陣中，對它的第i行（列）到第j行（列）翻轉(zhuǎn)是以第i行（列）和j行（列的）中心位置為轉(zhuǎn)軸，旋轉(zhuǎn)180度，這樣：第i行（列）和第j行（列）的位置互換，第i+1行（列）和第j-1行（列）位置互換，……最后就會收斂到最適應(yīng)環(huán)境的一個“”上，它就是問題的最優(yōu)解。遺傳算法步驟1)編碼,創(chuàng)建初始2)中適應(yīng)度計根據(jù)適應(yīng)度選擇被選擇進行交叉繁殖繁殖出新的,回到第二)n-1模型建立針對問題1~30顯然送貨員能夠一次帶上所有貨物到達各送貨點，而且貨物要送達的送貨點總共為個本模型運用圖論中最佳路徑問題與最佳Ｈ圈中的相出發(fā)點O/5121個送貨點結(jié)合起來構(gòu)造完備圖。問題一需要從1~30號貨物送到指定地點并返回至O點，要求總時間T11（各貨物信息表）30

TW130 1其中：W11

W Wss1 nss

Wss

Wnnv

W

30約束條件：必須全部遍歷并返回O求解過程中，根據(jù)FloydStep1：定義并初始化輔助矩陣Dist[n][n]和Path[n][n]，矩陣元素Dist[i][j]與Path[ij]ViVj之間的最短距離和最短路徑(由于最短路徑的源點ViVjPath[ij]只保存路徑中途徑其它頂點的部分)Dist與PathViVj之間直接到達(中間不途徑其它頂點)時的最短距ijDist[ij]置為∞，否則將Dist[ij]置為弧<Vi，VjijDist[ij0Path[ij沒Step3ViVj組合(1in1jn)Dist[i][kDist[kDist[ij]Dist[ijDist[i][kDist[kj]Path[ijPath[i][k]"Vk"Path[kj]；Dist[i][j]Path[i][j]保持不變(VkViVj之間的最短路徑中。符號“”表示連接運算，如"abcd""fg"="abcdfg"。)；Step4：kk+1kn轉(zhuǎn)Step3ViVj之間的最Dist[ij]ViVj之間的最短路徑則為"Vi"Path[ij"Vj"。從上面給出Floyd算法步驟可以看出，該算法過程極為簡捷，然而，為何經(jīng)過這樣的運算ViVj之間的最短距離。下面僅列出幾條用編程得到的近似最佳送貨路線及總路線長度：第I條送貨路線（圖二→45→40→34→39→27→31

Tf(Vi)/240.05*長度（米123 4→43→385→36→326圈（H圈。由完備圖,確定初始H圈,列出該初始H圈加點序邊框的距離定近似最佳H圈。1i在所有H圈中，找出權(quán)最小的一個，此即要找的最佳H圈的近似解。1i最佳H

1000f(V針對問題二

00

Wnnv

W

時間約束條件

Ws

Ws t 1 n1

總模型

nnv

00.

v

mm

nn

利用遺傳算法的思想得出如下計算步驟 記A為{1,2,3……22}的所有固定起點和終點的循環(huán)排列集合，起點和終點固定為點0（即22點。解空間S是滿足時間約束的A的子集。2)編 隨機序列L[012]作 ，其中，0<

<1（i=

0

=1如：取一個6目標問題為

表示一個或路徑)iiii在路徑中的順序。6— 種群初始化10~160150計算。適應(yīng)度函數(shù)的確定:取適應(yīng)度函數(shù)為走遍n個點的距離的倒數(shù)的的適應(yīng)度0 L為f(L)

1/Tn L為合 優(yōu)化的目標就是選擇適應(yīng)度函數(shù)值盡量可能大的,適應(yīng)度函數(shù)值越大的越終止條件設(shè)定 設(shè)置最大迭代次數(shù) 此排序。選擇群體中前70％的 交叉 采用單點交叉對兩個父 的部分結(jié)構(gòu)加以替換重組而生成新的。如f1f2設(shè)交叉點為第四個處，則s1s20.9變異:在群體中隨機確定座，以0.01的變異概率度這些座的值進行變得到兩個新的問題三遍歷所有的50個點單由于M147kg，V總

，而M50kg，V1m3Mk50kg和V1m判斷的標3kk目標函數(shù)

WW1W2約束條件

wk(i,

Mk

kV (kk算法與過程（5(Prim)（也即產(chǎn)生局部區(qū)域最小生成樹28每一階段（區(qū)域）多階段組合路線（無次序問題6.1遺傳算法從問題解的中集開始嫂索，而不是從單個解開始。這是遺傳算法與傳統(tǒng)優(yōu)化參考文[1],利用矩陣翻轉(zhuǎn)法求最佳H圈,后勤學(xué)報，第24卷第2008196頁[2],利用矩陣翻轉(zhuǎn)法求最佳H圈,后勤學(xué)報，第24卷第2008196頁劉國華包宏超， 2001，100083，第80頁.將金山潘少華最優(yōu)化計算方法遺傳算法的模式理論廣州華南理工大學(xué)238辛運幃劉璟陳有褀第6章圖數(shù)據(jù)結(jié)構(gòu)與算法高等教育2006第136附1第一問的floyd算法程fori=1:83V=[x1E=[x2y2fori=1:51forforif(i==x2(k)&j==y2(k))|(i==y2(k)&j==x2(k))elseifi==j

forforforforforifd(i,k)d(i,j)=d(i,k)+d(k,j);

forq=1:2000forp=1:a2(2)fori=1:21forforE=zeros(25,25);%áD3???3?ê?Hè|?óμ?Dò±??òμ??àà????ófori=1:23;forforforfo