物流配送中的最優(yōu)路徑規(guī)劃模擬軟件

1、物流配送中的最優(yōu)路徑規(guī)劃模擬軟件說(shuō)明書(shū) 學(xué)校：武漢輕工大學(xué)院系：數(shù)學(xué)與計(jì)算機(jī)學(xué)院 專(zhuān)業(yè)：信息與計(jì)算科學(xué) 指導(dǎo)教師：王防修 小組名稱(chēng)：一蘋(píng)微歌 小組成員：胡鵬 程新強(qiáng) 彭肖飛日期：_年_月_日目錄1引言-12算法思路-23總體設(shè)計(jì)-154系統(tǒng)出錯(cuò)處理設(shè)計(jì)-175客戶(hù)數(shù)據(jù)生成模塊設(shè)計(jì)說(shuō)明-186行車(chē)路徑最短模塊設(shè)計(jì)說(shuō)明-187行車(chē)時(shí)間最短模塊設(shè)計(jì)說(shuō)明-198解決堵車(chē)問(wèn)題模塊設(shè)計(jì)說(shuō)明-209未解決的問(wèn)題-2110參考資料-211引言1.1編寫(xiě)目的在B2C農(nóng)產(chǎn)品電子商務(wù)物流配送時(shí)，物流車(chē)裝載當(dāng)日需要配送的貨品從倉(cāng)庫(kù)出發(fā)，按照事先規(guī)劃好的最優(yōu)配送路徑為每一個(gè)客戶(hù)進(jìn)行配送，最后返回倉(cāng)庫(kù)。物流配送模擬系統(tǒng)就

2、是在配送之前需要根據(jù)客戶(hù)的配送地址間線(xiàn)路間距、經(jīng)驗(yàn)路況做分析計(jì)算出一條最優(yōu)配送路徑。在配送過(guò)程中，如果某路段堵車(chē)，物流配送模擬系統(tǒng)需要?jiǎng)討B(tài)調(diào)整配送路線(xiàn)。1.2背景說(shuō)明設(shè)計(jì)一個(gè)物流配送中的最優(yōu)路徑規(guī)劃模擬軟件，解決物流配送過(guò)程中路程最短，時(shí)間最短以及堵車(chē)后重新規(guī)劃等問(wèn)題，并在軟件的界面上模擬車(chē)輛的運(yùn)行。隨著市場(chǎng)經(jīng)濟(jì)的發(fā)展和物流技術(shù)專(zhuān)業(yè)化水平的提高，物流配送業(yè)得到了迅猛發(fā)展。配送路徑的選擇是否合理，對(duì)加快配送速度、提高服務(wù)質(zhì)量、降低配送成本及增加經(jīng)濟(jì)效益都有較大影響。配送路徑的優(yōu)化問(wèn)題是物流配送系統(tǒng)的一個(gè)主要問(wèn)題，物流配送路徑的優(yōu)化就是以最低的運(yùn)營(yíng)成本，最快捷的響應(yīng)速度、最短的配送運(yùn)輸時(shí)間，把貨物

3、運(yùn)至用戶(hù)手中，而后兩個(gè)指標(biāo)與第一個(gè)指標(biāo)之間存在著一定的制約關(guān)系，無(wú)法達(dá)到全體的最優(yōu)，因此嚴(yán)格地講，這是一個(gè)多目標(biāo)的優(yōu)化問(wèn)題。1.3定義 T S P（Traveling Salesman Problem）:旅行商問(wèn)題 Backtrack：回溯 GA（Genetic Algorithm）：遺傳算法 SA(Simulated Annealing)：模擬退火算法2算法思路2.1回溯算法2.1.1回溯法的定義 回溯法是一種選優(yōu)搜索法，按選優(yōu)條件向前搜索，以達(dá)到目標(biāo)。但當(dāng)探索到某一步時(shí)，發(fā)現(xiàn)原先選擇并不優(yōu)或達(dá)不到目標(biāo)，就退回一步重新選擇，這種走不通就退回再走的技術(shù)為回溯法，而滿(mǎn)足回溯條件的某個(gè)狀態(tài)的點(diǎn)稱(chēng)為

4、“回溯點(diǎn)”。2.1.2 回溯法的描述 可用回溯法求解的問(wèn)題P，通常要能表達(dá)為：對(duì)于已知的由n元組組成的一個(gè)狀態(tài)空間E= ，i=1，2，n，給定關(guān)于n元組中的一個(gè)分量的一個(gè)約束集D，要求E中滿(mǎn)足D的全部約束條件的所有n元組。其中是分量的定義域，且 | 有限，i=1，2，n。我們稱(chēng)E中滿(mǎn)足D的全部約束條件的任一n元組為問(wèn)題P的一個(gè)解。解問(wèn)題P的最樸素的方法就是枚舉法，即對(duì)E中的所有n元組逐一地檢測(cè)其是否滿(mǎn)足D的全部約束，若滿(mǎn)足，則為問(wèn)題P的一個(gè)解。但顯然，其計(jì)算量是相當(dāng)大的。 我們發(fā)現(xiàn)，對(duì)于許多問(wèn)題，所給定的約束集D具有完備性，即i元組滿(mǎn)足D中僅涉及到，的所有約束意味著j元組（，）一定也滿(mǎn)足D中僅

5、涉及到，的所有約束，i =1，2，n。換句話(huà)說(shuō)，只要存在0jn-1，使得（，）違反D中僅涉及到，的約束之一，則以（，）為前綴的任何n元組（，）一定也違反D中僅涉及到，的一個(gè)約束，因此，對(duì)于約束集D具有完備性的問(wèn)題P，一旦檢測(cè)斷定某個(gè)j元組（，）違反D中僅涉及，的一個(gè)約束，就可以肯定，以（，）為前綴的任何n元組（，）都不會(huì)是問(wèn)題P的解，因而就不必去搜索它們、檢測(cè)它們?；厮莘ㄕ轻槍?duì)這類(lèi)問(wèn)題，利用這類(lèi)問(wèn)題的上述性質(zhì)而提出來(lái)的比枚舉法效率更高的算法。 回溯法首先將問(wèn)題P的n元組的狀態(tài)空間E表示成一棵高為n的帶權(quán)有序樹(shù)T，把在E中求問(wèn)題P的所有解轉(zhuǎn)化為在T中搜索問(wèn)題P的所有解。樹(shù)T類(lèi)似于檢索樹(shù)，它可以

6、這樣構(gòu)造： 設(shè)中的元素可排成(1)，(2)，(-1)，| =，i=1，2，n。從根開(kāi)始，讓T的第I層的每一個(gè)結(jié)點(diǎn)都有個(gè)兒子。這個(gè)兒子到它們的雙親的邊，按從左到右的次序，分別帶權(quán)(1) ，(2) ，() ，i=0，1，2，n-1。照這種構(gòu)造方式，E中的一個(gè)n元組對(duì)應(yīng)于T中的一個(gè)葉子結(jié)點(diǎn)，T的根到這個(gè)葉子結(jié)點(diǎn)的路徑上依次的n條邊的權(quán)分別為，反之亦然。另外，對(duì)于任意的0in-1，E中n元組的一個(gè)前綴I元組對(duì)應(yīng)于T中的一個(gè)非葉子結(jié)點(diǎn)，T的根到這個(gè)非葉子結(jié)點(diǎn)的路徑上依次的I條邊的權(quán)分別為，反之亦然。特別，E中的任意一個(gè)n元組的空前綴（），對(duì)應(yīng)于T的根。 因而，在E中尋找問(wèn)題P的一個(gè)解等價(jià)于在T中搜索一個(gè)

7、葉子結(jié)點(diǎn)，要求從T的根到該葉子結(jié)點(diǎn)的路徑上依次的n條邊相應(yīng)帶的n個(gè)權(quán)滿(mǎn)足約束集D的全部約束。在T中搜索所要求的葉子結(jié)點(diǎn)，很自然的一種方式是從根出發(fā)，按深度優(yōu)先的策略逐步深入，即依次搜索滿(mǎn)足約束條件的前綴1元組（）、前綴2元組（，）、，前綴I元組，直到i=n為止。 在回溯法中，上述引入的樹(shù)被稱(chēng)為問(wèn)題P的狀態(tài)空間樹(shù)；樹(shù)T上任意一個(gè)結(jié)點(diǎn)被稱(chēng)為問(wèn)題P的狀態(tài)結(jié)點(diǎn)；樹(shù)T上的任意一個(gè)葉子結(jié)點(diǎn)被稱(chēng)為問(wèn)題P的一個(gè)解狀態(tài)結(jié)點(diǎn)；樹(shù)T上滿(mǎn)足約束集D的全部約束的任意一個(gè)葉子結(jié)點(diǎn)被稱(chēng)為問(wèn)題P的一個(gè)回答狀態(tài)結(jié)點(diǎn)，它對(duì)應(yīng)于問(wèn)題P的一個(gè)解。2.1.3回溯法的基本思想 (1)針對(duì)所給問(wèn)題，定義問(wèn)題的解空間； (2)確定易于搜索的

8、解空間結(jié)構(gòu)； (3)以深度優(yōu)先方式搜索解空間，并在搜索過(guò)程中用剪枝函數(shù)避免無(wú)效搜索。 用回溯法解題的一個(gè)顯著特征是在搜索過(guò)程中動(dòng)態(tài)產(chǎn)生問(wèn)題的解空間。在任何時(shí)刻，算法只保存從根結(jié)點(diǎn)到當(dāng)前擴(kuò)展結(jié)點(diǎn)的路徑。如果解空間樹(shù)中從根結(jié)點(diǎn)到葉結(jié)點(diǎn)的最長(zhǎng)路徑的長(zhǎng)度為h(n)，則回溯法所需的計(jì)算空間通常為O(n)。而顯式地存儲(chǔ)整個(gè)解空間則需要O(2n)或O(n!)內(nèi)存空間.2.1.4回溯法在TSP問(wèn)題上的應(yīng)用 旅行商問(wèn)題的回溯算法可作為類(lèi)Traveling 的一個(gè)成員。在其他例子中，有一個(gè)成員函數(shù)：Backtrack與T S P。前者是一個(gè)保護(hù)或私有成員，后者是一個(gè)共享成員。函數(shù)G .T S P ( v )返回最

9、少耗費(fèi)旅行的花費(fèi)，旅行自身由整型數(shù)組 v 返回。若網(wǎng)絡(luò)中無(wú)旅行，則返回No edge。Backtrack在排列空間樹(shù)中進(jìn)行遞歸回溯搜索， T S P是其一個(gè)必要的預(yù)處理過(guò)程。TSP假定x（用來(lái)保存到當(dāng)前節(jié)點(diǎn)的路徑的整型數(shù)組），best x（保存目前發(fā)現(xiàn)的最優(yōu)旅行的整型數(shù)組），c c（類(lèi)型為T(mén)的變量，保存當(dāng)前節(jié)點(diǎn)的局部旅行的耗費(fèi)），best c（類(lèi)型為T(mén)的變量，保存目前最優(yōu)解的耗費(fèi)）已被定義為T(mén)raveling中的靜態(tài)數(shù)據(jù)成員。 函數(shù)Backtrack見(jiàn)下。它的結(jié)構(gòu)與函數(shù)Perm相同。當(dāng)i=n 時(shí)，處在排列樹(shù)的葉節(jié)點(diǎn)的父節(jié)點(diǎn)上，并且需要驗(yàn)證從到有一條邊，從到起點(diǎn) 也有一條邊。若兩條邊都存在，則發(fā)

10、現(xiàn)了一個(gè)新旅行。在本例中，需要驗(yàn)證是否該旅行是目前發(fā)現(xiàn)的最優(yōu)旅行。若是，則將旅行和它的耗費(fèi)分別存入best x與best c中。當(dāng)in 時(shí)，檢查當(dāng)前i-1 層節(jié)點(diǎn)的孩子節(jié)點(diǎn)，并且僅當(dāng)以下情況出現(xiàn)時(shí)，移動(dòng)到孩子節(jié)點(diǎn)之一：1. 有從 到的一條邊（如果是這樣的話(huà)，定義了網(wǎng)絡(luò)中的一條路徑）；2.路徑 的耗費(fèi)小于當(dāng)前最優(yōu)解的耗費(fèi)。變量cc 保存目前所構(gòu)造的路徑的耗費(fèi)。每次找到一個(gè)更好的旅行時(shí)，除了更新best x 的耗費(fèi)外，Backtrack需耗時(shí)O(n- 1 )!)。因?yàn)樾璋l(fā)生O(n-1)!)次更新且每一次更新的耗費(fèi)為(n)時(shí)間，因此更新所需時(shí)間為O(n(n- 1)!)。通過(guò)使用加強(qiáng)的條件能減少由Ba

11、cktrack搜索的樹(shù)節(jié)點(diǎn)的數(shù)量。2.2遺傳算法2.2.1遺傳算法的定義 遺傳算法（Genetic Algorithm）是模擬達(dá)爾文的遺傳選擇和自然淘汰的生物進(jìn)化過(guò)程的計(jì)算模型，是一種通過(guò)模擬自然進(jìn)化過(guò)程搜索最優(yōu)解的方法，它是由美國(guó)Michigan大學(xué)J. Holland教授于1975年首先提出來(lái)的，并出版了頗有影響的專(zhuān)著Adaptation in Natural and Artificial Systems，GA這個(gè)名稱(chēng)才逐漸為人所知，J. Holland教授所提出的GA通常為簡(jiǎn)單遺傳算法（SGA）。 遺傳算法是從代表問(wèn)題可能潛在的解集的一個(gè)種群（population）開(kāi)始的，而一個(gè)種群則由

12、經(jīng)過(guò)基因（gene）編碼的一定數(shù)目的個(gè)體(individual)組成。每個(gè)個(gè)體實(shí)際上是染色體(chromosome)帶有特征的實(shí)體。染色體作為遺傳物質(zhì)的主要載體，即多個(gè)基因的集合，其內(nèi)部表現(xiàn)（即基因型）是某種基因組合，它決定了個(gè)體的形狀的外部表現(xiàn)，如黑頭發(fā)的特征是由染色體中控制這一特征的某種基因組合決定的。因此，在一開(kāi)始需要實(shí)現(xiàn)從表現(xiàn)型到基因型的映射即編碼工作。由于仿照基因編碼的工作很復(fù)雜，我們往往進(jìn)行簡(jiǎn)化，如二進(jìn)制編碼，初代種群產(chǎn)生之后，按照適者生存和優(yōu)勝劣汰的原理，逐代（generation）演化產(chǎn)生出越來(lái)越好的近似解，在每一代，根據(jù)問(wèn)題域中個(gè)體的適應(yīng)度（fitness）大小選擇（sele

13、ction）個(gè)體，并借助于自然遺傳學(xué)的遺傳算子（genetic operators）進(jìn)行組合交叉（crossover）和變異（mutation），產(chǎn)生出代表新的解集的種群。這個(gè)過(guò)程將導(dǎo)致種群像自然進(jìn)化一樣的后生代種群比前代更加適應(yīng)于環(huán)境，末代種群中的最優(yōu)個(gè)體經(jīng)過(guò)解碼（decoding），可以作為問(wèn)題近似最優(yōu)解。2.2.2遺傳算法的特點(diǎn) 遺傳算法是一類(lèi)可用于復(fù)雜系統(tǒng)優(yōu)化的具有魯棒性的搜索算法，與傳統(tǒng)的優(yōu)化算法相比，主要有以下特點(diǎn)：（1）遺傳算法以決策變量的編碼作為運(yùn)算對(duì)象。傳統(tǒng)的優(yōu)化算法往往直接決策變量的實(shí)際植本身，而遺傳算法處理決策變量的某種編碼形式，使得我們可以借鑒生物學(xué)中的染色體和基因的概

14、念，可以模仿自然界生物的遺傳和進(jìn)化機(jī)理，也使得我們能夠方便的應(yīng)用遺傳操作算子。（2）遺傳算法直接以適應(yīng)度作為搜索信息，無(wú)需導(dǎo)數(shù)等其它 輔助信息。（3）遺傳算法使用多個(gè)點(diǎn)的搜索信息，具有隱含并行性。（4）遺傳算法使用概率搜索技術(shù)，而非確定性規(guī)則。2.2.3遺傳算法求解TSP問(wèn)題的實(shí)現(xiàn)（1）編碼方法：對(duì)于一個(gè)TSP問(wèn)題的城市列表W,假定每個(gè)城市的一個(gè)訪(fǎng)問(wèn)順序?yàn)門(mén)=,規(guī)定每訪(fǎng)問(wèn)完一個(gè)城市,就從城市列表中將該城市去掉,則用第i(i=1,2,3,n)個(gè)訪(fǎng)問(wèn)的城市在所有未訪(fǎng)問(wèn)城市列表W中的對(duì)應(yīng)位置序號(hào)(i = 1，2，3,n+1)就可表示具體訪(fǎng)問(wèn)哪個(gè)城市,如此這樣直到處理完W中所有的城市。將全部gi順序擺

15、列在一起得到一個(gè)列表:G=就可表示一條巡回路線(xiàn) ,它即為遺傳算法中的一個(gè)個(gè)體的基因. 例如:W=(1 2 3 4 5 6 7 8 9 10 11 12 13 14 15),則Path=(8 15 2 10 7 4 3 11 14 6 12 9 5 13 1)對(duì)應(yīng)Chrome=(8 14 2 8 6 3 2 5 7 3 4 3 2 2 1). 這種編碼法的優(yōu)點(diǎn)在于任意的基因型個(gè)體都對(duì)應(yīng)著一條有實(shí)際意義的巡回路線(xiàn),因此可使用常規(guī)的交叉算子對(duì)其進(jìn)行操作。（2）TSP 問(wèn)題的數(shù)學(xué)模型:假設(shè)有一個(gè)圖G=( V ,E),其中V是頂點(diǎn)集,E是邊集,設(shè)D= 是頂i和頂點(diǎn)j之間的距離所組成的距離矩陣,TSP 問(wèn)

16、題就是求出一條通過(guò)所有頂點(diǎn)且每個(gè)頂點(diǎn)只通過(guò)一次的具有最短距離的回路。若(i j),稱(chēng)為對(duì)稱(chēng)TSP問(wèn)題,否則稱(chēng)為非對(duì)稱(chēng)TSP問(wèn)題。若對(duì)于城市W =的一個(gè)訪(fǎng)問(wèn)順序?yàn)門(mén) =,其中V = 1 , , n,且 = ,則 TSP 問(wèn)題的數(shù)學(xué)模型為:mink = d(i=1,n),其中,d表示頂點(diǎn)和頂點(diǎn)之間的距離.（3）遺傳算法的基本流程: 2.2.4遺傳算法的總體設(shè)定（1）參數(shù)編碼和初始群體設(shè)定:一般來(lái)說(shuō)，遺傳算法對(duì)解空間的編碼大多采用二進(jìn)制編碼形式，但對(duì)TSP一類(lèi)排序問(wèn)題，采用對(duì)訪(fǎng)問(wèn)城市序列進(jìn)行排列組合的方法編碼，即某個(gè)巡回路徑的染色體個(gè)體是該巡回路徑的城市序列。針對(duì)TSP問(wèn)題，編碼規(guī)則通常是取 n 進(jìn)

17、制編碼，即每個(gè)基因僅從1到n的整數(shù)里面取一個(gè)值，每個(gè)個(gè)體的長(zhǎng)度為 n，n為城市總數(shù)。我們定義一個(gè)s -t 大小的 pop 矩陣來(lái)表示群體，針對(duì) 30 個(gè)城市的TSP問(wèn)題，這里 t取值31。即矩陣每一行的前30個(gè)元素表示經(jīng)過(guò)的城市編號(hào)，最后一個(gè)元素表示經(jīng)過(guò)這些城市要走的距離。（2）適應(yīng)度函數(shù)設(shè)計(jì):在TSP的求解中，用距離的總和作為適應(yīng)度函數(shù)來(lái)衡量求解結(jié)果是否最優(yōu)。在 pop矩陣中每一行表示經(jīng)過(guò)的距離的最后一個(gè)元素作為適應(yīng)度函數(shù)。（3）選擇算子:選擇就是從群體中選擇優(yōu)勝個(gè)體、淘汰劣質(zhì)個(gè)體的操作，它是建立在群體中個(gè)體適應(yīng)度評(píng)估基礎(chǔ)上。這里采用方法是最優(yōu)保存方法。算法就是首先將群體中適應(yīng)度最大的 k個(gè)

18、個(gè)體直接替換適應(yīng)度最小的k個(gè)個(gè)體。（4）交叉算子:才交叉算子在遺傳算法中起著核心的作用，它是指將個(gè)體進(jìn)行兩兩配對(duì)，并以交叉概率把配對(duì)的父代個(gè)體加以替換重組而生成新個(gè)體的操作。這里采用的方法是有序交叉法. 有序交叉法實(shí)現(xiàn)的步驟是: 步驟1: 隨機(jī)選取兩個(gè)交叉點(diǎn)；步驟2: 兩后代先分別按對(duì)應(yīng)位置復(fù)制雙親和匹配段中的兩個(gè)子串和； 步驟3.在對(duì)應(yīng)位置交換雙親匹配段以外的城市,如果交換后, 后代中的某一城市與子串中的城市重復(fù)，則將該城市取代子串和中的城市具有相同位置的新城市.直到與子串中的城市均不重復(fù)為止。從圖可知，有序交叉算子能夠有效地繼承雙親的部分基因成分，達(dá)到了進(jìn)化過(guò)程中的遺傳功能，使該算法并不是

19、盲目搜索，而是趨向于使群體具有更多的優(yōu)良基因，最后 實(shí)現(xiàn)尋優(yōu)的目的。（5）變異算子:變異操作是以變異概率對(duì)群體中個(gè)體串某些基因位上的基因值作變動(dòng)，若變異后 子代的適應(yīng)度值更加優(yōu)異，則保留子代染色體，否則，仍保留父代染色體。2.3模擬退火算法2.3.1模擬退火算法的原理 模擬退火算法(Simulated Annealing，SA)來(lái)源于固體退火原理，將固體加溫至充分高，再讓其徐徐冷卻，加溫時(shí)，固體內(nèi)部粒子隨溫升變?yōu)闊o(wú)序狀，內(nèi)能增大，而徐徐冷卻時(shí)粒子漸趨有序，在每個(gè)溫度都達(dá)到平衡態(tài)，最后在常溫時(shí)達(dá)到基態(tài)，內(nèi)能減為最小。根據(jù)Metropolis準(zhǔn)則，粒子在溫度T時(shí)趨于平衡的概率為，其中E為溫度T時(shí)的

20、內(nèi)能，E為其改變量，k為Boltzmann常數(shù)。用固體退火模擬組合優(yōu)化問(wèn)題，將內(nèi)能E模擬為目標(biāo)函數(shù)值f，溫度T演化成控制參數(shù)t，即得到解組合優(yōu)化問(wèn)題的模擬退火算法：由初始解i和控制參數(shù)初值t開(kāi)始，對(duì)當(dāng)前解重復(fù)“產(chǎn)生新解計(jì)算目標(biāo)函數(shù)差接受或舍棄”的迭代，并逐步衰減t值，算法終止時(shí)的當(dāng)前解即為所得近似最優(yōu)解，這是基于蒙特卡羅迭代求解法的一種啟發(fā)式隨機(jī)搜索過(guò)程。退火過(guò)程由冷卻進(jìn)度表(Cooling Schedule)控制，包括控制參數(shù)的初值t及其衰減因子、每個(gè)t值時(shí)的迭代次數(shù)L和停止條件S。 2.3.2模擬退火算法的模型 模擬退火算法可以分解為解空間、目標(biāo)函數(shù)和初始解三部分。模擬退火的基本思想:(1

21、)初始化：初始溫度T(充分大)，初始解狀態(tài)S(是算法迭代起點(diǎn))，每個(gè)T值的迭代次數(shù)L；(2) 對(duì)k=1，L做第(3)至第6步；(3) 產(chǎn)生新解；(4) 計(jì)算增量=C()-C(S)，其中C(S)為評(píng)價(jià)函數(shù) ；(5) 若<0則接受作為新的當(dāng)前解，否則以概率接受作為新的當(dāng)前解；(6) 如果滿(mǎn)足終止條件則輸出當(dāng)前解作為最優(yōu)解，結(jié)束程序。終止條件通常取為連續(xù)若干個(gè)新解都沒(méi)有被接受時(shí)終止算法；7) T逐漸減少，且T->0，然后轉(zhuǎn)第2步。算法對(duì)應(yīng)動(dòng)態(tài)演示圖： 模擬退火算法新解的產(chǎn)生和接受可分為如下四個(gè)步驟： 第一步是由一個(gè)產(chǎn)生函數(shù)從當(dāng)前解產(chǎn)生一個(gè)位于解空間的新解；為便于后續(xù)的計(jì)算和接受，減少算法

22、耗時(shí)，通常選擇由當(dāng)前新解經(jīng)過(guò)簡(jiǎn)單地變換即可產(chǎn)生新解的方法，如對(duì)構(gòu)成新解的全部或部分元素進(jìn)行置換、互換等，注意到產(chǎn)生新解的變換方法決定了當(dāng)前新解的鄰域結(jié)構(gòu)，因而對(duì)冷卻進(jìn)度表的選取有一定的影響。 第二步是計(jì)算與新解所對(duì)應(yīng)的目標(biāo)函數(shù)差。因?yàn)槟繕?biāo)函數(shù)差僅變換部分產(chǎn)生，所以目標(biāo)函數(shù)差的計(jì)算最好按增量計(jì)算。事實(shí)表明，對(duì)大多數(shù)應(yīng)用而言，這是計(jì)算目標(biāo)函數(shù)差的最快方法。 第三步是判斷新解是否被接受,判斷的依據(jù)是一個(gè)接受準(zhǔn)則，最常用的接受準(zhǔn)則是Metropo1is準(zhǔn)則: 若<0則接受作為新的當(dāng)前解S，否則以概率接受作為新的當(dāng)前解S。 第四步是當(dāng)新解被確定接受時(shí)，用新解代替當(dāng)前解，這只需將當(dāng)前解中對(duì)應(yīng)于產(chǎn)生新

23、解時(shí)的變換部分予以實(shí)現(xiàn)，同時(shí)修正目標(biāo)函數(shù)值即可。此時(shí)，當(dāng)前解實(shí)現(xiàn)了一次迭代?？稍诖嘶A(chǔ)上開(kāi)始下一輪試驗(yàn)。而當(dāng)新解被判定為舍棄時(shí)，則在原當(dāng)前解的基礎(chǔ)上繼續(xù)下一輪試驗(yàn)。 模擬退火算法與初始值無(wú)關(guān)，算法求得的解與初始解狀態(tài)S(是算法迭代的起點(diǎn))無(wú)關(guān)；模擬退火算法具有漸近收斂性，已在理論上被證明是一種以概率l 收斂于全局最優(yōu)解的全局優(yōu)化算法；模擬退火算法具有并行性。2.3.3模擬退火算法的簡(jiǎn)單應(yīng)用 作為模擬退火算法應(yīng)用，討論貨郎擔(dān)問(wèn)題(Traveling Salesman Problem，簡(jiǎn)記為T(mén)SP)：設(shè)有n個(gè)城市，用數(shù)碼1,n代表 。城市i和城市j之間的距離為 i, j=1,nTSP問(wèn)題是要找遍訪(fǎng)

24、每個(gè)域市恰好一次的一條回路，且其路徑總長(zhǎng)度為最短。 求解TSP的模擬退火算法模型可描述如下： 解空間 解空間S是遍訪(fǎng)每個(gè)城市恰好一次的所有回路，是1，n的所有循環(huán)排列的集合，S中的成員記為,并記。初始解可選為(1，n) 目標(biāo)函數(shù) 此時(shí)的目標(biāo)函數(shù)即為訪(fǎng)問(wèn)所有城市的路徑總長(zhǎng)度或稱(chēng)為代價(jià)函數(shù)： 我們要求此代價(jià)函數(shù)的最小值。 新解的產(chǎn)生：隨機(jī)產(chǎn)生1和n之間的兩相異數(shù)k和m，若k<m，則將變?yōu)椋?。如果是則將變?yōu)椋荷鲜鲎儞Q方法可簡(jiǎn)單說(shuō)成是“逆轉(zhuǎn)中間或者逆轉(zhuǎn)兩端”。也可以采用其他的變換方法，有些變換有獨(dú)特的優(yōu)越性，有時(shí)也將它們交替使用，得到一種更好方法。 代價(jià)函數(shù)差 設(shè)將變換為 則代價(jià)函數(shù)差為： 根據(jù)

25、上述分析，可寫(xiě)出用模擬退火算法求解TSP問(wèn)題的偽程序： 模擬退火算法的應(yīng)用很廣泛，可以較高的效率求解最大截問(wèn)題(Max Cut Problem)、0-1背包問(wèn)題(Zero One Knapsack Problem)、圖著色問(wèn)題(Graph Coloring Problem)、調(diào)度問(wèn)題(Scheduling Problem)等等。 2.3.4模擬退火算法的參數(shù)控制問(wèn)題模擬退火算法的應(yīng)用很廣泛，可以求解NP完全問(wèn)題，但其參數(shù)難以控制，其主要問(wèn)題有以下三點(diǎn)： (1) 溫度T的初始值設(shè)置問(wèn)題。溫度T的初始值設(shè)置是影響模擬退火算法全局搜索性能的重要因素之一、初始溫度高，則搜索到全局最優(yōu)解的可能性大，但因

26、此要花費(fèi)大量的計(jì)算時(shí)間；反之，則可節(jié)約計(jì)算時(shí)間，但全局搜索性能可能受到影響。實(shí)際應(yīng)用過(guò)程中，初始溫度一般需要依據(jù)實(shí)驗(yàn)結(jié)果進(jìn)行若干次調(diào)整。 (2)退火速度問(wèn)題模擬退火算法的全局搜索性能也與退火速度密切相關(guān)。一般來(lái)說(shuō)，同一溫度下的“充分”搜索(退火)是相當(dāng)必要的，但這需要計(jì)算時(shí)間。實(shí)際應(yīng)用中，要針對(duì)具體問(wèn)題的性質(zhì)和特征設(shè)置合理的退火平衡條件。 (3)溫度管理問(wèn)題。溫度管理問(wèn)題也是模擬退火算法難以處理的問(wèn)題之一。實(shí)際應(yīng)用中，由于必須考慮計(jì)算復(fù)雜度的切實(shí)可行性等問(wèn)題，常采用如下所示的降溫方式：式中k為正的略小于1.00的常數(shù)，t為降溫的次數(shù) 。3總體設(shè)計(jì)3.1需求規(guī)定3.1.1.生成客戶(hù)數(shù)據(jù)1.用戶(hù)可以在軟件界面上隨機(jī)標(biāo)注倉(cāng)庫(kù)與客戶(hù)的地址(不少于10個(gè)客戶(hù))； 2.客戶(hù)的地址表示采用Window設(shè)備坐標(biāo)系?？蛻?hù)地址間的距離采用設(shè)備坐標(biāo)像素間距模擬，坐標(biāo)之間行駛速度采用隨機(jī)算法生成。3.1.2動(dòng)態(tài)路線(xiàn)規(guī)劃 1.軟件可根據(jù)用戶(hù)選擇的路徑規(guī)劃策略，如最短路徑、最少時(shí)間等進(jìn)行配送路線(xiàn)規(guī)劃。 2.模擬車(chē)輛從倉(cāng)庫(kù)出發(fā)，沿著規(guī)劃的配送路線(xiàn)行進(jìn)，最后返回倉(cāng)庫(kù)。在配送過(guò)程中可模擬前方行進(jìn)路線(xiàn)堵車(chē)事件，軟件能夠繞開(kāi)堵車(chē)路段動(dòng)態(tài)規(guī)劃配送路線(xiàn)。3.2運(yùn)行環(huán)境PC，Visual C+6.0軟件開(kāi)發(fā)平臺(tái)3.3基本設(shè)計(jì)概念和處理流程3.4結(jié)構(gòu)設(shè)計(jì)3.4.1結(jié)構(gòu) 3.4.2功能需求與