資源描述：
《物流配送管理中路徑優(yōu)化問題分析》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、摘要：經(jīng)典的優(yōu)化理論大多是在已知條件不變的基礎(chǔ)上給出最優(yōu)方案（即最優(yōu)解），其最優(yōu)性在條件發(fā)生變化時就會失去其最優(yōu)性。本文提出的局內(nèi)最短路問題，就是在已知條件不斷變化的條件下，如何來快速的計算出此時的最優(yōu)路徑，文章設(shè)計了解決該問題的一個逆向標(biāo)號算法，將它與傳統(tǒng)算法進(jìn)行了比較和分析，并針對實際中的物流配送管理中路徑優(yōu)化問題，按照不同的算法分別進(jìn)行了詳細(xì)的闡述與分析。一、引言現(xiàn)實生活中的許多論文發(fā)表經(jīng)濟(jì)現(xiàn)象通常都具有非常強(qiáng)的動態(tài)特征，人們對于這些現(xiàn)象一般是先進(jìn)行數(shù)學(xué)上的抽象，然后用靜態(tài)或統(tǒng)計的方法來加以研究和處理。從優(yōu)化的理論和方法上看，經(jīng)典的優(yōu)化理論大多是站
2、在旁觀者的立場上看問題，即首先確定已知條件，然后在假設(shè)這些已知條件不變的基礎(chǔ)上給出最優(yōu)方案（即最優(yōu)解）。條件一旦發(fā)生變化，這種方法所給出的最優(yōu)方案就會失去其最優(yōu)性。在變化的不確定因素對所考慮的問題影響很大的時候，經(jīng)典的優(yōu)化方法有：一是將可變化的因素隨機(jī)化，尋求平均意義上的最優(yōu)方案，二是考慮可變化因素的最壞情形，尋求最壞情形達(dá)到最優(yōu)的方案。這兩種處理方法對變化因素的一個特例都可能給出離實際最優(yōu)解相距甚遠(yuǎn)的解，這顯然是難以滿足實際的要求的。那么是否存在一種方法，它在變化因素的每一個特例中都能給出一個方案，使得這一方案所得到的解離最優(yōu)方案給出的解總在一定的比例
3、之內(nèi)呢？近年來興起的局內(nèi)問題與競爭算法的研究結(jié)果在一定意義上給如上問題一個肯定的答案。其實本文所提出的逆向標(biāo)號算法就是對應(yīng)局內(nèi)最短路問題的一個競爭算法，從本質(zhì)上來說它是一種貪婪算法，在不知將來情況的條件下，求出當(dāng)前狀態(tài)下的最優(yōu)解。[1]本文所考慮問題的實際背景是一個物流配送公司對其運輸車輛的調(diào)度。假設(shè)物流公司需要用貨車把貨物從初始點O(Origin)運送到目的點D(Destination)。從日常來看，物流公司完全可以通過將整個城市交通網(wǎng)絡(luò)看成一個平面圖來進(jìn)行運算，找到一條從O到D的最短路徑以減少運輸費用和節(jié)省運輸時間?，F(xiàn)考慮如下一個問題：如果當(dāng)運輸車輛
4、沿著最短路徑行駛到最短路徑上的一點A，發(fā)現(xiàn)前方路徑上的B點由于車輛擁塞而不能通過，車輛必須改道行駛，而此時物流配送公司應(yīng)如何應(yīng)對來保證其花費最低。問題推展開去，如果不是單個堵塞點，而是一個堵塞點序列，那物流配送公司又將如何來設(shè)計其最短路算法來在最短的時間內(nèi)求出已知條件發(fā)生變化后的最優(yōu)路徑，從而有效的調(diào)度其運輸車。本文首先建立了物流配送公司動態(tài)最短路的數(shù)學(xué)模型，相比較給出了求本文所提出的動態(tài)最短路問題的傳統(tǒng)算法和作者提出的逆向標(biāo)號算法，并分析了各自的算法復(fù)雜度。二、數(shù)學(xué)模型假設(shè)城市交通網(wǎng)絡(luò)是一個平面圖，記為G，各個交通路口對應(yīng)于圖G上的各個頂點，令G=(G
5、，V)為一邊加權(quán)無向圖，其中V為頂點的集合，E為邊的集合，
6、G
7、=n，對于一般平面圖上的三點之間，一定滿足三角不等式，即任意三角形的兩邊之和一定不小于另外一邊。對于本文要討論的城市交通網(wǎng)絡(luò)來說，即，任意三個結(jié)點之間的距離一定滿足三角不等式。我們用O來表示運輸?shù)钠鹗键c，D表示運輸?shù)哪康狞c。SP表示在沒有路口堵塞情況下的最短路徑，W(SP)表示沿著最短路徑所要花費的運輸費用。以下的討論都是基于如下的基本假設(shè)：第一，去掉堵塞點后圖G仍是連通的。第二，只有當(dāng)運輸車走到前一點后，才能發(fā)現(xiàn)后面的一點發(fā)生堵塞而不能通過。三、算法分析對于本文的上述問題，有兩種算法一(傳
8、統(tǒng)算法)和二(逆向標(biāo)號算法)可以滿足要求，但兩種算法在求動態(tài)最短路的過程中都將會用到Dijkstra算法[2]，通過對Dijkstra算法的分析我們知道，Dijkstra算法采用了兩個集合這樣的數(shù)據(jù)結(jié)構(gòu)來安排圖的頂點，集合S表示已經(jīng)被標(biāo)記點的集合，集合（G－S）表示未被標(biāo)記點的集合，一個點的標(biāo)號是這個點到源節(jié)點的最短距離，算法的主要思想是：從G－S集合中選取具有最小標(biāo)號的點w，而后把w點放入S集合中。因為S集合就是已經(jīng)被標(biāo)記點的集合，然后再從G-S集合中將所有經(jīng)過點w而與源節(jié)點相通的v點的路徑值T[v]統(tǒng)統(tǒng)作調(diào)整（如果存在某個點v，它的路徑值大于已經(jīng)被標(biāo)
9、記的點w的路徑值與點v到點w的距離之和，那么就對所有與點v相通的點的路徑值進(jìn)行調(diào)整）。重復(fù)此過程直至所有的點全部進(jìn)入S集合。從以上的分析我們可以看出，當(dāng)進(jìn)行完Dijkstra算法，所有的點都將會被標(biāo)號。首先我們先給出本節(jié)將會用到的符號和定義。我們用WOA表示沿著最短路從O點到A點的距離，W(SPAD)表示沿著最優(yōu)路徑SPAD從A點到D點的距離。Wij表示從i點到j(luò)點邊的權(quán)，T[v]表示的v點標(biāo)號值。[3]（一）算法一第一步，對于給定的平面圖G，運用Dijkstr算法求出從起點O點到終點D點的最優(yōu)路徑SP。第二步，到達(dá)A點后，如果下一個頂點B發(fā)生車輛擁塞不
10、能通車，計算子圖G-{B}。第三步，在此運用Dijkstra算法求出此時從A點到
