楊婷 韓冬桂 燕怒 劉芳

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

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

中圖分類(lèi)號(hào)：U116.2文獻(xiàn)標(biāo)識(shí)碼：A

0引言

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

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

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

1問(wèn)題描述和模型

1.1問(wèn)題描述

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

1.2模型建立

2算法設(shè)計(jì)

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

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

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

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

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

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

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

2.4偽隨機(jī)因子的改進(jìn)

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

3仿真分析

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

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

3.2試驗(yàn)結(jié)果

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

（2）當(dāng)算法采用偽隨機(jī)概率規(guī)則時(shí)，既可以利用關(guān)于問(wèn)題的先驗(yàn)性知識(shí)，又可以進(jìn)行傾向性的探索新路徑。而在蟻群算法中，參數(shù)取值仍處在探索階段，不具有普遍性，包括偽隨機(jī)因子，q。取值大小調(diào)節(jié)螞蟻“利用”和“探索”間的重要性，影響算法性能。由文獻(xiàn)[13-18]可知，偽隨機(jī)因子一般取值0.01、0.1、0.7、0.9。這里設(shè)偽隨機(jī)因子取值分別為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è)計(jì)的蟻群算法求解帶混合時(shí)間窗的車(chē)輛路徑問(wèn)題，使解的質(zhì)量提高了14%。從圖3和表5可知，偽隨機(jī)因子取值既不能過(guò)大也不能過(guò)小。當(dāng)q。值較大時(shí)，螞蟻傾向于選擇信息素濃度（先驗(yàn)值）較大的路徑，有利于快速找到最優(yōu)解。當(dāng)q。值較小時(shí)，螞蟻傾向于隨機(jī)選擇，有利于找到最新解。如何調(diào)節(jié)q。值大小，對(duì)運(yùn)算結(jié)果有一定影響。根據(jù)仿真結(jié)果，當(dāng)q。值為0.5時(shí)，取得最優(yōu)解且平均解最優(yōu)，對(duì)應(yīng)最優(yōu)成本1074.9元，解的質(zhì)量在原改進(jìn)基礎(chǔ)上又提高了3%。總優(yōu)化率17%。

4結(jié)論

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

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

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