基于改進蟻群算法的軟硬時間窗車輛路徑優化

楊婷 韓冬桂 燕怒 劉芳

摘要：文章針對客戶對時間緊迫性要求不同的情形，建立軟硬時間窗車輛路徑優化模型，在車輛行駛距離和載重約束下，以行駛成本、懲罰成本和固定成本形成的總成本最低為目標，利用改進蟻群算法優化車輛路徑。首先螞蟻狀態轉移規則采用隨機規則使螞蟻優先選擇時間窗較窄和到達時間較早的節點，接著采用偽隨機規則決定螞蟻傾向選擇信息素濃度較大的路徑或隨機選擇，并且探討偽隨機因子q。取值對解的影響并找到最優值，同時對不滿足硬時間窗約束的節點做返回到配送中心的處理。最后通過實例驗證，Matlab仿真計算，采用偽隨機規則且使用最優的q。值，使配送成本降低且總優化率提高了17%，進一步論證改進蟻群算法有優于遺傳算法的收斂效果。

關鍵詞：軟硬時間窗;蟻群算法;偽隨機規則;偽隨機因子

中圖分類號：U116.2文獻標識碼：A

0引言

隨著經濟全球化，物流行業作為“第三方利潤源泉”的學說被提出，配送是物流活動與消費者直接相連的重要環節，經調查，運輸成本在整個物流成本中占相當大的比例。因此，有效降低運輸成本對企業發展具有重要意義。

車輛路徑設計直接影響到物流配送成本，現實生活中，不同客戶對貨物送達時間的要求不一致，于是存在混合時間窗的問題。（1）硬時間窗，若車輛早于該客戶的約定時間，必須等待;若晚于約定時間，則拒絕服務。（2）軟時間窗，若車輛早于或晚于該客戶的約定時間，將按規定受到懲罰成本。目前，對單獨研究硬時間窗或軟時間窗或無時間窗車輛路徑問題比較多，但對時間窗同時存在的情況研究比較少。周蓉等利用粒子群算法求解軟硬時間窗共存裝卸一體化車輛路徑問題。史昊等探討用于求解軟硬時間窗共存情況下的車輛路徑問題的改進遺傳算法，設計改進的交叉和變異準則，以避免問題陷入局部最優解。彭鑫等構建帶混合時間窗的車輛路徑問題的數學模型，引入優良基因及最優個體保護策略改進遺傳算法。

解決車輛路徑問題VRP（Vehicle Routing Problem），使用較多的是遺傳算法，但遺傳算法存在早熟收斂問題，容易使算法陷入局部最優解。而蟻群算法具有正反饋機制和并行計算等優點，能夠快速發現較好解并在各領域得到廣泛應用。本文利用改進蟻群算法并采用偽隨機規則求解帶軟硬時間窗的車輛路徑問題，尋求最小成本路徑。并探討偽隨機因子對解的影響，尋找最優偽隨機因子。最后利用Matlab數值仿真論證該方法的有效性。

1問題描述和模型

1.1問題描述

本文研究的帶混合時間窗的車輛路徑問題VRPSHTW（vehicle Routing Problem with Soft and Hard Time Windows），可以描述為：某固定配送中心派發車輛，給已知的客戶點進行配送，每個客戶點只允許一輛車服務且每個客戶點都有相應的配送時間、服務時間和貨物需求量。車輛完成配送任務后，最后再返回到配送中心。車輛在配送過程中，需滿足三個約束條件：（1）車輛不允許超載。（2）車輛的行駛距離不允許超過其最大行駛距離。（3）對于特定客戶點，訪問車輛必須在該時間窗口內服務，早到必須等待;對于一般客戶點，訪問車輛早于或晚于時間窗將受到懲罰。在滿足所有約束條件下，求解最佳配送方案，以達到降低成本的目的。

1.2模型建立

2算法設計

2.1求解VRPSHTW的ACO算法執行流程

初始解構造的算法流程如圖1所示：

初始化所有參數，設置當前迭代次數iter=l，最大迭代次數iter max，螞蟻數目m，信息素揮發系數p，信息素重要程度因子α，啟發函數重要程度因子β，信息素釋放總量Q。且每只螞蟻按照轉移概率規則選擇下一個將訪問的節點，并判斷訪問的節點是否滿足以下約束：（1）該節點未訪問過;（2）滿足車輛最大行駛距離;（3）滿足車輛最大載重限制;（4）滿足特殊節點的硬時間窗口限制。構建解空間。

2.2路徑轉移規則

當螞蟻完全依賴隨機概率規則訪問下一個節點，僅由式（10）決定;當采用偽隨機概率選擇規則，螞蟻從i移動到j節點的規則由式（9）和式（10）共同決定。

2.3信息素更新規則

信息素更新方式分為兩種方式：局部更新信息素和全局更新信息素。這里采用全局更新信息素的方法，其更新規則如下：

2.4偽隨機因子的改進

偽隨機選擇規則涉及參數偽隨機因子q。，其參數取值仍處在探索階段，直接影響運算結果和解的好壞。本文將對偽隨機因子的取值進行探討，選擇最好的q。值，提高解質量。

3仿真分析

3.1數據集

為測試改進的蟻群算法求解VRPSHTW問題效果，應用文獻中的實例進行分析比較，車輛最大載荷25，車輛最大行駛距離300，車輛固定發車成本150，單位運輸成本為1，包括配送中心1節點共有15個節點。實例選取節點4、7和11作為硬時間窗約束，每個節點的數據如表1和表2所示，且不滿硬時間窗約束的及節點將重新返回到配送中心。

3.2試驗結果

（1）當算法采用隨機概率規則（僅使用輪盤賭法訪問下個節點），即此時偽隨機因子值不存在。結果如圖2和表4所示：

（2）當算法采用偽隨機概率規則時，既可以利用關于問題的先驗性知識，又可以進行傾向性的探索新路徑。而在蟻群算法中，參數取值仍處在探索階段，不具有普遍性，包括偽隨機因子，q。取值大小調節螞蟻“利用”和“探索”間的重要性，影響算法性能。由文獻[13-18]可知，偽隨機因子一般取值0.01、0.1、0.7、0.9。這里設偽隨機因子取值分別為0.01、0.1、0.2、0.3、0.4、0.5、0.6、0.7、0.8、0.9。

結果如圖3和表5所示：

從圖2和表4可知，本文設計的蟻群算法求解帶混合時間窗的車輛路徑問題，使解的質量提高了14%。從圖3和表5可知，偽隨機因子取值既不能過大也不能過小。當q。值較大時，螞蟻傾向于選擇信息素濃度（先驗值）較大的路徑，有利于快速找到最優解。當q。值較小時，螞蟻傾向于隨機選擇，有利于找到最新解。如何調節q。值大小，對運算結果有一定影響。根據仿真結果，當q。值為0.5時，取得最優解且平均解最優，對應最優成本1074.9元，解的質量在原改進基礎上又提高了3%。總優化率17%。

4結論

本文根據客戶對時間緊迫性要求不一致的情形，優化軟硬時間窗下的車輛路徑。構建VRPSHTW模型，利用改進蟻群算法，分別采用隨機規則和偽隨機規則，同時采用改進后的螞蟻轉移概率公式。并且該算法對晚于約定時間的硬時間窗客戶做重新返回到配送中心的處理。再討論偽隨機因子對解的影響并找到最好q。值。通過Matlab數值仿真，與遺傳算法計算結果比較，結果表明：改進蟻群算法可以得到更優的車輛配送方案。

（1）改進蟻群算法解決軟硬時間窗車輛調度問題，可得到最優解。較參考文獻中遺傳算法，優化率提高了17%。

（2）采用偽隨機規則比隨機規則得到的解更優。當偽隨機因子取值0.5時，解的質量最好。