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

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