柏鄉(xiāng)超市配送路徑優(yōu)化問(wèn)題研究

《運(yùn)輸與配送》結(jié)課論文題目柏鄉(xiāng)超市配送路徑優(yōu)化問(wèn)題研究柏鄉(xiāng)超市配送路徑優(yōu)化問(wèn)題研究摘要：隨著我國(guó)物流快速迅速，一些物流企業(yè)之間競(jìng)爭(zhēng)日益激烈，合理的控制物流配送成本已經(jīng)成為物流企業(yè)生存的根本。其中的最短路問(wèn)題是圖論問(wèn)題的一個(gè)經(jīng)典問(wèn)題，尋找最短路就是在指定網(wǎng)絡(luò)兩點(diǎn)間尋找一條距離最短的路，最短路徑算法的選擇與實(shí)現(xiàn)是通道路線設(shè)計(jì)的基礎(chǔ)，最短路徑算法是計(jì)算機(jī)科學(xué)與地理信息科學(xué)等領(lǐng)域的研究熱點(diǎn)，許多網(wǎng)絡(luò)相關(guān)問(wèn)題均可納入最短路徑問(wèn)題的傳承中，經(jīng)典的圖論與不斷發(fā)展完善的計(jì)算機(jī)數(shù)據(jù)結(jié)構(gòu)及算法的有效結(jié)合，使得新的最短路徑算法不斷涌現(xiàn)。通過(guò)對(duì)柏鄉(xiāng)鎮(zhèn)方魯村的小配送站與8個(gè)小超市之間的運(yùn)輸距離的收集整理，使用管理運(yùn)籌學(xué)軟件分析處理，得出從小配送站到各超市配送的最優(yōu)路徑，從而提高配送站物流配送效率，降低物流配送成本，提高市場(chǎng)競(jìng)爭(zhēng)力，實(shí)現(xiàn)精細(xì)化管理，使配送更合理、更高效。 關(guān)鍵詞：柏鄉(xiāng)配送站；超市；路徑優(yōu)化；管理運(yùn)籌學(xué)軟件；數(shù)據(jù)分析緒論1.1研究背景隨著物流產(chǎn)業(yè)不斷發(fā)展、規(guī)模的不斷擴(kuò)大，物流配送的作用日益顯著，配速是是一種綜合特殊的物流形式，它實(shí)際上包含了全部的物流功能要素，是一種小規(guī)模的物流活動(dòng)的表達(dá)，也可以說(shuō)是一種小的物流系統(tǒng)。配送系統(tǒng)在物流產(chǎn)業(yè)發(fā)展中發(fā)揮著重要的作用，樹立正確的物流配送意識(shí)，合理正確了解配送系統(tǒng)的結(jié)構(gòu)和運(yùn)行方式是配送站取得成功的保障，高效的配送效率和經(jīng)濟(jì)合理的物流配送成本是配送站提升市場(chǎng)競(jìng)爭(zhēng)力的必然要求，對(duì)于小配送站而言，優(yōu)化配送路徑可以提高物流配送效率，降低物流配送成本，從而完善配備服務(wù)，提高市場(chǎng)競(jìng)爭(zhēng)力[1]。在柏鄉(xiāng)鎮(zhèn)方魯村有一個(gè)小配送站，配送站向柏鄉(xiāng)鎮(zhèn)多個(gè)小超市配送物資，因?yàn)樾〕幸话銉H有周邊人去購(gòu)物，所以它的總需求量不大，故小配送站以每月兩次的頻率，用一輛大送貨車完成周邊9個(gè)超市物資的配送?，F(xiàn)小配送站實(shí)行精細(xì)化管理，規(guī)劃其最佳運(yùn)輸路線，節(jié)約成本，提高效益。1.2研究的目的和意義在整個(gè)物流系統(tǒng)中，配送是與消費(fèi)者有關(guān)，有著密切關(guān)聯(lián)的一個(gè)環(huán)節(jié)，而物流配送中的路徑優(yōu)化則在物流系統(tǒng)優(yōu)化環(huán)節(jié)中起關(guān)鍵作用，好的配送方案不僅能節(jié)約物流成本，提高商品流動(dòng)的速度，而且還由于它能有效連接生產(chǎn)與消費(fèi)，從而既有利于物流服務(wù)與商品附加價(jià)值的實(shí)現(xiàn)，又能有效促進(jìn)生產(chǎn)商品按需生產(chǎn)，真正使物流管理建立在持續(xù)經(jīng)營(yíng)的基礎(chǔ)上。隨著方魯村的小配送站的不斷發(fā)展，如何實(shí)現(xiàn)精細(xì)化管理，制定一個(gè)好的配送方案已經(jīng)是配送站目前必須需要關(guān)注的事情。小配送站需要實(shí)現(xiàn)物流配送中的路徑優(yōu)化，提高物流配送效率，降低物流配送成本，完善配備服務(wù)，提高市場(chǎng)競(jìng)爭(zhēng)力。2國(guó)內(nèi)外路徑優(yōu)化研究現(xiàn)狀2.1國(guó)內(nèi)路徑優(yōu)化研究現(xiàn)狀隨著物流行業(yè)的蓬勃發(fā)展，物流企業(yè)正在逐漸走入高質(zhì)量發(fā)展中，但我國(guó)物流行業(yè)和外國(guó)物流行業(yè)對(duì)比起步較晚，現(xiàn)在程度較低，20世紀(jì)70年代之前，我國(guó)各項(xiàng)經(jīng)濟(jì)研究中從未出現(xiàn)過(guò)物流一詞，然而物流的各個(gè)環(huán)節(jié)早就運(yùn)用在了國(guó)民經(jīng)濟(jì)的各個(gè)領(lǐng)域中，自20世紀(jì)80年代，物流出現(xiàn)在大眾視野，并逐漸得到了專家學(xué)者們的關(guān)注，20世紀(jì)90年代的流通，從實(shí)際意義上證實(shí)了配送是一種十分重要的物流方式，我國(guó)許多城市建立了物流配送中心，從而給物流配送提供了很廣闊的發(fā)展空間，越來(lái)越多的學(xué)者提出物流配送體系的構(gòu)建模型及具體構(gòu)建方法，從而使物流配送路徑最優(yōu)化。近年近年來(lái)我國(guó)物流配送發(fā)展迅速，但永遠(yuǎn)達(dá)不到現(xiàn)代物流發(fā)展的要求，我國(guó)各大小配送站的物流配送還存在諸多問(wèn)題，許多地方都有自己的小型配送中心，然而這些配送中心大多效率不高。導(dǎo)致配送不高的原因，一般是資金和技術(shù)缺乏和落后，配送功能不齊全，技術(shù)不先進(jìn)，導(dǎo)致配送中心配送直接脫節(jié)，另一方面，大多數(shù)配送中心只專注于“送”而忽略了“配”[2]。2.2國(guó)外路徑優(yōu)化研究現(xiàn)狀路徑優(yōu)化問(wèn)題屬于車輛路線問(wèn)題（VRP）類別，是Dantzig和Ranser在1999年第一次對(duì)VRP進(jìn)行研究，提出了加油站路線優(yōu)化的數(shù)學(xué)模型和算法，1964年Clarke和Wright提出了一種包含Ramser方式在內(nèi)的Dancer，更有效的提高了啟發(fā)式算法的保存算法，經(jīng)過(guò)兩篇開創(chuàng)性論文，VRP很快引起了應(yīng)用數(shù)學(xué)、運(yùn)籌學(xué)、圖論、組合數(shù)學(xué)、計(jì)算機(jī)的應(yīng)用及物流學(xué)派學(xué)科專家的重視。目前用來(lái)解決國(guó)外問(wèn)題的方式主要分可分為優(yōu)化算法和啟發(fā)式算法，因?yàn)閮?yōu)化算法的應(yīng)用領(lǐng)域有限，所以專家致力于構(gòu)建高品質(zhì)的啟發(fā)式算法。3最短路算法定量算法分析3.1Floyd算法Floyd算法只有五行代碼，代碼簡(jiǎn)單，三個(gè)for循環(huán)就可以解決問(wèn)題，所以它的時(shí)間復(fù)雜度為O(n*n*n)，可以求多源最短路問(wèn)題。Floyd算法可以處理帶有負(fù)權(quán)邊，但不能處理帶有“負(fù)權(quán)回路”的圖。3.2Dijkstra算法（單源最短路）Dijkstra算法是單源最短路，以一個(gè)頂點(diǎn)出發(fā)到所有點(diǎn)的最短路。每次找到離源點(diǎn)最近的頂點(diǎn)，然后以該頂點(diǎn)為中心進(jìn)行擴(kuò)展，最終得到源點(diǎn)到其余所有點(diǎn)的最短路徑。即為依次找到離源點(diǎn)最近的頂點(diǎn)跟每個(gè)點(diǎn)到源點(diǎn)的距離，然后每個(gè)點(diǎn)到源點(diǎn)的距離與離源點(diǎn)最近的頂點(diǎn)加上兩頂點(diǎn)的距離分別比較。就是dis[v]=dis[u]+e[u][v]。3.3Bellman-Ford（解決負(fù)權(quán)邊）Bellman-Ford算法最多有n-1個(gè)階段。在每一個(gè)階段，我們對(duì)每一條邊都要執(zhí)行松弛操作。其實(shí)每實(shí)施一次松弛操作，就會(huì)有一些頂點(diǎn)已經(jīng)求得其最短路，即這些頂點(diǎn)的最短路的“估計(jì)值”變?yōu)椤按_定值”。此后這些頂點(diǎn)的最短路的值就會(huì)一直保持不變，不再受松弛操作的影響[3]。3.4SPFA算法SPFA其實(shí)就是使用隊(duì)列優(yōu)化的Bellman-Ford算法。SPFA算法在形式上和廣度優(yōu)先搜索非常類似，不同的是在廣度優(yōu)先搜索的時(shí)候一個(gè)頂點(diǎn)出隊(duì)后通常就不會(huì)再重新進(jìn)入隊(duì)列。而這里一個(gè)頂點(diǎn)很可能再出隊(duì)列之后再次被放入隊(duì)列，也就是當(dāng)一個(gè)頂點(diǎn)的最短路程估計(jì)值變小之后，需要對(duì)其所有邊進(jìn)行松弛，但是如果這個(gè)頂點(diǎn)的最短路程估計(jì)值再次變小，仍需要對(duì)其所有邊再次進(jìn)行松弛，這樣才能保證相鄰頂點(diǎn)的最短路程估計(jì)值同時(shí)更新。初始時(shí)將源點(diǎn)加入隊(duì)列，每次隊(duì)首（head）取出一個(gè)頂點(diǎn)，并對(duì)與其相鄰的所有頂點(diǎn)進(jìn)行松弛嘗試，若某個(gè)點(diǎn)松弛成功，且這個(gè)相鄰的頂點(diǎn)不在隊(duì)列中，則將他加入到隊(duì)列中，對(duì)當(dāng)前頂點(diǎn)處理完畢后立即出隊(duì)，并對(duì)下一個(gè)新隊(duì)首進(jìn)行如上操作，直到隊(duì)列為空時(shí)算法結(jié)束。這里用一個(gè)book數(shù)組來(lái)記錄每個(gè)頂點(diǎn)是否在隊(duì)列中[4]。3.5管理運(yùn)籌學(xué)軟件管理運(yùn)籌學(xué)軟件提供了線性規(guī)劃，圖與網(wǎng)絡(luò)，其他模型三大類功能，擁有線性規(guī)劃、運(yùn)輸問(wèn)題、整數(shù)規(guī)劃、目標(biāo)規(guī)劃，對(duì)策論等運(yùn)籌方案，可以很好滿足用戶的各種運(yùn)籌管理需求，得到路徑的優(yōu)化方案。4數(shù)據(jù)的收集與整理4.1運(yùn)輸距離數(shù)據(jù)的采集4.1.1確定地圖位置研究的主題是柏鄉(xiāng)鎮(zhèn)方魯村小配送中心向柏鄉(xiāng)鎮(zhèn)8個(gè)小超市即福順超市、豐隆超市、冠遲超市、愛家超市、美陽(yáng)購(gòu)物、英杰購(gòu)物中心、聚寶隆超市、博宇超市配送的路徑優(yōu)化問(wèn)題。在高德地圖上標(biāo)出各地的具體位置，如圖所示。4.1.2確定各地運(yùn)輸距離如下圖所示，用高德地圖地位，分別得出不同地點(diǎn)之間的距離。配送站到各地的距離：新福順超市2.4千米，豐隆超市2.2千米，冠遲超市3.4千米，愛家超市3.3千米，美陽(yáng)購(gòu)物2.9千米，英杰購(gòu)物中心2.4千米，聚寶隆超市3.6千米，博宇超市1.1千米。新福順超市到各地距離：豐隆超市0.428千米，冠遲超市2.2千米，愛家超市0.802千米，美陽(yáng)購(gòu)物0.22千米，英杰購(gòu)物中心0.517千米，聚寶隆超市1.5千米，博宇超市5.9千米。豐隆超市到各地距離：冠遲超市3.3千米，愛家超市3.1千米，美陽(yáng)購(gòu)物2.6千米，英杰購(gòu)物中心1.4千米，聚寶隆超市3.0千米，博宇超市5.2千米。冠遲超市到各地距離：愛家超市2.6千米，美陽(yáng)購(gòu)物2.1千米，英杰購(gòu)物中心1.5千米，聚寶隆超市2.7千米，博宇超市6.7千米。愛家超市到各地距離：美陽(yáng)購(gòu)物5.9千米，英杰購(gòu)物中心5.3千米，聚寶隆超市4.3千米，博宇超市6.6千米。美陽(yáng)購(gòu)物到各地距離：英杰購(gòu)物中心1.6千米，聚寶隆超市2.8千米，博宇超市6.9千米。英杰購(gòu)物中心到各地距離：聚寶隆超市3.3千米，博宇超市6.6千米。聚寶隆超市到各地距離：博宇超市6.3千米。4.2運(yùn)輸距離數(shù)據(jù)整理 將所得數(shù)據(jù)進(jìn)行整理，填入表格中。配送站新福順超市豐隆超市冠遲超市愛家超市美陽(yáng)購(gòu)物英杰購(gòu)物中心聚寶隆超市博宇超市配送站2.42.23.43.32.92.43.61.1新福順超市0.4282.20.8020.220.5171.55.9豐隆超市3.33.12.61.43.05.2冠遲超市2.62.11.52.76.7愛家超市5.95.34.36.6美陽(yáng)購(gòu)物1.62.86.9英杰購(gòu)物中心3.36.6聚寶隆超市6.3博宇超市5管理運(yùn)籌學(xué)軟件求解5.1管理運(yùn)籌學(xué)軟件介紹管理運(yùn)籌學(xué)軟件3.0是一款功能強(qiáng)大的運(yùn)籌管理工具，為用戶提供了線性規(guī)劃，圖與網(wǎng)絡(luò)，其他模型三大類功能，擁有線性規(guī)劃、運(yùn)輸問(wèn)題、整數(shù)規(guī)劃、目標(biāo)規(guī)劃，對(duì)策論等運(yùn)籌方案，可以很好滿足用戶的各種運(yùn)籌管理需求，非常適用于科學(xué)、運(yùn)籌學(xué)、生產(chǎn)運(yùn)作管理等場(chǎng)合，讓運(yùn)籌管理更加輕松高效。并且軟件中的每種運(yùn)籌方案都提供了詳細(xì)的數(shù)據(jù)錄入方式，例如在線性規(guī)劃模式下就可以自定義變量個(gè)數(shù)、約束條件個(gè)數(shù)、目標(biāo)函數(shù)，設(shè)置完畢就可以生成表格錄入詳細(xì)的數(shù)據(jù)，從而在軟件快速分析各項(xiàng)數(shù)據(jù)，結(jié)合模型就可以直觀的查看分析結(jié)果，讓用戶可以輕松管理統(tǒng)籌項(xiàng)目。另外，管理運(yùn)籌學(xué)軟件還支持多重求解，將一組數(shù)據(jù)提供不同的函數(shù)變量計(jì)算出可能出現(xiàn)的多組數(shù)據(jù)。5.2管理運(yùn)籌學(xué)軟件建模求解打開管理運(yùn)籌學(xué)軟件，點(diǎn)擊“圖與網(wǎng)絡(luò)模塊”中的“最短路問(wèn)題”，根據(jù)所調(diào)查的數(shù)據(jù)，輸入信息。軟件輸出一系列結(jié)果，如下表所示。整理信息可得最短路徑為1→3→6→4→5→2→7→8→9→1，總路程為2.2+2.6+2.1+2.6+0.802+0.517+3.3+6.3+1.1=21.519。6總結(jié)將最短路理論應(yīng)用到實(shí)際生活中，尤其是在配送路線中的應(yīng)用具有非常重要的意義，可以提高物流配送效率，降低物流配送成本，完善配備服務(wù)，提高市場(chǎng)競(jìng)爭(zhēng)力。這顯出學(xué)習(xí)和應(yīng)用最短路問(wèn)題原理的重要性。另外最短路問(wèn)題在城市道路建設(shè)、物資供應(yīng)站選址等問(wèn)題上也有很重要的作用。使用管理運(yùn)籌學(xué)軟件可以大量分析數(shù)據(jù)，得出最短路線，極