基于改進(jìn)蟻群算法的時(shí)間窗約束下物流配送車(chē)輛路徑優(yōu)化研究

摘要：物流配送車(chē)輛路徑優(yōu)化作為一個(gè)涉及多影響因素、多目標(biāo)需求的組合優(yōu)化問(wèn)題，其中帶時(shí)間窗約束的物流配送車(chē)輛路徑優(yōu)化問(wèn)題更是一個(gè)NP難題，較難得到最優(yōu)解。文章分析帶時(shí)間窗約束的車(chē)輛路徑問(wèn)題并建立相應(yīng)數(shù)學(xué)模型，提出將變異和動(dòng)態(tài)信息更新的改進(jìn)蟻群算法應(yīng)用于解決這類(lèi)優(yōu)化問(wèn)題，同時(shí)仿真實(shí)驗(yàn)結(jié)果表明該算法能快速收斂于全局最優(yōu)解，能有效地解決有時(shí)間窗約束下的物流配送車(chē)輛路徑優(yōu)化問(wèn)題。

關(guān)鍵詞：改進(jìn)蟻群算法；時(shí)間窗約束車(chē)輛路徑問(wèn)題；物流配送

一、 引言

物流配送過(guò)程中的車(chē)輛路徑優(yōu)化問(wèn)題（Vehicle Rou-ting Problem，VRP）作為物流配送優(yōu)化的核心環(huán)節(jié)，一方面作為一項(xiàng)物流管理的重要內(nèi)容，它對(duì)整個(gè)物流運(yùn)輸?shù)乃俣取⒊杀尽⑿б嫫鹬陵P(guān)重要的作用；另一方面隨著現(xiàn)代物流配送的快速發(fā)展，物流配送越來(lái)越強(qiáng)調(diào)滿(mǎn)足顧客種類(lèi)、數(shù)量和時(shí)間等方面要求，提升顧客的滿(mǎn)意度。配送車(chē)輛路徑安排這一組合優(yōu)化問(wèn)題最初由Dcmtzing Ramser于1959年提出，一直以來(lái)，作為交通運(yùn)輸和物流配送領(lǐng)域的一個(gè)核心問(wèn)題，也成為一個(gè)運(yùn)籌學(xué)、優(yōu)化科學(xué)等學(xué)界研究的熱點(diǎn)。

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

二、 物流配送車(chē)輛路徑優(yōu)化問(wèn)題的數(shù)學(xué)模型

時(shí)間窗約束下物流配送車(chē)輛路徑優(yōu)化問(wèn)題可以描述為：從配送中心用多輛汽車(chē)向多個(gè)需求點(diǎn)送貨，每個(gè)需求點(diǎn)的位置、需求量和時(shí)間窗約束一定，每輛汽車(chē)的載重量一定，要求合理安排汽車(chē)行駛路線(xiàn)，使總運(yùn)輸成本最小，并滿(mǎn)足以下條件：

1. 每條配送路徑上需求點(diǎn)的需求量之和不超過(guò)汽車(chē)載重量；

2. 每條配送路徑的長(zhǎng)度不超過(guò)汽車(chē)一次配送的最大行駛距離；

3. 每個(gè)需求點(diǎn)的需求量得到滿(mǎn)足，且只能由一輛汽車(chē)送貨；

4. 每個(gè)需求點(diǎn)的時(shí)間窗約束得到滿(mǎn)足，且保證車(chē)輛工作總時(shí)間不超過(guò)其最長(zhǎng)工作時(shí)間。

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

其中，式（1）為目標(biāo)函數(shù)；式（2）保證每條路徑上各需求點(diǎn)的需求量之和不超過(guò)汽車(chē)的重量；式（3）保證每條配送路徑的長(zhǎng)度不超過(guò)汽車(chē)一次配送的最大行駛距離；式（4）、（5）保證車(chē)輛的工作總時(shí)間不超過(guò)最長(zhǎng)工作時(shí)間；（7）表明每條路徑上的需求點(diǎn)都得到配送服務(wù)；式（8）為每條路徑的需求點(diǎn)的組成；式（9）限制每個(gè)需求點(diǎn)只能由一輛汽車(chē)送貨；式（10）第k輛汽車(chē)服務(wù)的客戶(hù)數(shù)大于等于1時(shí)，說(shuō)明該輛車(chē)參加了配送，則取sign（nk）=1，當(dāng)?shù)趉輛汽車(chē)服務(wù)的客戶(hù)小于1時(shí)，表示未使用該車(chē)，取sign（nk）=0。

三、 算法的描述與實(shí)現(xiàn)

螞蟻與配送之間的對(duì)應(yīng)關(guān)系如表1所示。

在螞蟻進(jìn)行路徑搜索時(shí)，如果找到一段很短的子路徑（子解），它就釋放出相應(yīng)濃度的信息素，該信息素一方面直接影響位于子解的兩個(gè)點(diǎn)上的螞蟻；另一方面它會(huì)以該路徑為中心向外擴(kuò)散，影響其路徑附近的其它螞蟻的行為，使它們?cè)趯ふ衣窂綍r(shí)會(huì)以更大的概率在下一步選擇該路徑。同時(shí)在時(shí)間窗約束下螞蟻開(kāi)辟新的路徑遵循以下規(guī)則：從當(dāng)前路徑的最后一個(gè)路口出發(fā)，到所有未訪(fǎng)問(wèn)的路口中開(kāi)始服務(wù)時(shí)間最早的的那個(gè)路口。只有當(dāng)開(kāi)始服務(wù)時(shí)間超過(guò)路口的時(shí)間窗時(shí)，才主動(dòng)開(kāi)辟一條新路徑，并從未訪(fǎng)問(wèn)的路口中重新限制出發(fā)點(diǎn)，將所有未訪(fǎng)問(wèn)過(guò)的路口中開(kāi)始服務(wù)最早的那個(gè)路口作為最新路徑的第一個(gè)路口。通過(guò)這種基于時(shí)間窗約束下信息素?cái)U(kuò)散的協(xié)作方式，一方面指導(dǎo)螞蟻在滿(mǎn)足新的路口時(shí)間窗內(nèi)開(kāi)辟下一路徑，另一方面其他螞蟻在選擇下一個(gè)路口時(shí)選擇到最優(yōu)路徑的干擾性會(huì)降低。從而在滿(mǎn)足各路口的時(shí)間窗要求的同時(shí)使算法的收斂程度大大提高，提升算法搜索的效率和成功率。

具體的算法如下：

Step1：初始化，設(shè)置待定參數(shù)和最大進(jìn)化代數(shù)；

Step2：隨機(jī)選擇每只螞蟻的位置；

Step3：計(jì)算每只螞蟻k將要轉(zhuǎn)移的位置，假設(shè)為j，上一個(gè)位置假設(shè)為i。按所需等待時(shí)間較短和時(shí)間窗較窄的優(yōu)先原則計(jì)算下一路口j的時(shí)間窗寬度和所在路口i到達(dá)下一路口j的時(shí)間；然后按往下一路口j的路徑長(zhǎng)度以及路徑上的信息量計(jì)算轉(zhuǎn)移概率，計(jì)算公式為：

Step7：若本次循環(huán)中每只螞蟻都執(zhí)行了Step3~Step6，則轉(zhuǎn)至Step8，否則轉(zhuǎn)向Step3。

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

Step9：如果每只螞蟻都完成了一個(gè)完整的路徑，則轉(zhuǎn)向Step10，否則轉(zhuǎn)向Step3。

Step10：是否達(dá)到指定的進(jìn)化代數(shù)或者所求得的解在最近若干代中無(wú)明顯改進(jìn)，如果出現(xiàn)這樣情況，則轉(zhuǎn)向Step11，否則轉(zhuǎn)向Step3。

Step11：輸出優(yōu)化結(jié)果。

四、 仿真實(shí)例

在這篇文章中，應(yīng)用文獻(xiàn)“7”和文獻(xiàn)“10”中提出的算例進(jìn)行仿真。由中心倉(cāng)庫(kù)0向8個(gè)需求點(diǎn)運(yùn)輸貨物（編號(hào)為1，2，…，8），各任務(wù)貨運(yùn)量qi（i=1，2，L，8）、每客戶(hù)所需工作時(shí)間及每項(xiàng)客戶(hù)任務(wù)的時(shí)間窗由表1給出。這些任務(wù)發(fā)出的3輛容量為8噸的車(chē)輛完成，中心倉(cāng)庫(kù)與各客戶(hù)點(diǎn)間及各客戶(hù)點(diǎn)間的距離由表2給出，車(chē)速50，單位運(yùn)輸成本為1，超出時(shí)間窗的單位懲罰為：pe=50，pu=50。

用1，2，L，L表示各需求點(diǎn)，因?yàn)楣灿蠱輛汽車(chē)，最多存在M條配送路線(xiàn)，每條配送路徑都始于配送中心，也終于配送中心。為了在編碼中反映配送路線(xiàn)，采用了增加M-1虛擬配送中心的方法，分別用L+1，L+2，L，L+M-1表示。這樣1，2，L，L+M-1這路徑L+M-1個(gè)互不重復(fù)的自然數(shù)的通知數(shù)的隨機(jī)排列就構(gòu)成了一個(gè)個(gè)體，并對(duì)應(yīng)一種配送路徑方案。并將描述的算法用MATLAB編程，生成NDMACO.m文件運(yùn)行程序。

在同一臺(tái)計(jì)算機(jī)上將本文提出的改進(jìn)蟻群算法運(yùn)算結(jié)果與遺傳算法、基本蟻群算法的求解結(jié)果進(jìn)行比較。

五、 結(jié)論

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

參考文獻(xiàn)：

1. 盛麗俊，周溪召．帶有時(shí)間窗的車(chē)輛路徑問(wèn)題優(yōu)化．上海海事大學(xué)學(xué)報(bào)，2007，（4）:64-67．

2. 姜凌，沈桂蘭．基于蟻群算法的物流配送車(chē)輛路徑優(yōu)化問(wèn)題研究.首都經(jīng)濟(jì)貿(mào)易大學(xué)學(xué)報(bào)，2010，（1）:71-74.

3. 即茂祥，胡思繼.用混合遺傳算法求解物流配送路徑優(yōu)化問(wèn)題的研究.中國(guó)管理科學(xué)，2002，（10）：51-56．

4. 亓霞，陳森發(fā)，黃鹍等.基于免疫算法的物流配送車(chē)輛路徑優(yōu)化問(wèn)題研究.土木工程學(xué)報(bào)，2003，（7）：43-46．

5. 張毅，申彥杰.時(shí)間窗約束下的車(chē)輛路徑問(wèn)題多目標(biāo)優(yōu)化算法.數(shù)學(xué)的實(shí)踐與認(rèn)識(shí)，2009，（7）：124-130．

6. 劉北林，高爽.配送車(chē)輛路徑優(yōu)化問(wèn)題算法研究.商業(yè)經(jīng)濟(jì)，2008，（9）：31-33．

7. 李軍，郭耀煌．物流配送車(chē)輛優(yōu)化調(diào)度理論與方法.北京：中國(guó)物資出版社，2001．

8. 朱慶保，楊志軍.基于變異和動(dòng)態(tài)信息素更新的蟻群優(yōu)化算法．軟件學(xué)報(bào)，2004，（2）：85-92．

9. 肖國(guó)璽，彭玉青，林濤等．基于螞蟻算法的物流配送計(jì)劃的生成.河北工業(yè)大學(xué)學(xué)報(bào)，2005，（4）：163-165．

10. 肖力.基于改進(jìn)蟻群算法的物流配送問(wèn)題研究.計(jì)算機(jī)仿真，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. 李志威，張旭梅．基于動(dòng)態(tài)掃描和螞蟻算法的物流配送網(wǎng)絡(luò)優(yōu)化研究．管理工程學(xué)報(bào)，2006，（4）：9-12．

基金項(xiàng)目：國(guó)家自然科學(xué)基金資助項(xiàng)目“機(jī)動(dòng)多目標(biāo)跟蹤融合策略研究”（項(xiàng)目號(hào)：61005026）。

作者簡(jiǎn)介：張玉春，南京航空航天大學(xué)管理科學(xué)與工程博士，蘭州理工大學(xué)國(guó)際經(jīng)濟(jì)管理學(xué)院副教授、碩士生導(dǎo)師；余炳，蘭州理工大學(xué)國(guó)際經(jīng)濟(jì)管理學(xué)院碩士生；申風(fēng)平，蘭州理工大學(xué)經(jīng)濟(jì)管理學(xué)院教授、碩士生導(dǎo)師。

收稿日期：2010-11-09。