基于免疫算法的共享电动汽车网点选址研究

李伟斌，吴 芳，张 燕

(兰州交通大学 交通运输学院，兰州 730070)

近年来，随着大数据、云计算、人工智能等高科技的快速进步，共享经济给中国的经济发展注入了新鲜的血液.共享电动汽车推动着共享经济的高速发展，共享电动汽车对于缓解大城市交通拥堵、保护环境、节约能源方面有着重要意义.但在其发展中面临着如下问题，共享汽车基础设施不足，租赁网点较少且布局不合理，无法满足顾客租车需求.本文将通过优化网点布局，在规划建设阶段制定更优可选择方案，从而实现共享电动汽车系统资源的合理开发和使用.

国内外部分学者对电动汽车选址进行研究，并取得了一定的成果，如Erdogan等[1]提出了一种建设性的基于中值定理的精确分支切割算法，用于优化处理选址问题.Correia等[2]基于混合整数规划模型，考虑所有收入和成本的情况下使共享汽车企业的利润最大化.郑建国等[3]基于混合整数规划模型提出了一种充电站的容量和服务范围内的需求量相适应的方法，并进行了模拟仿真测试方法的松弛度和性能.以上学者采用了精确求解算法求解选址问题.Frade等[4]构造了最大化满足顾客需求的选址模型，以可用预算为约束条件，利用优化算法求解租赁系统的选址问题.Avella等[5]通过提出拉格朗日定理的P中值模型的新启发式算法实现达到尽量减少设施数量的目的.马作浩[6]引入共享电动汽车低碳和惩罚的市场特征网点前期选址的相关决策因素，基于P中值思想设计了多目标模型.杨宇[7]构建基于P中值的组合分配模型，对基于需求的单一判断模型和基于成本的分配模型结合后求解，得出车辆分配方案.马群[8]采用遗传算法进行求解租赁网点布设方案和车辆投放方案.创新地开发了网点布设仿真系统，输入参数可直接求解出网点的布设和投放方案.卢婷等[9]从三个角度考虑了网点选址影响因素，考虑相关约束条件情况下，利用遗传算法进行求解多目标多约束的网点选址模型.吴阳等[10]以居民出行距离最短和网点数量较少为目标函数，并以网点的覆盖范围、行驶距离等作为约束条件，建立了网点布局优化模型，利用改进遗传算法对模型进行求解.杨新渥等[11]建立考虑用户利益和社会投资的双层规划模型，采用了模拟退火算法求出最优解.闫天泽等[12]建立了车流信息及用户成本的电动汽车充电站最优规划模型，对传统粒子群算法引入模拟退火思想求解模型.

从研究现状可知，其主要使用精确求解算法和启发式算法模型求解的理论和方法.精确求解算法需遍历出所有可行解，计算量大且效率较低；启发式算法中传统遗传算法具备快速随机搜索能力，但是传统遗传算法有易早熟、局部搜索能力差问题.而免疫优化算法通过其维持机制和多样性产生的特点来保证群体的多样性，能够解决多数寻优过程尤其是多峰函数寻优过程中的“早熟”问题，最终求得全局最优解；免疫算法对抗体的评价较为全面，其选择抗体的方式也更加合理；免疫算法中还对抗体产生鼓励或者抑制作用，体现免疫算法的良好自我调节功能，从而保证种群的多样性.基于以上优势，结合具体问题对算法步骤进行设计，可得出研究区域网点的布设方案，为企业提供系统的规划时期建议.

1 问题描述

共享电动汽车网点选址是解决从多个候选网点中选择合适的网点，使得企业收益最大、出行总距离最少、运营成本花费最少.由于共享电动汽车网点选址过程中有共享电动汽车的保有量、站点之间的距离等主要的决策影响因素，为了方便研究科学性，对模型预先进行如下假设.

1)假设各个备选网点的位置、企业计划投入的车辆数、土地价格、汽车购置费、单位距离调度单价均已知；

2)假设所有共享网点的电动汽车只有一类汽车，充满电的行驶里程能达到100%发挥，电池不发生电量损耗；

3)假设在运营中，共享电动汽车企业总能通过车辆调度满足顾客的需求，完全覆盖距离内不产生惩罚成本；

4)本文为了计算更加简洁明了，暂不考虑共享电动汽车续航里程、电池电量、网点充电桩数量等诸多因素.

2 模型建立

2.1 选址过程分析

本文共享电动汽车网点选址方案的选择应满足以下要求，保证企业的利润，尽量增大企业的收益以及减少企业的运营成本；其次为了更好地保证顾客的需求，本文在构建共享电动汽车网点选址模型时追求所有网点与到相应需求点的距离成本最小.各目标函数如下：

1)企业总运营收益最大.

maxf1=NLM;

(1)

2)网点的固定成本和企业经营成本.

(2)

3)各网点与到相应需求点的距离成本.

(3)

式中：f1为总运营收益，元；f2为网点的固定成本和经营成本，元；f3为各个网点与到相应需求点的距离成本，元；N为一年中运营天数，d；L为企业计划投入共享电动汽车数，辆；M为一辆共享电动汽车的日收益，元；a1为网点建设土地费用，元；a2为企业购置单位共享电动汽车费用，元；a3为企业的调度费用，元；a4为企业的充电费用，元；n1为土地建设费用计费周期，a；n2为企业购置汽车费用计费周期，a；μ为单位距离惩罚费用，元.

2.2 数学模型

本文最后衡量结果需要将多目标函数归一化处理为单目标函数，所以本文通过线性加权方法把三个多目标函数归一化处理为最大化的单目标函数.本文构建的共享电动汽车网点选址优化模型如下.

目标函数为：

(4)

式中：f为目标函数值；W1为企业总运营收益权重系数；W2为固定成本和经营成本权重系数；W3为距离成本权重系数；C取一个趋近于正无穷的数;

(5)

为惩罚函数，对于违反距离约束的解给予惩罚.

约束条件为：

(6)

(7)

(8)

(9)

(10)

yij≤xj,i∈I,j∈J;

(11)

xj1·xj2·dj1j2≥d1,j∈J;

(12)

(13)

(14)

式中：n为计划建设网点的数量；φ为网点最大服务覆盖率，%；d1为网点间最小距离，m；d2为网点最大服务距离，m；dij为网点j到需求点i的距离，m；wij为网点j对需求点i覆盖程度.

式(4)为模型的目标函数；式(6)～式(14)均为模型的约束条件.其中式(6)表示网点位置选择的0-1变量；式(7)表示需求点i是否与网点j相连的0-1变量；式(8)保证网点个数为n个；式(9)保证选择的网点个数至少5个，最多15个；式(10)保证每个需求点仅有一个网点为其服务；式(11)保证每个需求点都有相对应的网点为其服务；式(12)保证网点之间的距离必须大于等于d1；式(13)保证网点与其服务的需求点间的距离必须小于等于d2；式(14)保证网点对其服务的需求点覆盖程度不低于预设数值.

3 算法设计

本文考虑该网点选址问题的约束条件和目标函数，结合问题设计算法步骤，通过求解模型可得出研究区域网点的布设方案，文中算法流程如图1所示.

图1 算法流程

3.1 染色体结构设计

考虑本文模型特点，对网点选择采用实数编码.每一个选址方案可生成一条长度为n的抗体，其中n为网点的个数，每个抗体表示被选为网点的序列.假设考虑从30个候选网点中选出8个网点，则种群中的其中一条抗体[4,15,11,23,2,27,6,19]表示在候选网点4,15,11,23,2,27,6,19处建设网点.

3.2 解的评价

3.2.1 抗体浓度

抗体浓度Cν为种群中的相似抗体所占比例，即

(15)

式中：M为种群数，

(16)

式中：kν,s为抗体ν与抗体s中相同的位数；L1为抗体的长度.例如，两个抗体为[2,5,23,15,14,25,11,3]、[2,11,16,9,7,21,15,25]，其中有4个相同的值，经计算他们的亲和度为0.5，T为预设的一个亲和度阈值.

3.2.2 期待繁殖概率

在种群中，每个抗体的期望繁殖概率P由适应度值(即目标函数值f)和抗体浓度Cν两部分共同决定，其中α为0.95，即

(17)

免疫算法在抑制高浓度抗体时，适应度最高的抗体可能会因其浓度高受到抑制，从而导致丢失已求得的最优值，所以本文采用了精英保留策略，在每次更新种群时，先将适应度最高的若干个抗体存入记忆库，再根据期望繁殖概率将剩余抗体存入记忆库[13].

3.3 种群更新

3.3.1 选择

本文采用轮盘赌的选择机制进行选择操作，由公式(17)可知，抗体适应度的越高，期望繁殖概率越大，则抗体被选择的概率越大；个体浓度越大，期望繁殖概率越小，则抗体被选择的概率越小.这种方法不仅鼓励了适应度高的抗体，也抑制浓度高的抗体，保证了种群的多样性.

3.3.2 交叉

本文采用部分匹配交叉(PMX重组)方式，即在种群中随机选取一对抗体A和B(父代)，两个抗体随机选择一个相同的交叉点，交换交叉点后两组基因的位置，得到A1和B1(子代)，抗体交叉过程示意图如图2(a)所示.最后进行基因冲突检测，根据交换的两组基因建立一个映射关系如图2(b)所示，以6-16-26这一映射关系为例，可以看到子代A1有相同的基因26，通过映射关系将交叉点前的基因26转变为基因6，以此类推至没有冲突为止.对抗体B1同样处理，即可得到抗体A2和B2(子代)[14].

图2 抗体交叉示意图

3.3.3 变异

本文中免疫算法的抗体变异采用常规的变异方法，即在基因长度和数值的取值范围内，随机生成1个变异位置，并随机生成一个基因.然后对抗体进行基因冲突操作，若抗体中出现重复基因，则在原变异位置，重新随机生成一个基因，直到抗体中无重复的基因，变异操作即可结束，抗体变异示意图如图3所示.

图3 抗体变异示意图

4 案例及结果分析

依据ArcGIS软件，找到安宁区部分学校、居民小区、商场、旅游景区、地铁站点等共计30个共享汽车候选网点，候选网点分布图如图4所示.同时根据《中国主要城市土地交易情报》文件，获取到每个候选网点2020年的地皮单价，部分候选点属性如表1所列.为了方便计算距离矩阵dij，需要将候选网点的经纬度坐标转换为二维平面坐标.模型中网点间最小间距d1为3 km，网点最大服务距离d2为2 km，网点覆盖程度预设数值φ为45.0%.通过专家分析法和层次分析法确定的目标函数权重W1为0.4、W2为0.25和W3为0.35.模型中相关参数如表2所列.网点选址过程中的各项成本如表3所列.

图4 候选网点分布图

表1 部分候选点属性

表2 模型相关参数

表3 模型参数设置

免疫算法相关参数为：迭代次数为100，种群大小为100，记忆库容量为10，交叉概率为0.5，变异概率为0.4.为了分析不同网点数对网点选址方案的影响，分别求解n取6、7、8、9和10时的网点选址优化方案.本文在选取不同网点数的情况下，分别运行10次，从10次运行结果中选取目标函数值最大的最优解.

当n取值不同时，计算得到不同的网点选址方案，目标函数值、各需求点到相应网点的总距离和平均覆盖度率也会随之变化.不同网点数求解结果如表4所列.当n=8时，目标函数值达到最优值，因为本文重要考虑企业收益，故将选取8个租赁点的选址方案.

表4 不同网点数求解结果

经过计算，本文利用免疫优化算法对模型进行求解，算法在迭代了51次后收敛到最优解，免疫优化算法收敛图如图5所示.算法得出的选址方案为1、2、3、4、6、9、17、18，即在甘肃高级人民法院、中海广场、兰州植物园、桃海市场、金水湾2号院、培黎广场、金河丽园和华泰佳苑处计划建设网点.此时该选址模型最优解为1 301 678.53，各需求点到相应网点的总距离为21 745.26 m，平均覆盖度率为79.3%，模型求解结果如表5所列.

图5 免疫优化算法收敛曲线

表5 模型求解结果

5 结论

本文首先论述了共享电动汽车网点选址问题，构建了网点选址优化模型，通过设置合理的目标函数与约束条件，保证了企业总收入最大、运营成本最小和出行总距离最短的目标.采用了免疫优化算法求解出该模型中共享电动汽车网点选址的最佳方案，最后结合实际算例，计算出最佳网点选址结果，验证了该模型和算法的有效性和正确性.通过对比研究发现，求解不同网点数下的选址方案，发现随着选取网点数的变化，最优方案会发生变化，出行总距离及平均覆盖率也随之变化；在满足相关约束的前提下，选取适当的网点数，在一定程度上能增加企业的利润.但本文只研究了共享电动汽车网点选址问题，而共享电动汽车系统实际运营中，调度、充电以及顾客的需求都是动态变化的.如何根据实际的动态要求，对运营中的共享电动汽车进行合理的调度、将是今后进一步研究的内容.