□ 李 沖 □ 錢 靜

江南大學(xué) 機(jī)械工程學(xué)院 江蘇無(wú)錫 214122

帶時(shí)間窗動(dòng)態(tài)車輛路徑問(wèn)題 WTVRP（Vehicle RoutingOptimizationProblemwithTimeWindows）是指一定數(shù)量的工位點(diǎn)，各自需求不同數(shù)量的貨物量，配送中心統(tǒng)一向工位點(diǎn)提供貨物，通過(guò)安排一定順序的行駛路線，使工位點(diǎn)在滿足一定約束條件下，實(shí)現(xiàn)諸如路徑最短、成本值最小、耗費(fèi)時(shí)間最少等目標(biāo)。路線安排過(guò)程中，根據(jù)工位點(diǎn)需求、車輛、運(yùn)輸網(wǎng)絡(luò)等信息是否確定，WTVRP可以分為靜態(tài)車輛路徑問(wèn)題SVRP（StaticVehicleRoutingOptimizationProblem）和動(dòng)態(tài)車輛路徑問(wèn)題DVRP （DymamicVehicleRouting OptimizationProblem）［1］。 其中 DVRP 又包括了工位點(diǎn)需求 VRP、動(dòng)態(tài)車輛 VRP和動(dòng)態(tài)運(yùn)輸網(wǎng)絡(luò) VRP［2-4］。本文主要研究帶時(shí)間窗的動(dòng)態(tài)車輛VRP。

車輛配送過(guò)程中造成動(dòng)態(tài)性主要由于兩個(gè)原因：①現(xiàn)有車輛總載荷小于貨物運(yùn)輸總量，為了完成配送任務(wù)，同一輛車在滿足時(shí)間窗的條件下可能需要進(jìn)行多次指派；②配送過(guò)程中車輛出現(xiàn)故障，需要重新派出車輛替換故障車輛［5］。此外，當(dāng)前對(duì)蟻群算法的研究，大部分都暗含了現(xiàn)有車輛總載荷大于全部運(yùn)輸物料重量這個(gè)假設(shè)，而在實(shí)際生產(chǎn)中，工位配送總需求大于現(xiàn)有車輛載重總和的情況常會(huì)發(fā)生。考慮到運(yùn)輸成本，通常希望完成任務(wù)車輛數(shù)盡可能少，因此需考慮對(duì)部分車輛進(jìn)行多次配送指派。

本文通過(guò)改進(jìn)基本蟻群算法［6-8］，解決了對(duì)車輛進(jìn)行多次派遣的問(wèn)題。在算法實(shí)現(xiàn)中，設(shè)定先完成任務(wù)的車輛即返回原點(diǎn)，判斷其是否滿足其余還未運(yùn)輸路徑的時(shí)間窗來(lái)判斷此輛車是否接受第二次任務(wù)指派，這可以在保證時(shí)間窗的條件下使用較少的車輛數(shù)來(lái)完成任務(wù)，節(jié)省下來(lái)的車輛可以用來(lái)進(jìn)行突發(fā)事件的配送或替代發(fā)生故障的車輛。

1 WTVRP數(shù)學(xué)模型構(gòu)建

WTVRP問(wèn)題是在VRP基礎(chǔ)上提出的，一般定義為：已知n個(gè)工位點(diǎn)坐標(biāo)及貨物需求量，要求用m輛汽車在時(shí)間窗內(nèi)從配送中心送達(dá)。每輛車的最大載荷確定，且每次配送量不能超過(guò)該車的最大載荷。每個(gè)工位點(diǎn)每次需求必須且只能由一輛車來(lái)滿足［9］。筆者將所有車輛在任務(wù)時(shí)間內(nèi)行駛距離最小作為該模型的優(yōu)化目標(biāo)，即：

式中：dij表示從工位i到工位j的行駛距離。

針對(duì)該數(shù)學(xué)模型，約束條件為式（2）～（7）：

式中：Xijk為決策變量，表示第k輛車是否從工位i出發(fā)開向工位j，如果是，其值為1，否則為0。

式中：yik為決策變量，表示工位i的任務(wù)是否由車輛k完成，如果是，其值為1，否則為0。

式中：gi表示工位i的貨物需求量；Qk表示牽引車k最大裝載量。

式 （4）對(duì)車輛裝載量進(jìn)行約束，即每輛車在一條運(yùn)輸路徑上貨物裝載量總和不能大于該車輛最大載荷。

式（5）確保每個(gè)工位的任務(wù)由一輛車來(lái)完成，且每個(gè)工位都得到了服務(wù)。

式（6）防止車輛在同一個(gè)工位點(diǎn)轉(zhuǎn)圈。

式中：ti為車輛到達(dá)工位i的實(shí)際時(shí)間；si為對(duì)工位i的服務(wù)時(shí)間；Ei和Li表示到達(dá)工位i的最早時(shí)間和最晚時(shí)間范圍。

式（7）確保車輛到達(dá)工位時(shí)不超出時(shí)間窗范圍。

2 基本蟻群算法的改進(jìn)

蟻群算法（AntSystem）是一種仿生優(yōu)化算法，具備了并行自催化以及優(yōu)良的分布式計(jì)算機(jī)制，魯棒性較強(qiáng)［10］，該算法最初用來(lái)解決旅行商問(wèn)題 TSP（Traveling SalemanProblem）。而WTVRP的復(fù)雜程度要遠(yuǎn)高于TSP，兩者有一定相似性又存在許多差別。因此設(shè)計(jì)蟻群算法來(lái)求解VRTWP時(shí)，要充分結(jié)合WTVRP的具體要求，并借鑒蟻群算法求解TSP的經(jīng)驗(yàn)。搜索時(shí)間長(zhǎng)，易陷入局部最優(yōu)，這是蟻群算法需要改進(jìn)的缺點(diǎn)。

WTVRP與TSP的不同之處主要體現(xiàn)在表1所示的3個(gè)方面。

表1 WTVRP與TSP蟻群算法求解的差別

2.1 改進(jìn)基本蟻群算法以實(shí)現(xiàn)WTVRP優(yōu)化

Pij（ij）為模型中t時(shí)刻車輛k從工位i到工位j的轉(zhuǎn)移概率，在滿足裝載量和時(shí)間窗前提下，主要由兩方面因素決定：①通往下一城市路徑長(zhǎng)度以及路徑上的信息量；②時(shí)間窗限制因素，即車輛等待時(shí)間較短優(yōu)先原則和時(shí)間窗較小優(yōu)先原則。因此，t時(shí)刻車輛k在工位i對(duì)下一個(gè)工位j的選擇概率為：

式中：τij和ηij分別表示信息素濃度和能見度；α為信息啟式因子；β 為期望啟發(fā)式因子；［ej，lj］表示工位 j點(diǎn)的時(shí)間窗；tij為由工位i到達(dá)工位j所需時(shí)間 （到達(dá)工位i服務(wù)的時(shí)刻+工位i服務(wù)時(shí)間+從工位i到j(luò)的行駛時(shí)間）；ω1和 ω2表示權(quán)重系數(shù)，均∈［0，1］，且有 ω1+ω2=1。

在這里ηij與解決TSP問(wèn)題不同:

式中：ω（j）為在工位j的開始服務(wù)時(shí)間之前到達(dá)所需要的等待時(shí)間。

2.1.2 改進(jìn)信息素更新方式

在基本蟻群算法中，每只螞蟻遍歷的路徑都需要對(duì)其進(jìn)行信息素的更新，這種方式收斂較慢，既拖延了計(jì)算時(shí)間，同時(shí)全局優(yōu)化性能也不明顯。本文保留了全局最優(yōu)解，同時(shí)為了擴(kuò)大信息素更新范圍，避免陷入局部最優(yōu)，選取每次迭代結(jié)果中前幾位的“精英螞蟻”進(jìn)行信息素更新。

針對(duì)基本蟻群算法的缺陷，本文采用如下動(dòng)態(tài)的信息素更新方式:

式中：△τgori為全局最優(yōu)解或迭代最優(yōu)解的倒數(shù)；ρ是信息素?fù)]發(fā)系數(shù)。

在搜索過(guò)程中，先對(duì)局部信息素進(jìn)行更新，當(dāng)?shù)揭欢ù螖?shù)n時(shí)，整個(gè)系統(tǒng)進(jìn)行一次全局信息素更新。接下來(lái)繼續(xù)對(duì)局部最優(yōu)信息素進(jìn)行更新，兩者交叉進(jìn)行，直至達(dá)到算法中規(guī)定的最大迭代次數(shù)Nmax時(shí)停止。這樣可以避免發(fā)生早熟現(xiàn)象，同時(shí)增加解的多樣性，有效提升了算法性能和解的質(zhì)量。

隨著搜索次數(shù)的增加和信息素的更新，某個(gè)可行解上的信息量可能會(huì)出現(xiàn)極大值或極小值：極大值會(huì)導(dǎo)致搜索早熟，算法陷入局部最優(yōu)使搜索停滯；極小值則會(huì)減緩收斂速度使求解過(guò)程延長(zhǎng)。因此將每條軌跡上信息素限制在［τmin，τmax］之間，若 τij≤τmin，則 τij=τmin；若 τij≥τmax，則 τij=τmax。

算法初始時(shí)，信息素尚未更新，使用式（11)、(12）來(lái)確定 τmin和 τmax:

當(dāng)信息素開始更新后則采用式（13）確定 τmax（t）：

式中：Lgb為通過(guò)PFIH算法構(gòu)造初始可行解得到的可行路徑總長(zhǎng)度；σ為精英螞蟻的個(gè)數(shù)，即每次循環(huán)中找出全局最優(yōu)解的螞蟻個(gè)數(shù)；τmin（t）不變。

2．2 蟻群算法參數(shù)組合選擇

在蟻群算法中參數(shù)的選擇直接影響到計(jì)算結(jié)果。根據(jù)具體問(wèn)題不同，需要對(duì)參數(shù)進(jìn)行相應(yīng)調(diào)整，通過(guò)實(shí)驗(yàn)分析，下面方法可以快速選擇出最優(yōu)組合參數(shù)。

（1）城市規(guī)模/螞蟻數(shù)目≈1．5，首先確定螞蟻數(shù)。

（2）對(duì)取值范圍較大的信息啟發(fā)式因子α、期望啟發(fā)式因子β、信息素強(qiáng)度Q進(jìn)行粗調(diào)，來(lái)得到效果較好的解。

（3）對(duì)取值范圍較小的信息素?fù)]發(fā)因子ρ進(jìn)行微調(diào)，提升最優(yōu)解的效果。

重復(fù)以上步驟，直至得到理想?yún)?shù)組合。

2．3 車輛行駛狀態(tài)的統(tǒng)計(jì)

在改進(jìn)的蟻群算法中，單只螞蟻k構(gòu)成的可行解即可看作某一車輛的運(yùn)輸路徑。算法中規(guī)定車輛完成運(yùn)輸任務(wù)即刻返回運(yùn)輸中心，返回運(yùn)輸中心的車輛在滿足時(shí)間窗的條件下可以進(jìn)行二次運(yùn)輸指派，即某一車輛完成的運(yùn)輸路徑可以看作在時(shí)間窗約束下，多只螞蟻構(gòu)成可行解的集合，這里需要對(duì)滿足約束條件的可行解進(jìn)行有效合并。

為了獲取車輛的行駛狀態(tài)、所在工位、預(yù)計(jì)回到運(yùn)輸中心時(shí)間等信息，需要對(duì)全部車輛的狀態(tài)進(jìn)行跟蹤，實(shí)現(xiàn)實(shí)時(shí)調(diào)度優(yōu)化。因此需要建立車輛-時(shí)間狀態(tài)圖，用來(lái)查看車輛的狀態(tài)。

具體實(shí)現(xiàn)過(guò)程為：對(duì)每輛車進(jìn)行編號(hào)，并建立時(shí)間統(tǒng)計(jì)表。當(dāng)?shù)谝惠v車V1走完第一個(gè)子路徑R0后回到原點(diǎn)，將回到原點(diǎn)時(shí)間t0記入時(shí)間統(tǒng)計(jì)表TV1中。接下來(lái)繼續(xù)檢測(cè)其它子路徑的出發(fā)時(shí)間 t1，t2，t3……如果t1≥t0，那么車輛V1再次出發(fā)走路徑R1，完成任務(wù)后返回原點(diǎn)，將時(shí)間t1記入時(shí)間統(tǒng)計(jì)表TV1中，將兩條路徑合并到車輛V1的行走路徑表中，并把新路徑的工位記入禁忌表。依次不斷迭代，直到最后一次返回原點(diǎn)的時(shí)間無(wú)法滿足剩余子路徑出發(fā)時(shí)間要求時(shí)，然后才能派出新的一輛車。依照此模式直到走完所有子路徑后，就可以得到最佳車輛數(shù)。

按照上面算法通過(guò)Matlab建立車輛—時(shí)間狀態(tài)模型：縱坐標(biāo)依次對(duì)派遣車輛進(jìn)行編號(hào)，橫坐標(biāo)時(shí)間軸上采用不同顏色來(lái)顯示車輛的不同行駛狀態(tài)。根據(jù)圖表，可以清楚了解到路上行駛的車輛和原點(diǎn)剩余車輛，以方便下一次車輛運(yùn)送或處理突發(fā)事件。

3 算法實(shí)現(xiàn)

針對(duì)本文中車輛配送二次調(diào)度，對(duì)蟻群算法改進(jìn)后，步驟如圖1所示。

4 算例

▲圖1 改進(jìn)后蟻群算法流程圖

▲圖2 改進(jìn)前蟻群算法迭代次數(shù)與總路程的關(guān)系

▲圖3 改進(jìn)后蟻群算法迭代次數(shù)與總路程的關(guān)系

選取數(shù)據(jù)模型見表2，模型中共22個(gè)坐標(biāo)點(diǎn)，其中第一個(gè)坐標(biāo)點(diǎn)為運(yùn)輸中心，車輛在230s內(nèi)完成全部運(yùn)輸任務(wù)，貨物量運(yùn)輸單位為kg。

表2 各工位需求信息

各參數(shù)取值為：螞蟻數(shù)量m=15；根據(jù)以往經(jīng)驗(yàn)和多次計(jì)算比較，取信息啟發(fā)式因子α=0.9；期望啟發(fā)式因子β=5；信息素?fù)]發(fā)因子ρ=0.1；信息素強(qiáng)度Q=1；車輛載重為150kg，最大迭代次數(shù)為100次。

經(jīng)過(guò)計(jì)算得到的最佳路徑：Routes=

車輛V1: 1 14 7 22 1 0 0

車輛V2: 1 6 3 1 13 5 1

車輛V3: 1 21 2 1 0 0 0

車輛V4: 1 20 16 17 4 19 1

車輛V5: 1 18 10 11 12 1 0

車輛V6: 1 15 8 9 1 0 0

圖2、圖3分別為改進(jìn)前、后蟻群算法迭代次數(shù)與總路程的關(guān)系，圖中橫坐標(biāo)為迭代次數(shù)，縱坐標(biāo)為里程數(shù)。由圖2中可以看出，達(dá)到最佳里程數(shù)需迭代30次以上，而改進(jìn)后（圖3）的蟻群算法經(jīng)過(guò)20次迭代即可達(dá)到最優(yōu)值，從而保證了計(jì)算的時(shí)間限制。

改進(jìn)后蟻群算法車輛巡回圖如圖4所示，車輛最佳里程數(shù)為680.465，改進(jìn)前為706.538。蟻群算法改進(jìn)后車輛—時(shí)間狀態(tài)如圖5所示，圖中白色為車輛在原點(diǎn)停止時(shí)間段，黑色為車輛行駛時(shí)間段，深灰色為車輛在其它工位等待時(shí)間段，淺色為車輛服務(wù)時(shí)間段。從圖中可以清晰顯示出全部車輛任一時(shí)刻的狀態(tài)。通過(guò)可行解路線進(jìn)行合并對(duì)車輛進(jìn)行二次指派，車輛2走完了工位6和3后返回原點(diǎn)，重新裝載貨物后對(duì)工位13和5進(jìn)行了貨物運(yùn)送。

表3 改進(jìn)前后結(jié)果對(duì)比

通過(guò)表3可以看出，改進(jìn)后最佳里程數(shù)和得到最佳里程的迭代次數(shù)都好于改進(jìn)前，縮短了行駛路程，同時(shí)提高了計(jì)算效率，并節(jié)省了一輛車輛。

5 結(jié)束語(yǔ)

本文針對(duì)VRPTW，建立了相應(yīng)的基于時(shí)間軸的數(shù)學(xué)模型。通過(guò)改進(jìn)的蟻群算法，首先排出最優(yōu)路徑，然后根據(jù)時(shí)間選擇出可合并路徑，從而得出最佳車輛數(shù)。運(yùn)算時(shí)間和最佳里程數(shù)均有所優(yōu)化。完成任務(wù)的車輛返回原點(diǎn)重新接受任務(wù)，提高了單輛車?yán)寐?，使帶?dòng)態(tài)時(shí)間窗的車輛路徑優(yōu)化更加具有實(shí)際應(yīng)用價(jià)值。

▲圖4 改進(jìn)后蟻群算法車輛巡回路線

▲圖5 改進(jìn)后蟻群算法車輛-時(shí)間狀態(tài)圖

［1］ 郎茂祥，胡思繼．車輛路徑問(wèn)題的禁忌搜索算法研究［J］．管理工程學(xué)報(bào)，2004，18（1）:81-84．

［2］ 謝秉磊，郭耀煌，郭強(qiáng)．動(dòng)態(tài)車輛路徑問(wèn)題：現(xiàn)狀與展望［J］．系統(tǒng)工程理論方法應(yīng)用，2002，11（2）:116-119．

［3］ 王訓(xùn)斌，陸慧娟，陳五濤．帶時(shí)間窗動(dòng)態(tài)車輛路徑問(wèn)題的改進(jìn)蟻群算法［J］．工業(yè)控制計(jì)算機(jī)，2009，22（1）：41-43．

［4］ 郝會(huì)霞．基于改進(jìn)蟻群算法的物流配送車輛路徑優(yōu)化方法的研究［D］．西安：長(zhǎng)安大學(xué)，2008．

［5］ 郎茂祥．動(dòng)態(tài)車輛配送優(yōu)化調(diào)度問(wèn)題的模型及其兩階段算法［J］．交通運(yùn)輸系統(tǒng)工程與信息，2009，9（4）：140-144．

［6］ 汪鵬飛．并行蟻群算法及其應(yīng)用研究［D］．成都：西南交通大學(xué)，2008．

［7］ 劉霞．給予最大最小螞蟻系統(tǒng)的動(dòng)態(tài)車輛路徑問(wèn)題研究［J］．計(jì)算機(jī)工程與科學(xué)，2013，35（1）:130-137．

［8］ 王俊鴻，修桂華．二次蟻群算法在運(yùn)輸調(diào)度問(wèn)題中的應(yīng)用［J］．計(jì)算機(jī)應(yīng)用與軟件，2008，25（7）：71-73．

［9］ 陳迎欣．基于改進(jìn)蟻群算法的車輛路徑優(yōu)化問(wèn)題［J］．計(jì)算機(jī)應(yīng)用研究，2012，29（6）:2031-2034．

［10］王君，李波，盧志剛．帶時(shí)間窗動(dòng)態(tài)車輛路徑問(wèn)題的優(yōu)化調(diào)度策略［J］．計(jì)算機(jī)工程，2012，38（13）:137-141．