□李響

我國儲備糧運(yùn)輸線路問題分析與求解

□李響

儲備糧；運(yùn)輸線路；靜態(tài)運(yùn)輸；動態(tài)運(yùn)輸；動態(tài)信息

儲備糧不僅關(guān)系到國家的糧食安全問題，而且是我國社會、經(jīng)濟(jì)和諧穩(wěn)定發(fā)展的重要基礎(chǔ)和保障。儲備糧運(yùn)輸線路問題是儲備糧物流的重要組成部分，情況比較特殊，限制條件較多，筆者對我國儲備糧運(yùn)輸線路問題進(jìn)行分析，以求得最佳運(yùn)輸線路。

一、儲備糧運(yùn)輸線路選擇現(xiàn)狀

我國目前實(shí)行“三三制”進(jìn)行儲備糧輪換管理，其中三分之一儲備糧可考慮實(shí)行年度總量控制，在保質(zhì)保量的前提下，儲備糧存儲企業(yè)可結(jié)合現(xiàn)貨市場輪換交易部分儲備糧，吐陳納新。這一部分儲備糧可以允許適當(dāng)架空輪換，輪換對應(yīng)的架空期往往低于4個月，儲備糧企業(yè)需要在短時期內(nèi)按照國家與地方政府的要求完成新糧的采購入庫。輪換的陳糧主要是銷往大中型糧食加工企業(yè)。因此，如何在短時間內(nèi)快速地完成陳糧的配送工作顯得尤其重要。

陳糧的配送主要由儲備糧企業(yè)負(fù)責(zé)運(yùn)輸，長距離的跨區(qū)運(yùn)輸主要通過鐵路或水路方式進(jìn)行，短距離的區(qū)域內(nèi)運(yùn)輸主要通過公路運(yùn)輸方式完成。長期以來，陳糧輪換的運(yùn)輸線路問題一直受到多方關(guān)注，運(yùn)輸方式較多，而且運(yùn)輸途中一些信息也在不斷發(fā)生動態(tài)變化，在此，筆者僅對儲備糧的公路運(yùn)輸線路問題進(jìn)行研究。

二、儲備糧運(yùn)輸線路問題分析

運(yùn)輸線路問題（VRP）的目標(biāo)函數(shù)主要分為單目標(biāo)和多目標(biāo)，常用目標(biāo)函數(shù)為配送運(yùn)輸總行程、運(yùn)輸總耗時及運(yùn)輸數(shù)量等。約束條件一般包括單車最大行程、多車型、多配送中心、配送運(yùn)輸終點(diǎn)非配送中心、時間約束、裝卸自動化等。因此，基于經(jīng)典運(yùn)輸線路問題選擇不同的目標(biāo)函數(shù)與約束條件，會得到不同的運(yùn)輸線路問題，這也是靜態(tài)運(yùn)輸線路問題的主要分類方式。

儲備糧公路運(yùn)輸中存在載量約束，屬于經(jīng)典運(yùn)輸線路問題（CVRP）。在CVRP的基礎(chǔ)上，考慮儲備糧公路運(yùn)輸中會出現(xiàn)各種不同類型的動態(tài)配送信息，比如，出現(xiàn)新的接受陳糧加工廠、老的加工廠取消運(yùn)糧、天氣變化、交通中斷或者運(yùn)糧車輛拋錨等情況，因此，筆者研究的運(yùn)輸路線問題屬于動態(tài)運(yùn)輸路線問題類型（D-CVRP）。由于研究的問題具有“數(shù)量大”和“動態(tài)”等屬性特征，比較復(fù)雜，因此需要在滿足所有糧食加工廠的需求前提下結(jié)合實(shí)時新信息不斷調(diào)度配送運(yùn)輸，目標(biāo)是使糧食運(yùn)輸行駛總里程最短。

三、儲備糧運(yùn)輸線路問題轉(zhuǎn)換

儲備糧靜態(tài)運(yùn)輸線路問題是在運(yùn)輸開始前對已知的所有運(yùn)輸信息（運(yùn)輸過程中不會出現(xiàn)新變化）進(jìn)行求解，得出運(yùn)糧方案；動態(tài)運(yùn)輸路線問題是在目前已知的運(yùn)糧信息下求解得到運(yùn)糧方案，在執(zhí)行過程中會不斷出現(xiàn)變動的送糧信息，要求不斷地考慮新信息變化而產(chǎn)生的新的運(yùn)糧方案。比如，在各個時間點(diǎn)會出現(xiàn)多次新信息，那么全過程需要求解多次（如圖1所示）。因此，運(yùn)糧的動態(tài)運(yùn)輸線路問題與靜態(tài)運(yùn)輸線路問題相比，要求在運(yùn)糧過程中對動態(tài)信息（事件）的時刻點(diǎn)分別做出優(yōu)化決策，產(chǎn)生新的運(yùn)糧方案。

圖1 靜態(tài)運(yùn)輸路線與動態(tài)運(yùn)輸路線問題方案比較

綜上所述，若在公路運(yùn)輸陳糧過程中出現(xiàn)動態(tài)信息（事件）的D-CVRP問題，需要分解為多個CVRP類型問題進(jìn)行求解。

四、儲備糧運(yùn)輸線路問題求解

求解D-CVRP模型，特別是動態(tài)信息（事件）較多的大數(shù)量的運(yùn)糧D-CVRP數(shù)模難度比較大，最大的難點(diǎn)在于在運(yùn)糧過程中會不斷出現(xiàn)新的信息，會發(fā)生動態(tài)事件。當(dāng)前的算法大部分都是基于靜態(tài)VRP模型開發(fā)得到，靜態(tài)VRP配送前知道所有的運(yùn)糧信息，運(yùn)輸前的算法有充足的時間，能保證算法的求解質(zhì)量，但算法的求解速度和復(fù)雜度卻不夠理想，這就對求解的算法速度提出了較高要求。

求解D-CVRP模型的算法盡管由靜態(tài)VRP模型算法修改得到，為滿足算法高速度的要求，需要控制D-CVRP中糧食加工廠的數(shù)量規(guī)模，同時局部調(diào)整即時運(yùn)糧方案來應(yīng)對突發(fā)動態(tài)信息（事件）。局部調(diào)整方案以動態(tài)應(yīng)對的典型方法是干擾管理方法。即將發(fā)生的動態(tài)事件看成干擾事件，然后通過局部調(diào)整當(dāng)前方案達(dá)到處理動態(tài)事件的目的，其目標(biāo)是以處理動態(tài)事件為前提，使當(dāng)前配送方案的擾動程度最小。該思路的優(yōu)點(diǎn)是可以盡量減少當(dāng)前配送計劃的變動，從而降低算法的速度需求；缺點(diǎn)是考慮的信息不夠全面，僅適合求解動態(tài)程度較低的動態(tài)運(yùn)輸線路問題，當(dāng)用于求解高動態(tài)的運(yùn)輸路徑問題時所產(chǎn)生的方案質(zhì)量會不夠理想。

求解D-CVRP的思路是將D-CVRP問題看成是由多個CVRP構(gòu)成，即出現(xiàn)一次動態(tài)信息（事件）后，將已知運(yùn)糧信息更新后得到一個新CVRP問題。開發(fā)一個快速算法，每次動態(tài)信息（事件）出現(xiàn)后從全局的角度合并新信息重新優(yōu)化得到新的運(yùn)糧方案。該思路的優(yōu)點(diǎn)是每次動態(tài)信息（事件）的處理均從全局考慮所有信息，缺點(diǎn)是由于要連續(xù)求解多個（約100次以上）CVRP問題，同時糧食輪換公路運(yùn)輸周期遠(yuǎn)低于架空期（略小于4個月），有時兩個動態(tài)事件發(fā)生的時間間隙非常小，所以算法需在短時間內(nèi)求解動態(tài)數(shù)量在100次以上的CVRP問題，算法速度要求較高。該D-CVRP的求解流程圖如圖2所示。

本文求解D-CVRP的思路與現(xiàn)有的干擾管理方法有較大的區(qū)別，具體見表1所列。

表1 求解D-CVRP思路與干擾管理方法的區(qū)別

圖2 D-CVRP求解流程圖

結(jié)合海特卡普模型與k維二叉樹法分別對儲備糧動態(tài)運(yùn)輸路線問題的貪婪算法進(jìn)行求解質(zhì)量與速度的改進(jìn)，改進(jìn)貪婪算法的流程圖如圖3所示。

圖3 求解儲備糧動態(tài)運(yùn)輸路線問題的改進(jìn)貪婪算法流程圖

改進(jìn)貪婪算法求解儲備糧運(yùn)輸路線問題效果明顯。選擇蟻群算法、貪婪算法、求解該算例與改進(jìn)貪婪算法對比，求解質(zhì)量與耗時有區(qū)別，按照圖3改進(jìn)的貪婪算法的求解質(zhì)量最高，求解耗時有一定的優(yōu)勢。經(jīng)過算例證明運(yùn)用改進(jìn)貪婪算法研究我國儲備糧的運(yùn)輸路線問題可行，有一定的理論價值。

（作者單位：武漢理工大學(xué)交通學(xué)院）

10.3963/j.issn.1006-8864.2014.11.021