隨機車輛路徑問題研究探討

熊沂鋮，王 杏，李金龍，秦 芃

（西安航空學(xué)院，陜西 西安 710077）

隨機車輛路徑問題研究探討

熊沂鋮，王 杏，李金龍，秦 芃

（西安航空學(xué)院，陜西 西安 710077）

文章闡述了隨機車輛路徑的起源、特性已經(jīng)發(fā)展的狀況，對發(fā)展過程中遇到的問題進行歸納總結(jié)，指出了研究該問題國內(nèi)外的進展，介紹了運用算法的低效率以及使用時的限制，提出了對算話的改進措施以及運用實際解決問題的思路和建議。

隨機車輛路徑問題；組合優(yōu)化；算法

車輛路徑問題（Vehicle routing problem，VRP）在現(xiàn)實生活中有著巨大的經(jīng)濟意義。自從學(xué)者從1959年提出有關(guān)車輛路徑的問題開始，后續(xù)的學(xué)者對其研究也就成了熱門的話題。在研究過程中需要經(jīng)常研究一個問題就是：對于商品或服務(wù)提供商提出的要求，運用車輛將貨物運送到分布相對分散的某個區(qū)域到顧客手中，規(guī)定路經(jīng)顧客只能一次，如何來制定行車的路線以及車輛的多少，來使得運輸成本最低。VRP問題的研究分兩個方向：動態(tài)與靜態(tài)，文章主要研究的是動態(tài)問題中的SVRP，并對其研究取得的成果進行歸納，為后續(xù)學(xué)者提供借鑒。

1 SVRP的概念和特征

（1）概念。對SVRP的研究如今最火熱的要數(shù)如下這些運輸問題：需要運送貨物給顧客，但是顧客的具體要求每天不同，并以顧客為中心呈現(xiàn)隨機分布的現(xiàn)象，由于時間相對倉促和自愿分配的不合理，在信息不全的情況下需要制定出配送方案。舉一個現(xiàn)實生活中的例子：銀行運鈔車對分布在市內(nèi)的各個銀行進行取款的操作，中國郵政對各個市縣收取包裹的服務(wù)等都屬于隨機車輛路徑問題。

（2）特征。SVRP經(jīng)過多年的發(fā)展對比與傳統(tǒng)的VRP存在很多方面的轉(zhuǎn)變，其區(qū)別在于：①目標(biāo)函數(shù)。對VRP來說，對時間的把握以及資源的分配都有清晰的了解，目標(biāo)函數(shù)的確定相對簡單，需要考慮的問題只是如何使得運輸路線最短、成本最低等問題。而對于SVRP，在已有信息的基礎(chǔ)之上還得考慮是否會有其他新的信息，所以此時的目標(biāo)函數(shù)是由各種分段函數(shù)構(gòu)成，在構(gòu)建的過程中相對麻煩。②解的特征。VRP中所有的因素都已經(jīng)固定不變，沒有考慮周圍環(huán)境的改變，其解的針對范圍有限。對于SVRP來說，由于對路徑的選取和對信息的重視，其解最大的現(xiàn)實意義也更準(zhǔn)確。③問題的求解過程。VRP和SVRP的求解過程都?xì)w屬于排列與組合的問題，從中找到最優(yōu)解。

2 SVRP的發(fā)展與現(xiàn)狀

（1）國外研究現(xiàn)狀。國外對求解SVRP的算法有很多，整體的思路還是以既定的信息為基礎(chǔ)。該方法的開展分為兩個步驟：在得到信息不準(zhǔn)確的情況下制定好序列的順序；在獲取準(zhǔn)確信息的前提下制定策略。兩個步驟的選取的原則基于兩點：第一步驟的成本與第二階段的期望值。對先驗序列的分類主要是兩種，一種考慮約束條件在內(nèi)，另一種是把可能性因素考慮進去。約束條件的主要思想是保持穩(wěn)定，把錯誤率控制在一定的范圍，并且對服務(wù)不成功而帶來的二次成本忽略不計。可能性因素主要說的是：把第二階段的期望值以及服務(wù)不成功帶來的二次成本降到最低的情況下，對第一個步驟的行車路線加以制定。后一種分類求解相對復(fù)雜，但是其針對的目標(biāo)函數(shù)的實際結(jié)果很有意義。

（2）國內(nèi)的研究現(xiàn)狀。對于我國來說，SVRP的發(fā)展才剛剛起步。主要的研究方法是將隨機問題通過加權(quán)處理之后來作為目標(biāo)函數(shù)，并由此引申出了神經(jīng)網(wǎng)絡(luò)的求解方法。運用此方法的核心思想是把運輸路線的所有服務(wù)

點依次通過某種關(guān)系映射到神經(jīng)網(wǎng)絡(luò)系統(tǒng)中來反應(yīng)神經(jīng)元的情況，當(dāng)網(wǎng)絡(luò)狀態(tài)收縮時，神經(jīng)元的各種因素也就固定不變，如果能夠找到符合這種排列規(guī)律的算法要求，那么也就找到解決SVRP問題的最佳方案。

3 目前算法的局限性

上文提到的各種算法都有各自的側(cè)重點也各有特色，但是使用的條件有一定的限制。主要是因為：①有些算法要想達到可以使用的情況需要有一定的經(jīng)驗并對算法進行化簡，在求解最解的過程中往往找不到正確的方法需要重新計算。而如果服務(wù)的區(qū)域相對較大，服務(wù)點數(shù)量增多，需要運算，浪費太多的時間，效率得不到提升。對于構(gòu)造出來的收斂函數(shù)需要在算法經(jīng)過加權(quán)之后并用一定的約束得到的，而這些加權(quán)涉及到的因素相對復(fù)雜，只能通過慢慢的測試才能得到，在算法實際運用當(dāng)中很難見到成效，就像之前說到的神經(jīng)網(wǎng)絡(luò)解法。②有些算法需要提前給出初始解，造成麻煩的同時也很難找到最優(yōu)路徑的解法。就拿模擬退火算法來說，先是通過整體找到算法的思路，在逐步找尋最優(yōu)解的兩個步驟，顯然這種算法很費時，如果只采用第一個步驟又不能很好的反映整體特征。

4 結(jié)語

文章研究的SVRP對國內(nèi)外的學(xué)者來說都開始進入起步，還有許多重大的項目與問題留待進一步的商榷和探索。主要體現(xiàn)在：①研究的現(xiàn)象主要集中在VRPSD，對于復(fù)雜的動態(tài)隨機性的問題研究不是很多。而日常經(jīng)常能碰到的問題大多都屬于不確定VRP，確定性VRP都是通過不確定VRP簡化得到的。現(xiàn)如今對SVRP的研究水平只能對小區(qū)域的隨機車輛路徑問題加以解答，對于較大區(qū)域的效果不是很好。要想解決大區(qū)域的SVRP問題，運用的主要方法還是通過計算機的大型運算功能，更加有效率的算法暫時還沒有研究出來。所以需要把領(lǐng)域的概念引用進來，根據(jù)領(lǐng)域的不同特征結(jié)合算法從而找到最優(yōu)解。②啟發(fā)式算法的研究需要進一步的加強，來到達設(shè)計并解決問題的目標(biāo)。啟發(fā)式的運用在現(xiàn)實生活中相對簡單，無法應(yīng)對在動態(tài)因素改變的情況下對調(diào)度的控制作用，所以需要研發(fā)更加快捷的運算方法。如果通過人工的手段對SVRP進行運算，耗費的時間相對較長，在引入計算機的前提下，編輯智能化的軟件將數(shù)據(jù)進行調(diào)試，放低對精度的精確才能有效將運算的速度加以提升，此種做好具有現(xiàn)實意義。若是轉(zhuǎn)向?qū)?fù)雜性的挖掘，也能從另一個方面提升響應(yīng)速度的靈敏性。③加深對開路式VRP的研究。相比于傳統(tǒng)VRP算法中車輛需要重回起始點進行運輸，開路式極大的縮短了運輸?shù)穆烦?。該方法運用的原理是將物流系統(tǒng)中的存儲地點進行集中式管理，而且在最近幾年開始逐步發(fā)展，也取得了一定的成果。由于該種方法的高效性，閉環(huán)式VRP可以將此優(yōu)點進行結(jié)合，發(fā)展成一種更加便捷的途徑。④如何把取得的項目進展成果轉(zhuǎn)化到實際的運用當(dāng)中，更好的為交通運輸?shù)陌l(fā)展和社會的便利貢獻出一份力量也是需要探討的問題。

Exploration on Stochastic Vehicle Routing Problem

XIONG Yi-cheng，WANG Xing，LI Jin-long，QIN Peng
（Xi'an Aviation College，Xi'an，Shaanxi 710077，China）

This paper expounds the origin and characteristics of stochastic vehicle routing and summarizes the problems encountered in the development，points out the research progress both at home and abroad，and introduces low efficiency of the algorithm and constraints，and puts forward improvement measures of calculating words and ideas and suggestions of solving the problems.

stochastic vehicle routing problem；combinatorial optimization；algorithm

U491

A

2095-980X（2016）10-0071-02

2016-09-13

熊沂鋮（1988-），男，陜西勉縣人，碩士研究生，助教，主要研究方向：發(fā)動機工作原理。