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

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

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

[中圖分類號]U115 [文獻(xiàn)標(biāo)識碼]A [文章編號]1005-6432（2012）45-0074-02

1 物流配送概述及其流程

1.1 物流配送的基本概述

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

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

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

1.3 物流配送的流程

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

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

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

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

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

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

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

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

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

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

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

2.2.1 精確算法

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

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

2.2.2 啟發(fā)式算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié) 論

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

參考文獻(xiàn)：

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

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

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

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

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