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

陳嘉楠 楊松 劉士廣 侯一萌 應博智

南京農業(yè)大學工學院 210031

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

陳嘉楠 楊松 劉士廣 侯一萌 應博智

南京農業(yè)大學工學院 210031

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

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

1 研究背景

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

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

2 軟件的功能分析

制作軟件的標準，以便于教學，直觀反映問題為目標。為此，我們詳細地調研分析了VRP問題在實際教學過程中所遇到的各種問題，并以此作為軟件功能設計思路。

軟件分為三大功能:

2.1 整體演示功能

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

2.2 分步演示功能

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

第一步:輸出路權矩陣表。

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

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

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

第五步:輸出最終配送路徑結果。

2.3 隨機練習功能

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

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

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

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

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

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

4.1 創(chuàng)新特色

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

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

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

4.2 應用前景

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

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

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

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

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

[4] 聶艷芳.VRP的數(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