英语原文共 33 页
动态交通分配的基础：过去，现在和未来
摘要
自Mershant和Nemhauser的开创性工作以来，动态交通路径分配已经取得了长足的进步。 从数学编程到变分不等式，为解决最优控制和基于仿真问题，已经有了许多公式和解决方案。这个特别的议题的目的是记录现有的动态交通路径分配方法以供后人参考。这篇开题报告将总结对DTA的不同理解，回顾现有文献，将文中提到的方法联系起来，并预测未来。
关键词：动态交通路径分配，实时部署，规划
1.背景简介
自从Merchant和Nemhauser的开创性工作以来，动态交通路径分配问题的研究虽然仍然处于发展阶段，但已经取得了长足的进步。目前动态交通路径分配问题引起了广大研究人员的兴趣，特别是将其应用于大规模实时路径规划方面。此外，研究人员越来越意识到DTA理论仍然相对不发达，这需要新的方法来解决应用领域的挑战以及与易处理性和现实性相关的基本问题。 代理商和从业者也越来越意识到DTA有可能通过现有静态规划方法的不切实际的假设和DTA评估智能交通系统（ITS）技术及成为发展引擎的潜力解决长期存在的问题。
DTA表示一个广泛的问题，每个问题对应于不同的决策变量集和潜在的行为和系统假设，并且在表示交通系统或控制行动方面拥有不同的数据要求和能力。 这些模型的一个共同特征是它们脱离标准的静态分配假设来处理时间流。 这些模型另一个共同特征是目前都没有为一般交通网络提供通用解决方案。也许促进研究人员之间一致意见的一个方面是，一般的DTA问题天生就有不良行为的系统属性，这些属性是交通现实性和人类行为的需要所决定的。系统输入的时间依赖性和随机性进一步加剧了这种情况。 这一现实的一个重要结果是，只有在假设交通理论环境和对驾驶员行为的潜在限制性假设之间折中，才能理论上保证系统的存在性，独特性和稳定性等属性。从互补的角度来看，充分捕捉交通动态和驾驶员行为倾向的能力排除了标准数学特性的保证。 DTA的这种固有的复杂性产生了从分析到基于模拟的方法的明确二分法。理论上不稳定的一个重要现实结果是DTA研究人员关注开发可部署的解决方案程序，寻求接近最优的解决方案，并清楚地认识到唯一性和/或全局最优性的要求在现实世界中既不是必要的，也不是特别有意义的。这表现为寻求有效性，稳健性和部署效率的大多数启发式实施程序的开发。另一个结果是不同方法之间的特征可比性的概念，以便在DTA的总体框架下处理广泛的目标和功能需求时，在所需特征之间的权衡允许对不同DTA问题的不同程度的响应。
一般DTA问题的一个令人放心的实际方面是，它的数学上的难解性并不是相关解决方法在实际应用中的一个全面障碍。过去十年的大量研究表明，在一些现实情况中，可以通过对数学难以处理的方面进行一些无关紧要的轻微违规和/或偶尔的自然表现，获得有效和高效的解决方案。在一些实际情况下，不良行为的问题特征并不会出现，即使出现了不良行为，实际上对于建模假设没有什么时间和空间后果。因此，不同的方法可以满足有着不同程度的稳健性的不同的功能需求，从而排除了通过对病理场景进行数学不稳定性的概括，特别是如果它们在实践中很少见。共识是，可部署的DTA认可应充分代表问题目标背景下的交通现实主义。
本文的结构如下：下一节将通过对主要方法进行分类，并根据目前对DTA的理解将其置于透视中，回顾过去在DTA中所做的努力。 第3节讨论了一些未来的研究问题和方向，目前处于初期阶段，这些问题和方向都是由应用领域或问题所驱动的特点。 第4节提出了一些结论性意见。
2.发展回顾
本节通过将各种方法分为四大类方法论组来回顾过去的DTA文献：数学规划，最优控制，变分不等式和基于模拟。其中，前三组进一步标记为分析方法。与静态情况一样（全面覆盖，见Sheffi（1985）和Patricksson（1994）），大多数公式倾向于关注用户平衡（UE）和系统最优（SO）目标，或者它们的一些变体。鉴于在DTA标签下解决了广泛的问题，过去二十年来该领域已经开发了大量文献，本节重点介绍了突出基本问题维度的一些努力。 Peeta（1994）提供了关于数学规划和基于最优控制的DTA公式的文献综述，特别关注实时信息提供。 Ran和Boyce（1994）讨论了各种最优控制模型。最近关注基于变分不等式的公式的努力在Ran和Boyce（199eth;a）和Chen（1999）中进行了讨论。 Mahmassani等（1998a）回顾了各种基于仿真的DTA模型。
2.1.数学编程公式
数学规划DTA模型在离散化的时间设定中形成问题。 Merchant和Nemhauser（1978a，1978b）代表性地将DTA问题表述为数学程序的第一次尝试。该表述仅限于确定性，固定需求，单一目的地，单一商品，SO案例。该模型（此后称为M-N模型）使用链路退出函数来传播流量，并使用静态链路性能函数来表示作为链路量的函数的旅行成本。它导致基于流的离散时间非凸非线性编程公式。该模型被证明可以提供传统静态SO分配问题的适当推广，并且通过求解模型的分段线性版本来获得全局解。 Ho（1980）表明，通过求解最多N 1个线性程序的序列可以获得这样的全局最优，其中N是周期数。
Carey（198eth;）证明了M-N模型满足线性独立约束条件，因为所提出的退出函数是连续可微的，验证了Merchant-Nemhauser（1978a，1978b）中的最优性分析。 Carey（1987）通过操纵退出函数将Merchant-Nemhauser问题重新定义为表现良好的凸非线性程序，这提供了比原始公式更多的数学和算法优势。基本配方与M-N模型非常相似。对于凸形的公式，退出函数用于约束链接流出而不是像M-N模型中那样的流出本身。由于它是凸的，可以使用标准的数学编程软件来解决问题。然而，本文指出应该探索诸如约束中的阶梯结构之类的特殊结构来开发更有效的算法。引入基本模型的扩展来处理多个目的地和商品。然而，由于“先进先出”（FIFO）要求引起的非凸性问题，所得到的配方仍然存在问题。对于UE和SO情况，这些困难似乎是针对时间相关分配问题的所有数学编程方法中固有的。多个目的地要求模型明确满足从交通现实主义观点来看必不可少的先进先出要求。 FIFO有两个维度，物理和算法。由于个别车辆有时可能违反实际交通网络中的FIFO（超车），因此从流量传播的角度来看，仅在平均意义上满足。
这里暗示的有问题的FIFO违规是算法引发的，其中一些商品（例如，一个源 - 目的地（O-D）对之间的流量）物理地跳过另一个以降低系统成本。这与交通现实主义不一致。在单目的地配方和某些特殊网络结构中很容易满足FIFO要求。在一般网络中，这一要求会引入额外的约束，产生非凸约束集，破坏公式的许多优良特性，并严重增加任何最终解算法的计算要求（Carey，1992）。
与影响交通现实主义的SO数学规划模型相关的另一个众所周知的现象是链路上车辆的“阻碍”。当链路退出约束被满足为严格的不等式时，就会出现这种情况。在交通网络中，有利于某些交通流或移动超过其他交通流或移动以最小化系统范围的行进延迟（例如，在交叉路口的次要接近处阻止交通以支持主要方法）。除非另有说明，否则SO分配公式的解决方案可能需要在路径重叠或交叉的点处在一个路径上保持业务量以支持其他路径上的业务一段大量时间。换句话说，车辆可能在链接上被人为地延迟超过可能被认为是“公平”或“合理”的时间。这种解决方案在社会上可能是不可接受的，也不是现实的。从建模的角度来看，这将需要明确的约束来排除阻止流量。 Carey和Subrahmanian（2000）阐述了FIFO和阻碍问题的某些方面。
Janson（1991a，1991b）代表性地将UE DTA问题建模为数学程序的最早尝试之一。他的方法的一个特点是，它寻求根据经验路径行程时间描述的平衡，而不是在几个先前研究中假设的瞬时行程时间。在公式中提出了非线性混合整数约束以确保O-D流的时间连续性，尽管它们可能在指定的解决方案过程中被违反，这是静态公式的众所周知的增量分配启发式的直接扩展。此过程的属性尚未充分确定，并且可能导致可能的不切实际的流量行为。此外，它依赖于静态链接性能函数进行流量建模。
Birge和Ho（1993）通过放宽O-D期望在整个计划范围内已知的假设，将M-N问题扩展到随机情况。他们开发了一个多阶段随机数学规划公式，在确定性情况下是非线性和非凸的。该模型假定随机变量实现的有限数量的场景，其中场景被定义为每个时段中过去的O-D期望的可能组合。但是，该公式假定当前的分配决策与未来的O-D需求无关。得到的模型确定O-D分配模式，该模式通过一系列线性优化使几个时间段内的预期分段线性凸成本最小化。
Ziliaskopoulos（2000）基于用于交通传播的小区传输模型（Daganzo，1994），引入了针对单目的地SO DTA问题的线性规划公式。当流程根据小区传输模型传播时，它绕过了对链路性能功能的需求，从而对流量现实更加敏感。虽然不是实际应用程序的操作模型，但它提供了一些有关DTA问题属性的见解。 Carey和Subrahmanian（2000）也提出了线性单目标SO DTA公式，同样旨在得出对模型属性的见解。如前所述，他们在数学规划公式的背景下研究FIFO和阻碍问题。
基于数学规划的DTA方法的大量研究突出了其目前在开发通用网络可部署模型方面的局限性。一个持久的问题是需要权衡数学易处理性与流量现实性。这主要体现在不充分的建模能力和/或与交通动态的表示相关的不方便的约束。一个这样的方面是显式地寻址FIFO属性所需的非凸约束。虽然有大量优化文献涉及非凸规划，但DTA上下文中的非凸性导致在一般网络中部署的分析和计算可处理性的损失。此外，一般而言，数学规划DTA公式往往存在以下方面的困难：（i）使用链路性能和/或链路退出功能，（ii）阻止流量，（iii）实时有效解决方案在大规模交通网络中部署，以及（iv）清楚地理解现实问题场景的解决方案属性。
2.2.最佳对照公式
在受约束的最优控制理论DTA公式中，O-D跳闸速率被假定为已知的连续时间函数，并且链路流被寻求作为时间的连续函数。约束类似于数学规划公式的约束，但是在连续时间设置中定义。这导致连续时间最优控制公式，而不是离散时间数学程序。
Friesz等人（1989）讨论了针对单个目的地案例的SO和UE目标的基于链路的最优控制公式。模型假设随着网络状况的变化，从一个系统状态到另一个系统状态的调整可能同时发生;也就是说，路由决策是基于当前网络条件做出的，但可以随着条件的变化而不断修改。 SO模型是静态SO模型的时间扩展，并且证明在最优解决方案中，O-D对的使用路径上的瞬时流量边际成本是相同的并且小于或等于未使用路径上的那些。应该注意的是，该SO配方的离散时间版本将与M-N模型相同。他们还提出了Beckmann等效优化问题（Beckmann等，195）的时间相关推广，用于通过瞬时用户路径成本的平衡以最优控制问题的形式进行静态UE流量分配。模型使用退出函数来传播流量，并链接性能函数以确定旅行成本。关键问题包括缺乏有意义的链接性能和退出功能，以及开发高效解决方案算法的困难。此外，配方将链接流入视为控制变量，尽管流出是一种功能。这是有问题的，因为退出函数的非线性使得很难建立Wardrop的第一原理（Wardrop，1952）对具有多个起源和目的地的网络的时间依赖性情况的概括。 Wie（1990）扩展了UE模型以包括弹性时变旅行需求，这导致隐含考虑出发时间选择。 Wie还列举了这种方法的一些局限性。
Ran和Shimazaki（1989a）使用最优控制方法为具有多个来源和目的地的城市交通网络开发基于链路的SO模型。他们还将退出流定义为一个函数，排除了最优性条件的推广。它们使用线性退出函数和二次链接性能函数，以减少时间空间分解解决方案程序的计算负担，该程序只能处理非常小的网络问题。除了不切实际的拥塞建模之外，他们还没有考虑到多个目的地出现的FIFO问题。 Ran和Shimazaki（1989b）提出了一种基于瞬时UE DTA模型的最优控制理论。退出链接的流被视为一组控制变量，而不是用于规避泛化问题的函数。没有有效的算法可用于解决这些配方。
Ran等人（1993）通过将链路流入和流出定义为控制变量，使用最优控制方法来获得瞬时UE DTA问题的凸模型。他们认识到通常的成本函数无法考虑动态排队和拥塞成本，并建议将链路旅行成本分成移动和排队组件。然而，假设这些函数是非负的，增加的和可微分的，因此可能不反映交通现实性。此外，没有提供或测试功能的特定实例。博伊斯等人（1995）讨论了使用Frank-Wolfe算法和扩展的时空网络表示来解决问题的离散化版本的方法。但是，他们没有实施该程序或通过实例说明。此外，静态链接性能函数的使用是该模型的限制。
尽管描述动态系统是一种极具吸引力的方法，但最佳控制类型的DTA配方受到许多限制，例如缺乏明确的限制来确保FIFO并阻止在节点处保持车辆，不充分且可能不现实的交通拥堵建模，以及 更重要的是，缺乏一般网络的解决方案程序。 此外，基于瞬时旅行时间对UE公式的实质性解释需要对研究人员假定的特定平衡条件下的行为过程的性质进行相当强烈且可能不切实际的假设。 由于DTA背景下最优控制理论的局限性以及变分不等式（VI）所带来的优势，近年来分析DTA模型已经转向VI方法，下文将对此进行讨论。
2.3.变分不等式公式
变分不等式为DTA上下文中的几类问题提供了一般公式，如优化，定点和互补。它促进了一个统一的机制来解决均衡和等效的优化问题。此外，可以以简单的方式说明其数学特性，例如唯一性。 Dafermos（1980）在静态交通均衡背景下引入了VI方法。
Nagurney（1998）提供了VI的综合总结并解决了各种均衡问题。 VI避免了由于不对称链接相互作用而在约束优化配方中出现的分析易处理性问题。从这个意义上说，它可以处理更真实的交通场景。此外，可以方便地进行扩展和灵敏度分析。虽然它比其他分析方法更为通用，装备更
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
