孫滬增，李章維，秦子豪，周曉根，張貴軍

1(浙江工業(yè)大學(xué) 信息工程學(xué)院，杭州 310023)

2(美國(guó)密歇根大學(xué)安娜堡分校 計(jì)算醫(yī)學(xué)與生物信息學(xué)系，美國(guó) 密歇根州 48109)

E-mail:zgj@zjut.edu.cn

1 引 言

隨著互聯(lián)網(wǎng)技術(shù)的迅速發(fā)展，傳統(tǒng)物流配送產(chǎn)業(yè)的優(yōu)化轉(zhuǎn)型已迫在眉睫.車輛路徑問(wèn)題作為物流配送產(chǎn)業(yè)研究的熱點(diǎn)問(wèn)題之一，對(duì)物流產(chǎn)業(yè)的轉(zhuǎn)型升級(jí)有著指導(dǎo)意義.考慮時(shí)間窗因素的車輛路徑問(wèn)題(VRPTW)，更加符合實(shí)際配送問(wèn)題需求.因此，VRPTW問(wèn)題得到國(guó)內(nèi)外學(xué)術(shù)和產(chǎn)業(yè)界的廣泛關(guān)注[1].

VRPTW是一個(gè)NP-hard組合優(yōu)化問(wèn)題，傳統(tǒng)的精確算法只能解決規(guī)模相對(duì)較小的問(wèn)題，且耗時(shí)較長(zhǎng)，而現(xiàn)實(shí)物流配送往往涉及大規(guī)模的客戶群體，因此元啟發(fā)式算法由于其較好的收斂性往往成為解決此類問(wèn)題的首選方案.這也促使了國(guó)內(nèi)外學(xué)者對(duì)VRPTW問(wèn)題轉(zhuǎn)向了元啟發(fā)式算法的研究.Alzaqebah等提出了一種通過(guò)限制差解的最大數(shù)量來(lái)避免人工蜜蜂盲目搜索，從而提高VRPTW收斂速度的優(yōu)化人工蜂群算法[2]；Nalepa等提出了一種能夠平衡搜索空間的探索和利用的自適應(yīng)模擬算法來(lái)解決VRPTW問(wèn)題[3]；李珍萍等建立了多需求混合整數(shù)規(guī)劃模型，設(shè)計(jì)了一種求解模型的聯(lián)合優(yōu)化遺傳算法，為解決實(shí)際問(wèn)題提供了決策依據(jù)[4]；李兵飛等設(shè)計(jì)了一種改進(jìn)的雙重進(jìn)化人工蜂群算法來(lái)求解速度時(shí)變VRPTW問(wèn)題，并通過(guò)實(shí)例驗(yàn)證了模型和求解方法的有效性[5]；Akpinar等提出了一種蟻群系統(tǒng)和大鄰域搜索的混合算法，使得在求解過(guò)程大大提高了算法的多樣性[6]；Osaba等提出了一種漸進(jìn)式離散螢火蟲(chóng)算法，成功將螢火蟲(chóng)算法應(yīng)用到VRPTW問(wèn)題的求解[7].

以上VRPTW問(wèn)題的研究主要針對(duì)測(cè)試數(shù)據(jù)集來(lái)驗(yàn)證算法的有效性.然而，結(jié)合實(shí)際路網(wǎng)的算法應(yīng)用在現(xiàn)有文獻(xiàn)中還鮮有報(bào)道.本文針對(duì)帶時(shí)間窗的車輛路徑問(wèn)題，設(shè)計(jì)了一種基于局部增強(qiáng)搜索策略混合的蟻群算法，通過(guò)標(biāo)準(zhǔn)數(shù)據(jù)集的測(cè)試驗(yàn)證了算法對(duì)不同類型、不同時(shí)間窗寬度VRPTW的適用性；進(jìn)一步基于浙江省杭州市路網(wǎng)數(shù)據(jù)集，基于ArcGIS平臺(tái)，設(shè)計(jì)并開(kāi)發(fā)了一套物流配送系統(tǒng).

2 帶時(shí)間窗的車輛路徑問(wèn)題數(shù)學(xué)模型

假定模型配送中心只有一個(gè)，本文考慮如下VRPTW的數(shù)學(xué)模型[8,9,14,15]：

(1)

(2)

(3)

(4)

(5)

(6)

目標(biāo)函數(shù)(1)表示完成所有客戶配送成本最??；約束(2)表示每輛車配送的客戶需求總數(shù)不能大于車的最大裝載量；式(5)表示每個(gè)客戶點(diǎn)有且僅有一輛車為其服務(wù)；式(6)表示所有客戶點(diǎn)有且僅被配送一次；在上述模型基礎(chǔ)上引入如下時(shí)間窗約束條件：

(7)

如果違反時(shí)間窗約束條件就需要進(jìn)行懲罰.設(shè)客戶i的時(shí)間窗范圍為[ai,bi]，Ti為車輛到達(dá)客戶i的時(shí)間，其中：ai為顧客i允許的最早服務(wù)時(shí)間，bi為顧客i允許的最遲服務(wù)時(shí)間.e為懲罰系數(shù)；半軟時(shí)間窗約束允許車輛到達(dá)i的時(shí)間早于ai但不允許晚于bi，早于ai配送客戶點(diǎn)i，必須等待至ai再為客戶i服務(wù)，因此需要支付一定的懲罰費(fèi)用p(Ti)=e(ai-Ti)2，遲于bi配送的客戶點(diǎn)i則通過(guò)后續(xù)的時(shí)間窗約束直接剔除.

3 基于混合局部增強(qiáng)搜索策略的蟻群算法

蟻群算法是一種模擬大自然螞蟻群體覓食行為的模擬優(yōu)化算法.通過(guò)螞蟻間信息素交互的正反饋機(jī)制，蟻群算法往往能較快地收斂于最優(yōu)解；但也是由于這種正反饋?zhàn)饔昧?，算法往往容易陷入局部最?yōu)解，無(wú)法每次都能快速地收斂于全局最優(yōu)解[10].因此本文在蟻群系統(tǒng)的基礎(chǔ)上引入了局部搜索等策略，通過(guò)對(duì)蟻群算法每代最優(yōu)解進(jìn)行局部搜索指導(dǎo)，提高了算法的全局搜索能力與收斂速度，進(jìn)而能夠避免算法早熟、停滯.

3.1 改進(jìn)的蟻群算法

1)路徑構(gòu)造過(guò)程

本文采用的路徑構(gòu)造方式與傳統(tǒng)的VRP問(wèn)題路徑構(gòu)造方式有所不同.通常的構(gòu)造方式，每只螞蟻產(chǎn)生的子回路僅是一個(gè)可行解的一部分，獲得一個(gè)完整的可行解需要各螞蟻產(chǎn)生的子回路組合來(lái)生成一些可行解，當(dāng)然也可能沒(méi)有可行解；這種路徑構(gòu)造方式生成的可行解往往需要通過(guò)對(duì)大量的子回路組合產(chǎn)生，在一定程度上影響了算法的效率，也無(wú)法很好地保證每次迭代可以出現(xiàn)較好的可行解[11].

而本文改進(jìn)的路徑構(gòu)造方式為一只螞蟻即可產(chǎn)生一個(gè)可行解，結(jié)合多種策略可以保證獲得較優(yōu)的解.每只螞蟻通過(guò)并行的方式隨機(jī)從各客戶結(jié)點(diǎn)出發(fā)，根據(jù)狀態(tài)轉(zhuǎn)移規(guī)則和確定性與隨機(jī)性選擇相結(jié)合的選擇策略來(lái)指導(dǎo)螞蟻選擇下一個(gè)需要配送的客戶，并實(shí)時(shí)更新自身的禁忌表用來(lái)指導(dǎo)后續(xù)路徑構(gòu)造過(guò)程[12,16].

(8)

(9)

其中：τij為信息素濃度；ηij=demandj/dij為啟發(fā)因子，demandj為客戶j的貨物需求量，dij為客戶i,j之間成本；widthj為客戶j的時(shí)間窗寬度，時(shí)間窗越緊，優(yōu)先配送級(jí)別相對(duì)較高；waitj為車輛在配送客戶j時(shí)需要等待的時(shí)間，當(dāng)車輛早于客戶j時(shí)間窗到達(dá)，就需要等待，等待時(shí)間越長(zhǎng)會(huì)影響配送效率、增加配送成本.當(dāng)車輛在客戶j時(shí)間窗內(nèi)到達(dá)，在j的等待時(shí)間waitj=0，在算法中取一個(gè)極小值；savej為從客戶i配送到客戶j比從客戶i回到配送中心，再?gòu)呐渌椭行某霭l(fā)到客戶j的節(jié)約量；allowedk為未配送的客戶集合；α,β,γ,θ,ω分別為各影響因素的權(quán)重因子；r為[0,1]之間的隨機(jī)數(shù)；r0為[0,1]之間的常數(shù)，用來(lái)控制轉(zhuǎn)移規(guī)則.當(dāng)r>r0時(shí)，算法依概率選擇下一個(gè)配送的客戶點(diǎn)，當(dāng)r≤r0時(shí)，算法根據(jù)輪盤賭策略偽隨機(jī)選擇客戶點(diǎn).

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

當(dāng)所有螞蟻構(gòu)造完成一次可行解時(shí)，算法進(jìn)行全局信息素更新，根據(jù)精英螞蟻策略[13]更新全局信息素，對(duì)于精英螞蟻額外進(jìn)行一次信息素累加，這種策略體現(xiàn)了算法的正反饋特性，但經(jīng)過(guò)幾代計(jì)算后易導(dǎo)致某個(gè)較好解路徑上的信息素濃度過(guò)高，從而陷入局部最優(yōu).因此算法引入最大最小信息素策略(MMACA)，把信息素濃度限制在[τmin(t),τmax(t)]區(qū)間[13]內(nèi)，并根據(jù)每代產(chǎn)生的最優(yōu)路徑來(lái)動(dòng)態(tài)更新最大最小信息素，使算法具有較好的自適應(yīng)性.信息素更新規(guī)則[14,17]如下：

τij(t+n)=(1-ρ)*τij(t)+Δτij

(10)

(11)

(12)

(13)

采用全局信息素更新策略來(lái)指導(dǎo)螞蟻的結(jié)點(diǎn)選擇過(guò)程，雖然考慮了信息素的反饋，但仍具有一定的延遲性，不能及時(shí)地引導(dǎo)蟻群尋找最優(yōu)路徑.有不少學(xué)者結(jié)合構(gòu)造性的貪婪算法來(lái)指導(dǎo)局部信息素更新，這樣往往能在算法早期獲得一個(gè)較優(yōu)解，把該解作為模擬退火算法的初始解，進(jìn)行全局優(yōu)化搜索，往往可以獲得更優(yōu)解.算法中結(jié)合實(shí)際問(wèn)題利用提前可知的先驗(yàn)知識(shí)來(lái)指導(dǎo)結(jié)點(diǎn)的選擇，譬如配送完客戶點(diǎn)i之后必須立馬配送客戶點(diǎn)j,這類先驗(yàn)知識(shí)往往可以使算法有較好的運(yùn)算效率.

3.2 算法描述

為了彌補(bǔ)蟻群算法容易進(jìn)入局部?jī)?yōu)解的特點(diǎn)，在算法的不同階段采用不同的策略，從而擴(kuò)大搜索空間，獲得全局最優(yōu)解.

3.2.1 局部搜索策略

算法在螞蟻構(gòu)造路徑的過(guò)程中以及迭代出全局較好路徑時(shí)對(duì)解進(jìn)行局部搜索，從而有概率通過(guò)差解或較優(yōu)解產(chǎn)生全局最優(yōu)解.算法中充分利用了1-Relocate、2-Relocate、2-opt、2-opt*、Exchange以及Exchange*局部搜索算子對(duì)可行解的子回路以及子回路之間進(jìn)行路徑改進(jìn)優(yōu)化，分別如圖1-圖6所示.

1)1-Relocate算子路徑改進(jìn)

算法對(duì)同一子路徑內(nèi)的兩客戶結(jié)點(diǎn)進(jìn)行1-Relocate算子改造，將前一客戶結(jié)點(diǎn)插入到后一客戶結(jié)點(diǎn)之后，若改造后的解符合約束條件，且成本比改造前的子路徑低則保留改造結(jié)果，反之則不保留.

圖1 子回路內(nèi)頂點(diǎn)重定向

2)2-Relocate算子路徑改進(jìn)

圖2 子回路間點(diǎn)頂點(diǎn)重定向

算法對(duì)不同子路徑間的兩客戶結(jié)點(diǎn)進(jìn)行2-Relocate算子改造，將前一客戶結(jié)點(diǎn)插入到后一客戶結(jié)點(diǎn)之后，若改造后的解符合約束條件，且成本比改造前的子路徑低則保留改造結(jié)果，反之則不保留.

3)2-opt算子路徑改進(jìn)

算法對(duì)同一子路徑的兩客戶結(jié)點(diǎn)之間的所有結(jié)點(diǎn)進(jìn)行2-opt算子改造，將這些客戶結(jié)點(diǎn)反向插入原先的隊(duì)列，若改造后的子回路符合約束條件，且成本比改造前的子路徑低則保留改造結(jié)果，反之則不保留.

圖3 子回路內(nèi)2-opt

4)2-opt*算子路徑改進(jìn)

算法對(duì)不同子路徑間的兩客戶結(jié)點(diǎn)之間的所有結(jié)點(diǎn)進(jìn)行2-opt*算子改造，將前一客戶結(jié)點(diǎn)插入到后一客戶結(jié)點(diǎn)之后，若改造后的每個(gè)子回路都符合約束條件，且總成本比改造前的子路徑低則保留改造結(jié)果，反之則不保留.

圖4 子回路間2-opt*

5)Exchange算子路徑改進(jìn)

算法對(duì)同一子路徑內(nèi)的兩客戶結(jié)點(diǎn)進(jìn)行Exchange算子改造，將兩結(jié)點(diǎn)互換位置，若改造后的子回路符合約束條件，并且成本比改造前的子路徑低則保留改造結(jié)果，反之則不保留.

圖5 子回路內(nèi)交換

6)Exchange*算子路徑改進(jìn)

算法對(duì)不同子路徑間的兩客戶結(jié)點(diǎn)進(jìn)行Exchange*算子改造，將兩結(jié)點(diǎn)互換位置，若改造后的都符合約束條件，且總成本比改造前低則保留改造結(jié)果，反之則不保留.

圖6 子回路間交換

3.2.2 動(dòng)態(tài)更新信息素?fù)]發(fā)以及轉(zhuǎn)移規(guī)則參數(shù)策略

當(dāng)算法的當(dāng)前代最優(yōu)解和前代最優(yōu)解連續(xù)n代的差值小于信息素?fù)]發(fā)率ρ更新的臨界閾值RHO，則說(shuō)明算法可能陷入了局部最優(yōu).將信息素?fù)]發(fā)率ρ逐代增加，直至出現(xiàn)新的全局最優(yōu)解；若經(jīng)過(guò)2n代計(jì)算仍然沒(méi)有搜索出新的最優(yōu)解，將信息素?fù)]發(fā)率ρ逐代減小，加速算法收斂，最終輸出全局最優(yōu)解.

在算法早期，設(shè)置較大的轉(zhuǎn)移規(guī)則參數(shù)r0，進(jìn)行確定性搜索，使算法加速收斂到較優(yōu)解；在算法中期，設(shè)置較小的r0，進(jìn)行探索性搜索，擴(kuò)大搜索空間，擺脫算法容易陷入局部?jī)?yōu)解的缺點(diǎn)；在算法后期，設(shè)置較大的r0，加快收斂速度，在局部空間搜索最優(yōu)解，提高算法運(yùn)算效率.即(NCmax為算法最大迭代次數(shù))：

(14)

3.2.3 算法步驟

算法步驟及流程圖如圖7所示：

1)參數(shù)初始化：最大迭代次數(shù)NCmax、信息素初始濃度τij、最大最小信息素系數(shù)C、螞蟻數(shù)K、車輛最大載貨量Qk、狀態(tài)轉(zhuǎn)移概率中的權(quán)重因子α,β,γ,θ,ω、信息素?fù)]發(fā)率ρ、蟻周系統(tǒng)參數(shù)O以及客戶點(diǎn)數(shù)據(jù)等參數(shù).

2)初始化蟻群，令各螞蟻隨機(jī)從各客戶結(jié)點(diǎn)出發(fā).

3)子回路構(gòu)造：根據(jù)狀態(tài)轉(zhuǎn)移規(guī)則和確定性與隨機(jī)性選擇相結(jié)合的選擇策略公式(8),公式(9)選擇下一節(jié)點(diǎn)，通過(guò)時(shí)間窗和載貨量約束來(lái)逐步增加禁忌表中的客戶點(diǎn).

4)若禁忌表未滿，則跳轉(zhuǎn)回步驟(3).

5)若禁忌表已滿，得到可行解.對(duì)可行解進(jìn)行局部搜索策略優(yōu)化解，根據(jù)公式(10)，公式(11)，公式(12)更新?lián)]發(fā)后的信息素和螞蟻分泌的信息素增量.

6)若產(chǎn)生更優(yōu)解，保存當(dāng)前最優(yōu)解，根據(jù)公式(13)動(dòng)態(tài)更新信息素最大最小值.

7)完成一次迭代后根據(jù)精英螞蟻策略(11)對(duì)全局信息素更新，對(duì)全局信息素進(jìn)行最大最小信息素策略修正，并根據(jù)信息素?fù)]發(fā)策略動(dòng)態(tài)更新ρ.

8)NC=NC+1，根據(jù)轉(zhuǎn)移規(guī)則參數(shù)策略動(dòng)態(tài)更新r0，若NC

4 實(shí)驗(yàn)結(jié)果與分析

實(shí)驗(yàn)數(shù)據(jù)集選取Solomon標(biāo)準(zhǔn)測(cè)試數(shù)據(jù)集[15]，客戶點(diǎn)規(guī)模為100.算法使用java語(yǔ)言來(lái)實(shí)現(xiàn)，實(shí)驗(yàn)環(huán)境為:Intel(R)Core(TM)i7-6700HQ CPU@2.60 GHz with 8GB RAM,Window10,算法代碼運(yùn)行平臺(tái)使用IntelliJ IDEA 2017.本文對(duì)算法的參數(shù)進(jìn)行大量組合測(cè)試用來(lái)選擇較合理的參數(shù)組合，最終選?。害?β,γ,θ,ω,ρ的值為(3.0，4.0，1.0，3.0，2.0，0.8)；NCmax設(shè)為50代，信息素?fù)]發(fā)率ρ為0.8，蟻周系統(tǒng)常系數(shù)O為500.0，信息素初始濃度τij為1.0，MMAS系數(shù)C為200.0；1-Relocate、2-opt以及Exchange算子一次迭代的優(yōu)化次數(shù)為5次，2-Relocate、2-opt*以及Exchange*算子一次迭代的優(yōu)化次數(shù)為3次.表1是算法程序?qū)Σ糠譁y(cè)試數(shù)據(jù)集C101、C105、C106、C107、C108(最優(yōu)解全為828.937)均運(yùn)行30次的實(shí)驗(yàn)結(jié)果，其中求出最好解的概率SR，求出最優(yōu)解時(shí)的平均迭代次數(shù)BI，平均計(jì)算時(shí)間T.

圖7 算法流程圖

為驗(yàn)證引入的策略在迭代過(guò)程中對(duì)算法探索全局最優(yōu)解的優(yōu)化改進(jìn)，本文列出了算法對(duì)C108數(shù)據(jù)集測(cè)試30次產(chǎn)生的平均每代最優(yōu)解圖，如圖8所示.

由表1可知，在較短的最大迭代數(shù)限制下，基本的蟻群算法基本無(wú)法得到全局最優(yōu)解，而本文改進(jìn)的蟻群算法幾乎都在50代之內(nèi)收斂到了最優(yōu)解，并且在運(yùn)算效率上優(yōu)于基本蟻群算法，而從圖8中分析得出，算法在迭代過(guò)程中多次陷入局部最優(yōu)解，但本文引入的策略可以有效地增強(qiáng)算法全局搜索能力，使算法擺脫局部最優(yōu)，最終收斂到全局最優(yōu).

表1 在50代之內(nèi)算法數(shù)據(jù)集測(cè)試表

Table 1 Algorithm data set test within 50 generations

求解算法基本蟻群算法SR/%BIT/s本算法SR/%BIT/sC10110.0322100.011C1050.0--100.022C1060.0--100.011C1070.0--100.0135C1080.0--96.67258

圖8 測(cè)試C108數(shù)據(jù)集30次每代最優(yōu)解平均值趨勢(shì)圖

5 案例應(yīng)用

基于上述算法，針對(duì)浙江省杭州市實(shí)際路網(wǎng)數(shù)據(jù)，利用ArcGIS平臺(tái)開(kāi)發(fā)了物流配送管理系統(tǒng)，實(shí)現(xiàn)運(yùn)輸任務(wù)、運(yùn)輸規(guī)劃等功能.系統(tǒng)以該地區(qū)地理信息數(shù)據(jù)為基礎(chǔ)，通過(guò)對(duì)數(shù)據(jù)進(jìn)行轉(zhuǎn)彎要素、道路等級(jí)以及方向要素、網(wǎng)絡(luò)連通性[6,16]、屬性賦值等手段來(lái)構(gòu)建實(shí)際路網(wǎng)模型，并通過(guò)Dijkstra算法[10,17]得到配送中心和各商場(chǎng)之間的最短距離和最短時(shí)間，從而獲取最短距離和最短時(shí)間的OD成本矩陣；本文以圖9為例說(shuō)明，針對(duì)某物流公司日常需要將貨物從配送中心運(yùn)送到25家商場(chǎng)的實(shí)際VRPTW問(wèn)題，圖中配送中心和所有商場(chǎng)分布用數(shù)字1～25表示，配送中心和商場(chǎng)的貨物需求量、時(shí)間窗口以及卸貨所需時(shí)間等信息如表2所示；配送中心和所有商場(chǎng)之間的最短時(shí)間OD成本部分?jǐn)?shù)據(jù)如表3所示.算法的主要目標(biāo)是為物流公司生成一組貨車車隊(duì)，車隊(duì)中的每輛卡車分配一組所要服務(wù)的商場(chǎng)，并確定送貨的順序，從而將總配送成本控制在最低.

圖9 商場(chǎng)及配送中心分布圖

表2 配送中心和25個(gè)客戶點(diǎn)信息

Table 2 Distribution center and 25 customer information

0～12節(jié)點(diǎn)0123456789101112需求量/磅0170615331580128913021775101417611815170910451414開(kāi)始時(shí)間9:0014:5414:209:2513:429:0613:0110:0610:3912:2711:1811:5413:13結(jié)束時(shí)間17:0015:1514:389:5714:049:2613:3310:2711:0612:5511:3912:1613:40卸貨時(shí)間/分010813101213810121081213～25節(jié)點(diǎn)13141516171819202122232425需求量/磅1863179113731962187210561950136415251767105315931469開(kāi)始時(shí)間9:1212:4011:2912:059:3810:1010:489:0414:5514:1513:449:2510:06結(jié)束時(shí)間9:3613:0111:4712:259:5710:3911:149:2815:1514:4314:029:5610:27卸貨時(shí)間/分10118108121310101210128

篇幅有限，表3只給出了其中15個(gè)商場(chǎng)與配送中心之間的OD成本矩陣，從上述數(shù)據(jù)中可以發(fā)現(xiàn)實(shí)際路徑問(wèn)題中客戶點(diǎn)i配送到客戶點(diǎn)j的成本與客戶點(diǎn)j配送到客戶點(diǎn)i是有差別的，這比常規(guī)VRP問(wèn)題中僅僅靠計(jì)算各客戶點(diǎn)坐標(biāo)之間的歐式距離作為成本更符合實(shí)際情況.

1)無(wú)時(shí)間窗約束車輛配送問(wèn)題應(yīng)用

本案例應(yīng)用中25家商場(chǎng)散落在城市的四周，貨車必須經(jīng)過(guò)復(fù)雜的城市路網(wǎng)才能配送下個(gè)商場(chǎng)，使用的貨車的最大裝載量為15000磅；貨車司機(jī)的費(fèi)用為每小時(shí)75元，貨車的燃料消耗、日常維護(hù)等費(fèi)用為每千米6元；由于長(zhǎng)期駕駛會(huì)導(dǎo)致疲勞駕駛，公司規(guī)定一次配送司機(jī)駕駛時(shí)間不能超過(guò)7小時(shí)(不包含等待服務(wù)時(shí)間)；算法對(duì)于沒(méi)有時(shí)間窗同時(shí)符合上述要求的最優(yōu)配送方案如圖10所示.此方案配送一次公司的費(fèi)用成本約為1866.9元，其中第一輛貨車配送路線“1”為：0-21-20-24-25-23-10-22-9-0，貨車裝載量為12295磅，司機(jī)花費(fèi)約6.77小時(shí)完成此次配送；其中第二輛貨車配送路線“2”為：0-19-18-17-8-1-2-3-15-0，貨車裝載量為12831磅，司機(jī)花費(fèi)約6.47小時(shí)完成此次配送；其中第三輛貨車配送路線“3”為：0-16-13-4-7-6-11-12-5-14-0，貨車裝載量為13455磅，司機(jī)花費(fèi)約6.15小時(shí)完成此次配送.

表3 配送中心和15個(gè)客戶點(diǎn)之間的最短時(shí)間OD成本矩陣(分鐘)

Table 3 Minimum time OD cost matrix between distribution center and 15 customer(min)

00.0012.5912.278.3011.8110.5217.3213.7217.3716.0420.7216.2710.708.887.674.75112.660.004.364.596.219.8414.549.7516.7426.1130.7816.9511.329.3811.928.44212.434.370.004.582.486.1211.837.7617.0825.1129.7913.237.596.208.748.4338.474.594.570.004.748.2514.1010.0214.0221.9226.5915.499.856.378.134.26411.916.202.484.720.003.869.695.6117.2324.5729.2411.085.453.726.268.58510.199.926.208.013.950.009.786.1820.9421.8526.5310.733.123.383.538.92617.3814.8411.9614.209.799.780.006.8326.7129.0433.727.658.7712.0310.8316.21713.599.757.8110.055.645.996.570.0022.5625.2529.927.914.978.247.0312.42817.5816.3516.6313.6016.8020.4426.1522.070.0031.7336.4127.5521.9119.0019.8514.66916.4225.8324.9821.6424.5222.3929.1925.5932.910.0015.5728.1422.5721.5519.5418.721020.1329.5328.6925.3428.2326.1032.8929.3036.6214.740.0031.8526.2725.2623.2422.431116.3116.6912.9715.2110.8010.577.697.9227.7127.9632.630.009.1812.8211.6115.341210.6611.337.619.855.443.448.805.1122.3522.3227.009.300.004.963.308.79138.929.396.186.393.703.7211.537.9419.3921.5726.2512.494.700.002.635.97147.6011.928.728.066.233.8710.777.1720.2519.5524.2311.733.302.630.005.85155.038.348.364.068.539.1216.0212.4315.1218.6723.3415.888.725.915.800.000123456789101112131415

圖10 無(wú)時(shí)間窗配送方案

2)帶時(shí)間窗約束車輛配送問(wèn)題應(yīng)用

然而實(shí)際VRP問(wèn)題一般都帶有時(shí)間窗約束，在算法中加入表2的各商場(chǎng)的時(shí)間窗約束后求出的最優(yōu)配送方案如圖11所示.此方案配送一次公司的費(fèi)用成本約為2106.1元，其中第一輛貨車配送路線“1”為：0-20-24-25-10-9-23-22-21-0，貨車裝載量為12295磅，司機(jī)花費(fèi)約6.55小時(shí)完成此次配送，由于提前到達(dá)商場(chǎng)而等待商場(chǎng)開(kāi)始服務(wù)的等待時(shí)間約為1.38小時(shí)；第二輛貨車配送路線“2”為：0-13-3-8-15-16-14-12-0，貨車裝載量為11744磅，司機(jī)花費(fèi)約4.87小時(shí)完成此次配送，由于提前到達(dá)商場(chǎng)而等待商場(chǎng)開(kāi)始服務(wù)的等待時(shí)間約為0.45小時(shí)；第三輛貨車配送路線“3”為：0-5-7-11-6-4-2-1-0，貨車裝載量為9664磅，司機(jī)花費(fèi)約6.53小時(shí)完成此次配送，由于提前到達(dá)商場(chǎng)而等待商場(chǎng)開(kāi)始服務(wù)的等待時(shí)間約為2.13小時(shí)；第四輛貨車配送路線“4”為：0-17-18-19-0，貨車裝載量為4878磅，司機(jī)花費(fèi)約2.41小時(shí)完成此次配送，由于提前到達(dá)商場(chǎng)而等待商場(chǎng)開(kāi)始服務(wù)的等待時(shí)間約為0.6小時(shí).

圖11 帶時(shí)間窗配送方案

從上述兩種配送方案中進(jìn)行分析，車輛總數(shù)從3輛車變成了4輛，且原先較早配送的節(jié)點(diǎn)可能由于時(shí)間窗約束變成較遲配送的節(jié)點(diǎn)，譬如0號(hào)配送中心到21號(hào)商場(chǎng)的時(shí)間比0號(hào)配送中心到20號(hào)商場(chǎng)要短，但由于21號(hào)商場(chǎng)要求貨物配送服務(wù)的時(shí)間窗為[14:55,15:15],20號(hào)商場(chǎng)的時(shí)間窗為[9:04,9:28]，所以導(dǎo)致20號(hào)商場(chǎng)優(yōu)于21號(hào)商場(chǎng)先進(jìn)行配送服務(wù)，同時(shí)由于0號(hào)配送中心的統(tǒng)一發(fā)車時(shí)間為上午9點(diǎn)，那么20號(hào)商場(chǎng)的貨物配送服務(wù)是非常緊急的，因此其中一輛貨車優(yōu)先去20號(hào)商場(chǎng)進(jìn)行配送服務(wù)；而車輛從3輛增加到4輛的主要原因是由于部分商場(chǎng)的時(shí)間窗比較相近，一輛車無(wú)法在時(shí)間窗約束下滿足這些商場(chǎng)的需求，因此必須派出不同的車輛分別進(jìn)行配送，譬如17號(hào)商場(chǎng)的要求服務(wù)時(shí)間和3號(hào)商場(chǎng)是十分相近的，但由于第二輛貨車在選擇對(duì)3號(hào)商場(chǎng)進(jìn)行配送任務(wù)后是無(wú)法趕到17號(hào)商場(chǎng)進(jìn)行令商場(chǎng)滿意的配送服務(wù)，因此物流公司需要增派一輛貨車對(duì)這些時(shí)間窗與其他車輛配送的商場(chǎng)節(jié)點(diǎn)相近的商場(chǎng)進(jìn)行令客戶滿意的配送服務(wù).

6 結(jié) 論

本文對(duì)帶時(shí)間窗的車輛路徑問(wèn)題進(jìn)行研究，在傳統(tǒng)數(shù)學(xué)模型的基礎(chǔ)上設(shè)計(jì)了一種基于蟻群系統(tǒng)和局部增強(qiáng)搜索策略的蟻群算法，針對(duì)蟻群算法搜索空間小、容易陷入局部最優(yōu)的特點(diǎn)，加入了多種局部搜索算子來(lái)改進(jìn)算法全局探索的能力，同時(shí)引入了動(dòng)態(tài)更新信息素?fù)]發(fā)以及轉(zhuǎn)移規(guī)則參數(shù)策略，來(lái)使算法在運(yùn)行的不同階段動(dòng)態(tài)進(jìn)行自適應(yīng)參數(shù)選擇，進(jìn)而通過(guò)與標(biāo)準(zhǔn)測(cè)試數(shù)據(jù)集比對(duì)表明算法在較短時(shí)間內(nèi)得出滿意解，最后將算法應(yīng)用到實(shí)際案例中，驗(yàn)證了算法在解決具有較大規(guī)模的實(shí)際車輛路徑問(wèn)題的有效性.