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

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

　　《車世界》以馬列主義、毛澤東思想、鄧小平理論和“三個代表”重要思想為指導，全面貫徹黨的教育方針和“雙百方針”，理論聯(lián)系實際，開展教育科學研究和學科基礎理論研究，交流科技成果，促進學院教學、科研工作的發(fā)展，為教育改革和社會主義現(xiàn)代化建設做出貢獻。

　　0引言

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

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

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

　　1問題描述和模型

　　1.1問題描述

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

　　1.2模型建立

　　2算法設計

　　2.1求解VRPSHTW的ACO算法執(zhí)行流程

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

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

　　2.2路徑轉移規(guī)則

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

　　2.3信息素更新規(guī)則

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

　　2.4偽隨機因子的改進

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

　　3仿真分析

　　3.1數(shù)據(jù)集

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

　　3.2試驗結果

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

　　(2)當算法采用偽隨機概率規(guī)則時，既可以利用關于問題的先驗性知識，又可以進行傾向性的探索新路徑。而在蟻群算法中，參數(shù)取值仍處在探索階段，不具有普遍性，包括偽隨機因子，q。取值大小調節(jié)螞蟻“利用”和“探索”間的重要性，影響算法性能。由文獻[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。值較大時，螞蟻傾向于選擇信息素濃度(先驗值)較大的路徑，有利于快速找到最優(yōu)解。當q。值較小時，螞蟻傾向于隨機選擇，有利于找到最新解。如何調節(jié)q。值大小，對運算結果有一定影響。根據(jù)仿真結果，當q。值為0.5時，取得最優(yōu)解且平均解最優(yōu)，對應最優(yōu)成本1074.9元，解的質量在原改進基礎上又提高了3%。總優(yōu)化率17%。

　　4結論

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

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

　　(2)采用偽隨機規(guī)則比隨機規(guī)則得到的解更優(yōu)。當偽隨機因子取值0.5時，解的質量最好。