實(shí)現(xiàn)物流配送路徑選擇仿真系統(tǒng)的關(guān)鍵性問題探討

馮向科　鄧瑩

摘要：該文以物流配送路徑選擇為研究內(nèi)容，通過分析實(shí)現(xiàn)仿真系統(tǒng)的關(guān)鍵性問題，提出可行性解決方法，進(jìn)行實(shí)驗(yàn)論證，提出實(shí)現(xiàn)物流配送路徑選擇仿真系統(tǒng)的方案，并在實(shí)踐中得到驗(yàn)證。

關(guān)鍵詞：物流配送路徑選擇；遺傳算法；grp矢量圖形格式；雙緩沖繪圖

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2014）36-8644-02

隨著市場(chǎng)經(jīng)濟(jì)的發(fā)展和物流技術(shù)專業(yè)化水平的提高，物流配送業(yè)得到了迅猛發(fā)展。配送路徑的選擇是否合理，對(duì)加快配送速度、提高服務(wù)質(zhì)量、降低配送成本及增加經(jīng)濟(jì)效益都有較大影響。配送路徑的優(yōu)化問題是物流配送系統(tǒng)的一個(gè)主要問題，物流配送路徑的優(yōu)化就是以最低的運(yùn)營成本、最快捷的響應(yīng)速度、最短的配送運(yùn)輸時(shí)間，把貨物運(yùn)至用戶手中，并且在三個(gè)指標(biāo)之間實(shí)現(xiàn)平衡。

在B2C農(nóng)產(chǎn)品電子商務(wù)物流配送時(shí)，物流車裝載當(dāng)日需要配送的貨品從倉庫出發(fā)，按照事先規(guī)劃好的最優(yōu)配送路徑為每一個(gè)客戶進(jìn)行配送，最后返回倉庫。在配送之前需要根據(jù)客戶的配送地址間線路間距、經(jīng)驗(yàn)路況做分析計(jì)算出一條最優(yōu)配送路徑。在配送過程中，如果某路段堵車，需要?jiǎng)討B(tài)調(diào)整配送路線。

實(shí)現(xiàn)物流配送路徑選擇仿真系統(tǒng)時(shí)，面臨如系統(tǒng)架構(gòu)、算法選擇、數(shù)據(jù)存儲(chǔ)和系統(tǒng)仿真問題等一系列技術(shù)難題，下面將逐一理清這些關(guān)鍵問題。

1 系統(tǒng)設(shè)計(jì)思想

將物流配送路徑選擇系統(tǒng)從應(yīng)用角度分為數(shù)據(jù)庫、接口服務(wù)層和客戶應(yīng)用三個(gè)層次，如圖1所示。

圖1 系統(tǒng)架構(gòu)

1） 數(shù)據(jù)庫層為整個(gè)系統(tǒng)提供數(shù)據(jù)支撐服務(wù)，它所包含的數(shù)據(jù)有配送地圖數(shù)據(jù)和行駛軌跡數(shù)據(jù)，其中配送地圖數(shù)據(jù)是支撐整個(gè)系統(tǒng)運(yùn)行的核心所在。

2） 接口服務(wù)層以接口形式為整個(gè)系統(tǒng)提供基礎(chǔ)性功能，接口服務(wù)可以和系統(tǒng)外部平臺(tái)實(shí)現(xiàn)數(shù)據(jù)共享、服務(wù)共享。

3） 客戶應(yīng)用層面向系統(tǒng)的各個(gè)終端用戶，主要為終端用戶提供配送網(wǎng)絡(luò)圖形處理和配送過程演示控制功能，以配送地圖數(shù)據(jù)為支撐，提示可視化、個(gè)性化的操作界面。

仿真系統(tǒng)擬實(shí)現(xiàn)的功能如圖2所示。

圖2 功能結(jié)構(gòu)

2 算法問題

實(shí)現(xiàn)多目的地的物流配送路徑選擇理論上可以選用枚舉法、回溯試探法等常規(guī)算法解決。采用枚舉算法時(shí)，對(duì)問題的所有可能答案一一列舉，然后根據(jù)條件判斷此答案是否合適，合適就保留，不合適就丟棄。采用回溯算法時(shí)，按照深度優(yōu)先策略，從始發(fā)地出發(fā)搜索解空間樹。算法搜索到解空間樹的任意一點(diǎn)時(shí)，先判斷該點(diǎn)是否包含問題的解。如果肯定不包含，則跳過對(duì)該結(jié)點(diǎn)為根的子樹的搜索，逐層向其祖先結(jié)點(diǎn)回溯；否則，進(jìn)入該子樹，繼續(xù)按深度優(yōu)先策略搜索。采用枚舉算法和回溯算法的時(shí)間復(fù)雜法分別為O（nn）、O（n2） ，當(dāng)n→+∞時(shí)，時(shí)間開銷不堪重負(fù)，實(shí)踐證明也是如此，在實(shí)驗(yàn)環(huán)境下，當(dāng)n>6時(shí)，得到最優(yōu)解的時(shí)間超過60秒，已經(jīng)無法達(dá)到實(shí)時(shí)處理要求。

采用遺傳算法，多次調(diào)優(yōu)，確定合適的種群規(guī)模、交叉因子和變異因子，科學(xué)計(jì)算迭代次數(shù)，確保搜索最優(yōu)（次優(yōu)）路徑所用時(shí)間較短。算法原型如下所示：

public class GA {//遺傳算法類

//判斷一個(gè)圖是否為連通圖

bool IsLinkGraph（double[，] graph）；

//獲取最短路徑

public List GetShortPath（GraphicContent content， List historyPoint， int flag）

//計(jì)算最短路徑

List GetShortPath（double[，] graph， int source， int target， List passList，List clientPoints）

//初始化種群

void InitShome（double[，] edge， int source， int target， List passPath， List clientPoints）

//計(jì)算路徑的適應(yīng)值

double GetFitness（List path， double[，] graph）

//選擇計(jì)算

void Select（double[，] graph）

//變異計(jì)算

void Change（）

//交叉計(jì)算

void Inter（）

//交叉運(yùn)算

List InterCouse（）

//計(jì)算未被包含的結(jié)點(diǎn)數(shù)目

public int IsContailsAll（List list， List subList）

//返回路徑長度

protected double GetLength（List path，double[，] edge）

}

在實(shí)驗(yàn)環(huán)境（CPU雙核2.9MHz，RAM 4GB，Windows XP，.NET Framework 2.0，DirectX 9.0）下經(jīng)過實(shí)驗(yàn)證明，當(dāng)配送地址數(shù)量≤65個(gè)時(shí)，算法所用的平均搜索時(shí)間<10.0秒；只有當(dāng)配送地址數(shù)量≥90個(gè)時(shí)，算法所用的平均搜索時(shí)間才會(huì)有顯著增加，但總體仍在可以接受的范圍之內(nèi)。

圖3 平均搜索時(shí)間

3 數(shù)據(jù)存儲(chǔ)問題

系統(tǒng)中所使用的物流配送網(wǎng)絡(luò)以圖形文件形式存儲(chǔ)，采用自定義矢量圖形格式（.grp），存儲(chǔ)內(nèi)容包括配送地址（坐標(biāo)位置、是否必須送達(dá)）、倉庫位置、各個(gè)配送地址之間的路徑信息（包括距離與行駛速度）等信息。

為防止保存在本地位置的物流配送網(wǎng)絡(luò)圖形文件被非法打開、篡改，導(dǎo)致重要信息被泄露，系統(tǒng)采用一種以異或運(yùn)算為基礎(chǔ)的對(duì)稱式加密方法，對(duì)保存的圖形文件內(nèi)容結(jié)合密鑰進(jìn)行加密，在讀取圖形文件內(nèi)容后，結(jié)合密鑰對(duì)其進(jìn)行解密。

4 系統(tǒng)仿真問題

實(shí)現(xiàn)系統(tǒng)仿真時(shí)，采用所見即所得的模型較為合適，方便用戶操作。基于.NET Framework的GDI+繪圖對(duì)象進(jìn)行圖形繪圖，為解決繪圖閃爍問題，宜采用雙緩沖技術(shù)繪圖，即按照如下步驟繪圖：①在內(nèi)存中創(chuàng)建與畫布一致的緩沖區(qū)；②在緩沖區(qū)畫圖；③將緩沖區(qū)位圖拷貝到當(dāng)前畫布上；④釋放內(nèi)存緩沖區(qū)。

為了更好地模擬汽車的行駛過程，采用圖像旋轉(zhuǎn)算法對(duì)汽車進(jìn)行旋轉(zhuǎn)，使其行進(jìn)方向始終與道路貼合平行。采用儀表盤模擬汽車的當(dāng)前行駛速度和當(dāng)前行駛距離。系統(tǒng)仿真效果如圖5所示。

圖5 系統(tǒng)仿真實(shí)現(xiàn)

5 小結(jié)

采用遺傳算法解決系統(tǒng)性能問題，采用grp自定義矢量圖形格式解決圖形數(shù)據(jù)存儲(chǔ)問題，采用雙緩沖技術(shù)解決繪圖仿真過程的圖形閃爍問題后，物流配送路徑選擇系統(tǒng)的全部關(guān)鍵問題都得以解決，仿真實(shí)現(xiàn)成為可能。以此為積累，指導(dǎo)學(xué)生參加第二屆中國大學(xué)生軟件設(shè)計(jì)大賽獲決賽優(yōu)秀獎(jiǎng)。

參考文獻(xiàn)：

[1] 王華.一種物流配送最短路徑混合算法[J].測(cè)繪科學(xué)，2013（11）.

[2] 趙若彤.一種物流配送車輛路徑智能優(yōu)化算法研究[J].計(jì)算機(jī)與數(shù)字工程，2013（4）.

[3] 張靜，衛(wèi)文學(xué)，劉倩.基于遺傳算法的物流配送路徑優(yōu)化算法[J].中國科技信息，2013（1）.

圖3 平均搜索時(shí)間

3 數(shù)據(jù)存儲(chǔ)問題

系統(tǒng)中所使用的物流配送網(wǎng)絡(luò)以圖形文件形式存儲(chǔ)，采用自定義矢量圖形格式（.grp），存儲(chǔ)內(nèi)容包括配送地址（坐標(biāo)位置、是否必須送達(dá)）、倉庫位置、各個(gè)配送地址之間的路徑信息（包括距離與行駛速度）等信息。

為防止保存在本地位置的物流配送網(wǎng)絡(luò)圖形文件被非法打開、篡改，導(dǎo)致重要信息被泄露，系統(tǒng)采用一種以異或運(yùn)算為基礎(chǔ)的對(duì)稱式加密方法，對(duì)保存的圖形文件內(nèi)容結(jié)合密鑰進(jìn)行加密，在讀取圖形文件內(nèi)容后，結(jié)合密鑰對(duì)其進(jìn)行解密。

4 系統(tǒng)仿真問題

實(shí)現(xiàn)系統(tǒng)仿真時(shí)，采用所見即所得的模型較為合適，方便用戶操作。基于.NET Framework的GDI+繪圖對(duì)象進(jìn)行圖形繪圖，為解決繪圖閃爍問題，宜采用雙緩沖技術(shù)繪圖，即按照如下步驟繪圖：①在內(nèi)存中創(chuàng)建與畫布一致的緩沖區(qū)；②在緩沖區(qū)畫圖；③將緩沖區(qū)位圖拷貝到當(dāng)前畫布上；④釋放內(nèi)存緩沖區(qū)。

為了更好地模擬汽車的行駛過程，采用圖像旋轉(zhuǎn)算法對(duì)汽車進(jìn)行旋轉(zhuǎn)，使其行進(jìn)方向始終與道路貼合平行。采用儀表盤模擬汽車的當(dāng)前行駛速度和當(dāng)前行駛距離。系統(tǒng)仿真效果如圖5所示。

圖5 系統(tǒng)仿真實(shí)現(xiàn)

5 小結(jié)

采用遺傳算法解決系統(tǒng)性能問題，采用grp自定義矢量圖形格式解決圖形數(shù)據(jù)存儲(chǔ)問題，采用雙緩沖技術(shù)解決繪圖仿真過程的圖形閃爍問題后，物流配送路徑選擇系統(tǒng)的全部關(guān)鍵問題都得以解決，仿真實(shí)現(xiàn)成為可能。以此為積累，指導(dǎo)學(xué)生參加第二屆中國大學(xué)生軟件設(shè)計(jì)大賽獲決賽優(yōu)秀獎(jiǎng)。

參考文獻(xiàn)：

[1] 王華.一種物流配送最短路徑混合算法[J].測(cè)繪科學(xué)，2013（11）.

[2] 趙若彤.一種物流配送車輛路徑智能優(yōu)化算法研究[J].計(jì)算機(jī)與數(shù)字工程，2013（4）.

[3] 張靜，衛(wèi)文學(xué)，劉倩.基于遺傳算法的物流配送路徑優(yōu)化算法[J].中國科技信息，2013（1）.

圖3 平均搜索時(shí)間

3 數(shù)據(jù)存儲(chǔ)問題

系統(tǒng)中所使用的物流配送網(wǎng)絡(luò)以圖形文件形式存儲(chǔ)，采用自定義矢量圖形格式（.grp），存儲(chǔ)內(nèi)容包括配送地址（坐標(biāo)位置、是否必須送達(dá)）、倉庫位置、各個(gè)配送地址之間的路徑信息（包括距離與行駛速度）等信息。

為防止保存在本地位置的物流配送網(wǎng)絡(luò)圖形文件被非法打開、篡改，導(dǎo)致重要信息被泄露，系統(tǒng)采用一種以異或運(yùn)算為基礎(chǔ)的對(duì)稱式加密方法，對(duì)保存的圖形文件內(nèi)容結(jié)合密鑰進(jìn)行加密，在讀取圖形文件內(nèi)容后，結(jié)合密鑰對(duì)其進(jìn)行解密。

4 系統(tǒng)仿真問題

實(shí)現(xiàn)系統(tǒng)仿真時(shí)，采用所見即所得的模型較為合適，方便用戶操作?；?NET Framework的GDI+繪圖對(duì)象進(jìn)行圖形繪圖，為解決繪圖閃爍問題，宜采用雙緩沖技術(shù)繪圖，即按照如下步驟繪圖：①在內(nèi)存中創(chuàng)建與畫布一致的緩沖區(qū)；②在緩沖區(qū)畫圖；③將緩沖區(qū)位圖拷貝到當(dāng)前畫布上；④釋放內(nèi)存緩沖區(qū)。

為了更好地模擬汽車的行駛過程，采用圖像旋轉(zhuǎn)算法對(duì)汽車進(jìn)行旋轉(zhuǎn)，使其行進(jìn)方向始終與道路貼合平行。采用儀表盤模擬汽車的當(dāng)前行駛速度和當(dāng)前行駛距離。系統(tǒng)仿真效果如圖5所示。

圖5 系統(tǒng)仿真實(shí)現(xiàn)

5 小結(jié)

采用遺傳算法解決系統(tǒng)性能問題，采用grp自定義矢量圖形格式解決圖形數(shù)據(jù)存儲(chǔ)問題，采用雙緩沖技術(shù)解決繪圖仿真過程的圖形閃爍問題后，物流配送路徑選擇系統(tǒng)的全部關(guān)鍵問題都得以解決，仿真實(shí)現(xiàn)成為可能。以此為積累，指導(dǎo)學(xué)生參加第二屆中國大學(xué)生軟件設(shè)計(jì)大賽獲決賽優(yōu)秀獎(jiǎng)。

參考文獻(xiàn)：

[1] 王華.一種物流配送最短路徑混合算法[J].測(cè)繪科學(xué)，2013（11）.

[2] 趙若彤.一種物流配送車輛路徑智能優(yōu)化算法研究[J].計(jì)算機(jī)與數(shù)字工程，2013（4）.

[3] 張靜，衛(wèi)文學(xué)，劉倩.基于遺傳算法的物流配送路徑優(yōu)化算法[J].中國科技信息，2013（1）.