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

□李響

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

□李響

儲備糧；運輸線路；靜態運輸；動態運輸；動態信息

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

一、儲備糧運輸線路選擇現狀

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

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

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

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

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

三、儲備糧運輸線路問題轉換

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

圖1 靜態運輸路線與動態運輸路線問題方案比較

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

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

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

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

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

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

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

圖2 D-CVRP求解流程圖

結合海特卡普模型與k維二叉樹法分別對儲備糧動態運輸路線問題的貪婪算法進行求解質量與速度的改進，改進貪婪算法的流程圖如圖3所示。

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

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

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

10.3963/j.issn.1006-8864.2014.11.021