• 
    

    
    

      99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看 ?

      物流配送問題中貪心算法與動態(tài)規(guī)劃法的分析與應(yīng)用

      2017-10-12 03:17:53徐西嘯
      科學(xué)家 2016年18期
      關(guān)鍵詞:最短路徑動態(tài)規(guī)劃

      徐西嘯

      摘要計算機的應(yīng)用觸及到了生活的各個方面,它的優(yōu)點之一就在于強大的計算處理能力上,這也正是物流領(lǐng)域配送路線的問題所需要的。如何選擇最佳路線,如何節(jié)約物流運輸成本,即選擇配送的最短路線,我們可以通過貪心算法和動態(tài)規(guī)劃算法來做決定。本文對于中國現(xiàn)今發(fā)展蓬勃的電子商務(wù)的線下運輸問題提出了見解,以一個簡化的模型介紹了貪心算法以及動態(tài)規(guī)劃法的應(yīng)用,為線下運輸問題提出了解決方案,有著十分重要的現(xiàn)實意義。

      關(guān)鍵詞物流問題;最短路徑;最小時間;貪心算法;動態(tài)規(guī)劃

      計算機自誕生以來,發(fā)展迅速,在社會中的各個領(lǐng)域都得到了廣泛的應(yīng)用。使用計算機快速處理問題成為當今社會發(fā)展的需要。筆者運用計算機知識為現(xiàn)實問題提供一些意見和建議。筆者在今年“雙十一”期間親身經(jīng)歷了爆倉問題,發(fā)現(xiàn)物體配送效率低下,“雙十一”期間物流速度極慢,形式十分嚴峻。據(jù)官方所提供的數(shù)據(jù),買家每秒創(chuàng)建訂單數(shù)額達到17.5萬筆,有些貨物甚至預(yù)計需要1個月左右的時間才能配送完畢。

      對于現(xiàn)今的物流配送,人們大多選擇第三方物流。當貨物運送到某地區(qū)時,物流公司的將貨物囤積在一處,再通過快遞員將快遞送往千家萬戶。筆者在此希望對快遞員的派送路線進行合理化選擇,以最短路程,最小時間完成貨物的配送。

      以城市中的快遞配送為例,現(xiàn)簡化模型如下:快遞員在某地區(qū)配送快遞,快遞公司(貨物囤積地)位于0點,快遞員需要派送6份快遞,分別送往A,B,C,D,E,F(xiàn)六個地點,每兩個地點之間的距離已標出,快遞員如何快速規(guī)劃路線,以最短路徑、最小時間完成快遞的配送,這不僅可以節(jié)約勞動力提高工作效率,也會使網(wǎng)購用戶收貨速度更快。

      在具體代碼實現(xiàn)中配送需求地映射為編號:0-0,A-1,B-2,C-3,D-4,E-5,F(xiàn)-6:

      城市之間的距離用二維數(shù)組來表示,記為D[i][j],如:D[0][1]表示0與A之間的距離,于是D[0][1]=6;設(shè)置flag[][],初始為0,表示此變量未被訪問(配送需求地未到達過),若被訪問(已到達過配送完畢)則修改為1。

      本文中筆者選擇貪心算法、動態(tài)規(guī)劃法來解決這一實際問題。

      1貪心算法

      貪心算法(Greedy algorithm)是一種對某些動態(tài)規(guī)劃中求優(yōu)秀解的簡單、迅速的算法,以當前情況為基礎(chǔ)根據(jù)某個標準作最優(yōu)選擇,而不考慮整體情況,省去大量時間。

      貪心算法在解決問題的策略上缺點是目光短淺,只根據(jù)當前已有的信息就做出選擇,而且一旦做出了選擇,不管將來有什么結(jié)果,這個選擇都不會改變。換言之,貪心算法并不是從整體最優(yōu)考慮,它所做出的選擇只是在某種意義上的局部最優(yōu)。這種局部最優(yōu)選擇并不總能獲得整體最優(yōu)解,但通常能獲得近似最優(yōu)解。但由于其處理問題簡單高效、節(jié)省空間,非常適合實際問題的解決。

      現(xiàn)在我們通過來解決這一問題,采用最近鄰點策略:從某地點(初始為快遞公司,即0點)出發(fā),每次在沒有到過的中選擇距離當前所在地中最近的一個,直到經(jīng)過了所有的配送需求地,完成了所有配送任務(wù),最后回到快遞公司,即0點。

      貪心算法具體求解流程如下:1)了解要求送達地點的的數(shù)量與各地點之間的距離。2)重復(fù)以下兩步直至已全部送達:(1)循環(huán)遍歷找到與當前出發(fā)地點最近的未到達過的配送需求地;(2)以當前找到的(最近一次找到的)送達地點為出發(fā)地點,重復(fù)步驟(1)。3)回到出發(fā)地點。

      在本題中貪心算法選擇路線經(jīng)過如下:快遞員從0點選擇較近的A點作為目的地。到達后選擇距離當前出發(fā)點A較近的點,0點當前已訪問,選擇B點。而后依次按照此規(guī)則選擇配送需求點,當所有快遞配送完畢返回0點,即快遞公司所在地。路線為0->AV>B->C->D>E->F->0。路程為44。

      從本例中也可以看出,貪心算法簡單便捷,對于問題的解決有很大的幫助。同時我們清楚地看出,使用貪心算法只能考慮當前的選擇,當面對復(fù)雜的整體問題時,貪心算法未必能給出最優(yōu)解只求出了近似最優(yōu)解。

      2動態(tài)規(guī)劃算法

      動態(tài)規(guī)劃算法通常用于求解具有某種最優(yōu)性質(zhì)的問題。在這類問題中,可能會有許多可行解。每一個解都對應(yīng)于一個值,我們希望找到具有最優(yōu)值的解。如本問題的簡化模型有許多可以把貨物送達的可行解,但我們希望找到能實現(xiàn)最短路程最小時間的最優(yōu)解。

      動態(tài)規(guī)劃算法與分治法類似,其基本思想也是將待求解問題分解成若干個子問題,先求解子問題,然后從這些子問題的解得到原問題的解。與分治法不同的是,適合于用動態(tài)規(guī)劃求解的問題,經(jīng)分解得到子問題往往不是互相獨立的。若用分治法來解這類問題,則分解得到的子問題數(shù)目太多,有些子問題被重復(fù)計算了很多次。

      如果我們能夠保存已解決的子問題的答案,而在需要時再找出已求得的答案,這樣就可以避免大量的重復(fù)計算,節(jié)省時間。我們可以用一個表來記錄所有已解的子問題的答案。不管該子問題以后是否被用到,只要它被計算過,就將其結(jié)果填入表中。

      在利用動態(tài)規(guī)劃求解的過程中值得注意的就是是否包含最優(yōu)子結(jié)構(gòu),簡單來講就是一個問題的最優(yōu)解是不是包含著子問題的最優(yōu)解。利用求解子問題的最優(yōu)解最后得到整個問題的最優(yōu)解,這是利用動態(tài)規(guī)劃求解問題的基本前提。

      動態(tài)規(guī)劃的求解過程主要分為如下的四步:1)描述最優(yōu)解的結(jié)構(gòu);2)遞歸定義最優(yōu)解的值;3)按白底向上的方式計算最優(yōu)解的值;4)由計算出的結(jié)果構(gòu)造一個最優(yōu)解。

      在本快遞配送問題的簡單模型中求解過程具體如下:假設(shè)從頂點0出發(fā),令stM表示從頂點0出發(fā)經(jīng)過圖中各個頂點,即配送需求地一次且僅一次最后回到出發(fā)點的最短路徑長度。

      2.1描述最優(yōu)解的結(jié)構(gòu)

      要使得從0(以0表示出發(fā)處0節(jié)點)點出發(fā)配送完畢回到0(以7表示返回處0節(jié)點,D[7][k]=D[0][k])點的路程最短,令f(i)為到第i個節(jié)點的最短距離,則f(7)=min{D[7][1],D17][5],D[7][6]),用同樣的方法可以求得f(1),f(5),f(6)等。

      2.2遞歸定義最優(yōu)解的值

      f(i)=min(f(j)+D[i][j]),其中j表示與i邊有連接的節(jié)點。

      2.3按自底向上的方式計算每個節(jié)點的最優(yōu)值

      此時我們就得利用遞歸公式分別求解f(0),f(1),f(2)…f(7),這樣最終便能得到最終的解。

      2.4由計算出的結(jié)果構(gòu)造一個最優(yōu)解

      本模型最終解為路線為0-(0)>A(1)->B(2)->c(3)->D(4)->E(5)->F(6)->0(7)。路程為44。

      動態(tài)規(guī)劃算法關(guān)鍵在于解決了重復(fù)計算的問題,大大提高了代碼運行效率??傮w來說,動態(tài)規(guī)劃算法就是一系列以空間換取時間的算法。

      3結(jié)論

      中國電商業(yè)發(fā)展十分迅速,但長期以來,線下運輸物流配送速度為人所詬病,筆者認為應(yīng)該有著更高效的配送方式。本文主要利用貪心算法和動態(tài)規(guī)劃算法來進行求解,快速而準確地得出流配送的近似最佳或最佳路線選擇,節(jié)約物流運輸成本,提高消費者滿意度,對快遞公司派發(fā)快遞的路線考慮有很強的現(xiàn)實參考意義。endprint

      猜你喜歡
      最短路徑動態(tài)規(guī)劃
      Dijkstra算法設(shè)計與實現(xiàn)
      基于Dijkstra算法的優(yōu)化研究
      圖論最短路徑算法的圖形化演示及系統(tǒng)設(shè)計
      ACM—ICPC競賽趣味學(xué)習(xí)系統(tǒng)設(shè)計
      大學(xué)生經(jīng)濟旅游優(yōu)化設(shè)計模型研究
      中國市場(2016年33期)2016-10-18 14:23:52
      動態(tài)規(guī)劃最優(yōu)控制在非線性系統(tǒng)中的應(yīng)用
      不確定條件下物流車最優(yōu)路徑選擇研究
      中國市場(2016年10期)2016-03-24 10:17:44
      動態(tài)規(guī)劃案例教學(xué)設(shè)計
      基于NFC的博物館智能導(dǎo)航系統(tǒng)設(shè)計
      產(chǎn)品最優(yōu)求解問題中運籌學(xué)方法的應(yīng)用
      阿合奇县| 榆中县| 宿迁市| 黔江区| 女性| 上栗县| 武义县| 东宁县| 通辽市| 泰来县| 辽阳县| 图们市| 临朐县| 蒙自县| 武功县| 龙口市| 会宁县| 定州市| 南溪县| 黄骅市| 鹤岗市| 忻城县| 青铜峡市| 永丰县| 长岛县| 电白县| 勃利县| 固原市| 通山县| 临泽县| 云霄县| 新巴尔虎右旗| 晋城| 藁城市| 武功县| 新丰县| 连南| 仁怀市| 仪征市| 蓝山县| 崇礼县|