TFP优化模型与算法介绍.ppt

现代交通流组织的理论与方法，闫海峰，2008年2月23日，教学安排，主要内容，现代交通流组织的内容，研究进展，交通流组织的基本原理和方法，聚集过程的随机描述，TFP模型，传统TFP算法介绍，遗传算法，马修斯定理介绍，铁路空车调整的模型和算法，有序组合树算法介绍，课时安排，教学22小时，自学33548小时(课外)教学36小时复习2小时，回答2小时，灵活2小时，考试方法，课堂讨论10%，教学20%，期末开卷考试70%，参考文献，彭启元，严海峰，魏德勇。 集装箱列车运输组织。成都：四川科学技术出版社，2005。李志忠、石峰、孙艳、胡建华。数学方法在铁路运输管理中的应用M。北京：中国铁路出版社，1995。孙艳、李志忠、史风。铁路运输管理的数学模型和算法，M .武汉：华中科技大学出版社，1995。曹奎久、孔。货运列车编组计划。北京：中国铁路出版社。1992.曹奎久。列车编组计划。北京：人民铁路出版社，1964年。又名比伦卡。刘等译。铁路运输技术直达列车。北京：人民铁路出版社，1959年。又名比伦卡。王：译。编组列车M。北京：人民铁路出版社，1956年。期刊论文，学术论文研究报告，概述和基本原则，第一部分。交通流组织的内容、交通流路径(计划)、列车编组计划(计划)、装载地点、直达列车技术站、直达列车区段、管内列车运行计划、交通流调整和计算(日常)其他事项：交通流确定、编组站.优化问题：交通流路径选择、装载地点、直达列车编组计划、技术直达列车编组计划、直达列车编组计划的核心问题、列车编组计划、技术站间直达列车编组计划、交通流组织的研究进展，发展初期，50是发展的高潮.货运列车编组计划的功能是分析绝对计算法的复杂性和复杂性，货运列车编组计划的功能是将交通流转化为列车流的全路组织计划，为全路技术站合理分配调车(解编)工作量，明确列车通过技术站的运行内容。 规定了列车的重量，列车运行图的编制为调整线路各区段的列车体积、各列车的运行路线、列车的起止、列车的等级、列车沿线的技术运行停靠点以及一些特殊列车(列车)的具体情况提供了依据。 交通流的原则是不会中断的。同一方向的某一交通流的任何部分必须与其他部分(或全部)具有相同的交通流路线。到达同一目的地的特定业务流的任何部分必须具有与其他部分相同的适应计划。到达同一目的地的特定交通流的任何部分必须以与其他部分相同的列车形式(类型、等级和性质)运输。具有相同目的地的特定交通流具有相同的确定OD(不同于货物的OD)。相关参数、计划交通流、繁忙交通流、空交通流路径、特殊列车编号、列车发车装配时间、特殊装配参数、卡车平均装配时间、不适于通过技术站的卡车节省的时间、不适于通过技术站的卡车节省的时间， ty=tdtctftwtj=tytwTC到达时间td中转时间tc出发时间t各种等待时间t非管制中转时间t管制中转时间t非管制中转时间tj由技术站保存，相关条件，基本条件(单独运行直达列车的基本条件)三个条件，必要条件，基本条件，充分条件，绝对条件，简单方法，绝对计算方法实质上，枚举法表格计算方法不计算相邻技术站之间的直达列车，而是以表格的形式计算和处理所有筛选方案。本质上，枚举法肯定能获得最优解。表格分析方法不一定能通过在三种条件下的分析和比较获得最优解。本质上，贪婪算法和无终止判断的随机优化就是优化。问题的复杂性和算法的复杂性，算法的复杂性是指解决问题的特定算法的执行时间，这是算法的本质。问题的复杂性指的是解决该问题的所有算法中最佳算法的复杂性。这是问题本身的复杂性和问题的本质。它不能通过枚举来获得，一般是预先估计，然后在理论上证明。决定性问题只需要回答是或否。任何一般的优化问题都可以转化为一系列确定性问题。可在多项式时间内解决的确定性问题属于P类问题。P类问题是一组多项式时间复杂度的问题。非确定性问题：这种能在多项式时间内检验一个解是否正确的问题称为NP问题。所有的p类问题都属于NP问题，但是p=nporpnp？NPC问题中最困难的问题每个NPC问题都可以在多项式时间内转化为任何一个NP问题。如果NPC问题有多项式时间算法，那么所有的NP问题都可以在多项式时间内解决，即P=NP成立。只有在解空间中的所有解都用尽之后，才能得到最优解。NP-Hard问题比任何其他NP问题都难。不一定是NP问题，不是NPC。如果一个NP-Hard问题可以分成若干个年度角度，那么在利用现有算法进行分解之后，可以为每个部分找到最优解，并且通过组合这些最优解，可以在很长时间内获得该问题的近似最优解。TFP问题是一类NP-Hard问题，其最简单的子类线性0-1规划也是一个NP-Hard问题。从数学模型出发，任何0-1线性规划问题都可以在多项式时间范围内归结为背包问题。这已被证明是一个NP难问题。原有的经典优化算法(如动态规划、枚举法、分解算法、分枝定界法等。)用于寻找最优解。算法的时间复杂度呈指数增长，算法固有的维数灾难无法避免。TFP问题发现算法的意义在于利用问题结构的特殊性，所构造的算法能有效地解决一定规模下的问题，如单纯形法求解线性规划问题、交通流路径和空车调整优化问题，第二部分，主要内容， 空车流量调整技术站间直达列车编组计划(车流组织优化)空车调整及车流路径整体优化重型空车流量路径及空车调整的整体优化，货车装配过程的随机描述，第3部分，装配参数的主要内容、意义前期研究及结论随机点过程介绍车流到达过程的计算公式推导描述装配时间消耗，全要素生产率优化模型及算法介绍，第4、1部分。 中国全要素生产率优化模型的特征分析。国内对全要素生产率的研究始于20世纪50年代，中间有断层。1978年后发表了大量的研究工作。其中，比较著名的有：混合整数规划模型线性0-1规划模型二次0-1规划模型总体优化模型有利目标模型，1.1混合整数规划模型M1，该模型的变量数和约束数都比较少。然而，没有特殊的性质足以提供有效的解决方案。它只能作为一般的混合整数规划模型，用传统的分支边界法和截平面法求解。可以求解的模型规模非常有限。1.2线性0-1规划模型M2，线性0-1规划模型中的约束可分为三组：第一组为每个交通流建立线性紧约束，描述相应的交通流在出发站并入哪个到达列车；根据合并出发站的原则，为具有相同出发站和公共运输路径的每两个车辆建立第二组约束。第三组约束是根据“到达合并原则”为每两辆到达相同且运行路径相同的车辆建立的。其目标函数在计算交通流的重复适应度时增加了一个项，从而补充了混合整数规划模型中整数变量所描述的函数。与以前的模型相比，约束的数量是相同的，但是变量的数量略有增加，并且其规模要小得多。根据模型结构的一些性质，可以用有序组合树方法来解决这个问题。然而，随着模型本身中不等式约束数量的增加，需要引入大量冗余变量和松弛变量，模型中变量较少的优势将被完全抵消。在构造决策变量的过程中，1.3二次0-1规划模型M3用其他变量的组合来代替一些变量，以减少变量的数量。该模型的约束是等式约束，每个交通流只对应一个约束条件，不仅减少了约束的数量，而且每个约束之间没有交集。约束条件的系数矩阵和增广矩阵中的元素也是0或1。目标函数包含二次项，每个二次项是适应变量和直接变量的乘积。该模型可以将目标函数分解成几个互不影响的子程序，然后求解它们。这可以大大降低解的计算复杂度，但只能保证局部优化而不是全局优化。由于模型是非线性规划，现有的比较成熟的线性规划算法不能完全适应模型的求解。在过去的全要素生产率模型中，不同交通流之间的路径及其关系被视为固定参数。如果考虑到适应消耗(时间和成本)，路线的选择可能会改变。路线和编组计划的优化问题是相互条件和相互参数的。两者应该一起优化。在此基础上，建立了总体优化模型。该模型的主要特点是：在网络结构中建立了交通流路径优化模型，同时解决了交通流路径优化问题。交通流路线的选择，可怕虽然交通流路径和交通流规划的整体优化模型在理论上是比较完整和全面的，但它将以往研究中的三个独立问题统一为一个模型，也可以解决复杂路网结构引起的路径选择优化问题。然而，由于模型的超大规模和非线性，它仍然不适用于实际的路网。1.5全要素生产率的其他优化模型、网络优化模型、受益目的地模型、阶跃函数模型、高阶0-1规划模型、特征：它们都为交通流组织的某一方面的研究得出了重要结论。二者都具有高阶非线性色散的特性，这使得这类问题具有更高的复杂性。对于非线性离散规划问题，即使最简单的子类无约束二次0-1规划问题也是NP完全的。1.6简化线性0-1规划模型M41.6.1交通流合并假设：对于不同始发地和目的地的集装箱流，当运输过程中需要中转时，必须将其与其他相应的集装箱流合并，并运输到下一个相同的节点站。合并情况如下：两个集装箱流的起点站相同，一个集装箱流的终点站与另一个集装箱流的第一转运站相同；(2)两个箱流具有相同的起始站和相同的第一转运站；(3)两个罐流具有相同的转运站，并且一个罐流的最终到达与另一个罐流的下一个相邻转运站相同；(4)两个罐流具有相同的转运站，且一个罐流的起始站与另一个罐流的相邻前一个转运站相同；(5)一个箱流的起点和终点与另一个箱流的两个相邻转运站相同；两个槽流具有相同的两个相邻的转运站；两个箱流到达同一个站，并有同一个转运站。两个箱流的终端站相同，一个箱流的起点站与另一个箱流的转运站相同。1.6.2交通流合并相关定理，定理1某一交通流的路径可以唯一地表示为有序集合，该有序集合中的元素是包含在交通流路径中的操作站，其顺序是通过每个操作站的交通流的顺序，即路径方向。推论1如果两个不同的业务流通过沿途两个相同的站点，并且这两个站点对于这两个业务流具有相同的顺序，那么这两个站点之间的路径必须是相同的。定理2如果需要传输和适应长距离的箱型流，它必须与同一个交通流一起以与操作站相同的方向传输。推论2长途集装箱流必须与内部交通流aik和akj一起运输，当它仅在沿途的K站被转移和调整时。推论3当长途集装箱流仅在包括在联合执行活动中的站点被转移和调整时，联合执行活动必须与其内部交通流一起运输。定理3长途箱式流aij仅在沿途的K站转移和调整的必要条件是aik和akj的两个分支必须运行直达列车。定理4长途箱型流aij要转移到Aij中包含的车站并从这些车站改编的必要条件是，其所有内部交通流必须在直达列车中。1.6.3决策变量的定义，1.6.4目标函数，1.6.5约束条件，运行计划的唯一性，交通流转移和适应的必要条件(第二组)是为一个站设置的适应变量；(三)为多站适应变量设置组；(二)组内约束数为2；(三)集团内约束的数量是多少；每个约束条件中变量的系数都是1，并且都是等式约束。在每组约束中，在相同的顺序不相等之后，每个约束的右边变量是相同的，即对应于该组约束的单站自适应变量或多站自适应变量。变量值约束的合理性，1.6.6模型，M4非常类似于M2，除了M2比M4有更多的约束条件来合并相同的到达流量。这组约束的一般形式是可以证明的。在M4中，这种约束可以由其他约束来表达或隐含在其他约束中。因此，M4和M2是平等的没有定义零流量，即相应的变量从模型中排除。该模型大大简化，但解空间将减少，最优解可能丢失。零流量是专门定义和处理的。如果零流量不是任何交通流的内部流量，则可以在不定义任何相应变量的情况下将其从模型中排除。否则，只需要定义对应于零流量的直接变量。1.6.8模型特征，每个非零交通流对应一组约束。其中，类型(I)约束是等式约束，并且每个业务流不会相互交叉。类别(二)和(三)的约束是不等式约束，它们相互交叉，不能完全分解。每个非零业务流定义一组独立变量，每个变量代表业务流的唯一单向适应方案或直接方案。并且每个适应变量对应于类别(二)或(三)约束。该模型显然是一个线性0-1规划问题。它与旅行商问题、背包问题、集合覆盖问题、顶点着色问题等有相似的特点。而且都属于NPC问题。与M3的模型相比，M4引入了类别(二)和(三)的约束，并消除了目标函数的二次项。然而，其他变量不能被变量的组合所代替，这比M3的变量和约束的数量还要多。模型M4相当于M2，它简化了到达车站的相同交通流的合并约束。1.6.9模型尺寸估计，对于n个节点的简化网络，约束条件的上限中的每个决策变量对应于一个约束条件，因此模型中仍然存在关系但存在许多不等式约束。模型标准化后，需要引入许多辅助变量。如果辅助变量也定义为0-1个变量，则引入的辅助