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

□李響

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

□李響

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖2 D-CVRP求解流程圖

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

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

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

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

10.3963/j.issn.1006-8864.2014.11.021