快速交通系统规划的优化方法

快速交通系统规划的优化方法GilbertLaportea,*,JuanA.Mesab,FranciscoA.OrtegacaCentrederecherchesiirlestransports,UiiiversitedeMontreal,C.P.6128,SuccursaleCentre-ville,Montreal,Quebec,CanadaH3C3J7bDepartamentodeMatematicaAplicadaII,EscuelaSuperiordeIiigeiiieros,UiiiversidaddeSevilla,Sevilla,SpaincDepartamentodeMatematicaAplicadaI,EscuelaTeaiicaSuperiordeArquitectura,UiiiversidaddeSevilla,Sevilla,SpainReceived1December1998;accepted31December1998摘要规划快速交通系统时的一个核心问题是线路和站位的确定。可行的研究方法能帮助解决这些问题，并且，它们也对于评估网络的特性有帮助。这份调查报告考察了主要的有效方法。62000ElsevierScienceB.V.Allriglitsreseived.关键词：快速交通系统、线路、车站、定位1、引言规划交通系统时的一个核心问题是线路和车站的确定。然而人们对适用于这个过程的分析工具却知之甚少。一份Gendieau等人的近期调查研究(1995年)表明：快速交通系统的规划是一个复杂的决策过程，其涉及多种目标和约束、不确定因素、非量化影响因素、庞大的基本建设支出和长期的责任。这个过程由儿个参与者共享，例如规划师、工程师、使用者、环保人士和其他利益集团。众所周知，标准网络设计工具对于完全地解决此类复杂问题(见，例如，Magnanti和Wong,1984)常常是不充分的，但它们在一个技术层面上能发挥有益的作用。规划的过程往往始于城市结构的分析，包括标识主要的商业、购物、工业、娱乐和旅游区域、大学、医院和其他重要建筑、机场、火车站、公共汽车站、交通主干道、现有交通系统等。随后分析O/D流，并将大交通走廊选定为目标线位。以此拟定出凡个方案，并依据技术可行性、费用、覆盖范围和利用率、效能、对土地利用的影响、不动产和零售业(Bay,1985;WulkanandHemy,1985)交通和停车(Schabas,1988)>环境(BlackledgeandHumpliieys,1984)和安全性(Siegel,1980;Stiaus,1980;PerrinandBenz,1990)等指标进行评估。EuropeanJournalofOperationalResearch122(2000)l±10/1ocate/orms*Correspondingauthor.TeL:fax:E-mailadchess:gilbert@crt.umontreal.ca(GilbertLaporte).0377-2217/00/$-seefiontmatter62000ElsevierScienceB.V.AllriglitsreservedPn：S0377-2217(99)00016-8这个过程总是要持续很长一段时间，并且牵涉大量参与者的参与。由于有些前景数据被修改，或者新的前景被引入，因此需要数次重复迭代。一组限定的有前景的解决方案被精细微调，就做出了最终的决定。令人关注的这一过程的应用可见于lackledge和Humphreys(1984),Lundstroni等人(1981),Page和Demesky(1985),Perrin和Benz(1990),和Schabas(1988)的研究中。分析方法被模式化地运用于规划过程的儿个阶段。工程技术被应用于帮助评估技术可行性和一些有潜力的线路的建造成本。复杂的仿真工具，如EMME/2(INRO咨询，1998),能够帮助在各种系统结构下得到交通流量。如今，根据一个系统的特性和价格体系，离散的选择模型能用作需求预测。Bierlaire(1998)的近期报告提出一个四类模型：决策者特性、可替代的交通方式、它们的属性和决策规则。尽管运筹学的儿种方法是近儿年才发展起来的，但在规划阶段，能在三个主要领域起到帮助作用：有利益的线路的产生、车站的位置和网络特性的评估。我们这项研究着重于战略性的或者长期的规划。因此，我们排除了运营的方面，如列车时刻调度和票价设置。我们的报告是根据这些线索组织的。第二章中，我们检验了一些与快速公交网络有关的模型问题。在第三章和第四章中描述了选择线位和站位的算法。更整体性的网络评估问题陈述于第五章。2、模型问题形成一个好的交通网络的难题可以看作是一个网络设计的难题(见，如Ahuja等人，1995)，但即使是隶属于这一范畴的最简单的模型，当网络的规格变大时,也难以通过分析法来处理。在快速交通规划的背景下，这个难题将约束与目标综合在一起，其中的一些很难清楚地表明或充分的度量。我们意识到：没有一种分析方法可以全面地解决快速交通系统规划的问题。所有己知的方法适用于单线的定位。因此，整体性的问题可以通过每次确定一条线的位置来逐步解决，然而技术确实能评价一个复杂网络的效率。在诸如交通走向定位的情境下，分析方法应当用于产生儿种而不仅仅是一种可供选择的解决方案。我们偏向于去寻找能够产生一系列按照这个问题的主要准则而定的好的解决方法。这些解决方案应当在形成阶段，接着按照其他未明确的标准被量化，而决策者应当从推荐方案中选择。快速交通系统的目标是高效地运送大量客流(见，如Blackledge和Humphreys,1984；Bonz,1983；Fukuyama,1983；Quqing,1984)。只要一条线被确定了，往往意味着被这条线覆盖的人口达到最大值。如果整个网络都被设计好了，全网的效率也不得不被考虑进去，正如我们在第四章中讨论的。即使在单线的情况下,人口最大化的目标也不那么容易度量。一些作者(见，如Chapleau等人，1986；Wirasinghe和Vandebona,1987)将它解释成住在离线路一定距离内的人数。—种度量的方法是用一系列沿线的嵌入式走廊。这种方法的问题在于：住的离线路近，却离车站相对较远的人们就不太可能使用这个系统。被车站覆盖的人口是更适当的需求量。为使这种措施可行，Diifourd等人(1996)和Bruno等人(1998a,b)使用绕着有潜在可能的车站的同心形状(轮廓线)，对于从车站出发，步行单位在d以内的人们，伴有一个递减的权重饥(这些作者用00=1.0,01=1.0,&=0.5,03=0.25,0d=O,d>4)o步行距离可以用米制的Zp来估计，通常l<p<2op=l表示曼哈顿距离，而p=2则表示欧凡里得距离。如果用曼哈顿标准来描述步行距离，轮廓线将成菱形。如果用欧儿里得标准，轮廓线将成圆形。这样，如果ri(x,y)是与坐标点(x,y)相对应的人数，那么位于S的车站的覆盖范围被定义成C(s)=/n(x,y)d(x,y)：D[(x,y)n]=dD[(x,y),s]是指之间的步行距离。因此，全线P=(sh...sn)覆盖范围为C(P)=X”C0)其他作者(如Gleason,1975；Current等人，1985)和许多交通规划师(Hadler和Majumder,1981；Lutin和Benz,1992)用相似的人口覆盖范围度量方法。这种定义一条线路覆盖范围的方法可能不能充分涵盖其乘客数。例如，一个住在距离北-南线的某车站很近的地方，却乘坐东•西轴线的人就不可能光顾这个系统。更好的统计乘客数的方法可以是考虑一条线P上所有相关车站的O/D对(Hiiber和Church,1985)。虽然这种方法比C(P)更为精确，但它需要大量的数据，且在优化算法下难以处理。此外，一些研究者(如Wulkan和Henry,1985)争论：一旦线路建成，人口的重新定位总会发生。所以，在规划阶段使用观测得的O/D模型可能不服从增长的精度。由于这个原因，如C(P)这种度量方法可能是最好也是最简单的测量全线覆盖范围的方法。一些作者不把人口覆盖范围看作交通规划中的主要的目标值。相反的，他们将快速交通系统的结构视作城市发展的催化剂。例如，Howard(1978)叙述了：轻轨系统的结构如何有利于泰恩河和威尔地区的发展。Alsaadi(1983)指出城市发展是巴格达地铁建设背后的一个基础动力。然而，其他作者，如Straus(1980),则强调：虽然快速交通系统有助于城市再造计划，但它永不能替代整体规划。还有一些研究表明：有时候，源于快速交通的存在的城市发展是较小的。这似乎就是在旧金山湾区的湾区捷运那种状况(见，如Fajans等人，1978；Knight和Trygg,1977)。当确定一条线路平面图时应将外部标准考虑其中。在一个泛用的优化算法框架中,其中一些与工程或环境问题相关的标准很难被列入考虑之中。这并不意味着它们可以被忽略，可能更可取的是当一条潜在的线路形成时将这些标准量化。站间距的要求必须被视为硬约束。通常限制任意两站中的最小站间距和任意两相邻站之间的最大站间距。一般说来，这两种标准都介于0.5・2km范围内。市中心区车站的间隔通常比市郊车站的短(见Bruno等人，1988a,b)。下限值确保列车不用经常停车。上限值使乘客不用步行太远至最近的车站，且这个上限值也间接地影响着总建设成本的上限值。快速交通系统选线的问题中最常见的是在站间距约束条件下，在给定区域内确定一条线路P=(Si，...sQ(或者在限定的走廊上)，目的在于使人口覆盖范围最大化(例如用C(P)值来衡量)。车站数n常常取决于小站间距的标准，且一条线路上的某些车站也许被事先确定好了。3、确定线位确定快速交通线路位置的最早的分析方法之一是在Dicesare(1970)的博士论文中，在该文中，作者将问题塑造成在各种各样的约束下，在起点和终点间确定一条最低成本路径。针对该问题的一个简单的解决方法由ChurchandClifford（1979）提出：（1）在研究区域添加一个网格。（2）由用户根据每一条标准为每一个单元打分。（3）将这各种各样的分数统计得到最小化的单一目标。（4）用最短路径算法解决这个提出的问题。这个方法的一个主要缺陷在于成本最小化算法可能产生一条给定起点和给定终点的最短路径，却不考虑人口覆盖范围。如果这条最短路径使覆盖范围这个目标最大化，那么这条生成的线路可能纵横交错于整个区域内。Current等人（1985）通过合并线路覆盖的人口和非覆盖人口的衔接成本这两个模型，改进了这个相对粗糙的方法。根据是否以一条线的人口覆盖率最大化为目标值，或者，是否以最短路径距离和最低到达成本为目标值，就产生了覆盖路径模型或平均最短路径模型。同类的另一个模型最近由Bnmo等人（1998a,b）提出。作者依照的O/D需求，而非将人口覆盖范围最大化。所有上述模型可以被视为网络中的路径定位问题（见Mesa和Boffey,1996和Labbe等人，1998）,且在后者的参考书目中，可以用符号将它公式化。令无向网络G=（V,E）,其中V=（%,...%）唯一系列顶点，E为一系列边（线段）。令勺表示边（％,巧）的成本（或距离），勿）表示0和巧之间最短链的长度。由SGV,定义集合6⑸=｛（%,巧）65,iGS,j《S｝。非负需求w占每一个顶点V.G7有关。令W=/为总需求。在覆盖问题上，对一个给定的rN0,定义£=｛VjG7：dtj<r｝为能够覆盖3的一系列顶点。给定一个非负的常数k,我们可以用二元变量（即0・1变量）的来定义几种问题的等级。当且仅当边（0,巧）属于该方案时，xtj=1；当且仅当顶点3属于该方案时，北=1：当且仅当顶点％间接被覆盖时，而=1；当且仅当顶点3和巧重合时，与=1。如果以费用最小化为目标，则其可以写成min£Gyxtj如果以总成本为约束，那么2-k（vf/vy）eE类似地，覆盖目标值可以表达为max£（3.州）eE其相应的约束为2W必t>kv（eV和及式2%03V）约束条件（6）确保只要顶点弓在方案内，顶点0就被覆盖到。如果k=w,那么该网络的所有需求都被覆盖到。如果kVw,我们成为间接覆盖。在这种情况下，人们都期望使介于路径和不在其上的需求点间的距离最小化，使£WjdjiZnv（,VjGV最小化，或者在总距离上加一个约束：£WjdjiZji<k当使用（7）或（8）时，必须引入下述技术约束：£勾+弘=1（ViGV）和Zij<yt（说,VjGV）这就迫使每一个顶点a都在路径上，或者与其他顶点?重合。无论一个目标函数用的是何种约束，该约束必须确保结果是一条路径：2勺=£"1（Vi，Vj）eE>xij乏Vk+无一1（丹,马）函（5）（SuV,%GS,vhS,2<|S|<n—1）,£<2y,（VjGV）（丹凹）&（｛咀）所有这些模型中的难点在于引入约束条件来适当控制相邻站间距，这在实际条件下是决定性的。这样的限制条件借由启发法被最优处理。近儿年，针对在人口覆盖率目标下和相邻站间距约束条件下的单线定位问题，有两种启发法被提出来。最初，Diifourd等人（1996）使用禁忌搜索，这是一种元启发式教学法，它通过允许中间恶化的解决方案来反复探索解空间（针对这方法的最近的综述，见Glover和Laguna（1997））。这种方法从一个产生于某平面上的随机运动的初始解开始。每一次迭代时，它移动一个或儿个站至邻近的位置上去，同时保证可行性。第二种启发法，由Brun。等人（1998a,b）逐步扩充到局部线路，方法是在确定一个位置的同时确保候选车站能有效地被连接到该局部线路上来。改进阶段则从一个己知可行的解决方案中选取凡段局部线路并用构造阶段的相同规则将他们向两端延伸。总的来说，这算法比Dufoiird等人（1996）的更有用。它更快速且陷入局部最优的可能性更小。即使从一个不怎么样的起点开始一条线路，也能产生一个很好的解决方案。随机生成的实例的测试表明：Bnmo等人的算法在计算机不普及的时代，可以始终如一地产生最优的或近似最优的解决方案。使用米兰的人口数据也进行了试验，并轻松地生成了一条覆盖主要居民点的线路。同步定位儿条线路位置的研充越来越少了。一个著名的例外是Wirasinglie等人（1977）的作品，在乘客初次使用衔接公交到达最近的车站这一背景下，他们对星形结构的设计进行了分析。这项工作的目的在于运用解析计算公式来确认星形结构合理的分支数量和车站的位置。这里有部分是基于Vuchic和Newell（1968）先前的结论。4、确定站位在第三章中的方法同时确定了一条线路和一系列车站的位置。然而，一旦线位被确定，常常需要依靠优化算法对站位进行微调。在这个阶段，因为线位己知，更精确地确定每个车站的覆盖范围和线路总客流量是可能的。该领域非常著名的一个研究是Viichic和Newell（1968）的文章，他们寻求在人们都往单一中心换乘的理想的星形系统中确定车站位置。该分析将沿线的乘客分布、通行速度、列车的动力特征、列车在车站的停车等待时间和站内换乘时间。目的就是将到达最终目的地的总交通时间最小化。运用同时发生的不同公式，作者表明：针对沿线标准化的人口分布，在乘客堆积的方向上加大站间距。Laporte等人（1998）通过适当确定线路上的站位，受制于相邻站的约束，忽略在列车上的交通时间，并追求将己定位的单线覆盖范围最大化。他们最先分离线路，但精确程度可以非常高。例如，按O.lkin分段是很现实的。然后，如在第二章中解释的，可以绕每个车站画等距离同心圆曲线。如果两相邻车站i和j的覆盖范围&和4重叠，那么画等距离平分线可以确定哪个车站可以吸引AiQAj区域内的居民。第二步是逐步确定住在任意两相邻等距离同心圆曲线间、且属于每个车站覆盖范围内的人口数量。实际上这非常困难，因为人口数据常常与户口统计数据相关，但这些与等距离同心圆曲线并不一致。然而，精确的人口统计可以通过三角法（O'Rourke,1994）和计算儿何技术（Laporte等人，1998）获得。二者选一地，如果针对等距离圆曲线的分析公式能够在这样的系统中被统一，且它们的图解陈述是可用的话，地理信息系统软件（Schweiger,1992）可以证实有用。事实上，确定每个潜在车站的人口覆盖率大概是足够的。更精确地估计出行量（与总人口数相对应）也可以通过运用吸引模型（见，如Oitiizar和Wilhimseii,1990）进行派生。一旦估计出每个潜在车站的潜在客流量，作为一种最短路径问题的解决方案，就可以正确地得到车站位置的实际选择，即定位在一个指定区域G=（VfA）o其中V是指一系列潜在位置，A是指介于V中各顶点间的一系列弧。孤（i〃・）只在可行时才被定义，考虑到站间距的限制，在一条线路上连续地确定i和j的位置。与0，）相关的成本是M-勺，勺是与0。段相关区域内的期望人口（或客流），M是一个很大的常数满足M>max（t;）e?1（c0｝。该方法的计算可行性由Laporte等人（1998）用塞维利亚的城市数据证实。5、评估交通网络正如所提及的，我们还不知道任何能够生成整个交通网络的算法。然而，评估一个潜在的或现实存在的网络的质量的分析工具是存在的。研究的线索根植于MussedVucliicC1988）的作品中，他们设计了一系列定量各种地铁网络G=（VfE）的因素的方法。他们包括一些简单的指标，诸如车站数、线网总长度、线路数、换乘站和更复杂的方法，例如最短周期（不包括其他任何周期）、网络的复杂指标B=旧|/|1/|、一个等同于|E|和可能出现在G中的边的数量的最大值之比的连通性指标和一个等价于O/D出行量中不换乘的比例的直接服务指标。Laporte等人（1994）引入另外两个方法。第一个是乘客-网络效率，定义如下：对网络G=（V,E）上每一段介于％和巧之间路径P,首先定义总客流成本如下：勾（P）=£勺+冲）邛+（s（P）-r（P）-l）tsV^VjEP其中勺是％和巧之间的旅行时间，r（P）和s（P）分别是该路径上的换乘数和边的数量，0是换乘时间，乌是停车时间。然后总客流成本为：0=2勾其中印=minp｛勾•（P）｝。乘客-网络效率指标为：A=0/£勺第二种方法为乘客•飞机效率，也就是将乘客使用交通网络出行的成本和坐飞机出行所产生的成本作比较得到的指标。假定一个标准Zp来描述步行距离。给定矩阵。=（勾）和Mp=（mijp）,其中m卯是用标准姑来计算过的介于％和巧间的旅行时间，那么乘客•飞机效率的量度是：“p=||®—Mp||/|l/|其中给定一个rXs矩阵A=（为），Frobenius标准||A||被定义为：

临=仅2>)v=l，=l/1/2该研究的结论是：在圆形城市，图1（b）中环和图1（C）中的三角形设计服从于最优（最小）的度量。在方格网形的城市中，改进的方格网（图1（e））和半方格网（图1（f））的结构最充分地考虑了乘客•网络效率，但考虑到乘客•飞机效率（见表1）的话就不如图1（d）中的方格网结构。星形（图临=仅2>)v=l，=l/1/2需要注意的是：伦敦、莫斯科、东京（日本铁路）、马德里和汉堡的网络属于环图1六种基本网络结构表1在环形和方格网形城市中一些基本结构的比较结构环形城市方格网形城市星形环形环加放射形三角形方格网形改进方格网形半方格网形乘客网络效率指数34.1732.5625.9118.4729.9027.6326.26乘客-飞机效率指数(p=1.5)0.880.800.530.590.941.021.43布拉格、法兰克福、基辅和圣彼得堡的城市显示为三角形或准三角形的结构。蒙特利尔、芝加哥和多伦多为改进的方格网系统。这分析只应用于网络拓扑结构,并且，假定所有的O/D对都是等可能的。在较次要的研究中，Laporte等人(1997)通过引入均一性假