粒子群算法在铁路双层规划模型求解中的应用

郝鹏海+程晓荣

摘要：在众多群体智能优化算法中，粒子群算法是一种原理相对简单的启发式算法，与其他仿生算法相比，它所需的代码和参数相对较少。该文先介绍了标准的粒子群优化算法，在原有算法的基础上加入惯性权重因子[ω]，对算法进行了优化。最后通过粒子群算法对一种依据高速铁路票价建立的双层规划模型进行求解。

关键词：粒子群算法；惯性因子；双层规划；求解

中图分类号：TP31 文献标识码：A 文章编号：1009-3044（2017）26-0238-02

随着经济的发展，高速铁路已经成为人们越来越青睐出行方式，票价也是人们关注的主要问题之一，定制一个合理的票价是铁路首要考虑的问题，要在使铁路的利益最大化和乘客的满意度之间进行权衡，从而制定一个合理的票价。双层规划模型最早在研究非平衡经济市场竞争时提出，这一模型在制定高速铁路的票价过程中同样适用。

通过鸟群捕食过程中，每一只鸟之间的合作，达到团体最优的行为，美国学者Eberhart、Kennedy提出一种基于个体寻求团体最优解的算法—粒子群算法（PSO）[1]。粒子群算法的基本机制是通过迭代算法实现的，首先在固定的范围内生成一组随机数当作粒子，通过迭代函数刷新粒子的运行速度和在固定范围内的位置，通过最优解函数寻找最优解。因此本文采用粒子群算法来寻求双层规划函数的最优解。

1 粒子群算法

随机产生的每一个粒子的位置首先被确定为该粒子的最优解。每次迭代中，首先会刷新粒子的位置和速度，然后与最优解比较，最后保存更符合目标函数的解为最优解。所有粒子中更符合目标函数的为全局最优解[2]。迭代在达到规定的次数或者目标函数到达可以接受的误差时结束。

PSO中并没有太多的参数，下面介绍常见的几种参数。

（1） 粒子数：粒子即个体，例如鸟群中的一只鸟就可以看做一个粒子，通常粒子数取10-30可满足需要，对于部分复杂的问题，粒子数可以取100-300之间，为了体现粒子的多样性并且找寻最优的优化路径。

（2） 惯性权重[ω]：[ω]是粒子持续移动的惯性参数，能使离子数组扩大搜寻范围，有利于整个粒子种群搜索最优解。[ω]在改进后的粒子群算法中具有相当重要的作用，[ω]决定了原始速度在下一次迭代中所占的比例，一般在迭代的过程中[ω]不断递减，这样可以在算法初始具有良好的全局搜索能力，随着搜索的进行，逐步确定最优区域，算法的局部搜索能力也随之提升。

（3） 最大速度Vmax：Vmax决定粒子在循环中移动的最远距离，即粒子当前位置和最优位置之间的区域的准确度。Vmax不宜太大或者太小，太大粒子会飞过最优位置，太小会导致局部最优[3]。

（4） 学习因子[c1]和[c2]：[c1]、[c2]用于调整每一个粒子自身经验和社会经验在其移动搜索中的作用，表示每一个粒子飞向本身最优解和全局最优解的位置的随机加速项的权重，一般都取值为2。

1.1 数学模型

基本粒子群算法的执行顺序如图1所示，具体步骤为：

1） 初始化粒子群：初始化粒子群中粒子的数量和每一个粒子应该包含的特性，包括每一个粒子的初始化速度和初始化位置。

2） 根据要优化的问题确定合适的适应度函数来评定每一个粒子。

3） 把整个粒子群中每个粒子的适应度值与此粒子的历史最优解比较，若适用度值大于该粒子历史最优解，更新该粒子历史最优解。

4） 把整个粒子群中每个粒子的适用度值与全局历史最优解比较，若适用度值大于全局历史最优解，更新该粒子历史最优解。

5） 通过循环迭代不断更新粒子速度和位置。

6） 重复1）-5）步骤，直到满足停止条件（误差达到可接受的范围或达到最大迭代数）停止迭代为止。

2 车票模型构建

2.1 双层规划模型

上层函数通过设置的值影响下层函数，n是m的函数，通常称函数n=n（m）为反应函数。双层规划能够解决两个层次之间的统一与协调，双层规划中的上层函数的决策并不直接影响下层函数的决策，两者是指导和被指导的关系，下层函数在上层函数结果的指导下，可以在约束范围内进行自由决策。因此，上层函数在决策时也要考虑下层函数的自由决策会对自己产生的影响。

2.2 铁路票价模型

高速铁路的票价直接影响旅客的选择，而旅客在各种交通工具中的所占比重反过来也会影响票价的制定，因此铁路管理部门就是上层函数，而旅客出行选择就是下层函数。文献[5]研究了双层规划模型在铁路票价中的应用，本文在文献[5]的基础上构建的模型如下：

2.2.1 上层模型构建

铁路的广义费用和客流量正相关。通过查阅资料，在本篇论文里我们采用幂函数形式。通用形式为：[fs（ds）=αqβs+Es]。其中[fs（ds）]是铁路运营的广义费用，[qs]是铁路客流量，[α]和[β]是权重系数，[Es]是其余的可预测费用。

3 基于粒子群算法求解双层规划函数

双层规划问题的求解十分困难，它是一个NP-HARD问题，尤其是对于变量较多的情况下，其全局最优解难以求出[7]。粒子群算法是一种群体智能优化算法，能够解决很多全局收敛以及全局优化的问题，并且它所需的代码和参数相对较少，因此把粒子群算法用于双层规划优化求解具有一定的可行性。

粒子群算法本质是基于迭代算法实现，因此本文采用基于粒子群算法的双层迭代规划算法，双层规划下层模型是旅客均衡模型，采用Frank-Wolfe算法对其进行求解，采用标准的粒子群改进算法求解上层模型，然后上下层反复迭代直至逼近最优解。

求解过程如下：

（1） 初始化粒子群参数。学习因子[c1]和[c2]取2，粒子种群数量m取20，粒子初始位置[Xs]和初始速度[Vs]，最大权重因子[ωmax]0.99，最小权重因子[ωmin]0.01，更新速度的范围是[-0.05，0.05]，满足下层规划函数的始解[ns]随机产生，[ns]是不同交通方式s的客流量，[Ps]为第s个粒子的初始位置，[Pb]是粒子群中的最优位置。

（2） 把上层规划中粒子s的位置即票价[Xs]代入下层函数，然后利用Frank-Wolfe算法求得最优解[y?s]，即各种类列车的客流量。

（3） 把[Xs]和[y?s]代入上层函数，所得到的函数值[F（Xs，y?s）]就是粒子s的适应度。

（4） 若更新后粒子的适应度比[Ps]的適应度高，则用[Xs]替代[Ps]，若更新后粒子的适应度比粒子群中所有粒子的适应度都要高，则用[Xs]替代[Pb]。

（5） 若此时函数已经收敛，则跳转到（7），否则根据公式1-1和1-2计算出更新后粒子的速度和位置，然后重复步骤（2）（3）（4）。

（6） 迭代结束，输出最优解[Pb]。

4 总结

合理的运用粒子群算法可以简化很多复杂函数的求解问题，并且实现资源的最大化利用，自粒子群算法被提出以来，有很多的改进机制，也被应用在了各种方面，在高速铁路方面的应用目前还并不是很成熟，本文通过反复迭代双层规划函数，逼近最优票价，在铁路的利润最大化和乘客的满意度之间取得了平衡。

参考文献：

[1] 唐娜. 改进粒子群算法及其应用研究[D].合肥工业大学，2016.

[2] 吴高超. 基于粒子群算法的路径规划问题研究[D].燕山大学，2016.

[3] 宁必锋.一种改进的粒子群算法在解非线性方程组中的应用[J].吉林化工学院学报，2013（30）；114-116.

[4] 任爱红.几类复杂双层规划问题的算法研究及应用[D].西安电子科技大学，2014.

[5] 姜达.基于不同运输方式竞争的高速铁路票价制定方法研究[D].西南交通大学，2014.

[6] 王修华.客运专线票价制定机理研究[J].铁道勘察，2008（2）：91-94

[7] 李和成，王宇平.几类非线性双层规划问题的混合遗传算法[J].系统工程与电子技术，2005，30（6）：1265-1272.endprint