基于人工免疫系統算法的建材企業車輛路徑問題優化

季曉紅

[摘 要] 建筑材料物流屬于大宗物資的運輸，占建筑項目成本比例很大，所以怎樣優化建材企業物流，降低成本成為國內外學者競相研究的課題。車輛路徑問題是建材企業配送系統可優化的三大部分之一。文章采用了基于人工免疫系統的車輛路徑優化算法，旨在求解距離總和最短的路徑組合。

[關鍵詞] 建材企業；物流配送；車輛路徑

doi ： 10 . 3969 / j . issn . 1673 - 0194 . 2017. 15. 027

[中圖分類號] F252 [文獻標識碼] A [文章編號] 1673 - 0194（2017）15- 0057- 02

0 前 言

隨著我國經濟的迅速發展，建材行業與我國國民經濟發展密切聯系在一起，這使建材市場迅速膨脹，這既是對建材行業的機遇又是巨大的挑戰。建材行業屬于大宗物資物流，材料成本在建筑工程項目里的比重到了60%～70%，而物流成本則占據了17%，所以建材物流是建材企業的重中之重，如何降低建材物流成本是每個建材企業的迫切需要。

1 基于人工免疫系統的物流配送車輛路徑問題方法概述

本文所研究的路徑優化目標為配送車輛所經歷的路徑的運輸距離和最小。采用的是先聚類后生成的求解模式，先聚類就是將客戶劃分為有限個聚類群體，然后對每個聚類群體求解出相應的路徑，即為車輛路徑問題的解，再通過策略找到距離之和最小的最優解[1]。本文首先設計了相對的算法后又引入了機會均等下的雙向學習策略，旨在得到更多相應的路徑，求得問題最優解。

2 配送車輛路徑模型的構造

2.1 問題假設條件

本文車輛路徑問題的條件假設：企業的客戶散布在系統網絡中，客戶的需求已知；企業的車輛容量相同且已知。

2.2 模型的構造

本文構造了如下的車輛路徑模型，如公式（1）-（3）所示：

minZ= cr·Xr（1）

s.t. arj·Xr=1，？坌j∈V（2）

Xr={0，1}，？坌r∈R（3）

2.2.1 變量及參數說明

V={1，1，…}：表示配送系統中的客戶集，任意客戶j∈V（位置為agj），對應需求為dj，0表示倉庫，ag0表示倉庫的地理位置；

R：表示所有路徑的集合；

Cr：表示路徑r的距離；

M：表示車輛容量；

arj：表示路徑r是否經過客戶j，如果arj=1，則表示“是”；如果arj=0，則表示“否”；

Xr：表示路徑r是否被選入問題解中，如果Xr=1，則表示“是”；如果Xr=0，則表示“否”。

2.2.2 模型說明

公式（2）保證了每位客戶只被一輛車服務，其需求在該方案中恰好滿足。公式（1）是在滿足公式（2）的前提下，問題的一組解。此公式考慮的是物流配送系統中配送里程最短條件。

2.2.3 基于人工免疫系統車輛路徑問題的求解編碼

本文需要對客戶聚類進行人工免疫系統編碼[2]。編碼規則參量：客戶j∈V為抗原；聚類子問題中的聚類中心i為抗體；AB為所有抗體組成的集合，i∈AB；abi為每個抗體i∈AB對應的位置；||abi-agj||為抗體i和客戶j之間的距離；|r|為路徑r中包含的所有客戶的數目。

引入0-1型決策變量uij，則其聚類客戶j∈V的規則表示為：

uij = 1，當||abi-agi||≤||abi-agk|（？坌uij≠1）且 uij+1≤|r|0，當 uij=|r|（4）

規則說明：公式（4）表示，當uij=1時，客戶j為所有未被聚類的客戶k（？坌uik≠1）中距抗體i的距離最近的客戶（uij=1且||abi-agj||≤||abiagk||），且抗體i中已經被聚類的客戶數目加上該客戶j，不會超過路徑的r所包含的客戶數目的最大值（ uij+1≤|r|）；當uij=0時，當且僅當抗體i中客戶的聚類數目已達到所對應路徑r的最大值|r|，則該抗體聚類完畢，不能再對剩余的客戶進行聚類。

2.4 網絡更新機制下初始抗體的生成

本文采用Mitra確定初始抗體的位置。每個初始抗體的位置都是從該抗體中選出一個客戶，該客戶的位置即為相應抗體的位置。初始抗體集合為AB ={i1，i2，…，in（N= dj / M）。 3 基于路徑覆蓋策略下的AIS優化算法

3.1 機會均等下的雙向學習

參考文獻[3]中的機會均等下的雙向學習策略旨在增加被抗體聚類次數較少的客戶的聚類次數，產生更優質路徑。每一次抗體擴增循環后，客戶都得到相等的路徑覆蓋次數。sT數目的標準覆蓋次數。令ABT-1=∪ABjT-1，ABjT-1={i|uij =1，i∈ABT-1}為上一次循環產生的抗體群ABT-1中聚類客戶j的抗體集合。每一循環T（1，2，…，T*），初始化ABjT = ABjT-1之后，步驟如下：

for j∈V

while （數目ABTj|≤sT）

任取i∈ABjT-1并記位置為abiold，依據abinew=abiold+αij（agj abiold），隨機產生αij∈[0，2][122]，得到新抗體inew，更新AbjT=AbjT∪inew

end

AB（T，temp）=∪

end

3.2 路徑算法求解

路徑算法求解過程如下：通過每次抗體的擴增循環后，進而產生更多不同的新路徑加入到路徑庫中，把路徑庫中的路徑組合利用ILOG CPLEX帶入公式（1）、（2）、（3）求解只有Xr（r∈RT）為變量的0-1線性規劃模型，RT對應的問題最優解和目標函數值被求出。

4 結 語

本文建材企業車輛配送路徑的背景下，以運輸路徑里程最短為目標，提出的基于人工免疫系統算法的車輛路徑問題，并引入機會均等下的雙向學習，擴大解的搜索范圍，得到更加優質解。本路徑算法優化了車輛路徑問題，對建材企業改善物流管理意義重大。

主要參考文獻

[1]穆東，王超，王勝春，等.基于并行模擬退火算法求解時間依賴型車輛路徑問題[J].計算機集成制造系統，2015，21（6）：1626-1636.

[2]Mitra S.A Parallel Clustering Technique for the Vehicle Routing Problem with Split Deliveries and Pickups[J].Journal of Operational Research Society，2008，59（11）：1532-1546.

[3]Cook W.Concorde TSP Solver[DB/OL].http：//www.tsp.gatech.edu/concorde.html.endprint