模拟退火算法在企业铁路车辆调度中的应用

林满山 郭永辉

（北方工业大学信息工程学院，北京100043）

0 引言

随着经济的发展，拥有自备铁路站的企业越来越多。这些企业内的铁路线之间连接情况各不相同，每条线路的长度也不尽相同，各个仓库在线路上的分布更是千差万别，如何使将一个站点上的车辆调度到企业内部各个仓库站点所行驶的路程最短，是企业火车调度所面临的一个问题。本文将使用模拟退火算法求路程最短的车辆调度路径。

1 模拟退火算法

模拟退火算法的思想最早是由Metropolis等提出的，其出发点是基于固体物质的退火过程与一般的组合优化问题之间的相似性［1］。模拟退火过程由3部分组成：（1）加温过程。其目的是增强粒子的热运动，使其偏离平衡位置。当温度足够高时，固体将熔为液体，从而消除系统原先存在的非均匀状态。（2）等温过程。对于与周围环境交换热量而温度不变的封闭系统，系统状态的自发变化总是朝着能量减少的方向进行，当自由能达到最小时，系统达到平衡状态。（3）冷却过程。使粒子热运动减弱，系统能量下降，得到晶体结构。模拟退火算法可以求解不同的非线性问题，对不可微分甚至不连续的函数进行优化，能以较大的概率求得全局最优解，该算法还具有较强的鲁棒性、全局收敛性、隐含并行性及广泛的适应性，并且能处理不同类型的优化设计变量（离散的、连续的、混合的），不需要任何的辅助信息，对目标函数和约束函数也没有任何要求［2］。

2 最短行程车辆调度路径的求解

首先根据企业内部铁路线及线上站点所在位置等信息，将铁路线及站点转化为图拓扑结构，然后利用图的最短路径算法求得每2个站点之间的最短距离，最后根据每2个站点之间的距离，利用模拟退火算法求最短行程路径。模拟退火算法的求解流程如图1所示。

图1 模拟退火算法求解流程图

算法实现步骤如下：

（1）控制参数设置。设置控制参数：降温速率q、初始温度T0、结束温度Tend和链长L。

（2）初始解。对问题的解空间进行编码，对于有n个站点的最短路程的调度路径，可以用1～n的一个排列表示，问题的解空间是n的全排列，随机生成n的一个排列作为初始解。

（3）变换生成新解。随机选择当前解中的2个站点进行交换，产生新的解。

（4）Metropolis准则。如果当前解S1的路程为f（S1），新解S2的路程为f（S2），路径差df＝f（S1）－f（S2），则 Metropolis准则为：

（5）降温。利用降温速率q降温，令T＝qT，若T小于结束温度，则停止。

3 仿真结果与分析

以某企业铁路线上的14个站点为例计算最短行程路径。每2个站点之间的最短距离如表1所示。

表1 每2站点之间的最短距离 单位：km

以降火速率q＝0．9、初始温度T0＝1 000K、结束温度Tend＝0．001K、链长L＝200次为参数，以表1中数据为输入数据，模拟退火算法得到的从V1去往全部站点并回到起始位置V1的最短路程是28km，最短路径是V1→V8→V13→V7→V6→V5→V12→V4→V14→V3→V2→V10→V9→V11→V1。模拟退火算法的进化过程如图2所示。

图2 模拟退火算法进化过程

4 结语

本文针对企业的铁路站车辆调度最短行程的路径优化问题，提出了模拟退火算法的求解过程，并用仿真实例验证了算法的正确性。

［1］李香平，张红阳．模拟退火算法原理及改进［J］．软件导刊，2008（4）

［2］汪灵枝，周优军．一种有效的全局优化算法——模拟退火算法［J］．柳州师专学报，2005（2）