緒論研究背景近幾年，伴隨著消費升級與生活質量的提高，企業(yè)越來越關注食品的質量與安全。有著規(guī)范與品質并存的冷鮮肉，受到市場和消費者的關注與歡迎。隨著消費者對食品的重視，我國豬肉行業(yè)存在著由低溫肉制品及冷鮮肉取代傳統(tǒng)生鮮肉的可能。目前國內對于冷鮮肉有專業(yè)的物流運輸，但依然存在著冷鮮肉運輸成本過高、運輸效率低、基礎設施不完善等問題。國內肉類企業(yè)用于冷鮮肉運輸配送的冷藏車及保溫車達不到發(fā)達國家的水平，不但數量不夠，且在技術也相對落后。然而在運輸途中需要設備持續(xù)制冷，保證產品品質，想要好的設備就需要投入更多資金。在運輸配送途中受天氣、時效、交通的影響，在運送途中時間較長也會影響品質，由于天氣不好、交通堵塞也可能會導致配送延遲，這些都是導致冷鮮肉的運輸成本高、維持冷鮮肉品質而造成浪費的情況。運輸問題是提高物流成本及效率的關鍵。若想解決冷鮮肉的運輸問題，則要從冷鮮肉運輸的運價、路程、時間以及配送方案等多方面進行綜合考慮，將科學的運輸模型運用到實踐中進行求解，最終解決問題。冷鮮肉物流運輸的完善讓市場資源供應及時，滿足了消費者的需求，并促進企業(yè)的經濟發(fā)展。本文在這樣的背景下，研究冷鮮肉的運輸決策問題和運輸分配問題。把理論與實踐相結合，最大程度地降低企業(yè)運輸成本，推動冷鮮肉企業(yè)更好的發(fā)展。研究意義本文對簡陽H公司物流運輸中存在的路徑規(guī)劃、運輸分配的問題展開調查，運用科學決策模型、算法進行優(yōu)化研究。通過對這兩大問題的研究，希望能促進物流運輸決策在冷鮮肉物流中的廣泛應用，使冷鮮肉不再出現運輸成本過高的現象。通過科學的研究和高效的技術，促進冷鮮肉企業(yè)的全面發(fā)展。其實在企業(yè)的發(fā)展中，對于物流運輸方面的問題常常以運輸路線規(guī)劃不全面，運輸決策設計不合理等現象出現，貨物的供應不及時，供貨量和需求量不準確，車輛調度的充分利用率低。這就對冷鮮肉物流企業(yè)的長久發(fā)展構成了威脅，要想解決這一大難題，就必須通過模型與實際案例的不斷結合，得出最有效的解決方法，從而對冷鮮肉物流企業(yè)發(fā)展提供一定的指導意義。研究內容本文通過對H公司冷鮮肉的物流運輸路徑及運輸分配進行優(yōu)化研究，結合H公司冷鮮肉在簡陽區(qū)域的運輸現狀，發(fā)現在運輸中存在的一系列問題，基于這些問題構建了Dijkstra算法的運輸決策模型及表上作業(yè)法運輸分配模型，結合H公司冷鮮肉供應地向周邊市區(qū)需求地進行運輸決策，再以H公司盛產冷鮮肉的三個鄉(xiāng)鎮(zhèn)作為供應地選擇最優(yōu)的運輸分配方案，將鮮肉運送到附近區(qū)縣進行加工的應用案例作為研究內容。本文通過模型及算法的實際運用針對實際問題提供指導性意義。研究方法與技術路線研究方法本文主要采用的是理論模型解決實際問題的研究方法。本文已進行相關資料數據的收集，掌握了物流模型與相關算法的理論知識。通過當地冷鮮肉的情況，包括特定的供應地到特定的需求地運輸時間，供應地的冷鮮肉供應量以及各供應地到各加工點之間的單位運價等。本文主要研究運輸決策問題和運輸分配方案的解決方法，所用數據是生活中的相關數據，沒有對數據進行過多篩選與求實，并且對于實際環(huán)境和情況有些忽視，與現實相關問題有一定差別?，F實情況飄忽不定且十分復雜，涉及的數據更加混雜，需要專業(yè)的團隊做準確的調查才能統(tǒng)計出真實數據，但解決思想是一致的。技術路線技術路線圖展示如下圖1.4：圖1.4論文技術路線圖國內外研究綜述國內研究綜述我國許多學者對于冷鮮肉運輸方面作出了研究。與國外相比，國內在冷鮮肉物流方面的研究相對來說比較落后，目前國內的研究雖然還處于起步階段，但是整體來說已經取得了一些理論方面的研究成果。張嘉琪淺析陜西省農產品的物流配送,以規(guī)范配送體系,實現農產品的高效配送REF_Ref14089\r\h[1]。黃建新、陳姣敏、賓厚利用Dijkstra算法在原有物流設施場所的基礎上進行物流節(jié)點選址的優(yōu)化，加上物流節(jié)點的優(yōu)化可適當減少物流成本，促進社會經濟效益的提高REF_Ref15098\r\h[2]。劉志遠學者結合配送數據及目標函數,利用MATLAB軟件編碼來計算模型求解的最優(yōu)路徑結果,得到路徑優(yōu)化后的成本及顧客滿意度REF_Ref15193\r\h[3]。李慧芝學者以S企業(yè)在漯河地區(qū)對連鎖店每日進行冷鮮肉物流配送路徑為研究對象，結合S企業(yè)目前的配送數據和所構建的目標函數,并對函數中的參數進行設定,利用改進后的遺傳算法作為求解算法,與原先的方案對比發(fā)現,新方案在各項配送成本方面明顯降低REF_Ref15307\r\h[4]。高建玲學者以H公司冷鮮肉物流為研究對象,通過分析企業(yè)物流配送狀況,找出配送的問題,把遺傳算法與爬山算法進行結合并求解,得出優(yōu)化后的配送方案,從而為H公司冷鮮肉配送提供參考意見REF_Ref15480\r\h[5]。張倩,徐靜,謝文華學者以X企業(yè)為研究對象，通過分析X企業(yè)冷鮮肉物流配送存在的不足，建立總配送成本的車輛路徑優(yōu)化模型，運用節(jié)約里程算法對模型進行求解。最后，驗證模型具有一定的可行性REF_Ref15624\r\h[6]。紀汝方學者通過實地調查W連鎖超市的配送路線和選取門店的訂貨資料,分析得出W連鎖超市的問題,分別建立目標為成本最小的VRP模型,最后發(fā)現得到了改善REF_Ref15905\r\h[7]。黃敏志學者構建載重耗電率的電動車路徑規(guī)劃模型,模型以總成本最小為目標函數,結合遺傳算法和爬山算法設計了改進遺傳算法,進行驗證表明本文研究理論為企業(yè)提供了決策支持,具有重要意義REF_Ref15999\r\h[8]。李可昕學者以M生鮮肉類公司為研究對象,在國內外生鮮品冷鏈配送路徑優(yōu)化問題及電動汽車冷鏈配送路徑優(yōu)化問題的基礎上,將時變路網情況融入到冷鏈配送路徑優(yōu)化的問題研究上REF_Ref15999\r\h[9]。李夏楠學者以M超市生鮮產品冷鏈物流為研究對象,對M超市生鮮產品在運送過程中產生的各項成本進行分析,以成本最小化為目標函數,建立物流配送路線優(yōu)化模型,通過改寫遺傳算法程序代碼求解該模型,分析得出合適配送路線,驗證算法的有效性和可行性REF_Ref16463\r\h[10]。王西狀學者主要研究HFZ社區(qū)便民直銷店配送路徑存在的問題,為解決該問題提出建議。將優(yōu)化前的配送里程數、配送的總成本與優(yōu)化后的配送里程數、配送的總成本進行比較,利用遺傳算法為企業(yè)降低了配送成本,減少了配送里程REF_Ref16554\r\h[11]。張敬璇學者針對生鮮農產品的特殊之處,在運輸車輛的載重量和時間約束下,采用多車型取送結合的配送模式,建立了以成本最小為目標函數的冷鏈物流配送路徑優(yōu)化模型REF_Ref16554\r\h[12]。呂成瑤,邵可南,張帥帥等學者以冷鏈配送過程中的總成本為優(yōu)化目標,以車輛載重以及客戶要求為條件建立模型,分析溫度和時間對各項成本的影響,分別討論運輸過程和卸貨過程的制冷、貨損成本,并用指數函數表示生鮮食品的腐敗規(guī)律REF_Ref16786\r\h[13]。黃遵娟學者對城市冷鏈物流配送路徑問題進行研究,本文得出的研究結論對優(yōu)化配送路徑,提高配送效率和物流服務水平具有一定參考價值REF_Ref16845\r\h[14]。王詩雅針對某易腐品企業(yè)沈陽市分公司冷鮮肉配送存在的的問題,所提出的VMI模式下的固定配送周期,對該企業(yè)采用先進的物流管理模式提升其運營能力具有一定的實踐指導意義REF_Ref16871\r\h[15]。國外研究綜述國外的學者也在研究冷鮮肉運輸方面的問題。20世紀50年代國外就開始了對于冷鮮肉配送路徑問題的研究，Dantzig和Ramser最先提出冷鮮肉車輛路徑研究的觀點，后來被廣泛的運用到不同的領域。近幾年很多不同領域的專家，把理論知識應用到冷鮮肉車輛路徑優(yōu)化問題之中，并對進行了深入的研究，且取得了顯著的成果。2013年WeiYang等人基于冷鮮肉物流配送路徑優(yōu)化模型，構造粒子群優(yōu)化算法求解優(yōu)化問題，以冷鮮肉物流配送路徑優(yōu)化問題為例，最后進行了結果驗證REF_Ref17926\r\h[16]。2015年Kim,G從利益相關者的角度進行考慮車輛路徑問題，設計了相關約束條件、構建了數學模型、并提出了解決方案，此外還指出了未來潛在研究領域的發(fā)展方向REF_Ref18054\r\h[17]?；A理論冷鮮肉物流基本理論冷鮮肉物流定義冷鏈物流，指的是一些需要冷凍的食品，從生產到運輸再到消費前的各個環(huán)節(jié)都處在規(guī)定的低溫環(huán)境中，采用溫度保存的這種方法來保證食品的質量，以便減少對食品的虧損。冷鏈物流建立在現代制冷技術設備與管理層面上，以現代冷凍工藝學為基礎，是一個復雜的低溫運輸過程。冷鏈物流的適用品種多，包括初級農產品（如蔬菜、水果、肉和蛋）、加工產品（如速凍冷藏品、肉等的包裝熟食、冰淇淋及快餐食品）、特殊商品和藥品、化工危險品。冷鮮肉對宰割后的牲畜肉體進行冷藏處理，使肉體的溫度在一天內降到0-4℃，并在后續(xù)的加工、流通、包裝處理下保持低溫的生鮮肉。冷鮮肉又叫“冷卻排酸肉”，是因為在加工前期經過了預冷排酸，把肉變成“成熟”的過程，讓肉呈現出一種濕潤感，摸起來綿軟且有彈性，加工后易入味，口感鮮嫩。冷鮮肉作為冷鏈中的一種產品，在后期的生產加工、冷藏、流通、包裝、配送的過程中持續(xù)保持在0-4℃內，因此冷鮮肉物流也屬于冷鏈物流范疇。冷鮮肉物流的特征冷鮮肉物流與普通物流不同，特殊之處在于對溫度、濕度等有極高要求在儲存和運輸方面上，總結如下。時效要求高冷鮮肉在常溫環(huán)境下細菌繁殖速度極快，容易產生氨氣味或酸味或刺鼻氣味，導致肉體腐敗變質，味道喪失，嚴重的會影響身體健康。冷鮮肉在運輸配送途中對時效要求極高，即便在低溫下細菌繁殖速度變慢，由于配送時間的問題也會導致食物變質，也會影響客戶對后續(xù)的肉類儲藏，因此要嚴格控制冷鮮肉的運輸時間。溫控要求高車輛在運輸途中，溫度隨時都在變化，溫度過高會加速微生物的繁殖速度，冷鮮肉需要保持在0-4℃低溫環(huán)境，以便冷鮮肉的質量能夠得到保證。高成本性隨著科技的發(fā)展，冷鏈設施設備也在不斷完善，與普通物流相比，冷鮮肉物流對運輸條件要求更高，產品在運輸過程中需要持續(xù)制冷，為了保證產品的質量，必須要安裝溫控設備，購買冷藏車或者低溫倉庫，采用的是現進技術，所以會投入大量資金，與傳統(tǒng)物流成本比相對更高。配送受交通的影響大由于需求量大冷鮮肉需要每日配送，但是配送的途中容易受到城市交通的管制的影響，比如號牌的限制、道路施工、天氣變化影響配送延遲配送等。運輸最短路徑問題及DIJKSTRA算法運輸最短路徑問題運輸最短路徑問題，就是求兩個頂點之間長度最短的路徑。也是指在多條運輸線路中，選中一個節(jié)點為起始點，從起點到一個或多個目的地的線路，其中會經過很多運輸節(jié)點，一個中轉節(jié)點到其他所有中轉節(jié)點的最短路徑，從而構成運輸最短路徑。DIJKSTRA算法當前，求解運輸最短路徑方法有很多，如Dijkstra、floyd（弗洛伊德算法）、SPFA算法等，其中Dijkstra算法是最典型的最短路算法，算法的基本過程是采用標號法，在操作過程中會用到兩種標號，永久性標號P和試探性標號T，其原理和步驟如下。算法原理：若某一路徑P是由起點v1到終點vi(i=2,3,4,5...）的最短路徑，那么該路徑P上的任意一點到起點算法步驟：第一步：記圖中的各個節(jié)點編號為vi(i=1,2,3...i);v1為終點;給v1標號，即P（v1）=0，其他各節(jié)點vi均記為T標號，T（第二步：從起點v1出發(fā)，尋找與它直接相連（有弧連接）的節(jié)點vi，計算各節(jié)點vi到起點的時間多少（即弧長T1i)。同時，把這些頂點vj的T標號修改為T（vi）=min{T（vi），第三步：比較所有的T標號，把最小的T標號修改為P標號。第四步：不斷尋找圖中剩下的點，直到全部頂點均為P標號，找出最終的最短路徑集合P，連接P中的路線即為最短路徑。當存在兩個相同或最小的T標號時，可以同時修改為P標號。運輸分配問題及表上作業(yè)法運輸分配問題運輸分配問題是指按照客戶的訂單，在物流節(jié)點處進行分揀，裝貨，加工和配貨等作業(yè)后，將裝配好的貨物運輸到接受地的過程。表上作業(yè)法求解運輸分配問題可以建立線性規(guī)劃模型進行求解，也可以通過構建運輸分配表，通過表上作業(yè)法進行求解，常用的表上作業(yè)法有西北角、最小元素法、位勢法、閉回路法等。本文將采用最小元素法尋找初始可行解、用位勢法進行檢驗、采用閉回路進行解的改進。最小元素法是一種尋找排序數據中最小項的算法，通過查找數據中的每一個元素，來尋找最小值。從供需表的最小元素的格子入手，選中運價最小的格子，滿足它的需求量，通過行（列）的銷量和產量的比較，在格子的右下方標上獲取的最大數，在原先的供需量基礎上修改余下的量。當某行（列）的供應量或銷量滿足時，則把該行（列）劃去，如此進行下去，直到得到一個初始基本可行解。位勢法：通過與基變量對應的單位運價，把各行各列對應的位勢（可先設成未知數）求出來，再利用它求出非基變量檢驗數的一種方法，方法的合理性來源于線性規(guī)劃問題的對偶理論。閉回路法：為了確認空格的檢驗數，可先找出以空格為頂點，其余頂點全是數字格的閉回路。閉回路就是從該空格出發(fā)，沿水平或垂直方向前進，遇到合適的數字格后轉90°，繼續(xù)前進。若能回到出發(fā)點，則稱這個封閉折線為閉回路。然后調整閉回路上其他數字格的運量，使產銷平衡。冷鮮肉物流運輸現狀及存在問題分析冷鮮肉物流運輸現狀分析近年來，簡陽被劃分到成都管理，成都市政府投入大量資金在基礎設施，比如簡陽的天府機場，地鐵18號線，高鐵等等，促進了簡陽經濟飛速發(fā)展。隨著經濟的發(fā)展，企業(yè)的生活水平得到了大大提升。冷鮮肉正處在快速發(fā)展階段，尤其是在新一線城市，消費者對生鮮肉類的需求日益增加。隨著環(huán)保壓力的日益增大，散戶養(yǎng)殖正在加速退出市場，降低市場生豬供給量，使得行業(yè)集中度提高。同時傳統(tǒng)的肉類銷售模式逐漸暴露出新鮮度、食品安全和交通成本等問題，這也為冷鮮肉行業(yè)的崛起提供了機遇。冷鮮肉行業(yè)以其獨特的優(yōu)勢不斷拓展市場份額。相比傳統(tǒng)肉類市場，冷鮮肉的供應鏈更加完善和透明，保證了產品的品質和食品安全。在冷鮮肉的發(fā)展過程中，互聯網技術的應用也發(fā)揮了重要的作用。通過電商平臺和移動應用程序，消費者可以方便地選購并迅速收到新鮮肉類產品。這種線上線下結合的模式使得冷鮮肉行業(yè)在市場競爭中具備了更大的優(yōu)勢。另外，以冷凍食品行業(yè)為代表的冷鏈物流是整個食品行業(yè)的一個重點發(fā)展方向。目前，國家政府也對冷鮮肉行業(yè)提出了政策支持，簡陽市政府也很看好冷鮮肉行業(yè)，頒布大力發(fā)展冷鮮肉行業(yè)的政策，比如在食品安全監(jiān)管和行業(yè)標準制定方面加大了力度，為冷鮮肉行業(yè)的規(guī)范化發(fā)展提供了保證同時，簡陽市政還鼓勵企業(yè)加大對冷鮮肉的研發(fā)和創(chuàng)新力度，推動行業(yè)的迅速壯大。當前簡陽冷鮮肉已銷往北京、上海、廣州、杭州、成都等地，深受消費者的喜愛。冷鮮肉的運輸是通過當地供應商安排大批貨運車運輸，從三岔、石盤、賈家路大批量運輸到成都、資陽、重慶等各大城市進行銷售，其次運往各個縣城進行小批量銷售或者二次加工成為附加值高的、儲存時間長的產品再運輸到各大城市進行售賣。冷鮮肉物流運輸存在問題分析由于鄉(xiāng)鎮(zhèn)地區(qū)物流運輸不科學，供應源分散且運輸決策設計不合理，導致在冷鮮肉的運輸路線選擇上缺乏科學的理論依據和專業(yè)的物流知識，從而導致運輸成本高、運輸時效性差、運輸效率不高。從產地到各個銷地之間有很多路線，會有鄉(xiāng)道、縣道、省道、國道，道路環(huán)境復雜多變，路程數據龐大，如何選擇最優(yōu)路線進行高效分配，這是一個復雜的決策問題。同時，冷鮮肉供應地供不應求，需求地供過于求的現象頻繁出現。路徑優(yōu)化和運輸決策問題所涉及的運輸效率低，運費過高導致物流成本占比高，企業(yè)獲得的利潤占比低，最終阻礙了企業(yè)冷鮮肉的發(fā)展。為此本文通過實際案例與模型結合進行科學決策，以這兩個問題為研究內容，通過Dijkstra算法和表上作業(yè)法來進行求解，希望通過理論與實踐相結合的方式來降低物流成本，促進企業(yè)冷鮮肉發(fā)展有一定的指導意義。H公司單一供應點到多個需求點運輸路徑決策研究H公司單一供應點到多個需求點運輸路徑決策問題導入針對本文的運輸路線選擇不科學問題，本文選取簡陽和五個市區(qū)作為案例進行運輸路徑決策研究。其運輸路線有：簡陽-成都、簡陽-樂山、簡陽-瀘州、簡陽-重慶、簡陽-廣安，其中供應點到多個銷售點會經過許多運輸節(jié)點，網絡結構復雜，因此，必須通過建立數學模型進行科學決策。通過對調研數據的分析進行運輸網絡的建模，簡陽到各個城市銷售的運輸網絡圖如下。其中v代表地點，T代表時間。如圖4.1所示。v1v（成都）v（廣安）v（樂山）v（資陽）v（安岳）v（遂寧）v8（v（內江）v（自貢）v（隆昌）v（瀘州）v（重慶）T11（T（簡陽到遂寧）T（成都到樂山）T（簡陽到樂山）T（簡陽到資陽）T（資陽到安岳）T（資陽到自貢）T18（T19（T20（T21（T22（T23（T24（T25（T26（T27（T28（T29（T30（T31（T32（T33（T34（T35（T36（圖4.1運輸網絡示意圖決策目標就是求從v1到v2,v3,v4,v12基于Dijkstra算法的運輸最短路徑求解Dijkstra算法的基本原理：如果某一路徑P是從起點v1到終點vn(n=2,3,4,5...）的最短路徑，那么該路徑P上的任意一點到起點第一步：初始化：給所有節(jié)點進行標號vi(λ，T），其中vi代表節(jié)點，λ代表節(jié)點vi設起點v1設置P為已找到最短路徑點集合，其初始值為{v1圖4.2最短路徑求解第1次迭代第二步：從起點v1出發(fā)，搜索與之相鄰連接的節(jié)點vi，計算各節(jié)點vi到起點的時間是多少，如果小于個節(jié)點標號中的初始值λ（v從中選出最短時間的節(jié)點（λ，（vi）），將其列入到最短路徑集合P={v1，圖4.2最短路徑求解第2次迭代第三步：從剩余網絡（成都、遂寧、廣安、安岳、潼南、自貢、內江、樂山、隆昌、瀘州、重慶）中搜索與節(jié)點相鄰的節(jié)點，重新計算路徑值，找出最小的路徑值。與資陽相鄰的節(jié)點有安岳、自貢。安岳：0.5+1.1=1.6<+∞自貢：0.5+1.5=2<+∞因此，修改的節(jié)點為安岳（資陽，1.6）、自貢（資陽，2）結合剩下的成都（簡陽，1.1）、遂寧（簡陽，1.5）、樂山（簡陽，2）。找出與出發(fā)點時間最短的節(jié)點，即成都（簡陽，1.1），將成都納入P集合中{簡陽、資陽、成都}，如圖所示：圖4.3最短路徑求解第3次迭代第四步：繼續(xù)從剩余的網絡中搜索與新增節(jié)點相鄰的節(jié)點vi與成都相鄰的節(jié)點有樂山、廣安。樂山：1.1+1.3=2.4>2廣安：1.1+3.2=4.3<+∞由于樂山節(jié)點大于原有值，所以修改節(jié)點為樂山（簡陽，2）、廣安（成都，4.3），結合剩余的未找到最短路徑的節(jié)點安岳（資陽，1.6）、自貢（資陽，2）、遂寧（簡陽，1.5）去尋找到出發(fā)點時間最短的節(jié)點，由本次計算中，到簡陽時間最短的節(jié)點為遂寧（簡陽，1.5），將遂寧納入到P集合中{簡陽、資陽、成都、遂寧}，如圖所示：圖4.4最短路徑求解第4次迭代第五步：繼續(xù)從剩余網絡中搜索與新增節(jié)點相鄰的節(jié)點，并重新計算到起點的路徑值。與遂寧相鄰的節(jié)點有潼南、廣安、安岳。廣安：1.5+2.1=3.6<4.3潼南：1.5+0.9=2.4<+∞安岳：1.5+1=2.5>1.5即廣安（遂寧，3.6）潼南（遂寧，2.4）因此，修改節(jié)點為廣安（遂寧，3.6）、潼南（遂寧，2.4），結合剩余的未找到最短路徑的節(jié)點安岳（資陽，1.6）、自貢（資陽，2）、樂山（簡陽，2）去尋找到出發(fā)點時間最短的節(jié)點，由本次計算中，到簡陽時間最短的節(jié)點為安岳（資陽，1.6），將安岳納入到P集合中{簡陽、資陽、成都、遂寧、安岳}，如圖所示：圖4.5最短路徑求解第5次迭代第六步：繼續(xù)從剩余網絡中搜索與新增節(jié)點相鄰的節(jié)點，并重新計算到起點的路徑值。與安岳相鄰的節(jié)點有內江、潼南。內江：1.6+1.1=2.7<+∞潼南：1.6+0.9=2.5>2.4（大于原有值不做修改）因此，修改節(jié)點為內江（安岳，2.7），結合剩余的未找到最短路徑的節(jié)點潼南（遂寧，2.4）、廣安（遂寧，3.6）、自貢（資陽，2）、樂山（簡陽，2）去尋找到出發(fā)點時間最短的節(jié)點，由本次計算中，到簡陽時間最短的節(jié)點為自貢（資陽，2），樂山（簡陽，2），將自貢和樂山納入到P集合中{簡陽、資陽、成都、遂寧、安岳、自貢、樂山}，如圖所示：圖4.6最短路徑求解第6次迭代第七步：繼續(xù)從剩余網絡中搜索與新增節(jié)點相鄰的節(jié)點，重新計算到起點的路徑值。與自貢相鄰的節(jié)點有內江、瀘州、樂山。內江：2+0.6=2.6<2.7瀘州：2+1.2=3.2樂山：2+1.3=3.3>2與樂山相連的節(jié)點有瀘州瀘州：2+2.5=4.5＞3.2由于瀘州這個節(jié)點大于原有值不做修改，修改節(jié)點為內江（自貢，2.6）、瀘州（自貢，3.2），結合剩余的未找到最短路徑的節(jié)點潼南（遂寧，2.4）、廣安（遂寧，3.6），去尋找到出發(fā)點時間最短的節(jié)點，由本次計算中，到簡陽時間最短的節(jié)點為潼南（遂寧，2.4），將潼南納入到P集合中{簡陽、資陽、成都、遂寧、安岳、自貢、樂山、潼南}，如圖所示：圖4.7最短路徑求解第7次迭代第八步：繼續(xù)從剩余網絡中搜索與新增節(jié)點相鄰的節(jié)點vi廣安：2.4+2=4.4>3.6重慶：2.4+1.9=4.3由于廣安節(jié)點大于原有的值，因此就不做修改，結合剩余的未找到最短路徑的節(jié)點廣安（遂寧，3.6）、內江（自貢，2.6）、瀘州（自貢，3.2)、重慶（潼南，4.3），去尋找到出發(fā)點時間最短的節(jié)點，由本次計算中，到簡陽時間最短的節(jié)點為內江（自貢，2.6），將自貢納入到P集合中{簡陽、資陽、成都、遂寧、安岳、自貢、樂山、潼南、內江}，如圖所示：圖4.8最短路徑求解第8次迭代第九步：繼續(xù)從剩余網絡中搜索與新增節(jié)點相鄰的節(jié)點vi（有弧連接），重新計算到起點的路徑值，若與內江相鄰的節(jié)點有潼南、隆昌潼南：2.6+1.5=4.1>2.4隆昌：2.6+0.6=3.2由于潼南節(jié)點大于原有的值，因此就不做修改，結合剩余的未找到最短路徑的節(jié)點隆昌（內江，3.2）、廣安（遂寧，3.6）、瀘州（自貢，3.2)、重慶（潼南，4.3），去尋找到出發(fā)點時間最短的節(jié)點，由本次計算中，到簡陽時間最短的節(jié)點為隆昌（內江，3.2），瀘州（自貢，3.2)將瀘州、隆昌納入到P集合中{簡陽、資陽、成都、遂寧、安岳、自貢、樂山、潼南、內江、瀘州、隆昌}，如圖所示：圖4.9最短路徑求解第9次迭代第十步：繼續(xù)從剩余網絡中搜索與新增節(jié)點相鄰的節(jié)點vi（有弧連接），重新計算到起點的路徑值，若與隆昌相鄰的節(jié)點有重慶、瀘州重慶：3.2+2.2=5.4＞4.3瀘州：3.2+1=4.2＞3.2由于隆昌節(jié)點處的瀘州大于原有的值，所以修改的節(jié)點為重慶（潼南，4.3），結合剩余的未找到最短路徑的節(jié)點廣安（遂寧，3.6），去尋找到出發(fā)點時間最短的節(jié)點，由本次計算中，到簡陽時間最短的節(jié)點為廣安（遂寧，3.6），將遂寧納入到P集合中{簡陽、資陽、成都、遂寧、安岳、自貢、樂山、潼南、內江、瀘州、隆昌、廣安}，如圖所示：圖4.10最短路徑求解第10次迭代第十一步：繼續(xù)從剩余網絡中搜索與新增節(jié)點相鄰的節(jié)點vi與廣安相鄰的節(jié)點有重慶、潼南重慶：3.6+2.1=5.7＞4.3潼南：3.6+2=5.6>2.4由于這兩個節(jié)點大于原有結點的值，因此不做修改，結合剩余的未找到最短路徑的節(jié)點重慶（潼南，4.3)，去尋找到出發(fā)點時間最短的節(jié)點，由本次計算中，到簡陽時間最短的節(jié)點為重慶（潼南，4.3)，將重慶納入到P集合中{簡陽、資陽、成都、遂寧、安岳、自貢、樂山、內江、瀘州、隆昌、廣安、重慶}，如圖所示：圖4.11最短路徑求解第11次迭代綜上，簡陽到成都最短路徑：簡陽-成都，所用時間為1.1h；簡陽到樂山最短路徑：簡陽-樂山，所用時間為2h；簡陽到瀘州最短路徑：簡陽-資陽-自貢-瀘州為3.2h；簡陽到廣安最短路徑：簡陽-遂寧-廣安為3.6h；簡陽到重慶最短路徑：簡陽-遂寧-潼南-重慶為4.3h。

H公司多個供應點到多個需求點運輸分配決策研究H公司多個供應點到多個需求點運輸分配決策問題導入簡陽冷鮮肉銷往全國各個城市，由于運輸距離遠，運輸時間長，中途會出現鮮肉腐爛、變質等一系列影響鮮肉質量問題，且單一運輸鮮肉的銷售利潤也無法讓企業(yè)獲得較多增收，相對的可能會導致企業(yè)虧本。把冷鮮肉進行多樣化加工，比如鮮肉罐頭、豬肉脯等，將冷鮮肉作為原料運往相近的縣區(qū)進行加工，通過加工提高附加值也能讓加工產品得到長期保存，從而運往全國各大城市進行銷售，企業(yè)也能獲得較大收益。運往加工的時間越短則加工產品完成率更高，從而使產品及時運往各個銷售地進行第一時間銷售。由H公司名下三個盛產冷鮮肉的供應地分別為三岔鎮(zhèn)，賈家鎮(zhèn)，蘆葭鎮(zhèn)，運往四個市區(qū)（需求商）：資陽市，內江市，眉山市，綿陽市進行加工。三岔鎮(zhèn)到資陽市、眉山市、內江市、綿陽市各地之間的單位運價分別為15元/噸、12元/噸、18元/噸、16.5元/噸；賈家鎮(zhèn)到資陽市、眉山市、內江市、綿陽市各地之間的單位運價分別為16.5元/噸、21元/噸、22.5元/噸、13.5元/噸；蘆葭鎮(zhèn)到資陽市、眉山市、內江市、綿陽市各地之間的單位運價分別為24元/噸、21元/噸、27元/噸、10.5元/噸；單位運價（用Cij表示）。三岔鎮(zhèn)、賈家鎮(zhèn)、蘆葭鎮(zhèn)各地供應量分別為80噸、120噸、90噸；資陽市、眉山市、內江市、綿陽市各地需求量分別為100噸、50噸、70噸、70噸；某一供應地運往需求地的運量用X表5.1供需表產銷資陽市眉山市內江市綿陽市供應量三岔鎮(zhèn)15121816.580賈家鎮(zhèn)16.52122.513.5120蘆葭鎮(zhèn)24212710.590需求量100507070290基于表上作業(yè)法的運輸分配決策求解第一步：求初始可行解最小元素法：方法是在表中找出最小的運價對應的供銷地，優(yōu)先滿足需求，然后再次比較運價選擇最小的運價對應的供銷地進行供應，依次下去，直到供需地滿足為止。最小運費為C34表5.2步驟一產銷資陽市眉山市內江市綿陽市供應量剩余量三岔鎮(zhèn)15121816.58080賈家鎮(zhèn)16.52122.513.5120120蘆葭鎮(zhèn)24212710.5（70）9020需求量100507070____不足量10050700____現在最小運價為C1表5.3步驟二產銷資陽市眉山市內江市綿陽市供應量剩余量三岔鎮(zhèn)1512（50）1816.58030賈家鎮(zhèn)16.52122.513.5120120蘆葭鎮(zhèn)24212710.5（70）9020需求量100507070____不足量1000700____現在的最小運價C11表5.4步驟三產銷資陽市眉山市內江市綿陽市供應量剩余量三岔鎮(zhèn)15（30）12（50）1816.5800賈家鎮(zhèn)16.52122.513.5120120蘆葭鎮(zhèn)24212710.5（70）9020需求量100507070____不足量700700____現在的最小運價C2表5.5步驟四產銷資陽市眉山市內江市綿陽市供應量剩余量三岔鎮(zhèn)15（30）12（50）1816.5800賈家鎮(zhèn)16.5（70）2122.513.512050蘆葭鎮(zhèn)24212710.5（70）9020需求量100507070____不足量00700____現在的最小運費C23表5.6步驟五產銷資陽市眉山市內江市綿陽市供應量剩余量三岔鎮(zhèn)15（30）12（50）1816.5800賈家鎮(zhèn)16.5（70）2122.5（50）13.51200蘆葭鎮(zhèn)24212710.5（70)9020需求量100507070____不足量00200____還剩最后一個運價C3表5.7步驟六產銷資陽市眉山市內江市綿陽市供應量剩余量三岔鎮(zhèn)15（30）12（50）1816.5800賈家鎮(zhèn)16.5（70）2122.5（50）13.51200蘆葭鎮(zhèn)242127（20）10.5（70）900需求量100507070____不足量0000____即初始可行解C總=15×30+12×50+16.5×70+22.5×50+27×20+10.5×70=4605（第二步：求檢驗數，并判斷初始可行解行解是否為最優(yōu)解——運用位勢法進行檢驗位勢法計算非基變量xij檢驗數公式：σij=cij-(ui+vj),在表5.7由最小元素法得到的初解中，x11，x12，x基變量檢驗數 x11c11-(u1+v1)=015-(x12c12-(u1+v2)=012-(x21c21-(u2+v1)=016.5-(x23c23-(u2+v3)=022.5-(x33c33-(u3+v3)=027-(x34c34-(u3+v4)=010.5-(令u1u1=0，u2=1.5，u3=6，v1=15，v2在初始方案表5.7中加入一列ui，一行vj，得到表5.8。ui表5.8檢驗數表產銷資陽市眉山市內江市綿陽市u三岔鎮(zhèn)15（30）12（50）1816.50賈家鎮(zhèn)16.5（70）2122.5（50）13.51.5蘆葭鎮(zhèn)242127（20）10.5（70）6v1512214.5__由表5.8和σij=cij-(uiσ13=c13-(u1σ14=c14-(u1σ22=c22-(u2σ24=c24-(u2σ31=c31-(u3σ32=c32-(u3因為σ13第三步：解的改進（閉回路法）：找到檢驗數為負的格子進行調整。選擇檢驗數中最小的檢驗數對應的非基變量處為起始點（以空格為奇數頂點），沿閉回路逆時針方向前進，尋找一條閉回路，選取閉回路中最小的基變量作為調整量θ。把閉回路上所有奇數頂點處的運輸量都增加這一數值θ，所有偶數頂點處的運輸量都減去這一數值θ，從而得到一個新的運輸方案。該運輸方案的總運費比原運輸方案少，改變量為θ。然后得到的新解進行最優(yōu)性檢驗，若不是最優(yōu)解，重復以上步驟進行調整，直到得到最優(yōu)解為止。從第二步得出的結果中，將未滿足條件的檢驗數σij（1）因為最小負檢數為σ13=-3，故以x13為起始點，x11，x21，x23依次為頂點得到一個閉環(huán)路，選擇最小調整量θ。調整：在x13構成的閉回路中，調整量θ=min(30,50)=30,即x13新的運輸分配方案表如表5.9所示：表5.9最新運輸分配方案表產銷資陽市眉山市內江市綿陽市供應量三岔鎮(zhèn)15（0）12（50）18（30）16.580賈家鎮(zhèn)16.5（100）2122.5（20）13.5120蘆葭鎮(zhèn)242127（20）10.5（70）90需求量100507070290最優(yōu)性判斷（閉回路法）：σ11=C11-C21（2）對其他空格（σ14，σ22，σ24表5.10檢驗表產銷資陽市眉山市內江市綿陽市供應量三岔鎮(zhèn)1512（50）18（30）16.580賈家鎮(zhèn)16.5（100）2122.5（20）13.5120蘆葭鎮(zhèn)242127（20）10.5（70）90需求量100507070290最優(yōu)性判斷（閉回路法）：σ14=C14-C13表5.11檢驗表產銷資陽市眉山市內江市綿陽市供應量三岔鎮(zhèn)1512（50）18（30）16.580賈家鎮(zhèn)16.5（100）2122.5（20）13.5120蘆葭鎮(zhèn)242127（20）10.5（70）90需求量100507070290最優(yōu)性判斷（閉回路法）：σ22=C22-C23+表5.12檢驗表產銷資陽市眉山市內江市綿陽市供應量三岔鎮(zhèn)1512（50）18（30）16.580賈家鎮(zhèn)16.5（100）2122.5（20）13.5120蘆葭鎮(zhèn)242127（20）10.5（70）90需求量100507070290最優(yōu)性判斷（閉回路法）：σ24=C24-C表5.13檢驗表產銷資陽市眉山市內江市綿陽市供應量三岔鎮(zhèn)1512(50)18（30）16.580賈家鎮(zhèn)16.5（100）2122.5（20）13.5120蘆葭鎮(zhèn)242127（20）10.5（70）90需求量100507070290最優(yōu)性判斷（閉回路法）：σ31=C31-C33+C表5.14檢驗表產銷資陽市眉山市內江市綿陽市供應量三岔鎮(zhèn)1512（50）18（30）16.580賈家鎮(zhèn)16.5（100）2122.5（20）13.5120蘆葭鎮(zhèn)242127（20）10.5（70）90需求量100507070290最優(yōu)性判斷（閉回路法）：σ32=C32-C33+C以上檢驗數均大于等于0，所以上述運輸分配方案為最優(yōu)方案。即三岔鎮(zhèn)分別往眉山市運50噸、內江市運30噸冷鮮肉；賈家鎮(zhèn)分別往資陽市運100噸、內江市運20噸冷鮮肉；蘆葭鎮(zhèn)分別往內江市運20噸、綿陽市運70噸冷鮮肉?？傔\費C=12*50+18*30+16.5*100+22.5*20+27*20+10.5*70=4515（元）

結論本文以簡陽冷鮮肉相關物流問題作為研究對象，針對運輸路徑和分配存在的問題進行研究與分析。通過理論與實踐的結合，最大程度地改善冷鮮肉物流運輸問題，并且該研究成果對其他冷鮮肉在物流運輸方面有一定的借鑒意義，促進了企業(yè)冷鮮肉物流的經濟發(fā)展。本文運用物流運輸決策的相關理論和方法，根據冷鮮肉存在的運輸路徑、運輸分配這兩大問題進行研究，成果如下：一是針對運輸路徑問題，運用Dijkstra算法進行科學地求解。首先根據已知條件畫出網絡圖，然后以簡陽為初始點（0，0）將剩余節(jié)點進行賦值（vi，+∞），搜索與簡陽直接相鄰的節(jié)點，計算各節(jié)點到起點的時間多少。同時，設置P為已找到最短路徑點集合，其初始值為｛簡陽}。找到最短路徑點集合P中新增節(jié)點相鄰的節(jié)點，重新計算到起點的路徑值，如果新值比原有的值小，則替換。最終結果為簡陽到成都最短路徑：簡陽-成都，所用時間為1.1h;簡陽到樂山最短路徑：簡陽-樂山，所用時間為2h;簡陽到瀘州最短路徑：簡陽-資陽-自貢-瀘州為3.2h;簡陽到廣安最短路徑：簡陽-遂寧-廣安為3.6h;簡陽到重慶最短路徑：簡陽-遂寧-潼南-重慶為4.3h二是針對運輸分配問題，運用表上作業(yè)法進行科學地選擇。在供應量以及需求量和單位運價限制下選擇最優(yōu)的分配方案。首先通過最小元素法得到初始解，運用位勢法經過多次檢驗，運用閉回路調整，最終使得全部非基變量檢驗數>=0，此時求得最優(yōu)解為三岔鎮(zhèn)分別往眉山市運50噸、內江市運30噸冷鮮肉；賈家