1、物流配送中的最優路徑規劃模擬軟件說明書 學校：武漢輕工大學院系：數學與計算機學院 專業：信息與計算科學 指導教師：王防修 小組名稱：一蘋微歌 小組成員：胡鵬 程新強 彭肖飛日期：_年_月_日目錄1引言-12算法思路-23總體設計-154系統出錯處理設計-175客戶數據生成模塊設計說明-186行車路徑最短模塊設計說明-187行車時間最短模塊設計說明-198解決堵車問題模塊設計說明-209未解決的問題-2110參考資料-211引言1.1編寫目的在B2C農產品電子商務物流配送時，物流車裝載當日需要配送的貨品從倉庫出發，按照事先規劃好的最優配送路徑為每一個客戶進行配送，最后返回倉庫。物流配送模擬系統就

2、是在配送之前需要根據客戶的配送地址間線路間距、經驗路況做分析計算出一條最優配送路徑。在配送過程中，如果某路段堵車，物流配送模擬系統需要動態調整配送路線。1.2背景說明設計一個物流配送中的最優路徑規劃模擬軟件，解決物流配送過程中路程最短，時間最短以及堵車后重新規劃等問題，并在軟件的界面上模擬車輛的運行。隨著市場經濟的發展和物流技術專業化水平的提高，物流配送業得到了迅猛發展。配送路徑的選擇是否合理，對加快配送速度、提高服務質量、降低配送成本及增加經濟效益都有較大影響。配送路徑的優化問題是物流配送系統的一個主要問題，物流配送路徑的優化就是以最低的運營成本，最快捷的響應速度、最短的配送運輸時間，把貨物

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

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

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

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

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

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

9、少耗費旅行的花費，旅行自身由整型數組 v 返回。若網絡中無旅行，則返回No edge。Backtrack在排列空間樹中進行遞歸回溯搜索， T S P是其一個必要的預處理過程。TSP假定x（用來保存到當前節點的路徑的整型數組），best x（保存目前發現的最優旅行的整型數組），c c（類型為T的變量，保存當前節點的局部旅行的耗費），best c（類型為T的變量，保存目前最優解的耗費）已被定義為Traveling中的靜態數據成員。 函數Backtrack見下。它的結構與函數Perm相同。當i=n 時，處在排列樹的葉節點的父節點上，并且需要驗證從到有一條邊，從到起點 也有一條邊。若兩條邊都存在，則發

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

11、cktrack搜索的樹節點的數量。2.2遺傳算法2.2.1遺傳算法的定義 遺傳算法（Genetic Algorithm）是模擬達爾文的遺傳選擇和自然淘汰的生物進化過程的計算模型，是一種通過模擬自然進化過程搜索最優解的方法，它是由美國Michigan大學J. Holland教授于1975年首先提出來的，并出版了頗有影響的專著Adaptation in Natural and Artificial Systems，GA這個名稱才逐漸為人所知，J. Holland教授所提出的GA通常為簡單遺傳算法（SGA）。 遺傳算法是從代表問題可能潛在的解集的一個種群（population）開始的，而一個種群則由

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

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

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

15、列在一起得到一個列表: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)對應Chrome=(8 14 2 8 6 3 2 5 7 3 4 3 2 2 1). 這種編碼法的優點在于任意的基因型個體都對應著一條有實際意義的巡回路線,因此可使用常規的交叉算子對其進行操作。（2）TSP 問題的數學模型:假設有一個圖G=( V ,E),其中V是頂點集,E是邊集,設D= 是頂i和頂點j之間的距離所組成的距離矩陣,TSP 問

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

17、制編碼，即每個基因僅從1到n的整數里面取一個值，每個個體的長度為 n，n為城市總數。我們定義一個s -t 大小的 pop 矩陣來表示群體，針對 30 個城市的TSP問題，這里 t取值31。即矩陣每一行的前30個元素表示經過的城市編號，最后一個元素表示經過這些城市要走的距離。（2）適應度函數設計:在TSP的求解中，用距離的總和作為適應度函數來衡量求解結果是否最優。在 pop矩陣中每一行表示經過的距離的最后一個元素作為適應度函數。（3）選擇算子:選擇就是從群體中選擇優勝個體、淘汰劣質個體的操作，它是建立在群體中個體適應度評估基礎上。這里采用方法是最優保存方法。算法就是首先將群體中適應度最大的 k個

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

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

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

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

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

23、解時的變換部分予以實現，同時修正目標函數值即可。此時，當前解實現了一次迭代。可在此基礎上開始下一輪試驗。而當新解被判定為舍棄時，則在原當前解的基礎上繼續下一輪試驗。 模擬退火算法與初始值無關，算法求得的解與初始解狀態S(是算法迭代的起點)無關；模擬退火算法具有漸近收斂性，已在理論上被證明是一種以概率l 收斂于全局最優解的全局優化算法；模擬退火算法具有并行性。2.3.3模擬退火算法的簡單應用 作為模擬退火算法應用，討論貨郎擔問題(Traveling Salesman Problem，簡記為TSP)：設有n個城市，用數碼1,n代表 。城市i和城市j之間的距離為 i, j=1,nTSP問題是要找遍訪

24、每個域市恰好一次的一條回路，且其路徑總長度為最短。 求解TSP的模擬退火算法模型可描述如下： 解空間 解空間S是遍訪每個城市恰好一次的所有回路，是1，n的所有循環排列的集合，S中的成員記為,并記。初始解可選為(1，n) 目標函數 此時的目標函數即為訪問所有城市的路徑總長度或稱為代價函數： 我們要求此代價函數的最小值。 新解的產生：隨機產生1和n之間的兩相異數k和m，若k<m，則將變為：。如果是則將變為：上述變換方法可簡單說成是“逆轉中間或者逆轉兩端”。也可以采用其他的變換方法，有些變換有獨特的優越性，有時也將它們交替使用，得到一種更好方法。 代價函數差 設將變換為 則代價函數差為： 根據

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

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