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

楊婷 韓冬桂 燕怒 劉芳

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

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

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

0引言

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

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

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

1問題描述和模型

1.1問題描述

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

1.2模型建立

2算法設(shè)計

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

初始解構(gòu)造的算法流程如圖1所示：

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

2.2路徑轉(zhuǎn)移規(guī)則

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

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

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

2.4偽隨機因子的改進

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

3仿真分析

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

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

3.2試驗結(jié)果

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

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

結(jié)果如圖3和表5所示：

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

4結(jié)論

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

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

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