物流配送車輛優(yōu)化調度問題的探討

[摘 要]隨著經濟的不斷發(fā)展，城市正發(fā)生著日新月異的變化。城市的發(fā)展離不開大量貨車的使用，所以如何解決物流配送車輛優(yōu)化調度的問題就逐步成為城市建設發(fā)展的焦點。物流配送車輛優(yōu)化調度的問題，即對固定的裝（卸）貨地點，選擇較為適當的行車路線讓車輛井然有序的從各個路點通過，并且在按照要求完成任務的情況下還起到了一定的優(yōu)化作用。本文從物流配送的概述和流程開始深入，針對物流配送車輛優(yōu)化調度問題的分類和優(yōu)化算法方面做了詳細的介紹，還進一步的分析了國內外在物流配送車輛優(yōu)化調度問題上的研究現(xiàn)狀以及以后的發(fā)展方向。

[關鍵詞]物流配送；分類；車輛調度；優(yōu)化算法

[中圖分類號]U115 [文獻標識碼]A [文章編號]1005-6432（2012）45-0074-02

1 物流配送概述及其流程

1.1 物流配送的基本概述

將目標貨物從發(fā)貨人送至收貨人的過程被稱為配送。由于配送最終的目標是收貨人，即為消費者，因此，配送也是物流系統(tǒng)中的一個至關重要的步驟。配送不僅僅局限于配貨和送貨。滿足客戶的需求，配送需要在滿足客戶對貨物種類數量的基礎上，在保證按時送達客戶的基礎上選取更快，更節(jié)約成本的配送方案，實現(xiàn)利益最大化。

1.2 物流配送系統(tǒng)的優(yōu)化

為找到一個最佳的物流配送方案，應該從以下幾個方面著手：配送車輛的調度，對集貨線路的選取，對送貨路線的選擇，實現(xiàn)集貨—送貨相統(tǒng)一。對配送系統(tǒng)的優(yōu)化不僅可以增加物流的經濟效益，更有助于實現(xiàn)科學化、現(xiàn)代化物流管理，顯著提升物流的服務質量，提高物流公司信譽，從而有效地降低物流成本。

1.3 物流配送的流程

隨著物流配送的發(fā)展，現(xiàn)代物流配送水平的提高，貨物流通性大大增強，傳統(tǒng)的存儲環(huán)節(jié)作用正逐漸式微，也使得配送環(huán)節(jié)取代存儲環(huán)節(jié)成為物流中最重要的部分。而作為配送的核心配送車輛對貨物的集貨、配送和送貨過程越來越被重視，如何選取最優(yōu)配送路線，是對整個物流質量的考驗，關系著物流整體的運輸速度、服務成本和經濟效益。隨著電子商務的崛起，以集貨作業(yè)和配貨作業(yè)為主體的新物流模式已然形成。

2 車輛優(yōu)化調度問題的分類和優(yōu)化算法

2.1 車輛優(yōu)化調度問題的分類

根據不同的性質，可將車輛優(yōu)化調度問題分成不同的類型。

按照運輸任務可將車輛優(yōu)化調度問題分為三類，即純裝、純卸、裝卸混合三類問題。

按照車輛的載貨情況可將車輛優(yōu)化調度問題分為兩類，即滿載、非滿載問題。滿載是指貨量大于車載量，需要多輛車運輸。非滿載是指車載量大于貨量，一輛車就能完成任務。

按照車輛類型可將車輛優(yōu)化調度問題分為兩類，即單車型、多車型問題。

按照車輛是否返回可將車輛優(yōu)化調度問題分為兩類，即車輛開放（車輛不返回）、車輛封閉（車輛返回）問題。

按照優(yōu)化的目標可將車輛優(yōu)化調度問題分為兩類，即單目標、多目標問題。

按照有無休息時間可將車輛優(yōu)化調度問題分為兩類，即有休息時間調度、無休息時間調度問題。

2.2 車輛優(yōu)化調度問題的優(yōu)化算法

2.2.1 精確算法

精確算法又稱最優(yōu)化算法，是指求出最佳解的算法。其算法有很多，比如切割平面法、網絡流算法等。

精確算法有一個弊端，就是其計算量隨著需要解決的問題規(guī)模的增大而大幅度的增大。由于這個弊端，精確算法只能適合解決規(guī)模較小的問題。因為精確算法適應能力較差，一般這種算法最適合解決一個特定的問題，所以在實際應用中這種算法不是很受提倡。

2.2.2 啟發(fā)式算法

啟發(fā)式算法完全不同于精確算法，它追求的是解決問題的滿意性而不是最優(yōu)性。它是一種用直觀、經驗構造出來的算法。到目前為止，啟發(fā)式算法已經有好多種，最主要是以下兩種算法。

構造啟發(fā)式算法，其實質就是按照標準將不在同一條線路的所有點逐個的增加進來。在算法的每一步上，都要將當前的線路構型和另外的線路構型比較后，綜合改進得到最后可行的構型。這類算法的代表算法是：最鄰近法、掃描法、節(jié)約法等。

智能化啟發(fā)式算法就是在人工智能的啟發(fā)式算法的基礎上發(fā)展的。它的主要算法有：蟻群算法、神經網絡算法等。

啟發(fā)式算法在解決大規(guī)模的PDPTW問題上分為經典啟發(fā)式算法和現(xiàn)代啟發(fā)式算法。

經典啟發(fā)式算法主要有路徑構造算法和路徑改造算法等。路徑構造算法其實質就是分解算法，就是將一個問題分為兩個階段（路由和排序）來解決。路徑改造算法是在路徑構造算法上改進的，其第一個階段就是找到一個可行解，下一階段就是調整客戶端，在滿足可行的條件下，對路徑進行調整，使其比當前路徑更加優(yōu)化，一直按照這樣優(yōu)化下去，直到不能優(yōu)化為止。

現(xiàn)代啟發(fā)式算法中，最主要的就是禁忌搜索算法和模擬退火算法。

禁忌搜索算法是禁忌搜索算法的一種變形，是現(xiàn)代局部搜索技術的一種。其實質是近期被多次循環(huán)搜索過的算法被禁用。它的優(yōu)點是減少需要考慮的移動次數，最終達到減少計算時間的目的。改進階段和混合階段是禁忌搜索算法的主要步驟，一個是得到最優(yōu)解，另一個是跳出最優(yōu)解。

模擬退火算法。其算法具體過程是：在隨機產生的可行解，每次循環(huán)時都隨機挑選出一個好的和一個較差的可行解，這樣就避免陷入局部最優(yōu)解里。這個算法的弊端就是執(zhí)行起來速度較慢。基于這個弊端提出了好幾類優(yōu)化后的算法，這些算法在實際應用中都很有效果。

2.3 動態(tài)求解算法

動態(tài)車輛調度問題相對前兩種比較其問題的規(guī)模較大解決起來相對比較困難些。并且這種算法的要求是在短時間內就要相應其實時信息。從求解策略上把動態(tài)求解算法分為重新優(yōu)化策略和局域優(yōu)化策略。

2.3.1 重新優(yōu)化策略

重新優(yōu)化策略就是當接收到一個新的實時信息時，要重新開始尋找始發(fā)到結束的最優(yōu)車輛的行車路徑。實質就是靜態(tài)方法解決動態(tài)問題。研究運送大宗商品的車輛調度問題就是一個較為成功的運用重新優(yōu)化策略的例子。還有在動態(tài)單車問題上，采用了乘子調整技術的靜態(tài)算法。其算法過程是：當有新實時信息時，就采用動態(tài)重新優(yōu)化法解決，可是這種算法最多能解決十種問題。

重新優(yōu)化策略的缺點是每次接到新的實時信息時都要重新優(yōu)化設計，這樣下去當接收的實時信息較多時，其計算量是較大的。當遇到需要迅速解決的問題時，根本沒有時間去進行重新優(yōu)化，所以這種算法在實際運用上是不可實現(xiàn)的。

2.3.2 局域優(yōu)化策略

局域優(yōu)化策略的實質是：提前擬定一些路徑的模板，當收到實時信息時，就在提前擬定的模板里進行搜索，找個適合的路徑進行使用。這種策略和重新優(yōu)化策略相比較，路徑可能是較差的，但是計算量是大大的減少了，從而節(jié)約了許多的時間。局域優(yōu)化策略在實際的車輛調度上比較適用，所以受到重視和近一步的研究。再后來提出的插入法較為適用，改進后的插入法其具體實現(xiàn)方法是：當接收到新的實時信息時，不直接進行優(yōu)化調度，而是等待以后的需求，這樣就可以降低它的短視行為。還可以把插入法和優(yōu)化算法結合起來使用，在對路徑優(yōu)化以后再獲得更好的解。

3 車輛優(yōu)化調度問題的研究現(xiàn)狀

物流配送車輛優(yōu)化調度問題在國外的應用要比國內發(fā)展迅速。其發(fā)展已經涉及各個領域，不論是工業(yè)材料的運輸、網購的貨運配送和運輸、連鎖店的貨物發(fā)送等這樣的大型車輛調度方面，還是報紙、牛奶投遞等這樣的小調度方面對于線路優(yōu)化的運用都會取得較為理想的經濟效益。最典型的例子就是全球聞名的沃爾瑪特公司，它們就是運用了最先進的物流配送指揮系統(tǒng)所以才會在同行中遙遙領先。隨著對物流配送車輛優(yōu)化調度問題的深入研究，物流配送車輛優(yōu)化調度不僅在汽車領域發(fā)展，現(xiàn)在還應用在了航空、輪船方面。在不久的將來，相信其發(fā)展領域會更加廣闊。

在我國境內，車輛調度問題的發(fā)展比國外晚發(fā)展近乎三十年，所以現(xiàn)在我國對于較為復雜的車輛調度路徑問題研究還是相對落后。由于我國對這方面研究起步較晚，對于通用理論研究不夠深入，再加上我國對于應用研究的問題提出雖多但是都是在具體算法上的改進，并沒有創(chuàng)新，所以我國在車輛優(yōu)化調度的問題上根本無法滿足配送業(yè)和物流業(yè)的發(fā)展需求。隨著物流業(yè)在市場上的地位日益重要。為了克服我國在車輛優(yōu)化調度上局限性較強的弱點，我國逐漸開始對車輛優(yōu)化調度問題進行深入的研究并且現(xiàn)在已經取得初步的成功。

4 結 論

隨著物流業(yè)和配送業(yè)在市場上的發(fā)展需求逐步擴大，車輛優(yōu)化調度問題日益重要。國外在車輛優(yōu)化調度問題上發(fā)展較快，已經在生產和生活方面廣泛應用并且得到了很好的經濟效益?？墒俏覈谲囕v優(yōu)化調度問題上的發(fā)展起步較晚，發(fā)展速度相對較慢，不能滿足我國經濟發(fā)展的需求。所以為了使我國國民經濟發(fā)展迅速、人們生活質量提高，就要在物流配送業(yè)上大力研究發(fā)展車輛優(yōu)化調度問題。其主要研究方向就是：根據車輛優(yōu)化調度的分類標準，以及各類問題上的特點應該按照何種算法進行優(yōu)化；在基本算法的基礎上針對特點問題如何改進；在不同地理環(huán)境和運輸特點的基礎上結合車輛優(yōu)化調度問題上的優(yōu)化算法，設計出更加適用的優(yōu)良算法。按照這個方向研究發(fā)展，車輛優(yōu)化調度的問題在現(xiàn)實生活中的意義會更加重要。

參考文獻：

[1]郎茂祥.配送車輛優(yōu)化調度模型與算法[M].北京：電子工業(yè)出版社，2009.

[2]馮輝宗，劉飛.基于遺傳算法的配送車輛優(yōu)化調度[J].計算機集成制造系統(tǒng)，2004（12）：34-37.

[3]張之富，余靜.基于改進遺傳算法的車輛優(yōu)化調度研究[J].中國水運，2009（4）：113-115.

[4]方金城，張岐山.物流配送車輛路徑問題（VRP）算法綜述[J].沈陽工程學院學報，2006（10）：67-69.

[作者簡介]楊菲（1978—），漢族，山東省膠南市人，就職于勝利油田物資供應處招標辦公室，經濟師。研究方向：物流、供應。