用户名: 密码: 验证码:
铁路车站取送车系统优化理论与方法研究
详细信息    本馆镜像全文|  推荐本文 |  |   获取CNKI官网全文
摘要
取送调车是货运站和货物作业较多的技术站的一项重要工作,取送车系统作为车站作业系统的子系统,其效率的高低直接关系到出发列车的正点率、车辆周转时间以及其他运输生产指标,而该系统中所产生的一系列问题统称为取送车问题。
     本文针对取送车系统的优化理论与方法展开研究,系统地分析了取送车系统的要素、结构、环境和特征,深入研究了取送车问题的建模方法、模型解的构造方法、寻优算法及其启发式方法,并以此为基础,提出二维组合优化问题的概念。论文的研究工作主要包括如下几个方面:
     1.对取送车系统进行了系统的分析,不仅对取送作业的对象、货物作业地点及其分布类型、取送作业及其单项组成要素、取送作业的组织方式和取送车系统的功能要素进行了深入地剖析、对有关概念进行了清晰地界定,还对取送车系统的环境和特征作了综合分析和阐述,以此为进一步研究取送车问题奠定了概念基础。
     2.对装卸区呈放射形布置的取送车问题进行了研究,在调机牵引能力和各装卸区车辆容纳能力均充分的假设条件下,将寻求合理取送顺序、取送时机和取送次数问题作为一个系统整体建立了非直达车流取送车问题理想模型和适用于各种车流形式的取送车问题理想模型。根据模型的特点,设计了解的表达方法,并针对解的构造和计算提出了一种模块化的模型解的构造方法。通过模型及其算法得到的取送方案具有适应性的作业组织方式,克服了采用固定作业方式的缺陷。
     3.基于装卸区呈树枝形布置条件下取送作业的特点,对多趟列车相继到达车站时非直达车流和混合车流形式的取送车问题分别建立了数学模型,并针对模型的特点设计了解的表示方法、提出了模型解的模块化构造方法。模型及其解的构造方法可根据问题具体情况自适应地选择各种合理的取送作业组织方式,通过对模型求解可得到合理的取送顺序、取送时机和取送批次数。
     4.基于装卸区呈放射形布置和树枝形布置的取送车问题的研究成果,对适用于各种装卸区布置形式、各种形式的到发车流的合理取送顺序、取送批次数和取送时机问题建立了取送车问题的一般模型。对取送车问题的二维组合优化性质进行了分析,将取送车问题明确为具有两个优化维度的新型组合优化问题。针对求解取送车问题时计算成本过高的问题,通过对问题客观约束条件和生产实践中所总结出的一些经验原则进行提炼、规范,提出一套完整的取送方案生成方法,利用这套方法可将问题解的搜索空间规模从n!×2n-1压缩至n!,从而有效提高了问题的求解效率。从集合论的角度出发,论述了取送批次划分方法的理论依据。对装卸区呈放射形布置、树枝形布置和混合形布置的取送车问题分别设计了一个基准算例,并给出了它们到目前为止已知的最优仿真结果。
     5.为了提高寻优算法对各种具体问题的适应能力,提出一种具有参数自适应能力的混合算法。该算法将蚁群算法和遗传算法作为它的两个平行策略,利用云关联规则、灰色预测、以及算法迭代过程中所反馈的信息,自适应地控制有关算法参数,有效减少了算法对参数初始设置的依赖。同时,根据取送车系统自身特征,提出时间期望启发式信息和一种新型变异算子。前者作为可视化因子用于节点选择的状态转移概率公式,改善算法的收敛效率;后者则是针对不满足交货时间窗约束的解而设计的变换,它可使该类不可行解向有利方向进行变换,显著减少算法系统的冗余计算、提高算法的寻优效率。
     论文以组合数学、集合论和生产实践经验等为基础,以系统科学理论与方法为指导,以计算机技术为工具,采用将定性要求与定量约束相结合、问题的客观约束与经验原则相融合、理论研究与实证分析相呼应的方法,建立了取送车问题的数学模型,提出了模型解的模块化构造方法以及提高问题寻优效率的启发式方法,并及时通过算例分析对研究成果的适用性进行验证,形成了一个相对完整的理论体系。取送车系统优化理论与方法的研究是车站调度系统优化理论不可或缺的组成部分,因此其研究成果将为车站智能调度系统的实现提供进一步的理论依据和技术支撑,有助于车站调度决策水平和运输效率的进一步提高、有助于车站综合自动化水平的进一步提高,进而可产生巨大的经济和社会效益。
The takeout and delivery shunting is important for the freight station and the technical station with a lot of cargo handling operations. The wagon's takeout and delivery scheduling system in railway freight station (WTDSS) is a subsystem of railway station scheduling system, and its operation efficiency has a close bearing on the on-schedule rate of departure trains, wagon turnround time and many other transportation production indexes. Those problems from the WTDSS are collectively referred to as the wagon's delivery and takeout problem (WTDP).
     This dissertation dealt with the optimization theory and method of the WTDSS. It systematically analysized elements, structure, environment and charactoristies of the WTDSS and deeply studied modeling, model implementation, optimization algorithm and heuristic methods of the WTDP, and put forward a novel concept that is two-dimensional combinatorial optimization problem. The research work in the dissertation mainly includes the following:
     1. The WTDSS was synthetically analysized. Specifically, the objects of wagons' takeout-and-delivery shunting, the loading-unloading locations and their layout forms, all kinds of takeout-and-delivery operations and their component elements, the operation organization modes, the functional factors of the WTDSS were analysized comprehensively, the relevent concepts were clearly defined, and the environment and characteristcs of the WTDSS were systematically discussed, which lay the groundwork for further research on the WTDP.
     2. The WTDP whose loading-unloading locations show radial layout (R-WTDP) was studied. Under the assumption that the locomotive haulage capacity and the wagon acceptance capacity of each loading-unloading location are both unlimited, the ideal models for the non-through and the unfixed form wagon flow were respectively established based on the fact that the sequence, moment and batch number problems of takeout-and-delivery operations during a period of time are a whole. According to features of the built models, expression method of the solution was designed, and modular implementation method for the models was proposed to construct solution and to calculate the value of solution. The scheduling schemes obtained by the models and their implemation method have various adapting operation organization modes, and therefore overcome the shortcomings caused by using the fixed organization modes.
     3. Based on the characteristics of WTDP whose loading-unloading locations show tree-shape layout (T-WTDP), two models were respectively built for the non-through and the unfixed form wagon flow in the case of several trains successively arrived in the railway station, and the solution expression and the modular implementation method for the models were successively presented. Through the models and their implementation method, the reasonable operation schemes can be found which not only include the reasonable sequences, moment and batch number of takeout-and-delivery operations in planning stage but also have the adpting operation organization modes.
     4. Based on the reaserch results about the R-WTDP and the T-WTDP, the generic model (G-WTDP) was built for the sequence, moment and batch number problems of takeout-and-delivery operations during a period of time, which applys to different loading-unloading location layouts, all kinds of arrival or departure wagon flows. And then the WTDP is clearly defined as a kind of combinatorial problem with two optimization dimensions by analysis on its two-dimensional combinatorial optimization property. Aiming at the high computational cost of solving the WTDP, a set of methods used to generate the complete solution was presented by abstracting and standardizing some objective constraints of the WTDP and principles arising from practical experience. Through the proposed methods, the search space of the WTDP can be reduced from n!×2n-1 to n!, and therefore improve the efficiency of solving problem. The therotical basis for the determination procedure of batch scheme was dicussed from the set theory point of view. Three benchmark examples which are respectively for R-WTDP, T-WTDP and G-WTDP were designed, and their best known solutions were given.
     5. To improve algorithm's adaptability to different situations, a hybrid algorithm with adapting parameters was proposed. It treats ant colony optimization system (ACO) and genetic algorithm (GA) as its two parallel strategies, and it uses the cloud association rules, grey prediction and feedback from its iterative process to control adaptively relevant parameters, which can effectively reduce the reliance on initial setting of parameters. In view of WTDP characteristics, the time-expectation heuristic information and a novel mutate operator are presented. The former is used as visibility in state transition probability formula of node selection to improve the algorithm convergence efficiency. The later is used to transform a kind of infeasible solution which cannot meet the time-domain constraint, which makes the obtained solution be or be more close to feasible one and therefore improve time efficiency for solving the WTDP.
     This dissertation is on the basis of the combinatorial mathematics theory, the set theory, some transportation production experience, and so forth, is under the guidance of theory and methodology of system science, uses computer technology as a tool, adopts many methods such as integrating qualitative requirements with quantitative constraints, combining objective constraints with empirical principles and harmonizing theoretical reaserch with example analysis, has established the mathematical models of the WTDP, has proposed the model's modular implementation method, has presented the heuristics that is helpful in increasing algorithm's capability to search optimal solution, has verified research conclusions by analysis on the simulation examples, and has finally formed a relatively intact theory system. The optimization theory and method of the WTDSS is an essential part of the railway station scheduling system theory, so its research results can provide the further theory basis and technical support for realizing the intelligent railway station scheduling system, contribute to improvement in scheduling decision level and transportation efficiency, help to raise comprehensive automatic performance of the railway station scheduling system, and then produce enormous economic and social benefit.
引文
1李德毅.发现状态空间理论.小型微型计算机系统.1994,15(11):1-6
    2李德毅,孟海军,史雪梅.隶属云和隶属云发生器.计算机研究与发展.1995,32(6):15-20
    3 Li D Y. Konwledge representation in KDD based on linguistic atoms. Journal of Computer Science and Technology.1997,12(6):481~496
    4 Li D Y, Han J W, Shi X M, Chan M C. Knowledge representation and discovery based on linguistic atoms. Knowledge-Based Systems.1998,10(7):431~440
    5 Fan J H, Li D Y. Mining classification knowledge based on cloud models. Lecture Notes in Computer Science.1999,1574:317~326
    6李德毅.知识表示中的不确定性.中国工程科学.2000,2(10):73-79
    7 Wang S L, Chen G Q, Li D Y, Li D R, Yuan H N. A try for handling uncertainties in spatial data mining. Lecture Notes in Computer Science.2004,3215:513~520
    8刘常昱,李德毅,潘莉莉.基于云模型的不确定性知识表示.计算机工程与应用.2004,40(2):32-35
    9王洪利,冯玉强.基于云理论的群体复杂决策中不确定知识的表示.黑龙江大学自然科学学报.2007,24(3):340-344,348
    10刘桂花,宋承祥,刘弘.云发生器的软件实现.计算机应用研究.2007,24(1):46-48
    11吕辉军,王晔,李德毅,刘常昱.逆向云在定性评价中的应用.计算机学报.2003,26(8):1009-1014
    12刘常昱,冯芒,戴晓军,李德毅.基于云X信息的逆向云新算法.系统仿真学报.2004,16(11):2417-2420
    13李德毅,刘常昱.论正态云模型的普适性.中国工程科学.2004,6(8):28-34
    14刘常昱,李德毅,杜鹢,韩旭.正态云模型的统计分析.信息与控制.2005,32(2):236-239,248
    15罗自强,张光卫,李德毅.一维正态云的概率统计分析.信息与控制.2007,36(4):471-475
    16张勇,赵东宁,李德毅.相似云及其度量分析方法.信息与控制.2004,33(2):129-132
    17 Zhang G W, Kang J C, Luo Z Q, Meng X Y, Fang P C, Li D Y. A new kind of subjective trust model. Wuhan University Journal of Natural Sciences.2006,11(6):1457~1461
    18 Li D Y, Di K C, Li D R, Shi X M. Mining association rules with linguistic cloud model. Journal of Software.2000,11(2):143~158.
    19杜鹢,宋自林,李德毅.基于云模型的关联规则挖掘方法.解放军理工大学学报.2000,1(1):29-34
    20杜鹢,李德毅.基于云的概念划分及其在关联采掘上的应用.软件学报.2001,12(2): 196-203
    21高志年,柴日发,邢汉承.基于云概念的近似规则提取策略.计算机学报.2003,26(7):882-886
    22张飞舟,范跃祖,沈程智,李德毅.基于隶属云发生器的智能控制.航空学报.1999,20(1):89-92
    23张飞舟,范跃祖,沈程智,李德毅,陈晖.利用云模型实现智能控制倒立摆.控制理论与应用.2000,17(4):519-523
    24刘艳,李众,吴晓庆.基于推理映射的云模型控制器研究.江苏科技大学学报(自然科学版).2007,21(2):62-66
    25张光卫,康建初,李鹤松,李德毅.基于云模型的全局最优化算法.北京航空航天大学学报.2007,33(4):486-490
    26宋远骏,李德毅,杨孝宗,崔东华.电子产品可靠性的云模型评价方法.电子学报.2000,28(12):74-76,68
    27胡伶俐,贾珊珊.基于云模型的交通运输枢纽系统综合评价.中国水运.2007,7(8):135-136
    28陆建江,钱祖平,宋自林.正态云关联规则在预测中的应用.计算机研究与发展.2000,37(11):1317-1320
    29蒋嵘,李德毅,陈晖.基于云模型的时间序列预测.解放军理工大学学报.2000,1(5):13-18
    30梁俊斌,苏德富.基于云模型的网格资源分配策略.计算机工程与应用.2005,41(5):147-149,160
    31 Jia S P, Hao B H. Research on CFCM:car following model using cloud model theory. Journal of Transportation Systems Engineering and information Technology.2007,7(6): 67~73
    32邓聚龙.灰理论基础.武汉:华中科技大学出版社,2002
    33邓聚龙.灰预测与灰决策.武汉:华中科技大学出版社,2002
    34刘思峰,党耀国,方志耕.灰色系统理论及其应用.北京:科学出版社,2004
    35 Deng J L. Control problems of grey systems. Systems & Control Letters.1982,1(5): 49~55
    36徐元栋,武振业.基于有限理性的股票灰色定价与股票市场非有效性现象.管理工程学报.2003,17(2):115-117
    37李俊峰,戴文战.基于级比数据处理的多段灰色建模方法及在我国GDP建模中的应用.系统工程理论与实践.2004,24(9):98-101,120
    38陈德军,张玉民,陈绵云.系统云灰色宏观调控预测模型及其应用研究.控制与决策.2005,20(5):553-556,588
    39 Ku L L, Huang T C. Sequential monitoring of manufacturing processes:an application of grey forecasting models. The International Journal of Advanced Manufacturing and Technology.2006,27(5-6):543~546
    40 Wu A X, Xi Y, Yang B H, Chen X S, Jiang H C. Study on grey forecasting model of copper extraction rate with bioleaching of primary sulfide ore. Acta Metallurgica Sinica.2007,20(2):117~128
    41谢乃明.灰色系统建模技术研究.南京航空航天大学博士学位论文.2008
    42宋中民,刘希强,王树泽.生成空间及IM模型.系统工程.1992,10(6):37-42
    43黄福勇.灰色系统建模的变换方法.系统工程理论与实践.1994,14(6):35-39
    44 Deng J L. Moving operator in grey theory. The Journal of Grey System.1999,11(1):1-4
    45 Song Z M, Wang Z D, Tong X J. Grey generating space on opposite accumulation. The Journal of Grey System.2001,13(4):305~308
    46 Song Z M, Xiao X P, Deng J L. The character of opposite direction AGO and class ratio. The Journal of Grey System.2002,14(1):9-14
    47 Deng J L, Proving GM(1,1) modeling via four data (at least). The Journal of Grey System.2004,16(1):1-4
    48刘希强.多因素的灰色预测模型.系统工程理论方法应用.1995,4(1):34-36
    49何勇,鲍一丹,吴江明.随机型时间序列预测方法的研究.系统工程理论与实践.1997,17(1):36-43
    50谭冠军.GM(1,1)模型的背景值构造方法和应用(Ⅰ).系统工程理论与实践.2000,20(4):98-103
    51谭冠军.GM(1,1)模型的背景值构造方法和应用(Ⅱ).系统工程理论与实践.2000,20(5):125-127,132
    52谭冠军.GM(1,1)模型的背景值构造方法和应用(Ⅲ).系统工程理论与实践.2000,20(6):70-74
    53张辉,胡适耕.GM(1,1)模型的精确解法.系统工程理论方法应用.2001,10(1):72-74
    54穆勇.无偏灰色GM(1,1)模型的直接建模法.系统工程与电子技术.2003,25(9):1094-1095,1107
    55刘斌,刘思峰,翟振杰,党耀国.GM(1,1)模型时间响应函数的最优化.中国管理科学.2003,11(4):54-57
    56蒋卫东,李夕兵,赵国彦.非等时序列预测的时数分离研究.系统工程理论与实践.2003,23(1):68-72
    57戴文战,李俊峰.非等间距GM(1,1)模型建模研究.系统工程理论与实践.2005,25(9):89-93
    58何海,陈绵云.GM(1,1)模型预测公式的缺陷及改进.武汉理工大学学报.2004,26(7):81-83
    59党耀国,刘思峰,刘斌.以x(n)为初始条件的GM模型.中国管理科学.2005,13(1):132-135
    60谢乃明,刘思峰.离散GM(1,1)模型与灰色预测模型建模机理.系统工程理论与实践.2005,25(1):93-99
    61谢乃明,刘思峰.离散灰色模型的拓展及其最优化求解.系统工程理论与实践.2006, 26(6):108-112
    62谢乃明,刘思峰.一类离散灰色模型及其预测效果研究.系统工程学报.2006,21(5):520-523
    63 Xie N M, Liu S F. Discrete grey forecasting model and its optimization. Applied Mathematical Modelling.2009,33(2):1173~1186
    64 Lin Y H, Lee P C. Novel high-precision grey forecasting model. Automation in Construction.2007,16(6):771~777
    65刘思峰.冲击扰动系统预测陷阱与缓冲算子.华中理工大学学报.1997,25(1):25-27
    66宋中民,张曙红.灰色系统的分离建模方法.系统工程理论与实践.2002,22(5):103-107
    67党耀国,刘思峰.关于弱化缓冲算子的研究.中国管理科学.2004,12(2):108-111
    68党耀国,刘斌,关叶青.关于强化缓冲算子的研究.控制与决策.2005,20(12):1332-1336
    69肖敏,令伟家.铁道部总经济师:中国铁路是世界上最繁忙的铁路.http:// news.xinhuanet.com/fortune/2005-09/21/content 3519008.htm.2005.09.21
    70俞玮.铁道部:2009年铁路客货运量再创新高.http://www.chinadaily.com. cn/dfpd/huimo2009/2010-01/07/content_9281922.htm.2010.01.07
    71铁道部科学技术情报研究所.国外铁路.中国铁道出版社,1991
    72马许.车站与专用线在统一技术作业过程中相互配合条件之研究.北京铁道学院第一次科学讨论会论文选集(铁道运输部分),1956:69-111
    73高资,杨明伦.确定树枝型专用线最优取送方案的探讨.西南交通大学学报.1981,(3):64-88
    74徐忠民,孔庆铃.直达列车取送车顺序的优化.北方交通大学学报.1988,(2):70-74
    75顾守淮.两类取送车模型的取送顺序计算方法.兰州铁道学院学报.1992,11(3):58-63
    76韩廷桂.车站货运作业过程优化的探讨.兰州铁道学院学报.1992,11(Z01):120-125
    77林诒勋.排序论在铁路专用线调车问题中的应用.郑州大学学报(理学版).1987,(2):1-2
    78杜文,李文权.放射形专用线直达列车取送车问题的算法.西南交通大学学报.1995,30(5):503-508
    79李文权,杜文.树枝状铁路专用线取送车问题的数学模型及算法.河南大学学报(自然科学版).1997,27(2):1-8
    80王慈光.运输模型及优化.北京:中国铁道出版社,2004
    81王慈光.放射形专用线非直达车流取送车问题研究.交通运输工程与信息学报.2006,4(3):16-23
    82王慈光.树枝形专用线取送车问题的研究.西南交通大学学报.1996,31(6):675-680
    83宋建业.直达列车多点装卸取送顺序优化的表上移动法.兰州铁道学院学报.2002,21(1):76-79
    84关镇东.关于应用技术分析方法合理配置取送调车机的探讨.中国铁道科学.2001,22(4):93-96
    85赵洋,方晓平.层次分析法在取送调车作业计划编制中的应用.铁道运输与经济.2005,27(7):78-80
    86杨信丰,李引珍.直达车流取送问题的模型及其算法.交通运输系统工程与信息.2008,8(2):103-107
    87谢金宝.非直达车流取送方案的中断时间筛选法研究.兰州交通大学学报.2009,28(3):95-99
    88靳磊.铁路树枝形专用线取送车作业优化.北京交通大学硕士论文.2007
    89田毅.改进调车作业方法压缩货物作业车停时.铁道运输与经济.2000,(2):17-18
    90王雅琳,李开峰,马杰等.遗传算法在企业铁路取送调车作业优化中的应用.系统工程.2007,25(3):94-99
    91杨运贵,王慈光,薛锋.树枝形铁路专用线取送车问题的遗传算法研究.计算机工程与应用.2008,44(12):210-211,214
    92石红国,彭其渊,郭寒英.树枝型专用线取送车问题的哈密尔顿图解法.中国铁道科学.2005,26(2):132-135
    93张键,宋建业.货物作业车取送模型的优化.货物运输,2008,(10):13-16
    94敬媛媛.树枝型专用线取送车算法的研究.成都大学学报(自然科学版),1998,17(4):36-42
    95黄向荣.树枝型专用线取送车的模型及算法研究.兰州交通大学学报(自然科学版).2007,26(3):51-54
    96余少鹤,李夏苗.货物作业车取送模型及算法研究.铁道运输与经济.2002,24(12):46-48
    97李智.基于改进型蚁群算法的货物作业车取送模型优化.铁道运输与经济.2004,26(4):73-76
    98潘玲巧,林志安.关于树枝形专用线取送车问题的探讨.内蒙古科技与经济.2008,(6):288-289,291
    99 Mosheiov G. The traveling salesman problem with pickup and delivery. European Journal of Operational Research.1994,79(2):299~310
    100Anily S, Mosheiov G. The traveling salesman problem with delivery and backhauls. Operations Research Letters.1994,16(1):11-18
    101Gendreau M, Laporte G, Vigo D. Heuristics for the traveling salesman problem with pickup and delivery. Computers & Operations Research.1999,26(7):699-714
    102Renaud J, Boctor F F, Ouenniche J. A heuristic for the pickup and delivery traveling salesman problem. Computers & Operations Research.2000,27(9):905-916
    103Renaud J, Boctor F F, Laporte G. Perturbation heuristics for the pickup and delivery traveling salesman problem, Computers & Operations Research.2002,29(9):1129-1141
    104Gendreau M, Hertz A, Laporte G. The traveling salesman problem with backhauls.

© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号

地址:北京市海淀区学院路29号 邮编:100083

电话:办公室:(+86 10)66554848;文献借阅、咨询服务、科技查新:66554700