陳嘉楠 楊松 劉士廣 侯一萌 應(yīng)博智

南京農(nóng)業(yè)大學(xué)工學(xué)院 210031

基于路網(wǎng)配送路線優(yōu)化教學(xué)軟件開發(fā)

陳嘉楠 楊松 劉士廣 侯一萌 應(yīng)博智

南京農(nóng)業(yè)大學(xué)工學(xué)院 210031

當(dāng)前，國外對于VRP問題的研究已經(jīng)應(yīng)用于生產(chǎn)，生活等多個領(lǐng)域。但是，VRP問題的研究，盡管擺在了高校的課本中，但是在教學(xué)演示方面遇到很大的問題，無法向?qū)W生形象生動的演示算法過程。為了提高教學(xué)質(zhì)量，解決教學(xué)演示的相關(guān)難題，本項目設(shè)計了教學(xué)軟件系統(tǒng)，達到了對該問題的分步演示及可視化, 改善了教學(xué)方法，并初步應(yīng)用到了校內(nèi)的教學(xué)演示，取得了良好的效果。

隨機路網(wǎng)；VRP；節(jié)約算法；教學(xué)軟件

1 研究背景

當(dāng)前，現(xiàn)代物流已被公認(rèn)為是企業(yè)在降低物質(zhì)消耗，提高勞動生產(chǎn)率以外創(chuàng)造利潤的第三個重要源泉，也是企業(yè)降低生產(chǎn)經(jīng)營成本，提高產(chǎn)品市場競爭力的重要途徑，而發(fā)展現(xiàn)代物流則需要一批高素質(zhì)的物流專業(yè)人才隊伍。高校本著與時代接軌的目的，紛紛開設(shè)物流相關(guān)專業(yè)，用以滿足社會對物流人才的需求。

但目前，各高校對配送車輛路線優(yōu)化問題的教學(xué)，僅僅流于刻板的理論教學(xué)的形式上，教學(xué)模式陳舊，局限于從有限的課本上獲取物流方面的知識，未能直觀的反映車輛路線問題的模型，造成專業(yè)人才的稀缺。正是基于這樣的物流教學(xué)現(xiàn)狀，我們利用了計算機軟件Visual Basic，將VRP領(lǐng)域的算法進行分類比較，并最終選取了啟發(fā)式算法中的節(jié)約算法，并將其算法步驟編程，開發(fā)出應(yīng)用VRP模型教學(xué)的軟件，具有重要的實際意義與現(xiàn)實意義。

2 軟件的功能分析

制作軟件的標(biāo)準(zhǔn)，以便于教學(xué)，直觀反映問題為目標(biāo)。為此，我們詳細(xì)地調(diào)研分析了VRP問題在實際教學(xué)過程中所遇到的各種問題，并以此作為軟件功能設(shè)計思路。

軟件分為三大功能:

2.1 整體演示功能

此功能的想法初衷，是為了讓使用者對VRP問題有個較為清晰的認(rèn)識，軟件界面的設(shè)計采用了選擇菜單的多窗體，以盡可能的體現(xiàn)軟件的強大功能為目的，加以操作軟件的演示，形象直觀的反映軟件的功能與作用。

2.2 分步演示功能

作為軟件設(shè)計的核心，分步演示功能是基于教學(xué)的應(yīng)用考慮，將解決VRP問題的具體過程，體現(xiàn)在了軟件的應(yīng)用功能當(dāng)中。在隨機路網(wǎng)的生成的基礎(chǔ)上，以隨機節(jié)點數(shù)為20，客戶數(shù)目為10，車輛載重量為4，為例，具體的軟件的計算過程圖為:

第一步:輸出路權(quán)矩陣表。

第二步:輸出最短距離矩陣。

第三步:輸出節(jié)約矩陣。

第四步:用節(jié)約算法求配送路徑的輸出計算結(jié)果生成過程。

第五步:輸出最終配送路徑結(jié)果。

2.3 隨機練習(xí)功能

在做完演示功能等作用之后，軟件還考慮到學(xué)生的自學(xué)等因素，添加了隨機練習(xí)功能。本作品避免了傳統(tǒng)軟件的冗雜的輸入數(shù)據(jù)，采用隨機數(shù)組，即:隨機路網(wǎng)，隨機需求量，默認(rèn)配送中心等，并將得到的隨機數(shù)據(jù)輸出，方便了題目的設(shè)計，靈活多變，并根據(jù)做題過程的中間數(shù)據(jù)，完成自我的檢測，給自我學(xué)習(xí)能力得到不小的提升。

3 軟件開發(fā)的關(guān)鍵技術(shù)問題

隨機配送路線網(wǎng)絡(luò)圖的生成，其核心思想在于將界面中的隨機點，以連接最近點為原則，呈十字形連接，這樣克服了以往隨即連線會生成新節(jié)點，從而導(dǎo)致確定路權(quán)矩陣難的問題。

傳統(tǒng)的隨機路網(wǎng)同本作品的軟件作圖直觀比較:

由此，可以直觀地看到，傳統(tǒng)的隨機路網(wǎng)并沒有解決隨機連線的新節(jié)點所帶來的路權(quán)矩陣混亂問題，由此說明，我們隨機路網(wǎng)的科學(xué)性與突破性。

4 創(chuàng)新特色以及應(yīng)用前景

4.1 創(chuàng)新特色

在基本車輛路線問題（VRP）的基礎(chǔ)上，本作品將其延伸和作以相應(yīng)的優(yōu)化。具體體現(xiàn)在:隨機需求車輛路線問題（vehicle routing problem with stochastic demand，VRPSD），在生成隨機路網(wǎng)的前提下，本作品還加以極具創(chuàng)新的隨機客戶端，隨機客戶端需求量等。

本作品中隨機路網(wǎng)的生成是先隨機產(chǎn)生點，然后連接相鄰幾條不相交的線，克服了以往隨機連線生成許多新節(jié)點，導(dǎo)致確定路權(quán)矩陣難的問題；采用Floyd算法計算最短路徑；節(jié)約算法計算配送路徑，保證軟件計算的科學(xué)性與創(chuàng)新性。

本作品開發(fā)了圖形化界面，增強了直觀性，比單純的數(shù)字講解更易理解。能隨機產(chǎn)生例題，克服例題少不好學(xué)的情況；能隨機生產(chǎn)練習(xí)題，強化對問題的理解；能求解多車輛的VRP問題，比僅有單車輛TSP問題更接近實際。

4.2 應(yīng)用前景

該作品作為輔助教學(xué)類軟件，將提高教學(xué)質(zhì)量作為軟件開發(fā)的宗旨，更加貼切學(xué)生自主動手能力解決身邊問題的教育思想。軟件的需求說明書以及后期顯著的實踐教學(xué)，都充分說明了其廣泛的應(yīng)用前景，一經(jīng)推廣，必然會掀起一股高校的物流教學(xué)熱，也是由于其讓學(xué)生更加明晰理論知識，讓教師授課更加生動形象。

該作品的使用范圍為現(xiàn)階段高校的物流教學(xué)相關(guān)的人群，將作品實物化，軟件化，推廣具有可行性，推廣應(yīng)用前景深遠(yuǎn)，有著良好的市場前景與經(jīng)濟效益。

[1] 張強，荊剛.車輛路線問題研究現(xiàn)狀及發(fā)展方向.交通科技,2004，60-150

[2] 張學(xué)志,陳功玉.車輛路線安排的改進節(jié)約算法.系統(tǒng)工程, 2008.11

[3] 郎茂祥.配送車輛優(yōu)化調(diào)度模型與算法.電子工業(yè)出版社,2009.3

[4] 聶艷芳.VRP的數(shù)學(xué)模型及算法分析.山西電子技術(shù),2010.1

[5] Laporte G, GendreauM, Potvin J Y.Classical andMod2ern Heuristics for the Vehicle Routing Proble J ].IntlTrans in Oper Res, 2000, 7 (4 /5) : 285 - 300.

10.3969/j.issn.1001-8972.2012.13.046