數(shù)模 送貨路線設(shè)計(jì)問題論文

1、目錄一、問題重述- 2 -1.1問題背景- 2 -1.2實(shí)際現(xiàn)狀- 2 -1.3問題提出- 2 -二、基本假設(shè)- 3 -三、符號(hào)說明及名詞解釋- 3 -3.1基本符號(hào)- 3 -3.2部分符號(hào)說明與名詞解釋- 3 -四、問題分析、模型建立與模型求解- 4 -4.1問題一- 4 -問題分析- 4 -4.1.2 模型建立- 4 -模型求解- 6 -4.1.4 模型的優(yōu)化- 7 -4.2問題二- 9 -問題分析- 9 -模型建立- 9 -模型求解- 10 -4.2.4 通過模擬進(jìn)行校驗(yàn)- 11 -4.3問題三- 12 -問題分析- 12 -模型建立- 12 -模型求解- 14 -五、模型分析- 17

2、-5.1 模型優(yōu)點(diǎn)- 17 -5.2 模型缺點(diǎn)- 17 -5.3模型的推廣- 17 -六、參考文獻(xiàn)- 17 -附錄：- 19 -附錄一：- 19 -附錄二：- 23 -附錄三：- 23 -送貨路線設(shè)計(jì)問題一、問題重述1.1問題背景 現(xiàn)今社會(huì)網(wǎng)絡(luò)越來越普及，網(wǎng)購(gòu)已成為一種常見的消費(fèi)方式，隨之物流行業(yè)也漸漸興盛，每個(gè)送貨員需要以最快的速度及時(shí)將貨物送達(dá)，而且他們往往一人送多個(gè)地方。對(duì)于送貨員而言，如何在按時(shí)將貨物送到的前提下，使其送貨耗時(shí)最少是一個(gè)不得不考慮的問題?；谏鲜銮闆r，根據(jù)已有數(shù)據(jù)，運(yùn)用數(shù)學(xué)建模的方法，對(duì)送貨員的送貨線路作出分析并提出合理建議是一個(gè)重要問題。準(zhǔn)確分析進(jìn)而制定出正確合理的決

3、策，使送貨員能在最短的時(shí)間內(nèi)將貨物送達(dá)顧客，對(duì)于提高公司名聲、效益，創(chuàng)造和諧的社會(huì)壞境，節(jié)約能源等諸多方面都具有重要意義。1.2實(shí)際現(xiàn)狀對(duì)送貨員送貨路線的要求主要有以下幾個(gè)特點(diǎn)，如：1）送貨員出于成本及節(jié)約時(shí)間的考慮，總是要使送貨所用時(shí)間最??；2）由于受設(shè)備等的限制，送貨員最大載重50公斤，所帶貨物最大體積1立方米；3）考慮顧客對(duì)商品的需求情況，有些貨物必須在指定時(shí)間前送達(dá)；這些因素都影響著送貨路線最優(yōu)化方案的設(shè)計(jì)。1.3問題提出 從目標(biāo)位置的實(shí)際分布情況以及上述要求出發(fā)，依據(jù)相關(guān)數(shù)據(jù)： 1）在將130號(hào)貨物送到指定地點(diǎn)并返回的前提下，建立一送貨員送貨線路模型，使得求得的最優(yōu)化方案能夠達(dá)到用時(shí)

4、最省的目的； 2）現(xiàn)實(shí)情況下，不同的顧客對(duì)貨物的需求情況不同，有的顧客急需貨物，就要求送貨員在指定時(shí)間將貨物送達(dá)。在進(jìn)一步考慮顧客指定送貨時(shí)間的情況下，制定出送貨員的送貨線路，使得送貨員從早上8點(diǎn)上班開始送貨，在不超過指定時(shí)間內(nèi)將130號(hào)貨物送達(dá)，并能夠達(dá)到用時(shí)最省的目的；3）在1、2的基礎(chǔ)上，若不考慮所有貨物送達(dá)時(shí)間的限制(包括前30件貨物)，并要將100件貨物全部送到指定地點(diǎn)并返回，設(shè)計(jì)最快完成路線與方式。二、基本假設(shè)本題給出了送貨員送貨地點(diǎn)的網(wǎng)絡(luò)圖及相關(guān)數(shù)據(jù)，要求在不同的條件下送貨的最佳路線。為解決此問題，需做如下的簡(jiǎn)化和抽象：1、由于送貨指定地點(diǎn)的大小，與送貨線路長(zhǎng)相比，它們相對(duì)地小得

5、多，故可以抽象的看做一個(gè)點(diǎn)。兩指定送貨地點(diǎn)之間的線路，省略其彎曲，抽象簡(jiǎn)化為直線段，而直線段的長(zhǎng)即為此段線路的長(zhǎng)度。于是線路網(wǎng)絡(luò)圖在數(shù)學(xué)上抽象為賦權(quán)圖。將送貨員的送貨網(wǎng)絡(luò)圖中的每個(gè)指定地點(diǎn)看作圖中的一個(gè)頂點(diǎn)，各指定地點(diǎn)之間的線路看作圖中對(duì)應(yīng)頂點(diǎn)之間的邊，各線路的長(zhǎng)度看做各條邊的權(quán)。2、問題可歸結(jié)為圖上的優(yōu)化問題：在給定的賦權(quán)圖上尋找從給定點(diǎn)O出發(fā)，經(jīng)過圖上某些或全部點(diǎn)后，再回到該給定點(diǎn)且使得所用的總時(shí)間最省的閉路線。3、假設(shè)送貨員送貨過程中的時(shí)間消耗只來自于指定地點(diǎn)之間的行走和貨物交接花費(fèi)，忽略其他應(yīng)突發(fā)情況（如堵車等）造成的時(shí)間消耗。說明：以上是模型討論過程中的全局假設(shè)，在以后的分步討論中我

6、們可能引入新的局部性假設(shè)。三、符號(hào)說明及名詞解釋3.1基本符號(hào)G賦權(quán)圖 G與賦權(quán)圖G對(duì)應(yīng)的完全賦權(quán)圖V賦權(quán)圖和完全賦權(quán)圖的頂點(diǎn)e賦權(quán)圖和完全賦權(quán)圖的邊賦權(quán)圖和完全賦權(quán)圖的權(quán)賦權(quán)圖上任意兩頂點(diǎn)之間的距離QH回路所對(duì)應(yīng)的路程Wg每件貨物的重量Tj每件貨物的體積N貨物編號(hào)Sp送貨員的行進(jìn)速度T完成任務(wù)所需時(shí)間t限時(shí)時(shí)間控制變量3.2部分符號(hào)說明與名詞解釋 上表所列符號(hào)并不完整，我們?cè)诤罄m(xù)各步中引入的新符號(hào)，到時(shí)再做說明。四、問題分析、模型建立與模型求解4.1問題一問題分析問題一要求得，在將130號(hào)貨物送到指定地點(diǎn)并返回的前提下，建立一用時(shí)最省的送貨員送貨線路模型。由于130號(hào)貨物的總重量、總體積均未

7、超出范圍，且由MATLAB作圖可以發(fā)現(xiàn)130），若只考慮130號(hào)貨物的送達(dá)情況，可將問題一轉(zhuǎn)化為從庫(kù)房O點(diǎn)出發(fā)，行遍130號(hào)貨物指定送達(dá)地點(diǎn)至少一次再回到O點(diǎn)，使得總權(quán)（路程） 圖 4.1.1 (大圖見附錄)最小，即最佳旅行售貨員回路的問題，然后加以修正即得到最優(yōu)解。但此問題是不可解的，即無法給出最優(yōu)解，只能給出一種啟發(fā)式算法，得到一個(gè)較優(yōu)解。因此有如下思路：簡(jiǎn)化抽象最佳售貨員回路問題問題的疑似最優(yōu)解 修正 比較問題的近似最優(yōu)解4.1.2 模型建立單個(gè)售貨員的最佳旅行售貨員回路的問題是一個(gè)非常實(shí)際的問題，其本質(zhì)是Hamilton回路的應(yīng)用與引申，圖論提法是在一個(gè)賦權(quán)圖上尋求過每一個(gè)頂點(diǎn)至少一次

8、的總權(quán)最小的路，即所謂的最短售貨員回路。賦權(quán)H圖的總權(quán)最小的回路稱為最短H回路。一般地，在 同一賦權(quán)圖中，最短售貨員回路與最短H回路不同。如 圖 4.1.2圖所示，最短售貨員回路為V1V2V1V3V1，權(quán)為4，而最短H回路為V1V2V3V1，權(quán)為5。 這里我們不加證明的給出如下結(jié)論：若G=（V,E,W）中任意兩個(gè)相異定點(diǎn)，均能滿足三角不等式，則G中最短售貨員回路與最短H回路相同。對(duì)于本題中的無向賦權(quán)圖G，可以應(yīng)用任意頂點(diǎn)對(duì)之間的最短路徑算法構(gòu)造一個(gè)等價(jià)完全賦權(quán)圖,即在G中各頂點(diǎn)對(duì)之間的權(quán)由他們之間的最短路徑的權(quán)代替。顯然，在G中三角不等式均能滿足，于是，由G解得的最短H回路即為原無向賦權(quán)圖G的

9、最短售貨員回路。l .1確立目標(biāo)函數(shù)目標(biāo)函數(shù)考慮完全賦權(quán)圖G的H回路使得總權(quán)最小: （4.1.1）其中，Q是H回路的總權(quán)，為G中每條所走路線的權(quán)值；由于G中各頂點(diǎn)對(duì)之間的權(quán)由它們之間的最短路徑的權(quán)代替，故可由計(jì)算賦權(quán)圖G中任意兩點(diǎn)之間的最短路得到。這里我們采用Floyd算法：設(shè)G是賦權(quán)圖，權(quán)為實(shí)數(shù),|V|=nd(i,j):i到j(luò)的距離r(i,j)：i到j(luò)之間的插入點(diǎn)輸入：帶權(quán)鄰接矩陣（1）賦初值：對(duì)所有 （2）更新：對(duì)所有i，j，若，則（3）若k=n，停止。否則，轉(zhuǎn)（2）l 構(gòu)造約束條件在第一問中約束條件主要考慮的是體積與重量的限制，于是有如下的約束條件： (4.1.2)實(shí)際上，我們?cè)谟?jì)算13

10、0號(hào)貨物的中來重量與體積之后，發(fā)現(xiàn)它們的重量與體積均未超出范圍，也就可以不考慮約束條件，于是問題轉(zhuǎn)化為單純的單售貨員的最佳售貨員回路問題，也就是與之對(duì)應(yīng)的完全賦權(quán)圖的最短H回路問題。l .3 建立模型由前面的分析可得到問題一的模型是完全賦權(quán)圖的最短H回路問題，即模型求解 由于問題一最終轉(zhuǎn)化為單售貨員的最佳售貨員回路問題，進(jìn)一步轉(zhuǎn)化為了完全賦權(quán)回路的最短H回路問題。約束條件（1）表示H回路只能從出發(fā)一次，約束條件（2）表示H回路只能到達(dá)一次，約束條件（3）表示不會(huì)出現(xiàn)K個(gè)頂點(diǎn)構(gòu)成的回路，K=2,3,n-1。最短H回路問題屬于NP完全問題，目前還沒有找到有效的算法。這里我們考慮矩陣翻轉(zhuǎn)實(shí)現(xiàn)的二邊逐

11、次修正法和遺傳算法。l 矩陣翻轉(zhuǎn)實(shí)現(xiàn)的二邊逐次修正法首先構(gòu)造完全賦權(quán)圖，并用距離矩陣表示之，使所選初始圈的頂點(diǎn)為矩陣主對(duì)角線的上方元素對(duì)應(yīng)的頂點(diǎn)；然后對(duì)距離矩陣加邊框并進(jìn)行若干次翻轉(zhuǎn)，直到矩陣不滿足二邊逐次修正法的修正原則，最后得到的矩陣主對(duì)角線的上方元素確定了最佳H圈的權(quán)重和路線。算法如下：（1）任取初始H圈（2）對(duì)所有的，若，則C在中刪去邊而加入邊，形成新的H圈（3）對(duì)C重復(fù)步驟二，直到條件不滿足為止，最后得到的C即為所求l 遺傳算法 遺傳算法（如圖4.1.3）是從代表問題可能潛在的解集的一個(gè)種群開始，仿照基因編碼的工作，初代種群產(chǎn)生之后，按照適者生存和優(yōu)勝劣汰的原理，逐代演化產(chǎn)生出越來越

12、好的近似解，在每一代，根據(jù)問題域中個(gè)體的適應(yīng)度大小選擇個(gè)體，并借助于自然遺傳學(xué)的遺傳算子進(jìn)行組合交叉和變異，產(chǎn)生出代表新的解集的種群。這個(gè)過程將導(dǎo)致種群像自然進(jìn)化一樣的后生代種群比前代更加適應(yīng)于環(huán)境，末代種群中的最優(yōu)個(gè)體經(jīng)過解碼，可以作為問題近似最優(yōu)解。 遺傳算法圖解在編程實(shí)現(xiàn)方面，我們選擇了遺傳算法，MATLAB程序代碼見附錄。 模擬得到的最佳結(jié)果如說明：其他所得結(jié)果見附錄圖4.1.4 最佳H圈 圖4.1.5 最佳H圈搜索過程最短距離S=51051m，最短時(shí)間T=S / V+ t =51051/400+330=218min其中，t為交接時(shí)間。4.1.4 模型的優(yōu)化 在前面的求解過程中，由于1

13、-30號(hào)貨物的送達(dá)地點(diǎn)相對(duì)集中，故我們以這些點(diǎn)為主，搜索其最佳售貨員回路。實(shí)際上，我們?cè)跇?gòu)造鄰接矩陣時(shí)已經(jīng)將另外的點(diǎn)考慮在內(nèi)，這也是對(duì)原模型的優(yōu)化修正。4.2問題二問題分析問題二中假定送貨員從早上8點(diǎn)上班開始送貨，要求130號(hào)貨物的送達(dá)時(shí)間不能超過指定時(shí)間，設(shè)計(jì)出最快完成路線與方式并標(biāo)出送貨線路。由問題一的分析，我們已經(jīng)知道最佳旅行售貨員回路問題不可解的，即無法給出最優(yōu)解，只能給出一種啟發(fā)式算法，得到一個(gè)近似最優(yōu)解，因此我們可以在問題一的基礎(chǔ)上增加上時(shí)間限制條件，再進(jìn)行最短H回路的搜索。算法如下：（1）求出賦權(quán)圖G中任意兩個(gè)頂點(diǎn)之間的的最短距離（采用Floyd算法），構(gòu)造出完全賦權(quán)圖；（2）隨

14、機(jī)產(chǎn)生一個(gè)存在潛在的解集的初始種群；（3）根據(jù)問題域中個(gè)體的適應(yīng)度大?。ㄖ饕菚r(shí)間的限制方面）選擇滿足條件的個(gè)體，并借助于自然遺傳學(xué)的遺傳算子進(jìn)行組合交叉和變異，產(chǎn)生出代表新的解集的種群。若不存在滿足條件的個(gè)體，則重新產(chǎn)生初始種群；（4）在第（3）步求出的所有H圈中，找出權(quán)最小的一個(gè)，此即要找的最優(yōu)H圈的近似解。模型建立l .1確立目標(biāo)函數(shù) 目標(biāo)函數(shù)仍然考慮完全賦權(quán)圖G的H回路使得總權(quán)最小: （4.2.1）其中，Q是H回路的總權(quán)，為G中每條所走路線的權(quán)值；l 4.2.2.2 構(gòu)造約束條件：由問題一得分析知道，130號(hào)貨物的總重量、總體積均未超出范圍，且由MATLAB作圖可以發(fā)現(xiàn)130號(hào)貨物的送

15、達(dá)地點(diǎn)相對(duì)集中（見附錄），這樣只需考慮130號(hào)貨物的送達(dá)時(shí)間情況。只要在指定時(shí)間前將貨物送到就算滿足條件，于是有約束條件其中，為第n件貨物送達(dá)時(shí)送貨員所用時(shí)間， 為送貨員從上班開始計(jì)時(shí)其送編號(hào)為n的貨物的可用時(shí)間，具體數(shù)據(jù)見附錄。l 4.2.2.3 建立模型由前面的分析，并結(jié)合問題一所建立的模型，我們對(duì)問題二建立了如下模型：模型求解 由于問題二是建立在問題一的基礎(chǔ)之上的，因而其求解思路與問題有相似之處。隨機(jī)產(chǎn)生種群，接著進(jìn)行其中個(gè)體是否滿足送貨時(shí)間的要求的判斷，根據(jù)適者生存和優(yōu)勝劣汰的原理，篩選出符合時(shí)間限制的個(gè)體，組成新的中間過渡種群，然后按照自然遺傳學(xué)的遺傳算子進(jìn)行組合交叉和變異，產(chǎn)生出代

16、表新的解集的下一代種群，這樣逐代演化就會(huì)產(chǎn)生出越來越好的近似解。算法上，我們?nèi)匀徊捎眠z傳算法。由于加入了新的限制條件，故而在根據(jù)自然遺傳學(xué)的遺傳算子進(jìn)行組合交叉和變異，產(chǎn)生出代表新的解集的下一代種群之前需進(jìn)行一次判斷，以排除其中不符合時(shí)間限制的個(gè)體。這一我們引入“中間過渡種群”的概念。中間過渡種群是指從上一代種群中按一定條件篩選出的滿足要求的所有個(gè)體的集合。容易知道，中間過渡種群可以看作產(chǎn)生新的下一代種群的初始種群。對(duì)于約束條件的考慮，我們是對(duì)每一代種群中的每一個(gè)個(gè)體進(jìn)行時(shí)間限制方面的考察。首先確定庫(kù)房O點(diǎn)在每個(gè)個(gè)體中的位置，然后以O(shè)為起始點(diǎn)順序讀取其后的各個(gè)位置，并讀進(jìn)該位置的相關(guān)信息，包括

17、送達(dá)該地貨物的件數(shù)以確定交接時(shí)間、該位置與上一位置的最短距離以確定行車時(shí)間等，進(jìn)而循環(huán)檢測(cè)其后各個(gè)送貨地點(diǎn)的到達(dá)時(shí)間是否滿足條件。若全部滿足，則將該個(gè)體放入中間過渡種群，用以產(chǎn)生新的下一代種群；若不滿足，則將此個(gè)體排除。用MATLAB程序?qū)崿F(xiàn)的最佳結(jié)果結(jié)果如下（圖4.2.1和圖4.2.2）： 圖4.2.1 最佳H圈 圖4.2.2 最佳H圈搜索過程最短距離S=60362m，最短時(shí)間T=S / V+ t =60362/400+330=241min其中，t為交接時(shí)間。 通過模擬進(jìn)行校驗(yàn)現(xiàn)在我們已利用MATLAB程序求得問題的近似最優(yōu)解，需要對(duì)所建立的模型進(jìn)行校驗(yàn)，測(cè)試此結(jié)果是否可以滿足相應(yīng)的時(shí)間限制

18、，并且具有相應(yīng)的較小的路徑。 l .1模擬規(guī)則及方法 1、用MATLAB程序隨機(jī)產(chǎn)生滿足條件的最佳H圈，并還原成最佳售貨員回路 2、根據(jù)相應(yīng)的時(shí)間限制校驗(yàn)各個(gè)指定地點(diǎn)是否滿足條件3、若計(jì)算所得送貨員達(dá)到指定地點(diǎn)的時(shí)間與所要求的時(shí)間相差不大，則可認(rèn)為模型是合理的。l .2校驗(yàn)結(jié)果我們共對(duì)問題二的模型進(jìn)行了10次模擬，全部基本符合要求。校驗(yàn)結(jié)果見附錄。4.3問題三問題分析問題三建立在問題一和在問題二的基礎(chǔ)之上，要求設(shè)計(jì)出在不考慮貨物送達(dá)時(shí)間的前提下，將100件貨物全部送到指定地點(diǎn)并返回的最快完成路線與方式。要求標(biāo)出送貨線路，給出送完所有快件的時(shí)間。由于受重量和體積限制，送貨員可中途返回取貨。這個(gè)問

19、題可以描述為:一中心倉(cāng)庫(kù)擁有最大載重50公斤，所帶貨物最大體積1立方米的送貨員1人, 負(fù)責(zé)對(duì)100個(gè)客戶進(jìn)行貨物分送工作, 客戶i 的貨物需求為已知 , 求滿足需求的路程最短的送貨員行駛路徑,并滿足以下條件:1) 送貨員每次所載貨物之和不超過個(gè)人最大負(fù)重，而且體積不能超過1立方米。2) 每件貨物必須送到指定地點(diǎn)；3）每次貨物交接的時(shí)間為3分鐘，途中速度為24km/h。4）為了計(jì)算方便，我們將貨物一律用重量和體積來衡量，則貨物總重量為148千克，總體積為2.8立方米。出于實(shí)際情況的考慮, 我們對(duì)人的最大行程不加限制，試圖從最優(yōu)化的角度，建立起滿足設(shè)計(jì)要求的送貨的數(shù)學(xué)模型，借助于計(jì)算機(jī)的高速運(yùn)算與

20、邏輯判斷能力，求出滿足題意要求的結(jié)果。對(duì)于上述的路線確定問題，應(yīng)用如下啟發(fā)：從公司總部配出一個(gè)人，到任意未配送的送貨點(diǎn)，然后將這個(gè)人配到最近的未服務(wù)的送貨點(diǎn)范圍之內(nèi)的鄰居，并使各送貨點(diǎn)總重量不超過50kg，總體積不超過1立方米。在上一售貨員回到庫(kù)房以后繼續(xù)上述指派，直到?jīng)]有未服務(wù)的送貨點(diǎn)。對(duì)得到的可行的行程安排解中的每一條路徑，求解一個(gè)最短售貨員回路問題，決定指派給每一條行程的送貨員的順序，得到可行解的行程安排解后退出。模型建立根據(jù)上述分析，問題三就可轉(zhuǎn)換為我們熟悉的接力賽問題。這樣我們就把一個(gè)送貨員的問題轉(zhuǎn)化成了多個(gè)送貨員的接力問題。上面的方法通過以下兩種方法實(shí)現(xiàn)：（1）每一個(gè)行程的第一個(gè)送

21、貨點(diǎn)是距離總部最近的未服務(wù)的送貨點(diǎn)。用這種方法，即可得到一組運(yùn)行路線，總的運(yùn)行公里數(shù)，以及總時(shí)間。（2）每一個(gè)行程的第一個(gè)送貨點(diǎn)是距離總部最遠(yuǎn)的未服務(wù)的送貨點(diǎn)，然后以該點(diǎn)為基準(zhǔn)，選擇距它最近的點(diǎn)，加上約束條件，也可得到一組數(shù)據(jù)。 然后比較兩組結(jié)果，通過函數(shù)擬合即可得到最優(yōu)化結(jié)果。l 4.3.2.1 基本假設(shè)為求解模型，我們先做如下假設(shè)：（1）假設(shè)每個(gè)人的送貨路線一旦確定，再不更改； （2）同一地點(diǎn)的貨物必須在一次送完；（3）如果到某一個(gè)點(diǎn)距離最近的點(diǎn)不至一個(gè)，就按下面的方法進(jìn)行確定：考慮該點(diǎn)需求的貨物量，將其從大到小依次排列，貨物量需求大者優(yōu)先，但路線中各點(diǎn)總重量加上該點(diǎn)的貨物重量超過50kg

22、或體積1立方米的上限時(shí)，該點(diǎn)舍去。另外，由常識(shí)我們知道回去取包裹的次數(shù)越少，越節(jié)省時(shí)間，而且此問題中至少需要分三次取包裹。在我們抽象簡(jiǎn)化的接力模型中，這一條件就轉(zhuǎn)化為使用人數(shù)盡量少。l 符號(hào)說明A所有送貨點(diǎn)的集合C任意一點(diǎn)到庫(kù)房的距離一條路線所運(yùn)行的總公里數(shù)i,j表示送貨點(diǎn)，如i點(diǎn)，j點(diǎn)KK條路線qi點(diǎn)i的需求量，q0=0，表示庫(kù)房的需求量Xij送貨員路線安排m接力問題中送貨員人數(shù)注：A=0，1，2，3，.，50，其中0代表庫(kù)房l 4.3.2.3模型建立由問題一和問題二以及上述分析可把問題三轉(zhuǎn)化為多個(gè)售貨員接力的最佳售貨員回路問題，其數(shù)學(xué)描述如下：目標(biāo)函數(shù)：約束條件： 模型求解下面用框圖來說明

23、兩種方法的實(shí)現(xiàn)過程始開 找離庫(kù)房最近的點(diǎn)V且把該點(diǎn)標(biāo)記為可到達(dá)，輸出該點(diǎn)并記錄貨物的重量Wg1和體積Tj1找離V最近的點(diǎn)，到達(dá)該點(diǎn)貨物的重量Wg2和體積Tj2，且有Wg1+ Wg250，Tj1+ Tj2a d(i,j)=a; r(i,j)=k; end end endend最短H回路算法：遺傳算法求最佳H圈function gaTSPCityNum=22;%城市數(shù)dislist,Clist,goodc=tsp(CityNum);%初始化TSP問題inn=100; %初始種群大小gnmax=200; %最大代數(shù)pc=0.8; %交叉概率pm=0.8; %變異概率num=0;%產(chǎn)生初始種群，順序編

24、碼for i=1:inn s(i,:)=randperm(CityNum); dn=size(s(i,:),2);endf,p=objf(s,dislist);%計(jì)算初始種群的適應(yīng)值gn=1;%迭代次數(shù)while gngnmax+1%判斷是否達(dá)到最大迭代次數(shù) for j=1:2:inn%從1開始，間隔為2，到種群大小，保證每次產(chǎn)生2個(gè)新個(gè)個(gè)體 seln=sel(s,p); %選擇操作 scro=cro(s,seln,pc); %交叉操作 scnew(j,:)=scro(1,:);%獲取進(jìn)行變異的第1個(gè)個(gè)體 scnew(j+1,:)=scro(2,:);%獲取進(jìn)行變異的第2個(gè)個(gè)體 smnew(j

25、,:)=mut(scnew(j,:),pm); %對(duì)第1個(gè)個(gè)體進(jìn)行變異操作 smnew(j+1,:)=mut(scnew(j+1,:),pm);%對(duì)第2個(gè)個(gè)體進(jìn)行變異操作 end s=smnew; %產(chǎn)生了新的種群 f,p=objf(s,dislist); %計(jì)算新種群的適應(yīng)度 fmax,nmax=max(f);%記錄當(dāng)前代最好和平均的適應(yīng)度 ymean(gn)=1000/mean(f);%記錄每一代種群的平均路徑長(zhǎng)度 ymax(gn)=1000/fmax;%記錄每一代種群的最短路徑長(zhǎng)度 %ymax %輸出 x=s(nmax,:);%記錄當(dāng)前代的最佳個(gè)體 drawTSP(Clist,x,yma

26、x(gn),gn,0);%畫圖 gn=gn+1; %pause;end %搜索結(jié)束for i=1:22goodc(x(i)%最優(yōu)解順序endgn=gn-1;figure(2);plot(ymax,r); hold on;%繪制最短路徑變化曲線plot(ymean,b);grid;%繪制平均路徑變化曲線title(搜索過程);legend(最優(yōu)解,平均解);%text(5,5,最終搜索結(jié)果：最短距離 ,num2str(ymax);end%-%計(jì)算適應(yīng)度函數(shù)function f,p=objf(s,dislist);%f為種群中每個(gè)個(gè)體的適應(yīng)值，p為每個(gè)個(gè)體的累積選擇概率inn=size(s,1);

27、 %讀取種群大小for i=1:inn %依次計(jì)算種群中每個(gè)個(gè)體的路徑長(zhǎng)度 f(i)=CalDist(dislist,s(i,:); endf=1000./f;%取倒數(shù)，使路徑短和個(gè)體具有較大的適應(yīng)值%計(jì)算選擇概率fsum=0;for i=1:inn fsum=fsum+f(i)15;endfor i=1:inn ps(i)=f(i)15/fsum;end%計(jì)算累積概率p(1)=ps(1);for i=2:inn p(i)=p(i-1)+ps(i);endp=p;end%-function pcc=pro(pc);%根據(jù)交叉概率決定是否進(jìn)行交叉操作%根據(jù)變異概率決定是否進(jìn)行變異操作test(1

28、:100)=0;%令中所有數(shù)為0k=round(100*pc);%概率與100相乘后取整得ktest(1:k)=1;%令test中從1到k的數(shù)為1n=round(rand*99)+1;%隨機(jī)數(shù)與99的積取整后加1pcc=test(n);%取test中的第個(gè)n數(shù) end%-%“選擇”操作function seln=sel(s,p);%s為當(dāng)前種群，p為每個(gè)個(gè)體的累積選擇概率inn=size(p,1);for i=1:2%從種群中選擇兩個(gè)個(gè)體 r=rand; %產(chǎn)生一個(gè)隨機(jī)數(shù) prand=p-r;%計(jì)算每個(gè)個(gè)體的累積選擇概率與隨機(jī)數(shù)之差 j=1; while prand(j)0%循環(huán)，直到找到一個(gè)

29、累積選擇概率大于隨機(jī)數(shù)的個(gè)體 j=j+1; end seln(i)=j; %選中個(gè)體的序號(hào)endend%-%“交叉”操作function scro=cro(s,seln,pc);%s為當(dāng)前種群，seln為被選中的兩個(gè)個(gè)體編號(hào)，pc為交叉概率bn=size(s,2);%獲取個(gè)體的編碼長(zhǎng)度，即城市數(shù)pcc=pro(pc); %根據(jù)交叉概率決定是否進(jìn)行交叉操作，1則是，0則否%torf=1;%while(torf)scro(1,:)=s(seln(1),:);%獲取被選擇的第1個(gè)個(gè)體scro(2,:)=s(seln(2),:);%獲取被選擇的第2個(gè)個(gè)體if pcc=1%如果要進(jìn)行交叉 c1=roun

30、d(rand*(bn-2)+1; %在1,bn-1范圍內(nèi)隨機(jī)產(chǎn)生一個(gè)交叉位 c2=round(rand*(bn-2)+1; %在1,bn-1范圍內(nèi)隨機(jī)產(chǎn)生另一個(gè)交叉位 chb1=min(c1,c2);%獲得交叉位的最小值 chb2=max(c1,c2);%獲得交叉位的最大值 middle=scro(1,chb1+1:chb2);%獲得第1個(gè)個(gè)體編碼中位于兩交叉點(diǎn)間的部分 scro(1,chb1+1:chb2)=scro(2,chb1+1:chb2);%用第2個(gè)個(gè)體的中間部分替換第1個(gè)個(gè)體的中間部分 scro(2,chb1+1:chb2)=middle;%用第1個(gè)個(gè)體的中間部分替換第2個(gè)個(gè)體的中間部分 %-以下用部分映射交叉（PMX）