铁路编组站动态配流的约束传播和多点构建性搜索的混合算法

为了提高动态配流模型的通用性和稳定性,基于约束程序累积调度和字典序多目标优化,以作业之间实施逻辑和优先级关系、班计划和列车编组计划要求、资源容量限制等为约束,按照配流成功的出发列车优先级总和最大、车辆平均中停时最小和资源利用率最高3个目标的优先级,建立适应于不同解体方式的动态配流字典序多目标累积调度的3层模型.为提高算法效率,设计了约束传播和多点构建性搜索混合的带初始解迭代算法,每层先通过约束传播算法化简模型,再通过带约束传播的多点构建性搜索算法快速求解,以决策出优化的作业排程和配流方案.实验表明,模型扩展性更强、更稳定、更符合现场实际;算法效率高,能够满足现场对计划编制和调整的实施性需求.     

文物碎块虚拟拼接中的表面特征优化

为了有效地度量空间曲面相似性,针对噪声敏感、部分匹配的受损文物碎块模型,提出一种基于空间曲面特征优化的匹配算法.首先计算模型表面点体积积分不变量形成匹配约束簇,提取匹配约束簇特征,并结合曲面凹凸互补性得到初始匹配簇对;然后定义3类空间几何一致性约束,并采用最大独立集方法对非正确匹配对进行消除,求解粗匹配最优化问题;最后在粗匹配实验基础上,采用不变特征迭代最近点进行精确对齐.实验结果表明,该算法能较好地实现高噪声影响下存在部分匹配关系的受损文物虚拟拼接.     

基于几何约束及0-1规划的视频帧间线段特征匹配算法

针对线段因遮挡、断裂以及端点提取不准确等原因造成的线段特征匹配困难问题,特别是现有匹配算法在匹配过程中出现"多配多"时直接采取"最相似匹配"而导致丢失大量真实匹配的问题,提出了一种基于多重几何约束及0-1规划的线段特征匹配算法。首先,基于校正后视频帧间线段特征的空间相邻性计算线段匹配的初始候选集;然后,基于极线约束、单应矩阵模型约束以及点-线相邻性约束等多重几何约束,对候选集进行筛选从而剔除部分错误匹配;其次,将线段匹配问题建模为一个大规模0-1规划问题;最后,设计了一种基于分组策略的两阶段求解算法对该问题进行求解,从而实现线段特征的"一配一"精确匹配。实验结果表明,该算法与LS（Line Sigature）、LJL（Line-Junction-Line）方法相比,匹配正确率接近,但匹配线段数量分别提高了60%和11%。所提算法可以实现视频帧间的线段特征匹配,为基于线特征的视觉SLAM（Simultaneously Localization and Mapping）奠定基础。     

基于改进SURF算法的双目视觉测量系统研究

针对双目立体测量中所使用的图像匹配算法精度不高的问题,提出了一种基于SURF算法的改进图像匹配算法并运用到双目立体测量系统中。首先运用SURF算法检测和描述图像对特征点、特征向量;其次采用双向特征向量匹配策略对匹配点集进行初始过滤;最后采用PROSAC算法根据极线约束几何模型对初始过滤后的匹配点集进行二次筛选,得到最终的优质匹配集合。实验表明,改进的SURF算法具有更高的匹配准确性和较好的算法实时性,运用改进SURF匹配算法的双目测量系统可实现更准确的定位测距。     

面向正常性的飞机排班优化算法

针对航班正常性问题,在飞机排班问题基础上,引入正常性约束,建立面向正常性的飞机排班模型,提出一种两阶段启发式算法进行求解.构建符合正常性要求的候选航班链集合,将排班问题转化为候选链对航班计划的集合覆盖问题.通过0-1整数规划求解集合覆盖问题,得到满足正常性约束的最小飞机数量排班方案.松弛正常性约束减小飞机使用数量,满足飞机数量约束.通过迭代搜索寻求正常性与飞机数量平衡的最优排班方案.实验结果表明,该方法可以有效提升航班计划的正常性期望.     

铁路编组站配流与调机运用的协调决策优化

运用数学优化方法,研究列车配流与调机运用的协调决策问题。建立了以欠轴列车数最少为目标的协调优化模型,并采用改进遗传算法求解。根据列车解体和编组顺序的特点,利用解体序号矩阵,采用自然数编码,并针对问题的特殊性应用联赛选择规则进行选择,且进行有限制的个体变异操作,减少了遗传算法本身随机性带来的影响,使变异后的种群能向高适应度方向进化。以某编组站为例进行模拟计算,结果表明该算法能够在较短时间内收敛至满意解。     

基于硬时间窗的技术站解编方案综合协调优化

针对现有制定的解编方案无法有效地满足铁路技术站阶段计划配流工作,基于牵引质量和换长的不同硬时间窗满轴约束,并综合考虑车流接续和编组去向约束,以总车流量、满轴出发列车最多为目标,建立了技术站多目标动态配流模型。为实现解编方案综合协调优化,依据解体和编组顺序调整规则,并通过定义可解集合和改进蚁群算法的状态转移规律及信息素更新策略,设计了一种基于蚁群算法的辅助决策支持系统。算例表明该辅助决策支持系统可以缩小配流问题规模,帮助决策者选择满意的解编配流方案,同时可以考虑解编顺序的改变对配流结果带来的影响,做到解体照顾编组,从而为实现铁路技术站调度系统的综合协调优化提供理论支持。     

含各向异性尺度形变数据集匹配问题的Lie群方法

通过分析含各向异性尺度形变的数据集匹配问题, 将尺度约束引入模型, 再结合迭代最近点(Iterative closest point, ICP)方法的一般过程, 将含各向异性尺度形变的数据集匹配问题描述为Lie群约束优化问题. 通过Lie群的局部参数化和局部线性化方法, 将带尺度上下界约束的Lie群约束优化问题转化为一系列的二次规划问题, 最终形成了一个完整的匹配迭代算. 该方法不仅具有传统ICP方法的快速准确的特点, 而且还能够处理存在大尺度形变的数据集匹配问题. 由于对尺度参数进行约束, 因此比传统方法有更好的鲁棒性. 最后, 为确保匹配的全局性, 给出了一套初始变换的选择方案.     

几何约束有向图的规划分解研究

在基于有向图表达的几何约束系统中,几何约束的匹配方向、分布状态以及有向图中强连通分量的规模直接影响到整个约束系统的求解;如何对几何约束系统进行合理规划,得到正确有效的求解序列,是目前约束分解研究的重要内容。该文提出了一个规划分解算法,它针对欠约束几何系统的特点,能够优化约束的初始匹配方向,对于约束匹配过程中生成的强连通子图,通过调整约束匹配方向,自适应地改善约束分布,从而减小强连通子图的规模,以求得到几何约束系统正确而高效的求解序列。同时,基于规划分解算法,完成了约束的奇异性分析,提供了面向分解的奇异性分析算法。     

一种基于多粒度语言偏好矩阵的多属性群决策方法

针对决策专家以多粒度语言偏好矩阵形式给出偏好信息的多属性群决策问题,提出一种基于二元语义一致化的多属性群决策方法.首先,构建一个基本语言偏好集作为多粒度语言一致化的参考集合;然后,采用基于二元语义的一致化处理方法将不同粒度的语言偏好信息均统一转化为相同粒度的二元语义形式,再通过二元语义的相关集结算子,对各决策专家给出的偏好信息进行集结并进行方案优选,得到满意结果;最后,通过算例说明了该方法的有效性.     

基于TPr/T_系统的编组站配流研究

通过考虑分析编组站作业流程,根据Petri网理论,将Pr/T_系统扩展为基于时延性的TPr/T_系统,在此基础上,逐步建立编组站TPr/T_系统模型。在模型中,以列车（车列）为元组,解决配流对资源的约束;通过谓词容量限制,解决配流在空间上的约束;通过变迁限制,解决配流对时间的约束。系统以满轴、尽量不晚点为优化目标,根据反向推理思想设计算法,以求得较为合理的配流方案。最后,通过实例,验证提出理论的合理性。     

Approaches to modeling train scheduling problems as job-shop problems with blocking constraints

The problem of scheduling a set of trains traveling through a given railway network consisting of single tracks, sidings and stations is considered. For every train a fixed route and travel times, an earliest departure time at the origin and a desired arrival time at the destination are given. A feasible schedule has to be determined which minimizes total tardiness of all trains at their destinations. This train scheduling problem is modeled as a job-shop scheduling problem with blocking constraints, where jobs represent trains and machines constitute tracks or track sections. Four MIP formulations without time-indexed variables are developed based on two different transformation approaches of parallel tracks and two different types of decision variables leading to job-shop scheduling problems with or without routing flexibility. A computational study is made on hard instances with up to 20 jobs and 11 machines to compare the MIP models in terms of total tardiness values, formulation size and computation time.     

A dispatching method for automated lifting vehicles in automated port container terminals

In automated container terminals, containers are transported from the marshalling yard to a ship and vice versa by automated vehicles. The automated vehicle type studied in this paper is an automated lifting vehicle (ALV) that is capable of lifting a container from the ground by itself. This study discusses how to dispatch ALVs by utilizing information about pickup and delivery locations and time in future delivery tasks. A mixed-integer programming model is provided for assigning optimal delivery tasks to ALVs. A procedure for converting buffer constraints into time window constraints and a heuristic algorithm for overcoming the excessive computational time required for solving the mathematical model are suggested. Numerical experiments are reported to compare the objective values and computational times by a heuristic algorithm with those by an optimizing method and to analyze the effects of dual cycle operation, number of ALVs, and buffer capacity on the performance of ALVs.     

A feasible timetable generator simulation modelling framework for train scheduling problem

An important problem in management of railway systems is the train scheduling/timetabling problem. This is the problem of determining a timetable for a set of trains that do not violate track capacities and satisfy some operational constraints. In this study, a feasible timetable generator framework for stochastic simulation modelling is developed. The objective is to obtain a feasible train timetable for all trains in the system. The feasible train timetable includes train arrival and departure times at all visited stations and calculated average train travel time. Although this study focuses on train scheduling/timetabling problem, the developed simulation framework can also be used for train rescheduling/dispatching problem if this framework can be fed by real time data. The developed simulation model includes stochastic events, and can easily cope with the disturbances that occur in the railway system.     

具有极大时间约束的轨道交通系统的周期分析

运用极大–加代数方法研究具有极大时间约束的轨道交通系统的周期运行规律.分别建立具有两个车站的双回路城际轨道交通系统和具有n个车站的单回路城市轨道交通系统的极大–加线性模型.对于前者,运用系统状态矩阵的周期性,证明各个车站第k次与第(k+2)次的发车时间间隔相同;对于后者,运用状态变量的线性替换,证明在任何初始状态下,系统经过一次循环便可进入周期稳态运行,即列车连续两次到达同一车站的时间间隔相同.周期时间分析有利于轨道交通系统列车时刻表的编排和周期运行方案的设计.为验证本文结果的实用性和有效性,给出周期时间分析在列车调度和线路规划中的应用例子.     

Decentralized control of heavy-haul trains with input constraints and communication delays

The heavy-haul trains consist of a large number of locomotives and wagons which usually cover a very long range of train tracks with different slopes and curvatures. As a consequence, the control design for the heavy-haul trains has posed a significant challenge due to the modeling complexity and the complicated traveling conditions, under which the problems of communication delays and input constraints naturally arise. In this paper, a novel decentralized control design is proposed for the heavy-haul trains by explicitly addressing the issues of input constraints and time-varying communication delays. Specifically, the complicated longitudinal dynamical model of the heavy-haul trains is first converted into a double integrator form by introducing a set of state and input transformations. Then, a decentralized cooperative control is proposed to regulate the speeds of individual train units (locomotives and wagons) to the desired profile with the objective of maintaining the minimum in-train force for safety consideration. It is rigorously proved that the closed-loop system is uniformly asymptotically cooperative stable under the least communication conditions among individual train units. Extensive simulations are conducted to validate the performance of the proposed new design.     

网约拼车出行的乘客车辆匹配及路径优化

城市道路拥堵严重及共享理念的盛行带来了拼车出行的兴起。出行线路相似的乘客共乘一辆车,可提高座位利用率、节省费用、缓解交通压力。以带时间窗约束的无换乘多车辆静态拼车问题为研究背景,从车辆使用费、途中走行成本及到达时间窗惩罚成本3个方面建立乘客车辆匹配及路径优化的目标函数,以车辆容量、乘客出发及到达时间窗、路径无迂回、乘客车辆匹配无重叠等限制构建模型约束条件,采用演化策略算法求解问题,根据模型特征设计编码解码规则,解码结果可同时获得车辆乘客匹配关系和走行路径,采用交叉变异操作更新迭代个体种群,进而求得最优解。运用MATLAB求解算例验证了模型可行性及算法有效性,结果表明算法能快速响应静态拼车问题,在较短时间即可给出乘客车辆的先后匹配关系及车辆走行路径,拼车方案相比独自出行能节省更多成本。     

有色冶炼企业专用铁路运输智能调度系统研究

针对有色冶炼企业铁路运输的特点,设计了有色冶炼企业铁路运输智能调度系统,并对系统实现中的两个关键问题——调度优化和调度模拟进行了深入讨论。提出了基于混合策略的优化调度方法,把企业铁路运输调度优化问题分解成列车分组优化、列车解编优化、进路优化以及取送车优化四个子问题,并采用不同方法分别进行优化,以期得到全局满意解,文中着重论述了取送车排序的优化问题。从调度监控的需要出发,给出了企业铁路站场动静态实体信息描述方法,构建了站场静态网络模型,并定义了调车机车的状态矩阵和轨道状态矩阵,实现了调度计划模拟。文章所提方法在南方某有色冶炼企业的铁路运输调度中得到应用,验证了方法的可行性。     

基于换乘导向的大型客运枢纽高铁列车接续优化

针对高速铁路成网条件下的客运枢纽高铁列车接续优化问题,分析了枢纽内的旅客换乘过程,提出了中长途客流的换乘满意度概念;以平均换乘满意度和枢纽车站列车到发均衡性为优化目标,以大站合理发车时间、合理终到时间、车站作业间隔时间、旅客换乘时间、车站到发线能力等为约束条件,建立了基于换乘协同的大型客运枢纽高速列车接续优化模型。设计了改进染色体编码方式和选择策略的遗传算法对算例进行了求解。改进后的遗传算法同基本遗传算法、基本模拟退火算法相比,目标函数中所求的平均换乘满意度分别增加了5.10%、2.93%,枢纽车站列车到发均衡性分别提高了0.27%、2.31%,算例结果验证了改进遗传算法的有效性和稳定性,表明所提方法可以有效地提高大型枢纽高铁列车的接续质量。