車輛調(diào)度算法研究及其應(yīng)用文獻綜述

車輛調(diào)度算法研究及其應(yīng)用文獻綜述文獻綜述車輛調(diào)度算法研究及其應(yīng)用前言部分車輛調(diào)度問題是現(xiàn)代物流系統(tǒng)優(yōu)化中關(guān)鍵的一環(huán)，也是開展電子商務(wù)不可缺少的內(nèi)容。對車輛調(diào)度優(yōu)化理論與算法進行系統(tǒng)研究是構(gòu)建綜合物流系統(tǒng)、建立現(xiàn)代調(diào)度指揮系統(tǒng)、發(fā)展智能交通運輸系統(tǒng)和開展電子商務(wù)的基礎(chǔ)[1]。車輛調(diào)度問題是運籌學(xué)與組合優(yōu)化領(lǐng)域的研究熱點。有效的調(diào)度車輛，不僅可以提高物流工作效率，而且能夠為及時生產(chǎn)模式的企業(yè)提供運輸上的保障，從而實現(xiàn)物流管理科學(xué)化。由于該問題的理論涉及很多學(xué)科，很多實際問題的理論抽象都可歸結(jié)為這一類問題，研究該問題具有很重要的理論意義和實際意義。1.VRP（VehicleRoutingProblem）問題描述及其分類VRP問題一般可定義為：對一系列的裝貨點或卸貨點，組織適當(dāng)?shù)男熊嚶肪€，使車輛有序地通過它們，在滿足一定的約束條件(貨物需求量、發(fā)送量、車輛容量限制、行駛里程限制、時間限制)下，達到一定的目標(路程最短、時間最小、費用最省、車輛數(shù)目最少等)。由于該問題研究范圍非常廣，根據(jù)其網(wǎng)絡(luò)性能大致可以分為兩類：一類為靜態(tài)VRP(StaticVRP,SVRP)，一類為動態(tài)VRP(dynamicVRP,DVRP)。(1)靜態(tài)VRP問題描述SVRP問題是VRP中較簡單的一類問題，是大部分研究者研究的熱點。該問題具有一個很重要的特征：在安排初始路線時，和路線相關(guān)的所有信息已知，并且在安排路線以后其相關(guān)信息始終保持改變[2]。以下列舉了一些常見的SVRP問題:僅考慮車輛容量限制的VRP(CVRP)、帶時間窗的VRP(VRPTW)、帶有回收的VRP(VRPwithbackhauls)、帶有集派的VRP(VRPPD)。除此以外，還有許多其它CVRP的延伸問題，如顧客有優(yōu)先權(quán)，考慮卸貨時間、裝卸時間、等待時間等，甚至綜合了以上不同的特征。這些問題的相關(guān)信息均已知且保持不變[3]。(2)動態(tài)VRP問題描述所謂DVRP，是指在安排初始路線時，并不是和路線相關(guān)的所有信息都為已知，并且初始路線安排以后，其相關(guān)信息可能發(fā)生改變。DVRP研究范圍較廣，需求不確定、動態(tài)網(wǎng)絡(luò)、服務(wù)車輛不確定、提供數(shù)據(jù)有偏差等都屬于DVRP的研究范疇。從網(wǎng)絡(luò)性能角度，DVRP可以分為以下三種類型：1)時間依賴型VRP(TDVRP)。2)概率VRP(PVRP)。車輛運行時間以離散或連續(xù)概率發(fā)生變化。在這種網(wǎng)絡(luò)中可用期望運行時間代替路徑運行時間，再進行問題的求解。目前對該問題在最短路中研究比較多，一般是求得存在長度不超過給定值的路線概率及所給出路線為最短路的概率等[4]。3)時間依賴且概率變化的VRP。2.VRP問題算法描述(1)插入算法插入算法是指通過k步迭代時，將第k個節(jié)點插入到路線中。算法的關(guān)鍵在于確定在第k+1步可以被插入到路線中的點以及該點的最佳插入位置。因此，該算法由兩個關(guān)鍵的部分組成。第一部分是節(jié)點選擇階段，即確定下一步被插入到路線中的顧客節(jié)點；第二部分是路徑插入階段，即確定所選擇的顧客節(jié)點在路線中的最佳插入位置[5]。(2)節(jié)約算法節(jié)約算法是一類最為經(jīng)典的構(gòu)造型啟發(fā)式算法之一，該算法最早由Clark和Wright于1964年提出[6]，通常被簡稱為C-W算法。該算法的思想是：根據(jù)顧客點之間連接可以節(jié)省的距離（節(jié)約值）最大的原則，將不在線路上的顧客點依次插入到路線中，直到所有的點都被安排進路線為止。(3)最短路徑算法用于解決最短路徑問題的算法被稱做“最短路徑算法”，有時被簡稱作“路徑算法”。最常用的路徑算法有：Dijkstra算法、A*算法、Bellman-Ford算法、Floyd-Warshall算法、Johnson算法[7]。迪杰斯特拉提出的Dijkstra算法是最典型的最短路徑算法[8]。(4)遺傳算法遺傳算法（GeneticAlgorithm，簡稱GA）是美國J.Holland和他的學(xué)生于1975年受生物進化論的啟發(fā)而提出并建立發(fā)展起來的。其基本思想是借鑒大自然生物進化中“適者生存”的規(guī)律，通過對產(chǎn)生的解（“父代”）不斷操作（包括復(fù)制、交叉、變異和競爭）以產(chǎn)生新的解（“子代”），如此反復(fù)迭代，最終收斂到“最適應(yīng)環(huán)境”的個體，從而得到相對比較好的解[9]。綜上所述，各種優(yōu)化方法在一定情況下都有各自的優(yōu)點，都有解決某一問題的優(yōu)越性。最優(yōu)化算法有一個共同的特點就是可以求得最優(yōu)解，但不適應(yīng)現(xiàn)在的復(fù)雜的車輛優(yōu)化問題，尤其是對多配送點的大型配送服務(wù)，相對求得最優(yōu)解比較費時費力，且難以實現(xiàn)；而傳統(tǒng)的啟發(fā)式算法比最優(yōu)化算法相對好些，但仍有不太適用于現(xiàn)在于現(xiàn)在實際遇到的問題，和現(xiàn)代啟發(fā)式算法相比有些不足，但可以將各種算法結(jié)合使用，這樣就更方便使用解決實際當(dāng)中遇到的各種問題。求解VRP問題時，我們旨在得到一系列路線，車輛按照該路線來服務(wù)顧客，在滿足顧客需求的同時，使得總的運輸費用最小。在設(shè)計這些路線時，還要根據(jù)不同問題考慮不同約束，設(shè)計的路線不能夠違背相應(yīng)的約束。二、主題部分1.VRP問題研究的歷史背景1959年，Dantzig等人首先從旅行商問題（TravelingSalesmanProblem，簡稱TSP問題，）得到啟發(fā)，提出了車輛分配問題TDP（TruckDispatchingProblem）。這是一類具有重要研究價值的問題。一方面，它代表了一類典型的組合優(yōu)化問題，具有深遠的理論意義；另一方面，它是一類重要的物流運輸問題，直接影響著相關(guān)企業(yè)的運轉(zhuǎn)效率，具有廣泛的實踐意義。半個世紀以來，許多的專家學(xué)者對該問題進行了廣泛而深入的研究，并將這類問題統(tǒng)稱為車輛路徑調(diào)度問題（VehicleRoutingProblem，簡稱為VRP問題）。他們從基本問題出發(fā)，根據(jù)不同的約束和目標，構(gòu)建了不同的模型，并有針對性地開發(fā)出了有效的算法[5]。2.VRP問題算法的發(fā)展現(xiàn)狀隨著定位導(dǎo)航技術(shù)、數(shù)據(jù)通訊技術(shù)、自動控制技術(shù)、圖像分析技術(shù)以及計算機網(wǎng)絡(luò)和信息處理技術(shù)的快速發(fā)展，車輛優(yōu)化調(diào)度問題作為智能交通系統(tǒng)的一個重要組成部分，在很多國家受到關(guān)注。80年代以來，隨著ITS研究領(lǐng)域和內(nèi)容的不斷深入發(fā)展，逐漸形成了美國、歐洲和日本三大智能交通體系，且三大體系研究方面各有側(cè)重。目前，某些常用且較成熟的算法并已被人們運用的有實際的動態(tài)車輛調(diào)度系統(tǒng)，美國利用最短路徑算法、啟發(fā)式算法開發(fā)計算機配送調(diào)度系統(tǒng)用來解決貨運汽車作業(yè)計劃路線優(yōu)化選擇和車輛分配等問題，使汽車里程利用率提高5%-15%，運輸成本和運輸時間也有了明顯下降。目前已經(jīng)開發(fā)并應(yīng)用于實踐的動態(tài)車輛調(diào)度系統(tǒng)有美國IBM公司開發(fā)的VIIPX系統(tǒng)，其核心算法為最短路徑算法和啟發(fā)式算法；日本富士通公司開發(fā)的VSS系統(tǒng)，以節(jié)約為核心算法；美國美孚公司開發(fā)的HOCAD系統(tǒng)，以掃描為核心算法[10]。由于該問題在交通運輸、工業(yè)生產(chǎn)管理等領(lǐng)域具有廣泛而重要的應(yīng)用，因此近年來引起了人們極大的興趣，運籌學(xué)、應(yīng)用數(shù)學(xué)、組合數(shù)學(xué)、網(wǎng)絡(luò)分析、圖論、計算機應(yīng)用等學(xué)科的專家與運輸計算制定者和管理者進行了大量的理論研究及實驗析，取得了很大的進展。運用這些研究成果，車輛優(yōu)化調(diào)度問題已被成功運用到郵件速遞、出租車服務(wù)、奶品配送、生產(chǎn)計劃、緊急服務(wù)等業(yè)務(wù)之中。車輛的優(yōu)化調(diào)度問題是一種具有相當(dāng)廣泛實用價值的學(xué)術(shù)研究問題，在理論上屬于復(fù)雜的組合優(yōu)化問題[11]。當(dāng)前，現(xiàn)代物流已被公認為是企業(yè)在降低物質(zhì)消耗、提高勞動生產(chǎn)率以外創(chuàng)造利潤的第三個重要源泉，也是企業(yè)降低生產(chǎn)經(jīng)營成本，提高產(chǎn)品市場競爭力的重要途徑。配送是物流系統(tǒng)中的一個重要環(huán)節(jié)，它是指按客戶的訂貨要求，在物流中心進行分貨、配貨工作，并將配好的貨物及時送交收貨人的物流活動。在配送業(yè)務(wù)中，配送車輛調(diào)度問題的涉及面較廣，需要考慮的因素較多，對配送企業(yè)提高服務(wù)質(zhì)量、降低物流成本、增加經(jīng)濟效益的影響也較大。該問題包括集貨線路優(yōu)化、貨物配裝及送貨線路優(yōu)化等，是配送系統(tǒng)優(yōu)化的關(guān)鍵。3.VRP問題算法的發(fā)展方向相對于精確算法，啟發(fā)式算法具有更好的工程實際應(yīng)用價值。因為它既能夠在合理的時間內(nèi)得到問題的較優(yōu)解，又能夠使得到的較優(yōu)解的精度滿足工程要求。從總結(jié)可以看到，啟發(fā)式算法是一類基于直觀或者經(jīng)驗設(shè)計而成的算法，因而算法設(shè)計具有較高的靈活性和較大的自由度[12]。另外，隨著人們對VRP問題研究的深入以及對VRP問題解的質(zhì)量要求的提高，人們開始研究如何在算法中加進人的主觀判斷以提高解的質(zhì)量，比如如何在行駛過程中判斷到倉庫補貨的時機，這歸結(jié)為補貨策略問題；另外，人們也開始研究如何結(jié)合顧客庫存的情況來制定運輸策略的問題，這歸結(jié)為庫存運輸問題；諸如此類的研究尚處于起步階段，因此具有很大的研究潛力和意義。4.VRP問題算法的主要應(yīng)用隨著定位導(dǎo)航技術(shù)、數(shù)據(jù)通訊技術(shù)、自動控制技術(shù)、圖像分析技術(shù)以及計算機網(wǎng)絡(luò)和信息處理技術(shù)的快速發(fā)展，該問題在交通運輸、工業(yè)生產(chǎn)管理等領(lǐng)域具有廣泛而重要的應(yīng)用。(1)智能交通系統(tǒng)車輛調(diào)度中的應(yīng)用[13]。在智能交通系統(tǒng)(ITS,IntellignetTransportationSystems)的各個子系統(tǒng)中,先進的公共交通系統(tǒng)(APTS,AdvancedPublicTransportationSystem)具有重要地位和作用,其中車輛調(diào)度問題是APTS的關(guān)鍵.為了提高車輛調(diào)度的智能化,提出了一種基于遺傳算法(GA,GeneticAlgorithm)的公交車輛智能調(diào)度方法,采用最小費用作為目標函數(shù),考慮了車輛配置、時間、運營效率及資源利用等方面因素,通過選擇、交叉及變異等遺傳操作,得到了最優(yōu)的調(diào)度排序方案,并對2種交叉方式進行了比較,仿真結(jié)果表明,利用GA解決車輛調(diào)度問題具有可行性、先進性和快速性.(2)物流管理[14]。車輛調(diào)度問題是物流管理研究中的一項重要內(nèi)容。選取恰當(dāng)?shù)能囕v路徑,可以加快對客戶需求的響應(yīng)速度,提高服務(wù)質(zhì)量,增強客戶對物流環(huán)節(jié)的滿意度,降低服務(wù)商運作成本。(3)動態(tài)車隊管理[15]。開展貨物運輸作業(yè)的優(yōu)化組織工作是降低運輸成本、提高運輸效率的重要手段和關(guān)鍵。貨運車輛作為貨物運輸?shù)闹苯虞d體，同時也是貨物運輸作業(yè)過程中最重要的可支配資源。運用所掌握的車輛資源合理安排組織運輸任務(wù)，消除對流、迂回、重復(fù)等不合理現(xiàn)象，實現(xiàn)車輛的優(yōu)化組合與配置，并達到以最少的資源投入獲得最優(yōu)經(jīng)濟效益的目的，是整個貨物運輸優(yōu)化組織工作的核心內(nèi)容。車隊管理問題的研究就是在這種背景與需求下提出的，通過對貨運車輛的科學(xué)有效管理，可以大大提高車輛利用率，實現(xiàn)貨物運輸科學(xué)化。同時，對車隊管理問題展開系統(tǒng)化地研究工作也是構(gòu)建高效的貨物運輸組織體系、建立現(xiàn)代調(diào)度指揮系統(tǒng)、實現(xiàn)物流集約化和科學(xué)化、發(fā)展智能交通運輸系統(tǒng)的基礎(chǔ)與關(guān)鍵。三、總結(jié)部分VRP問題自從被提出來以后就受到了廣泛的關(guān)注，不少學(xué)者對求解該問題的算法進行了研究，并取得了不少成果。VRP模型方面雖有許多研究，但缺少綜合方面的研究。現(xiàn)代物流中，要求盡量減少庫存，及時配送變得越來越重要，所以今后滿足客戶的時間窗口是制定車輛路線優(yōu)先考慮的重點。還有現(xiàn)有的配送路線的研究多為開發(fā)靜態(tài)的模型，很少分析參數(shù)隨時間變化的特性，而在現(xiàn)代物流日趨快速化、信息化、實時化的情況下已經(jīng)有些不適應(yīng)。例如，倉庫位置的成本將隨時間變化；在一定的時間范圍內(nèi)，公司需要根據(jù)情況的變化來重新決策配送中心及銷售網(wǎng)點的分布。因此，在配送路線模型中加入動態(tài)特性，實現(xiàn)實時或在線物流管理，會極大地提高與現(xiàn)實接近的程度。目前對VRP問題的研究，大部分還停留在SVRP問題上。從近幾年的文獻可以發(fā)現(xiàn)，已經(jīng)有一些關(guān)于TDVRP的模型及算法的研究。SVRP問題研究為DVRP問題研究奠定了理論基礎(chǔ)，DVRP問題更貼近實際，隨著研究的不斷深入，其理論成果不僅可以在物流、供應(yīng)鏈優(yōu)化、通信線路設(shè)計等相關(guān)領(lǐng)域得到廣泛應(yīng)用，還可以促進智能交通系統(tǒng)的發(fā)展，有助于物流配送與發(fā)達的交通系統(tǒng)相結(jié)合，對于節(jié)約能源、提高物流工作效率、優(yōu)化交通資源、改善城市交通狀況也將起到十分重要的作用。這將是VRP領(lǐng)域未來研究的熱點。本課題研究的研究旨在通過應(yīng)用動態(tài)規(guī)劃思想，改進求解VRP問題的節(jié)約法，建立不斷增加節(jié)約量的動態(tài)規(guī)劃數(shù)學(xué)模型，使其能夠得到全局最優(yōu)解，并將此算法應(yīng)用于一種實際中。四、參考文獻[1]賈永基.車輛調(diào)度問題優(yōu)化算法研究[D];上海交通大學(xué);2004.[2]LarsenA.Thedynamicvehicleroutingproblem[D].Dept.ofMathematicalModelling,Technical[3]李妍峰,李軍,趙達.車輛調(diào)度問題研究現(xiàn)狀及展望[D].四川成都，2005.[4]AliHaghani,JungSoojung.Ageneticalgorithmforvehicleroutingproblemwithtimedependenttraveltimes[J].ComputersandOperationsResearch,2005,32:2959–2986.[5]楊燕旋,宋士吉.車輛調(diào)度問題的啟發(fā)式算法綜述[D].北京：清華大學(xué)自動化系，2007.[6]ClarkeG,WrightJW.Schedulingofvehiclesfromacentraldepottoanumberofdeliverypoints.OperationsResearch1964;12(4):68-81.[7]彭立云.最短路徑算法——Dijkstra算法[EB/OL];/hanchan/archive/2009/09/23/1572509.html:2009-09-23/13:05.[8]嚴蔚敏,吳偉民.《數(shù)據(jù)結(jié)構(gòu)（C語言版）》[M].北京：清華大學(xué)