改進(jìn)AHP-GA算法的多目標(biāo)配送路徑優(yōu)化①

李鳳坤

(大連東軟信息學(xué)院 智能與電子工程學(xué)院,大連 116023)

1 引言

隨著電子商務(wù)的發(fā)展,物流專業(yè)技術(shù)的提高,城市快遞配送業(yè)務(wù)得到了迅速的發(fā)展.城市快遞配送作為快遞物流的“最后沖刺”,是物流配送的重要環(huán)節(jié),因此,城市配送路徑的優(yōu)化對提升快遞服務(wù)起著關(guān)鍵的作用.快遞配送路徑優(yōu)化目標(biāo)是高效率尋找成本最低、耗時最短的快遞配送路線,實現(xiàn)快遞配送車輛的優(yōu)化調(diào)度.城市快遞配送路徑的優(yōu)化不僅要關(guān)注配送路徑的長度,還要關(guān)注配送的時間、配送成本、配送車型及負(fù)載.城市快遞配送路徑優(yōu)化問題實質(zhì)是一個非確定性多項式NP(Non-deterministic Polynomial)完全問題.

近年來,仿生智能優(yōu)化算法被廣泛應(yīng)用于解決快遞路徑的優(yōu)化問題.如,遺傳算法[1]、禁忌搜索算法[2,3]、啟發(fā)式搜索算法、模擬退火算法、人工蜂群算法、爬山算法、蟻群算法[1,4,5]、離散蝙蝠算法[6]、粒子群算法等等.

遺傳算法(Genetic Algorithm,GA)是由美國J.Holland 教授受生物進(jìn)化論的啟發(fā)而提出的一套較為完整的理論和方法,是一種基于適者生存,優(yōu)勝劣汰遺傳機(jī)制的自然選擇和進(jìn)化原理的全局搜索隨機(jī)算法、該算法搜索能力強(qiáng)大,遺傳算法在選址問題、配送問題、調(diào)度問題、運輸問題、布局問題方面具有重大的意義.該算法利用自然選擇規(guī)律和基因遺傳機(jī)制來實現(xiàn)仿生運算,它對適用條件幾乎沒有任何限制,以概率論為基礎(chǔ)自適應(yīng)概率搜索,具有強(qiáng)大的搜索能力,在解的空間中進(jìn)行隨機(jī)化搜索,得到全局最優(yōu)解.

層次分析法(Analytic Hierarchy Process,AHP)是薩蒂教授提出的一種層次權(quán)重決策分析方法.它將定性分析與定量分析相結(jié)合,用數(shù)學(xué)的方法將人的思維過程層次化、數(shù)學(xué)化,為決策分析提供量化指標(biāo),但傳統(tǒng)的AHP算法容易受到極端值影響.

本文構(gòu)造的改進(jìn)AHP-GA算法有效整合中位數(shù)AHP算法和遺傳算法的優(yōu)勢,消除了極端值的不良影響,科學(xué)評價快遞配送路徑優(yōu)化問題中各層次目標(biāo)權(quán)重,并給出最佳定量值.同時利用改進(jìn)遺傳算法解決全局優(yōu)化問題的優(yōu)勢,提高了決策的時效性和有效性.

蔣國清[1]等人提出的基于兩階段式的物流配送路徑優(yōu)化方法,將遺傳算法與蟻群算法相結(jié)合,充分利用了遺傳算法全局搜索速度快的優(yōu)點進(jìn)行第一階段的路徑搜索,并將搜索結(jié)果作為第二階段的初始值,同時利用蟻群算法局部搜索能力強(qiáng)的優(yōu)點進(jìn)行第二階段的路徑優(yōu)化.劉恒宇[7]研究了考慮擁堵和工作量的一致性車輛路徑問題,構(gòu)建的混合整數(shù)規(guī)劃模型考慮了車輛容量約束.楊志清[8]提出在多目標(biāo)優(yōu)化問題的基本遺傳算法求解中,可以通過使用權(quán)重系數(shù)變化法將多個子目標(biāo)進(jìn)行權(quán)重配比,從而將多目標(biāo)優(yōu)化問題轉(zhuǎn)化為單目標(biāo)優(yōu)化問題.但是,文中提到的權(quán)重系數(shù)變化法指的是根據(jù)實際情況進(jìn)行設(shè)定和相應(yīng)調(diào)整,沒有關(guān)注先驗信息,主觀性較強(qiáng).本文研究的是帶有軟時間窗的多目標(biāo)快遞配送路徑優(yōu)化問題,并提出利用改進(jìn)AHP-GA算法對該問題進(jìn)行優(yōu)化,利用中位數(shù)AHP算法關(guān)注先驗信息,并消除了極端值帶來的不良影響;利用改進(jìn)GA算法進(jìn)行全局優(yōu)化搜索.

2 問題描述

快遞配送的最優(yōu)路徑,必須滿足以下約束:

(1)配送中心的配送車輛的數(shù)量、型號一定;

(2)每一輛配送車的負(fù)載量必須大于等于所行駛路線上所有待服務(wù)客戶需求貨物的總重量,配送車不得超載運行;

(3)每一輛配送車的配送時間有預(yù)定上限,不得超時間運行;

(4)配送中心為多個,并且每次僅由一個配送中心為某條路徑上的客戶配送貨物,并最終回到出發(fā)的配送中心.

(5)每一個客戶存在且僅存在于一條配送路線上.

(6)滿足客戶要求的時間窗.如果準(zhǔn)時或提前將貨物配送給顧客,則不予懲罰;否則,要給予懲罰.

本文要解決的配送問題是在以上約束條件的基礎(chǔ)上,如何進(jìn)行車輛調(diào)度,以滿足總配送成本最低,總的配送時間最短,配送車輛最少.其中配送成本包括車輛在約定時間之前到達(dá)獲得的機(jī)會成本、在約定時間之后到達(dá)的罰金成本以及車輛行駛的費用.因此,本文可歸結(jié)為多目標(biāo)優(yōu)化問題.

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

基于以上目標(biāo)構(gòu)建的數(shù)學(xué)模型如下:

cij表示從點i到點j的費用;[ETi,LTi]表示該任務(wù)執(zhí)行所允許的時間范圍,m1表 示在ETi之前到達(dá)任務(wù)點等待的單位時間成本,m2表 示在LTi之后到達(dá)點i,所交的罰金成本.目標(biāo)函數(shù)(1)表示運輸成本,(2)表示時間懲罰與機(jī)會成本,(3)表示車輛數(shù)目最少.將目標(biāo)函數(shù)進(jìn)行歸一化處理,使其取值范圍在[0,1]之間.

式(7)中w1,w2,w3分別為3個目標(biāo)函數(shù)的系數(shù)權(quán)重.

4 構(gòu)建評價指標(biāo)權(quán)重子集

根據(jù)式(7)的目標(biāo)函數(shù),需要構(gòu)建一個各項指標(biāo)權(quán)重子集,本文采用中位數(shù)AHP層次分析法[9],有效的摒除了極端值的影響,提高了客觀性,在運用中位數(shù)AHP方法進(jìn)行評價和決策時,可分為以下4個步驟[9]:

(1)分析模型,建立遞階層次結(jié)構(gòu),如圖1所示.

(2)根據(jù)專家打分,對準(zhǔn)則層進(jìn)行指標(biāo)重要性排序.

(3)中位數(shù)是指在變量數(shù)列按照有序(升序或者降序)排列的時候,位于中間位置所對應(yīng)的變量值[3].故中位數(shù)不受分布數(shù)列的極大值和極小值的影響,從而在一定程度上提高了中位數(shù)對分布數(shù)列的代表性.因為中位數(shù)不易受極端值影響且與所有評價值距離最短的優(yōu)點[9],故采用中位數(shù)確定指標(biāo)權(quán)重,通過歸一化處理使得所有指標(biāo)的中位數(shù)權(quán)重之和等于1.

圖1 快遞配送方案層次結(jié)構(gòu)(AHP)圖

如5位專家分別對P1S1、P1S2、P2S2、P2S3、P35個指標(biāo)項權(quán)重評分分別為:

則計算的中位數(shù)分別為

因為0.312+0.223+0.187+0.147+0.131=1,所以此時無需進(jìn)行歸一化處理,因此確定P1S1、P1S2、P2S2、P2S3、P3五個指標(biāo)項的權(quán)重分別為: 0.312,0.223,0.187,0.147,0.131.

在此步驟中,采用了中位數(shù)方法來求取各項指標(biāo)權(quán)重,較之傳統(tǒng)的AHP方法,無需構(gòu)造判斷矩陣,避免了采用不同的標(biāo)度構(gòu)造的判斷矩陣所產(chǎn)生的一致性矛盾.無須進(jìn)行一致性檢驗,避免了大量的計算.且中位數(shù)不受極端值的影響.經(jīng)過簡單的代數(shù)變換得到,在變量數(shù)列中變量值與中位數(shù)離差的絕對值的總和為最小[9].

(4)計算各層要素對系統(tǒng)目的(總目標(biāo)的合成(總)權(quán)重,選擇最優(yōu)方案.由(3)可得因素層指標(biāo)項所占整個指標(biāo)體系的權(quán)重.

將式(8)代入已經(jīng)定義好的數(shù)學(xué)模型式(1)、(2)、(3),將其加和,得到目標(biāo)函數(shù).

5 改進(jìn)遺傳算法求解

5.1 編碼設(shè)計

本文采用自然數(shù)編碼的方式,用0代表配送中心,自然數(shù)1,2,…,N代表客戶點,每個客戶點采用k輛車進(jìn)行配送,以車輛數(shù)k=3,待配送客戶數(shù)=8為例,可構(gòu)造如下編碼.

如圖2所示,通過遺傳算法的編碼,初始化行車路線,如第1輛車的行車路線為0--->3--->8--->1--->0,第2輛車的行車路線為0--->4--->5--->7--->0,第3輛車的行車路線為0--->2--->6--->0.該染色體實質(zhì)是一條忽略了車載容量約束和時間窗約束的廣義路徑.

圖2 編碼設(shè)計

由于遺傳算法是一類借鑒生物界的適者生存,優(yōu)勝劣汰遺傳機(jī)制的進(jìn)化規(guī)律而演化而來的隨機(jī)化搜索方法,因此由傳統(tǒng)的簡單遺傳算法出始化種群得出的適應(yīng)度較低,并制約算法的收斂速度[10].本文采用貪婪算法對初始個體進(jìn)行優(yōu)化,利用貪婪算法局部尋優(yōu)的優(yōu)勢產(chǎn)生新個體.其初始化種群步驟如下:

首先,選擇配送中心(0,0)點加入個體,然后選擇離配送中心最近的一個配送點,標(biāo)記為A配送點,并對A進(jìn)行配送,然后計算其它配送點距離A點的距離,選擇離A點最近的配送點,標(biāo)記為B,并將B作為接下來的配送對象,以此類推直至所有配送點全部加入,由此可見,由貪婪算法生成的初始種群不失隨機(jī)性,同時,由于貪婪算法生成的初始化種群質(zhì)量較高,導(dǎo)致整體質(zhì)量有所提高,有助于加快尋優(yōu)速度[10].

5.2 選擇操作

通過選擇操作保留種群中的最佳個體,本例中采用最佳個體保存策略,采用輪盤賭策略進(jìn)行基因選擇和復(fù)制.計算種群中每一個個體的適應(yīng)度,計算每個個體的適應(yīng)度值與種群總體適應(yīng)度值的比值,并按照適應(yīng)度值大小進(jìn)行排序.設(shè)計隨機(jī)選擇概率,并按照大小進(jìn)行排序.將具有較大適應(yīng)度的染色體進(jìn)行復(fù)制.

5.3 交叉操作

為提高各個解交流到優(yōu)秀基因的機(jī)會,本文對選擇操作產(chǎn)生的新種群(除第一條染色體外的其他染色體)進(jìn)行交叉操作.本文采用的交叉操作要確保每條染色體的合理性,不能對某兩個基因或片段進(jìn)行簡單的交叉,而是要按照交叉概率,對除配送中心外的配送點片段進(jìn)行交叉.本文設(shè)計的交叉規(guī)則是將染色體i的交叉片段移到另一條染色體的尾部,配送中心保持不變,將染色體j的其余數(shù)依次排開,如圖3所示.

圖3 交叉操作

其中,交叉概率采用自適應(yīng)調(diào)節(jié)機(jī)制,以滿足在初期適應(yīng)度值較大時,需要增大交叉概率,在適應(yīng)度值趨于穩(wěn)定時,需要適當(dāng)降低交叉概率.故交叉概率采用文獻(xiàn)[10]提出的自適應(yīng)調(diào)節(jié)機(jī)制.

其中,G: 最大迭代數(shù);g: 當(dāng)前迭代數(shù);fmax: 當(dāng)前所有個體的最大適應(yīng)度值.

5.4 變異操作

變異操作是為了避免求解過程陷入局部最優(yōu)解,保證染色體的多樣性.在傳統(tǒng)的二進(jìn)制編碼的遺傳算法中,通常都采用直接取反的方式來進(jìn)行變異;也有的采用直接刪除節(jié)點或者重新加入節(jié)點的方式來進(jìn)行變異.由于本文是采用自然數(shù)對配送點和配送中心進(jìn)行編碼的方式,所以必須保證染色體的合理性,即各染色體中編碼不能重復(fù),故本文采取對非0點進(jìn)行交換的方式來完成變異操作,如圖4所示.

5.5 適應(yīng)度評估

進(jìn)化論中的適應(yīng)度,表示該個體繁殖后代、適應(yīng)環(huán)境的能力.遺傳算法的適應(yīng)度函數(shù)也叫評價函數(shù),是用來判斷群體中的個體的優(yōu)劣程度的指標(biāo),它是根據(jù)所求問題的目標(biāo)函數(shù)來進(jìn)行評估的.對于某個個體所對應(yīng)的配送路徑方案,是否滿足約束條件、配送成本是否最低、配送路徑總長度是否最短這三者是評價其優(yōu)劣的重要指標(biāo).根據(jù)配送路徑優(yōu)化問題的特點所確定自然數(shù)編碼方法,滿足了每個客戶點都得到配送服務(wù)且每個客戶點僅由一輛汽車配送的約束條件,但不能保證滿足每條路徑上各需求點需求量之和不超過汽車載重量及每條配送路線的長度不超過汽車一次配送的最大行駛距離的約束條件.因此,對每個個體所對應(yīng)的配送路徑方案,要對各條路徑逐一進(jìn)行判斷,看其是否滿足上述兩個約束條件.

圖4 變異操作

6 實例分析

6.1 實例介紹

本文以大連市某快遞配送案例為原型,編寫MATLAB程序進(jìn)行仿真試驗,以此驗證比較傳統(tǒng)的GA算法和本文設(shè)計的基于改進(jìn)AHP-GA算法的多目標(biāo)配送路徑優(yōu)化算法的可靠性與有效性.配送中心為1個,配送中心選取為遼寧省大連市甘井子區(qū)高能街128號運輸管理處,客戶點選取20個不同的位置,設(shè)其相對坐標(biāo)為(0,0),其余20個客戶點均以此配送中心為參考原點換算出的坐標(biāo)距離.其坐標(biāo)分別如表1所示.軟時間窗口為8:00～17:00.

GA算法與改進(jìn)AHP-GA算法選取的種群數(shù)目均為50,進(jìn)化代數(shù)為50,種群的交叉概率參照公式(9)和公式(10),故交叉概率初始值為0.9 ,種群變異概率為0.1,選擇同型號車輛,設(shè)置車輛數(shù)目為3,車輛載重量為1 t,設(shè)置平均車速為60 km/h.罰金成本系數(shù)m2=10.00.

6.2 實驗結(jié)果

本文分別利用傳統(tǒng)的GA算法和改進(jìn)AHP-GA算法對表1中的數(shù)據(jù)執(zhí)行100次得到GA優(yōu)化調(diào)度成本結(jié)果如圖5所示、改進(jìn)AHP-GA優(yōu)化調(diào)度成本結(jié)果如圖6所示,由改進(jìn)AHP-GA規(guī)劃路徑結(jié)果如圖7所示.

表1 各客戶點坐標(biāo)及需求

圖5 GA算法優(yōu)化調(diào)度成本結(jié)果

由仿真結(jié)果可見,本文提出的基于時間窗的多目標(biāo)快遞配送路徑的數(shù)學(xué)模型利用GA算法進(jìn)行優(yōu)化時,當(dāng)?shù)?0代時,搜索到最優(yōu)值約為1152.53.而利用改進(jìn)AHP-GA算法進(jìn)行優(yōu)化本文提出的基于時間窗的多目標(biāo)快遞配送路徑的數(shù)學(xué)模型,當(dāng)?shù)?0代時,搜索到最優(yōu)值約為672.65.傳統(tǒng)的GA算法在初始種群為50,進(jìn)化代數(shù)為50時,很難跳出局部最優(yōu)解.而在相同條件下,本文提出的算法在設(shè)置個體種群為50時,能夠通過該算法很強(qiáng)的局部搜索能力跳出局部最優(yōu)解,在進(jìn)化代數(shù)為50時,能盡可能的搜索到全局最優(yōu)解,收斂效果遠(yuǎn)遠(yuǎn)優(yōu)于傳統(tǒng)的GA.因此,采用改進(jìn)AHPGA算法優(yōu)化調(diào)度成本效果遠(yuǎn)遠(yuǎn)優(yōu)于傳統(tǒng)GA算法,采用改進(jìn)AHP-GA算法優(yōu)化基于時間窗和拖期懲罰成本的多目標(biāo)快遞配送路徑如圖7所示.

圖7 改進(jìn)AHP-GA快遞配送路徑結(jié)果圖

7 結(jié)論

為提高物流配送效率,控制配送成本,提高顧客滿意度,本文提出了基于改進(jìn)AHP-GA算法優(yōu)化帶有軟時間窗的多目標(biāo)快遞配送路徑問題.本文利用改進(jìn)的AHP方法具有科學(xué)評價快遞配送路徑優(yōu)化問題中各層次目標(biāo)權(quán)重的優(yōu)勢且有效改善了構(gòu)建評價指標(biāo)權(quán)重子集的主觀性;而改進(jìn)的遺傳算法具有強(qiáng)大的搜索能力,自適應(yīng)調(diào)節(jié)能力以及優(yōu)化NP問題的能力,本文將二者有效的結(jié)合,有效解決了本文提出的帶有軟時間窗的快遞配送路徑多目標(biāo)優(yōu)化問題.此種方法在探究物流配送路徑改善方面具有顯著的優(yōu)勢,并能夠獲得理想的配送路徑,具有一定的實用價值意義.可為物流配送優(yōu)化調(diào)度問題提供參考.