物流配送車輛調度問題算法綜述

陳君蘭， 葉春明 （上海理工大學 管理學院，上海 200062）

CHEN Jun-lan, YE Chun-ming (Manage School,University of Shanghai for Science and Technology,Shanghai 200062,China)

配送是物流中的一個環(huán)節(jié)，一般的配送包括裝卸、包裝、保管、運輸，其目的就是將貨物成功送達。而特殊的配送以加工活動為支撐，包括更廣泛的方面。配送過程中有兩個重要環(huán)節(jié)，一個是運輸，另一個是分揀配貨，分揀配貨就是根據(jù)特殊的要求，將貨物根據(jù)送貨時間、送貨地點等具體要求，將貨物送達。所以分揀是配送的獨特要求，而運輸則是最后實現(xiàn)配送的主要手段。隨著物流體系的發(fā)展，人們常將配送的各個環(huán)節(jié)綜合起來考慮，而核心部分就是配送的車輛、貨物裝卸及送貨。因而配送車輛優(yōu)化調度就成為人們關注的焦點，其中包括集貨線路優(yōu)化、貨物配裝及送貨線路優(yōu)化，以及集貨、貨物配裝和送貨一體化優(yōu)化等等。

無論是對于物流中心，還是第三方物流公司，物流配送運輸車輛的調度都是工作重點，通過減少運輸成本、節(jié)約運輸時間，從而提高經濟效益。

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

車輛路徑調度問題的一般定義為：對一系列發(fā)貨點和收貨點，組織適當?shù)男熊嚶肪€，使車輛有序通過它們，在滿足一定的約束條件下 （如貨物需求量、車載量、交發(fā)貨時間、行車里程、時間限制，路線約束等），達到一定目標最優(yōu)化 （如路程最小、運費最少、時間準時、車輛較少等）。

1.1 按時間因素分類

配送車輛調度優(yōu)化問題可以簡單地分為三類，第一類問題稱為車輛路徑規(guī)劃問題 （Vehicle Routing Problems，VRP），VRP問題關注為車輛安排合理、高效益的線路，僅是在空間上對問題進行優(yōu)化，而不考慮時間因素。第二類問題稱為車輛調度問題 （Vehicle Scheduling Problems，VSP），VSP問題也關注合理、高效安排車輛行車路線，所不同的是，VSP問題考慮的是在滿足時間要求的前提下實現(xiàn)最優(yōu)調度。第三類問題稱為路徑和調度的混合問題 （Vehicle Routing And Scheduling Problems，VRP&VSP），就是將前兩類問題綜合考慮的問題。而目前也有學者不區(qū)分VRP和VSP問題，而是將考慮時間因素的VSP問題稱為VRPTW （Vehicle Routing Problem with Time Windows）問題。

1.2 按性質分類

車輛優(yōu)化調度問題可以根據(jù)其不同的性質分為以下幾類：

（1）按運輸任務可以分為純裝問題、純卸問題和裝卸混合問題。純裝問題就是每一項任務只有裝貨點，是一個集貨的過程。純卸問題是指每一項任務只有卸貨點，是一個送貨的過程。而裝卸混合問題是指每一項任務有不同的裝貨點和卸貨點，是集貨、送貨一體化的過程。

（2）按車輛載貨情況可以分為滿載問題和非滿載問題。滿載問題是指一次任務的貨運量多于車輛的最大容量，而非滿載問題是指一次任務的貨運量不多于車輛的最大容量。

（3）按車輛類型分為單車型問題和多車型問題。單車型問題指所有車輛的容量都給定同一值，多車型問題指所有車輛的容量都給定不同值。

（4）按車場的數(shù)量可以分多車場和單車場問題。因為多車場問題可以轉化為單車場問題，而且通常一個車場 （倉庫）都會有固定的服務對象。根據(jù)傳統(tǒng)的處理方法，在將多車場問題轉化為單車場問題的過程中，先設一個虛擬車場，將所有配送點和實際車場都看作虛擬車場的配送點，這樣就轉化為單車場問題了。所以這里的算法只考慮單車場問題。

（5）按車輛是否返回車場可以分為車輛開放問題和車輛封閉問題。車輛開放問題是指在車輛開出車場以后不返回車場。而車輛封閉問題是指在車輛開出車場以后返回其發(fā)出車場。

（6）按優(yōu)化目標可以分為單目標優(yōu)化問題和多目標優(yōu)化問題。單目標優(yōu)化問題是指目標函數(shù)只要求一項指標最優(yōu)，如要求運輸路徑最短。多目標優(yōu)化問題是指目標函數(shù)要求多項指標最優(yōu)或較優(yōu)，如同時要求運輸費用最少和運輸路徑最短。

（7）按貨物種類可分為同種貨物優(yōu)化調度和多種貨物優(yōu)化調度。同種貨物優(yōu)化調度是指要運輸?shù)呢浳锏姆N類只有一種。多種貨物優(yōu)化調度是指要運輸?shù)呢浳锏姆N類多于一種，所以車輛裝載時要考慮一些種類的貨物不能同時裝配運輸。

（8）按有無休息時間要求可分為有休息時間的優(yōu)化調度問題和無休息時間優(yōu)化的調度問題。

（9）按有需求點有無時間窗要求，可分為無時間窗問題、硬時間窗問題、軟時間窗問題。硬時間窗問題指車輛必須在時間窗內到達，早到則等待，晚到則拒收。軟時間窗問題指車輛不一定要在時間窗內到達，但是在時間窗外到達必須受到懲罰。

建立車輛調度問題模型如下：

目標函數(shù)：a.單目標，b.多目標 （目標函數(shù)包括總費用最小、總里程最小、休息時間最大、懲罰最少等）

約束條件：a.時間約束 （無時間窗、硬時間窗、軟時間窗）

b.距離約束 （無距離限制、硬距離限制、軟距離限制）

c.行車路線約束 （無相交性限制、頂點不相交）

d.流量限制 （無流量限制、邊限制、頂點限制）

e.滿載限制 （滿載，非滿載）

f.其它要求

2 物流配送車輛調度算法綜述

在求解車輛優(yōu)化調度問題時，可以將問題歸類為幾個簡單的組合優(yōu)化基本原型，如旅行商問題（TSP）、最短路徑問題、最小費用流問題、中國郵遞員問題等，再用相關的理論和方法進行求解，得到模型最優(yōu)解或較優(yōu)解。

一般求解VRP問題主要可分兩大類，一類是精確算法；一類是啟發(fā)式算法。精確算法主要有分支定界法、割平面法、線性規(guī)劃法、動態(tài)規(guī)劃法等，它的主要思想是根據(jù)問題先建立具體的數(shù)學模型，然后利用數(shù)學方法進行求解。啟發(fā)式算法主要有構造法、人工智能法等，如構造算法、兩階段法、神經網絡法、遺傳算法等，它的主要思想是根據(jù)直觀和經驗開發(fā)出能朝著最優(yōu)解方向搜索或靠近的算法。

由于車輛優(yōu)化調度問題的規(guī)模大、復雜性強，而各種計算和實驗得出，智能算法在求解這類問題時有較強的可行性，所以這里僅探討智能算法求解車輛優(yōu)化調度問題。

2.1 遺傳算法

遺傳算法 （Genetic Algorithm，GA）由美國J.Holland和他的學生于1975年建立并發(fā)展起來的。遺傳算法是根據(jù)自然選擇和遺傳理論，將生物進化過程中適者生存規(guī)則與同一群染色體的隨機信息交換相結合的智能算法。遺傳算法的基本思想是：首先，通過一組編碼，將問題在表現(xiàn)型與基因型之間轉換，并形成初始種群，計算種群中個體的適應度；其次，設計遺傳算子 （包括復制、交叉、變異），從對已產生的解 （“父代”）中根據(jù)交叉率，從部分個體中選取部分基因，按某種組合形成新的個體；根據(jù)變異率，從部分個體中選取部分基本變異，產生新的個體；同時將 “父代”中適應度高的個體進行復制，成為新一代個體，不斷操作、迭代，以形成新的一組解 （“子代”），計算個體適應度。如此反復，可求出整個種群的最優(yōu)解。

遺傳算法具有良好的全局搜索能力，可以快速求出全局最優(yōu)解，但存在過早收斂和搜索效率低、局部搜索能力低的缺點，導致算法比較費時。目前，許多遺傳算法在車輛調度問題中應用的研究都通過對編碼、遺傳算子的設計、基因構建和定義、適應度定義等方面來改進算法效能，如李軍[1]等設計最大保留交叉來保證群體的多樣性求解非滿載車輛調度問題等；也有許多學者通過在遺傳算法中引入其它算法來增加其局部搜索能力，如張濤[2]等用3-OPT算法結合遺傳算法來加強算法的局部搜索能力，得到針對車輛調度優(yōu)化問題的混合算法等，而隨著模型變化，車輛調度優(yōu)化問題的求解算法也會有所改變，如Giselher[3]等利用GA算法對裝卸混合問題進行了研究。可見，遺傳算法正從多方面影響著車輛調度問題。

2.2 模擬退火算法

模擬退火算法 （Simulated Annealing，SA）由Kirkpatrick等人于1983年成功引入組合優(yōu)化領域。模擬退火法是源于材料科學和物理領域的一種搜索過程。模擬退火算法的基本思想是：首先，任意選擇一個初始狀態(tài)，并設定初始溫度和降溫次數(shù)，并在鄰域中產生另一個解，根據(jù)控制參數(shù)t選擇接受和舍棄，經過大量操作后，求得給定t時優(yōu)化問題的相對最優(yōu)解；其次，通過降溫函數(shù)，不斷減小t的值直到0時的最后系統(tǒng)狀態(tài)對應優(yōu)化問題的全局最優(yōu)解。前半部分是通過加熱增加物體能量；后半部分是通過降溫和冷卻降低物體的能量。對應數(shù)學模式時，問題的解就是系統(tǒng)狀態(tài)，而問題的目標函數(shù)就是物體的能量，因此求最優(yōu)解的過程就是求能量最低態(tài)的過程。

模擬退火算法的優(yōu)點是有很強的全局搜索能力，但是由于允許移動到較差的解，所以可能接受目標值不好的狀態(tài)，從而使算法陷入局部最優(yōu)，所以要求出最優(yōu)解要花費較長時間。而模擬退火的有效性取決于鄰域選擇設計，如果鄰域以一種促進移到更好解而移出局部極小解的方式設計，那么算法將會表現(xiàn)出其優(yōu)越性。謝秉磊[4]等用模擬退火算法求解配送/收集旅行商問題；蔡延光[5]等用模擬退火算法求解多重運輸調度問題等。由于模擬退火算法一個顯著缺點就是收斂速度慢，因此在求解車輛優(yōu)化調度問題時，多將模擬退火算法與其它智能算法結合，加快收斂速度。

2.3 禁忌搜索算法

禁忌搜索算法 （Tabu Search，TS）由Glover在1986年提出。禁忌搜索算法是用一個禁忌表記錄已經到達過的局部最優(yōu)解，確保在下一次搜索過程中，不再選擇這些點，從而跳出局部最優(yōu)解。禁忌算法的基本思想是：首先，從一個初始可行解s開始，確定解的搜索鄰域N（）s，在這個鄰域內選出最優(yōu)解s'，則從s移到s'繼續(xù)搜索；其次，設定禁忌表最大容量，將每次的移動根據(jù)先進先出準則放入禁忌表中，在每次迭代中，表中的移動是可能被禁止的，這都取決于一個渴望水平函數(shù)，這個函數(shù)用來評價移動的損益，如果損益是可以接受的，則移動不被禁止，反之，移動被禁止；最后，根據(jù)迭代停止準則，求出問題的最優(yōu)解。

從上面的算法描述中可以看出，禁忌搜索算法的主要缺點是對初始解的依賴性很強，當遇到不好的初始解時，將會導致計算時間過長。而且禁忌表最大容量的設定對禁忌搜索算法來說也起著很重要的作用，因為如果容量過多，將會導致搜索被過分限制，造成時間浪費；而容量過少，會造成循環(huán)，不利于求解。由于禁忌搜索算法只能對一個解進行操作。鐘石泉[6]等在求解多車場車輛調度問題時，以一組初始解的鄰域作為搜索空間，突破點點操作，減少禁忌搜索算法對初始解好壞的依賴；并且采用局部、全局兩種禁忌表來避免重復操作。但總體來說，禁忌算法比較容易與其它啟發(fā)式算法相結合構建混合算法。結合之前介紹的兩個算法，可以看出，遺傳算法在每次迭代中都會生成很多不同的調度，而且會延續(xù)到下一次迭代，而在模擬退火法和禁忌搜索法中，只有一個調度從一次迭代延續(xù)到下一次迭代。

2.4 蟻群算法

蟻群算法 （Ant Colony Algorithm，ACA）由意大利學者M.Dorigo及其導師Colorni于1991年提出并用于求解TSP問題，它是根據(jù)自然界中螞蟻覓食行為而提出的一種優(yōu)化算法。蟻群通過尋找信息素濃度最高的路徑，從而求出最佳路徑。蟻群算法的基本思想是：首先，初始化各螞蟻，將m只螞蟻放在n個頂點上，并設定初始參數(shù)，并將初始解置于當前解集中；其次，每只螞蟻根據(jù)選擇策略和轉移概率選擇頂點，并將該頂點置于當前解集中，則螞蟻從初始點轉移，不斷操作，直到所有的點都已置于解集中，則求出各螞蟻的適應度，記錄當前最優(yōu)解；通過更新信息素，不斷迭代，直到結束條件滿足，求出種群進化后的最優(yōu)解，也就是問題的最優(yōu)解。

蟻群算法的優(yōu)點是其正反饋機制和分步式計算。但對于規(guī)模較大的問題，其搜索時間長且易收斂至局部最優(yōu)解。目前，蟻群算法收斂性方面的理論成果則非常稀少。馬良[7]等通過在蟻群算法的基礎上嵌入2-OPT等算法加速其循環(huán)最優(yōu)解的得出來求解帶容量限制的多目標車輛路徑問題；陳金[8]等結合sweep和saving算法確定客戶歸屬的混合算法求解帶時間窗的中轉聯(lián)盟運輸調度問題。而蔡延光[9]等人也提出調整選擇策略、信息素濃度與揮發(fā)速度的同向關系調節(jié)信息素更新方程的方法改進傳統(tǒng)蟻群算法求解帶軟時間窗的聯(lián)盟運輸調度問題。許多學者在求解車輛優(yōu)化調度問題時都對蟻群算法作了多種改進，這些改進都具有很強的意義。

2.5 微粒群算法

微粒群算法 （Particles Swarm Optimization，PSO）由美國心理學家Kennedy[10]和電氣工程師Eberhart于1995年提出。微粒群算法起源于鳥類在搜索食物過程中，個體之間可以進行信息的交流和共享，每個成員可以得益于所有其他成員的發(fā)現(xiàn)和飛行經歷[11]。微粒群算法的基本思想是：首先，產生一組初始解，得到初始位置并初始化速度、個體最優(yōu)解、全局最優(yōu)解；然后，通過位置更新方程和速度更新方程產生一組新的解，并更新個體最優(yōu)解和全局最優(yōu)解；如此不斷操作迭代，粒子漸漸向最優(yōu)解靠近，直至到達循環(huán)結束條件，此時得到問題最優(yōu)解。

微粒群算法有通用性強，具有記憶能力，保留個體和全局最優(yōu)信息，協(xié)同搜索的優(yōu)點。但微粒群算法局部搜索能力較差，通過多點同時搜索，使運算時間大大減少，但也造成了計算精度較差的特點，所以要設置迭代次數(shù)較多，此外算法對參數(shù)設置具有很強的依賴性。現(xiàn)在對微粒群算法的應用研究很多，朱露露[12]等采用量子算法與微粒群算法相結合的混合算法，通過采用一種二進制的編碼方式求解了經典的車輛路徑問題。因此在處理車輛優(yōu)化調度問題時，也可以將其它算法的思想引入到微粒群算法中，從而克服其易陷入局部最優(yōu)的缺點。

3 對未來研究方向的展望

車輛優(yōu)化調度問題一直是配送運輸領域關注的熱點，諸多學者都對其進行了不少研究，也取得了不少成果。在對該問題的算法研究雖然種類很多，但實現(xiàn)起來都存在不少問題。根據(jù)學者們現(xiàn)有的研究發(fā)現(xiàn)，目前對算法的改進主要表現(xiàn)在以下幾個方面：其一，通過混合算法的方式，結合各算法優(yōu)點，彌補各算法缺點，形成一條可行的方案；其二，根據(jù)對自然界的不斷探索以及結合交叉學科的方式，提出新的算法；其三，改進現(xiàn)有算法，就現(xiàn)有算法中各步驟中的細節(jié)進行調整。諸如此類的研究還在進行中，因此研究車輛優(yōu)化調度問題是有潛力、有意義的。

[1] 李軍，謝秉磊，郭耀煌.非滿載車輛調度問題的遺傳算法[J].系統(tǒng)工程理論方法應用，2000,9(3):235-239.

[2] 張濤，王夢光.遺傳算法和3-OPT結合求解帶能力約束的VRP[J].東北大學學報，1999,20(3):253-256.

[3] Giselher,Pankratz.A grouping genetic algorithm for the pickup and delivery problem with time windows[J].Operation Research,2005(27):21-41.

[4] 謝秉磊，李良，郭耀煌.求解配送/收集旅行商問題的模擬退火算法[J].系統(tǒng)工程理論方法應用，2000,11(3):40-43.

[5] 蔡延光，錢積新，孫優(yōu)賢.多重運輸調度問題的模擬退火算法[J].系統(tǒng)工程理論與實踐，1998,18(10):11-15.

[6] 鐘石泉，賀國光.多車場車輛調度智能優(yōu)化研究[J].華東交通大學學報，2004,21(6):25-29.

[7] 馬良，朱剛，寧愛兵.蟻群優(yōu)化算法[M].北京：科學出版社，2008.

[8] 陳金，蔡延光.帶時間窗的中轉聯(lián)盟運輸調度問題的混合算法研究[J].工業(yè)控制計算機，2010,23(1):70-72.

[9] 蔡延光，師凱.帶軟時間窗的聯(lián)盟運輸調度問題研究[J].計算機集成制造系統(tǒng)，2006,12(11):1903-1908.

[10] Kennedy J,Eberhart R.Particle Swarm Optimization[C]//Proc.IEEE Int.Conf.on Neural Networks.Perth,WA,Australia:[s.n.],1995:1942-1948.

[11] 王凌，劉波.微粒群優(yōu)化與調度算法[M].北京：清華大學出版社，2008.

[12] 朱露露，葉春明，何洋林.基于量子微粒群算法的車輛路徑問題研究[J].物流科技，2008(5):12-14.

[13] 閆彥，張立麗，楊文雄.物流配送車輛優(yōu)化調度方法初探[J].水運科學研究，2005,3(1):37-41.

[14] 師凱，蔡延光.聯(lián)盟運輸調度問題模型結構與算法研究[J].計算機技術與發(fā)展，2007,17(1):56-59.

[15] 潘凌，葉如意.規(guī)模車輛調度問題的有效算法分析[J].寧波大紅鷹職業(yè)技術學院學報，2006,9(3):48-52.

[16] 李芳，鄭晴，邱俊茹,等.帶時間窗的某物流配送車輛調度問題的方案優(yōu)化分析[J].數(shù)學的實踐與認識，2010,40(17):176-181.

[17] 管顯筍.基于微粒群優(yōu)化算法的車間調度問題研究[D].秦皇島：燕山大學 （碩士學位論文），2010.

[18] Fukuyama Y.Fundamentals of particle swarm techniques[C]//Lee K Y,El-Sharkawi M A.Modern Heuristic Optimization Techniques with Applications to Power Systems[s.l.]:IEEE Power Engineering Society,2002:45-51.

[19] （美）Pinedo M.調度：原理、算法和系統(tǒng)[M].2版.北京：清華大學出版社，2007.