城市轨道交通线网检测车路径优化

胡政汉

（华东交通大学 软件学院，南昌 330013）

通过运行大型检测车辆，如轨道检查车、钢轨探伤车等，采集轨面数据进行病害分析是目前实现轨道检测的主要手段[1-2]。然而，目前手工制定的轨检车作业路径主要依靠专家的经验和知识。人工编排的大型检测车辆路径方案无论是里程还是时间均衡性都存在优化空间。如何兼顾一个编排周期内大型检测车辆的总行驶里程和线网上各条线路的时间均衡性自动编制出更优的大型检测车辆路径是目前的研究难点。

地铁轨道检测车辆路径优化问题(urban track inspection vehicle routing problem，UTIVRP)本质上属于弧路径优化问题(arc routing problem，ARP)的分支，与目前被广泛关注的能力受限的弧路径问题(capacitated arc routing problem，CARP)[3]较为类似。经典的CARP是定义在无向图上的路径优化问题，每个弧都有非负的花费和需求，车辆要对有非负需求的弧进行服务，且每辆车提供的服务总量不得超过车辆的能力(能力约束)。目标是寻找最低成本且起始于某一特定车库的路径。CARP 理论已被应用于多个领域，如城市垃圾回收[4-5]、洒水车路径规划[6]、邮件包裹运送[7]和冬季道路除雪[8]等。小规模的CARP 可以通过精确求解的算法(比如分支定界法)求得最优解[8]。启发式算法虽不能确保求解结果一定是全局最优，但可以在较短的时间内得到一个满意的近似解[9-10]，如遗传算法[11]、蚁群算法[12]等。目前关于CARP 的研究大部分是单目标优化，但是实际问题中除了最小化总路由成本以外，还有很多其他因素需要考虑，如最小化最长行程长度、最小化运用车辆数等。文献[13]最早提出了多目标CARP 模型。文献[14]针对同时降低总行驶成本和最长行程的CARP 问题，利用构造性启发式算法改造非支配排序的遗传算法进行求解。文献[15]研究了周期性能力受限的路径问题(periodic capacitated arc routing problem，PCARP)，将CARP 的服务时间扩展到一段时期内(称为规划周期)，用来解决服务任务具有多周期特点的弧路径问题。但是，根据实际路网和生产需要，UTIVRP 需要另外满足检测完整性和作业时长约束。因此，UTIVRP 可视作CARP 的变体，也是NP-hard问题。

目前，CARP 方面的相关探索更多集中在道路网方面[16]，鲜有与城市轨道交通线网的相关研究。本文针对城市轨道交通线网的特点，提出双层染色体编码方式，设计文化基因算法进行求解，探索城市轨道交通检测车路径方案，并通过算例对比北京地铁线网检测车路径的在用方案，对本文所建模型与设计算法进行验证。

1 地铁大型检测车辆路径优化模型

1.1 问题描述

地铁轨道检测车作业过程如下：编排周期伊始，大型检测车辆从城市轨道交通线网的固定车库出发开始作业。由于地铁线网白天承担客运任务，因此检测车只能在夜间规定的时间内执行检测作业(如02:00 am-04:00 am)。在规定时间结束前，检测车需要停放在车辆段中。不同线路有不同检测次数的要求，检测车辆在完成线网上各条线路规定次数的检测后需返回到固定车库。轨道检测数据分析和管理一般以整条线为单位，这要求大型检测车辆应尽可能在一天之内完成一个线别的检测，保证一个线别上检测数据的完整性。与道路网情况不同，大型检测车辆在作业过程中若要从某条线路转到另一条线路必须借助联络线。一个编排周期内大型检测车辆的行驶成本包括消耗的柴油、检测人员的人工成本和大型检测车辆的损耗等，即与编排周期内的总行驶里程成正比。因此本文以行驶里程来量化大型检测车辆的行驶成本，总行驶里程主要包括检测里程和调车里程，其中检测线路的里程是大型检测车辆所必须走行的，不存在优化空间。由此可见，大型检测车辆的总行驶里程取决于调车里程。同一线路相邻两次检测之间的时间间隔应尽可能保持一致，也就是大型检测车辆路径优化需要兼顾总调车里程和时间均衡性。

1.2 模型假设

本文将基于两个基本假设对UTIVRP 进行研究：大型检测车辆以恒定的速度运行；大型检测车辆作业过程中在联络线上的时间忽略不计。

1.3 变量与符号定义

模型中涉及的符号定义如下。

V：城市轨道交通线网中的节点集合；

A：城市轨道交通线网中的有向弧集合；

B：车库节点集合，B⊆V；

Cs i,j：弧(i，j)在被第s次检测时所在的天数；

D：完工天数，即轨检车的实际走行天数；

DP：给定的检测周期；

DW：检测车的纯工作天数；

depot：轨检车整条路径的起终点；

F：车辆每天可经过的最多弧的数量；

Ki,j：弧(i，j)的规定检测次数；

li,j：弧(i，j)的长度；

r：线路编号；

ti,j：轨检车在弧(i，j)上的走行时间；

W：检测车夜间作业时长限制；

1.4 目标函数

由于轨检车的任务Ki,j是确定的，所以轨检车的检测里程是定值。轨检车的最短走行里程Z1由空走调车里程所决定。

检测间隔平均偏差Z2，表示需要多次检测的线路实际检测间隔与理想检测间隔差值的平均值。偏差越小说明时间均衡性越好，反之越差。

检测间隔最大偏差Z3，表示需要多次检测的线路实际检测间隔与理想检测间隔差值的最大值。偏差越小说明时间均衡性越好，反之越差。

1.5 约束条件

各线路的检测次数要达到工务部门的要求：

2 文化基因算法

2.1 算法流程

文化基因算法(memetic algorithm，MA)是元启发式算法的一种，该算法在遗传算法(genetic algorithm，GA)的框架下融合了局部搜索和全局搜索，在车辆路径优化问题中有着广泛的应用。该算法的具体操作过程如图1 所示。首先，随机初始化种群。结合轮盘赌与精英个体选择法确定父代个体，通过交叉变异获得子代。然后，判断生成的解是否可行，若可行，则计算其适应度函数，并利用Metropolis 准则筛选子代；否则，重复选择、交叉和变异过程。当迭代满足终止条件时，终止计算，输出最佳解。

图1 算法流程Figure 1 Algorithm flow chart

2.2 染色体编码方式

染色体的编码是元启发式算法的使用前提，良好的编码方式不仅能够减少搜索空间，而且能够有效提高搜索效率。染色体编码方式如下：第一层为线路序列，第二层为弧序列。线序列染色体上的一个基因代表了轨检车对某条线路的一次检测，用整数表示。弧的整数序列表示规划周期内轨检车的一条检测路径。表1 表示既定的检测任务，图2 展示了一个简化的地铁线网。在城市轨道交通线网中，各线路之间设有联络线，车辆经由联络线驶入另一线路，若待检线路与车辆当前停留的线路间不存在联络线，则车辆无法直接驶入目标线路，而需要暂时经由其他线路寻找合适的走行路径。图3 给出了简化地铁线网(共计5 条线路)的编码示例，其中相邻两条线路之间的路径由Floyd-Warshall 算法确定。

表1 简化地铁线网的一组线路编码数据Table 1 Line codes for simplified urban rail transit network

图2 简化地铁线网Figure 2 A simplified urban rail transit network

图3 双层染色体编码示意Figure 3 Double-layer chromosome coding method

根据最远里程约束和车库约束将染色体解码为每一天的轨检车行驶路径，同时可以得到轨检车按照该检测路径完成规划周期内所有检测任务的总天数DW，如图4 所示。

图4 染色体解码示意Figure 4 Chromosome decoding method

2.3 选择操作与进化算子

综合考虑轮盘赌和精英个体选择两种方式的优缺点，本文将这2 种选择方式进行结合：将父代优良个体按照一定比例直接放入子代，同时从父代的所有个体中以轮盘赌的方式选择剩余名额的个体进入子代。

MA 所采用的交叉算子如下：随机选取P1 染色体中的基因段复制到C1 的相同位置处，再将P2 染色体中与之相同的基因段删除，之后将剩余的基因按照从左到右的顺序复制到C1 中，C2 的染色体操作方式相同，具体过程见图5。

图5 交叉算子示意Figure 5 Example of crossover operator

本文所采用的线染色体变异算子包括挪位和换位，如图6 所示。挪位是选取线序列中任意连续的q个基因(q取小于线序列长度的随机整数)插入某位基因之前(后)；换位是选取线序列中任意p对基因(p是不大于线序列长度的随机整数)交换位置。

图6 线染色体变异Figure 6 Line-chromosome mutation

Metropolis 筛选准则为

3 案例分析

3.1 案例介绍

以北京市地铁线网为例对轨检车的运行路径展开研究，其地铁线网如图7 所示。实验环境配置为2.60GHz CPU、8.00 GB 内存。

图7 北京地铁公司线网示意Figure 7 Network managed by Beijing Metro company

图8 参数 Z 1min 和 Z 1max 的迭代过程示意Figure 8 Parameters Z 1min and Z 1max iterative process

图9 参数 Z 2min 和 Z 3min 的迭代过程示意Figure 9 Parameters Z 2min and Z 3min iterative process

3.2 参数设置与运算结果

综上，文化基因算法在处理单目标问题时，收敛值及解的质量均能令人满意。为进一步评价文化基因算法的有效性，在计算Z时，对文化基因算法中的各输入参数选取不同的值，参数设置及计算结果见表2，迭代过程见图10。

表2 参数设置Table 2 Parameter settings

图10 求解Z 的迭代过程示意Figure 10 Schematic diagram of the Z iterative process

计算结果的标准差s=0.0048，变异系数cv=3.299%，分布较为集中。本节从相同参数多次运算和多种参数独立运算的两种角度对算法进行评估，结果表明，针对UTIVRP 所设计的MA 算法有较高的精度。

表3 列举出曲线5 对应的轨检车路径编制方案与目前在用方案的对比结果。

由表3 可以看出，人工安排的轨检车空走调车里程为603.530 km，完成所有检测任务共需要43 d，检测间隔平均偏差日为10.38 d，检测间隔最大偏差日为14.99 d。而经过本文优化所得到的空走调车里程为308.514 km，完成所有检测任务的纯工作时间为29 d，检测间隔平均偏差日为1.00 d，检测间隔最大偏差日为1.00 d。调车里程降低约48.88%，检测间隔平均偏差率降低约90.37%，最大偏差率降低约93.33%。

本文所规划的轨检车作业路线如图11 所示，其中车辆走行而不开启检测模式的路径被标记为黄色；在两站点之间的检测路径被标记为绿色。

图11 检测车作业路线Figure 11 Routes of the track inspection vehicle

4 结论

针对城市轨道交通线网的特点，建立了复杂约束条件下的多目标UTIVRP 模型，提出了双层染色体结构及编码方式，设计出MA 算法。将模型应用于北京市轨道交通线网，并将求解结果与目前北京市地铁工务部门在用的轨检车检测路径进行对比。结果表明：相比于手工方案，优化后的检测路径降低了48.88%的空走调车里程，减少了14 d 的作业天数；极大地提高了各线路的检测效果，优化后的车辆调度计划的检测间隔平均偏差率降低约90.37%，最大偏差率降低约93.33%。

UTIVRP 仍存在进一步改进的空间。本文只考虑了单辆城市轨道检测车的路径优化过程。下一步将针对在城市轨道交通线网上同时优化两辆及以上大型检测车辆的路径展开讨论，为未来城市轨道检测车路径规划的应用奠定基础。