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

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

0-1 tntntWiW3

節(jié)點(diǎn)s和節(jié)點(diǎn)e之間的最短距離問題二中第n問題二中第n問題i的總路程(i1,2,3)問題3第i階段的總路程問題i的總時(shí)間(i1,2,3) 問題分的送貨行程最短。此即圖論中最佳路徑問題。而送貨路線問題可以理解為：已知起點(diǎn)和終圈（H圈。從而得出送貨員的最佳送貨方案。模型準(zhǔn)問題一的基本算法及其相關(guān)概念Floyd算法的基本思想GV,E，V為頂點(diǎn)集合，En(n1)個(gè)頂V1,…,Vn。FloydViVj(1ijn)Vk(k1n)，并計(jì)算出只任取初始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)為一個(gè)無向圖，其中V=｜v1,v2,……，vn｜為頂點(diǎn)集合，E為Gew(e)w(e)為該邊的權(quán)。若任意兩點(diǎn)均有邊相連，則G為完備圖。哈圖設(shè)G=(V,E)是連通無向圖，經(jīng)過G的每個(gè)頂點(diǎn)正好一次的圈，稱為G的一條哈圈，簡稱H圈；含H圈的圖成為哈圖或H圖。最佳H圈在圖G=(V，E)中，權(quán)最小的哈圈稱為最佳H圈判定一個(gè)圖G=(V，E)是否存在哈圈是一個(gè)NP問題而它的完備圖G'=(V,E（E'中的每條邊（x,y）xyG中最短路徑的權(quán)）中一定存在哈圈所以在完備圖G'=(V,E')中尋找最佳H圈該過程采用二邊逐次修 在一個(gè)矩陣中，對它的第i行（列）到第j行（列）翻轉(zhuǎn)是以第i行（列）和j行（列的）中心位置為轉(zhuǎn)軸，旋轉(zhuǎn)180度，這樣：第i行（列）和第j行（列）的位置互換，第i+1行（列）和第j-1行（列）位置互換，……最后就會收斂到最適應(yīng)環(huán)境的一個(gè)“”上，它就是問題的最優(yōu)解。遺傳算法步驟1)編碼,創(chuàng)建初始2)中適應(yīng)度計(jì)根據(jù)適應(yīng)度選擇被選擇進(jìn)行交叉繁殖繁殖出新的,回到第二)n-1模型建立針對問題1~30顯然送貨員能夠一次帶上所有貨物到達(dá)各送貨點(diǎn)，而且貨物要送達(dá)的送貨點(diǎn)總共為個(gè)本模型運(yùn)用圖論中最佳路徑問題與最佳Ｈ圈中的相出發(fā)點(diǎn)O/5121個(gè)送貨點(diǎn)結(jié)合起來構(gòu)造完備圖。問題一需要從1~30號貨物送到指定地點(diǎn)并返回至O點(diǎn)，要求總時(shí)間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之間的最短距離和最短路徑(由于最短路徑的源點(diǎn)ViVjPath[ij]只保存路徑中途徑其它頂點(diǎn)的部分)Dist與PathViVj之間直接到達(dá)(中間不途徑其它頂點(diǎn))時(shí)的最短距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之間的最短路徑中。符號“”表示連接運(yùn)算，如"abcd""fg"="abcdfg"。)；Step4：kk+1kn轉(zhuǎn)Step3ViVj之間的最Dist[ij]ViVj之間的最短路徑則為"Vi"Path[ij"Vj"。從上面給出Floyd算法步驟可以看出，該算法過程極為簡捷，然而，為何經(jīng)過這樣的運(yùn)算ViVj之間的最短距離。下面僅列出幾條用編程得到的近似最佳送貨路線及總路線長度：第I條送貨路線（圖二→45→40→34→39→27→31

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

1000f(V針對問題二

00

Wnnv

W

時(shí)間約束條件

Ws

Ws t 1 n1

總模型

nnv

00.

v

mm

nn

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

<1（i=

0

=1如：取一個(gè)6目標(biāo)問題為

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

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

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

WW1W2約束條件

wk(i,

Mk

kV (kk算法與過程（5(Prim)（也即產(chǎn)生局部區(qū)域最小生成樹28每一階段（區(qū)域）多階段組合路線（無次序問題6.1遺傳算法從問題解的中集開始嫂索，而不是從單個(gè)解開始。這是遺傳算法與傳統(tǒng)優(yōu)化參考文[1],利用矩陣翻轉(zhuǎn)法求最佳H圈,后勤學(xué)報(bào)，第24卷第2008196頁[2],利用矩陣翻轉(zhuǎn)法求最佳H圈,后勤學(xué)報(bào)，第24卷第2008196頁劉國華包宏超， 2001，100083，第80頁.將金山潘少華最優(yōu)化計(jì)算方法遺傳算法的模式理論廣州華南理工大學(xué)238辛運(yùn)幃劉璟陳有褀第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