改进logit多路径分配模型及其求解算法研究

一种改进的多路径负载分配均衡算法
朱尚明; 高大启
【期刊名称】《《华东理工大学学报（自然科学版）》》
【年(卷),期】2007(033)001
【摘要】分析了实现均衡路由的功能模型和算法,重点研究了LDM(多路径负载分配)算法。

为了充分利用候选路径的信道容量,提出了一种改进的LDM算法。

改进后的算法在多个候选路径之间根据比例系数均衡分配通信流量。

通过算法性能分析表明:改进后的算法和最初的LDM算法具有相同的复杂度,但对于给定的通信流量能够提升网络性能。

【总页数】4页(P89-92)
【作者】朱尚明; 高大启
【作者单位】华东理工大学计算机科学与工程系上海 200237
【正文语种】中文
【中图分类】TP393
【相关文献】
1.一种实时的无线传感器网络能量均衡多路径路由算法 [J], 田玉昆;张海洋;孙正章
2.WDM网络中一种基于负载均衡的多路径路由算法 [J], 牛俊勇;杨君刚
3.一种无线多媒体传感器网络能量均衡多路径路由算法 [J], 孙毅;黄可心;刘浩程;陆俊
4.一种改进的多路径路由探测算法 [J], ZENG Fan-zhi;LI Wen-wei;WANG
Tao;WANG Zhi-ming
5.最宽不相交多路径均衡路由算法的改进及其分析 [J], 朱尚明; 高大启
因版权原因，仅展示原文概要，查看原文内容请购买。

基于有效路径的多路径交通流分配摘要：在城市道路交通网络中，任意起、讫点间的路径可能会有若干条，合理选取有效路径集合在随机交通分配中具有十分重要的地位。

本文首先介绍Logit路径选择模型；然后依次介绍了改进的Dial算法和基于图的遍历算法两种有效路径搜索算法；最后通过算例分析，结果表明基于图的遍历算法比前种算法更为有效。

关键词：交通分配；多路径；有效路径0 引言作为城市交通需求预测的关键性步骤，交通分配将预测得到的起讫点间的交通量，按现有或规划中路网分配到具体的道路上，以实现对规划设计方案路网流量的预测，对于城市交通系统的优化管理和控制具有重要意义[1]。

1 Logit路径选择模型该模型认为出行者在起讫点间众多路径中选用k路径的概率[2]为：2 有效出行路径搜索算法2.1 改进后的Dial算法该算法认为路段(i,j)是否位于有效路径上，只需当S(i)>S(j)时，路段(i,j)即位于有效路径上[3]。

2.2 基于图的遍历算法该算法认为如果OD间的路径k满足无环简单路径，且不允许走“回头路”；路径K上的路段(i,j)满足S(i)>S(j)；路径k的阻抗和最短路径阻抗的差值不允许超过规定阀值，即，则称路径k为有效路径[4]。

3 算例分析图1所示，连线上数字为路段阻抗（最小行驶时间/h）,节点1至5的交通量为1200（辆/h）。

图1交通网络图依据图1所示，可找出节点1至节点5的所有可行路径，并计算得出各路径阻抗，结果见表1。

表1节点1至5的所有无环简单路径和阻抗按改进后Dial算法对有效路径的定义，有效路径为路径1、路径2、路径3、路径4。

若按基于图的遍历算法，有效路径为路径1、路径2、路径4。

用Logit路径选择模型计算各路径的分配率（θ取值3.5），得出对应的交通流量分配情况。

根据改进Dial算法确定的有效路径集，计算对应有效路径的分配率，见表2。

有效路径流量分配表2改进Dial算法中节点1至5根据基于图的遍历算法确定的有效路径集，计算对应有效路径的分配率，见表3。

城市轨道交通客流分配的改进Logit模型及方法林湛;蒋明青;刘剑锋;四兵锋【摘要】In this paper, the major factors (including travel time, transfer time and transfer count) that impact the passenger' s route choice in urban rail transit network are fully considered. The generalized travel cost function is formulated and then the passenger' s route choice behaviour is analyzed based on the random utility theory. A Logit-based model is presented for urban rail transit network flow assignment problem. Simultaneously, a searching algorithm based on depth-first method is proposed to obtain the set of effective routes between 0D pair. On basis of these, the application of the model and algorithm is illustrated with Beijing rail transit network and practical data.%摘要; 充分考虑城市轨道交通网络中影响乘客路径选择的主要因素,包括乘车时间、换乘次数和换乘时间,通过对换乘时间进行惩罚,构造了包括换乘在内的城市轨道交通网络的路径广义费用模型,基于随机效用理论分析了乘客的路径选择行为.根据最短路径费用定义OD之间的有效路径集合,同时,使用路径相对费用代替路径绝对费用,对传统Logit模型进行改进,提出基于改进Logit模型的城市轨道交通网络客流分配方法.采用基于图的遍历算法确定OD间的有效路径.最后,以2008年北京市轨道交通网络为研究对象,对模型和算法进行了分析和验证.【期刊名称】《交通运输系统工程与信息》【年(卷),期】2012(012)006【总页数】7页(P145-151)【关键词】城市交通;客流分配;Logit模型;轨道交通;广义出行费用;路径选择【作者】林湛;蒋明青;刘剑锋;四兵锋【作者单位】北京交通大学交通运输学院,北京100044;北京交通大学交通运输学院,北京100044;北京交通发展研究中心,北京100055;北京交通大学交通运输学院,北京100044【正文语种】中文【中图分类】F570.7目前，针对城市道路交通网络，国内外专家学者提出了许多流量分配模型和算法[1-4]，而对城市轨道交通网络客流分配的研究相对较少，对城市轨道交通的研究主要集中在网络规划、运营组织和管理上[5-9].虽然有些学者试图将城市道路交通的配流方法应用在轨道交通网络中，如文献[10]基于用户平衡原理，建立了城市轨道交通网络的客流量平衡分配模型，并采用Frank-Wolfe算法对模型进行求解；文献[11]在分析乘客的交通选择行为的基础上，基于随机用户平衡理论构造了城市轨道交通网络的配流模型及算法；文献[12]提出了一种基于深度搜索优先和分支界定思想的有效路径搜索算法来确定城市轨道交通网络中OD对之间的有效路径.但直接采用这些方法来解决城市轨道交通网络的流量分配，存在较大问题.一方面，城市轨道交通与道路交通的流量分配有着明显的不同，例如，两者研究对象明显不同，前者研究的是基于乘客交通选择的客流分配，而后者研究的是基于车辆的车流分配；前者影响乘客路径选择的因素多且复杂，尤其是换乘因素对于乘客的路径选择具有重要影响，而后者通常只考虑时间因素.另一方面，在以前的这些研究中，一些关键问题还没有很好地解决，如轨道交通网络中不同线路之间换乘费用（包括换乘次数和换乘时间）的处理、最短路径的搜索算法等，而这些问题直接影响着城市轨道交通网络客流分配的效果.本文充分考虑影响乘客在轨道交通网络中路径选择的主要因素，包括乘车时间、换乘时间和换乘次数，并将换乘时间和换乘次数进行单独处理，构造路径广义效用模型，基于随机效用理论分析乘客的路径选择问题，并提出了基于改进Logit的城市轨道交通网络流量分配方法，并采用基于图的深度优先搜索算法来确定OD间的有效路径集合.最后，以2008年北京市地铁网络为研究对象，对模型和算法进行了测算分析.主要考虑乘车时间、换乘时间及换乘次数三个因素对乘客路径选择行为的影响. （1）乘车时间（如果在起始站，还包括等车时间）.表示线路l的列车在区间（i，j）上的行驶时间；表示乘客在起始车站i等待线路l 的列车进站的平均等车时间；表示线路l列车运行中在车站i的平均停车时间；乘客乘坐线路l在区间（i，j）的乘车时间可表示为（2）换乘时间.表示乘客在换乘站i从线路l到线路m进行换乘的步行时间；表示乘客在换乘车站i等待线路m的列车进站的平均等车时间；乘客在换乘站i从线路l换乘到线路m 的换乘时间可表示为根据出行心理，对于选择城市轨道交通出行的乘客而言，相同的时间花费在换乘过程中和花费在列车上的效果是不同的，乘客对前者的心理感觉要比后者长.因此，用换乘时间乘以一个换乘放大系数α（α＞1）表示由乘客的换乘心理感觉时间即（3）换乘次数.一般而言，随着换乘次数增加，乘客感知费用逐次递增.城市轨道交通出行路径上乘客换乘心理费用为每次换乘时间逐次放大处理得到的时间值.根据上面分析，提出城市轨道交通换乘费用模型乘客在OD对r-s间第k条路径上广义费用等于组成该路径的所有区间乘车时间、所有站点停车时间及换乘费用之和，即在城市轨道交通网络的出行中，乘客通常不会考虑OD间全部连通路径，而是将其中一部分路径作为选择方案，被出行者考虑的路径称为有效路径.通常，被乘客所考虑路径的费用应该在一定范围之内，假定为OD对r-s之间的最小路径费用，则r-s之间有效路径费用为大于或等于的某个范围内，即满足以下条件路径选择问题从行为科学上解释，就是一个决策制定问题.为了模拟乘客心理活动，可以为每条有效路径确定一个费用值，反映乘客选择某路径的综合费用.在实际中，该费用很难被直接观测和估计，影响路径费用值的因素还包括随机成分，因此，可以将路径费用看作随机变量.出行者选择OD对r-s间有效路径k∈Krs的随机费用乘客的路径选择问题是一个概率问题，即在城市轨道交通网络中，乘客以多大概率选择OD间的某条有效路径.这个选择概率就是该路径随机费用在所有可选路径中为最小的概率，这个概率也等价于在OD间所有的乘客中选择该路径的比例.即选择概率具有如下性质：以上分析可知，路径选择概率取决于随机误差项的随机分布，以及可确定路径费用.如果相互独立且服从Gumbel分布，路径选择概率可以表示为[3]采用基于路径配流方法解决城市轨道交通网络流量分配问题.算法具体步骤如下：步骤1对于网络OD对r-s，基于路径费用式（5），搜索最小费用路径，得出；步骤2根据有效路径式（6），寻找OD对r-s间的有效路径集合Krs，并记录各有效路径的费用；步骤3根据改进Logit模型式（10）计算OD对r-s间各有效路径的选择比例，k∈Krs；步骤4根据式（11）计算路径流量步骤5 根据，计算线路流量、区间流量及换乘流量以2008年北京市轨道交通网络为研究对象，对模型及算法进行了验算.网络结构如图1所示.相关数据及参数取值如下：①发车间隔，北京市现有轨道交通系统的平均发车间隔为5min；②乘客换乘步行时间，本算例中共有8个换乘站，各站的换乘走行时间如表1所示；③站间车辆运行时间，根据北京地铁公司网站公布的站间运行时间；④非换乘站的平均停车时间，取值为2min；⑤根据2008年9月完成的北京地铁乘客路径选择意愿调查数据（共有2 000份有效问卷），采用极大似然估计方法，对Logit模型参数进行回归分析，得出α=1.264 0，β=1.848 1，θ=1.866 0，而对于有效路径扩展系数，则根据经验取值为H=0.15；⑥在本算例中，为了验证计算效果，采用2008年某天的北京地铁网络OD数据作为输入数据.表2给出以苹果园—天通苑北为例的相应计算结果，输出数据包括有效路径上的换乘次数、乘车时间、路径总费用以及配流比例等.进一步对配流方法的效果进行分析，以北京地铁OD数据为输入，分别采用全有全无法及本文所提出的方法进行配流计算，并以2008年实测换乘流量为参考对象，对计算效果进行对比分析.图2给出了采用不同方法得到的各换乘流量与实际换乘流量之间的比较，可以看出，本文提出的配流方法比全有全无法计算结果更加接近实际.此外，由于模型和算法中涉及到许多变量和参数，这些数据作为已知条件，对于最终的配流结果也会产生影响，下面分别对参数α和β进行灵敏度分析，其目的是为了准确把握这两个参数发生变化时，网络客流的变化规律.假定其他条件不变，路径广义费用函数中α分别取值为1、1.5、2、2.5和3时，而β分别取0.5、1.0、1.5、2.0、2.5时，计算并分析客流分配结果的变化趋势.图3～图6分别给出了参数α和β分别取不同的值时，计算结果与实测数据的对比情况.参数α和β取不同的值对配流结果的影响比较明显，当β=1时，随着α取值从1到3，配流结果的相对误差从32％下降到25％；而当α=1时，随着β取值从0.5到2.5，配流结果的相对误差从37％下降到23％；这说明对换乘时间和换乘次数的惩罚程度会直接影响模型和算法的计算效果.在本算例中，当α=1和β=2.5、α=1.5和β=2.5、α =2和β=1.5及α=2和β=2几种组合计算效果最好.随着城市轨道交通的不断发展，轨道交通系统将由目前单线运营转变为网络运营，而网络运营中出现的客流非线性增长，以及所引起的乘客出行选择行为的变化，将对城市轨道交通的运营管理提出更高的要求.因此，从理论上研究城市轨道交通的客流分布规律，对于城市轨道交通多线路网络一体化运营和管理具有重要的意义. 本文在充分考虑影响城市轨道交通网络客流分配的主要因素，对换乘时间和换乘次数分别进行了分析，基于随机效用理论构造了城市轨道交通网络客流分配的改进Logit模型，给出了配流方法.并以北京地铁网络为例对模型和算法进行了说明.计算结果表明，本文所提出的模型及算法可行有效.当然，本文的配流方法还存在一些不足之处，没有考虑拥挤因素对乘客路径选择的影响，也没有考虑不同乘客属性对路径选择的影响等，而这些问题将在今后的研究中进一步完善.【相关文献】[1] Beckmann A B，McGuire C B，Winsten C B.Studies in the economics of transportation[R].Yale University Press，New Haven，Connecticut，1956.[2] McFadden D.Econometric models of probabilistic choice，in C.F.Manski andD.McFadden（eds.）， Structural analysis of discrete data with econometric applications[M].Cambridge，Massachusetts：MIT Press 1981.[3] Sheffi Y.Urban transportation networks：Equilibrium analysis withmathematical programmingmethods[M].Prentice-Hall，Englewood Cliffs，NJ 07632，1985.[4] Dial R B.Bicriterion traffic assignment：basic theory and elementaryalgorithms[J].Transportation Science， 1996（30）：93-111.[5] 王忠强，高世廉，降金琦.轨道交通路网规划若干问题探讨[J].西南交通大学学报，1999，34（3）：369-373.[WANG Z Q，GAO S L，JIANG J Q.Discussions on network planning of urban rail transit [J].Journal of Southwest Jiaotong University，1999， 34（3）：369-373.] [6] 王忠强，黎青松，陈旭梅.轨道交通路网基本图式研究[J].西南交通大学学报，2000，35（3）：288-292.[WANG ZQ，LIQS，CHEN XM.Research on fundamental pattern of urban rail transit network[J].Journal of Southwest Jiaotong University，2000，35（3）：288-292.][7] 顾保南，曹仲明.城市轨道交通路网结构研究[J].铁道学报，2000（S1）（增刊）：25-29.[GUB N， CAO ZM.Study on structure of urban railway network [J].Journal of China Railway Society，2000（S1）（Sup.）：25-29.][8] Wendler E.The scheduled waiting time on railway lines [J].Transportation Research，2007（41B）：148-158.[9] Rodriguez J.A constraint programmingmodel for realtime train scheduling at junctions[J].Transportation Research，2007（41B）：231-245.[10] 吴祥云，刘灿齐.轨道交通客流量均衡分配模型与算法[J].同济大学学报（自然科学版），2004，32（9）：1158-1162.[WU X Y，LIU C Q.Traffic equilibrium assignment model specially for urban railway network[J].Journal of Tongji University（Natural Science），2004，32（9）：1158-1162.][11] 四兵锋，毛保华，刘智丽.无缝换乘条件下城市轨道交通网络客流分配模型及算法[J].铁道学报，2007，29（6），12-18.[SIB F，MAO B H，LIU Z L.Passenger flow assignment model and algorithm for urban railway traffic network under the condition of seamlesstransfer[J].Journal of China Railway Society，2007，29（6），12-18.][12] 刘剑锋，孙福亮，柏赟，等.城市轨道交通乘客路径选择模型及算法[J].交通运输系统工程与信息，2009，9（2）：81-86.[LIU JF，SUN F L，BAI Y，et al.Passenger flow route assignmentmodel and algorithm for urban rail transit network[J].Journal of Transportation Systems Engineering and Information Technology，2009，9（2）：81-86.][13] 北京交通发展研究中心.北京轨道交通网络流量分配模型与算法研究报告[R].北京：北京交通大学， 2010.[Beijing TRC（Transportation Research Center）.Research on passenger flow assignmentmodel andmethod [R].Beijing：Beijing Jiaotong University，2010.]。

基于改进LOGIT模型的交通微观仿真动态分配方法
李辰;毛荣昌;孙宁
【期刊名称】《交通科技》
【年(卷),期】2004(000)002
【摘要】采用改进LOGIT模型作为路径选择模型,广义的出行成本作为交通阻抗,对交通微观仿真系统中发出的车辆进行动态分配,实现路网的随机用户均衡配流.【总页数】4页(P52-55)
【作者】李辰;毛荣昌;孙宁
【作者单位】河海大学交通与海洋工程学院,南京,210098;河海大学交通与海洋工程学院,南京,210098;河海大学交通与海洋工程学院,南京,210098
【正文语种】中文
【中图分类】TP3
【相关文献】
1.基于动态广义费用的客运通道交通方式选择Logit模型 [J], 孙启鹏;朱磊;陈波
2.城市轨道交通客流分配的改进Logit模型及方法 [J], 林湛;蒋明青;刘剑锋;四兵锋
3.基于Logit模型的动态交通分配研究 [J], 温凯歌;曲仕茹
4.基于Logit分配的交通网络设计模型的改进粒子群算法 [J], 刘炳全;孙广才
5.基于动态博弈的行人交通微观仿真模型 [J], 李得伟;韩宝明;张琦
因版权原因，仅展示原文概要，查看原文内容请购买。

第46卷　第5期2007年　9月中山大学学报(自然科学版)ACT A S C I E NTI A RUM NAT URAL I U M UN I V ERSI T ATI S S UNY ATSE N I Vol 146　No 15Sep 1　2007一种改进的Logit 型多路径交通分配算法3辛松歆,李　军(中山大学工学院,广东广州510275)摘　要:提出了一种改进的基于拓扑遍历Logit 型多路径交通分配算法。

算法将基于拓扑遍历的最短路算法与合理路径的选择相结合,有效减少了最短路的计算次数,提出了与经典D ial 算法的单步法计算工作量相等的算法,改进了合理路径的定义并提高了计算精度。

通过计算实例对不同算法的效率与合理性进行了比较。

关键词:交通工程;Logit 型交通分配;D ial 算法;拓扑遍历;最短路径中图分类号:U11612 文献标识码:A 文章编号:052926579(2007)0520029204 随机交通分配可以反映出行者对不同路径的认识误差,分析出行者对不同路径的选择概率,从而对出行者的路径选择行为进行分析。

Pr obit 型随机交通分配模型目前只能用仿真的方法来进行,难以获得出行者对不同路径的选择概率;而Logit 型随机交通分配模型由于存在分析算法,可以针对不同要求进行有效的分析,特别是对出行者的动态选择行为分析极为有用,因而得到了研究者广泛的重视。

文献[1]对基于D ial 算法[2]的Logit 交通分配方法进行改进,使其可以应用于动态交通分配中,利用D ial 算法的高效性提高了动态交通分配算法的效率。

但因为D ial 算法缺陷的存在[3],限制了Logit 模型在实际中的应用。

Bell 、Aka matsu等人提出了全路径Logit 模型[3-5],但模型求解效率却比较低且不能保证收敛[6]。

文献[7]通过改进D ial 算法中计算顺序的不合理性并放松对“合理路径”的定义,提出了一种基于拓扑遍历的Logit 交通分配算法。

基于改进的Logit型随机用户平衡分配模型及算法研究基于改进的Logit型随机用户平衡分配模型及算法研究摘要：在旅游行业中，用户平衡分配是一个重要的问题。

本文通过改进Logit型随机用户平衡分配模型以及设计相应的算法来解决这个问题。

首先，对现有的Logit型随机用户平衡分配模型进行分析，并发现其在应对复杂场景时存在一定的不足。

然后，我们基于用户行为和偏好的特点提出了改进的模型，以更好地适应各种应用场景。

接着，我们设计了相应的算法，并进行了实验验证。

实验结果表明，改进后的模型和算法在用户平衡分配问题上取得了显著的改进效果。

1. 引言用户平衡分配问题在旅游行业中非常常见和重要。

在旅游资源有限的情况下，如何合理地分配资源给不同的用户群体，以满足他们的需求和提高他们的满意度成为了一个挑战。

现有的用户平衡分配模型大多基于Logit模型，但是在复杂的应用场景下存在一定的问题。

2. Logit型随机用户平衡分配模型在旅游行业中，用户的行为和偏好对资源的选择有着重要的影响。

Logit型随机用户平衡分配模型是根据用户的选择概率设计的，可以用于预测用户选择某个资源的概率。

该模型的基本思想是通过建立用户偏好函数，结合资源的属性和用户行为数据，计算每个用户选择每个资源的概率。

3. 模型改进然而，现有的Logit型随机用户平衡分配模型在复杂的场景下存在一定的问题。

首先，现有模型忽略了用户之间的相互影响，没有考虑到社交网络和用户关系的作用。

其次，在算法设计上，现有模型在计算用户选择概率时存在一定的局限性，不能很好地适应不同用户偏好和行为的变化。

为了解决上述问题，我们在现有模型的基础上进行了改进。

首先，我们引入了社交网络和用户关系因素，考虑用户之间的相互影响和信息传播的作用。

其次，我们将用户选择概率的计算过程优化为一个优化问题，通过迭代的方式逐步调整用户选择概率，以适应不同用户偏好和行为的变化。

4. 算法设计与实验验证在模型改进的基础上，我们设计了相应的算法。

基于综合运输网络的logit多路径分配模型的求解算法研究摘要:在综合运输路网中增加虚拟的节点和虚拟路段,将交通方式间的转运(换乘)延误当做路段阻抗处理,通过使用现有的交通分配模型和算法去处理带有转向延误(换乘)的交通问题。

关键词:Dial算法拓扑结构转向延误Abstract:Increasing the virtual nodes and sections in the comprehensive transportation network, treating transshipment (change) as road impedance processing, through the use of existing traffic distribution model and algorithm to dealing with turned to delay (change) the traffic problem.Key words:Dial algorithm topological structure Turn delay1 问题的提出交通的分配是交通四阶段法的最后一步,但也是最关键的一步,如何将OD量准确的分配到路段上成为人们关注的对象。

在实现Logit随机网络模型加载的过程中,Dial算法是一种相当有效的算法,但是Dial算法无法正确的处理需要考虑转向延误(或转运费用)的OD加载工作,主要表现在:①无法考虑节点的延误函数对流量分配的影响②不需要路径枚举,但也无法直接得到节点的转运流量[1]。

Dial算法存在上述的不足,本质就是无法对节点的转向延误函数进行考虑,这在综合路网中体现在无法处理枢纽的转运延误(费用),为此任刚(2005)提出了基于转向的Logit型加载算法,既能考虑转向延误对流量分配的影响,又能求得转向流量,同时也避免了路径的枚举。

在本文之前就有论文在交通分配的过程中涉及到了转向延误[2][3],但是本文主要是从改造综合运输网络拓扑结构入手,在路网中增加虚拟的节点和虚拟路段,将方式间的转运或换乘延误当做路段阻抗处理,这样我们就可以通过使用现有的交通分配模型和算法去处理带有转向延误(换乘)的交通问题。