發布時間：2020-09-18所屬分類：管理論文瀏覽：1次
摘 要： 摘 要：車輛調度指的是車輛的合理化調度，自四十多年前被提出之后，便成為了廣大學者研究的重點以及熱點課題。文章首先對車輛調度問題進行了簡單的描述，重點總結了相關學者在算法求解上的研究成果，主要包括算法的分類以及特點分析，最后對后續問題的研究工
摘 要：車輛調度指的是車輛的合理化調度，自四十多年前被提出之后，便成為了廣大學者研究的重點以及熱點課題。文章首先對車輛調度問題進行了簡單的描述，重點總結了相關學者在算法求解上的研究成果，主要包括算法的分類以及特點分析，最后對后續問題的研究工作進行了預測與展望。
關鍵詞：車輛調度;合理化;算法
一、引言
隨著市場經濟的發展和交通運輸業專業化水平的提高，交通運輸業成為了國民經濟發展的重要行業，它與社會生活建立了密切的關系。與此同時，運輸成本的問題也成為人們日益關注的重點問題。如何平均分配資源、合理安排配送路線、減少運力資源的浪費成為當前研究的熱點問題[1]。在物流優化的過程中，優化車輛調度方案成為其中至關重要的一環。
二、車輛調度問題的描述
車輛調度問題(Vehicle Routing Problem，簡稱 VRP)由 Dantzig 和 Ramser 首次提出后，便引起了運籌學、數學、計算機等各大領域學者的極大重視。建立合理的配送方案可以有效縮短物流配送過程中的交貨時間，大大提高配送效率以及經濟效益，因此，車輛調度問題的研究對降低物流配送成本、實現合理的物流管理具有重要作用。
車輛調度問題指的是：根據發貨點以及接收點，組織適當的運輸路線，當車輛到達目的地時，它可以滿足規定的限制(例如運輸時限、貨物數量限制、貨物類型限制、車輛數量限制等)，又能達到最終目標(如最短的配送距離、最少的配送車輛數量、最低的配送價格、最低的勞動消耗、最短的花費時間等等)。
三、車輛調度問題算法的分類
VRP 問題根據研究重點的不同，可以分為很多類。本文依據求解 VRP 問題方法的不同，認為基本上可以分為兩大類，分別是精確算法以及啟發式算法。
1.精確算法
最終能夠得到最優解的算法我們稱為精確算法，由于隨著 VRP 問題規模的逐漸增大，計算量隨之會呈指數級增長，因此該算法一般適合于解決小規模的 VRP 問題。精確算法有如下幾種。
相關期刊推薦：《科技資訊》雜志，旬刊，于2003年經國家新聞出版總署批準正式創刊，由北京市科學技術研究院主管，北京國際科技服務中心:北京合作創新國際科技服務中心主辦的學術性刊物，本刊在國內外有廣泛的覆蓋面，題材新穎，信息量大、時效性強，其中主要欄目有：科技前沿、信息技術、動力與電氣工程、工程技術、工業技術、農業與生態環境、企業管理、科技教育、圖書館論壇、學術論壇。
分枝定界法(Branch and Bound Approach)是由 Laporte 等人首次提出，這是一種應用范圍十分廣泛的搜索算法，基本思想是：將給定問題分解為若干子問題，再把子問題進一步分解，直到無法分解或者無法產生最優解為止。而分解成子問題的這個過程稱之為分枝。該算法在解決車輛調度問題的過程中使用 VRP 和 m-TSP 之間的密切關系，其中關鍵的步驟是將 m-TSP 轉換成 1-TSP。本算法可求解最大 260 個顧客點的 VRP 問題。
割平面法(Cutting Planes Approach)1958 年由美國格莫理提出�；舅悸肥牵菏紫惹缶�性規劃問題的最優解，如果最優解恰巧滿足是整數的條件，那么將此解作為該問題的最優解。否則，添加一個新約束, 稱為割平面。重復以上做法，經有限次切割后，可行域將逐漸縮小，并且最終將存在整數極點，如此一來，在該整數極點處獲得整數規劃問題的最終解。從幾何意義上講，R 依據約束條件進行分割，而分割后的 R’中，將所有整數可行解保留了下來，而無法滿足條件的解就會被舍棄，重復進行上述“切割”操作，最終得到的就是最優解。
網絡流算法(Network flow approach)，該方法與圖論中的一些傳統算法(如最短路徑、寬度搜索算法等)相結合，經�？梢越鉀Q一些搜索與動態規劃無法解決的非 NP 問題。在解決實際問題的過程中，最核心的問題是如何構造模型，因為它不存在一個固定而又可以直接套用的模型，需要研究者充分了解網絡流的性質，不同的問題可以建立多種模型，而模型種類的不同也會在很大程度上影響對問題的解決效率。這是一種高效實用的算法，適用范圍也比較廣泛。
動態規劃法是解決多階段決策問題的一種方法，動態規劃法的具體步驟為：首先將求解 VRP 問題視為一個 n 階段的決策問題，初始狀態做為起始點，結束狀態做為終止點，在這個過程中，需要經過多個階段決策選擇，形成一個決策序列。由于一個階段決策的執行會直接影響下一階段的決策，甚至會影響整個活動的總體效果，因此通常按照一定的模式完成動態規劃設計，具體過程表示為如圖 1 所示。
2.啟發式算法
常見的啟發式算法包括三大類，分別是構造型啟發算法、改進型啟發算法、人工智能算法。具體表示為表 1 所示。
(1)構造型啟發算法
構造型啟發算法最大的特點是主要依據直觀感受或對長期經驗的歸納推理而構造的算法，這種算法最大的特點是每一次將一個不在已構建路線上的點添加到已經構建的路線中去，直到所有的點都添加進來為止，這種算法運行速度快，靈活性高。構造型啟發算法的經典算法分為插入算法、節約算法。
插入算法是通過逐步插入來實現的，通過 k 步迭代之后，將第 k 個節點插入到路線中，算法的重點以及難點在于根據不同的選擇規則，確定第 k+1 步(下一步)插入到路線中的點，以及插入的最佳位置。比如考慮最短距離做為選擇規則的一個主要考慮因素，就形成了最短距離插入算法(Nearest Insertion)，該算法的核心是：路線中已經存在 n 個點，確定距離路線中的已經存在的所有點的任意一點距離，將距離最近的點繼續插入到路線當中。其中 Renaud 和 Boctor[2]等人開發了 CLOCK 插入算法，插入算法是這種算法的核心思想，具體步驟從起始節點開始，按旋轉順序分別包括順時針和逆時針順序。 將其他節點依次插入到路線中，這樣一來，初始路線可能無法包含所有的節點，隨后我們需要將其他的節點依次插入到路線當中，最終得到的是一個完整的路線。
節約算法是由 Clark 和 Wright[3]兩人在 1964 年提出的，該算法的核心思想是：將原本不在線路上的顧客點依次插入到線路當中，其中節省距離記為 s(i,j)=ci0+ c0j- cij，ci0、c0j 表示單獨服務 i 和 j 需要花費的費用，cij 表示從 i 運輸到 j 需要花費的總費用。該算法后期被很多學者借鑒以及引用。
(2)改進型啟發算法
改進型啟發式算法[4]最大的特點是，首先得到一個初始解，之后對當前存在的解反復進行調整，直到目標函數達到最優并且無法再改進為止。改進型啟發算法的經典算法為 Petal 算法、Sweep 算法。
Petal 算法是 Lin 等人提出，該算法的核心思想是首先以倉庫為坐標中心建立極坐標，獲取所有節點的極坐標角，并將這些極坐標角按照大小進行排序，這樣一來，Petal 是由任何一組連續節點構成的集合，然后使用分割模型來獲取優化的路線并得到最優解。本算法提出之后，許多學者從中受到了啟發，使用該算法進行了很多后續研究，并提出了許多新的算法。
Sweep 算法是由 Gillett 和 Miller 于 1974 年提出，該算法首先對所有的顧客節點進行排序，排序的依據是上面提到的 Petal 算法，之后將運輸任務分配給各個車輛，形成一個相對來說比較合理的解，之后將第 n 條路線上的一個節點記為 j 抽出來，其中 n=1,2……K-1,K 指的是路線的總數，與此同時，將第 n+1 條路線上的若干個點換到第 n 條路線中，通過指定的函數，確定節點 j，將 j 分配到其他路線當中，重復進行上述操作。這是 Sweep 算法的核心思想，這種算法適合處理裝貨或者卸貨問題，并且車輛是封閉的。
(3)人工智能算法
人工智能算法的經典算法分為遺傳算法(GA)、蟻群優化算法。遺傳算法(GA)[5]由美國學者 J. Holland 和他的學生于 1975 年提出，它的工作機理較為簡單。 該算法受到生物進化論的啟發，核心思想是：依據大自然的進化規律——適者生存，對生成的解(作為父代) 不斷的進行操作，具體操作包括復制、變異、競爭、交叉，從而產生新的一代，通過對這一過程的反復迭代，最終會產生最適應環境的個體。遺傳算法在解決 VRP 問題的時候，首先通過構建往返于倉庫和顧客節點的路線集并且編碼，產生初始種群，隨后選出部分染色體，通過取出不同的基因的方式或者改變某些基因的方式(變異)，產生新的染色體，進而通過競爭機制篩選出優秀的個體，反復重復上述操作，直到得到最優解為止。該算法可用于處理復雜的線性、非線性問題。
蟻群算法由 M. Dorigo 和其他學者在 20 世紀 90 年代提出，該算法受啟發于蟻群覓食行為。研究者發現，單只螞蟻覓食能力有限，行為也較為簡單，但是群體螞蟻的行為就會相當復雜，他們通過相互協作，能夠很輕松的找到從蟻穴到食物的最短距離，因為他們會在通往食物的路上釋放一種“信息素”，蟻群會通過“信息素”實現螞蟻之間的信息交流，信息素的濃度指導著螞蟻的移動方向，由于短路徑受到螞蟻的青睞，因此螞蟻行走的頻率比較高，“信息素”的濃度也會隨之提高，從而其他螞蟻也可以獲取從蟻穴到食物的最短距離。
四、總結與展望
現階段，VRP 問題成為廣大學者研究的焦點。本文結合國內外相關研究，對比較典型的兩大類算法進行了詳細的分析和具體的總結，有助于后續 VRP 問題的研究。如何產生高質量的解，如何在行駛的過程中判斷倉庫補貨時機，另外如何依據庫存確定運輸策略這些問題都引起了研究者的關注，由于對這些問題的研究剛剛開始，因此會有更多的研究空間。——論文作者：宋亞青，王海賓，高娟娟
SCISSCIAHCI
