運用動態(tài)規(guī)劃模型解決最短路徑問題

1、運用動態(tài)規(guī)劃模型解決物流配送中的最短路徑問題王嘉?。}城師范學(xué)院數(shù)學(xué)科學(xué)學(xué)院09 （1）班）摘要：隨著現(xiàn)代社會的高速發(fā)展，物流配送成為了連接各個生產(chǎn)基地的樞紐，運輸?shù)某杀締栴}也成為了企 業(yè)發(fā)展的關(guān)鍵。運費不但與運量有關(guān)，而且與運輸行走的線路相關(guān)。傳統(tǒng)的運輸問題沒有考慮交通網(wǎng)絡(luò)， 在已知運價的條件下僅求出最優(yōu)調(diào)運方案，沒有求出最優(yōu)行走路徑。 文中提出“網(wǎng)絡(luò)上的物流配送問題 “，在未知運價，運量確定的情況下，將運輸過程在每階段中選取最優(yōu)策略，最后找到整個過程的總體最優(yōu)目 標(biāo)，節(jié)省企業(yè)開支。關(guān)鍵詞：動態(tài)規(guī)劃，數(shù)學(xué)模型，物流配送 ，最優(yōu)路徑1引言物流配送是現(xiàn)代化物流系統(tǒng)的一個重要環(huán)節(jié)。它是指按用戶的訂

2、貨要求，在 配送中心進(jìn)行分貨、配貨，并將配好的貨物及時送交收貨人的活動。在物流配送 業(yè)務(wù)中，合理選擇配送徑路，對加快配送速度、提高服務(wù)質(zhì)量、降低配送成本及 增加經(jīng)濟效益都有較大影響。物流配送最短徑路是指物品由供給地向需求地的移 動過程中，所經(jīng)過的距離最短（或運輸?shù)臅r間最少，或運輸費用最低），因此， 選定最短徑路是提高物品時空價值的重要環(huán)節(jié)。1經(jīng)典的Dijkstra 算法和Floyd算法思路清楚,方法簡便，但隨著配送點數(shù)的 增加，計算的復(fù)雜性以配送點數(shù)的平方增加，并具有一定的主觀性。我國學(xué)者用模 糊偏好解試圖改善經(jīng)典方法5!取得了較好的效果。遺憾的是，模糊偏好解本身就 不完全是客觀的。文獻(xiàn)6】詳

3、細(xì)分析了經(jīng)典方法的利弊之后，提出將鄰接矩陣上三 角和下三角復(fù)制從而使每條邊成為雙通路徑，既適用于有向圖也適用于無向圖， 但復(fù)雜性增加了。為了避免上述方法存在的不足，本文以動態(tài)規(guī)劃為理論，選擇合 理的最優(yōu)值函數(shù)，用于解決物流配送最短路徑問題。動態(tài)規(guī)劃是解決多階段決策過程最優(yōu)化問題的一種數(shù)學(xué)方法。1951年美國數(shù)學(xué)家Bellman （貝爾曼）等人根據(jù)一類多階段決策問題的特性，提出了解決這 類問題的“最優(yōu)性原理”，并研究了許多實際問題，從而創(chuàng)建了最優(yōu)化問題的一 種新方法一一動態(tài)規(guī)劃。動態(tài)規(guī)劃在工程技術(shù)、管理、經(jīng)濟、工業(yè)生產(chǎn)、軍事及現(xiàn)代控制工程等方 面都有廣泛的應(yīng)用，而且由于動態(tài)規(guī)劃方法有其獨特之處，

4、 在解決某些實際問題 時，顯得更加方便有效。由于決策過程的時間參數(shù)有離散的和連續(xù)的情況，故決策過程分為離散決策過程和連續(xù)決策過程。2這種技術(shù)采用自底向上的方式遞推求值， 將待求解的問題分解成若干個子問題，先求解子問題，并把子問題的解存儲起來以便以后用來計算所需要求的解。簡言之， 動態(tài)規(guī)劃的基本思想就是把全局的問題化為局部的問題，為了全局最優(yōu)必須局部最優(yōu)。多階段決策問題是根據(jù)問題本身的特點，將其求解的過程劃分為若干個相互獨立又相互聯(lián)系的階段，在每個階段都需要做出決策，并且在每個階段的確定后再轉(zhuǎn)移到下一個階段，在每一個階段選取其最有決策，從而實現(xiàn)整個過程總體決策最優(yōu)的目的。2,4適合用動態(tài)規(guī)劃方法

5、求解的問題是一類特殊的多階段決策問題，具有“無后效性”的多階段決策問題，一般具有以下特點：(1) 可以劃分為若干個階段，問題的求解過程就是對若干個階段的一系列決策過程。(2) 每個階段有若干個可能狀態(tài)。(3) 一個決策將你從一個階段的一種狀態(tài)帶到下一個階段的某種狀態(tài)。(4) 在任一個階段，最佳的決策序列和該階段以前的決策無關(guān)。(5) 各階段狀態(tài)之間的轉(zhuǎn)換有明確定義的費用，而且在選擇最佳決策時有遞推關(guān)系(即動態(tài)轉(zhuǎn)移方程)。 32 動態(tài)規(guī)劃模型在現(xiàn)實生活的生產(chǎn)運輸中，往往出發(fā)地與目的地之間有多種路線可供選擇，不同的路線所花費的時間與費用也不同，時間與費用決定著企業(yè)的發(fā)展，這就需要選擇最短的路徑來提

6、高效率。為了解決這個問題，將動態(tài)規(guī)劃的理論與方法運用于生產(chǎn)運輸中，節(jié)約了時間，為： 企業(yè)的發(fā)展提供了契機。建立這個規(guī)劃模型的具體步驟如下：劃分階段：把所給問題的過程，恰當(dāng)?shù)膭澐譃槿舾蓚€相互聯(lián)系的部分，以便于求解，其中每個部分叫階段。通常用k表示階段變量確定狀態(tài)變量及其取值范圍：狀態(tài)表示在任一階段所處的，它既是該階段的起點， 又是前一階段的終點。通常一個階段有若干個階段。描述狀態(tài)的變量稱為狀態(tài)變量。參數(shù)&表示第k階段的狀態(tài)變量。該階段所有可能狀態(tài)的全體稱為狀態(tài)集合，記為s 。狀態(tài)變量要能描述決策過程演變的狀態(tài)，又要滿足無后效k性的要求，而且維數(shù)要盡可能地少。確定決策變量及其取值范圍：在某

7、一階段，當(dāng)狀態(tài)給定后，往往可以作出 不同的決定，從而確定下一階段的狀態(tài)，這種決定稱為決策。描述決策的變量稱 為決策變量，用Uk(Sk朕示第k階段當(dāng)狀態(tài)為Sk時的決策變量，它是狀態(tài)變量Sk的 函數(shù)。決策變量的取值范圍稱為決策集合，通常用 Dk(Sk )表示第k階段狀態(tài)為Sk 時的允許決策集合。顯然有Uk (Sk產(chǎn)Dk (Sk )。建立狀態(tài)轉(zhuǎn)移方程：狀態(tài)轉(zhuǎn)移方程描述由一個狀態(tài)到另一個狀態(tài)的演變過 程。因為某一階段的狀態(tài)變量及決策變量取定后，下一階段的狀態(tài)就隨之而定。 用Sk+=T(Sk，Uk )表示k階段與k+1階段狀態(tài)的變換規(guī)律指標(biāo)函數(shù)和最優(yōu)指標(biāo)函數(shù)值：階段指標(biāo)(又稱階段效益)是衡量該階段決 策

8、效果的數(shù)量指標(biāo)，它是整個系統(tǒng)效益的一部分，是階段狀態(tài)和階段決策的函數(shù)。 用dk ”Uk)表小在第k階段由狀態(tài)Sk和執(zhí)行決策Uk(Sk四得的效益。指標(biāo)函數(shù)(又稱目標(biāo)函數(shù))是衡量所實現(xiàn)過程優(yōu)劣的一種數(shù)量指標(biāo)， 它表示 系統(tǒng)執(zhí)行某一策略所產(chǎn)生的效益， 它是定義在過程(可以是全過程，也可以是后 部子過程)上的數(shù)量函數(shù)，用fk,n表示：fk,n fk,n Sk , Uk , Sk 1 , Uk -l1, , Sn 1 , k 1,2, n當(dāng)初始狀態(tài)給定時，過程的策略就確定了，因而指標(biāo)函數(shù)也就確定，故指標(biāo) 函數(shù)是初始狀態(tài)和策略的函數(shù)，即：fk,n = fk,n I.Sk , Pk (Sk ) I,指標(biāo)函數(shù)

9、fk,n的最優(yōu)值，稱為最優(yōu)指標(biāo)函數(shù)值，記為 fk(Sk),它表示從第k階 段由狀態(tài)Sk出發(fā)到過程結(jié)束時所獲得的最優(yōu)指標(biāo)函數(shù)值。 在最短路線問題中，fk,n 表示從第k階段的點Sk至終點G的距離，fk (Sk)表示由點Sk到G的最短距離，用 dk(Sk,Uk廬示在第k階段由點Sk到點Sk+=Uk(Sk )的距離。最后得到動態(tài)規(guī)劃的一般模型為：fksk= opt1dksk,uk-fk1uksk;,Uk .Dk skfk i sk i =0, k =n,n -1, T,fk (sk)為從斗犬態(tài)Sk出發(fā)到終點的最優(yōu)效益，“opt”是optimization (最優(yōu)化)的縮寫213實例分析為進(jìn)一步說明該

10、方法的有效性和實用性，先將該方法運用于某物流配送網(wǎng)絡(luò)中：設(shè)某物流配送網(wǎng)絡(luò)圖由9個配送點組成，點Ao為配送中心，A9為終點，試求自A9到圖中任何配送點的最短距離。圖中相鄰兩點的連線上標(biāo)有兩點間的距離口首先根據(jù)網(wǎng)絡(luò)圖以及上面的建模方法我們可以將運輸過程劃分成三個階段，分別為：第一階段Ao ,第二階段Ai，A3，A5，A7 ,第三階段A2，A4，A6，A8 ,顯然兩點之間直線 路徑小于折線路徑階段變量用k表示；狀態(tài)變量Ak表示k階段初可能的位置;決策fk(Ak/示k階段初可能選擇的路線；由后向前逐步推移計算最優(yōu)路徑：當(dāng) k = 3 時，由 A2, A4，A6,A8 至 |JA9 只有一條路線，故 f

11、3(A2尸6, f304) = 8,f3 ( Ag)=4,£335) = 14當(dāng)k=2時，出發(fā)點有A1, A3,A5, A7三個，若從打出發(fā)，只有一個選擇，至A2,所以f2fAi=27, ，一 一一，d2 A3，A2 , f3 A2f5 - 16從A出發(fā)，有兩個選擇，至A2，A4 ,所以f2fA3 =minI m m Jy = min W *=18d2 A3, A4 - f3 A4 “J10 8,d 2 A5, A4 f3 A416-8從A5出發(fā)，有兩個選擇，至 A4, A6 ,所以f2fA5、= min()< )$ = min&=19d2 A5, A6 f3 A6 )

12、j J15 - 4,d2 A7, A6 . 一 f3 A6 -.|f 11 - 4 I從A7出發(fā)，有兩個選擇，至A6, A8 ,所以f2fA7 =min<)')$ = min I*=15d2 A7,A8 ' f3 A8 "：(I12 - 14最短路線是 A7 A6 A9當(dāng)k=1時，出發(fā)點有A0一個，若從A0出發(fā)，至A1 ,所以f1(Ao )=31若從A0出發(fā)，至A3 ,所以f1 (A。)=25若從A0出發(fā)，至A5 ,所以f1 (A0 )=27若從A。出發(fā)，至A7，所以 (A。產(chǎn)4由上面計算得到最優(yōu)路徑 f1(A0尸24,最優(yōu)路徑為A°t A7TA6 T

13、 A9由本實例我們可以總結(jié)出動態(tài)規(guī)劃的優(yōu)越性所在：(1)求解過程，結(jié)果清晰明了；(2)能得到一組解，有利于分析結(jié)果；(3)易于確定全局最優(yōu)解；4結(jié)論用動態(tài)規(guī)劃解決多階段決策問題可以提高效率，而且思路清晰簡便，同時易于實現(xiàn)，雖然使用動態(tài)規(guī)劃方法也有一定的限制，如狀態(tài)變量必須滿足無后效性， 不考慮路況，天氣等不確定因素對行程的影響，并且只適用一些維數(shù)相對較低的 問題等。但是可以看到，動態(tài)規(guī)劃的應(yīng)用是很廣的，已成功解決了許多實際問題， 具有一定的實用性。本文將動態(tài)規(guī)劃思想運用到求解物流配送中的最短路徑問題 中，其優(yōu)點在于思路清晰，方法簡便，理論可靠，在實際運用中取得了良好的效果。但是本文只考慮了一個

14、起點的應(yīng)用實例，在實際中有可能存在多個起點的情況，因此我們可以考慮將其進(jìn)行改進(jìn)，使之更好的運用在實際中，為企業(yè)的發(fā)展提供更 多的幫助。Using the dynamic programming model isused to solve the shortest path problemlogistics distributionWangjiajunAbstract: with the rapid development of modern society, the logistics distribution became connected each production base hub

15、, transportation cost problem has become the key to the development of the enterprise.Freight volume, and not only from about transportation and walking routes related. Traditional transport problems did not consider the traffic network, under the condition of the known freight rate only find out op

16、timal scheduling solutions, not asked the optimal walk path.This paper put forward "Internet logistics distribution problem", volume in unknown rate, the case, will determine the transportation process is divided into several stages, in each phase of the selection of the optimum strategy, finally found the whole process of the overall optimum target, save enterprise spending.Keywords: dynamic planning, mathematical model, the logistics distribution, optimal path 參考文獻(xiàn)1 蔣琦瑋， 陳治亞 物流配送