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

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

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

3、指標(biāo)之間存在著一定的制約關(guān)系，無法達(dá)到全體的最優(yōu)，因此嚴(yán)格地講，這是一個(gè)多目標(biāo)的優(yōu)化問題。1.3定義 t s p（traveling salesman problem）:旅行商問題 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ù)為回溯法，而滿足回溯條件的某個(gè)狀態(tài)的點(diǎn)稱為“回溯點(diǎn)”。2.1.2 回溯法的描

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

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

6、，(2)，(-1)，| =，i=1，2，n。從根開始，讓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中尋找問題p的一個(gè)解等價(jià)于在t中搜索一個(gè)葉子結(jié)點(diǎn)，要求從t的根到該葉子結(jié)點(diǎn)

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

8、搜索解空間，并在搜索過程中用剪枝函數(shù)避免無效搜索。 用回溯法解題的一個(gè)顯著特征是在搜索過程中動(dòng)態(tài)產(chǎn)生問題的解空間。在任何時(shí)刻，算法只保存從根結(jié)點(diǎn)到當(dāng)前擴(kuò)展結(jié)點(diǎn)的路徑。如果解空間樹中從根結(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問題上的應(yīng)用 旅行商問題的回溯算法可作為類traveling 的一個(gè)成員。在其他例子中，有一個(gè)成員函數(shù)：backtrack與t s p。前者是一個(gè)保護(hù)或私有成員，后者是一個(gè)共享成員。函數(shù)g .t s p ( v )返回最少耗費(fèi)旅行的花費(fèi)，旅行自身由整型數(shù)

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

10、是否該旅行是目前發(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. 有從 到的一條邊（如果是這樣的話，定義了網(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)!)。通過使用加強(qiáng)的條件能減少由backtrack搜索的樹節(jié)點(diǎn)的數(shù)量。

11、2.2遺傳算法2.2.1遺傳算法的定義 遺傳算法（genetic algorithm）是模擬達(dá)爾文的遺傳選擇和自然淘汰的生物進(jìn)化過程的計(jì)算模型，是一種通過模擬自然進(jìn)化過程搜索最優(yōu)解的方法，它是由美國michigan大學(xué)j. holland教授于1975年首先提出來的，并出版了頗有影響的專著adaptation in natural and artificial systems，ga這個(gè)名稱才逐漸為人所知，j. holland教授所提出的ga通常為簡(jiǎn)單遺傳算法（sga）。 遺傳算法是從代表問題可能潛在的解集的一個(gè)種群（population）開始的，而一個(gè)種群則由經(jīng)過基因（gene）編碼的一定數(shù)目

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

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

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

15、一條巡回路線 ,它即為遺傳算法中的一個(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í)際意義的巡回路線,因此可使用常規(guī)的交叉算子對(duì)其進(jìn)行操作。（2）tsp 問題的數(shù)學(xué)模型:假設(shè)有一個(gè)圖g=( v ,e),其中v是頂點(diǎn)集,e是邊集,設(shè)d= 是頂i和頂點(diǎn)j之間的距離所組成的距離矩陣,tsp 問題就是求出一條通過所有頂點(diǎn)且每個(gè)頂

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

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

18、（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)化過程中的遺傳功能，使該算法并不是盲目搜索，而是趨向于使群體具有更多

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)來源于固體退火原理，將固體加溫至充分高，再讓其徐徐冷卻，加溫時(shí)，固體內(nèi)部粒子隨溫升變?yōu)闊o序狀，內(nèi)能增大，而徐徐冷卻時(shí)粒子漸趨有序，在每個(gè)溫度都達(dá)到平衡態(tài)，最后在常溫時(shí)達(dá)到基態(tài)，內(nèi)能減為最小。根據(jù)metropolis準(zhǔn)則，粒子在溫度t時(shí)趨于平衡的概率為，其中e為溫度t時(shí)的內(nèi)能，e為其改變量，k為boltz

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

21、始解狀態(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，然后轉(zhuǎn)第2步。算法對(duì)應(yīng)動(dòng)態(tài)演示圖： 模擬退火算法新解的產(chǎn)生和接受可分為如下四個(gè)步驟： 第一步是由一個(gè)產(chǎn)生函數(shù)從當(dāng)前解產(chǎn)生一個(gè)位于解空間的新解；為便于后續(xù)的計(jì)算和接受，減少算法耗時(shí)，通常選擇由當(dāng)前新解經(jīng)過簡(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)函

22、數(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)生新解時(shí)的變換部分予以實(shí)現(xiàn)，同時(shí)修正目標(biāo)函數(shù)值即可。此時(shí)，當(dāng)前解實(shí)現(xiàn)了一次迭代?？稍诖嘶A(chǔ)上開始下一輪試驗(yàn)。而當(dāng)新解被判定為舍棄時(shí)，則在原當(dāng)前解的基礎(chǔ)上繼續(xù)下一輪試驗(yàn)。 模擬退火算法與初始值無關(guān)，算法求得的解與初始解狀態(tài)s(是算法迭代的起點(diǎn))無關(guān)；模擬

23、退火算法具有漸近收斂性，已在理論上被證明是一種以概率l 收斂于全局最優(yōu)解的全局優(yōu)化算法；模擬退火算法具有并行性。2.3.3模擬退火算法的簡(jiǎn)單應(yīng)用 作為模擬退火算法應(yīng)用，討論貨郎擔(dān)問題(traveling salesman problem，簡(jiǎn)記為tsp)：設(shè)有n個(gè)城市，用數(shù)碼1,n代表 。城市i和城市j之間的距離為 i, j=1,ntsp問題是要找遍訪每個(gè)域市恰好一次的一條回路，且其路徑總長(zhǎng)度為最短。 求解tsp的模擬退火算法模型可描述如下： 解空間 解空間s是遍訪每個(gè)城市恰好一次的所有回路，是1，n的所有循環(huán)排列的集合，s中的成員記為,并記。初始解可選為(1，n) 目標(biāo)函數(shù) 此時(shí)的目標(biāo)函數(shù)即為

24、訪問所有城市的路徑總長(zhǎng)度或稱為代價(jià)函數(shù)： 我們要求此代價(jià)函數(shù)的最小值。 新解的產(chǎn)生：隨機(jī)產(chǎn)生1和n之間的兩相異數(shù)k和m，若km，則將變?yōu)椋?。如果是則將變?yōu)椋荷鲜鲎儞Q方法可簡(jiǎn)單說成是“逆轉(zhuǎn)中間或者逆轉(zhuǎn)兩端”。也可以采用其他的變換方法，有些變換有獨(dú)特的優(yōu)越性，有時(shí)也將它們交替使用，得到一種更好方法。 代價(jià)函數(shù)差 設(shè)將變換為 則代價(jià)函數(shù)差為： 根據(jù)上述分析，可寫出用模擬退火算法求解tsp問題的偽程序： 模擬退火算法的應(yīng)用很廣泛，可以較高的效率求解最大截問題(max cut problem)、0-1背包問題(zero one knapsack problem)、圖著色問題(graph coloring

25、 problem)、調(diào)度問題(scheduling problem)等等。 2.3.4模擬退火算法的參數(shù)控制問題模擬退火算法的應(yīng)用很廣泛，可以求解np完全問題，但其參數(shù)難以控制，其主要問題有以下三點(diǎn)： (1) 溫度t的初始值設(shè)置問題。溫度t的初始值設(shè)置是影響模擬退火算法全局搜索性能的重要因素之一、初始溫度高，則搜索到全局最優(yōu)解的可能性大，但因此要花費(fèi)大量的計(jì)算時(shí)間；反之，則可節(jié)約計(jì)算時(shí)間，但全局搜索性能可能受到影響。實(shí)際應(yīng)用過程中，初始溫度一般需要依據(jù)實(shí)驗(yàn)結(jié)果進(jìn)行若干次調(diào)整。 (2)退火速度問題模擬退火算法的全局搜索性能也與退火速度密切相關(guān)。一般來說，同一溫度下的“充分”搜索(退火)是相當(dāng)必要

26、的，但這需要計(jì)算時(shí)間。實(shí)際應(yīng)用中，要針對(duì)具體問題的性質(zhì)和特征設(shè)置合理的退火平衡條件。 (3)溫度管理問題。溫度管理問題也是模擬退火算法難以處理的問題之一。實(shí)際應(yīng)用中，由于必須考慮計(jì)算復(fù)雜度的切實(shí)可行性等問題，常采用如下所示的降溫方式：式中k為正的略小于1.00的常數(shù)，t為降溫的次數(shù) 。3總體設(shè)計(jì)3.1需求規(guī)定3.1.1.生成客戶數(shù)據(jù)1.用戶可以在軟件界面上隨機(jī)標(biāo)注倉庫與客戶的地址(不少于10個(gè)客戶)； 2.客戶的地址表示采用window設(shè)備坐標(biāo)系?？蛻舻刂烽g的距離采用設(shè)備坐標(biāo)像素間距模擬，坐標(biāo)之間行駛速度采用隨機(jī)算法生成。3.1.2動(dòng)態(tài)路線規(guī)劃 1.軟件可根據(jù)用戶選擇的路徑規(guī)劃策略，如最短路徑、最少時(shí)間等進(jìn)行配送路線規(guī)劃。 2.模擬車輛從倉庫出發(fā)，沿著規(guī)劃的配送路線行進(jìn)，最后返回倉庫。在配送過程中可模擬前方行進(jìn)路線堵車事件，軟件能夠繞開堵車路段動(dòng)態(tài)規(guī)劃配送路線。3.2運(yùn)行環(huán)境pc，visual c+6.0軟件開發(fā)平臺(tái)3.3基本設(shè)計(jì)概念和處理流程3.4結(jié)構(gòu)設(shè)計(jì)3.4.1結(jié)構(gòu) 3.4.2功能需求與程序