铁路勘测外业的送接车辆调度优化问题

曾俊豪，邓连波

(1.中铁四院集团南宁勘察设计院有限公司，广西 南宁 530003；2.中南大学 交通运输工程学院，湖南 长沙 410075)

铁路工程勘测外业需要根据勘测工作量配置负责送接勘测人员(包含勘测设备)的车辆数量，各车辆从外业驻地出发，完成外业勘测区域内的多个勘测点之间的人员派送和接回任务，并最终返回驻地。随着铁路建设工程精细化管理要求的提出[1]，铁路勘测设计工作时间紧，任务重，要求以较短的勘测时间提交满足设计要求的勘测数据。在勘测过程中，铁路勘测外业的送接车辆调度安排，决定了各个勘测点的开始作业时间，在一定程度上决定了勘测任务的衔接紧密性，进而影响到整个勘测任务的进度。该问题的研究，对提高勘测作业效率具有积极意义。

当前关于铁路勘测外业送接问题的研究极少，单玉民[2]认为，铁路勘测任务需在线路走向方案提出后汇总各专业勘测工作量确定勘测计划，进而对勘测用车、勘测里程及偏距(地点)、勘测作业时间、送接勘测作业人员的顺序、车辆行驶路径等作出安排。目前，铁路勘测用车的调度方式通常为均等或按照远近顺序分配各车勘测点位，司机按照勘测人员完成任务、提出接回需求的先后次序作出响应，完成勘测人员送、接。该方式无法从系统最优角度实现人员送、接，产生较多等待时间。

铁路勘测外业的送接车辆调度安排为车辆路径问题(vehicle routing problem, VRP)中的一个特例。其中，勘测人员是送接车辆的服务对象，决策者关注勘测任务的完成情况，给各个车辆安排其所负责的勘测点送−接任务，每一车辆的司机用最少行驶里程和等待时间完成任务。二者在双层决策系统中属于领导与被领导关系。决策者只能通过为各车辆分配勘测点来控制勘测进度；而司机通过选定行驶路线反馈给决策者。双方无法在双层决策系统中使用1个目标函数来表示2个相互冲突的目标，故通常用双层规划模型[3-5]研究此类问题，用上层模型表示决策者的任务分配，下层模型表示各车辆的路径优化问题。

铁路勘测外业的送−接车辆调度安排问题本质上是一个具有时间窗要求的特殊车辆路径问题。与一般车辆路径问题相比，其特殊性主要表现在勘测车辆需要为勘测点先后提供送、接两种服务，勘测点在送接之间的时间段进行勘测作业等方面。本文基于送−接车辆调度安排问题的特点，采用勘测送−接扩展网络描述问题特征，基于既有VRP问题研究成果[6-7]建立勘测外业的送−接车辆调度双层规划模型，并设计嵌套遗传算法进行求解，最后通过实例验证模型和算法的有效性，有效提高生产组织效率。

1 问题描述

铁路勘测日常出工具体流程为所有勘测人员根据勘测任务分成若干个勘测小组，为每一车辆分配勘测节点送−接任务，全体勘测人员乘坐一辆或多辆勘测车辆从项目部驻地出发，各勘测车辆在指定的勘测点之间派送和接回勘测人员，并最终返回驻地的过程。对于任一勘测车辆，须先将各勘测小组送到预定的勘测点，在任务完成后恰当的时机返回去将其接回，当日勘测工作量未完成时则前往下一个勘测点，如已完成则可返回驻地。

该问题有如下特点。

1) 每一勘测车辆的送−接路径，包含驻地和该车辆所承担送−接任务的勘测点，所配置的勘测车辆应能覆盖所有勘测点。

2) 各勘测车辆的送−接路径可视为均从驻地出发，并在完成所有送−接任务后返回驻地的一个有向、有序闭合路径。假定每一勘测点的派送和接回任务由同一辆勘测车辆完成，即各车辆的送−接路径间不存在交叉关系。

3) 在每一勘测车辆的送−接路径上，每一勘测点需要被勘测车辆经由两次，即派送人员至勘测点和从勘测点接回人员的送和接两个任务分时先后进行。两个任务之间的时间间隔不少于勘测点的作业时间。

以图1(a)所示的勘测送−接网络为例，由驻地和3个勘测点构成该网络的节点集合，图中所示路径为只有1辆车时的一个单车辆送−接调度方案。该单车辆调度方案由派送弧和接回弧两类弧段组成，是一个送−接任务网络上的有向、有序闭合路径，弧上数字为其先后次序标号。为简化单车辆送−接调度方案的表达，可将勘测网络中每一勘测点按照送−接任务分拆成送点和接点，转化为图1(b)所示的勘测送−接扩展网络。在勘测送−接扩展网络上，单车辆送−接方案可以描述为遍历所有节点，每个节点仅访问一次的一条有向闭合路径，且每一勘测点对应的送点和接点之间的时间间隔不少于该点的勘测作业时间。由于勘测送−接扩展网络上有向弧的次序可清晰表达，不必在弧段上再增加序号表示其先后关系。由此，单车辆的送−接调度，可归结为带送−接约束条件的车辆路径问题。该问题的优化目标可根据实际情况，设置为勘测人员的总等待时间最短，车辆行驶成本最小等。上述问题可拓展到多车辆情形。在多车模式下，可将其分解为送−接车辆的勘测点任务指派和各车辆送−接路径优化问题，两者可视为一个双层规划问题。即上层决策点是如何为各车指派勘测点使得工作量均衡分配且用时最短；下层决策点是对各车辆按单车模式下带送−接约束条件的车辆路径问题，分别求解最佳送接路径，并反馈给上层决策以调整勘测点的指派方案。

图1 单车送−接扩展网络示意Figure 1 Send-pick survey network for a single car

2 数学模型

2.1 模型假设

为简化问题的建模优化，进一步提出如下假设。

1) 送−接车辆数量已经给定，各送−接车辆无能力限制，均能容纳所承担的勘测点的人员和设备运输装载要求；

2) 所有勘测点的勘测任务无优先等级要求和先后顺序要求；

3) 勘测网络上任意两节点间均可相互联通，节点间车辆行驶时间、每个勘测点的作业时间均已知。

2.2 模型建立

令勘测网络的节点集合为N(其中驻地编号为0)，i,j为 勘测点，i,j≠0 。E为派送车辆集合，e∈E为一辆派送车辆，|E|为车辆数。在勘测网络中，Ne为车辆e负 责的勘测点集合，满足wi为勘测网络节点i∈N的 作业时间；sij为勘测网络节点i到j的车辆行 驶 里 程；分别为 车 辆e运行到勘测网络节点i∈N派送和接回的时刻。决策变量xei，若车辆e负 责勘测点i的派送和接回任务则取1，否则取0。

对于车辆e的扩展送−接网络，有节点和分 别表 示中接 回 和派 送节 点，为勘测网络N中节点i,j的 对应节点。决策变量xe˜i˜j，若车辆e从扩展送−接网络节点运行到节点则取1，否则取0。

根据前述分析，将该问题用双层规划模型进行表达。作为上层规划的勘测点任务指派模型(U)为

其中，式(1)为各车辆送−接持续时间最短和最均衡的目标函数，γ为所有送−接车辆的广义费用(见式11)的均衡性权重；式(2)表示任一物理勘测点只由一辆车负责派送和接回；式(3)表示各车辆至少负责1个勘测点。

下层规划为各车辆送−接路径优化问题，对各车辆的送−接调度方案相互独立求解。对车辆e，其车辆送−接路径优化模型(L)为

其中，式(4)表示车辆e勘测总等待时间最短，包括人等车和车等人两种情况；式(5)表示车辆固定成本加行驶成本最小；对于车辆e，式(6)、(7)表示扩展送−接网络中任一顶点都要被访问一次；式(8)、(9)保证从驻地出发的车辆必须返回驻地；式(10)表示接人时间不早于送人时间。 为便于多目标优化问题求解，采用线性加权组合法将式(4)和式(5)组合作为送接路径的广义费用。

其中，α为勘测地区单位时间内工资成本，采用α 作 为Z2e的权重系数。

由上层规划的勘测点任务指派模型(U)和下层规划的车辆送−接路径优化模型(L)构成送−接车辆调度优化问题的一对多双层规划模型。

3 嵌套遗传算法设计

下层规划(L)中的车辆送−接路径问题属于典型的组合优化问题，目前无多项式时间算法，在算法复杂性上为NP难题[8]，本文的双层规划模型难以用精确算法求解。20世纪90年代以来，遗传算法由于具有多点并行搜索、基于采样随机搜索和基于概率搜索等优良特性，在解决组合优化问题上显示出强大功能[9-10]。为求解本文双层规划模型，设计嵌套遗传算法，外层遗传算法求解上层规划，内层遗传算法求解下层规划，实现双层规划一体优化。

3.1 染色体设计

1) 外层遗传算法编码设计。根据上层规划模型(U)的特征，以二进制矩阵来表示决策变量，即车辆e负责勘测点i的送接任务则用1表示，否则用0表示。该编码方式形成的编码空间中的所有点与可行解空间中的所有点一一对应。考虑式(2)，同一染色体等位基因上具有成组关联的特征。假设模型中共有n辆车，m个勘测点，图2所示为二进制矩阵表示的染色体，1列为1个基因组，同一基因组中所有基因之和为1，确保模型解的可行性。在遗传操作中，为避免单基因变换对染色体的可行性造成破坏，以基因组为单位进行交叉和变异操作。

图2 二进制矩阵表示的染色体Figure 2 Chromosome of binary matrix

2) 内层遗传算法染色体设计。对任一车辆e，其负责送−接范围内的每一个勘测点都要访问两次，即送、接各一次。对应到送−接扩展网络上，下层规划染色体设计需要区分每一个勘测点的勘测接点、勘测送点两种扩展网络节点。本文提出勘测点i∈N及其扩展节点的编、解码方法，如表1所示。

表1 送-接扩展网络编、解码设计Table 1 Coding and decoding design of extended send-pick network

3.2 遗传算子设计

1) 外层遗传算子设计。

(1) 变异操作。外层遗传算子运算操作基于二进制矩阵表示的染色体，其中变异操作采用基因组反转变异，即以一定的概率pOm选 择一个染色体C1O。先随机选择一个变异组x，再随机选择基因组中异于原值为1的位置，调换二者基因，其余位置的基因不变，如图3所示。

图3 外层染色体成组反转变异Figure 3 Group inverting mutation of outer chromosome

(2) 交叉操作。交叉操作采用单基因位的成组交叉，确保染色体在交叉过程中的可行性，有效改进遗传编码，即以一定的概率选择两个染色体C1O和C2O，随机生成一个交叉点位x，则C和C2O交叉点位x之前的基因组不变，将包括x在内的之后的基因组相互交换，生成两个子代染色体和，如图4所示。

图4 外层染色体成组交叉Figure 4 Group crossover of outer chromosomes

(3) 评价。采用上层规划问题(U)的目标函数来评价各染色体CkO={cen|e=1,···,|E|,n=1,···,|N|}，k=1,···,popSize，染色体的适值函数为

其中，根据问题特征Z1>0。

2) 内层遗传算子设计。

(1) 交叉操作。内层遗传算法的编码方式决定了内层染色体的基因组成为送−接扩展网络的车辆送、接顺序，故其交叉操作是以一定的概率选择两个染色体和，对其采用部分一致交叉法(partial-mapped crossover, PMX)[10]，交叉过程如图5所示。

图5 部分一致交叉法示例Figure 5 Illustration of PMX

(2) 变异操作。内层遗传算法的变异操作是从父代以一定的概率随机选择一个染色体，随机生成2个变异位置x和y，交换这2个点的基因得到子代染色体，如图6所示。

图6 变异算子示例Figure 6 Illustration of mutation operator

(3) 评价。下层规划模型(L)通过计算送−接路径广义费评价各染色体|N|}，k=1,···,popSize ，染色体的适值函数如式(13)所示。

其中，M为较大的正整数，是对染色体所产生的解不满足约束条件而进行的惩罚；根据问题特征，Z4e＞0。

3.3 嵌套遗传算法处理过程

采用嵌套遗传算法求解本文双层规划模型。计算步骤如下。

步骤 0设定内、外层种群的大小分别为popSizeI和 p opSizeO，交叉率分别为pIc和pOc，变异率分别为和pOm，最大代数m ax GenI和m ax GenO，初始评价函数值min EvalI和min EvalO。

步骤 1外层算法开始，生成满足上层规划模型(U)约束条件的初始解的二进制染色体(编码)。

步骤 2根据染色体，计算适值函数(解码)，解码染色体后逐一将每辆车e∈E负责送−接的勘测点集传入内层算法作为输入。

1) 内层算法开始，随机生成当前车辆e下层规划模型(L)初始解的染色体(编码)。

3) 代数g en=gen+1，进行如下操作。

(1) 部分一致交叉(内层)。交叉生成的新染色体数用 cCntI表示，令 cCntI=0，生成 (0,1)区间内的随机数。选择满足rk＜pIc的 染色体，并对被选染色体进行配对，令 cCntI=cCntI+2，按图5所示方法进行交叉操作，得到的新染色体分别定义为

(2) 变异(内层)。令变异生成的染色体数mCntI=0。 生成 (0,1)区 间内的随机数选择满足的染色体，按图6所示方法进行变异，令 mCntI=mCntI+1，生成新的染色体

(3) 轮盘赌选择(内层)。按式(13)计算染色体的适值，按适值大小进行排序，用轮盘赌模型[11]选择适值较高的 p opSizeI数目的染色体作为子代染色体。

4) 若 gen＜max GenI，返回2)；否则循环结束，返回当前最佳送−接路径及其广义费用。

步骤 3代数g en=gen+1，进行如下操作。

1) 基因组交叉(外层)。交叉生成的新染色体数用 c CntO表 示，令 c CntO=0。 生成 (0,1)区间内的随机数。选择满足的染色体，并对被选染色体进行配对，令c CntO=cCntO+2，按图4所示方法进行单点位基因组交叉，得到的新染色体分别定义为

2) 基因组变异(外层)。令用来变异生成的染色体数 mCntO=0 。生成 (0,1)区 间内的随机数。选择满足的染色体CkO，按图3所示方法进行成组反转变异，令 m CntO=mCntO+1，生成新的染色体

3) 轮盘赌选择(外层)。按式(12)计算染色体的适值按适值大小进行排序，用轮盘赌模型选择适值较高的popSizeO数目的染色体作为子代染色体。

步骤 4若g en＜max GenO，返回步骤 2；否则循环结束，输出每辆车负责的勘测点及其最佳送−接路径。

4 实例计算

为验证本文模型和算法的有效性，以我国中南地区某新建高速铁路的现场勘测数据为例进行铁路勘测车辆调度优化。某日出工计划两辆勘测用车负责沿线位附近19个勘测点，详细数据如表2所示，其中驻地编号为0，其余按编号升序依次远离驻地。车辆行驶速度v=0.6 km/min，单位里程行驶费用f=0.8 元/km，车辆的固定使用费用F=150 元，勘测所在地区单位时间内工资成本α=0.5 元/min。

表2 勘测点数据Table 2 Coordinates of survey points

本文利用C#对提出的送−接车辆调度优化问题的嵌套遗传算法进行编程实现。外层遗传算法参数：迭代次数 max GenO= 4 000，种群规模 popSizeO=10，交叉率=0.6，变异率为pOm=0.2；内层遗传算法参数：迭代次数m ax GenI= 2 000，种群规模 p opSizeI=10，交叉率= 0.4, 变异率为=0.6。将基于本文双层规划模型与算法的优化结果与目前的响应式车辆送−接调度方法进行对比，两种方法对应的路径为如下。

1) 在拓展网络上的优化送−接路径。车辆1：0-19S-17S-8S-18S-17P-5S-7S-13S-5P-8P-13P-7P-18P-19P-0；车 辆2：0-15S-14S-12S-6S-1S-2S-11S-14P-16S-9S-4S-15P-11P-2P- 3S-6P-10S-10P-16P-9P-1P-3P-4P-12P-0。

2) 按传统的响应式思想编制的送−接路径。车辆1：0-1S-2S-3S-4S-5S-6S-7S-8S-5P-2P-7P-3P-6P-9P-1P-4P-8P-0；车辆2：0-10S-11S-12S-13S-14S-15S-16S-17S-18S-19S-10P-14P-11P-13P-15P-17P-16P-18P-12P-19P-0。

其中，S表示送，P表示接。响应式调度方法是根据勘测点数量，平分给两辆车，即车辆1负责前9个勘测点的送−接任务，车辆2负责后10个勘测点的送−接任务。经两种方法计算得到的指标对比如表3所示。

由表3可看出，调度优化算法的总广义费用相较于响应式调度减少18.0%。二者差距在于调度优化算法求解的双层规划模型中体现了对送−接调度方案的总广义费用的优化，故两辆车的各个指标都较均衡，任务分配更加合理，等待时间也远小于响应式调度方式。通过送、接次序的优化提高了勘测进度紧凑性，其中人等车的时间仅占总等待时间的20%，各指标都优于目前的响应式调度方法。

表3 优化算法结果与响应式调度结果比较Table 3 Comparison of results between optimization and responsive scheduling

调度优化算法求得的最优送−接方案调度方案，如图7所示。可见，各车在大部分勘测点接人时产生的等待时间较小，对从送−接车辆组织环节上加快勘测进度，提高勘测效率具有积极意义。

图7 优化方案勘测车辆调度运行图Figure 7 Survey vehicle dispatching diagram of optimal scheme

5 结论

本文基于铁路工程勘测中送−接车辆的调度问题，以多车指派问题和单车带作业时间窗和送−接约束VRP问题为切入点，建立双层规划模型将二者有机结合进行研究。该模型为NP难问题，针对该模型的特点提出了内外层嵌套的遗传算法用以求解该模型，专门设计了嵌套遗传算法的遗传算子。

求解实例表明，本文提出的模型与算法求解得到的广义勘测费用相较于响应式调度方式减少了18.0%，成本、里程和等待时间等指标更加均衡，车辆任务分配更加合理，可有效提高勘测效率和勘测进度的衔接程度。

本文所提出的模型与算法不仅为解决多车送−接的车辆路径问题提供了一种有效的工具和手段，也可为铁路工程勘测送−接车辆调度优化提供可行方法，在理论研究和实践应用上具有一定意义。