基于人工免疫系统算法的建材企业车辆路径问题优化

季晓红

[摘 要] 建筑材料物流属于大宗物资的运输，占建筑项目成本比例很大，所以怎样优化建材企业物流，降低成本成为国内外学者竞相研究的课题。车辆路径问题是建材企业配送系统可优化的三大部分之一。文章采用了基于人工免疫系统的车辆路径优化算法，旨在求解距离总和最短的路径组合。

[关键词] 建材企业；物流配送；车辆路径

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