動態(tài)路網(wǎng)選址–路徑優(yōu)化算法及實現(xiàn)

武楚雄,陳 馳,張貴軍

(浙江工業(yè)大學信息工程學院,浙江杭州 310023)

1 引言

隨著我國經(jīng)濟的發(fā)展,物流已經(jīng)成為推動經(jīng)濟發(fā)展的重要因素.而配送中心的選址和配送車輛路徑的優(yōu)化是物流體系優(yōu)化的重要環(huán)節(jié)[1].選址–配送方案直接影響著物流服務的效率、成本,從而影響到企業(yè)的競爭力.同時,Salhi和Rand[2]證明了分別地求解選址問題與配送路徑優(yōu)化問題經(jīng)常會導致次優(yōu)解的出現(xiàn).因此,同時考慮設施選址問題與配送路徑優(yōu)化問題的特點,將設施選址與配送車輛的路徑優(yōu)化進行聯(lián)合決策具有重要的現(xiàn)實意義.為了同時考慮設施選址與車輛路徑的優(yōu)化,Maranzana[3]首次提出了選址–路徑問題(location-routing problem,LRP)將兩種問題作為一個整體進行研究.但是,傳統(tǒng)的LRP問題算法解決的都是靜態(tài)網(wǎng)絡中的問題,即網(wǎng)絡中的邊權與到達邊尾的時間無關.然而,近年來,隨著分布式處理、云計算和智能交通系統(tǒng)的興起,傳統(tǒng)問題面臨著新的挑戰(zhàn):邊權的時間依賴性,即有向邊的通行時間隨著不同時段內(nèi)的通行速度的變化而發(fā)生改變.考慮邊權動態(tài)下的LRP問題具有重要的實際應用意義,目前國內(nèi)外這方面的研究很少,本文正是從這個角度出發(fā),將LRP問題與具有連通性質(zhì)的實際城市動態(tài)路網(wǎng)相結合,做了有益的嘗試.

在LRP研究方面,Duhamel等[4]針對有容量限制的選址–路徑問題(location-routing problem with capacity constraints,CLRP)提出了結合鄰域搜索的貪婪隨機搜索算法(greedy randomized adaptive search algorithm,GRASP);Hemmelmayr等[5]對兩級LRP 問題進行建模,并提出了一種大鄰域搜索算法進行求解;Chen等[6]針對低碳LRP問題,建立了雙目標LRP模型,并通過改進遺傳算法與禁忌搜索算法結合的混合算法進行求解;Yannis等[7]建立了隨機需求選址–路徑問題的模型,并通過克隆選擇算法(clonal selection algorithm,CSA)與可變鄰域搜索算法相結合的混合算法進行求解;Vincent等[8]針對開放式選址–路徑問題首次建立了基于最小總成本目標的模型,并通過改進的模擬退火算法進行求解;王雪峰等[9]針對大規(guī)模CLRP問題,提出了一種基于禁忌搜索及雙種群蟻群算法的混合啟發(fā)式算法.

綜合來說,考慮了邊權的動態(tài)性與實際路網(wǎng)約束的LRP問題的國內(nèi)外研究文獻較少,尚缺乏一定的理論支持,本文針對具有動態(tài)邊權的實際道路路網(wǎng)結構,在對選址–路徑問題進行研究時考慮了不同時段下路段的通行時間以及實際路網(wǎng)的靜態(tài)約束,在構建了基于實際路網(wǎng)結構的LRP數(shù)學模型的基礎上,通過遺傳算法與改進蟻群算法進行問題的求解,并通過實驗驗證了算法的有效性.

2 數(shù)學模型建立

2.1 動態(tài)路網(wǎng)的時間依賴函數(shù)

從車輛配送的實用性出發(fā),本文將研究的LRP問題建立在離散時間依賴函數(shù)的基礎上;本文采用Ichoua等[10]提出的離散時間依賴函數(shù),如圖1所示,將旅行時間函數(shù)用旅行速度函數(shù)代替,使動態(tài)路網(wǎng)滿足先進先出(first in first out,FIFO)準則.

圖1 路網(wǎng)時間依賴函數(shù)Fig.1 Time dependent function of road network

2.2 車輛行駛速度的分布

王祺等[11]通過對下一代交通仿真(next generation simulation,NGSIM)數(shù)據(jù)的研究進而對一般車輛速度分布進行了分析,所得到的結果表明,在交通流密度較小的時間段速度分布服從對數(shù)正態(tài)分布;在交通流密度較大時間段速度分布趨近負指數(shù)分布;關偉等[12]在對快速路實際交通數(shù)據(jù)分析后得到的結果表明;車輛速度分布在低、中等以及高密度的情況下都接近于高斯分布.

基于上述研究,為了更加符合車輛在實際道路路網(wǎng)上配送的實際情況,本文LRP模型假設時根據(jù)不同時段車輛速度的分布的不同,本文假設在交通流密度較大時,即一般時間段及高峰時間段,速度分布服從正態(tài)分布,在交通流密度較低時,即暢通時間段速度分布服從對數(shù)正態(tài)分布:

其中:tn1,tn2,tn3分別為暢通時間段、一般時間段、高峰時間段;μ為不同時段內(nèi)的速度期望值;σ為不同時段內(nèi)的速度標準差.

2.3 動態(tài)道路路網(wǎng)跨時段車輛行駛時間

給定路網(wǎng)G(V,A,T),其中V是非空結點集;A是有限邊集;用表示從結點wi到結點wj的有向邊;Tn表示在tn時段結點wi到結點wj的行駛時間;設車輛從結點wi1由t0時刻出發(fā)到達結點win的過程中經(jīng)過了N個時段,其中第N個時段的端點為MN,MN+1;設wi1與win之間的距離為d;tk時段車輛的行駛速度為vtk;由第2.1節(jié)所述的旅行速度時間依賴函數(shù)可得車輛行駛的總旅行時間為

2.4 路網(wǎng)邊權時變的影響

2.4.1 通行時間的分段連續(xù)函數(shù)計算

由上討論可以得出,采用旅行速度時間函數(shù)可以使得車輛的路段通行時間滿足FIFO準則,滿足多車輛配送的實際要求,避免了以往使用旅行時間依賴函數(shù)時出現(xiàn)的“超車”問題,即多車輛在路段中行駛時出現(xiàn)的先出發(fā)車輛后到達的現(xiàn)象.進一步地,對于結點wi與wj間的時間段集合

2.4.2 時間依賴下的約束處理

2.5 路網(wǎng)靜態(tài)約束的影響

在以往的研究中,大多數(shù)學者并沒有考慮到路網(wǎng)的實際結構對于選址方案及車輛配送計劃的影響,如果將配送網(wǎng)絡建模為笛卡爾坐標下的若干離散點集合,由于此時的距離矩陣為歐氏距離矩陣D=(dij),因此無法考慮到交通因素的制約:道路等級限速、轉(zhuǎn)向延遲、單行限制等.而實際路網(wǎng)中結點之間的真實距離是復雜于歐氏距離的,如圖2所示,1–2之間由于單行限制,導致5–2之間的實際距離為∞.因此,本文采用基于空間連通性的OD(origin destination)成本矩陣作為網(wǎng)絡的距離矩陣D=OD(i,j),在設置路網(wǎng)網(wǎng)絡模型的連通性策略的基礎上,通過構建轉(zhuǎn)彎要素可以將轉(zhuǎn)彎延遲時間轉(zhuǎn)化到路網(wǎng)邊權中,同時在定義了路段的單行屬性后,便得到了有向富屬性網(wǎng)絡,即可調(diào)用Dijkstra算法得到路網(wǎng)中源節(jié)點(origin)到目的結點(destination)的實際距離OD(i,j).

圖2 有向富屬性網(wǎng)絡Fig.2 Directed rich attribute network

2.6 模型的建立

2.6.1 符號與變量

2.6.2 模型的構建

傳統(tǒng)選址–路徑的成本函數(shù)如下:

可以看到,選址–路徑模型的成本函數(shù)包括設施建設固定成本、配送成本與車輛使用成本,目標是使總成本最小.同時,由上述討論,可以構建得到動態(tài)路網(wǎng)選址–路徑問題的混合非線性整數(shù)規(guī)劃模型

成本函數(shù)的目標是使總成本最小.約束(5)保證客戶點只由一輛車服務;約束(6)限制運輸量不超過車輛的載重;約束(7)確保滿足倉庫的容量限制;約束(8)保證線路連續(xù);約束(9)限制每輛車只能從一個設施駛出;約束(10)保證需求點只能由選中的設施提供服務;約束(11)為輔助變量約束;約束(12)為子回路消除約束;約束(13)–(15)保證時間的連續(xù)性.

2.7 模型的驗證

為避免自行設置測試數(shù)據(jù)時的盲目性,本文在Solomon R101測試集的基礎上,利用運算Mi=rand%n+1,產(chǎn)生出3個潛在配送中心,其中n為測試集中客戶點的數(shù)目.同時,再利用上述公式產(chǎn)生出5個客戶點數(shù)據(jù).車輛容量Qk=40,配送中心建立固定成本Fr=200,配送中心容量Ml=70,車輛固定使用成本Rk=30;車輛單位時間行駛成本=1.5;客戶點、配送中心的坐標、客戶點的需求量如表1所示.

此處,將車輛行駛時間分為3個時段,在時段0～5內(nèi),車輛的行駛速度為30,在時段5～10內(nèi)的速度為80,在時段10～15內(nèi)的速度為60,可得在此條件下車輛實際跨1個時段,則可計算得到此時的tijk為

進一步,利用LINGO11.0,在計算平臺Intel(R)Core(TM)i5–4670 CPU@3.40 GHz 8 GB RAM上運行時間51 min,得到局部最優(yōu)解如圖3所示,可以看到所構建模型為混合非線性整數(shù)規(guī)劃模型.

表1 需求量容量表Table 1 Demand and capacity

圖3 LINGO求解結果Fig.3 LINGO solution results

模型的驗證結果見表2.

表2 模型驗證結果Table 2 Model validation results

3 動態(tài)路網(wǎng)選址–路徑問題的算法設計

述動態(tài)路網(wǎng)選址–路徑問題優(yōu)化模型可以分為2個子問題,即設施選址問題(facility location problem,FLP)與車輛路徑優(yōu)化問題(multi-depot vehicle routing problem,MDVRP).研究人員目前普遍采用兩階段法來解決這2個子問題,而分階段法實質(zhì)上是將LRP問題拆成2個獨立的子問題分別予以求解,在設施選址時普遍基于結點間距離直接進行客戶點的劃分與設施定位,未考慮到與VRP問題的依賴關系,是一種靜態(tài)的選址結果.事實上,在針對不同實際需求進行車輛調(diào)度的優(yōu)化時也會影響到設施的選址結果,考慮到子問題間的相互制約與相互關聯(lián)對于實際問題來說尤為重要.因此,針對問題的特點,通過將目標函數(shù)進一步轉(zhuǎn)化為式(17)–(18),在上層設施選址決策的同時進行下層車輛路徑的訪問順序決策.

3.1 GA–IACO算法

基于動態(tài)路網(wǎng)選址–路徑問題特征,設計遺傳算法(genetic algorithm,GA)與改進蟻群算法(improved ant colony algorithm,IACO)協(xié)同智能算法(GA–IACO):采用遺傳算法進行FLP 優(yōu)化,采用IACO 算法將GA尋優(yōu)過程中的FLP中間結果作為輸入,同步進行MDVRP優(yōu)化,并將優(yōu)化結果反饋給GA.IACO和GA 分工合作,協(xié)同完成LRP 優(yōu)化.GA–IACO 協(xié)同智能算法框架如圖4所示.

GA采用二進制0–1編碼,染色體長度為候選配送中心的數(shù)目n,gi(i=1,2,···,n)表示n位基因位的值,gk=1表示在第k個候選點處建立配送中心;由于交叉操作在此處可能破壞染色體模式,產(chǎn)生不可行解;而在配送中心數(shù)目確定的情況下,采用基于交換的變異策略可以保證種群的多樣性,所以在這里不進行交叉操作.采用精英保留策略取前m個個體作為精英個體,直接傳遞到下一代的種群中.

圖4 GA–IACO協(xié)同智能算法框架Fig.4 GA–IACO collaborative intelligent algorithm framework

3.2 改進蟻群算法IACO

算法通過構造虛擬配送中心進行MDVRP問題的求解,所有車輛都從構造的虛擬配送中心出發(fā),再將實際配送中心插入到車輛路徑中;虛擬配送中心到實際配送中心的網(wǎng)絡阻抗為0.算法主要流程描述如下:

步驟1初始化系統(tǒng)參數(shù),系統(tǒng)初始溫度T0;

步驟2利用最近鄰算法(nearest neighbor clustering,NNC)初始化策略構造初始解,初始化信息素;

其中:Q為蟻周模型參數(shù);Rbest為精英路徑總成本;為了防止解的過早收斂,利用Max-Min信息素動態(tài)更新策略進行全局信息素更新之后的修正:τmin=,Sp為常數(shù),產(chǎn)生第1代解之前,

C為MMAS系統(tǒng)參數(shù);

步驟8降低系統(tǒng)的溫度,T=αT,如果ite

3.3 算法復雜度分析

對于上層迭代次數(shù)Gmax,種群數(shù)量Ng,下層迭代次數(shù)Nc,螞蟻數(shù)m,客戶數(shù)N,時間分段數(shù)為T的問題,復雜度分析時只需考慮每個步驟中復雜度最高的操作,則一次迭代中:NNC初始化復雜度O(N),信息素初始化O(N2),螞蟻跨時段通行時間計算O(TN2m),增量信息素更新O(N2m),模擬退火過程中當鄰域解違反時間約束時,重新評價鄰域解的復雜度O(TN2m),全局信息素更新O(N2m),因此復雜度為O(NcTN2m).上層選擇策略等復雜度忽略不計,算法整體復雜度為GmaxNgTO(NcN2m),而一般的用于解決TSP問題的基于種群的算法,復雜度為GmaxNgO(N2),張景玲等[13]提出的解決時間依賴下同時送取貨VRP問題的超啟發(fā)式算法的復雜度為GmaxNgTO(N2).從而,對于解決2個NP問題組合的選址–路徑雙層規(guī)劃模型的GA–IACO算法的復雜度是在計算機可接受的范圍內(nèi)的.同時,與兩階段法得出的靜態(tài)結果不同,GA–IACO算法可以根據(jù)下層不同的調(diào)度需求規(guī)劃出相應的選址方案,這對于實際問題的決策是至關重要的,而選址–路徑?jīng)Q策對于企業(yè)來說重視的是物流成本的降低,這種計算時間的消耗是不會影響企業(yè)決策的.

3.4 初始化策略

本文將基于最小網(wǎng)絡成本的NNC算法[14]擴展到MDVRP問題:

步驟1車輛由虛擬中心出發(fā)并隨機選擇一個實際車場,插入到路徑中;

步驟2在滿足約束條件的未訪問點集合Uh中,如果結點j ∈Uh且T(last-node,j,tn),則將j插入到當前車輛路徑中,last-node為當前最后訪問結點;

步驟3若當前車輛已達到滿載,當前車輛回到虛擬結點中的出發(fā)車場.若Uh=?,結束計算,否則轉(zhuǎn)到步驟1.

3.5 模擬退火中的鄰域解構造

1)2–opt變換:路徑內(nèi)結點變換,如圖5所示.

圖5 2–opt示意圖Fig.5 2–opt diagram

2)1–0 relocate變換:路徑間結點變換,如圖6所示.

圖6 1–0 relocate示意圖Fig.6 1–0 relocate diagram

3)2–opt*變換:路徑間結點變換,如圖7所示.

圖7 2–opt*示意圖Fig.7 2–opt*diagram

4 實驗及分析

4.1 算例

由于在動態(tài)路網(wǎng)上的MDVRP問題還沒有基準算例,為了測試算法,本文參照文獻[15–16]的做法,通過對傳統(tǒng)的MDVRP問題的算例[17–20]增加速度依賴函數(shù)來構造動態(tài)路網(wǎng)上的MDVRP問題的測試算例.將速度時間依賴函數(shù)定義為:根據(jù)3類不同的道路等級,將每個函數(shù)的速度特性進一步劃分為3個時段,基本速度時間依賴比設置為1.最后,得到的速度時間依賴函數(shù)如表3所示.

表3 路網(wǎng)屬性設置Table 3 Road network attribute setting

各路段所屬道路等級由式(21)確定[16]:

其中:Hierarchy為邊i,j之間的等級,Mod為取余算子.

4.2 算法參數(shù)設置

本文通過試算法確定參數(shù),通過保持要調(diào)節(jié)的參數(shù)之外的參數(shù)固定不變,通過算例每次的實驗結果確定算法的最優(yōu)參數(shù).取

4.3 實驗結果分析

為了驗證算法的有效性,在實驗環(huán)境為Intel(R)Core(TM)i5–4670 CPU@3.40 GHz 8 GB RAM,實驗算法均采用Java語言實現(xiàn),算法運行平臺為IntelliJ IDEA 2018.3的條件下進行實驗分析.

4.3.1 初始化策略的影響

為了分析采用NNC算法進行初始化對算法的影響,在測試例P02上進行2組實驗;2組實驗的算法迭代次數(shù)均設置為6000次,其中,第1組實驗中沒有引入模擬退火過程,而第2組實驗中引入了模擬退火過程.2組實驗中蟻群算法的參數(shù)設置均相同(第4.2節(jié)),而第2組實驗中模擬退火算法的參數(shù)設置見第4.2節(jié).第1–2組實驗的收斂曲線如圖8所示,縱坐標均為30次實驗所得最優(yōu)解的平均值.可以看到,算法在采用基于NNC算法的初始化策略后,最優(yōu)值可以收斂到1065.750,而隨機生成初始解的算法只能收斂到1088.857,基于NNC算法來生成初始解更為有效;同時可以看到,在引入模擬退火過程后,由于隨系統(tǒng)溫度不同對候選解進行接收,2種算法所能收斂到的最優(yōu)值均有所降低,其中,隨機生成初始解的算法收斂到1028.416,基于NNC初始化算法的最優(yōu)值收斂到1017.645.

圖8 30次實驗最優(yōu)解均值的收斂曲線Fig.8 Convergence curve of the mean value of the optimal solution in 30 experiments

由表4 可以看到,分別在Cordeau[16–19]測試例P01–P10上對采用不同初始化方法的算法進行測試,2種算法最優(yōu)值偏差率在1.06%～2.97%之間,在采用了NNC 算法進行初始化后,算法的平均效率提高了1.783%,同時在一定程度上加快了算法的收斂.

表4 初始化策略與模擬退火的影響Table 4 Impact of initialization strategy and simulated annealing

4.3.2 本文算法的實驗結果分析

針對本文提出的算法與基本蟻群算法進一步地在Cordeau測試算例P01–P10上進行測試,測試結果如表5及圖9所示,表4中第1列為算例序號,第2列為客戶點數(shù)目,第3 列為配送中心數(shù)目,基本蟻群算法、本文算法(GA–IACO)求解30次后的最優(yōu)解分別記為;基本蟻群算法、本文算法求解30次后的平均值分別記為;提高效率分別通過式

計算得到;可以看到除了P02算例效率沒有明顯提高外,本文算法的結果均明顯優(yōu)于蟻群算法,其中MDVRP 成本最優(yōu)解降低11.578%,平均值降低11.519%,圖10所示為P01–P10算例的求解30 次實驗后的最優(yōu)解均值的收斂曲線.

表5 30次實驗最優(yōu)解及其均值比較Table 5 Comparison of the optimal solution and its mean value in 30 experiments

圖9 結果對比圖Fig.9 Results comparison diagram

圖10 30次實驗最優(yōu)解均值的收斂曲線Fig.10 Convergence curve of the mean value of the optimal solution in 30 experiments

5 實例分析與應用

基于本文提出的算法,在杭州市實際路網(wǎng)數(shù)據(jù)上進行動態(tài)路網(wǎng)下LRP問題的求解,本文建立的杭州市富屬性網(wǎng)絡模型(如圖11所示)中,結點(Junctions)數(shù)為88164,邊(edge)數(shù)為95883,其中主要干道路段數(shù)50193,支干道路路段數(shù)36969.

5.1 基于空間連通性的動態(tài)路網(wǎng)路段阻抗設置

基于所構建的杭州市富屬性路網(wǎng)模型,通過設置路段(edge)的屬性值,可以進一步計算出結點之間的基于空間連通性的真實矢量距離.將必要的交叉路口定義為轉(zhuǎn)向要素;設置單行限制字段:矢量化方向與單行方向一致時賦值為FT,否則賦值為TF屬性;道路等級字段(hierarchy)賦3個值:1,2和3.進而通過調(diào)用Dijkstra算法,計算得到源結點(origin)與目的結點(destination)之間的最短時間通行成本D(i,j,tn,ti)作為邊權,表示在tn時段的ti時刻從結點i出發(fā),經(jīng)過時間D(i,j,ti)到達結點j.在優(yōu)化過程中,時刻ti是未知的,因此D(i,j,tn,ti)隨時間變化,路網(wǎng)權值并不固定.因此,本文采用分時段更新路網(wǎng)OD矩陣的方式來解決基于時間最優(yōu)的動態(tài)路網(wǎng)模型所遇到的問題,本文的邊連通性策略設置為覆蓋連通(overide);點連通性策略設置為任意折點連通(anyvertex).

圖11 富屬性網(wǎng)絡Fig.11 Rich attribute network model

5.2 參數(shù)設置

基于本文上述所提出的協(xié)同式啟發(fā)算法,在所構建的杭州市路網(wǎng)模型上,求解基于動態(tài)路網(wǎng)的LRP問題,對杭州市某物流公司的10家配送中心的選址–配送問題進行分析求解,要求在此公司的10家配送中心中選擇合適位置的4家配送中心,使得在動態(tài)路況下車輛配送路徑的總成本與設施固定成本之和最小.

本文考慮3種道路等級:快速路、主干路和支路;其中快速路的設計車速取70 km/h、主干路的設計車速取50 km/h、支路的設計車速取30 km/h;規(guī)定各個配送中心的工作時間為8:00～20:00,不考慮用戶的卸貨時間,不考慮用戶的時間窗,具體參數(shù)設置如表6所示,同時,50家客戶點的需求量如表7所示;算法的參數(shù)設置上,遺傳算法種群規(guī)模大小取20;而染色體變異概率取0.5,精英個數(shù)取2.蟻群算法中,取α=3,β=3,ρ=0.95,q0=0.85,n=60,蟻周參數(shù)Q=3500,Sp=3000,T0=2.5×105,τ=0.99(冷卻系數(shù)),C=1000.其中n為蟻群大小.

表6 速度分布參數(shù)Table 6 Velocity distribution setting

5.3 實驗結果及分析

配送中心1–10擁有的車輛數(shù)均為4輛,發(fā)一輛車的固定成本為300元,即F=300元/輛;車輛單位時間的運輸成本為20元/h.在配送中心于8:00開始營業(yè)時,每輛車的發(fā)車時間都為8:00;在此條件下,進行LRP問題的求解,圖12所示分布圖中,共有10個待選配送中心用“星形”表示;50個客戶點用“方形”表示.

同時,本文為3個時段tn1,tn2,tn3分別求解OD成本矩陣得到3個不同時段下的OD成本矩陣,其中,圖13所示為時段1的OD成本矩陣求解結果;在對問題進行求解時,依據(jù)此3個不同時段的OD成本矩陣進行跨時段路段通行成本的計算.

表7 杭州市50家客戶點需求量Table 7 Demands of 50 customers in Hangzhou

圖12 客戶點與配送中心分布Fig.12 Distribution of customers and distribution centers

圖14所示為配送中心由8:00開始營業(yè)時,即:車輛都從8點出發(fā)的選址–配送結果;每輛車的載重均為80 t(噸),配送中心1–10 的車輛數(shù)均為4輛;在求解得到的選址–配送結果中可以得到,選擇50#(A),51#(C),53#(D),55#(G)作為配送中心,共派出了10輛車,總行駛時間為2669.127 min,配送總成本為3899.709元.

圖13 時段1OD成本矩陣求解結果Fig.13 OD cost matrix of time period 1

其中,車輛1的行駛路線為A–18–7–50–19–A,行駛時間為256.223 min;車輛2的行駛路線為C–16–3–4–5–6–C,行駛時間為276.179 min;車輛3 的行駛路線為C–49–15–14–12–C,行駛時間為233.589 min;車輛4的行駛路線為C–8–9–11–13–C,行駛時間為197.141 min;車輛5的行駛路線為C–10–20–28–27–29–26–C,行駛時間為166.219 min;車輛6的行駛路線為D–17–45–48–44–46–47–D,行駛時間為203.271 min;車輛7的行駛路線為D–43–23–21–22–2–1–D,行駛時間為261.810 min;車輛8的行駛路線為G–30–31–24–25–32–G,行駛時間為202.660 min;車輛9的行駛路線為G–35–41–40–39–42–G,行駛時間為358.889 min;車輛10的行駛路線為G–36–33–34–38–37–G,行駛時間為513.148 min.

圖14 選址–配送求解結果Fig.14 Location–allocation solution results

進一步地,不同優(yōu)化模型在杭州市區(qū)域路網(wǎng)上的求解結果如表8所示,表中在不同時段分別選取了配送中心的營業(yè)時間進行模型優(yōu)化目標與算法求解結果的比較,從實驗結果可以看到由于已有模型基于靜態(tài)的路段通行時間,因此當車輛行駛在邊權時變的路網(wǎng)中時,其所得結果與實際結果相比會產(chǎn)生較大誤差.進一步的,對成本來說,按式

計算出兩者的具體差異,其中:G-best(tn)為已有模型在tn時段的最優(yōu)目標值;N-best(tn)為本文模型在tn時段的最優(yōu)目標值,則配送成本在3個時段內(nèi)的差異分別為?8.91%,?6.13%,?5.73%,從而,本文模型得到的結果與已有模型相比,配送成本平均降低了6.92%;同時,選址–路徑規(guī)劃總成本在3個時段內(nèi)的差異分別為?7.39%,?3.30%,?10.58%,選址–路徑規(guī)劃總成本平均降低7.09%;而在高峰時間段,兩者差異尤為顯著;進一步地,由實驗結果可以得到結論:

1)從基于靜態(tài)路網(wǎng)模型的求解結果可以看到,由于此時可視作固定速度比率下的總成本,從而如果設施營業(yè)時間在路況較為擁堵的時段,由于此時車輛行駛速度較低,則選址結果傾向于選擇附近有較多客戶點的配送中心(如:配送中心J(固定成本9645元)、配送中心F(固定成本11026元)、配送中心B(固定成本9281元)),而這些配送中心往往固定費用較高,而這也說明了選址方案必然不是靜態(tài)的;

2)從本文算法的求解結果可以看到,在暢通時間段傾向于更少的發(fā)車數(shù)量,同時,此時的車輛傾向于服務較多的客戶點數(shù),而由于此處車輛載重的限制,車輛數(shù)沒有出現(xiàn)明顯地減少;

3)影響配送成本的因素主要有行駛時間與發(fā)車數(shù)量,而發(fā)車數(shù)量是主要影響因素,如果配送中心的營業(yè)時間大都處于暢通時間段,則增大車輛容量將有效降低成本.

表8 不同優(yōu)化模型下的結果Table 8 Results of different optimization models

6 結論

本文對動態(tài)路網(wǎng)下的LRP問題進行研究,設計了遺傳算法與蟻群算法協(xié)同的啟發(fā)式算法,通過實驗結果可以看到在采用了基于NNC算法的初始化策略后一定程度上加快了算法的收斂速度,同時通過引入模擬退火過程并按最大–最小蟻群系統(tǒng)的原則動態(tài)地更新信息素的范圍降低了算法陷入局部最優(yōu)解的可能性;最后在杭州市的實際道路路網(wǎng)上通過實時更新不同時段的路網(wǎng)OD成本矩陣進行問題的求解,實驗結果證明了本文算法在實際動態(tài)路網(wǎng)上的可行性與有效性.