基于免疫优化算法的战略装车点选址研究

（西南交通大学 交通运输与物流学院，四川 成都 610031）

1 研究背景

国家“十二五”综合交通发展规划战略目标明确提出：大宗货物要实现重载化，加快既有区域干线扩能改造和新线建设，完善跨区域大能力运输通道[1]。战略装车点作为重载运输通道组成的一部分，是整个重载运输网络的关键节点，它联系着货物的供给点和需求点，是货物运输的中转站，重载运输通道拓扑结构图如图1所示。对战略装车点的合理布局既可以提高线路的利用能力、节省铁路支出、降低铁路运营成本、增加经济效益，还可以充分完善我国的重载通道资源配置，优化通道结构。同时，随着货运作业集中化的推进，也有利于组织直达列车，加快货物和车辆的周转，对发展重载运输、完善重载通道理论体系建设具有重要意义。

图1 重载运输通道拓扑结构图

目前对装车点选址研究的大多停留在宏观层面的指导和常规的选址方法研究上[2-3]，缺少对新型方法的探索和理论研究。由于战略装车点的选择优化问题是一个复杂多约束的NP问题，采用常规方法求解时收敛速度慢，有时得不到最优解，而免疫优化算法具有寻优能力强、收敛性能好等优点，因而拟构造一种基于免疫优化计算的战略装车点选址优化方案。

2 重载战略装车点选址优化问题的数学描述

2.1 条件假设

为方便构建模型，假定以下条件：①战略装车点的货运处理能力足够大，在模型应用期内不会出现装车点处理能力不够的情况；②各货源点和需求点的供需能力已知；③初始装车点备选集已知，在备选集中寻优。

2.2 模型建立

战略装车点选址关键是在供给点和需求点之间选择最优的装车点，即从给定的战略装车点备选集中确定使整个路网运输费用最低的战略装车点。

定义 0-1 决策变量 zk如下。

综合考虑运输成本、装车点建设费用及装车点货物处理费用，建立模型如下。

模型中，式⑵为目标函数，旨在使综合运输费用最小；式⑶和式⑷分别为货物的供给约束和需求约束；式⑸为节点流平衡约束；式⑹为建设资金约束。其中，为i 货源点到第 k 装车点的单位运输费用，元/t；为k 装车点到 j 需求点的单位运输费用，元/t；为第 k 装车点的货运处理费用，元/t；为第 k 装车点的日均建设费用，元/d；xik为i 货源点到第 k 装车点的运输量，t；ykj为k 装车点到 j 需求点的运输量，t。

3 基于免疫优化算法的选址方案

3.1 算法思想

生物免疫系统是1个高度进化的生物系统，它旨在区分外部有害抗原和自身组织，从而保持有机体的稳定。从计算角度分析，生物免疫系统是1个高度并行、分布、自适应和自组织的系统，具有很强的学习、识别和记忆能力。免疫算法是1种受生物免疫系统启发，在免疫学理论基础上发展起来的新兴智能计算方法。它利用免疫系统的产生和维持机制来保持群体的多样性，克服了一般寻优过程尤其是多峰函数寻优过程中难处理的“早熟”问题[4]。

3.2 编码方案和初始抗体的产生

在备选方案集里选择合适的装车点采用实数编码方式比较直观，每个选址方案可以形成一个长度为L的抗体 (L为战略装车点的建设数量)，每个抗体代表被选为战略装车点的一个序列。免疫优化算法的计算需要一个初始抗体群，因此算法开始阶段需随机产生一个初始种群。由于免疫算法需要经过一定代数的繁殖才能获得最优解，因而在每一代的繁殖过程中都可以根据问题的先验知识和历史数据得到一些较好的潜在最优解，把这些解存入记忆库，在下一代计算中取出和子代抗体组成初始抗体种群作为算法输入参数进行寻优计算，可以有效提高收敛速度。

3.3 抗体多样性评价

3.3.1 抗体与抗原间亲和力

把目标函数解看作抗体，战略装车点的选址优化问题看作抗原，那么抗体与抗原之间的亲和力可以表示为抗体对抗原的识别程度，即衡量抗体质量的一个重要指标。针对装车点的选址问题，设计抗体与抗原间亲和力函数为

3.3.2 抗体与抗体间的亲和力

抗体与抗体之间的亲和力反映了抗体之间的相似程度。该处借鉴由 Forrest 等提出的R 位连续方法计算抗体与抗体间的亲和力。R 位连续方法时确定一个判定阀值 R，如果2个抗体中有超过 R 位或连续 R 位的编码相同，则视2个抗体近似相同，否则可视为2个抗体不同，即在2个任意的选址方案中，如果存在 R个相同的装车点，则认为2个方案一样，此时2个方案的多样性降低，不利于算法找到最优解。针对战略装车点选址问题，考虑采用变形的R 位连续方法，即不考虑编码排序，不考虑阀值 R，计算公式为

式中：Sv.s为抗体 v 与抗体 s 间的亲和力；kv，s为抗体v与抗体s中相同的位数；L为抗体长度。

3.3.3 抗体浓度

抗体浓度指群体中相似抗体所占的比例，计算公式为

3.3.4 期望繁殖概率

在群体中，每个个体的期望繁殖概率 P 由抗体与抗原间亲和力 Av和抗体浓度 Cv2个部分共同决定，计算公式为

式中：α为常数，也称为抗体多样性评价参数。

从式(11)可知，抗体的适应度越高，被选中的期望繁殖概率越大；抗体的浓度越高，被选中的期望繁殖概率越小。通过在鼓励适应度高抗体的同时抑制浓度高的个体，可以保证种群的多样性。免疫优化算法在抑制高浓度抗体时，与抗原亲和度最高的抗体也可能因其浓度高而受到抑制，从而导致已求得的最优解丢失。因此，采取精英保留策略[6]在每次更新记忆库时，先将与抗原亲和度最高的几个抗体存入记忆库，再按照期望繁殖概率将剩余群体中优秀个体存入记忆库。

3.4 免疫操作

（1）选择算子。采用轮盘赌方法[7]进行选择操作，抗体被选择的概率为公式⑾计算出的期望繁殖概率。

（2）交叉算子。采用单点交叉法进行交叉操作。

（3）变异算子。采用随机变异位法进行变异操作。

3.5 算法步骤

根据上述分析，具体算法步骤如下。

步骤 1：分析具体问题及其解的特性，确定合适的有利于算法迭代的算子形式。

步骤 2：确定抗体种群规模 N 和记忆库容量 M。在首次初始化抗体群时，由于记忆库抗体为空，所以先随机生成 N个抗体；在以后的子代中，皆由记忆库中的M个抗体和 (N－M)个经选择、交叉、变异产生的抗体共同组成初始抗体群。

步骤 3：对上述种群中的各个抗体进行评价。通过抗体的多样性评价，确定个体的期望繁殖概率 P。

步骤 4：形成父代群体。将初始抗体群按期望繁殖概率 P 进行降序排列，取前 M个存入记忆库中，取前 N个抗体作为父代群体。

步骤 5：判断是否满足结束条件，若满足则结束，所得的当前最优解即为问题最优解；否则，进行步骤6操作。结束条件一般为算法迭代到最大代数、算法迭代时间停止或2次迭代的最优解误差在容许范围内。

步骤 6：新种群的产生。在新形成的父代群基础上，对抗体进行选择、交叉、变异操作得到新的抗体群，再从记忆库中取出全部抗体，共同构成新的种群。

步骤 7：转到步骤 3。

4 算例验算

4.1 背景条件

为验证算法的有效性，构造以下算例：设某区域重载路网有16个货源点和20个需求点，现欲在10个备选战略装车点中选取4个择优建设，建设费用投资在14700 万元以内。各货源点提供的货物量和各需求点的货物需求量分别如表1 和表2所示。

综合考虑运距和货物周转量的影响，得到从货源地到装车点、从装车点到需求地的单位运输费用分别用矩阵 cos tO 和 cos tD 表示，单位元/t。

表1 货源地所提供的货物量 t

表2 需求地对货物的需求量 t

假设装车点建成后的使用寿命为20个考察期，每个备选装车点的建设费用和单位货物处理成本如表3所示。

表3 备选装车点建设费用及货物处理成本

4.2 参数确定

设抗体种群规模 M=4 0，其中记忆库容量N =10；算子的交叉概率pcross=0.5、变异概率pmutation=0.4。算子的选择概率由期望繁殖概率确定，抗体多样性评价参数 α = 0.95，抗体长度 L = 4，最大迭代次数 MAXGEN = 30。在初始种群生成前，根据模型约束，先随机生成40组运量分配矩阵用于算法适应性评价。

4.3 结果分析

把确定的参数作为已知条件输入算法，经 matlab运算得到最优解 bestchrom = [9 6 7 2]，最佳适应度值 min F = 1 861.8 万元，从货源地到装车点和从装车点到需求地的最佳货流分配分别用矩阵 c arg oO和 c arg oD所示，单位 t。

战略装车点选址优化收敛曲线如图2所示，经过12次迭代后算法收敛到最优并且趋于平衡，从而证明了算法收敛的快速性。通过分析图中最优适应度曲线和平均适应度曲线的走向可知，每一次迭代后曲线都呈下降趋势，进而证明了该算法的可靠性。

图2 战略装车点选址优化收敛曲线

5 结束语

通过把战略装车点的选址问题抽象为1个3层网络结构，在建立目标函数时综合考虑上层决策者和下层客户间的利益，以实现整个运输系统成本最小化，最后在此基础上运用免疫优化算法进行求解。算法的创新之处在于使运量分配和装车点选址在算法寻优过程中紧密结合，使得运量分配和选址问题同时达到最优，为战略装车点的建设提供一套科学可行的方法。

[1] 中华人民共和国国务院.“十二五”综合交通运输体系规划[J].综合运输，2012(7)：4-17.

[2] 纪丽君，林伯梁，乔国会，等.战略装车点多点选址模型及算法[J].北京交通大学学报，2009，33（6）：31-35.

[3] 纪丽君，林伯梁.战略装车点选址模型研究[J].铁道学报，2008，30(5)：8-11.

[4] 史 峰，王 辉，胡 斐，等.MATLAB 智能算法30个案例分析[M].北京：北京航空航天大学出版社.

[5] 朱思峰，刘 芳，柴争义，等.基于免疫计算的IEEE 802.16j网络基站及中继站选址优化[J].计算机研究与发展，2012，49(8)：1 649-1 654.

[6] 杨咚咚，焦李成，公茂果.求解偏好多目标优化的克隆选择算法[J].软件学报，2010，21(1)：14-33.

[7] 玄光男.遗传算法与工程优化[M].北京：清华大学出版社，2004.