黄宇达， 魏霞,2， 赵红专， 王迤冉

(1. 周口职业技术学院 信息工程学院， 周口 466000； 2. 三峡大学 理学院， 宜昌 443002;3. 重庆大学 自动化学院， 重庆 400044； 4. 周口师范学院 网络工程学院， 周口 466000)

一种基于通信膜计算的拥堵道路收费模型

黄宇达1， 魏霞1,2， 赵红专3， 王迤冉4

(1. 周口职业技术学院 信息工程学院， 周口 466000； 2. 三峡大学 理学院， 宜昌 443002;3. 重庆大学 自动化学院， 重庆 400044； 4. 周口师范学院 网络工程学院， 周口 466000)

针对城市交通拥堵问题，提出了一种利用并行通信膜计算原理的拥堵道路使用收费模型(CMC_ DTAM)。在考虑拥堵收费的情况下，建立了出行者的出行决策算法，出行者在交通膜计算中动态进化，外部可以通过调整收费参数来影响出行者决策，进而影响整个系统进化。对CMC_ DTAM模型进行了仿真并将该模型与基于粒子群算法的拥堵收费模型(PSO_ DTAM)在同一参数条件下进行了比较，仿真实验结果不仅验证了前者的有效性和可行性，而且表明了前者由于考虑了出行者的动态决策，故相对后者则更为符合客观真实情况。

智能运输系统与交通工程； 道路收费动态模型； 通信膜计算； 拥堵道路使用收费； 出行者决策； 交通选择算法

0 引言

中国近年来小轿车的家庭拥有量快速增长，导致连一些三四线城市的某些路段在上下班高锋时也出现交通拥堵[1]。而通过扩展道路设施不但投入大，而且周期长。因此需要转变思路，寻求其它可能的缓解交通拥挤办法[2]。如果城市路段在某些时段出现交通严重拥挤，可以考虑通过拥挤道路使用收费 (congested road-use pricing)来达到缓解交通拥挤的目的。拥挤道路使用收费是通过对道路使用者收取一定的费用，让一些不愿意出这些费用的出行者改变出行时间或改变行程[3]。每个出行者都只会考虑自己的方便程度，或者考虑自己付出的经济和时间成本。当道路通行通畅的时候，这些行为不会影响到其它出行者，但当道路通行接近或到达极限时，就势必会影响到其它出行者。实行道路使用收费后交通缓解的程度，或者收费价格的多少等问题都需要通过建模来进行模拟。

目前，一些不同学科的学者从各种角度分析研究了道路拥堵问题，比如Rosenthal[4]从非合作博弈理论分析说明了纳什均衡解的存在性对拥塞的影响；Levinson[5]用非合作博弈理论从微观层面角度分析城市交通拥堵，研究了发生交通拥堵的条件和拥堵收费是作为一种合作机制，决定最小化出行总成本；张毅媚等[6]用经济学理论和方法研究了城市交通挤塞情况的发生机制；许薇等[7]利用博弈论中的“公共地悲剧”理论模型对汽车拥有量增多与城市路网容量短缺问题进行了系统分析，说明了交通拥堵产生的根源；刘志刚等[8]用基于博弈论分析“囚徒困境”问题的方法分析了城市交通拥挤；吴兵等[9]认为交通出行是衍生的需求的博弈过程，分别用演化博弈理论分析了动态交通弹性和非弹性出行需求条件；曾鹦等[10]从合作博弈角度对城市道路拥堵网络问题进行了分析；何南等[11]分析讨论了道路建设或扩大诱增交通流量；赵柴厚等[12]应用粒子群优化算法和动态交通流分配理论，建立了一种系统动态拥堵收费策略的系统算法，但没有考虑出行者中改变出行路径的情况，这不符合真实情况。拥挤道路使用收费会让一些不急于在上下班高峰期时段出门的出行者改变出行时间或者出行者不愿意缴纳拥堵费而不得不改变经过路段。

膜计算(又称为P系统)是从细胞及从细胞组成的组织或器官的结构和功能受到启发而抽象出的一种计算模式，作为如今自然计算的一个新分支和较为活跃的智能计算研究领域之一，其不仅为计算机科学引入了一种新的并行分布式处理技术和方法，而且为计算困难问题的求解开辟了新途径，同时为生物系统的仿真建模提供了新工具。通信膜计算是膜计算在通信相关领域中的进一步应用及研究。

本文将从出行者和交通流通量两方面考虑，利用通信膜计算原理建立拥挤道路收费动态演化模型，并进行了仿真实验。仿真结果与文献[12]所提出的用粒子群优化算法进行动态拥堵策略收费模型(PSO_DTAM)进行了对比分析，验证了模型的有效性并进一步揭示出在不同时段收费和不同路段收费时的交通流量的变化规律。

1 通信膜计算优化算法

1.1 出行者决策选择算法

出行者决策基于如下思想：出行者会根据拥堵收费指标进行决策，这些拥堵收费指标变量会带来正倾向，也会带来负倾向，当拥堵收费指标变量超过某个临界值，出行者则会作出“是”的出行决定，或作出“否”的出行决定。现在有3个方面的问题需要解决：

(1) 综合倾向如何表达？

(2) 收费的临界值如何选取？

(3) 个体决策的概率如何计算？

(1)

在公式(1)中，ui是随机扰动项，在本文中指道路拥堵收费指标，式(1)也称为潜回归方程，其中

(2)

如果给定ui～F(·)随机扰动项的分布，那么可以确定出行者的决策概率。推导如式(3)。

(3)

1.2 通信膜计算

1998年，罗马尼亚科学家Gheorghe Paun在芬兰Turku Center for Computer Science的交流研究报告中首次提出膜计算的思想，并于2000年发表了论文“Computing with membranes”[13]。随后，在学术界引起一部分研究者的兴趣。从2003年开始，膜计算研讨会每年召开一次；膜计算(membrane computation，MC)具有分布式计算和并行计算的特点，它是通过模拟生物细胞的机理来模拟进化，膜计算具有类似于细胞膜性质的层次结构[14]。膜计算与其它智能优化算法结合会得到更好的优化效果，例如，黄亮等将基因算法和膜计算相结合，在搜索区域内进行收缩和扩展[15]；潘林强等利用了活动膜的膜计算结构求解了0-1背包问题[16]；Nishida求解TSP问题时，将问题空间分成一个个膜(区域)，在有的区域内使用禁忌搜索算法，有的区域内使用遗传算法，并与模拟退火算法比较，得到较好的优化结果[17]。

通信膜计算(Membrane system with symport/antiport rules)应用共运输、对运输规则，在膜内部，对象不会生成、改变、消失，只允许对象在膜之间进行转移，膜与膜之间的规则与膜中的对象集合相关，决定该线路相连的两点，即规则与线路相关联，抽象到图型结构则，如图1所示。

图1 图型结构

通信膜计算是树型结构[15,18-21]。

基于膜系统的结构[19]，通信膜计算的形式化表示如式(4)。

∏=(O,E,μ,w1,…，wm,(R1,ρ1),…,(Rm,ρm),i0)

(4)

其中，O里面的元素一般称为对象，是字符表集合；E⊆O表示对象的集合，可以在膜环境中进行无限拷贝；μ表示系统膜结构，H为标号集(有m个膜)，表示各个膜及其所围的区域，H={1,2,…,m}，其中m称为Π的度；wi∈O*(1≤i≤m)表示在膜i中对象的多重集合，O*是字符串的集合，由O中字符组成的任意字符串；i0(1≤i0≤n)，是表示在运算结束后的最后留下的那个输出膜，为一个基膜。

用n+1元组(μ,wi,…,wn)来表示膜计算的初始状态，通信膜计算的执行方式如下：通信膜计算内部不能产生新对象，只能从环境中运输进来新的对象进来，这里用符号集E表示，理论上可以运输无限个对象进来，也就有可能得到无限大的运算结果；膜计算的计算过程是由初始状态经过的一系列状态转换，计算是否成功的标记是没有规则可以被使用的状态，而且，通信膜计算下不存在膜消散的情况。图2是一个包含四个膜的通信膜计算示例图，如图2所示。

图2 通信膜计算

通过该示例对通信膜计算过程进行具体说明。

在图2中，1、2 、3、4和5为膜的标号，基本膜的含义是不包含其它膜，例如膜4；标号为2的膜结构称为普通膜；表层膜是表示外面没有其它膜，是最外层的膜，例如膜5；膜内所包含的范围称为区域，区域内有属于该区域的对象，这些对象规定了本区域内的进化规则。膜计算利用区域中的对象和对应的进化规定进行，计算过程如下：

(2) 个体的出行到2的成本由膜1中的催化剂β′来表示，ui代表拥堵收费，系统的进化规则如下：例如在膜2，规则b→β′b3在催化剂β的作用下将对象bi运输到区域3，如果膜3中的对象集的个数等于某个指定临界值，或到达指定的进化代数，则计算停止。

1.3 通信膜计算交通选择算法模型(CMC)

通信膜计算利用膜系统内部的信息生成、传递以及处理规则来构建交通选择算法。具体来说，CMC算法迭代步骤如下：

第一步：初始化。随机各个膜(区域)给定初始化种群，设定对象集的大小，最大运行代数，变量数等运行参数；

第二步：膜进化。给定每个膜内ui内的参数和出行成本的参数，每个膜同时进化，膜内规则不分先后次序使用；

第三步：各个膜根据每个膜的交流规则彼此交换它们的一些对象；

第四步：如果满足某个时间段交换的数量大于饱和容量ca，算法终止，重新调整ui的参数，回到第三步。ui参数是指影响出行者的随机扰动项(也指拥堵收费值)，其决定出行者作出“是”或“否”的行为，该参数动态可调，将影响整个系统的演化发展；

第五步：用运行预先指定的进化代数来停止，也可以根据实际情况来确定，例如当某个路段或时段的交通流量值达到预先满意的结果。

2 数值算例

选用有7个节点，包含3个起点，1个终点，11条路段的一个小型的路网作为算例，作为算例的路网结构，如图3所示。

图3 路网结构图

假定收费路段的收费上下限分别为：0≤ua≤10，出行时间采用BPR函数形式为式(5)。

(5)

式(5)中是路段a上的个体自由选择的时间；ca为路段a的容量；α，β为系数，取值分别为0.15和4。

可以用N来表示路段a上的出行量，采用公式(6)计算，表示为式(6)。

(6)

在式(6)中，A(p,ca)和B(p,ca)xa是与出行决策概率p和路段a的饱和容量ca相关的常数。ui为道路拥堵时的收费值，初始值随机给定，路网的基本输入参数见表1所示。

表1 路网的输入参数

在系统演化过程中，为了防止过多地将字符串进入到同一个膜(区域)中，可以限制对象的最大重复数为膜内对象规模的1/3。经过一定时间进化后，计算得到道路拥堵收费ui如表2所示。

为了比较两种算法模型的优缺点，这里将基于膜计算的拥堵收费模型(CMC_ DTAM)与基于粒子群算法的拥堵收费模型(PSO_ DTAM)在同一条件下进行比较， 结果如表3、图4所示。

表2 道路费表

表3 不同的算法模型比较

注：PSO_DTAM数据引用文献[1]

图4 收费模型在三种收费费率下的路径总流量对比

其中表3部分数据引用文献[12]。从实验结果不难发现：在考虑收费的情况下，前者对应3种收费费率情况下的路径总流量都分别低于后者，当然前者所对应的3种收费费率情况下的车辆平均延误也都分别低于后者，说明前者由于考虑了出行者决策，则更加符合实际交通运行情况，因为实行收费以后有的出行者改变路线或者改变时间出行，以使得道路交通流量下降，如图5所示。

3 总结

本文利用膜计算建立了一种拥挤道路收费模型及其演化算法，选取有7个节点，包含3个起点，1个终点，11条路段的一个具有一定代表性的小型路网作为算例，考虑拥堵收费后交通流量变化问题，以及路网收费高低的问题进行建模，通过仿真计算与同类算法进行了比较，验证了这个用并行通信膜计算理论建立下的道路拥挤收费模型的有效性和可行性。通过与基于粒子群算法的拥堵收费模型(PSO_ DTAM)在相同参数条件下进行对比分析，结果表明本文建立的模型与实际交通拥堵情况更为符合。到目前为止，膜计算在智能控制、NP难题、智能医疗等领域已有部分应用，但还比较初步。膜计算应用于交通拥堵收费建模计算是膜计算应用的一种尝试，同时也给一些相关研究者提供了一种新的思路。膜计算作为一种相对较新的优化算法，将该智能计算方法与其它智能算法相结合，深入探讨各种混合膜计算的优化方法，并进一步开展在其他相关领域的应用研究，将作为笔者下一步主要研究方向。

图5 收费模型在三种收费费率下的车辆平均延误对比

[1] 熊伟.考虑排放的交通分配模型及其算法研究 [D].武汉：武汉理工大学 ,2008.

[2] 崔红建.城市交通结构优化机理与方法研究[D]. 西安:长安大学,2010.

[3] 吴艳. 关于征收道路拥堵费的思考[J]. 产业与科技论坛,2011,10(17):60-63.

[4] Rosenthal R W． A Class of Games Possessing Pure-strategy Nash Equilibria[J]． International Journal of Game Theory，1973，2( 1) : 65-67．

[5] Levinson D． Micro-foundations of congestion and pricing: a game theory perspective[J]． Transportation Research (Part A)，2005，39: 691-704．

[6] 张毅媚，晏克非．城市交通拥挤机理的经济解析[J]．同济大学学报( 自然科学版) ， 2006， 34( 3) : 359-362．

[7] 许薇，贾元华．城市道路交通拥堵问题的博弈分析[J]．交通科技，2006，2: 80-82．

[8] 刘志刚，申金升．城市交通拥堵问题的博弈分析[J]．城市交通，2005，2: 63-65．

[9] 吴兵，李林波．交通拥堵的进化动态分析[J]．中国公路学报，2006，19(3): 106-110.

[10] 曾鹦，李军．合作博弈视角下城市道路交通拥堵收费研究[J]. 运筹与管理. 2013,22(1):9-14.

[11] 何南，赵胜川．道路诱增交通量及其相关交通政策的解决方法[J].交通科技. 2013,257(2) :143-146.

[12] 赵柴厚，刘伟铭．基于粒子群优化的求解城市动态拥堵收费费率策略的模拟算法[J].科学技术与工程，2008,8 (10).

[13] Gh. Paun. Computing with Membranes [J].Journal of Computer and System Sciences，2000, 1(61):108-143.

[14] Huang L,He X X,Wang N. Membrane Systems Based on Multi-objective optimization algorithm[J]. Progress in Natural Science，2007，17(4):458-465

[15] 黄亮.膜计算优化方法研究[D]. 杭州:浙江大学,2007.

[16] Pan L, C. Martin. Solving Multidimensional 0-1 knapsaek Problem by Systems with Input and Active Membranes[J]. Journal of Parallel and Distributed Computing，2005，65(12):1578-1584

[17] Nishida T Y. An Application of Membrane system: A new Algorithm for NP-complete Optimization Problems[A]∥Proceeding of 8th world Multi- conference on Systems[C]. Orlando: Cybernetics and Informatics， 2004:18-21.

[18] 艾淼. 膜计算模型中若干运算的研究及仿真实现[D]. 哈尔滨：哈尔滨工业大学，2010.

[19] 张葛祥. 自然计算的新分支——膜计算[J]. 计算机学报,2010.33(2):208-214.

[20] Paun A， Paun G. The Power of Communication: Membrane Systems with Symport/Antipart[J]. New Generation Computing, 2002, 20(3):295-305.

[21] Gexiang Zhang, Marian Gheorghe, Chaozhong Wu. A Quantum-Inspired Evolutionary Algorithm Based on Membrane Systems for Knapsack Problem [J]. Fundamentals Informatics.2008, 87(l):93-116.

Pricing Model for Congestion Road Based on Membrane Computing

Huang Yuda1, Wei Xia1,2, Zhao Hongzhuan3, Wang Yiran4

(1. Information and Engineering College， Zhoukou Vocational and Technical College，ZhouKou 466000， China；2. College of Science, China Three Gorges University, Yichang 443002， China;3. ChongQing University，College of Automation，ChongQing 400044， China；4. College of Network Engineering， Zhoukou Normal University， ZhouKou 466001， China)

For urban traffic congestion problem, a congested road-use pricing model based on the theory of parallel communication membrane computing is proposed. Considering congestion charges, the travel decision algorithm of travelers is established, travelers dynamic evolution is given in traffic membrane system, In the outside, the charging parameters can be adjusted so as to influence the decision of the traveler, and then affect the whole system evolution. The CMC_ DTAM model is simulated, and is compared with the congestion pricing model based on the particle swarm algorithm (PSO_ DTAM) in the same parameters, the simulation results not only verify the validity and feasibility of the former, but also show because the former considers the dynamic decision of the traveller, it is more consistent with the objective reality.

Intelligent transportation system and traffic engineering; Dynamic model of road charge; Communication membrane computing; Congested road use charging; Traveler decision-making; Traffic selection algorithm

国家自然科学基金(61103143)；河南省科技计划项目(112300410307)

黄宇达(1975-)，男，河南周口人，硕士，副教授，研究方向：交通信息化，智能计算，智能算法分析. 魏霞(1978-)，女，河南周口人，硕士，讲师，研究方向：人工智能与模式识别. 王迤冉(1976-)，男，河南周口人，硕士，副教授，研究方向：人工智能，自动化技术. 赵红专(1985-)，广西桂林人，博士研究生，研究方向：自动化技术及应用.

1007-757X(2017)04-0004-05

TP18； U491

A

2016.09.29)