基于博弈理论的货运列车编组调度模型与算法研究
详细信息    本馆镜像全文|  推荐本文 |  |   获取CNKI官网全文
摘要
随着我国铁路现代化建设的高速发展,车站编组调度效率瓶颈已凸显。作为一类典型组合优化复杂问题,货运列车编组调度优化成为具有理论水平和实际应用意义的重要研究领域。
     本文介绍了现阶段铁路信息化的成果与不足、国内外对于货运列车编组调度模型与算法研究现状。阐述了Agent、MAS的相关概念、性质及应用等基础知识。分析了几种经典优化理论方法。研究了博弈论的发展、类型划分、表示形式及算法实现平台等。
     以GMAIM为原型,进一步研究应用于编组调度问题的多Agent博弈协作,建立了货车编组调度博弈概念模型,并设计了相应博弈算法。
     根据货运列车编组调度过程的性质和特征,分析讨论了货车编组调度的工作流程、效率评价指标、优化目标及约束条件,建立了基于博弈论的货运列车编组调度优化可解模型。
     本文比较了多种常用的系统作业调度算法。提出了针对编组调度模型的编组调度贪心算法、基于网络优化配流的表上作业法、编组调度遗传算法等3类求解算法。
     作者研究了基于FCFS的货车编组调度算法实现。以某编组站为计算实例,针对3类编组调度优化算法进行了算法效率比较,并分析了中时上限、满轴率等因素对编组调度效率的影响。
     最后,作者分析了影响编组站解体能力的相关因素。在参考现存研究成果的基础上,建立了编组站通过能力计算模型,针对性的研究了编组站设备数量与负荷优化策略。通过编组站到解过程仿真数据的构建,在设置一系列的初始仿真条件下对编组站到解作业过程进行连续多次仿真。
With the rapid development of the modernization of China's railway, the efficiency of marshalling stations is an obvious bottleneck, as a typical combinatorial-optimizing complex problem, the optimization of marshalling-scheduling of freight trains attracts the attentions of many countries and scholars to be an academic hot-spot.
     The paper describes the advantages and shortcomings of railway informational at this stage and the researches of the marshalling-scheduling model and algorithm for the freight train at home and abroad. The author describes the basic knowledge, as the related concepts, nature and application of Agent, MAS. Several classical optimal theory methods are analysis of. The development, type, classification and representation of game theory and the platform of algorithm implementation have been studied.
     Taking the GMAIM as a prototype, the author makes further research in marshalling-scheduling problem of multi-Agent Game collaboration, and establishes a marshalling-scheduling game-concept model of freight trains, designs the corresponding game algorithm.
     According to the nature and characteristics of freight train marshalling-scheduling process, the author analyzes and discusses the marshalling-scheduling workflow, efficiency evaluation index, optimization objectives and constraints of the freight trains, establishes a solvable marshalling-scheduling optimal model of freight trains based on game theory.
     The author introduces a variety of common system job scheduling algorithms with comparing. 3 kinds of algorithms for salvation of the marshalling-scheduling model are proposed: the marshalling-scheduling greedy algorithm, the operating table method based on the network optimization, and the genetic algorithm.
     The author studies the achieve of marshalling-scheduling algorithms of freight trains based on FCFS. Taking a marshalling station as calculation example, for the three categories of marshalling-scheduling optimal algorithms the efficiency of the algorithms is compared, analyzing in the impact of the time-limit, full-axis rate and other factors on the marshalling-scheduling efficiency.
     Finally, the author analyses the relevant impact factors of the disintegration of the marshalling yard capacities. In reference to the existing research results, the marshalling yard capacity calculation model is established, targeted to the optimization strategy of the equipment quantity and load whithin the marshalling yard. By constructing the simulation data for the arriving-disintergration marshalling process, setting up a series of initial simulation, the author made simulation of the marshalling process for times.
引文
[1]曹魁久,孔庆铃.货物列车编组计划[M].中国铁道出版社, 1992
    [2]曹家明,朱松年.优化列车编组计划的0-1规划法[J].铁道学报,1992:14(4):49-57.
    [3]曹家明,朱松年.铁路网上技术直达列车编组计划优化的二次0-1规划法[J].铁道学报, 1993: 15(2):62-70
    [4]曹家明,朱松年.铁路网上列车编组计划的综合编制[J].西南交通大学学报, 1993: No.5
    [5]杨时刚,史峰,李致忠.制定列车编组计划的人工神经网络方法[J].长沙铁道学院学报, 2002: 20(3):79-84
    [6]林柏梁,朱松年.优化编组计划的非线性0-1规划模型及模拟退火算法[J].铁道学报, 1994: 16(2):61-66
    [7]林柏梁,朱松年.带有改编能力限制的编组计划优化模型及算法[J].铁道学报, 1994: 29(5):488-493
    [8]林柏梁,朱松年,史德耀,何世伟.装车地直达列车编组计划的优化模型[J].中国铁道科学, 1995: 16(2):108-114
    [9]林柏梁.直达与区段列车编组计划及车流径路的整体优化方法[J].铁道学报, 1996: 18(5):1-8
    [10]朱松年.路网上车流径路与列车编组计划的整体优化[J].铁道学报,1996:18 (1):1-7
    [11]史峰,李致中.列车编组计划网络优化方法[J].铁道学报, 1994: 16(2):74-79
    [12]胡安洲.车流径路与编组计划综合优化的网络方法[J].铁道学报,1997:19(1)1-6
    [13]李映红,吴世贵,彭其渊.货物列车编组计划网络模型的建立及算法[J].西南交通大学学报, 2002: 97(1): 68-71
    [14]林柏梁,朱松年,赵强.技术直达列车编组计划的阶跃模型及其同沟变换[J].西南交通大学学报, 1994: 29(1):91-96
    [15]林柏梁.具有非线性改编能力费用的列车编组计划优化[J].铁道学报, 1996: 18增刊: 37-42
    [16] Keaton, M.H.”Designing Optimal Railroad Operating Plans: Lagrangian Relaxation andHeuristic Approaches,”Transportation Research, 23B, pp.415-431, 1989
    [17] Keaton, M.H.,”Designing Railroad Operating Plans: A Dual Adjustment Method for Implementing Lagrangian Relaxation,”Transportation Science, 26, pp.263-279, 1992.
    [18]薛定宇,陈阳泉.系统仿真技术与应用[M].北京:清华大学出版社, 2002.
    [19]飞思科技产品研发中心. MATLAB 6.5辅助优化计算与设计[M].北京:电子工业出版社2003.1.
    [20]孙兆林. MATLAB 6.x图像处理[M].北京:清华大学出版社, 2002.5.
    [21]梁迪,陶泽.多目标柔性作业调度的优化研究[J].计算机工程与应用,2009,45(15)
    [22] Okan Orsan Ozener. Collaboration in transportation [D].Georgia: Georgia Institute of Technology, 2008.
    [23]杜荣华,吴泉.城市区域交通协调控制中的多Agent博弈研究[J].计算机工程与科学.Vol 29(4), 2007: 120-123.
    [24]李文权,王炜.铁路编组站到发线运用的排序模型和算法[J].系统工程理论与实践,2000.6
    [25]王世东,郑力.蚁群算法在调机运用计划中的应用[J].中国铁道科学,2007.5
    [26]刘霆,何世伟.编组站调度计划随机机会约束规划模型及算法研究[J].铁道学报,2007.8
    [27]王明慧,赵强.编组站智能调度系统阶段计划优化模型及算法研究[J].铁道学报,2005.12
    [28]王慈光.用表上作业法求解编组站配流问题的研究[J].铁道学报, 2002.8
    [29] Andrew Gilpin.Algorithms for abstracting and solving imperfect information games [D]. Pennsylvania: Carnegie Mellon University, 2009.
    [30]袁爱进,曹立明,王小平.一种基于博弈论的多Agent交互模型[J].计算机工程.Vol 31(6).2005.
    [31] Ieong.Cooperation in competition: Efficiently representing and reasoning about coalitional games [D].California: Stanford University, 2008.
    [32] Mutz.Eliciting honest behavior on computational grids [D].California: University of California, Santa Barbara, 2008.
    [33] Borghetti.Opponent modeling in interesting adversarial environments [D].Minnesota: University of Minnesota, 2008.
    [34] Brandon, Bettye Lynn.Computers in the design process: Comparing creativity ratings of interior design solutions using pencil-based and computer-based design methods in schematic development [D].Virginia: Virginia Polytechnic Institute and State Universit, 1994.
    [35] Buettner.Designing an optimal software intensive system acquisition: A game theoretic approach [D].California: University of Southern California, 2008.
    [36]姜启源.数学建模(第三版)[M].北京:高等教育出版社, 2003.
    [37]赵静.数学建模与数学实践[M].北京:高等教育出版社, 2000.
    [38]关强.交通运输技术管理[M].北京:人民教育出版社, 2004.
    [39]城市公共交通运营调度管理[M].北京:中国铁道出版社2001.
    [40] Yang Zhao-Sheng, Sun Jian-ping, Yang Chunxiao.Multi-A-gent Urban Expressway Control System Based on General-ized Knowledge-Based Model [A].Proc of the 6th IEEE IntConf on Intelligent Transportation Systems[C].2003.1759-1763.
    [41]乔增伟.一种基于支持向量机决策树多类分类器[J].计算机应用与软件, 2009.
    [42] Ieong.Cooperation in competition: Efficiently representing and reasoning about coalitional games [D].California: Stanford University, 2008.
    [43] Trandafir.A strategic model of investment and price competition among container ports [D].Rhode Island: University of Rhode Island, 2009.
    [44] William Stallings.操作系统-精髓与设计原理[M].北京:电子工业出版社, 2006.
    [45]扬启帆,李浙宁.数学建模案例集[M].北京:高等教育出版社,2006.
    [46]蔡锁章,数学建模原理与方法[M].北京:海洋出版社,2000。
    [47]陈东彦等,数学建模[M].北京:科学出版社,2007。
    [48] Tulett David Micheal. Optimal Railway Marshaling [D]. Canada: Queen's University at Kingston, 1986.
    [49] Vorobeychik.Mechanism design and analysis using simulation-based game models [D].Michigan: University of Michigan, 2008.
    [50] Hewitt C.Open Information Systems Semantics for Distributed Artificial Intelligence.Artificial Intelligence.1991.47 (1).pp.79~106
    [51]石纯一,张伟等著.基于Agent的计算.清华大学出版社. 2007.
    [52] Rouff Christopher, Vanderbilt Amy, Hinchey Mike, Truszkowski Walt. Verification of emergent behaviors in swarm-based systems. Proceedings-11thIEEE International Conference and Workshop on the Engineering of Computer-Based Systems, ECBS 2004, Proceedings-11th IEEE International Conference and Workshop on the Engineering of Computer-Based Systems, ECBS 2004. 443-448
    [53]Vu Duc Nguyen.A dispatching method for automated lifting vehicles in automated port container terminals[J].Computers & Industrial Engineering,2009,56(3)
    [54]Lee, Y.A neighborhood search heuristic for pre-marshalling export containers[J].European Journal of Operational Research,2009,196(2)
    [55]Yusin Lee.An optimization model for the container pre-marshallingproblem[J].Computers & Operations Research,2007,34(11)
    [56]景云,王慈光,薛锋等.编组站列车溜放时间的估计方法[J].西南交通大学学报,2009,44(6)
    [57]邢群雁,栗学人.图像识别在编组站驼峰作业过程控制中的应用[J].中国铁道科学,2005,26(4)
    [58]李海鹰,张超.编组站到解系统通过能力计算方法[J].中国铁道科学,2010,31(3)
    [59]李海鹰,杨肇夏.基于不均衡运输的编组站能力计算方法探讨[J].北京交通大学学报(自然科学版),2005,29(6)
    [60]俞平.成都北编组站CIPS的功能与运用[J].中国铁路,2008,""(5)
    [61]杨焱,谈振辉,钟章队.铁路大型枢纽地区GSM-R网络无线资源的管理[J].北京交通大学学报,2010,34(2)
    [62]Zhang Peiyan.提高编组站调车场尾部能力措施的研究[J].铁道标准设计,2008,""(9)
    [63]薛纬华.侯月线亿吨通道月山编组站扩能改造[J].铁道标准设计,2008,""(1)
    [64]景云,王慈光.不确定条件下编组站动态配流模型及算法研究[J].铁道学报,2010,32(4)
    [65]任广伟.编组站调度指挥智能化管理[J].中国铁路,2009,""(11)
    [66]张开治.编组站综合自动化配置规模与作业能力匹配分析[J].中国铁路,2008,""(11)
    [67]耿颖.我国铁路编组站综合集成自动化的发展[J].中国铁路,2008,""(9)
    [68]荆世明,吴健波.铁路编组站车流配流问题研究[J].铁道运输与经济,2008,30(1)
    [69]Zhang, Yanwei,Mi, Weijian,Chang, Daofang.An Optimization Model for Intra-Bay Relocation of Outbound Container on Container Yards[A].Automation and Logistics, 2007 IEEE International Conference on; Jinan,China[C].2007.
    [70]Yanwei Zhang,Weijian Mi.An Optimization Model for Intra-Bay Relocation of Outbound Container on Container Yards[A].2007 IEEE International Conference on Automation and Logistics (ICAL 2007), vol.2[C].2007.
    [71]Feng Xue.A METHOD OF EXCHANGE WAGON-FLOW ALLOCATING IN BIDIRECTIONAL MARSHALLING YARDS[A].First International Conference on Transportation Engineering (ICTE 2007), vol.3[C].2007.
    [72]Rail renaissance [J].Industrial Minerals, 2008, 0(486)
    [73]王正彬.区段站阶段计划调整模型与算法研究[D].2007.
    [74]张军占.摘挂列车编组钩计划自动编制研究和实现[D].2007.
    [75]菅美英.基于MAS的列车编组计划与运行图的一体化优化方法研究[D].2006.
    [76]李海鹰.铁路货物运输组织模式改革及相关技术研究[D].2008.
    [77]李艳春.基于移动agent的电子商务的研究与应用[D].2006.
    [78]陈强.基于Agent技术的电子商务系统的研究与应用[D].2006.
    [79]刘婷.基于移动Agent的协商机制的研究与应用[D].2009.
    [80]伍雄斌.城市交通集成系统的多智能体博弈模型研究[D].2007.
    [81]赵杰.活塞加工工艺与资源调度及其仿真的研究[D].2006.
    [82]江岸.基于多Agent的城市交通控制与诱导系统协作研究[D].2007.
    [83]詹征.湖南联鑫ERP实施研究[D].2008.
    [84]张全文.高等级公路沥青路面养护管理研究[D].2010.
    [85]韩冰.遗传算法在帕昭拉水库优化调度中的应用研究[D].2007.
    [86]林闯,李雅娟,王忠民.性能评价形式化方法的现状和发展[J].电子学报,2002,30(z1)
    [87]朱寒菡.基于交通流理论的短消息信息流研究[D].2009.
    [88]郝颖娟.有偏好信息的不确定多属性决策途径[D].2009.
    [89]刘平.谈层次分析法在决策中的应用[J].时代经贸(学术版),2008,6(8)
    [90]祝木田.基于层次分析的蔬菜种植决策系统[D].2006.
    [91]闫成玉.辽化烯烃厂生产现场整体优化管理研究[D].2008.
    [92]周靖.产品质量竞争与激励的博弈机制分析[D].2005.
    [93]朱晓建.基于信息熵的博弈支付及纳什均衡选择研究[D].2008.
    [94]赵相茹.中国货币政策的国际协调分析——从日本实践谈起[D].2007.
    [95]刘俊.基于电子商务环境的供销管理信息系统的研究与开发[D].2004.
    [96]杨异.校园网络教学系统[D].2007.
    [97]何全庆.钢铁企业ERP系统的研究与开发——攀钢产销一体化管理系统设计与实现[D].2007.
    [98]乔贵春.基于知识地图的教师个人知识管理平台的设计与实现[D].2007.
    [99]韩中庚.货运列车的优化编组调度方案与实现方法[J].数学的实践与认识,2009,39(16)
    [100]江志华.常用作业调度算法的分析与评价[J].乐山师范学院学报,2008,23(12)
    [101]王慈光.用表上作业法求解编组站配流问题的研究[J].铁道学报,2002,24(4)

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

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

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