基于人工免疫系統(tǒng)算法的建材企業(yè)車輛路徑問題優(yōu)化

季曉紅

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

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

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

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

0 前 言

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

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

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

2 配送車輛路徑模型的構(gòu)造

2.1 問題假設條件

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

2.2 模型的構(gòu)造

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

minZ= cr·Xr（1）

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

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

2.2.1 變量及參數(shù)說明

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

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

Cr：表示路徑r的距離；

M：表示車輛容量；

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

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

2.2.2 模型說明

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

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

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

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

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

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

2.4 網(wǎng)絡更新機制下初始抗體的生成

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

3.1 機會均等下的雙向?qū)W習

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

for j∈V

while （數(shù)目ABTj|≤sT）

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

end

AB（T，temp）=∪

end

3.2 路徑算法求解

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

4 結(jié) 語

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

主要參考文獻

[1]穆東，王超，王勝春，等.基于并行模擬退火算法求解時間依賴型車輛路徑問題[J].計算機集成制造系統(tǒng)，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