冷鏈配送中的優(yōu)化算法分析及應(yīng)用

徐清泉　趙夏　尚慶生

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

關(guān)鍵詞：冷鏈配送 優(yōu)化算法 分析應(yīng)用

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

1 引言

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

2 冷鏈配送概述

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

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

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

3 物流配送優(yōu)化算法比較

目前優(yōu)化算法有兩種：精確算法和啟發(fā)式算法。精確算法有Floyd算法、割平面法、Dijkstra算法、動態(tài)規(guī)劃算法、分支定界法等。啟發(fā)式算法有禁忌搜索算法、蟻群算法、節(jié)約算法、模擬退火算法、遺傳算法[4]、粒子群算法、掃除算法等。

物流配送優(yōu)化算法，大多數(shù)選擇蟻群算法、禁忌搜索算法、節(jié)約算法、神經(jīng)網(wǎng)絡(luò)算法、遺傳算法、帶時間窗的遺傳算法、粒子群算法等，或者選擇相互組合和優(yōu)化改進的啟發(fā)式算法。對以上算法進行比較[5]如表1所示。

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

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

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

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

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

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

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

4 Floyd算法與遺傳算法

4.1 Floyd算法

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

4.2 遺傳算法

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

4.3 Floyd算法求解步驟與應(yīng)用

Floyd算法求解步驟：

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

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

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

根據(jù)MyEclipse運行得出結(jié)果如圖3所示。

5 結(jié)語

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

參考文獻

[1]國務(wù)院.物流發(fā)展中長期規(guī)劃（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].甘肅農(nóng)業(yè)，2014，384（06）：7-8.

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

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

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