基于改進蟻群算法的時間窗約束下物流配送車輛路徑優化研究

摘要：物流配送車輛路徑優化作為一個涉及多影響因素、多目標需求的組合優化問題，其中帶時間窗約束的物流配送車輛路徑優化問題更是一個NP難題，較難得到最優解。文章分析帶時間窗約束的車輛路徑問題并建立相應數學模型，提出將變異和動態信息更新的改進蟻群算法應用于解決這類優化問題，同時仿真實驗結果表明該算法能快速收斂于全局最優解，能有效地解決有時間窗約束下的物流配送車輛路徑優化問題。

關鍵詞：改進蟻群算法；時間窗約束車輛路徑問題；物流配送

一、 引言

物流配送過程中的車輛路徑優化問題（Vehicle Rou-ting Problem，VRP）作為物流配送優化的核心環節，一方面作為一項物流管理的重要內容，它對整個物流運輸的速度、成本、效益起著至關重要的作用；另一方面隨著現代物流配送的快速發展，物流配送越來越強調滿足顧客種類、數量和時間等方面要求，提升顧客的滿意度。配送車輛路徑安排這一組合優化問題最初由Dcmtzing Ramser于1959年提出，一直以來，作為交通運輸和物流配送領域的一個核心問題，也成為一個運籌學、優化科學等學界研究的熱點。

在實際應用中帶時間窗的車輛路徑問題（VRP With Time Windows，VRPTW）作為傳統VRP問題的擴展和衍生，已被Savelsbergh證明是一個NP難題，對于大規模的VRP問題很難得到全局最優解。近年來在構造啟發式算法和兩階段啟發式算法的基礎上發展起來的智能啟發式算法如禁止搜索算法、模擬退火法、遺傳算法、神經網絡法、蟻群算法和粒子群算法等應用在有時間窗的車輛路徑優化，取得了較好的效果。但這些算法存在著一些明顯的缺陷，如：禁止搜索算法由于涉及復雜領域轉換和求解策略，在現實中不易實現；模擬退火法也只能結合其它局部搜索算法構造混合算法應用；遺傳算法不能保證最大的概率收斂于全局最優解；神經網絡法、蟻群算法和粒子群算法易產生局部收斂和收斂速度較慢等。這篇文章研究一種高速收斂的改進蟻群算法，在該算法中，滿足個點的時間窗約束的前提下采用一種新穎的動態信息新策略，以保證在每次搜索中，每只螞蟻都對搜索做出貢獻，同時還采取了一種獨特的變異策略，以對每次搜索結果進行搜索，以對每次搜索的結果進行優化。

二、 物流配送車輛路徑優化問題的數學模型

時間窗約束下物流配送車輛路徑優化問題可以描述為：從配送中心用多輛汽車向多個需求點送貨，每個需求點的位置、需求量和時間窗約束一定，每輛汽車的載重量一定，要求合理安排汽車行駛路線，使總運輸成本最小，并滿足以下條件：

1. 每條配送路徑上需求點的需求量之和不超過汽車載重量；

2. 每條配送路徑的長度不超過汽車一次配送的最大行駛距離；

3. 每個需求點的需求量得到滿足，且只能由一輛汽車送貨；

4. 每個需求點的時間窗約束得到滿足，且保證車輛工作總時間不超過其最長工作時間。

本文設配送中心有M輛汽車，第k輛汽車的載重量為 Qk（k=1，2，L，C）其一次配送的最大行駛距離為Dk，需要向L個需求點送貨，每個需求點的需求量為qi（i=1，2，L，L），時間窗為[ei，ui]，其中ei為任務i允許最早開始時間，如果車輛早于ei到達，則需在i處等待；ui為任務i允許最遲開始時間，如果車輛晚于ui到達，則任務i將被延遲進行。設nk為第k輛汽車配送的需求點數（nk=0表示未使用第k輛汽車），用集合Rk表示第k輛車的行駛路徑，其中rki表示一個需求點，且這個需求點的路徑Rk中的順序為i，rk0=0表示配送中心。再設trki表示第k輛車在行駛路徑Rk上到達i點的時刻，wrki表示第k輛車完成任務i（如：驗收、簽單和卸貨等）需要的時間。另外在目標函數中用ck表示車輛k行駛的單位運輸成本，pe表示在ei之前到達需求點i單位時間的機會成本，pu表示在ui之后到達需求點i單位時間的罰金成本。由此可建立如下物流配送車輛路徑優化問題的數學模型。

其中，式（1）為目標函數；式（2）保證每條路徑上各需求點的需求量之和不超過汽車的重量；式（3）保證每條配送路徑的長度不超過汽車一次配送的最大行駛距離；式（4）、（5）保證車輛的工作總時間不超過最長工作時間；（7）表明每條路徑上的需求點都得到配送服務；式（8）為每條路徑的需求點的組成；式（9）限制每個需求點只能由一輛汽車送貨；式（10）第k輛汽車服務的客戶數大于等于1時，說明該輛車參加了配送，則取sign（nk）=1，當第k輛汽車服務的客戶小于1時，表示未使用該車，取sign（nk）=0。

三、 算法的描述與實現

螞蟻與配送之間的對應關系如表1所示。

在螞蟻進行路徑搜索時，如果找到一段很短的子路徑（子解），它就釋放出相應濃度的信息素，該信息素一方面直接影響位于子解的兩個點上的螞蟻；另一方面它會以該路徑為中心向外擴散，影響其路徑附近的其它螞蟻的行為，使它們在尋找路徑時會以更大的概率在下一步選擇該路徑。同時在時間窗約束下螞蟻開辟新的路徑遵循以下規則：從當前路徑的最后一個路口出發，到所有未訪問的路口中開始服務時間最早的的那個路口。只有當開始服務時間超過路口的時間窗時，才主動開辟一條新路徑，并從未訪問的路口中重新限制出發點，將所有未訪問過的路口中開始服務最早的那個路口作為最新路徑的第一個路口。通過這種基于時間窗約束下信息素擴散的協作方式，一方面指導螞蟻在滿足新的路口時間窗內開辟下一路徑，另一方面其他螞蟻在選擇下一個路口時選擇到最優路徑的干擾性會降低。從而在滿足各路口的時間窗要求的同時使算法的收斂程度大大提高，提升算法搜索的效率和成功率。

具體的算法如下：

Step1：初始化，設置待定參數和最大進化代數；

Step2：隨機選擇每只螞蟻的位置；

Step3：計算每只螞蟻k將要轉移的位置，假設為j，上一個位置假設為i。按所需等待時間較短和時間窗較窄的優先原則計算下一路口j的時間窗寬度和所在路口i到達下一路口j的時間；然后按往下一路口j的路徑長度以及路徑上的信息量計算轉移概率，計算公式為：

Step7：若本次循環中每只螞蟻都執行了Step3~Step6，則轉至Step8，否則轉向Step3。

Step8：按式（10）更新各條路徑上的信息素濃度，此時式（10）中取m=1。

Step9：如果每只螞蟻都完成了一個完整的路徑，則轉向Step10，否則轉向Step3。

Step10：是否達到指定的進化代數或者所求得的解在最近若干代中無明顯改進，如果出現這樣情況，則轉向Step11，否則轉向Step3。

Step11：輸出優化結果。

四、 仿真實例

在這篇文章中，應用文獻“7”和文獻“10”中提出的算例進行仿真。由中心倉庫0向8個需求點運輸貨物（編號為1，2，…，8），各任務貨運量qi（i=1，2，L，8）、每客戶所需工作時間及每項客戶任務的時間窗由表1給出。這些任務發出的3輛容量為8噸的車輛完成，中心倉庫與各客戶點間及各客戶點間的距離由表2給出，車速50，單位運輸成本為1，超出時間窗的單位懲罰為：pe=50，pu=50。

用1，2，L，L表示各需求點，因為共有M輛汽車，最多存在M條配送路線，每條配送路徑都始于配送中心，也終于配送中心。為了在編碼中反映配送路線，采用了增加M-1虛擬配送中心的方法，分別用L+1，L+2，L，L+M-1表示。這樣1，2，L，L+M-1這路徑L+M-1個互不重復的自然數的通知數的隨機排列就構成了一個個體，并對應一種配送路徑方案。并將描述的算法用MATLAB編程，生成NDMACO.m文件運行程序。

在同一臺計算機上將本文提出的改進蟻群算法運算結果與遺傳算法、基本蟻群算法的求解結果進行比較。

五、 結論

在這篇文章中，在有時間窗約束下的物流車輛配送路徑問題應用變異和動態信息素更新的改進蟻群算法，即將 m只螞蟻均勻放置于n個邊部配送點，采用最近鄰居節點選擇原則，在此基礎上滿足各路口時間窗約束，同時進行動態局部信息素更新并用變異算法加速局部尋優使收斂速度提高較多，在同樣一臺計算機上運算結果與遺傳算法和基本蟻群算法等其他算法求解結果相比具有明顯的優越性。因此，應用文中描述的算法，可以進行有時間窗約束的物流配送車輛路徑優化，且滿足各點時間窗需求的情況下較快地得到近似的最優解，為今后解決有時間窗約束下的物流配送車輛路徑優化問題提供一定的參考。

參考文獻：

1. 盛麗俊，周溪召．帶有時間窗的車輛路徑問題優化．上海海事大學學報，2007，（4）:64-67．

2. 姜凌，沈桂蘭．基于蟻群算法的物流配送車輛路徑優化問題研究.首都經濟貿易大學學報，2010，（1）:71-74.

3. 即茂祥，胡思繼.用混合遺傳算法求解物流配送路徑優化問題的研究.中國管理科學，2002，（10）：51-56．

4. 亓霞，陳森發，黃鹍等.基于免疫算法的物流配送車輛路徑優化問題研究.土木工程學報，2003，（7）：43-46．

5. 張毅，申彥杰.時間窗約束下的車輛路徑問題多目標優化算法.數學的實踐與認識，2009，（7）：124-130．

6. 劉北林，高爽.配送車輛路徑優化問題算法研究.商業經濟，2008，（9）：31-33．

7. 李軍，郭耀煌．物流配送車輛優化調度理論與方法.北京：中國物資出版社，2001．

8. 朱慶保，楊志軍.基于變異和動態信息素更新的蟻群優化算法．軟件學報，2004，（2）：85-92．

9. 肖國璽，彭玉青，林濤等．基于螞蟻算法的物流配送計劃的生成.河北工業大學學報，2005，（4）：163-165．

10. 肖力.基于改進蟻群算法的物流配送問題研究.計算機仿真，2008，（4）:182-185．

11. Dorigo M，Grambardalla L M．Ant colony system ：a cooperative learning approach to the traveling salesmen problem ．IEEE Transaction Son Evolutionary Computer，1997，（1）：53-56．

12. 李志威，張旭梅．基于動態掃描和螞蟻算法的物流配送網絡優化研究．管理工程學報，2006，（4）：9-12．

基金項目：國家自然科學基金資助項目“機動多目標跟蹤融合策略研究”（項目號：61005026）。

作者簡介：張玉春，南京航空航天大學管理科學與工程博士，蘭州理工大學國際經濟管理學院副教授、碩士生導師；余炳，蘭州理工大學國際經濟管理學院碩士生；申風平，蘭州理工大學經濟管理學院教授、碩士生導師。

收稿日期：2010-11-09。