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

徐清泉　趙夏　尚慶生

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

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

中圖分類號(hào)：TP301 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1007-9416（2016）08-0143-03

1 引言

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

2 冷鏈配送概述

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

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

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

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

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

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

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

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

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

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

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

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

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

4 Floyd算法與遺傳算法

4.1 Floyd算法

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

4.2 遺傳算法

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

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

Floyd算法求解步驟：

（1）計(jì)算距離矩陣，并保存到每次加入插入點(diǎn)后的矩陣，其中

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

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

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

5 結(jié)語

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

參考文獻(xiàn)

[1]國務(wù)院.物流發(fā)展中長期規(guī)劃（2014-2020）[J].綜合運(yùn)輸，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]趙夏，張靜芳，向萬里.基于蔬菜特性的蘭州高原夏菜物流運(yùn)作模式研究[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.