【作者】 夏明；

【导师】 周磊山；

【作者基本信息】 北京交通大学 ， 交通运输规划与管理， 2011， 博士

【摘要】 列车运行图编制问题涉及部门众多、决策空间庞大,一直是铁路运输组织理论方法的难点问题。目前,我国高速铁路系统得到了快速的发展,与既有线相比,其高标准的运输服务质量要求需要高速铁路运营管理部门能够随着旅客运输市场的不断变化,统筹考虑列车运行计划、动车交路计划和车站进路生成计划,快速形成科学、合理的一体化运输组织方案。高速铁路列车运行图编制要求已经超越了单元编图系统和编图个体的能力。以不断快速发展的计算机网络技术为基础发展而来的列车运行图网络协同编制模式,将为高速铁路列车运行图编制工作提出更高效的解决方案,它能够根据运输市场的频繁变动,快速的组建运行图编制动态联盟,经济、有效的制定高速铁路时空资源优化配置方案。不过,从目前国内外的研究进展和工作实践来看,高速铁路列车运行图网络化协同编制的研究还刚刚起步,其编制模式与协同工作机理、适应列车运行图网络协同编制的数学模型、同步编制的实时求解方法、基于网络的协同调整方法还很不成体系,应用系统的设计和实现等问题还需要大量的技术创新。鉴于此,本文根据当前高速铁路列车运行图编制的特点和要求,对高速铁路列车运行图网络化协同编制的相关理论和关键技术展开研究和探讨,以期得到对高速铁路列车运行图编制工作有益的研究成果。具体研究内容为：首先,在对高速铁路列车运行图网络协同编制的定义、内涵进行分析的基础上,提出了列车运行图网络协同编制的三维协同模型,从对象、时间和空间三个维度上,探讨了列车运行图网络协同编制的理论体系,指出了实现高速铁路列车运行图网络协同编制的关键要素。其次,针对网络协同环境下高速铁路列车运行图编制问题呈现的空间分布特征,在运用资源分配理论分析了列车运行计划、动车组交路计划和车站进路安排计划的问题属性的基础上,基于约束满足理论(CSP)构建了该问题的分布式约束满足模型,设计了同步回溯求解框架,制定了软约束网络协作调整策略。为了满足网络协同编制对问题求解效率的要求,根据问题特点,结合约束满足求解方法和分布并行计算技术,分别设计了三个子问题优化方法：(1)在列车运行计划问题求解研究中,本文利用协作网络计算资源,根据各分枝子问题无关性特点,设计了并行分支定界算法。利用析取图描述了列车运行过程,提出了基于弧一致性约束传播的区间占用冲突检测方法,给出了子任务生成策略,设计了基于拉格朗日算法的并行任务求解方法,研究了并行算法的实现机制和加速机制。(2)在动车交路计划编制问题求解研究中,本文根据问题的多阶段决策特性,提出了基于蚁群算法的求解思路。针对随着运行线数量的增加,解构造图的规模以及蚂蚁生成解的计算量均成指数增长的情况,设计了粗粒度并行蚁群算法,以列车运行图网络协同编制系统为计算环境,利用分布式并行计算技术,将蚁群的搜索任务放置在不同的计算机上并行执行,互相合作的完成整个计算任务。(3)在车站进路生成问题的求解的研究中,本文针对站场结构较为复杂的大型车站的进路生成问题,设计了一种并行回退算法,将原来十分集中的计算任务和较大的内存需求分配到参与并行计算的各台计算机上,有效缩短因发生回退而产生的额外搜索时间。在针对软约束的网络协作调整研究中,本文分析了高速铁路列车运行图网络协同编制人机交互操作过程,详细讨论了协作调整过程中的数据一致性维护和死锁现象,给出了导致死锁产生的并发对象冲突和并发逻辑冲突定义,并提出了运行图协同编制环境下并发冲突的检测方法,设计了自动疏解、双方协商和第三方仲裁的分层并发控制机制。最后,在系统实现和工程实践方面,阐述了基于.NET平台的高速铁路列车运行图网络协同编制原型系统框架结构,讨论了原型系统的基本功能设置、网络节点模块设计等问题。同时,基于某高速铁路列车运行图编制实际设计了编制任务,并将本文的研究成果在算例中进行应用,验证了方法的可行性。更多还原

【Abstract】 Train scheduling problem was research hotspot and difficult points of transportation organization theory, since it includes numerous branch and large decision space. At present, the high speed railway system was developed quickly.High speed railway has some special efficiency and quality requirements compared with common railways., which is not in the power of unit ts system and individual worker.With the development and mature of Internet and CSCW, networked collaborative train scheduling is becoming the trend of train scheduling pattern. According to transportation market fluctuation, NCTS could quickly organize train scheduling alliance which helps to set up time and space resources optimum allocation plan for high speed railway. Study of NCTS is still at a very early stage, the following issues needs deeply study:scheduling mode and collaborative work principals, mathematic model which adapted to NCTS, real time solving method, networked cooperative decision and adjustment method, and the design and realization of prototype system. According to characteristic and request of current high speed railway, this paper deeply studies the related theory and key technology of NCTS.Firstly, this paper put forward basic concept of NCTS. Based on analysis of definition and scheduling mode of NCTS, a three-dimention collaborative modal was put forward to discuss the framework structure of NCTS on object, time and space.Secondly, the property of timetable, rolling stock circulation and routing generation were analyzed based on resource allocation theory. In order to describe the spatial distribution features of NCTS under networked collaborative circumstance, a distribute constraint satisfaction modal was given based on CSP theory. And Synchronous Backtracking algorithm framework was put forward, meanwhile networked cooperative adjustment strategies was made. To meet the requirement of solving efficiency of NCTS, three sub-problem optimization method was proposed based on the combination of CSP method and distribute computing technology.In the study of train timetable problem solving, this paper designed a distribute branch and bound algorithm according that branch notes are independent, using collaborative networked computing resources. The train running process was described by disjunctive graph, and a section occupation conflict detection method based on arc consistency was proposed, sub task generation strategy and distribute task solving method based on lagrange algorithm. Implementing mechanisms and accelerating mechanisms of distribute algorithm were studied.In the study of rolling stock circulation problem solving, a solving thought based on ant colony algorithm was put forward according to its multistage decision property. This paper designed a coarse-grained distribute ant colony algorithm, since the scale of solution construction graph and the amount of computation increased exponentially. NCTS could be used as distribute computing circumstance, we put the search task on different computer respectively, using distribute computing technology, so the computers can finish the task collaborating with each other.In the study of routing generation problem solving, a distribute parallel backtracing algorithm was proposed to solve big station routing problem with complex structure, which distribute the concentrate task to several parallel computer. And this could decrease computing time because of backtracing.In the study of soft constraints networked cooperative adjustment, this paper analyzed the process of human machine interaction during networked cooperative train scheduling. The data consistency preservation and deadlock phenomenon were discussed in detail. Meanwhile, the detection method of concurrency conflict under the cooperative scheduling environment was proposed, and the stratified concurrency control automatic resolution, mutual negotiation and arbitration of party was put forward.Finally, on the aspect of system realization and engineering practice, the prototype system framework of NCTS based on.NET was described, and the basic function and network note module were discussed. Meanwhile, a scheduling task based on some real high speed railway line was designed, and the research result was put into practice to validate the validity and feasibility of the method.更多还原