摘 要：作為企業(yè)的“第三利潤源泉”，物流日益受到企業(yè)的關注。但物流運輸成本過高，日漸成為制約我國物流業(yè)發(fā)展的主要瓶頸。文中對國內外前沿成果進行分析和歸納的基礎上，介紹了主要的SDVRP求解算法，并針對不足提出了新的求解途徑。

關鍵詞：需求可拆分車輛路徑問題；精確算法；啟發(fā)式算法

一、引言

伴隨著全球經濟一體化，社會分工日趨細化，配送功能從企業(yè)中外包出來。在我國，第三方物流作為一個新興產業(yè)，于20世紀80年代后期開始快速發(fā)展。但由于起步較晚，物流運作水平與發(fā)達國家相比仍存在較大差距，其中最突出的問題就是物流成本高。國家發(fā)改委、國家統(tǒng)計局和中國物流與采購聯(lián)合會聯(lián)合發(fā)布的2012年統(tǒng)計數(shù)據(jù)顯示[1]，全國社會物流總費用為9.4萬億元，占GDP的比重為18%，而同期新加坡、美國等發(fā)達國家物流總費用占GDP比重僅為8%-10%。運輸成本是物流成本的重要組成部分，2011年與2012年的全國物流運行統(tǒng)計數(shù)據(jù)顯示，全國社會物流總費用中運輸成本分別為4.4萬億元與4.9萬億元，占社會物流總費用的比重分別為52.8%與52.5%，以上數(shù)據(jù)顯示，我國運輸成本占物流總費用比例高，且增長較快，因此降低運輸成本，無疑是提高運輸質量與效率，促進物流產業(yè)發(fā)展的重要途徑。

配送中心是物流配送網絡的樞紐，是企業(yè)實施供應鏈管理的重要設施之一。配送中心接受并處理末端用戶的訂貨信息，根據(jù)客戶的需求進行配送。其主要任務是處理不確定環(huán)境下的訂單整合（Order Consolidation，OC）和車輛路徑問題（Vehicle Routing Problem，VRP）。VRP是物流配送優(yōu)化的核心環(huán)節(jié)，配送路線的規(guī)劃合理與否都將對配送成本、時間和效率產生較大的影響，特別是在有著多客戶需求且其路徑規(guī)劃比較復雜的情況下，如何確定合理的配送路線，是配送規(guī)劃過程中一項非常重要的工作。

二、SDVRP的常用求解算法

SDVRP是傳統(tǒng)VRP的一個較新分支。自從SDVRP被提出后，對其求解算法的研究一直是研究的重點和難點。Archetti et al. （2005）指出[2]，當Q=2時，具備整數(shù)需求的SDVRP可以在多項式時間里得到相對滿意的解；當Q>2時，SDVRP則成為一個NP-hard問題。而在Archetti et al. （2010）的研究里[2]，通過對特定圖中VRP和SDVRP的計算復雜度進行研究，其結果表明，在某些特定的圖中，SDVRP的計算復雜度不會難于VRP。目前，關于SDVRP的主要求解算法主要分為精確算法和啟發(fā)式算法兩大類：

（一） 精確算法

精確算法可以求得問題的最優(yōu)解，但是，其計算時間會隨問題規(guī)模的擴大呈指數(shù)增長，因此，精確算法只適用于求解小規(guī)模問題。第一種精確算法由Dror et al. （1994）于1994年提出[2]，在其研究中，他們提出了一個集合新的有效不等式類的弧流列方程式，其實驗結果證明不等式在求解下界上得到顯著改善，在大多數(shù)的算例中，對上下界差值的改善超過30%。Desaulniers （2010）設計了一種分支定價法優(yōu)化帶時間窗的SDVRPTW的運輸成本[2]。當需求確定且顧客數(shù)目小于100時，該優(yōu)化方法表現(xiàn)優(yōu)異。Gulczynski et al. （2010）研究了帶最小運輸量約束的SDVRP[2]，并建立了一個混合整數(shù)規(guī)劃模型優(yōu)化該問題的運輸成本。Hertz et al. （2012）對有一個擁有不同車型的車隊和很多倉庫[4]，并且顧客需求量大于車載容量的水泥運輸問題進行了研究。在他們的論文中，他們提出了一個兩階段整數(shù)線性規(guī)劃模型解決這種SDVRP。

（二） 啟發(fā)式算法

當問題規(guī)模較大，利用精確算法無法在有效時間內求得最優(yōu)解時，通常釆用啟發(fā)式算法求取“近優(yōu)解”或“滿意解”。Dror Trudeau （1989，1990）提出了第一個基于局部搜索的啟發(fā)式算法[2]。Archetti et al. （2006）提出了一種禁忌搜索算法[2]，實驗證明雖然計算速度相對較慢，但此算法在計算效率上明顯優(yōu)于Dror Trudeau提出的基于局部搜索的啟發(fā)式算法。Boudia et al.（2007）在遺傳算法的基礎上提出了一種文化基因算法[2]，該算法對局部搜索過程進行強化，并整合距離策略以控制群體的多樣性。通過與Archetti et al. （2006）的算例集進行對比測試[3]，發(fā)現(xiàn)禁忌搜索算法在某些算例上其計算結果優(yōu)于Archetti et al. （2006）提出禁忌搜索算法。除此以外，為了規(guī)避單一算法計算速度慢或者計算效率過低的問題，Chen et al. （2007）、Archetti et al. （2008）和Jin et al. （2008）提出了三種不同的混合啟發(fā)式算法[2]，其中前兩種算法的實驗結果與Archetti et al. （2006）相比在很多的算例上，都得到了不同程度的改進。而Jin et al. （2008）相對割平面法在Belenguer et al. （2000）所測試的12個算例中的6個中，都能夠求得更好的上下界。[2]

三、結論

通過對SDVRP的常用算法進行總結和歸納，我們發(fā)現(xiàn)SDVRP的復雜性決定了利用精確算法和傳統(tǒng)的啟發(fā)式算法很難得到滿意的解，精確算法可以得到相對精確地最優(yōu)解，但是運算效率較低；啟發(fā)式算法運行時間較短，很容易陷入局部最優(yōu)，或者出現(xiàn)無法收斂的現(xiàn)象。但隨著計算機硬件和軟件的進步，現(xiàn)代啟發(fā)式算法的運行效率得到很大的改善。從文獻檢索的結果看，目前，已經有學者開始采用以現(xiàn)代啟發(fā)式優(yōu)化算法為核心，結合系統(tǒng)仿真的方法對SDVRP問題進行建模與優(yōu)化。隨著全球供應鏈管理觀念的流行，物流管理的水平日益成為衡量一個國家綜合能力的重要指標，對SDVRP問題進行研究不僅可以很大程度上減少國內物流運輸成本過高的現(xiàn)狀，而且具有很高的經濟意義。

參考文獻

[1]國家發(fā)展改革委，國家統(tǒng)計局，中國物流與采購聯(lián)合會.2012年全國物流運行情況通報[R].http：//www.chinawuliu.com.cn/lhhkx/201302/26/210410.shtml

[2]Archetti， C.， M. G. Speranza. Vehicle routing problems with split deliveries. International Transactions in Operational Research. 19（2012）：3-22

[3]Archetti， C.， Hertz， A.， Speranza， M.G. A tabu search algorithm for the split delivery vehicle routing problem. Transportation Science ， 2006（40）： 64–73.

[4]Hertz， A.， M. Uldry， and M. Widmer. Integer linear programming models for a cement delivery problem. European Journal of Operational Research 2012（222）： 623–631.