基于约束规划的编组站配流模型研究.pdf

2011全国博士生学术论坛(交通运输工程) 基于约束规划的编组站配流模型研究马亮1,云培研1, (,四川成都, 张雪松2,郭进1 610031 ,北京,100844) 摘要:为了解决编组站配流模型规模过于庞大、适用性不强、求解方法复杂、算法收敛慢等缺点, 通过集合论分析了问题的本质,在此基础上建立了一个以不同属性车流累积为模型对象、出发车车流来源及解编顺序为决策变量、以中停时最小及出发车最多为总目标的约束规划(Constraint Programming,CP)模型。将模型求解分为:利用约束传播得到初始解和利用搜索技术结合约束转播改进初始解两部分,并用约束规划算法引擎(cP Optimizer):对于阶段计划到发列车为40列左右情况下,本模型均能在普通Pc机上运行10秒左右就能得到比较满意的方案,符合现场对算法时间及空间复杂度要求。关键词:编组站;配流;解编顺序;优化模型;约束规划;集合论中图分类号::A Research onWagon--Flow Model Based Constraint Programmingin aMarshalling Yard .YALian∥。Y[/NPei-.-( of Information Science and Technology,SouthwestJiaotong University,Chengdu 610031, and Technologies Center MOR,Beijingl00844,China) Abstract:In order tosolve these ings ofwagon-flowailocation model,such as:es too large,the applicabilityis not plexsolving methods,algorithms slowlyconvergence,and SO on. Thenature of the problem Was analyzed through set constraint programming(Constraint Programming,CP)model contains:atraffic with diffemntproperties accumulated as model object,the resource ofdeparture trainsanddisintegration andgrouping orderas decision variables,the minimum time tostopand maximum ofthedeparture trainsup tothe overall themodelis divided into:using theconstraint propagation toget theinitialsolutions and using thesearchtechnology toimprovethe initialSOlution constraint broadcast in two parts,and constraint program mingal godth mengine(CP Optimizer)was used to achievesolving thecase ofthenumber ofthe arrivingand thedeparture trainsup to40,the moresatisfactory solution Was got when themodeirun onan ordinary PCforl shows thatthe model satisfiestherequirements plexity inspot. Keywords:Marshalling Yard;Wagon·flow Allocation;Disintegration andGrouping Order; Optimization model;Constraint Programming;Set Theory 0引言为了提高铁路编组站自动化、信息化水平,就必须要实现阶段计划的自动编制,而阶段计划编制的前提就是要对车站目前及未来某一时间段的车流进行统筹、分配。由于编组站本质是一个离散基金项目:国家自然科学基金(5096