电子笔记理论计算机科学50号1（2001）。ATMOS 2001网址：http://www.elsevier.nl/locate/entcs/volume50.html10页基于混合规划Anita Schobel1大学数学系在凯撒宫，InstitutfurTechno-undWirtschaftsmathematik德国摘要延误车辆的处理是公交公司处置工作中必不可少的环节如果车辆到达某个车站时出现延误，则必须决定连接车辆是否应等待换乘乘客，或者是否应及时离开。一个可能的目标函数是最小化使用运输网络的所有客户的所有延迟之本文将延误管理问题转化为一个混合整数线性规划问题，并给出了相应的求解方法1引言不幸的是，延误是公共交通投诉的主要问题，似乎不可能完全避免。使用延迟车辆的客户可能会按计划晚些到达目的地。更糟糕的是，如果一些乘客想从延误的车辆换乘另一辆公共汽车或火车，他们可能会错过他们的连接，也许不得不等待很长一段时间的下一个。在本文中，我们分析了这些影响，并将提出一个模型如何处理延误。假设一列火车到达k站，晚点几分钟。在k站有一辆公共汽车准备发车。这辆接驳巴士应该做什么？有两种选择：公共汽车可以等待，因此导致公共汽车内的顾客的延迟，但也会导致稍后想要乘坐该公共汽车的顾客的延迟，并且可能导致将不得不等待其延迟的后续其他公共汽车的延迟。1电子邮件地址：schoebel@mathematik.uni-kl.dec 2001年由Elsevier Science B出版。V.CC BY-NC-ND许可下的开放访问。2LJK我ATMOS2001{A. SchoBel图1.一、在站点k处从车辆i到车辆j的连接（i; j; k）。另一方面，如果公共汽车及时出发，所有计划从晚点的火车换乘公共汽车的顾客将错过他们的连接。延误管理问题是指不仅针对一辆公交车，而且针对公交网络中的所有车辆的等待发车决策，以使所有乘客的不便最小化。作为对顾客的不便，我们考虑他到达目的地时的延误量。由于在延误管理问题中，必须确定每个车站每个车辆的新发车时间，因此它与以下问题密切相关：在公共交通中设置时刻表。在这一领域，已经做了大量的研究，作为组合和图论方法以及各种数学和元数学的例子，参见[9]和其中的参考文献作为目标函数，主要考虑总等待时间或旅行时间，有时也考虑运行时刻表的成本。其他主要在调度和排程中考虑的模型，但在处理延迟时可能有用的是最大加代数（例如，[6]或[7]，或[13]，或[14]，或[15]，或[16]，或[17]，或[18]，或[19]，或[除了目标函数略有不同之外，与延迟管理问题的主要区别在于，在延迟管理问题中，连接不是预先给定的。事实上，必须做出的主要决定是决定哪些连接应该保持，哪些可以丢弃。延迟及其后果已在以前的几篇论文中讨论过，[8，3]用于分析延迟的发生[11，1，7，12]涉及铁路系统的延迟。在处理对初始延迟的反应时，主要使用模拟和专家系统。与这些方法相比，本文将延迟管理问题建模为混合整数规划，以便优化方法可以用于nding良好的决策。3ijk我我ATMOS2001{A. SchoBel2混合整数规划公式在本文中，我们将处理延迟管理问题定义如下。给定在运输网络内运行的一组车辆，以及这些车辆之一的初始延迟V，应该如何调整车辆的调度，使得网络内所有客户的总延迟量最小化？我们首先介绍一些符号。为了描述交通网络，设V是站点的集合，F是车辆的集合（eet）。 对于每辆车，我们引入EiVv作为其在交通网络内的行驶边的集合。 如果可以在站点k从车辆i换乘到车辆j，则（i; j; k）将被称为连接，并且整个连接集合由下式给出：UFF V：我们还需要参数pk、pkl和pk，这些参数表示伊日车辆i在站点k的等待时间，对于车辆i在其上的行驶时间，从站k到站l的路线，以及在站k处从车辆i改变到车辆j的客户。由于目标是最小化网络中所有客户的所有延迟之和，因此我们需要指定有关客户的数据。为此，设A是通过公共交通网络的一组路径，并且wa是使用特定路径a2A的客户数量。来描述这些路径在A中，我们使用如下定义的 参数一ijk =81如果站点k由车辆i到达并由路径a中的车辆j离开：0，否则为了避免车站的时间依赖性表示，我们假设每个车辆i2 F和每个客户路径a2 A最多包含一次任何车站。此外，我们假设T是所有车辆的（公共）时间段，并且在下一个时间段中，所有车辆都在时间内。初始延迟被给定为特定车辆到达特定站点的时间量V，并且我们假设VT。作为变量，xk=车辆i在k站的出发延误y k=车辆i在k站的到达延误Za=1 如果保持路径A上的：0，否则。H4IaIa1也就是说，对于所有i2F;k 2 V，yk =xk= 0，对于所有a2A，za= 1。 当然是yk=Vk，对于所有（i; k）2D;IJATMOS2001{A. SchoBel为了计算使用特定路径a2A的所有乘客的延误之和，我们区分两种情况。情况1：路径a上的所有连接都已保持。那么使用该路径的乘客的延迟简单地是他们的最后一辆车ia在他们的目的地站ka的到达延迟，由wayka给出。请注意，这些乘客在旅行期间可能会有更大的延误，但只有到达目的地的延误才是相关的。情况2：路径a上至少有一个连接未维护。然后，我们假设使用路径a的乘客必须等待整个时间段T以等待下一辆前往其目的地的车辆，因此延迟由wa T给出。现在可以给出延迟管理问题的模型（DM）minXwa（1za）T+zayka2A，这样（一）（二）y1= Vykx k+ pk8i 2 F;k 2 V我我我（三）XKy l+ pkl8k; l2 V;i2 F：（k; l）2Ei我我我xk+ pkyk（四）一ijk伊季M一期+18（i; j; k）2 U;a2 A(5)0y k;x kT 的;我我(6)za2 f0;1g其中ia表示路径a上的最后一辆车，ka表示路径a上的最后一个站，并且M应该被选择为使得MMax（i;j;k）2Uk+T：注意，约束（5）确保不需要考虑大于公共时间段的延迟，因为在这种情况下，客户可以乘坐下一个时间段的非延迟车辆。约束（1）包含源延迟，例如，1号车在1号站注意，这个单一约束是公式中的关键约束;放松约束（1）将导致没有任何延迟的平凡最优解我我也可以使用一组源延迟，即，我我Hp个zla5其中D描述了基于车辆到达时间的初始延迟集合。不等式（2）确保以延迟到达某个站点k的车辆也将以该延迟离开，其中可以减去可能为正的松弛时间，并且约束（3）确保正确地6我我ijk到达站车辆我驱动车辆j驱动m站发车客户改变K站发车K站到达车辆i停止车辆j停止客户改变K站到达K站发车车辆i驱动车辆J驱动出发站L站到达ATMOS2001{A. SchoBel图二. 事件活动网络沿着车辆的行驶边缘。（4）xkYK变量与关于客户的数据相耦合托默斯 为了理解约束（4）的含义，取从车辆i到某个站点k处的车辆j的连接（i; j; k）2 U和路径a 2 A包含该特定连接，即，其中ha= 1。 注意j x k+ p ky kjj x ky k j + j p kjT +max p kM：吉吉伊j iiji;j;kij因此，如果不保持连接，即，ykpk> xki ij j我们知道Mx k+ p ky k<0，因此，伊季我xk+ pkyk0jijM+111使得当且仅当zA= 0时满足约束（4）。 另一方面，在一项研究中， 如果保持连接，xk+ pkyk伊季M+11 1使得zA不受约束条件（4）的限制，并且由于目标函数的最小化，因此可以选择为zA基于事件活动网络（例如，[9]），该公式可以在图形理论上解释如下。我们构造了一个事件-活动网络G=（V; E），其中节点集V=V∈[Vdep F V]表示车辆i在某个站点k的所有到达（i; k）dep和车辆i在7某个站点k的所有离开（i; k）dep。然后可以使用三种类型的边8Ia1IaIaIa节点权重yk;xk对应于表示节点权重的决策变量（DM）=）（DM ′）：设yk;xk;z是（DM）的可行解. De nefory kay ka z a+ T（1za）8a2 Ayk; xk; za; ua对于（DM '）是可行的，并且两个解具有相同的ob。（DM）=）（DM）：设yk;xk;za;u是（DM '）的可行解. 然后yk;xk;za对于（DM）也是可行的从（11）我们得出结论，ATMOS2001{A. SchoBel区别（见图2）。等待边（（i; k）n;（i; k）dep）驱动边（（i; k）dep;（i; l）n），其中（k; l）2 Ei改变边（（i; k）n;（j; k）dep），其中（i; j; k）2 U在事件-活动网络中，边的权重是给定的松弛度时间即pk表示等待边沿，pkl表示驱动边沿，pk表示变化边沿。伊日我我分别是到达和离开事件（i; k）的延迟ddp和（i; k）dep目标是决定哪些变化的边缘可以被丢弃，哪些应该被保留，以最小化所有客户的总体延迟模型（DM）的给定公式可以通过用新的变量ua代替二次项ykaza来线性化（和弱化），从而得到模型（DM）。minXwa（（1za）T+ua）2A，这样(7)(8)y1= Vykx k+ pk8i 2 F;k 2 V我我我(9)XKy l+ pkl8k; l2 V;i2 F：（k; l）2Ei我我我xk+ pkyk(10) 个zla一ijk伊季M一期+18（i; j; k）2 U;a2 A(11)uay kaT（1za）8a2 A(12)0y k;x kT 的;我我(13)u a 0 的整数;(14)za2 f0; 1g引理2.1线性化是正确的。证据我我所有a2 Au a=y kaz a。以来我啊我啊我我客观价值我我我我u ay ka 如果z a=H9Ia1u a0，否则。因此，ua ykaza，因为我们最小化了，目标函数不会增加。10ijkIaIa1jkP0yk; xk不ATMOS2001{A. SchoBel23上下界为了计算上界，我们通过将整数变量za;a2 A构造可行解设A表示已被固定为1的变量za的集合，并且设U= f（i; j; k）2 U：存在一个2A使得ha= 1g是从A开始的路径上的连接的集合。 然后约束（4）简化为xk+ pkyk1个月这相当于i+1 8（i; j; k）2Uxk+ pkyk08（i; j; k）2U：吉吉伊因此，模型（DM）的混合整数规划可归结为以下线性规划。minXwayka使得11xk+yka2A=VPK8i 2 F;k 2 Vi我我xk ylpkl8k; l2 V;i2 F：（k; l）2Ei我我我x k+y kPK8（i; j; k）2Uj伊季报我我该公式可以通过线性规划或通过使用前一节中描述的事件-活动网络并执行活动网络的关键路径方法（例如，[4]见[5]。为了确定za变量的值，以下策略是可能的。所有车辆都及时离开：那么上限可以通过下式计算：Xa2A：ia=1wa yka+Xwa Ta2A1其中第一项由yVPa2A限定：ia=1wa，A1 =fa2 A：9j2 F;k2 V使得（1; j; k）2U;ha= 1g：所有车辆等待：这导致了2Awa V的平凡界限，如果松弛时间大于零，则通过求解线性节目楼上启发式方法：构建一 在许多人使用的路径之外，顾客，不关心别人。元启发式方法：找到一个好的集合A也可以通过元启发式方法来解决，例如遗传算法或模拟退火。y11ijk一IJ我IaIJIa一IJ注意，另一方面，对于xk，yk的任何可行值集，引理3.1给定yk; xk，（DM）的最优解由下式给出：函数与xk+pk yk成比例。这意味着连接（i; j; k）IJATMOS2001{A. SchoBel我我i2 F;k 2 V，则za，a2 A的最佳值设Ua = f（i; j; k）2U：ha= 1g是路径a2 A上的连接集。我z=如果min（i;j;k）2Uai：1否则：xj+pkyk<0证据在给定x和y变量的情况下，（DM）可以简化为minXwa（1za）T+zayka使得一ijk的2A基季8（i; j; k）2 U;a 2 Aza2f0;1g;xk+pkykk其中gk=伊季Mi+ 1：因为我们想要最小化，并且因为y是T，都是a2 A，我们得出结论，z= 1，如果这是可行的，即如果gk1为所有（i; j; k）2 U a. 使用该gk1（） xk+ pk yk0伊吉伊吉结果如下。2（DM）的下界可以通过求解（DM '）的线性规划松弛来获得，其中za2 f0; 1g被za1代替。为了加强公式化，约束（10）可以被替换为xk+ pkyk一ijk伊季 Mi+1 8（i; j; k）2 U;a2 A;哪里一Ma= max（i;j;k）2Uak+V：在这种放松中，错过的连接对目标的贡献吉吉伊仅仅因为几分钟的时间就错过了，功能不如车辆J在车辆I到达之前很长时间就已经离开。4应用与展望本文的项目是由两个大型的交通协会提出的，服务于莱茵兰-普法尔茨州和萨尔州（都在德国）。他们感兴趣的是分析延误的后果，或者更一般地说，也是分析进度表中的（小）变化的后果。在分析这些变化时，重zahGHp个zla12要的是不要只看一家运输公司，而要考虑到13确定yk和xk可以在PII/500计算机上在几秒钟内完成，劳特雷肯-格伦巴赫维斯韦勒·奥芬巴赫鲍姆霍尔德罗恩韦勒海因岑豪森542拉斯韦勒格兰布吕肯克舍瑙539贝尔施魏莱539埃尔德斯雷克魏勒霍夫R93沃尔夫施泰因罗斯巴赫弗赖森·赖希魏莱Ruthsweiler557542阿尔滕格克赖因巴Kusel弗里德尔豪森布莱兹巴537542539泰斯贝格斯特根·孔肯557弗克尔贝格耶滕巴赫奥尔斯布吕R93卡茨韦勒537奥特巴赫R93奥姆巴赫布吕肯KL.WestKaiserslautern.Hbf屈贝尔贝格瓦尔德莫耶格斯堡537HomburgATMOS2001{A. SchoBel图三.计算德国莱茵兰-普法尔茨Lautertalbahn地区的所有延误车辆（红色）。还考虑到不同公共交通公司之间的连接。在实践中，还有其他方面需要考虑时，处理延迟管理问题。其中两个在下面提到在单线线路上，必须考虑迎面而来的列车。这个效应可以通过引入一些新的连接（i; j; k）来建模，这些新的连接表示在迎面而来的列车到达之前不允许车辆j离开。利用变量za被固定为1的人工路径a，可以确保所有这些新连接被保持。此外，车辆调度和驾驶员调度可能对模型有影响，因为延迟的车辆或延迟的驾驶员不能及时开始他的下一个任务。也可以通过引入新的连接来模拟这些影响，这些连接可以被保持或丢弃，但要确保延迟的时间将被转移到下一个任务。我们与项目合作伙伴一起确定了两个具有代表性的测试区域，并收集了有关站点、边缘和时间表的数据。一些基于此数据的RST数值结果表明，求解线性规划，我我还可以获得超过1000辆车的完整一天的数据图将具有延迟的3辆车（在给定的za，a2的解内A) 用红色表示。目前，我们正在收集有关客户行为的真实数据，并正在实施和测试第3节中讨论的策略分支定界方法，其中za是分支变量，并利用上一节中开发的边界也在考虑之中[10]这是一个很好的例子。14ATMOS2001{A. SchoBel附加的假设确保分支定界方法在多项式时间内得出最优解。引用[1] Adenso-Diaz，B.，M. O. Gonz alez和P. Gonzalez-Torre，区域列车服务的在线时刻表重新调度，交通研究33 B（1999），pp. 387{398.[2] 卡斯托尔迪湖A. SCHo bel和T. Sonneborn，启发式应用于延迟管理问题，技 术 报 告 ， 法 国 研 究 所，RTe chno-undWirtschaftsmathematik ，Kaiserenstern（2001），working paper.[3] 陈湾，澳-地Harker，Two moments estimation of the delay on single trackrail lines with scheduled traffic ， Transportation Science24 （ 1990 ） ，pp.261{275.[4] Elmaghraby，S.，\Activity Networks，”Wiley Interscience Publication，1977.[5] Ginkel，A.，\Event-activity networks in delay management，”硕士论文，University of Kaiseraustern（2001（expected）），目前正在研究中。[6] 戈沃德河，铁路时刻表设计的最大代数方法，在：铁路计算机VI：第六届铁路和其他先进公共交通系统计算机辅助设计、制造和运营国际会议论文集，里斯本，1998年，1998年，pp. 339{350.[7] 亨德里克森角和G. Kocur，确定性模型中的调度延迟和出发时间决策，运输科学15（1981），pp. 62{77.[8] 希金斯，A.和E. Kozan，城市网络中的列车延误建模，交通科学 32（1998），pp. 346{357.[9] Nachtigall，K.，周期网络优化和固定间隔时间表“rLuft{undRaumfahrt，InstitutfurFlugfuhrung，Brauns chw eig，1998，《解释》。[10] S choll ， S. ， 在 我 的 记 忆 中 ，PNV ， ”Master'sthesis ， University ofKaiserlestern（2001）.[11] 苏尔湖和T.Mellouli，铁路运营控制系统的要求和设计，载：计算机辅助运输调度（1999）。[12] 苏尔湖和T. Mellouli，通过仿真和优化管理和预防铁路运输延误，在：运输系统优化的数学方法（2001），pp. 3{16.[13] van Egmond，R.，列车运行调度的一种代数方法，见：第八届计算机辅助运输调度国际会议论文集，柏林，2000，2001。
