冷鏈配送中的優化算法分析及應用

徐清泉　趙夏　尚慶生

摘要：本文針對蘭州隴海農產品市場有限公司物流配送數字化集成與示范項目中存在的的難點問題，提出基于地理信息系統（GIS）的車輛路徑優化算法問題。對物流配送問題和GIS進行理論研究，得出GIS的地圖技術與物流配送結合是可行的。通過相關算法比較分析后，本文中選擇使用Floyd算法解決LRP問題，利用數字技術的優勢，實現整合現有資源，引進先進的信息處理技術，降低用戶的使用難度。在短期內使冷鏈配送業務實現信息化。解決蘭州隴海農產品市場有限公司物流配送的實際問題，為中小企業使用信息化手段進行物流車輛調度管理提供樣板和示范作用。

關鍵詞：冷鏈配送 優化算法 分析應用

中圖分類號：TP301 文獻標識碼：A 文章編號：1007-9416（2016）08-0143-03

1 引言

我國冷鏈物流的發展相對滯后。蔬菜產業已成為農村經濟的支柱產業。但是，由于我國蔬菜的采收和流通設施落后，在流通和消費領域，造成蔬菜嚴重腐損。不僅造成了巨大的經濟損失，還給人們的飲食安全構成了威脅[1]。實現高原夏菜的冷鏈配送已經成為促進高原夏菜產業長遠發展的必然選擇。高原夏菜冷鏈配送數字化技術集成項目建設也就顯得尤為迫切，利用數字技術將銷售系統、庫存管理系統、運輸車輛調度系統和配送信息查詢系統集成在一起，各系統之間實現數據共享和業務流程協作，提高高原夏菜冷鏈配送的效率，降低配送成本，建立起適合同類企業借鑒的新型配送模式[2]。甘肅省蔬菜種植面積逐年增加，高原夏菜已經成為多個地方農業生產發展中速度快、效益高的支柱產業之一。實現高原夏菜的冷鏈配送數字化集成已經成為促進高原夏菜產業長遠發展的必然選擇[3]。建成完善的高原夏菜冷鏈物流系統需要長期投入和建設。利用數字技術的優勢，整合現有資源，在短期內使冷鏈配送業務實現信息化，蘭州隴海農產品市場有限公司物流配送數字化集成與示范項目中已經進行該領域的積極研究探索和實踐應用[4]。

2 冷鏈配送概述

傳統配送、倉儲業正在向現代物流業轉化，而在這個轉化過程中，能否實現信息自動化處理是一大關鍵。目前大多數學者對定位-路徑優化問題研究停留在理論階段，在實際中運用較少[5]。甘肅省農業產業化重點龍頭企業蘭州隴海綠色產業集團有限公司現已建成榆中高原夏菜冷鏈物流基地、紅古高原夏菜種苗繁育基地，開展高原夏菜產業的品種選育、種苗繁育、市場交易、冷鏈物流、凈菜配送、技術研究等業務，致力于高原夏菜產業的發展，重視高原夏菜的信息化建設，積累了豐富的業務和技術經驗。對物流配送問題和GIS進行理論研究，結合企業應用的實踐說明，得出GIS的地圖技術與物流配送結合是可行的。

通過企業引進先進的信息處理技術，不僅會提高企業的自動化程度和信息共享度，提高工作效率，降低成本，更重要的是從根本上改變企業的戰略發展，使企業經營管理邁上新臺階。將最新的計算機信息技術應用到高原夏菜冷鏈配送的各個環節，通過信息化手段，提高企業的管理效率，降低運行成本建立適合于冷鏈物流企業的貨物配送模式，并構建相應的軟件平臺。本系統的關鍵點就在于物流配送優化算法，即在按需求合理安排車輛，并給出打印和查詢的運輸單和貨物的動態作業信息狀態的跟蹤，并為衛星定位技術（GPS），地理信息系統（GIS），射頻標識技術（RF）等提供接口，支持單物流配送中心和多物流配送中心等組織形式。

如圖1所示，通過配送中心將銷售系統、冷庫庫存管理系統、運輸車輛調度決策支持系統、配送信息查詢系統進行整合，提供訂單自動拆分、庫存自動查詢、自動規劃運輸路線、實時提供配送信息查詢等功能，建成一個自動化、高效率的高原夏菜冷鏈配送管理平臺，為企業發展提供助力。

3 物流配送優化算法比較

目前優化算法有兩種：精確算法和啟發式算法。精確算法有Floyd算法、割平面法、Dijkstra算法、動態規劃算法、分支定界法等。啟發式算法有禁忌搜索算法、蟻群算法、節約算法、模擬退火算法、遺傳算法[4]、粒子群算法、掃除算法等。

物流配送優化算法，大多數選擇蟻群算法、禁忌搜索算法、節約算法、神經網絡算法、遺傳算法、帶時間窗的遺傳算法、粒子群算法等，或者選擇相互組合和優化改進的啟發式算法。對以上算法進行比較[5]如表1所示。

遺傳算法參數如下：種群大小為100，城市數量為25，最大迭代次數為100，交叉率為0.8，變異率為0.9。

模擬退火算法有：城市數量，降溫次數，每個溫度迭代步長，初始溫度，降溫系數。

蟻群算法參數有：螞蟻數量，城市數量，運行代數，信息素發揮因子，alpha，beta，rho。

對模擬退火算法、遺傳算法、蟻群算法、貪心算法比較可知：針對在百度地圖中選取的坐標位數較多，數值較復雜，貪心算法對參數數值要求較高，所以無法得出滿意解。模擬退火算法對迭代步數要求高，在有限代數內無法得出有效解。蟻群算法有先天優勢，但算法對搜索時間過長，無法在較短的時間內求出最優解。在物流配送過程對時間和算法的效率要求高的前提下，在最短的時間內高效地得出最優解，從而規劃出最優路線。因此本文選擇遺傳算法解決LRP問題[6]。

tsplib上關于驗證TSP問題的數據bayg29，其中1-29是代表29個城市，X，Y代表城市的定位坐標。如表2所示。

為了驗證JAVA技術編寫遺傳算法的性能和可行性，選擇使用tsplib上關于驗證TSP問題的數據集bayg29在MyEclipse中進行計算，結果如圖2所示。

精確算法比較。最短路徑的精確算法有Floyd算法、分支定界法、Dijkstra算法、動態規劃法等。Dijkstra算法和Floyd算法都是在潛在配送中心和配送點之間的距離拓撲關系圖上進行計算，符合本文要求。Dijkstra算法是計算從一個源點到其他節點的單源點最短路徑。Floyd算法是計算節點之間的多源點最短路徑。本文中的LRP問題屬于多源點路徑問題，因此選擇Floyd算法解決LRP問題[7]。

4 Floyd算法與遺傳算法

4.1 Floyd算法

Floyd算法[2]是求出所有節點之間的最短距離，即多源點最短路徑算法。設距離圖D=（G，E），其中G表示潛在配送中心和配送點，E表示潛在配送中心和配送點之間的距離。Floyd算法的主要思想：首先求出每個節點之間的最短距離，然后計算各個節點到其他節點的最短距離，構造成距離矩陣。每次插入其他點gk，然后將g1到g2之間的最短距離與插入其他點gk后計算的最短距離進行比較，其中最小的作為新的距離矩陣[5]。不斷迭代，到達最后一個配送點，得出最終距離矩陣Ak。

4.2 遺傳算法

傳統遺傳算法大都遵行“適者生存，不適者被淘汰”的仿自然法則，Holland早期對遺傳算法的理解，認為遺傳算法的本質是自適應算法，在最優路徑、系統優化等方面應用最多[6]。Wetzel在1983年首先使用遺傳算法解決TSP問題。經過多年國內外學者的研究，遺傳算法發展迅速，形成一套完善的思想體系，基本思想：從初始種群開始，初始種群決定了。個體是染色體帶有特征的實體，決定了個體的形狀的外部表現。首先，確定初始種群并對初始種群進行編碼，即把實際問題參數表示為遺傳中的染色體形式，一般選擇十進制編碼或二進制編碼。利用適應度函數對經過編碼的染色體進行評估，適應度值越大，被選擇的概率越大。

4.3 Floyd算法求解步驟與應用

Floyd算法求解步驟：

（1）計算距離矩陣，并保存到每次加入插入點后的矩陣，其中

（2）配送中心分配。1個初始配送中心和25個配送點之間的最短距離已經通過百度地圖計算得出，運用Floyd算法把配送點按離第一個配送中心由近到遠排列，按照距離大小選出配送中心，并分配配送點。

（3）運用遺傳算法對分配好的配送中心和配送點尋找最優路線。選取蘭州隴海農產品市場有限公司為初始配送中心。從初始配送中心（X：104.061172，Y：35.936717）只分配一輛車到各配送中心配送蔬菜。每個配送中心對每一個配送點只能配送一次，對每個配送點進行隨機編號為第1至第25配送點，每個配送點都是潛在配送中心，運用Floyd算法選定配送中心。當配送點被選為配送中心后，編號為1-3。最后根據遺傳算法求出最優結果。

根據MyEclipse運行得出結果如圖3所示。

5 結語

本文針對蘭州隴海農產品市場有限公司物流配送數字化集成與示范項目中存在的的實際問題，提出基于地理信息系統（GIS）的車輛路徑優化算法問題。通過Floyd和遺傳組合算法解決無擁堵的LRP問題和有擁堵的LRP問題，并在百度地圖上對配送中心和配送點進行定位和標記，最后在百度地圖上規劃配送路線。具體實現對物流配送LRP應用問題進行整體研究和數學建模，通過配送中心將銷售系統、冷庫庫存管理系統、運輸車輛調度決策支持系統、配送信息查詢系統進行整合，提供訂單自動拆分、庫存自動查詢、自動規劃運輸路線、實時提供配送信息查詢等功能，建成一個自動化、高效率的高原夏菜冷鏈配送管理平臺。提出一種可推廣到同類企業的高原夏菜冷鏈配送模式。能夠提高冷鏈配送的效率，降低配送成本，較好地為企業發展提供助力。

參考文獻

[1]國務院.物流發展中長期規劃（2014-2020）[J].綜合運輸，2014，29（10）：78-86.

[2]Goldberg DE，Korb B，Deb K.Messy Genetic Algorithms： Motivation， Analysis and First Results. Complex Systems， 1989（3）：494-525.

[3]Kirkpatrick， Gelatt CD， VechiJr MP.Optimization by Simulated Annealing [J].Science，1983，220（4598）：671-680.

[4]趙夏，張靜芳，向萬里.基于蔬菜特性的蘭州高原夏菜物流運作模式研究[J].甘肅農業，2014，384（06）：7-8.

[5]趙夏，楊逸凡.基于GIS的高原夏菜物流配送問題研究[J].甘肅科技縱橫，2015，44（4）：49-51.

[6]李鑫麗.LRP及其圖論模型研究中[D].南京信息工程大學，2007.

[7]胡大偉.設施定位和車輛路線問題模型及其啟發式算法研究[D].長安大學，2008.