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

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

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

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

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

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

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

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

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

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

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

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

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

14、起點的應用實例，在實際中有可能存在多個起點的情況，因此我們可以考慮將其進行改進，使之更好的運用在實際中，為企業的發展提供更 多的幫助。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 參考文獻1 蔣琦瑋， 陳治亞 物流配送