双线铁路列车运行调整问题的蚁群算法研究

双线铁路列车运行调整问题的蚁群算法研究 返利购(hi369.com)-你来购物，我来返利～铁路免费资源尽在铁路吧(www.tielu8.cn) 双线铁路列车运行调整问题的蚁群算法研究 摘 要:列车运行调整问题的计算机自动求解是实现铁路行车指挥自动化的重要内容，也是我国铁路信息化建设的一个关键技术。从我国铁路行车组织实际出发，将列车运行调整问题归并为制造系统中的Flow-Shop调度问题，构建了双线铁路列车运行调整问题的优化模型。针对模型解空间大、约束条件复杂的特点， 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 了一种基于蚁群算法的求解算法。仿真试验 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 明，该算法是可行的，可以快速得到近似最优解。 关键词:列车运行调整; Flow-Shop调度;优化模型;蚁群算法 引言 一直以来，国内外许多专家学者分别运用最优化方法、人工智能方法、离散事件动态系统方法和智能计算方法对列车运行调整问题进行了研究，取得了一定的成果。如:文献[1]将调度问题视为0-1混合整数 规划 污水管网监理规划下载职业规划大学生职业规划个人职业规划职业规划论文 问题，并利用分枝定界法求出优化解;文献[2]结合了模糊数学、Petri网的知识构建了专家系统推理机，并将其应用到列车运行调整中;文献[3]将列车运行调整系统描述为离散事件动态系统，通过建立系统状态转移方程来解决列车运行调整问题;文献[4]在建立混合0-1线性规划优化模型后，采用禁忌搜索算法来优化列车铺画顺序。这些方法各有特点，为该问题的深入研究起到了积极的作用，但是，列车运行调整问题约束条件复杂、解空间庞大，求解精度、速度和操作的简便性还有待提高，客观上需要引入新的方法来进一步完返利购(hi369.com)-你来购物，我来返利～铁路免费资源尽在铁路吧(www.tielu8.cn) 返利购(hi369.com)-你来购物，我来返利～铁路免费资源尽在铁路吧(www.tielu8.cn) 善。而蚁群算法是一种新兴的解决组合优化问题的方法，具有分布式并行搜索的本质特征，并有良好的发现新解能力和很强的鲁棒性[6][7][8]。为此，本文尝试将蚁群算法应用到列车运行调整问题优化求解中，从而达到对列车运行调整问题迅速优化求解的目的。 1 列车运行调整模型 列车运行过程中的作业按照时间和空间上的离散特征可以分为若干区间和车站的单项作业，因而，列车运行调整问题可以看作对列车区间和车站作业的安排问题，类似于生产制造系统中的流水作业调度问题(即flow-shop问题)。闭塞区间对应加工机器，车站对应缓冲区，列车对应加工工件，列车占用区间可以看作机器加工工序，列车的区间运行时间就是工序调度时间。因此，可以借鉴流水作业调度问题较完备的研究理论，对列车运行调整问题进行分析求解。 如图1所示的两列车通过和两个连续区间的调整问题，ab,kk，1 1234r可以抽象为作业序列:(表示列车通过区间的作Vvvvv,{,,,}vjkakakbkbk，，jk11 r业，表示该作业在全部作业序列中的位置)。 bka ak+1 图1 列车通过区间示意图 tak21vvak，1ak 43vvbk1，bktbk 图2 列车工序的析取图 返利购(hi369.com)-你来购物，我来返利～铁路免费资源尽在铁路吧(www.tielu8.cn) 返利购(hi369.com)-你来购物，我来返利～铁路免费资源尽在铁路吧(www.tielu8.cn) 上述调度过程可以用析取图清晰表示。其中，表示GVCD,,(,)V调度列车集通过区间作业的集合，在图上以节点形式表示;为所有C合取弧的集合，合取弧表示列车通过调度区段各个区间的顺序，每条合取弧上都标注一个正的权值，表示开始节点所对应作业的加工时间，即列车区间运行时分;为所有析取边的集合，析取边将不同列D 车在同一区间的运行作业两两相连。 可以将图1中的调整问题转化为如图2所示的析取图形式。其中 表示列车在区间的运行时间;实线表示合取弧，虚线表示析取弧;tkak 在图中确定析取弧的指向，即制定列车在区间的通行策略是这ab,k，1 个局部调度问题的关键。图1中已经确定列车先通过第个区间，bk，1 42所以析取边由指向。依据上述方法，可以将被调整列车通过各vv，，bk1ak1 个区间的作业集全部表示成图2的扩展形式，便得到了列车运行调整问题的析取图。 为了不失一般性，下面以不存在支线的铁路双线自动闭塞区段下行系统为研究对象，来研究列车运行调整问题。设区段内共有个区m间，个车站，依次记作，。调整开始时间为，DDD,,,SSS,,,Tm，112m121m，b调整时间长度，则调整时间范围为。在此时间范围内，需T[T,T，T]dbbd 要调整的列车有列(包括该区段技术站始发列车和调整时间范围内J 将要到达本区段的列车)记作。列车在区间允许Llll,{,,,}(,)SSjkk，112J 开始调度时间记作qb，区间运行时分为p，作业完毕时间为qc，则jkjkjk存在qcqbp,，成立，其中，jJ,(1,2,,),km,，(1,2,,1)。 jkjkjk 根据以上约定，定义双线铁路区段下行方向列车运行调整问题的返利购(hi369.com)-你来购物，我来返利～铁路免费资源尽在铁路吧(www.tielu8.cn) 返利购(hi369.com)-你来购物，我来返利～铁路免费资源尽在铁路吧(www.tielu8.cn) 规划模型为: mJ22(1) min()()CwqbQBqcQC,,，,,,jjkjkjkjk,,11kj st. '' (2) qbqbkkmkk,,,，,0,(1,2,,1),'jkjk (3) qbqbIqbqb,,,''jkjkjkjk ' (4) qbqcjjL,,,,,,'jk到发，jk1 ' (5) qcqbjjL,,,,,,'jk发到，jk1 (6) qbqcA,,,jkjkjkjk,,,111 pqt (7) ptOtOt,，，jkjkjkjkjkjk，，11 LtLNtTTT()[,],,,， (8) jkkbbd (9) qbTjL,,,jf 式(1)为模型的目标函数，因为列车运行调整的目的是使列车恢复按图行车，提高列车正点率，所以模型的目标函数确定为列车晚点时间最小，即列车区间工序的推迟完成时间最小，目标函数可表达为加权后的列车实际运行时间与图定时间的欧氏空间距离最小，其中QB、QC分别表示列车在区间运行图规定的开始调度时间和结束jkjkjk 调度时间;式(2)、(3)为列车通过区间顺序约束。式(2)表明列车必须按照区间的先后顺序运行，式(3)表明在同一区间通过的先后两列车之间，必须满足一定的追踪间隔时间I;式(4)、(5)为在不能同时办理接、发列车作业的车站，先后通过车站的两列车之间需要满足不同时到发时间,和不同时发到时间,;式(6)为车站作到发发到 ,,1,,0业时间约束，其中，表示列车在车站有作业要求，表示jkjkjk返利购(hi369.com)-你来购物，我来返利～铁路免费资源尽在铁路吧(www.tielu8.cn) 返利购(hi369.com)-你来购物，我来返利～铁路免费资源尽在铁路吧(www.tielu8.cn) 列车在车站没有作业要求;式(7)为列车区间运行时间约束，其jk 中， 为引入的决策变量，表示列车在站停车等待加工，O,1Ojkjkjk pqt表示列车在站不停车通过;、、分别表示列车在区间O,0tttjjkjkjkjkjk 的纯运行时分和起、停车附加时分;式(8)和式(9)分别为车站k 到发线约束和列车最早发车时间约束。 2 模型的求解 在实际列车运行调整过程中，一旦列车的铺画顺序确定了，那么列车的会让 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 也就确定了，所以我们可以在满足约束条件的情况下，通过确定调整列车的最优工序调度顺序，来解决列车运行调整问题。近年来，蚁群算法在求解工序调度问题中得到长足的发展并取得了良好的效果，越来越受到关注。因此，本文尝试利用蚁群算法来求解列车运行调整问题。 2.1蚁群算法求解过程描述 基于蚁群算法的列车运行调整问题求解过程可以表述为:根据算法的要求，在最早开始占用区间的列车调度工序节点上放置一定数量的蚂蚁。每只蚂蚁在调度工序集合中搜索时，为了保证操作符合列车的区间运行顺序，需要按照状态转移规则选取一个前驱工序已经完成，而本身未完成的工序节点作为移动目标，并逐步遍历所有工序节点，实现对列车工序的排序[9]。接着，在满足约束的条件下，按照给定的列车工序调度顺序逐一安排，就可以得到列车运行调整问题的一个优化解。算法总流程图如图3。 返利购(hi369.com)-你来购物，我来返利～铁路免费资源尽在铁路吧(www.tielu8.cn) 返利购(hi369.com)-你来购物，我来返利～铁路免费资源尽在铁路吧(www.tielu8.cn) 图3:蚁群算法求解列车运行调整问 题流程 2.2 蚁群算法状态转移规则 r在不引起误解的情况下，考虑用节点在序列中的位置来代表V sr这个节点。设当前蚂蚁位于调度作业处，需要选择下一调度作业vv''jkjk插入到作业序列中。 ,,{1,2,}r 选择的规则是: ,,,argmax([()][()]),,tt,qq,rkrk,a0,kPr(10) s,,'qq,0,s, 式中q是随机变量，q是预设的0,1之间的阈值，它 决定 郑伟家庭教育讲座全集个人独资股东决定成立安全领导小组关于成立临时党支部关于注销分公司决定 了在搜0 索过程中知识的利用和探索两者的权重。在搜索过程中，蚂蚁将以概 ,,a率选择具有最大的值的工序;与此对应，蚂蚁将q[()][()],,tt,kP,0rkrkr 返利购(hi369.com)-你来购物，我来返利～铁路免费资源尽在铁路吧(www.tielu8.cn) 返利购(hi369.com)-你来购物，我来返利～铁路免费资源尽在铁路吧(www.tielu8.cn) 以概率进行随机搜索，扩大解的寻优范围，在这种情况下，当前1,q0 a'位于作业r的蚂蚁将以概率选择作业工序。 pt()s'rs a选择概率的计算方法为: pt()'rs ,,,[()][()],,tt,''rsrs'a,,,sp,,ra([()][()])tt,,,,rkrk(11) pt(),',ars,kpr,否则,0, '(1)表示第步，弧上的信息素数量，它代表列车作业,()t(,)rst'rs 'r在处理序列中紧接着作业后的期望程度。 s (2)表示第步，问题的启发式信息值。启发式信息对于蚁,()tt'rs 群算法的快速收敛有着重要的指导作用。本文采用列车运行正点度和 zc行程完成度的加权值作为启发式信息，记做:。 ,,,()tee,，'''zcrsrsrs z其中，，表示列车运行正点程度， qc和QCeTqcQCT,,,[()]/'''''''''ddjkjkrsjkjk 'kmcpp分别表示工序的实际完成时间和图定完成时间。，表示ett,/''''',,rsjkjk'',,11kk p'列车的行程完成度，表示列车在第个区间的纯运行时分。，t,,，,1k''zcjk ，为两指标的权重，通常情况下，不同种类的列车对两指标,,,[0,1],zc 的侧重不同，旅客列车倾向于恢复按图行车，货物列车更希望能够加速运行，可以根据不同的需要而设定。 (3)代表信息素启发式因子，它反映蚂蚁在寻优过程中所积, 累的信息量在指导蚁群搜索中的相对重要程度，其取值大小体现了蚁群在路径搜索过程中随机性因素作用的强度;代表期望值启发式因, 子，反映蚂蚁在寻优过程中启发信息在指导蚁群搜索中的相对重要程度，其取值体现了蚁群在路径搜索过程中先验性因素作用的强度。 ar(4)表示位于作业处的蚂蚁的候选列车作业集合。 par 返利购(hi369.com)-你来购物，我来返利～铁路免费资源尽在铁路吧(www.tielu8.cn) 返利购(hi369.com)-你来购物，我来返利～铁路免费资源尽在铁路吧(www.tielu8.cn) 2.3蚁群算法信息素的更新规则 蚂蚁之间通过信息素传递寻优信息，共同完成求解过程。本文为了强化循环最优解的信息强度，使问题迅速收敛到最优解，规定只有当次迭代的最优解具有更新信息素的资格，并且利用当次迭代最优解的评价函数值来更新信息素。在此基础上还采取了对每次循环的最差解进行惩罚，弱化最差解的路径信息的策略，使求解过程避开较差解 [10]的干扰。 信息素更新规则如下: (12) ,,,,()(1)()()ttttt，,,,，,，,rsrsrs Qt(),迭代最优解ib,fso(),(13) ,,，,,()tt,rs'Qt(),,迭代最差解ib,fso(), 式中: 表示信息素的消逝程度，就表示信息素的残留系数。 ,1,, ib代表蚁群本次迭代的最优解。 so 表示评价函数。在这里采用式(1)的模型目标函数作为评价f(), 函数。 表示信息素强度，表征蚂蚁所留信息素数量的一个常量，随着Q 迭代次数的增加，仍然采用较高的信息素强度，容易使算法集中到Q 几个信息素强度高的解上，使算法陷入局部最优解，产生停滞。采用阶跃函数Qt()来代替常数值，随着迭代步数的增加适当减少增加的Q 信息素强度，从而避免陷入局部最优解。 '是与Qt()相对应的惩罚因子，对迭代过程中的最差解进行惩Qt() 返利购(hi369.com)-你来购物，我来返利～铁路免费资源尽在铁路吧(www.tielu8.cn) 返利购(hi369.com)-你来购物，我来返利～铁路免费资源尽在铁路吧(www.tielu8.cn) 罚。 2.4 蚁群算法求解列车运行调整问题的详细步骤 rstep1 初始化列车的调度工序列表，并构造图; Vv,{}Gik step2 将图中各路径的信息素浓度初始值设为1; step3 构建初始调度作业集合，并根据算法规定数量放置蚂蚁; step4 计算蚂蚁在当前调度时刻各可行节点与蚂蚁所在节点的信息素浓度和启发式信息值，按照规则(10)选择下一调度工序节点; step5 如果蚂蚁已经遍历所有工序，得到工序的一个排列，则转6，否则转4; step6 按照(2)-(9)的约束条件，将得到的工序节点序列铺画成列车运行曲线，并对其进行评价。 step7 找出本次迭代中最优解(评价值最高的解)，并按照式(12)对最优解路径进行信息素更新。 step8 根据迭代步数调整的值; Q step9 判断是否达到迭代次数或结束条件，如果是则输出结果，否则转3; 3 求解实例 利用蚁群算法对某双线铁路区段共9个区间的列车运行调整问题进行了建模求解。调整时间范围内共有列车14列，分解为工序126个。人工蚂蚁20个。，均取为1，q,0.7，迭代200次，得,,0.05,,,0 到问题的优化解，收敛过程如果图4所示。仿真结果表明:基于蚁群算法的列车运行调整问题的求解算法，可以有效的缩短制定列车运行返利购(hi369.com)-你来购物，我来返利～铁路免费资源尽在铁路吧(www.tielu8.cn) 返利购(hi369.com)-你来购物，我来返利～铁路免费资源尽在铁路吧(www.tielu8.cn) 调整计划的时间，减少列车运行延误影响，从而实现降低列车调度员劳动强度的目的。 图4:算法收敛图 4 结论 本文将列车运行调整问题看作制造系统中的工序调度问题，建立了列车运行调整问题的优化模型，并利用蚁群算法对模型进行了求 解，通过仿真实例验证了算法的可行性。研究表明蚁群算法的并行搜索能力，对解决列车运行调整等一类解空间大、约束条件多的大规模复杂问题有着很好的适用性和可操作性。但是，由于蚁群算法涉及的参数较多，如何确定一组合适的参数，目前还无理论依据，仍要根据实际调度问题确定，还需要做进一步的深入研究。 参考文献 [1]Araya S, Abe K, Fukumori K 1983. An optimal rescheduling for online train traffic control in disturbed situation[C].Proc.22nd IEEE Conf.Decision and Control. IEEE, New York,pp.489-494. 返利购(hi369.com)-你来购物，我来返利～铁路免费资源尽在铁路吧(www.tielu8.cn) 返利购(hi369.com)-你来购物，我来返利～铁路免费资源尽在铁路吧(www.tielu8.cn) [2]H.Schafer, S.Pferdmenges. An expert system for real-time train dispatching[C]. In: Proceeding of the COMPRAIL’94 in Madrid computational mechanics publication. Southanmpton, England. Pp:27-34. [3]周磊山，秦作睿(列车运行计划与调整的通用算法及其计算机实 现[J](铁道学报，1994，16(3):56-65. [4]董守清，王进勇，闫海峰.双线铁路列车运行调整的禁忌搜索算法 [J].中国铁道科学.2005,26(4):114-119. [5]金福才，胡思继. 列车运行调整的无延迟调度算法研究[J].铁道 学报，2003，25(2):10-14. [6]Dorigo M，Meniezzo Vittorio，Colomi Alberto(The Ant System: Optimization by a colony of cooperating agents[J](IEEE Transactions on Systems，Man，and Cybernetics—Part B，1996， 26(1):l-13( [7]Dorigo M，Gambardelta L M(Ant Colony System:A Cooperative Learning Approach to the Traveling Salesman Problem [J](IEEE Transactions on Evolutionary Computation，1997， 1(1):53-66( [8]王颖，谢剑英.一种自适应蚁群算法及其仿真研究[J].系统仿真学 报，2002，14(1):31-33. [9]刘志刚，李言，李淑娟.基于蚁群算法的Job-Shop多资源约束车 间作业调度[J].系统仿真学报，2007，19(1):216-220. 返利购(hi369.com)-你来购物，我来返利～铁路免费资源尽在铁路吧(www.tielu8.cn) 返利购(hi369.com)-你来购物，我来返利～铁路免费资源尽在铁路吧(www.tielu8.cn) [10] 王常青，操云甫，戴国忠.用双向收敛蚁群算法解作业车间调 度问题[J].计算机集成制造系统，2004，10(7):820-824. 返利购(hi369.com)-你来购物，我来返利～铁路免费资源尽在铁路吧(www.tielu8.cn)