1、 車輛路徑優化及算法綜述袁建清（黑龍江東方學院計算機科學與電氣工程學部，黑龍江哈爾濱）摘要：闡述了的主要求解算法，在參閱大量文獻基礎之上以禁忌搜索算法、遺傳算法、螞蟻算法三種主要的算法為劃分總結了的研究現狀以及三種算法的改良與應用情況，最后對車輛調度問題進行了展望，提出了進一步發展動向。關鍵詞：車輛路徑問題；算法中圖分類號：文獻標識碼：文章編號：（）作者簡介：袁建清（），女，黑龍江穆棱人，碩士，黑龍江東方學院講師，研究方向為信息管理。引言車輛路徑問題（，）是指在客戶需求和位置已知的情況下，確定車輛在各個客戶間的行駛路線，使得運輸路線最短或運輸成本最低。對運輸車輛進行優化調度，通過選擇車輛的最佳

2、運輸路徑，合理安排車輛調度順序，可以有效減少車輛的空駛率和行駛距離。它是物流系統優化環節中關鍵的一環。已經典型應用到牛奶配送、報紙和快件投遞、垃圾車的線路優化及連鎖商店的送貨線路優化等眾多社會領域，而且在工業管理、物流管理、交通運輸、通訊、電力、計算機設計等領域都有廣泛的應用。求解算法是一個難問題，因此根據各具體類型問題的特點應用啟發式算法算法求解已經成為研究的主流。其中傳統啟發式算法主要有節約算法、插入算法、二階段算法法等；現代啟發式算法主要有禁忌搜索算法（，）、遺傳算法（，）、模擬退火算法（，）、螞蟻算法（，）等。近年來應用最多的是禁忌搜索算法、遺傳算法、螞蟻算法以及它們之間或它們與傳統啟

3、發式算法之間的結合形成的混合算法。（）禁忌搜索算法（）：是一種全局優化搜索算法，通過引入一個靈活的存儲結構和相應的禁忌準則來避免迂回搜索，并通過藐視準則來赦免一些被禁忌的優良狀態，進而保證多樣化的有效探索以最終實現全局優化。但是存在對初始解有較高的依賴性的缺點。（）遺傳算法（）：是一種基于自然進化原理的全局搜索隨機算法，它使用群體搜索技術，通過對當前群體施加選擇（）、交叉（）及變異（）等一系列遺傳操作，從而產生出新一代的群體，并逐步使群體進化到包含或接近最優解的狀態。該算法有局部搜索能力不強、易陷入早熟、總體上可行解的質量不是很高的缺點。（）蟻群算法（）：是一種概率搜索算法，它模擬螞蟻群體在覓

4、食過程中所體現出的智能行為，利用信息激素為媒介進行間接的信息傳遞，根據信息素的強度做出對較優解的選擇。此算法有易陷入早熟、停滯、局部最優的缺點。研究現狀一直是物流屆研究的熱點問題，縱觀國內外學者研究都是通過對以上幾種算法進行改良或將其結合形成有效地混合算法，而對不同約束條件下車輛路徑優化問題進行求解。本文針對三種主要算法總結研究現狀如下：（）應用遺傳算法研究。文獻分別用改進的遺傳算法、免疫遺傳算法、小生境遺傳算法、以及與爬山算法、禁忌搜索算法、蟻群算法相結合的混合算法對時間窗的車輛路徑優化問題（）進行了求解。另外：張海剛等提出用基于自然數編碼的遺傳算法同時處理有軟硬時間窗的，魏航等設計了基于自

5、然數編碼的遺傳算法，針對有行駛里程限制的多車場滿載車輛調度問題。（）應用禁忌搜索法研究。學者們對禁忌搜索法的應用主要針對兩方面進行改良。一是構造好的初始解，在這方面主要形成三種方法：隨機排列，然后將顧客按序列聚類分配到每輛車，從而產生每輛車的路徑；先分組，然后在每個組內采用旅行商算法產生初始解；用啟發式構造線路。二是通過改進鄰域移動方法構造候選解優化算法。此外：利用算法求解了多車型的；等利用禁忌搜索算法對帶回程的進行了研究；鐘石泉等對軟、硬時間窗約束的進行了研究，并用禁忌搜索算法分別進行求解。（）應用蟻群算法研究。算法的改良總結起來也是兩個方面：一是信息素更新機制的改進，即通過對信息素生成和更

6、新策略的優化來提高蟻群算法的尋優能力，改善解的全局收斂性。二是搜索機制的改進，對隨機搜索過程的控制策略進行調整，以減少迭代次數，加速收斂。例如吳慶洪等提出用變異策略以加快局部搜索的變異特征的蟻群算法，丁建立等提出將遺傳算法與蟻群算法相融合的算法。另外朱慶保等將以上兩種改進機制的相結合，提出了一種基于變異和動態信息素更新的算法，提高算法時間。研究展望根據對現狀的分析，文中總結提出以下三方面發展動向。（）多種約束條件下的車輛調度問題研究。現如今大多數的研究都是針對一種或兩種約束下的車輛調度研究，多種約束條件下研究極少，而現實中往往是多種限制條件并存的，因此對多種約束條件下的進行建模，給出更好的改良

7、算法或混合算法求解是進一步需要研究的。（）動態車輛調度。在以往的大多數研究中，多數是對靜態車輛調度研究，即在調度之前，認為所有的信息（包括客戶信息、車輛信息等）都是確定。而在實際的車輛調度計劃制定和執行過程中，往往會有新的客戶請求的提出或客戶信息的變化，這時要求系統能夠快速地響應這種信息更新，并重新制定車輛調度計劃。國內對動態車輛調度研究剛剛起步，理論、算法還不是很成熟，而且研究都是基于單時窗的，沒有考慮多時間窗分布的，以及路線網絡性能、車輛負載對成本的影響等更多因素約束下的情況。（）避免擁塞現象的車輛路徑問題。大多數研究者致力于空間最優路徑（閉合路徑）的研究和應用，大量交通工具向最優路徑聚集

8、，勢必造成嚴重的道路擁塞問題。因此，根據現有的道路網絡及其設施與出行的分布狀況，改善管理，可以整個系統在時間和空間分布上盡可能地得到協調，保證路網暢通。國內對于這方面的研究的文獻也不多，只有劉志碩等提出基于解均勻度的車輛路徑問題的自適應蟻群算法；潘登等研究出了一種避免車輛路徑擁塞的動態蟻群算法；于德新等提出動態限制搜索區域的帶約束則最優路徑算法，用于均衡路網上的交通流。因此也有很大的研究空間。參考文獻：，（）謝秉磊，李軍，郭耀煌有時間窗的非滿載車輛調度問題的遺傳算法系統工程學報，（）楊宇棟，朗茂祥有時間窗車輛路徑問題的模型及其改進模擬退火算法研究管理工程學報，（）余振華車輛路徑問題的改進免疫遺傳算法微計算機信息，（）張海剛，顧幸生改進的粒子群算法及其在帶軟時間窗車輛調度問題中的應用華東理工大學學報（自然科學版），（）魏航，李軍有行駛里程限制的滿載車輛調度問題西南交通大學學報，（）郎茂祥，胡思繼車輛路徑問題的禁忌搜索算法研究管理工程學報，（）劉興，賀國光車輛路徑問題的禁忌搜索算法研究計算機工程與應用，（）張立東，畢篤彥一種基于洪水消退模型的快速分水嶺算法模式識別與人工智能，（），鐘石泉，賀國光有時間窗約束車輛調度優化的一種禁忌算法系統工程理論方法應用，（），：，黃國銳，曹先彬，王煦法基于信息素擴散的蟻群