基于GIS先驗知識的智能配送優化及實現
2011-01-01 00:00:00鄭湘麗
計算技術與自動化 2011年4期
文章編號：1003-6199(2011)04-0111-04
摘 要：物流配送作為物流產業的核心進程，其效率的高低直接影響整個物流業的發展。鑒于目前的配送調度多依賴于傳統的數學模型導致規劃的最優路線與實際經驗不相符，文章提出將實時交通信息、行車經驗等現實因素作為GIS先驗知識指導智能配送的優化的算法并進行實現。應用結果表明該成果能在很大程度上提高物流配送的效率。
關鍵詞：智能配送；遺傳算法；GIS先驗知識
中圖分類號： P208 文獻標識碼：A
Optimization and Realization of the Intelligence Distribution Based on Prior Knowledge of GIS
ZHENG Xiangli
(Shenzhen Careland Technology Co.， Ltd. Shenzhen 518040，China)
Abstract:As the core process of the logistics ，the efficiency of distribution will affect the development of logistics industry directly.The optimal route planning of distribution does not match to the actual experience because of much the current distribution schedule depends on traditional mathematical models.The paper proposes a algorithm that took realtime traffic information， driving experience and other practical factors as GIS prior knowledge to guide the intelligent distribution and carried out to achieve. Application results show that the research can improve the efficiency of logistics and distribution greatly.
Key words:intelligence distribution; genetic algorithms;prior knowledge of GIS
1 引 言
近年來，隨著物流行業的不斷發展，物流信息量迅速增加，需求的處理也越來越復雜，對配送系統的要求也越來越高，因此人們開始研究如何構建智能的物流配送系統來滿足需求。目前國內研發生產的物流配送系統大多是基于各種啟發式算法基礎構建的VRP模型，利用這些數學模型分析配送路線，結果可能會與實際經驗不完全相符，具有一定的局限性，因此應用率不高。基于此背景，在已有的導航軟件研發的經驗基礎之上，研究將行車配送過程中的現實因素如實時交通、行車經驗等信息與現有智能配送系統進行整合，建立基于GIS先驗知識的智能配送系統，提高其實用價值。
2 智能配送概述
配送是物流中一種特殊的、綜合的活動形式，集裝卸、運輸于一身，通過一系列的活動完成送貨的目的。隨著集約化、一體化的物流配送的發展，需將配送的各個環節綜合起來，配送的核心在于集貨線路優化、貨物配裝及送貨過程的優化。
智能物流配送是指在配送規劃時，運用計算機技術、圖論、運籌、統計、GIS等方面的技術，根據配送的要求，由計算機自動規劃出一個最佳的配送方案，包括物品的裝載與車輛的調度、配送路線規劃的優化等方案，旨在降低物流成本，提高客戶服務水平，減輕調度人員和司機勞動強度，滿足城市配送、電子商務、電話購物等現代城市物流配送業務的發展需要；以車輛最少、里程最少、運輸費用最低、時間最快、滿意度最高等因素為目標，把配送訂單科學地分配給可用的車輛，結合配送路線的規劃進行合理的裝載，以完成配送任務［1］。
在實際配送過程中，由于受交通路況、客戶需求、商品本身特性等條件的制約，而且各種因素又具有不確定性的特點，物流配送規劃往往是一個極其復雜的系統工程［2］。目前解決這一問題的辦法是將復雜問題分解或轉化為一個或幾個已經研究過的基本問題，如背包問題、最短路徑問題、最小費用流問題等，再采用較為成熟的理論和方法進行求解，以得到智能配送問題的最優解或滿意解。但是這種求解方法得到的最優解往往是理想狀態下的，未能考慮現實世界的不確定因素的影響，實用性較低［3］。因此文章引入了以歷史交通數據、司機行車經驗信息作為樣本的先驗知識，再結合現今較為成熟的方法求得配送的最佳路徑，最后根據規劃的路徑進行貨物的合理裝載與配送。
3 基于先驗知識的智能配送的優化策略
3.1 優化原理
要實現對貨物的智能配送，首先需將物流配送中心當日訂單的配送信息可視化到GIS電子地圖上，然后利用GIS特有的空間分析功能對客戶的位置、訂單數量及種類等進行分析，最后結合配送中心本身的位置、道路的交通狀況以及車輛的裝載能力確定配送路線。其中道路的交通狀況除了道路的通達情況之外，還應考慮道路的實時通行狀況。
當前實時交通信息的應用發展還不是很成熟，直接運用實時交通信息進行路線規劃的可行性較小，再者此時的路線規劃只是單純的通過確定配送的路線來安排貨物的裝載，往往與車輛在途的實時路線規劃存在差異。基于此，將歷史的交通路況、司機行車經驗等信息加以分析作為GIS先驗知識加以運用，結合遺傳算法進行配送路線的優化。
線路的規劃主要考慮以下幾個原則［3］：
a、 集中的原則：分布位置比較集中的客戶盡量劃分在一條線路上；
b、 線路最少的原則：在車輛運力允許的條件下，盡量用最少的線路進行配送；
c、 線路最短的原則：劃分線路時，盡量使線路最短；
d、 行車時間最短的原則：在一定的交通狀況下，保證車輛配送所花費的時間最短。
配送路線確定之后，每條路線上的客戶數量、訂單數量、配送商品的總體積、總重量、商品特殊性等信息也就決定了。根據這些參數和物流中心的車輛、人員狀況，就可以決定裝車方案。
3.2 具體的方法
智能物流配送的優化主要體現在兩個方面：一是利用遺傳算法實現智能配送車輛調度的優化；二是在GIS優化的遺傳算法的基礎上，將歷史交通路況、司機行車經驗、等信息作為經驗知識引入。
3.2.1 遺傳算法實現物流配送優化
遺傳算法是通過模擬生物的遺傳和進化過程而建立的一種自適應全局優化概率搜索算法，它通過模擬達爾文“優勝劣汰、適者生存”的原理鼓勵產生好的結構，模仿孟德爾的遺傳變異理論在算法迭代的過程中在保持原有的結構地基礎上，再去尋找更好的結構而產生的［4］。其基本思想是對一組可行解個體組成的群體進行選擇、交叉和變異等遺傳算子的運算，產生新一代群體，并逐步使群體進化到最優解的狀態。
遺傳算法的運算過程：①初始化。設置進化代數計數器t=0；設置最大進化代數T；隨機生成M個個體作為初始群體P(0)。②個體評價。計算群體P(t)中各個個體的適應度。③選擇運算。將選擇算子作用于群體。④交叉運算。將交叉算子作用于群體。⑤變異運算。將變異算子作用于群體。群體P(t)經過選擇、交叉、變異運算之后得到下一代群體P(t+1)。⑥終止條件判斷。若t≤T，則t=t+1，轉到步驟②；若t＞T，則以進化過程中所得到的具有最大適應度的個體作為最優解輸出，終止計算［5］。
利用遺傳算法進行物流配送的優化，算法的設計如下：
1） 編碼方法設計［6］：采用Crefenstette等提出的巡回路線編碼法：假設將配送問題中所有用戶所組成的列表記為W，給配送中心和每個用戶分配一個1~n之間的序號，序號的排列也記為W，即W=(t0，t1，t2…tn)。配送順序記為T，T=(t0，t1，t2，…tn)，規定每配送完一個用戶，就從W中將其刪除。
2） 遺傳算子設計
選擇算子常用的方法有輪轉法、最優保存法和期望值選擇方法，其中輪轉法以被證明不能收斂到全局最優解，而最優保存方法可以收斂到全局最優解，故在此選用最優保存法［7］。
交叉算子一般采用單點交叉、雙點交叉和均勻交叉等算子，但由于配送優化問題采用的是序號編碼方法，常規的交叉算子無法直接使用，在此首先進行常規的雙點交叉，然后通過路徑有效順序的修改來實現交叉運算［8］。
配送優化問題中個體編碼串上的各基因與配送路徑上的用戶號是對應的，各基因值互不相同，可以采用倒位變異算子，通過將個體編碼串中隨機選取的兩基因座之間的基因逆序排列，從而產生新的巡回路徑［9］。
根據遺傳算法的過程對實際問題進行分析、運算，在過程中加入先驗知識模型，求得物流配送路徑的最優解，其流程如下圖1所示：
3.2.2 先驗知識統計與分析
在地理信息系統的應用中，往往存在很多現實因素，若能對這些因素加以分析和處理，就可以在一定程度上提高處理的效率。在智能配送這一行業中，可以運用的GIS先驗知識包括道路交通、司機的行車經驗等信息。
1）道路交通信息
在目前的技術條件下，要將實時交通信息數據直接應用于智能物流配送還存在一定的困難，但是可以將已有的歷史交通信息數據進行充分的利用，將其作為先驗知識輔助決策。在使用歷史交通信息數據之前，首先對其進行統計分析，將其按照一定的準則抽象存儲于先驗知識庫中以備調用。
2） 司機經驗
雖然根據最短路徑程序算法規劃的道路都是按地理距離最短優先，已經考慮了長度、車道數、道路等級等影響因素，但由于道路存在一些客觀因素如修路、車流量等，可能與實際不符。物流配送老司機如果多年來都配送相同的幾段道路的話，對路在線的交通狀況就非常了解，根據常年累積的行車經驗選擇避開一些易擁堵路段，使得司機所選擇的路徑不一定是最短的，但是到達配送地點的時間相對較短，可以在一定程度上提高配送效率；司機在道路等級的選擇上，通常選擇城市道路網中等級較高的路段，除非該路段車流量大、行車緩慢，或者有更好的低級別的道路，這樣司機的行車路線就能在一定程度上保證了道路等級的一致性和連貫性；除此之外司機在配送過程中，如非特別需要，對于一些生僻的、路況較差的路段選擇的概率較小，而根據一般算法規劃的路徑為了追求里程最短而忽略了這一點。
因此將老司機的行車經驗信息作為一種先驗信息儲存于GIS先驗知識庫中，在進行配送優化時綜合考慮其影響，規劃的結果會更切實際，實用性更強。
為了有效的運用這些先驗信息，首先建立一個GIS先驗知識庫對其進行統一管理和調用，然后對先驗知識庫中的先驗知識進行建模，最后指導路線的規劃，先驗知識建模思路如下圖2所示。
4 應用實例
文中研究成果已在公司幾個系統中進行了運用，實驗以凱立德電子地圖數據作為基礎平臺，以湖北省某醫藥公司在武漢市的藥店藥品配送為例，隨機選取了部分門店數據和配送車輛數據進行配送規劃實驗（門店數為30車輛數為4），實驗結果如圖3所示。
3-a 為優化前系統規劃配送情況
3-b 優化后系統規劃配送情況
通過結果可以看出，系統成功地將配送中心的待配送任務進行了規劃，利用四輛車對30家門店的送貨任務進行了分配并規劃了配送路線（包括返程路線）。其中圖3-a是利用原有的系統對車輛鄂A-C1553進行配送規劃的結果，車輛的配送里程為336.371公里，圖3-b是用文中方法優化后對車輛鄂A-C1553的配送路線規劃，配送里程為317.015公里，較優化前縮短里程近20公里；加入先驗知識優化后車輛行走的路線為以省道優先，避開了路況較差的鄉道，企業按照系統規劃的路線，根據路線上客戶分布順序安排貨物的裝載方案，派出車輛鄂A-C1553進行配送。根據配送結果分析，該優化方案確定。提高了物流配送的效率。
5 總 結
文章將實時交通信息、行車經驗等信息作為先驗數據進行建模，并將其與遺傳算法結合實現，應用到智能配送的優化中來，在很大程度上解決了傳統算法規劃的配送方案與實際不相符的問題。研究的應用表明，該研究成果對于提高物流配送的效率具有指導意義，由于條件的限制，未能將物流貨物的類別對建模的影響考慮進來，這是需要進一步研究的問題。
參考文獻
［1］ 葉年發，沈海燕，馮云梅.基于RFID及智能優化的物流配送方法和技術的研究［J］.交通運輸系統工程與信息，2008，8(2):131-135.
［2］ 劉云霞，彭鴻廣，曹玉華.不確定信息的物流配送系統實時車輛優化調度策略［J］.浙江科技學院學報，2008，20(4):289-291.
［3］ 李子豪.智慧物流平臺——公路運輸管理系統的設計與實現［D］.北京:北京交通大學，2011.
［4］ 張連蓬，劉國林，江濤，等.基于先驗知識的GIS路徑尋優算法［J］.測繪科學:2003，28(3):27-29.
［5］ 陳國良，王煦法，莊鎮泉，等.遺傳算法及其應用［M］.北京:人民郵電出版社，1996.
［6］ 林娜，李志.基于GIS和遺傳算法的物流配送中心選址研究［J］.遙感信息:2010，5:110-114.
［7］ 王會云，肖建祿，劉登泰，等.基于遺傳算法的配送路線優化［J］.后勤工程學院學報:2008，24(3):91-94.
［8］ 郎茂祥，胡思繼.用混合遺傳算法求解物流配送路徑優化問題的研究［J］.中國管理科學:2002，10(5):51-56.
［9］ 曾國清.0-1背包問題的遺傳算法求解［J］.科技信息:2006，3:242-243.
收稿日期：2011-11-22
作者簡介：鄭湘麗（1965—），女，湖南湘鄉人，工程師，碩士，研究方向：GPS導航技術及計算機應用(E-mail：zhengxl@careland.com.cn)。
