□李響

我國儲備糧運輸線路問題分析與求解

□李響

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

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

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

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

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

二、儲備糧運輸線路問題分析

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

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

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

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

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

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

四、儲備糧運輸線路問題求解

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

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

求解D-CVRP的思路是將D-CVRP問題看成是由多個CVRP構(gòu)成，即出現(xiàn)一次動態(tài)信息（事件）后，將已知運糧信息更新后得到一個新CVRP問題。開發(fā)一個快速算法，每次動態(tài)信息（事件）出現(xiàn)后從全局的角度合并新信息重新優(yōu)化得到新的運糧方案。該思路的優(yōu)點是每次動態(tài)信息（事件）的處理均從全局考慮所有信息，缺點是由于要連續(xù)求解多個（約100次以上）CVRP問題，同時糧食輪換公路運輸周期遠低于架空期（略小于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)運輸路線問題的貪婪算法進行求解質(zhì)量與速度的改進，改進貪婪算法的流程圖如圖3所示。

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

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

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

10.3963/j.issn.1006-8864.2014.11.021