论文部分内容阅读
摘要：本文阐述了货物列车编组计划的复杂性，引入多Agent技术，建立了基于多Agent的编组计划优化模型，并重点讲述了Agent之间的交互机制以及车流合并过程，最后指出了该方法的优越之处，对于列车编组计划智能化编制具有借鉴作用。
关键词：编组计划；多Agent系统；协商机制
中图分类号：U292.3文献标识码：A文章编号：1002-3100(2007)04-0132-02
Abstract: This paper explains the complexity of making freight train formation plan, brings in the multi-agent technology and founds the optimizing model of train formation plan based on multi-agent. Afterwards it gives the collaboration mechanism as well as the process of distribution. At last, it points out the superiority of this method, which can be used for references for intelligent making freight train formation plan.
Key words: train formation plan; multi-agent system; collaboration mechanism
在铁路运输组织中，制定列车编组计划是基础性工作，是确定各支车流的运送途径和中转方式的过程，其优劣程度直接影响铁路设备的利用率及运输成本。近年来，国内外学者对于列车编组计划与车流组织优化的研究主要集中在数学模型的建立和求解方面，比较有代表性的有：0—1规划法[1]、二次0—1规划法[2]以及几种网络优化模型[3-5]；在模型的求解方面比较成功的是模拟退火算法[6]。但是由于该问题还涉及车辆走行里程、运输成本、车站能力与区段通过能力等众多因素，因此，在其建模过程中需进行一定的简化，造成理论研究同实际情况存在着距离。此外在路网规模庞大，车流数目众多的情况下，其在模型的求解上也相当复杂，存在着一定的难度。
列车编组计划的优化是一个十分复杂的问题，具有：（1）复杂性，车流之间相互耦合，某支车流改编方式的变动可能引起其他车流也发生变化；（2）不确定性，车流的组合形式是不确定的；（3）分布性，各支车流是分散的。对于这类问题的求解，目前人工智能领域兴起的多Agent方法[7]有较大优势。
此外，列车编制组计划的编制过程可看作为资源分配相应任务的过程，其中，每支车流看作需要完成的一种类型的任务量，而车站和区段看作为完成任务的资源，则列车编组计划转化为一个任务分配的问题，而目前多Agent在车间的任务分配得到了很好的应用，因此，本文将Agent引入列车编组计划的优化中，借助Agent的自主性、智能性、主动性以及交互性，将每个任务分配给合理的资源，提高铁路设备的利用率。
1基于多Agent的列车编组计划优化模型
1.1模型的创建。列车编制计划的优化主要涉及的实体为车流、车站以及区段，其整个过程实质上是为各支车流选取适当的车站和区段组织货物运输的过程。如上面所说，可以将该问题转化为任务分配过程来求解，车流寻找路径的过程看作需要完成的任务，而路网中的所有车站和区段看作资源，则每支车流的运送路径由相应进行作业的车站和区段组成。分别为每个任务和资源都各设置一个Agent作为代理，通过它们之间直接或间接的交互来为每个资源分配任务。基于多Agent的编组计划优化模型如图，包括：（1）负责与人交互的交互Agent；（2）资源Agent，映射车站和区段实体，负责监测发来的任务是否超出了能力限制；（3）任务Agent，映射车流实体，负责与其它的任务Agent交互，寻找合适的合并对象；（4）管理Agent，用来进行冲突处理；最后还有两个数据库分别为路网数据库和编组去向库。其中，路网数据库主要存放路网信息，从车流角度来说，存放的是各支车流的所有径路；编组去向数据库存放车流选定的所有编组去向信息，是由任务Agent不断写入以及删除的。
1.2Agent之间的交互机制。列车编组计划的优化中主要的交互是车流与车流之间的相互作用，在此本文借用招商机制来实现它们之间的合并问题。当某支车流或合并车流达到直达运送的绝对条件时，发布公告，成为已定招商者；而当其每站改编的车小时节省大于等于0.8cm时，也发布公告，成为暂定招商者，其他车流为投资者，不断检测公告中是否存在与其有部分相同路径，然后计算投资的效益来决定是否投资。当一轮投资完后，各暂定招商者判断合并车流是否满足绝对条件，若满足转为已定招商者，反之招商失败，还原所有车流的状态；对于已定招商者，要计算判断其内部的合并车流对其始发或终到站是否满足绝对条件，从而延长其始发或终到站。
1.3运作过程以及招商机制。由于技术站的车流合并过程比较复杂，因此本文只针对技术站的招商过程加以介紹。在车流与车流的交互合并过程中，存在某站的改编任务超过其能力的可能性，需管理Agent来仲裁处理。整个运作步骤如下：
初始状态：每支车流为一个直达去向。
（1）每支车流Agent对其所有的可行径路进行计算判断，若满足绝对条件Nt节最小≥cm，将其定为直达去向转为已定状态；若满足条件Nt节最小≥0.8cm，暂时将其定为直达去向转为暂定状态；若都不满足保持初始状态，计算有没有一站节省Nt节≥cm，如果存在则标记不应该在该站截流。
（2）直达车流Agent发布其直达的消息，其他车流Agent读到所有消息后计算其收益，若收益为正并且相对于直达车流或车流组合只须进行一次改编，则该Agent向相应的车流Agent发送同意投资的消息，并转为与对应的招商者相同的状态，否则不进行投资。若存在多种可投资的方案，选取可获得收益最大的投资。
（3）各直达车流Agent收到所有投资消息后，作进一步检查，对于暂定状态的直达车流，再次判断合并后车流是否满足绝对条件，若满足将所包含的车流转为已定状态；若不满足，回复所有对其投资的车流，表示此直达去向已失效，其他车流收到后恢复初始状态。
（4）检测已定状态中的所有直达去向，判断合并车流后对于其始发和终到站是否满足绝对条件，若满足，延长相应车流的始发或终到站，并处理对其他车流的影响，计算延长前后所有车流的消耗，取消耗最少的方案。将所有已定状态的车流所标记的不该截流站取消。
（5）车站Agent检测其改编任务是否超出其改编能力后，若否，转到6；若是，则向管理Agent发送报告，由管理Agent按如下步骤进行调整。
选取其他的有直达车流始发和终到且剩余改编能力较大的车站，将一部分改编作业转到该站；若该站存在始发或终到的直达车流，将可投资该直达车流的车流在超负荷车站的改编转为在该站改编，合并相同径路的车流，按照上述（2）、（3）、（4）、（5）步骤进行招商处理；若不存在直达车流，试着将在超负荷车站的某些改编作业转移到该站，按照上述（2）、（3）、（4）、（5）步骤进行招商处理，通过计算其对整体车小时消耗的影响，取车小时消耗相对较少的方案。
（6）若路网中各站车流合并不满足绝对条件或各部分车站个数≤4，则转到（8），并将不满足必要条件的直达去向取消；反之，车站管理Agent设置截流点，其原则为：直达已定状态中，若存在可衔接的去向且其衔接站的t节不大于短路网上其他站的，且其改编能力较大，则选取该衔接站；如果不存在，选取处于路网中部的直达去向的始发或到达站的t节不大于其他各站的，且改编能力较大的站；若都不满足，选取处于路网中起全部通过车流不满足充分条件且其改编能力相对较大的车站；若不存在，选择靠近路网中部的站，且其t节不大于其他各站的，改编能力较大的。
（7）将所有初始车流以及暂定状态的直达以及非直达车流在截流点分为左右两部分。两部分可以按照上述步骤1、2、3、4、5再进行计算。
（8）取消初始状态中不满足必要条件的直达车流，编入区段列车，输出所有结果。
2结论
论文首次将多Agent技术引用到列车編组计划的优化过程中：将车流送达目的地过程看作要完成的任务，并设置一个Agent为其寻找合适的径路；将每个车站和区段看作资源，也设置一个Agent，用来组成路网，供各任务Agent分配其任务。在优化过程中，各任务Agent在路网条件下通过间接交互寻求自身利益最大的同时由管理Agent仲裁管理从而求得总体的满意解。此外，每一个任务Agent映射一支车流实体，使其具有自主性和智能性，将以前专家才具有的经验知识分布到各支车流中，由各支车流主动地在路网中寻找合适的运输路径，体现了运算的分布性。但是，目前提出的还仅仅是一个模型，以后还需要进一步做深入细致的研究，包括各个Agent需要具备的知识表达、Agent之间的协作规则、冲突处理等，才能实现整个列车编组计划的优化。
参考文献：
[1] 曹家明，朱松年. 优化列车编组计划的0—1规划法[J]. 铁道学报，1992,14(4):49-57.
[2] 曹家明，朱松年. 铁路网上技术直达列车编组计划优化的二次0—1规划法[J]. 铁道学报，1993,15(2):62-70.
[3] 史峰，李致中，孙焰,等. 列车编组计划网络优化方法[J]. 铁道学报，1994,16(2):74-79.
[4] 林柏梁，朱松年. 路网上车流径路与列车编组计划的整体优化[J]. 铁道学报，1996,18(1):1-7.
[5] 李映红，吴世贵，彭其渊. 货物列车编组计划网络模型的建立及算法[J]. 西南交通大学学报，2002,97(1):68-71.
[6] 林柏梁，朱松年. 优化编组计划的非线性0—1规划模型及模拟退火算法[J]. 铁道学报，1994,16(2):61-66.
[7] 张洁，高亮，李培根. 多Agent技术在先进知道中的应用[M]. 北京：科学出版社，2004.
[8] 李英. 多Agent系统以及其在预测与智能交通系统中的应用[M]. 上海：华东理工大学出版社，2004.
关键词：编组计划；多Agent系统；协商机制
中图分类号：U292.3文献标识码：A文章编号：1002-3100(2007)04-0132-02
Abstract: This paper explains the complexity of making freight train formation plan, brings in the multi-agent technology and founds the optimizing model of train formation plan based on multi-agent. Afterwards it gives the collaboration mechanism as well as the process of distribution. At last, it points out the superiority of this method, which can be used for references for intelligent making freight train formation plan.
Key words: train formation plan; multi-agent system; collaboration mechanism
在铁路运输组织中，制定列车编组计划是基础性工作，是确定各支车流的运送途径和中转方式的过程，其优劣程度直接影响铁路设备的利用率及运输成本。近年来，国内外学者对于列车编组计划与车流组织优化的研究主要集中在数学模型的建立和求解方面，比较有代表性的有：0—1规划法[1]、二次0—1规划法[2]以及几种网络优化模型[3-5]；在模型的求解方面比较成功的是模拟退火算法[6]。但是由于该问题还涉及车辆走行里程、运输成本、车站能力与区段通过能力等众多因素，因此，在其建模过程中需进行一定的简化，造成理论研究同实际情况存在着距离。此外在路网规模庞大，车流数目众多的情况下，其在模型的求解上也相当复杂，存在着一定的难度。
列车编组计划的优化是一个十分复杂的问题，具有：（1）复杂性，车流之间相互耦合，某支车流改编方式的变动可能引起其他车流也发生变化；（2）不确定性，车流的组合形式是不确定的；（3）分布性，各支车流是分散的。对于这类问题的求解，目前人工智能领域兴起的多Agent方法[7]有较大优势。
此外，列车编制组计划的编制过程可看作为资源分配相应任务的过程，其中，每支车流看作需要完成的一种类型的任务量，而车站和区段看作为完成任务的资源，则列车编组计划转化为一个任务分配的问题，而目前多Agent在车间的任务分配得到了很好的应用，因此，本文将Agent引入列车编组计划的优化中，借助Agent的自主性、智能性、主动性以及交互性，将每个任务分配给合理的资源，提高铁路设备的利用率。
1基于多Agent的列车编组计划优化模型
1.1模型的创建。列车编制计划的优化主要涉及的实体为车流、车站以及区段，其整个过程实质上是为各支车流选取适当的车站和区段组织货物运输的过程。如上面所说，可以将该问题转化为任务分配过程来求解，车流寻找路径的过程看作需要完成的任务，而路网中的所有车站和区段看作资源，则每支车流的运送路径由相应进行作业的车站和区段组成。分别为每个任务和资源都各设置一个Agent作为代理，通过它们之间直接或间接的交互来为每个资源分配任务。基于多Agent的编组计划优化模型如图，包括：（1）负责与人交互的交互Agent；（2）资源Agent，映射车站和区段实体，负责监测发来的任务是否超出了能力限制；（3）任务Agent，映射车流实体，负责与其它的任务Agent交互，寻找合适的合并对象；（4）管理Agent，用来进行冲突处理；最后还有两个数据库分别为路网数据库和编组去向库。其中，路网数据库主要存放路网信息，从车流角度来说，存放的是各支车流的所有径路；编组去向数据库存放车流选定的所有编组去向信息，是由任务Agent不断写入以及删除的。
1.2Agent之间的交互机制。列车编组计划的优化中主要的交互是车流与车流之间的相互作用，在此本文借用招商机制来实现它们之间的合并问题。当某支车流或合并车流达到直达运送的绝对条件时，发布公告，成为已定招商者；而当其每站改编的车小时节省大于等于0.8cm时，也发布公告，成为暂定招商者，其他车流为投资者，不断检测公告中是否存在与其有部分相同路径，然后计算投资的效益来决定是否投资。当一轮投资完后，各暂定招商者判断合并车流是否满足绝对条件，若满足转为已定招商者，反之招商失败，还原所有车流的状态；对于已定招商者，要计算判断其内部的合并车流对其始发或终到站是否满足绝对条件，从而延长其始发或终到站。
1.3运作过程以及招商机制。由于技术站的车流合并过程比较复杂，因此本文只针对技术站的招商过程加以介紹。在车流与车流的交互合并过程中，存在某站的改编任务超过其能力的可能性，需管理Agent来仲裁处理。整个运作步骤如下：
初始状态：每支车流为一个直达去向。
（1）每支车流Agent对其所有的可行径路进行计算判断，若满足绝对条件Nt节最小≥cm，将其定为直达去向转为已定状态；若满足条件Nt节最小≥0.8cm，暂时将其定为直达去向转为暂定状态；若都不满足保持初始状态，计算有没有一站节省Nt节≥cm，如果存在则标记不应该在该站截流。
（2）直达车流Agent发布其直达的消息，其他车流Agent读到所有消息后计算其收益，若收益为正并且相对于直达车流或车流组合只须进行一次改编，则该Agent向相应的车流Agent发送同意投资的消息，并转为与对应的招商者相同的状态，否则不进行投资。若存在多种可投资的方案，选取可获得收益最大的投资。
（3）各直达车流Agent收到所有投资消息后，作进一步检查，对于暂定状态的直达车流，再次判断合并后车流是否满足绝对条件，若满足将所包含的车流转为已定状态；若不满足，回复所有对其投资的车流，表示此直达去向已失效，其他车流收到后恢复初始状态。
（4）检测已定状态中的所有直达去向，判断合并车流后对于其始发和终到站是否满足绝对条件，若满足，延长相应车流的始发或终到站，并处理对其他车流的影响，计算延长前后所有车流的消耗，取消耗最少的方案。将所有已定状态的车流所标记的不该截流站取消。
（5）车站Agent检测其改编任务是否超出其改编能力后，若否，转到6；若是，则向管理Agent发送报告，由管理Agent按如下步骤进行调整。
选取其他的有直达车流始发和终到且剩余改编能力较大的车站，将一部分改编作业转到该站；若该站存在始发或终到的直达车流，将可投资该直达车流的车流在超负荷车站的改编转为在该站改编，合并相同径路的车流，按照上述（2）、（3）、（4）、（5）步骤进行招商处理；若不存在直达车流，试着将在超负荷车站的某些改编作业转移到该站，按照上述（2）、（3）、（4）、（5）步骤进行招商处理，通过计算其对整体车小时消耗的影响，取车小时消耗相对较少的方案。
（6）若路网中各站车流合并不满足绝对条件或各部分车站个数≤4，则转到（8），并将不满足必要条件的直达去向取消；反之，车站管理Agent设置截流点，其原则为：直达已定状态中，若存在可衔接的去向且其衔接站的t节不大于短路网上其他站的，且其改编能力较大，则选取该衔接站；如果不存在，选取处于路网中部的直达去向的始发或到达站的t节不大于其他各站的，且改编能力较大的站；若都不满足，选取处于路网中起全部通过车流不满足充分条件且其改编能力相对较大的车站；若不存在，选择靠近路网中部的站，且其t节不大于其他各站的，改编能力较大的。
（7）将所有初始车流以及暂定状态的直达以及非直达车流在截流点分为左右两部分。两部分可以按照上述步骤1、2、3、4、5再进行计算。
（8）取消初始状态中不满足必要条件的直达车流，编入区段列车，输出所有结果。
2结论
论文首次将多Agent技术引用到列车編组计划的优化过程中：将车流送达目的地过程看作要完成的任务，并设置一个Agent为其寻找合适的径路；将每个车站和区段看作资源，也设置一个Agent，用来组成路网，供各任务Agent分配其任务。在优化过程中，各任务Agent在路网条件下通过间接交互寻求自身利益最大的同时由管理Agent仲裁管理从而求得总体的满意解。此外，每一个任务Agent映射一支车流实体，使其具有自主性和智能性，将以前专家才具有的经验知识分布到各支车流中，由各支车流主动地在路网中寻找合适的运输路径，体现了运算的分布性。但是，目前提出的还仅仅是一个模型，以后还需要进一步做深入细致的研究，包括各个Agent需要具备的知识表达、Agent之间的协作规则、冲突处理等，才能实现整个列车编组计划的优化。
参考文献：
[1] 曹家明，朱松年. 优化列车编组计划的0—1规划法[J]. 铁道学报，1992,14(4):49-57.
[2] 曹家明，朱松年. 铁路网上技术直达列车编组计划优化的二次0—1规划法[J]. 铁道学报，1993,15(2):62-70.
[3] 史峰，李致中，孙焰,等. 列车编组计划网络优化方法[J]. 铁道学报，1994,16(2):74-79.
[4] 林柏梁，朱松年. 路网上车流径路与列车编组计划的整体优化[J]. 铁道学报，1996,18(1):1-7.
[5] 李映红，吴世贵，彭其渊. 货物列车编组计划网络模型的建立及算法[J]. 西南交通大学学报，2002,97(1):68-71.
[6] 林柏梁，朱松年. 优化编组计划的非线性0—1规划模型及模拟退火算法[J]. 铁道学报，1994,16(2):61-66.
[7] 张洁，高亮，李培根. 多Agent技术在先进知道中的应用[M]. 北京：科学出版社，2004.
[8] 李英. 多Agent系统以及其在预测与智能交通系统中的应用[M]. 上海：华东理工大学出版社，2004.