一种复杂山区铁路线站协同优化方法

摘要

本发明公开了一种复杂山区铁路线站协同优化方法，包括以下步骤：S1：划分单元格；S2：建立综合地理信息模型，添加单元格的地理信息属性；S3：初始化各单元格的线站协同搜索相关属性；S4：线站协同优化扫描，更新各单元格的属性，得到扫描距离图；S5：依据扫描距离图生成线路路径方案群；S6：生成线-站方案群。本发明将图形学中的距离变换法应用到线站协同搜索算法中，创建了线站协同搜索双邻域模板，并充分考虑线站协同搜索过程中的静态约束和随线-站方案的生成实时计算的耦合伴生型约束，将对复杂约束的处理分治于线站协同搜索的前、中、后三个阶段，能自动搜索出满足复杂约束条件的线站协同优化线路方案，提高铁路设计的自动化程度。

说明书

技术邻域

本发明涉及铁路设计方法，具体涉及一种复杂山区铁路线站协同优化方法。

背景技术

当代铁路由普速向高速发展，铁路线路设计标准大幅提升；建设区域由平原向山区转变， 面临的环境日趋复杂，且线路技术标准的提高又将减弱线路及车站对环境的适应能力。这些 变化使铁路空间线位和车站的协调布置难题变得尤为突出。

目前，国内外关于铁路智能选线已开展了大量研究，总体看来，可以分为针对空间线位 的“线”的优化和针对车站选址的“点”的优化两个方面。

针对“线”的优化：Chew等采用三次样条曲线代表线路，并用牛顿下降法搜索线路方案； 詹振炎提出了梯度投影法求解优化目标函数导数的方法，寻找下降方向；易思蓉、韩春华提 出了基于栅格数据最优路径分析及知识推理自动生成线路平面的方法；DeSmith提出了一种 坡度和曲线约束方法；Cheng和Lee提出了邻域启发法；旷达智能选线系统基于模糊数学理 论进行线路搜索；近年来，马里兰大学的Paul,Schonfeld教授团队建立了基于遗传算法的线 路智能搜索方法。

针对“点”的优化：王齐荣应用专家系统技术对车站分布标准和分布方法(概略分布、 车站选址、分布方案选优)的智能辅助决策开展了研究，并建立了原型系统；Laporte以沿线 所有车站吸引范围的最大化为目标，提出了最长路径算法实现车站位置的优化布设，Samanta 先后采用蚁群算法和蚁群与遗传算法结合的复合算法对铁路车站的智能选择进行了持续深入 研究，优化效果得到逐步提升；廖勇基于三角模糊数并结合TOPSIS法建立了一种新的铁路 客运站选址方案评价方法，SimonP.Blainey基于GIS评价得出最优站址方案，取得良好效果。

综上可知，现有的方法主要是考虑静态约束条件下单独针对空间线位的“线”的优化， 或是针对车站选址的“点”的优化，是一种有限目标下的子优化，即：车站的选址优化与线 路的优化是彼此分离、孤立和片面。而忽视了线路和车站之间的耦合关系和动态特征，尚未 实现“点线结合”的协同优化，常常无法给出线路、车站综合协调的优化解。因此，设计人 员迫切需要借助智能优化技术破解上述难题，实现线位与站址的协同优化。

发明内容

针对复杂环境下铁路线位与站址协同优化技术的不足，本发明提出了一种复杂山区铁路 线站协同优化方法。该方法将图形学中的距离变换法应用到线站协同搜索算法中，创建了线 站协同搜索双邻域模板，并充分考虑线站协同搜索过程中的静态约束和随线-站方案的生成实 时计算的耦合伴生型约束，将对复杂约束的处理分治于线站协同搜索的前、中、后三个阶段， 能自动搜索出满足复杂约束条件的线站协同优化线路方案，提高铁路设计的自动化程度。

本发明的技术方案为：

一种复杂山区铁路线站协同优化方法，包括以下步骤：

S₁：划分单元格

基于距离变换的思想，将选线范围划分为包含M×N个正方形单元格的规则格网，格网 内各单元格的宽度为w，其取值范围为30m-90m；线路起点和线路终点分别位于该格网左上 角和右下角的单元格处。

S₂：建立综合地理信息模型

采集线路搜索所需要的各类信息，包括描述地形、地物、地价和工程单价信息，将其作 为各单元格的地理环境属性。

S₃：初始化各单元格的线站协同搜索相关属性；

定义单元格的线站协同搜索相关属性及其赋初值情况如下：

(1)分别以起点和终点为目标点时，各单元格距最近站址的连接距离DIST，初值赋为0。

(2)各单元格到目标点的连接代价COST，包括各单元格到线路起点的连接代价和到线 路终点的连接代价：起点到起点的连接代价初值赋为0，终点到终点的连接代价初值赋为0， 其他所有单元格到起点和终点的连接代价初值均赋为无穷大；

(3)分别以起点和终点为目标点时，使得单元格的COST最小的连接方案下，单元格距 相应的邻域单元格的横向偏移量XV，初值赋为0；

(4)分别以起点和终点为目标点时，使得单元格的COST最小的连接方案下，单元格距 相应的邻域单元格的纵向偏移量YV，初值赋为0；

(5)表征各单元格是否为站址单元格的类型属性，记为TYPE：若单元格为非站址单元 格，则TYPE赋值为False；若单元格为站址单元格，则TYPE赋值为True；所有单元格的 TYPE初值均赋为False，即所有单元格的初始类型均为非站址单元格；

(6)表征各单元格能否通行铁路线路的属性，记为PROPERTY：若单元格不能通行铁路 线路，则PROPERTY＝0；若单元格可以通行铁路线路，则PROPERTY＝1；所有单元格 PROPERTY的初始值均为1；

S₄：线站协同优化扫描

S_4-1：依据“预处理”约束要求，剔除不符合约束条件的单元格。

S_4-2：对剩下的单元格，基于线站协同搜索双邻域模板，即站址搜索邻域模板和线路搜索 邻域模板，依次进行四次扫描：

第一次扫描和第二次扫描均以线路起点为目标点；第一次扫描以线路起点为起始点，从 上至下、从左至右进行逐行扫描，直到扫描到线路终点；第二次扫描从线路终点沿第一次扫 描的原路返回扫描至线路起点；第一次扫描和第二次扫描完成后生成以线路起点为目标点扫 描的距离图DT_S；

第三次扫描和第四次扫描均以线路终点为目标点，第三次扫描以线路终点为起始点，从 下至上、从右至左进行逐行扫描，直到扫描到线路起点；第四次扫描从线路起点沿第三次扫 描的原路返回扫描至线路终点，第三次扫描和第四次扫描完成后生成以线路终点为目标点扫 描的距离图DT_E。

每一次扫描的具体步骤如下：

S_4-2-1：首先基于站址搜索邻域模板进行扫描，判断当前单元格与所涉及的邻域单元格之 间是否满足站址搜索过程中的“中处理”约束要求，如均不满足，则跳至步骤S_4-2-6进行线路 邻域模板扫描；如存在满足约束要求的站址邻域单元格，则进行如下步骤：

S_4-2-2：依次计算当前单元格与满足约束要求的每一个邻域单元格的连接代价，加上相应 的邻域单元距目标点的连接代价，得到当前单元格经相应的邻域单元格至目标点的连接代价 COST’，若该连接代价COST’小于当前单元格的COST，则更新当前单元格的COST，令当前 单元格的COST＝COST’，找出使得当前单元格的COST(当前单元格距目标点的连接代价) 最小的连接方案；

站址段连接代价C_Sta具体计算方法如下：

$C_{Sta}=C_{Sta}^1+C_{Sta}^2=\left\{\right[\underset{j=1}{\overset{m}{\Sigma }}(H_{sta}-H_j)\times F_j+\underset{i=1}{\overset{n}{\Sigma }}(H_i-H_{sta})\times C_i]+\underset{k=1}{\overset{m+n}{\Sigma }}{J}_k\}\times w^2$

其中，为站址土方工程代价；为站址用地代价；H_sta为站址计算高程，为方便计 算，取H_sta＝0.5×(H_p,q+H_r,c)，H_p,q和H_r,c分别是当前单元格G_p,q和邻域单元格G_r,c的地面高 程；H_j、F_j分别为站址区域内第j个填方单元格的高程和填方单价；H_i、C_i分别为站址区 域内第i个挖方单元格的高程和挖方代价；J_k为第k个单元格的用地代价；w为单元格宽度； m、n分别为站址范围内的填方和挖方的单元格个数。

S_4-2-3：计算使得当前单元格的COST最小的连接方案中，当前单元格距相应的邻域单元 格的横向偏移量XV和纵向偏移量YV，并更新当前单元格的相应属性；用于记录使得当前单 元格的COST最小的连接方案中，相应的邻域单元格的位置；

S_4-2-4：更新当前单元格为站址单元格，即将TYPE赋值为True；

S_4-2-5：更新当前单元格距最近站址的连接距离为0，即将当前单元格的DIST赋值为0； 返回步骤S_4-2-1进行下一单元格的扫描，直至所有单元格扫描完成；

S_4-2-6：对当前单元格基于线路搜索邻域模板进行扫描，判断当前单元格与所涉及的邻域 单元格之间是否满足线路搜索过程中的“中处理”约束要求，如均不满足，则结束当前单元 格搜索，并将当前单元格属性赋为不可行单元格，不更新其到目标点的连接代价COST，其 值仍为无穷大；返回步骤S_4-2-1进行下一单元格的扫描；如存在满足约束要求的连接方案，则 进行如下步骤：

S_4-2-7：依次计算当前单元格与满足约束要求的每一个邻域单元格之间的连接代价；加上 相应的邻域单元距目标点的连接代价，得到当前单元格经相应的邻域单元格至目标点的连接 代价COST’；若该连接代价COST’小于当前单元格的COST，则更新当前单元格的COST， 令当前单元格的COST＝COST’；找出使得当前单元格的COST最小的连接方案；

线路段连接代价包括路基地段土方工程费用、桥梁工程费用、隧道工程费用、征地费用、 线形费用，具体计算方法在专利申请CN2014108415900“一种复杂山区铁路线路走向自动生 成方法”中有详细的介绍，故在此申请中不赘述。

S_4-2-8：计算使得当前单元格的COST最小的连接方案中，当前单元格距相应的邻域单元 格的横向偏移量XV和纵向偏移量YV，并更新当前单元格的相应属性；用于记录使得当前单 元格的COST最小的连接方案中，相应的邻域单元格的位置

S_4-2-9：更新当前单元格距最近站址的连接距离DIST为：使得当前单元格的COST最小 的连接方案中，与其相连的邻域单元格的DIST值与线路搜索邻域模板的搜索半径R的和； 返回步骤S_4-2-1进行下一单元格的扫描，直至所有单元格扫描完成；

S₅：依据扫描距离图生成线路路径方案群，具体包括以下步骤：

S_5-1：叠加以线路起点为目标点扫描的距离图DT_S和以线路终点为目标点扫描的距离图 DT_E；

S_5-2：遍历叠加距离图中的所有单元格，选出距线路起点和线路终点的连接代价均不为无 穷大的单元格作为双向连接单元格；

S_5-3：选取任一双向连接单元格，并以双向连接单元格为中心，根据单元格内存储的连接 信息属性XV和YV，分别向线路的起点和终点扩展，生成线路路径方案；

S_5-4：遍历所有双向连接单元格，并根据步骤S_5-3所述的方法生成起点到终点的线路路径 方案群；

S_5-5：依据“后处理”约束要求对所S_5-4中生成的线路路径方案进行逐一判断，调整不符 合“后处理”约束要求的线路路径方案；

S₆：生成线-站方案群：

S_6-1：选取步骤S_5-5中得到的任意一条线路路径方案，遍历该路径方案上的所有单元格， 找出其站址单元格，并由站址单元格和其邻域单元格形成站址连接段；

S_6-2：判断各个站址连接段间是否满足最大、最小站间距要求，如满足则选为线-站方案， 如不满足则剔除此方案；

S_6-3：遍历步骤S₅生成的所有线路路径方案，选出满足要求的方案，生成线-站方案群。

所述步骤S_4-2中的线路搜索邻域模板用于遍历与当前单元格距离为R的所有单元格，所 遍历的单元格均分布在一个以当前单元格为中心的半圆弧上，称当前单元格的线路邻域单元 格；半径R可根据设计人员的经验设置；

线路搜索邻域模板分为线路搜索邻域正向模板和线路搜索邻域反向模板；记所遍历的单 元格相对于当前单元格的行列偏移值为△R，△C，则线路搜索邻域正向模板中△R，△C的计 算方法为：

$\left(\begin{array}{c}\alpha =w/R\\ n=\pi /\alpha \\ \Delta R=-[R\times \sin (\alpha \times i)],i=1,...n\\ \Delta C=[C\times cos(\alpha \times i)],i=1,...n\end{array}\right)---\left(1\right)$

线路搜索邻域反向模板中△R，△C的计算方法为：

$\left(\begin{array}{c}\alpha =w/R\\ n=\pi /\alpha \\ \Delta R=[R\times \sin (\alpha \times i)],i=1,...n\\ \Delta C=-[R\times cos(\alpha \times i)],i=1,...n\end{array}\right)---\left(2\right)$

所述步骤S_4-2中的站址搜索邻域模板用于遍历与当前单元格距离为R₁的所有单元格，所 遍历的单元格均分布在一个以当前单元格为中心的半圆弧上，称当前单元格的站址邻域单元 格，半径R₁取值为站坪长度L_sta；

站址搜索邻域模板分为站址搜索邻域正向模板和站址搜索邻域反向模板；记所遍历的单 元格相对于当前单元格的行列偏移值为△R，△C，则站址搜索邻域正向模板中△R，△C的计 算方法为：

$\left(\begin{array}{c}\alpha =w/R_1\\ n=\pi /\alpha \\ \Delta R=-[R_1\times \sin (\alpha \times i)],i=1,...n\\ \Delta C=[R_1\times cos(\alpha \times i)],i=1,...n\end{array}\right)---\left(3\right)$

线路搜索邻域反向模板中△R，△C的计算方法为：

$\left(\begin{array}{c}\alpha =w/R_1\\ n=\pi /\alpha \\ \Delta R=[R_1\times \sin (\alpha \times i)],i=1,...n\\ \Delta C=-[R_1\times cos(\alpha \times i)],i=1,...n\end{array}\right)---\left(4\right)$

所述第一次扫描和第四次扫描均基于线路搜索邻域正向模板和站址搜索邻域正向模板进 行扫描；所述第二次扫描和第三次扫描基于线路搜索邻域反向模板和站址搜索邻域反向模板 进行扫描。

在复杂山区环境下存在大量的约束，有约束状态明晰固定，不随线站方案的变换而变化 的静态稳定型约束；更有约束初始状体不明晰，需随线站方案的生成实时计算的耦合伴生型 约束，线站协同智能搜索中这类约束的状态会影响线站方案的生成，反之生成的线站方案又 将影响约束状态。为解决复杂约束下的线站协同搜索问题，本发明将复杂约束的处理分治于 线站协同优化扫描的前、中、后三个阶段，分为：预处理、中处理、后处理。

第一阶段：预处理

预处理是指在距离变换前预先遍历选线范围内的所有单元格，检查绕避区域、平面和高 程可达性约束，筛选出不满足约束的单元格，以减少距离变换的计算量，即所述“预处理” 约束包括：

1)绕避区域约束

根据S2中的地理环境属性，设置需绕避的区域(如自然保护区、名胜古迹等)，将需绕 避的区域所在单元格的PROPERTY赋值为0，PROPERTY值为0的单元格不满足绕避区域约 束要求；

2)平面可达性约束

记线路起点为S，其所在的单元格行列号及高程分别为i_S,j_S,H_S；线路终点为E，其所 在的单元格行列号及高程分别为i_E,j_E,H_E，任意单元格C_i,j(第i行，j列)到线路起点和线路 终点的距离分别为L_S和L_E；从平面可达性考虑，单元格到线路起点和线路终点的距离的和 与线路起点和线路终点之间的距离(起点到终点的直线距离)L_SE的比值不得超过最大容许展 线系数γ_max，即必须满足以下条件：

$L_S=\sqrt{{(i-i_S)}^2+{(j-j_S)}^2}\times w,L_E=\sqrt{{(i-i_E)}^2+{(j-j_E)}^2}\times w---\left(5\right)$

(L_S+L_E)/L_SE<γ_max

3)高程可达性约束

单元格到线路起点和线路终点的距离须保证在使用最大限制坡度i_max和最大容许展线系 数γ_max条件下能克服线路起点和线路终点之间的高差，即满足：

(L_S+L_E)×γ_max×i_max>|H_E-H_S|(6)

另外，单元格C_i,j的高程取值范围不能为空，即需满足：

H_S,max＝H_S+i_max×L_S×γ_max，H_S,min＝H_S-i_max×L_S×γ_max

H_E,max＝H_E+i_max×L_E×γ_max，H_E,min＝H_S-i_max×L_E×γ_max(7)

U＝[H_S，min,H_S，max]∩[H_E，min,H_E，max]

其中，H_S,max、H_S,min分别为从线路起点开始，使用最大限制坡度i_max和最大容许展线系 数γ_max到单元格C_i,j的最大、最小高程值；H_E,max、H_E,min分别为从线路终点开始，使用最大 限制坡度i_max和最大容许展线系数γ_max到单元格C_i,j的最大、最小高程值。

第二阶段：中处理

在线站协同搜索过程中，其核心过程是计算当前被扫描的单元格G_p,q和其邻域内任意单 元格G_r,c之间的广义距离。该过程实质上是在当前单元格的站址邻域和线路邻域内进行试算， 在每一次试算中，都需要满足各类静态和耦合伴生出的约束条件：

1)在站址邻域内进行试算主要考虑平面和纵面约束，即所述站址搜索过程中的“中处理” 约束要求包括平面和纵面约束：

1.1)平面约束包括：最大最小站间距约束、绕避约束、转角约束、自交叉约束：

1.1.1)最大最小站间距约束

车站设置应满足最大、最小站间距要求，即当前单元格距最近站址的连接距离应在最大、 最小站间距范围内，满足：

L_min<DIST<L_max(8)

其中，L_min为最小站间距，L_max为最大站间距，DIST为当前单元格距最近站址的连接距 离，与其相连的邻域单元格的DIST值与站址搜索邻域模板的搜索半径R₁的和；

1.1.2)绕避约束

根据单元格属性PROPERTY进行约束判断：判断当前单元格与相应的邻域单元格的连接 线的范围内是否有PROPERTY值为0的单元格，如有则剔除该连接方案；

1.1.3)转角约束

若当前单元格G_p,q和其邻域单元格G_r,c相连，而G_r,c与G_m,n相连，则G_m,n至G_r,c的连接线与 G_r,c至G_p,q的连接线之间的转角α_k应小于最大容许转角α_max，即满足：

α_k<α_max(9)

1.1.4)自交叉约束

在路径的生成过程中，可能会出现自交叉现象。因此，在单元格连接的时候需进行自交 叉检测。自交叉约束的检测方法为遍历G_p,q到目标点的所有路径，判断这些路径是否与G_p,q→ G_r,c相交，如果相交则存在自交叉，不满足自交叉约束要求。

“中处理”中不符合自交叉约束或转角约束则直接排除掉该线路连接方式，换其他连接 方式。

1.2)纵面约束包括：车站与桥、隧不重叠约束、站坪最大限制坡度约束：

1.2.1)车站与桥、隧不重叠约束

车站不宜设置在桥梁、隧道上，因此站坪范围内，即以站址连接段(由当前单元格G_p,q与 其邻域单元格G_r,c形成的连接段)中点所处单元格为中心的矩形L_sta×w₁内所包含单元格的高 程应满足：

H_sta-H_xq<H_r<H_sta+H_xs(10)

其中，H_r为站坪范围内任意单元格的高程；H_sta为站坪的计算高程，为方便计算，取 H_sta＝0.5×(H_p,q+H_r,c)，H_p,q和H_r,c分别是单元格G_p,q和G_r,c的地面高程；w为设置单元格宽 度；p，q分别为单元格G_p,q的行列号；r，c分别为单元格G_r,c的行列号；H_xq为线桥分界 填高；H_xs为线隧分界挖深；L_sta为站坪长度；w₁为站坪宽度。

1.2.2)站坪最大限制坡度约束

站坪坡度应满足站坪最大限制坡度要求i'_max，即被扫描的单元格G_p,q和其邻域单元格G_r,c之间的坡度应小于i'_max，即满足如下公式：

$\frac{|H_{r,c}-H_{p,q}|}{w\sqrt{{(p-r)}^2+{(q-c)}^2}}<i_{\max }^{\prime }---\left(11\right)$

其中，i'_max为站坪最大限制坡度。

2)在线路邻域内进行试算需考虑平面、纵面、桥梁、隧道的约束条件，即所述线路搜索 过程中的“中处理”约束要求包括平面、纵面、桥梁、隧道约束：

2.1)平面约束包括：转角约束、自交叉约束和绕避约束，检测处理方法与在站址邻域内 进行试算的处理方法相同，此处不再赘述；

2.2)纵面约束为线路最大限制坡度约束，即：

线路坡度应满足线路最大限制坡度要求i_max，即被扫描的单元格G_p,q和其邻域内任意单元 格G_r,c之间的坡度应小于i_max，即满足如下公式：

$\frac{|H_{r,c}-H_{p,q}|}{w\sqrt{{(p-r)}^2+{(q-c)}^2}}<i_{max}---\left(12\right)$

其中，H_p,q和H_r,c分别是单元格G_p,q和G_r,c的地面高程；w为设置单元格宽度；p，q分 别为单元格G_p,q的行列号；r，c分别为单元格G_r,c的行列号，i_max为线路最大限制坡度。

当两单元格满足约束可以相连时，其连接线即为局部铁路设计线，设计线上任意一点高 程，均可由两单元格高程推算得到。

2.3)桥梁约束包括最大容许桥高约束H_Qmax，即设计高程与地面高程差应小于等于最大 容许桥高：

H_s-H_d≤H_Qmax(13)

其中，H_s为设计线高程，H_d为地面高程，H_Qmax为最大容许桥高。

2.4)隧道约束包括最大容许隧长约束，即隧道长应在最大容许隧长范围内。在专利申请 CN2014108415900“一种复杂山区铁路线路走向自动生成方法”中有介绍判断设置隧道的计算 方法，即当挖深超过线隧分界挖深时，需要设置隧道，从而可以得到隧道长。

第三阶段：后处理

由于DT_S和DT_E是分别以起终点为目标点进行距离变换的两个独立距离图。扫描过程中， 虽然可保证任意单元格C_i,j到S和E均满足各类约束条件，但将两路径连接为一个贯通路径 时仍可能出现过大转角和自交叉现象。因此，在扫描结束后，需对不满足约束的方案进行调 整。

即所述步骤S_5‐5中的“后处理”约束要求包括转角约束和自交叉约束；对于不符合后处 理约束要求的线路路径方案的调整方法为：

1)自交叉：当线路路径在任意单元格C_r,c内出现自交叉时，尝试以C_r,c为衔接点，形成 S→C_r,c→E的路径，如该路径满足所有约束，则保留S→C_r,c→E的路径，否则剔除该线路路 径方案；

2)过大转角：从C_i,j开始，遍历C_i,j至线路起点的线路路径P_S和至线路终点的线路路P_E上的所有单元格，尝试寻找一对单元格C_r,c，C_m,n，使得S→C_r,c→C_m,n→E的路径满足所有约 束，如找到则保留S→C_r,c→C_m,n→E路径，否则剔除该线路路径方案。

有益效果：

1)本发明针对复杂环境下铁路线位与站址协同优化技术的不足，提出了一种复杂山区铁 路线站协同优化方法，基于该方法能自动搜索出线站协同优化线路方案，提高铁路设计的自 动化程度。

2)在复杂山区环境下存在大量的约束，本发明将对复杂约束的处理分治于线站协同搜索 的前、中、后三个阶段，分为：预处理、中处理、后处理，解决了线站协同搜索过程中对复 杂约束的处理问题。

3)该方法自动化程度高、实用性强、运行效率高，具有很高的推广应用价值。

附图说明

图1为本发明流程图；

图2为线站协同优化扫描流程图；

图3为线路搜索邻域和站址搜索邻域正、反向模板扫描范围示意图；

图4为约束条件示意图；

图5为自交叉和过大转角处理示意图；

图6为生成线路路径方案和线-站方案群流程图；

图7为线-站方案三维展示图。

具体实施方式

以下结合附图对本发明进行进一步具体说明。

本发明采用的距离变换法(DistanceTransformation，DT)是图像学中的一种常用变换， 它执行的是将一幅二值图像转换为一幅灰度图像(距离图)，在这幅灰度图像中，每个像素的 灰度值是该像素到其最近背景点(目标点)的最小距离。本发明将距离变换中的“距离”概 念扩展到包含线路方案工程费、运营费、环境影响代价构成的综合代价，即广义距离。基于 距离变换的思想，本发明将选线范围划分为M×N的规则格网，整个格网被视为一张图像；将 线路端点设为距离变换中的目标点；用单元格之间的广义距离来代替距离变换中的“距离”； 则生成的距离图中DT(p)值表示点p到线路端点的最小代价，对应的路径即为到线路端点的 最优路径。距离变换算法中距离图的更新过程就是按照一定顺序选取研究区域的单元格，遍 历其邻域模板，从模板中找到最优连接单元格。

本实施例以安顺至六盘水双线铁路为例对本发明的技术方案做进一步说明。如图1所示， 本发明所涉及的复杂山区环境下铁路线站协同设计与优化方法包括以下步骤：

S₁：划分单元格

基于距离变换的思想，将选线范围为103km×40km的矩形区域划分为包含1145×445个正 方形单元格的规则格网，单元格的宽度为90m；线路起点和线路终点分别位于该格网左上角 和右下角的单元格处。

S₂：建立综合地理信息模型

采集线路搜索所需要的各类信息，包括描述地形、地物、地价和工程单价信息，将其作 为各单元格的地理环境属性，建立综合地理信息模型图。

S₃：初始化各单元格的线、站协同搜索相关属性；包括：各单元格距最近站址的连接距 离(DIST)、各单元格到目标点的连接代价(COST)、单元格距相应的邻域单元格的横向偏 移量(XV)和纵向偏移量(YV)、表征各单元格是否为站址单元格的类型属性、以及表征 各单元格能否通行铁路线路的属性。

S₄：线站协同优化扫描

如图2进行线站协同优化扫描，具体步骤如下：

S_4-1：依据预处理约束要求，剔除不符合约束条件的单元格。

S_4-2：对剩下的单元格，基于线站协同搜索双邻域模板，即站址搜索邻域模板和线路搜索 邻域模板，依次进行四次扫描：

第一次扫描和第二次扫描均以线路起点为目标点；第一次扫描以线路起点为起始点，从 上至下、从左至右进行逐行扫描，直到扫描到线路终点；第二次扫描从线路终点沿第一次扫 描的原路返回扫描至线路起点；第一次扫描和第二次扫描完成后生成以线路起点为目标点扫 描的距离图DT_S；

第三次扫描和第四次扫描均以线路终点为目标点，第三次扫描以线路终点为起始点，从 下至上、从右至左进行逐行扫描，直到扫描到线路起点；第四次扫描从线路起点沿第三次扫 描的原路返回扫描至线路终点，第三次扫描和第四次扫描完成后生成以线路终点为目标点扫 描的距离图DT_E。

首先进行站址邻域模板扫描，如找到满足要求的站址邻域单元格，则依次计算当前单元 格与满足要求的站址邻域单元格之间的连接代价，选出距目标点连接代价最小的连接方案， 更新单元格属性信息；如没找到满足要求的站址邻域单元格，则进行线路邻域模板扫描，如 找到满足要求的线路邻域单元格，则依次计算当前单元格与满足要求的线路邻域单元格之间 的连接代价，选出距目标点连接代价最小的连接方案，更新单元格属性信息；如站址邻域模 板扫描和线路邻域模板扫描均未找到满足要求的邻域单元格，则跳过该单元格进行对下一单 元格的搜索；直至所有单元格扫描完成；

S₅：依据扫描距离图生成线路路径方案群，如图6所示，具体包括以下步骤：

S_5-1：叠加以线路起点为目标点扫描的距离图DT_S和以线路终点为目标点扫描的距离图 DT_E；

S_5-2：遍历叠加距离图中的所有单元格，选出距线路起点和线路终点的连接代价均不为无 穷大的单元格作为双向连接单元格；

S_5-3：选取任一双向连接单元格，并以双向连接单元格为中心，根据单元格内存储的连接 信息属性XV和YV，分别向线路的起点和终点扩展，生成线路路径方案；

S_5-4：遍历所有双向连接单元格，并根据步骤S_5-3所述的方法生成起点到终点的线路路径 方案群；

S_5-5：依据后处理约束要求对所S_5-4中生成的线路路径方案进行逐一判断，调整不符合后 处理约束要求的线路路径方案。

S₆：生成线-站方案群；

S_6-1：选取步骤S_5-5中得到的任意一条线路路径方案，遍历该路径方案上的所有单元格， 找出其站址单元格，并由站址单元格和其邻域单元格形成站址连接段；

S_6-2：判断各个站址连接段间是否满足最大、最小站间距要求，如满足则选为线-站方案， 如不满足则剔除此方案；

S_6-3：遍历步骤S₅生成的所有线路路径方案，选出满足要求的方案，生成线-站方案群。

如图3所示，所述步骤S_4-2中的线路搜索邻域模板用于遍历与当前单元格距离为R的所 有单元格，所遍历的单元格均分布在一个以当前单元格为中心的半圆弧上，称当前单元格的 线路邻域单元格，半径R可根据设计人员的经验设置，本案例选用2km半径。线路搜索邻域 模板分为线路搜索邻域正向模板和线路搜索邻域反向模板；

所述步骤S_4-2中的站址搜索邻域模板用于遍历与当前单元格距离为R₁的所有单元格，所 遍历的单元格均分布在一个以当前单元格为中心的半圆弧上，称当前单元格的站址邻域单元 格，半径R₁取值为站坪长度L_sta(本案例取2km)；站址搜索邻域模板也分为站址搜索邻域正 向模板和站址搜索邻域反向模板。

所述第一次扫描和第四次扫描均基于线路搜索邻域正向模板和站址搜索邻域正向模板进 行扫描；所述第二次扫描和第三次扫描基于线路搜索邻域反向模板和站址搜索邻域反向模板 进行扫描；

本实施例为解决复杂约束下的线站协同搜索问题，将复杂约束的处理分治于线站协同优 化扫描的前、中、后三个阶段，分为：预处理、中处理、后处理，如图4所示。

第一阶段：预处理

预处理是指在距离变换前预先遍历选线范围内的所有单元格，检查绕避区域、平面和高 程可达性约束，筛选出不满足约束的单元格，以减少距离变换的计算量，即所述“预处理” 约束包括：

1)绕避区域约束

根据S2中的地理环境属性，设置需绕避的区域，将需绕避的区域所在单元格的 PROPERTY赋值为0，PROPERTY值为0的单元格不满足绕避区域约束要求；

2)平面可达性约束

记线路起点为S，其所在的单元格行列号及高程分别为i_S,j_S,H_S；线路终点为E，其所 在的单元格行列号及高程分别为i_E,j_E,H_E，任意单元格C_i,j(第i行，j列)到线路起点和线路 终点的距离分别为L_S和L_E；从平面可达性考虑，单元格到线路起点和线路终点的距离的和 与线路起点和线路终点之间的距离(起点到终点的直线距离)L_SE的比值不得超过最大容许展 线系数γ_max(本案例取1.5)。

3)高程可达性约束

单元格到线路起点和线路终点的距离须保证在使用最大限制坡度i_max(本案例取28‰) 和最大容许展线系数γ_max条件下能克服线路起点和线路终点之间的高差；另外，单元格C_i,j的 高程取值范围不能为空。

第二阶段：中处理

在当前单元格的站址邻域和线路邻域内进行试算，在每一次试算中，都需要满足各类静 态和耦合伴生出的约束条件：

1)在站址邻域内进行试算主要考虑平面和纵面约束，即所述站址搜索过程中的“中处理” 约束要求包括平面和纵面约束：

1.1)平面约束包括：最大最小站间距约束、绕避约束、转角约束、自交叉约束：

1.1.1)最大最小站间距约束

车站设置应满足最大、最小站间距要求，即当前单元格距最近站址的连接距离应在最大、 最小站间距范围内；本案例中最小站间距L_min取为12km，最大站间距L_max取为30km；

1.1.2)绕避约束

根据单元格属性PROPERTY进行约束判断：判断当前单元格与相应的邻域单元格的连接 线的范围内是否有PROPERTY值为0的单元格，如有则剔除该连接方案；

1.1.3)转角约束

若当前单元格G_p,q和其邻域单元格G_r,c相连，而G_r,c与G_m,n相连，则G_m,n至G_r,c的连接线与 G_r,c至G_p,q的连接线之间的转角α_k应小于最大容许转角α_max(本案例取60°)；

1.1.4)自交叉约束

自交叉约束的检测方法为遍历G_p,q到目标点的所有路径，判断这些路径是否与G_p,q→G_r,c相交，如果相交则存在自交叉，不满足自交叉约束要求。

“中处理”中不符合自交叉约束或转角约束则直接排除掉该线路连接方式，换其他连接 方式。

1.2)纵面约束包括：车站与桥、隧不重叠约束、站坪最大限制坡度约束：

1.2.1)车站与桥、隧不重叠约束

车站不宜设置在桥梁、隧道上，因此站坪范围内，即以站址连接段(由当前单元格G_p,q与 其邻域单元格G_r,c形成的连接段)中点所处单元格为中心的矩形L_sta×w₁(本案例为2km×0.4km) 内所包含单元格的高程应满足：

H_sta-H_xq<H_r<H_sta+H_xs

其中，H_r为站坪范围内任意单元格的高程；H_sta为站坪的计算高程，为方便计算，取 H_sta＝0.5×(H_p,q+H_r,c)，H_p,q和H_r,c分别是单元格G_p,q和G_r,c的地面高程；w为设置单元格宽 度；p，q分别为单元格G_p,q的行列号；r，c分别为单元格G_r,c的行列号；H_xq为线桥分界 填高；H_xs为线隧分界挖深；L_sta为站坪长度；w₁为站坪宽度。

1.2.2)站坪最大限制坡度约束

站坪坡度应满足站坪最大限制坡度要求i'_max(本案例取6‰)，即被扫描的单元格G_p,q和 其邻域单元格G_r,c之间的坡度应小于i'_max。

2)在线路邻域内进行试算需考虑平面、纵面、桥梁、隧道的约束条件，即所述线路搜索 过程中的“中处理”约束要求包括平面、纵面、桥梁、隧道约束：

2.1)平面约束包括：转角约束、自交叉约束和绕避约束，检测处理方法与在站址邻域内 进行试算的处理方法相同，此处不再赘述；

2.2)纵面约束主要为线路最大限制坡度约束，即：

线路坡度应满足线路最大限制坡度要求i_max(本案例取28‰)，即被扫描的单元格G_p,q和 其邻域内任意单元格G_r,c之间的坡度应小于i_max。

当两单元格满足约束可以相连时，其连接线即为局部铁路设计线，设计线上任意一点高 程，均可由两单元格高程推算得到。

2.3)桥梁约束包括最大容许桥高约束H_Qmax(本案例取130m)，即设计高程H_s与地面高 程H_d差应小于等于最大容许桥高H_Qmax。

2.4)隧道约束包括最大容许隧长约束，即隧道长应在最大容许隧长范围内(本案例取8km)。

第三阶段：后处理

所述步骤S_5‐5中的“后处理”约束要求包括转角约束和自交叉约束；如图5所示，对于 不符合后处理约束要求的线路路径方案的调整方法为：

1)自交叉：当线路路径在任意单元格C_r,c内出现自交叉时，尝试以C_r,c为衔接点，形成 S→C_r,c→E的路径，如该路径满足所有约束，则保留S→C_r,c→E的路径，否则剔除该线路路 径方案；

2)过大转角：从C_i,j开始，遍历C_i,j至线路起点的线路路径P_S和至线路终点的线路路P_E上的所有单元格，尝试寻找一对单元格C_r,c，C_m,n，使得S→C_r,c→C_m,n→E的路径满足所有约 束，如找到则保留S→C_r,c→C_m,n→E路径，否则剔除该线路路径方案。

本次选取的安顺至六盘水双线铁路线站协同优化选线案例在惠普Z600工作站上进行(4 核2.14GCPU，4G内存，1T硬盘)，优化总耗时147分钟，生成线-站方案83个。选取自动 生成方案中5条具有典型代表性的线-站方案进行拟合，并将其导入中南大学开发的GERail 软件中，实现方案的三维展示，展示效果如图7所示。

所描述的实施例是本发明的一部分实施例，而不是全部的实例，不能理解为对本发明的 限制。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动的前提下所获得 的所有其它实施方式都属于本发明的保护范围。