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

李鳳坤

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

1 引言

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

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

遺傳算法(Genetic Algorithm,GA)是由美國(guó)J.Holland 教授受生物進(jìn)化論的啟發(fā)而提出的一套較為完整的理論和方法,是一種基于適者生存,優(yōu)勝劣汰遺傳機(jī)制的自然選擇和進(jìn)化原理的全局搜索隨機(jī)算法、該算法搜索能力強(qiáng)大,遺傳算法在選址問題、配送問題、調(diào)度問題、運(yùn)輸問題、布局問題方面具有重大的意義.該算法利用自然選擇規(guī)律和基因遺傳機(jī)制來實(shí)現(xiàn)仿生運(yùn)算,它對(duì)適用條件幾乎沒有任何限制,以概率論為基礎(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)勢(shì),消除了極端值的不良影響,科學(xué)評(píng)價(jià)快遞配送路徑優(yōu)化問題中各層次目標(biāo)權(quán)重,并給出最佳定量值.同時(shí)利用改進(jìn)遺傳算法解決全局優(yōu)化問題的優(yōu)勢(shì),提高了決策的時(shí)效性和有效性.

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

2 問題描述

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

如5位專家分別對(duì)P1S1、P1S2、P2S2、P2S3、P35個(gè)指標(biāo)項(xiàng)權(quán)重評(píng)分分別為:

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

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

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

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

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

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

5.1 編碼設(shè)計(jì)

本文采用自然數(shù)編碼的方式,用0代表配送中心,自然數(shù)1,2,…,N代表客戶點(diǎn),每個(gè)客戶點(diǎ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.該染色體實(shí)質(zhì)是一條忽略了車載容量約束和時(shí)間窗約束的廣義路徑.

圖2 編碼設(shè)計(jì)

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

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

5.2 選擇操作

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

5.3 交叉操作

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

圖3 交叉操作

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

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

5.4 變異操作

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

5.5 適應(yīng)度評(píng)估

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

圖4 變異操作

6 實(shí)例分析

6.1 實(shí)例介紹

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

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

6.2 實(shí)驗(yàn)結(jié)果

本文分別利用傳統(tǒng)的GA算法和改進(jìn)AHP-GA算法對(duì)表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 各客戶點(diǎn)坐標(biāo)及需求

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

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

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

7 結(jié)論

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