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

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

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

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

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

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

6、最短的路徑來提高效率。為了解決這個問題，將動態(tài)規(guī)劃的理論與方法運 用于生產(chǎn)運輸中，節(jié)約了時間，為：企業(yè)的發(fā)展提供了契機。建立這個規(guī)劃模型 的具體步驟如下：3劃分階段：把所給問題的過程，恰當?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、策變量及其取值范圍：在某一階段，當狀態(tài)給定后，往往可以作出不同的決定，從而確定下一階段的狀態(tài)，這種決定稱為決策。描述決策的變量稱 為決策變量，用Uk(Sk水示第k階段當狀態(tài)為Sk時的決策變量，它是狀態(tài)變量Sk的 函數(shù)。決策變量的取值范圍稱為決策集合，通常用Dk(Sk )表示第k階段狀態(tài)為Sk時的允許決策集合。顯然有Uk (Sk產(chǎn)Dk (Sk )。 建立狀態(tài)轉移方程：狀態(tài)轉移方程描述由一個狀態(tài)到另一個狀態(tài)的演變過 程。因為某一階段的狀態(tài)變量及決策變量取定后，下一階段的狀態(tài)就隨之而定。 用&中=丁國山)表示k階段與k+1階段狀態(tài)的變換規(guī)律 指標函數(shù)和最優(yōu)指標函數(shù)值：階段指標(乂稱階段效益)

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

9、 L指標函數(shù)fk,n的最優(yōu)值，稱為最優(yōu)指標函數(shù)值，記為 fk (Sk )，它表小從第k階 段由狀態(tài)Sk出發(fā)到過程結束時所獲得的最優(yōu)指標函數(shù)值。 在最短路線問題中，fk,n 表示從第k階段的點Sk至終點G的距離，fk(Sk )表示由點Sk到G的最短距離，用 dk(Sk,Uk成示在第k階段由點Sk到點Sk+=Uk(Sk )的距離。最后得到動態(tài)規(guī)劃的一般模型為：fkSk= optdksk,ukfk1ukSj,a SkJfk1 Sk 1 = 0, = n, n -1-1,fk (Sk)為從狀態(tài)Sk出發(fā)到終點的最優(yōu)效益，“opt”是optimization (最優(yōu)化)的縮寫213實例分析為進一步說明該方

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

11、，故 f3(A2 )=16, f3(A4 ) = 8, fa ( Ag )=4 , f 3 ( A& )=14當k=2時，出發(fā)點有A1,A3,A5,A7三個，若從打出發(fā)，只有一個選擇，至A2，所以f2fAi=27從A3出發(fā)，有兩個選擇，至從A5出發(fā)，有兩個選擇，至A2, A4 ,所以 f2（ A3 ）=minA4, A6 ,所以 f2（A5）=mindd2A3, A2- f3 A2-minA3, A4- f3 A4 "j J5 - 16=1810 - 8dd2A5，A4f3 A4 加j A5 , A6. ： f 3 j A6 - |J16 - 8=1915 4d,A7, A-

12、 f3Ar'.IM14從罵出發(fā)，有兩個選擇，至Ar, A8 ,所以f2”7 =minI ）'） = min=15d2A7,A8 f3A8：I12 - 14最短路線是 A7 r A6 r A9當k=1時，出發(fā)點有A0一個，若從A0出發(fā)，至A1 ,所以f1(A° )=31若從A0出發(fā)，至A3，所以f1 (A° )=25若從A°出發(fā)，至A5 ,所以七(A。)=27若從A。出發(fā)，至A,所以f1 (A° )=24由上面計算得到最優(yōu)路徑 f(A°尸24，最優(yōu)路徑為A°t a7t a6t a9由本實例我們可以總結出動態(tài)規(guī)劃的優(yōu)越性所

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

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

15、 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 optimal scheduling

16、 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參考文獻1