改進AHP-GA算法的多目標配送路徑優化①

李鳳坤

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

1 引言

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

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

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

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

本文構造的改進AHP-GA算法有效整合中位數AHP算法和遺傳算法的優勢,消除了極端值的不良影響,科學評價快遞配送路徑優化問題中各層次目標權重,并給出最佳定量值.同時利用改進遺傳算法解決全局優化問題的優勢,提高了決策的時效性和有效性.

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

2 問題描述

快遞配送的最優路徑,必須滿足以下約束:

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

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

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

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

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

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

本文要解決的配送問題是在以上約束條件的基礎上,如何進行車輛調度,以滿足總配送成本最低,總的配送時間最短,配送車輛最少.其中配送成本包括車輛在約定時間之前到達獲得的機會成本、在約定時間之后到達的罰金成本以及車輛行駛的費用.因此,本文可歸結為多目標優化問題.

3 數學模型構建

基于以上目標構建的數學模型如下:

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

式(7)中w1,w2,w3分別為3個目標函數的系數權重.

4 構建評價指標權重子集

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

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

(2)根據專家打分,對準則層進行指標重要性排序.

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

圖1 快遞配送方案層次結構(AHP)圖

如5位專家分別對P1S1、P1S2、P2S2、P2S3、P35個指標項權重評分分別為:

則計算的中位數分別為

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

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

(4)計算各層要素對系統目的(總目標的合成(總)權重,選擇最優方案.由(3)可得因素層指標項所占整個指標體系的權重.

將式(8)代入已經定義好的數學模型式(1)、(2)、(3),將其加和,得到目標函數.

5 改進遺傳算法求解

5.1 編碼設計

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

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

圖2 編碼設計

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

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

5.2 選擇操作

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

5.3 交叉操作

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

圖3 交叉操作

其中,交叉概率采用自適應調節機制,以滿足在初期適應度值較大時,需要增大交叉概率,在適應度值趨于穩定時,需要適當降低交叉概率.故交叉概率采用文獻[10]提出的自適應調節機制.

其中,G: 最大迭代數;g: 當前迭代數;fmax: 當前所有個體的最大適應度值.

5.4 變異操作

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

5.5 適應度評估

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

圖4 變異操作

6 實例分析

6.1 實例介紹

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

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

6.2 實驗結果

本文分別利用傳統的GA算法和改進AHP-GA算法對表1中的數據執行100次得到GA優化調度成本結果如圖5所示、改進AHP-GA優化調度成本結果如圖6所示,由改進AHP-GA規劃路徑結果如圖7所示.

表1 各客戶點坐標及需求

圖5 GA算法優化調度成本結果

由仿真結果可見,本文提出的基于時間窗的多目標快遞配送路徑的數學模型利用GA算法進行優化時,當迭代到50代時,搜索到最優值約為1152.53.而利用改進AHP-GA算法進行優化本文提出的基于時間窗的多目標快遞配送路徑的數學模型,當迭代到50代時,搜索到最優值約為672.65.傳統的GA算法在初始種群為50,進化代數為50時,很難跳出局部最優解.而在相同條件下,本文提出的算法在設置個體種群為50時,能夠通過該算法很強的局部搜索能力跳出局部最優解,在進化代數為50時,能盡可能的搜索到全局最優解,收斂效果遠遠優于傳統的GA.因此,采用改進AHPGA算法優化調度成本效果遠遠優于傳統GA算法,采用改進AHP-GA算法優化基于時間窗和拖期懲罰成本的多目標快遞配送路徑如圖7所示.

圖7 改進AHP-GA快遞配送路徑結果圖

7 結論

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