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

運(yùn)用動態(tài)規(guī)劃模型解決物流配送中的最短路徑問題王嘉?。}城師范學(xué)院數(shù)學(xué)科學(xué)學(xué)院09（1）班）摘要：隨著現(xiàn)代社會的高速發(fā)展，物流配送成為了連接各個生產(chǎn)基地的樞紐，運(yùn)輸?shù)某杀締栴}也成為了企業(yè)發(fā)展的關(guān)鍵。運(yùn)費(fèi)不但與運(yùn)量有關(guān)，而且與運(yùn)輸行走的線路相關(guān)。傳統(tǒng)的運(yùn)輸問題沒有考慮交通網(wǎng)絡(luò)，在已知運(yùn)價的條件下僅求出最優(yōu)調(diào)運(yùn)方案，沒有求出最優(yōu)行走路徑。文中提出“網(wǎng)絡(luò)上的物流配送問題“在未知運(yùn)價，運(yùn)量確定的情況下，將運(yùn)輸過程在每階段中選取最優(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é)。它是指按用戶的訂貨要求，在配送中心進(jìn)行分貨、配貨，并將配好的貨物及時送交收貨人的活動。在物流配送業(yè)務(wù)中，合理選擇配送徑路，對加快配送速度、提高服務(wù)質(zhì)量、降低配送成本及增加經(jīng)濟(jì)效益都有較大影響。物流配送最短徑路是指物品由供給地向需求地的移動過程中，所經(jīng)過的距離最短（或運(yùn)輸?shù)臅r間最少，或運(yùn)輸費(fèi)用最低），因此，選定最短徑路是提高物品時空價值的重要環(huán)節(jié)。［1］經(jīng)典的Dijkstra算法和Floyd算法思路清楚，方法簡便，但隨著配送點(diǎn)數(shù)的增加，計(jì)算的復(fù)雜性以配送點(diǎn)數(shù)的平方增加，并具有一定的主觀性。我國學(xué)者用模糊偏好解試圖改善經(jīng)典方法［5，取得了較好的效果。遺憾的是，模糊偏好解本身就不完全是客觀的。文獻(xiàn)［6詳細(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)性原理”，并研究了許多實(shí)際問題，從而創(chuàng)建了最優(yōu)化問題的一種新方法——動態(tài)規(guī)劃。動態(tài)規(guī)劃在工程技術(shù)、管理、經(jīng)濟(jì)、工業(yè)生產(chǎn)、軍事及現(xiàn)代控制工程等方面都有廣泛的應(yīng)用，而且由于動態(tài)規(guī)劃方法有其獨(dú)特之處，在解決某些實(shí)際問題時，顯得更加方便有效。由于決策過程的時間參數(shù)有離散的和連續(xù)的情況，故決策過程分為離散決策過程和連續(xù)決策過程。⑵這種技術(shù)采用自底向上的方式遞推求值，將待求解的問題分解成若干個子問題，先求解子問題，并把子問題的解存儲起來以便以后用來計(jì)算所需要求的解。簡言之，動態(tài)規(guī)劃的基本思想就是把全局的問題化為局部的問題，為了全局最優(yōu)必須局部最優(yōu)。多階段決策問題是根據(jù)問題本身的特點(diǎn)，將其求解的過程劃分為若干個相互獨(dú)立又相互聯(lián)系的階段，在每個階段都需要做出決策，并且在每個階段的確定后再轉(zhuǎn)移到下一個階段，在每一個階段選取其最有決策，從而實(shí)現(xiàn)整個過程總體決策最優(yōu)的目的。國］適合用動態(tài)規(guī)劃方法求解的問題是一類特殊的多階段決策問題，具有“無后效性”的多階段決策問題，一般具有以下特點(diǎn)：可以劃分為若十個階段，問題的求解過程就是對若十個階段的一系列決策過程。每個階段有若十個可能狀態(tài)。一個決策將你從一個階段的一種狀態(tài)帶到下一個階段的某種狀態(tài)。在任一個階段，最佳的決策序列和該階段以前的決策無關(guān)。各階段狀態(tài)之間的轉(zhuǎn)換有明確定義的費(fèi)用，而且在選擇最佳決策時有遞推關(guān)系(即動態(tài)轉(zhuǎn)移方程)。［3］2動態(tài)規(guī)劃模型在現(xiàn)實(shí)生活的生產(chǎn)運(yùn)輸中，往往出發(fā)地與目的地之間有多種路線可供選擇，不同的路線所花費(fèi)的時間與費(fèi)用也不同，時間與費(fèi)用決定著企業(yè)的發(fā)展，這就需要選擇最短的路徑來提高效率。為了解決這個問題，將動態(tài)規(guī)劃的理論與方法運(yùn)用于生產(chǎn)運(yùn)輸中，節(jié)約了時間，為：企業(yè)的發(fā)展提供了契機(jī)。建立這個規(guī)劃模型的具體步驟如下：①劃分階段:把所給問題的過程，恰當(dāng)?shù)膭澐譃槿羰畟€相互聯(lián)系的部分，以便于求解，其中每個部分叫階段。通常用k表示階段變量⑵確定狀態(tài)變量及其取值范圍：狀態(tài)表示在任一階段所處的，它既是該階段的起點(diǎn)，又是前一階段的終點(diǎn)。通常一個階段有若十個階段。描述狀態(tài)的變量稱為狀態(tài)變量。參數(shù)*表示第k階段的狀態(tài)變量。該階段所有可能狀態(tài)的全體稱為狀態(tài)集合，記為飛。狀態(tài)變量要能描述決策過程演變的狀態(tài)，又要滿足無后效性的要求，而且維數(shù)要盡可能地少。確定決策變量及其取值范圍：在某一階段，當(dāng)狀態(tài)給定后，往往可以作出不同的決定，從而確定下一階段的狀態(tài)，這種決定稱為決策。描述決策的變量稱為決策變量，用u(s)表示第k階段當(dāng)狀態(tài)為s時的決策變量，它是狀態(tài)變量s的函數(shù)。決策變量的取值范圍稱為決策集合，通常用氣(s「表示第k階段狀態(tài)為、時的允許決策集合。顯然有七(s「gD(七)。建立狀態(tài)轉(zhuǎn)移方程：狀態(tài)轉(zhuǎn)移方程描述由一個狀態(tài)到另一個狀態(tài)的演變過程。因?yàn)槟骋浑A段的狀態(tài)變量及決策變量取定后，下一階段的狀態(tài)就隨之而定。用S=t(s,u)表示k階段與k+1階段狀態(tài)的變換規(guī)律?指標(biāo)函數(shù)和最優(yōu)指標(biāo)函數(shù)值：階段指標(biāo)(又稱階段效益)是衡量該階段決策效果的數(shù)量指標(biāo)，它是整個系統(tǒng)效益的一部分，是階段狀態(tài)和階段決策的函數(shù)。用d(s,u)表示在第k階段由狀態(tài)s和執(zhí)行決策u(s)所得的效益。kkkkkk指標(biāo)函數(shù)(又稱目標(biāo)函數(shù))是衡量所實(shí)現(xiàn)過程優(yōu)劣的一種數(shù)量指標(biāo)，它表示系統(tǒng)執(zhí)行某一策略所產(chǎn)生的效益，它是定義在過程(可以是全過程，也可以是后部子過程)上的數(shù)量函數(shù)，用f表示：f=f(s,u,s,u,??.,s),k=1,2,nk,nk,nkkk+1k+1n+1當(dāng)初始狀態(tài)給定時，過程的策略就確定了，因而指標(biāo)函數(shù)也就確定，故指標(biāo)函數(shù)是初始狀態(tài)和策略的函數(shù)，即：f,n=f,n[\，P(\)]，指標(biāo)函數(shù)f的最優(yōu)值，稱為最優(yōu)指標(biāo)函數(shù)值，記為f(s)，它表示從第k階k,nkk段由狀態(tài)s出發(fā)到過程結(jié)束時所獲得的最優(yōu)指標(biāo)函數(shù)值。在最短路線問題中，f表示從第k階段的點(diǎn)s至終點(diǎn)G的距離，f(s)表示由點(diǎn)s到G的最短距離，用kkkkd(s,u)表示在第k階段由點(diǎn)s到點(diǎn)s=u(s)的距離。kkkkk+1kk最后得到動態(tài)規(guī)劃的一般模型為:f(s)=optb(s,u)+f("(s))},

kkkkkk+1kk4I”eD^(：「[f<s)=0,k-n,n-1,1,f(s)為從狀態(tài)s出發(fā)到終點(diǎn)的最優(yōu)效益，“opt”是optimization(最優(yōu)化)的縮寫kkk[23實(shí)例分析為進(jìn)一步說明該方法的有效性和實(shí)用性，先將該方法運(yùn)用于某物流配送網(wǎng)絡(luò)中：設(shè)某物流配送網(wǎng)絡(luò)圖由9個配送點(diǎn)組成，點(diǎn)人為配送中心，A為終點(diǎn)，試求自人到圖中任何配送點(diǎn)的最短距離。圖中相鄰兩點(diǎn)的連線上標(biāo)有兩點(diǎn)間的距離由首先根據(jù)網(wǎng)絡(luò)圖以及上面的建模方法我們可以將運(yùn)輸過程劃分成三個階段，分別為：第一階段人，第二階段人,人，人，人，第三階段人，人，A,A，顯然兩點(diǎn)之間直線013572468路徑小于折線路徑階段變量用k表示；狀態(tài)變量人表示k階段初可能的位置；決策f^(氣)表示k階段初可能選擇的路線；由后向前逐步推移計(jì)算最優(yōu)路徑：當(dāng)k=3時，由人，人，人，人到人只有一條路線，故f(a)=16,f(A)=8,f(A)=4,f(a)=142468932343836當(dāng)k=2時，出發(fā)點(diǎn)有A,A,A,A三個，若從A出發(fā)，只有一個選擇，至A，所以f(A)=2713571221有兩個選擇，所以f(A)=min<d有兩個選擇，所以f(A)=min<d(A,A)+f(A)]23232I_命八d(A,A)+f(A)[-min23434J5+16]=1810+8從A出發(fā)，有兩個選擇，至％A6，所以f(A)=min<d2(A5,A4)+f3(A』.J16+8d(A,A)+f(A)|mm[任+425636J=19從a出發(fā)，有兩個選擇，所以f(A)=min'd(A,A)+f(A)]f11+4]J2/7636|=minJ|=15Id(A,A)+f(A)|112+14TOC\o"1-5"\h\zI27838^最短路線是A7tA6tA9當(dāng)k=1時，出發(fā)點(diǎn)有A一個，若從A出發(fā)，至A，所以f(A)=3100110若從a出發(fā)，至A，所以f(A)=250310若從a出發(fā)，至A，所以f(A)=270510若從a出發(fā)，至A，所以f(A)=240710由上面計(jì)算得到最優(yōu)路徑f(A)=24,最優(yōu)路徑為A-A-A-A從a出發(fā)，有兩個選擇，所以f(A)=min由本實(shí)例我們可以總結(jié)出動態(tài)規(guī)劃的優(yōu)越性所在：求解過程，結(jié)果清晰明了；能得到一組解，有利于分析結(jié)果；易于確定全局最優(yōu)解；4結(jié)論用動態(tài)規(guī)劃解決多階段決策問題可以提高效率，而且思路清晰簡便，同時易于實(shí)現(xiàn)，雖然使用動態(tài)規(guī)劃方法也有一定的限制，如狀態(tài)變量必須滿足無后效性，不考慮路況，天氣等不確定因素對行程的影響，并且只適用一些維數(shù)相對較低的問題等。但是可以看到，動態(tài)規(guī)劃的應(yīng)用是很廣的，已成功解決了許多實(shí)際問題，具有一定的實(shí)用性。本文將動態(tài)規(guī)劃思想運(yùn)用到求解物流配送中的最短路徑問題中，其優(yōu)點(diǎn)在于思路清晰，方法簡便，理論可靠，在實(shí)際運(yùn)用中取得了良好的效果。但是本文只考慮了一個起點(diǎn)的應(yīng)用實(shí)例，在實(shí)際中有可能存在多個起點(diǎn)的情況，因此我們可以考慮將其進(jìn)行改進(jìn)，使之更好的運(yùn)用在實(shí)際中，為企業(yè)的發(fā)展提供更多的幫助。Usingthedynamicprogrammingmodelis

usedtosolvetheshortestpathproblem

logisticsdistributionWangjiajunAbstract:withtherapiddevelopmentofmodernsociety,thelogisticsdistributionbecameconnectedeachproductionbasehub,transportationcostproblemhasbecomethekeytothedevelopmentoftheenterprise.Freightvolume,andnotonlyfromabouttransportationandwalkingroutesrelated.Traditionaltransportproblemsdidnotconsiderthetrafficnetwork,undertheconditionoftheknownfreightrateonlyfindoutoptimalschedulingsolutions,notaskedtheoptimalwalkpath.Thispaperputforward"Internetlogisticsdistributionproblem",volumeinunknownrate,thecase,willdeterminethetransportationprocessisdividedintoseveralstages,ineachphaseoftheselectionoftheoptimumstrategy,finallyfoundthewholeprocessoftheoveralloptimumtarget,saveenterprisespending.Keywords:dynamicplanning,mathematicalmodel,thelogisticsdistribution,optimalpath［參考文獻(xiàn)］［1］蔣琦瑋，陳治亞物流配送最短徑路的動態(tài)規(guī)劃方法