Bat算法在交通网络设计问题中的应用

摘要

随着文明的发展，道路服务和交通网络发展规划的要求应运而生。在车辆数量不断增加的现代城市交通场景中，解决网络拥堵和最小化出行时间非常重要。这项工作是基于确定微观离散模型交通信号的最佳等待时间。该问题被描述为一个双层模型。上层通过减少交通信号的等待时间来优化出行时间，下层解决随机用户均衡问题。软计算技术，如遗传算法、蚁群优化和许多其他受生物学启发的技术，被证明对双层问题有很好的效果。本文利用Bat智能解决了交通网络的设计问题。结果与现有技术进行了比较。

1.导言

如今，越来越多的车辆对现代城市交通提出了挑战可能的网络。因此，寻找最优路径是交通优化问题的重要判据。但在许多情况下，道路交叉口是有限的或不可用的，或者也可能在特定的时间内，似乎较短的某一特定连接是不可用的或存在很大的争议。另一种有效的方法是优化交通信号的等待时间。这不仅可以节省车辆使用者宝贵的时间，还可以减少拥堵，提高道路安全，顺利推进医疗应急和行业需求。

随着文明的发展，对交通和道路网规划的需求步入正轨[1.]提出了一种求解连续变量胡克-吉夫斯技术的车辆平衡网络设计问题的方法。在1985年，josef Shefi [2.]通过城市网络一直作为两个竞争系统的突出模式。系统的用户说，司机，乘客或行人，努力以与运输系统相结合的不兼容性的方式行驶。此外，与旅行时间相关的这种不兼容是不一致的，并且在某种程度上取决于运输系统的使用情况。

阿尔索普[3.]为中型道路网设计互相一致的交通讯号设置及交通分配。海德克(4.]提出了一种线性约束近似模型，并将二层问题作为约束优化问题求解。

通过网络的哪条路径的旅行时间最短，这是无法理解的。我们可以得出结论，车辆使用者的反应是可以预测的，而不是听写的。受生物启发的技术已经证明在这种情况下能产生很好的效果。大自然以许多不寻常的形式、大小和形式提供了广泛的灵感属性。

塞兰和贝尔[5.]集成遗传算法、交通分配（使用TRANSYT进行评估）和交通控制（使用路径流量估计器（PFE）解决最小化问题），开发了GATRANSPFE来解决网络设计问题，并通过数值示例将其性能与相互一致（MC）解并排。与中问题的MC解决方案相比，性能指数（PI）提高了34%一代。KOH [6.]用微分求值法求解双层连续网络设计问题。Ozgur Basken和声纳Haldenbilen[7.]为了在交通优化问题的双层模型的信号设置问题中找到更好的信号配时，开发了一种ACO缩减搜索空间（ACORSS）。胡辉[8.]采用双层规划求解城市交通均衡网络设计问题，并采用粒子群算法和Frank-Wolfe算法求解。与模拟退火算法相比，该算法有效且迭代次数少，可以得到更好的解。斯里瓦斯塔瓦和萨哈纳[9,10]设计了一个离散的进化模型，以减少城市交通系统中车辆在交通信号灯处的等待时间，使用Stackelberg博弈模型5测试网络，使用Petri网设计了12、16、20、24、28个节点。为了优化交通信号的等待时间和SUE，解决了所提出的混合技术。混合算法的性能优于蚁群算法和遗传算法[11,12]还有很多人以前提出过离散模型，但大多数都是宏观仿真模型。建议的模型在道路网内的路段水平上工作，因此可以考虑各种微观困难。

杨新社[13–15]针对连续约束优化问题，受bat回声定位行为的启发，提出了一种元启发式方法bat算法（BA）。由于其鲁棒的参数控制特性和频率调谐能力，BA被发现比粒子群优化、遗传算法和和声搜索更强大。BA证明对许多优化问题都能给出很好的结果。基奥·科维茨和达米安·格雷拉[16]用于非线性优化问题。Abatari等人[17]提出了一种求解最佳功率流（OPF）问题的BA启发方法。Yassine Saji等人。[18利用BA解决离散旅行销售人员问题。

本文分为五个部分。第一部分介绍了本文并讨论了相关工作。部分2.给出问题制定。部分3.讨论了bat算法。部分4.介绍了研究方法和最后一节5.使用BA讨论3个测试用例及其解决方案。

2.问题制定

道路网络可以被视为有向图G=（N，a），其中“N”是节点集；即，道路交叉点“a”是连接交叉点的连接，如图所示1..对于每对始发地和目的地（O-D），存在非负的出行需求， ．道路网络可以作为强连接的图形，其中每个节点“i”通过遵循网络n的定向路径来通过另一节点“j”来访问。

我们假设连接节点的链路具有旅行时间函数 ,用于指定的流量 ．目的是选择合适的set链路从起点到终点，并减少每个路口的交通延误。在链路容量扩展的预算约束下，选择连续网络设计模型。这两个目标是相互依存的，可以表述为一个双层问题。上级负责减少指定出行者的出行时间。下层是交通分配模型，用于估计出行者流量。模型如图所示2.．

对于这两个层，该模型可按如下所示的数学公式表示。

上层函数 其中，A是网络N中所有链路A的集合。x（y）给出了用户平衡流量，该流量是根据链路容量y的分配值从模型的较低级别估计的。

是链接a的施工成本，B是预算。

低级别功能 其中f是路径k上的流，r-s是连接O-D对的路径上的节点。

3.Bat算法

Bat算法是一种创新技术，证明它比许多流行的传统算法和启发式算法提供更好的解决方案[9,10]用于解决复杂的工程问题。Bat算法基于微型卫星的回声定位。回声定位（回声定位）是一种由微型蝙蝠发出的迷人的声纳波；它帮助它们找到猎物，并且以某种神奇的方式，它们能够在完全黑暗的情况下辨别通往猎物的路上的各种障碍物或危险。如图所示3.．

蝙蝠发出响亮的超声波声波，并听取从周围物体反射的回声。BAT算法使用一些idolized规则以简便。(1)蝙蝠利用回声定位来感知猎物、捕食者或路径和距离上的任何障碍物。(2)蝙蝠用速度飞行位置 ．它们有频率f和响度达到他们的猎物。它们可以调整脉冲发射频率R。(3)当它们接近猎物时，脉冲增强，声音减弱。

数字4.呈现BAT算法的流程图。

4.研究方法

求解TNDP的投影方法是基于二层模型的。数字5.给出了求解该问题的一种广义解法。利用bat算法对上层目标函数进行求解，得到的解进一步用于下层目标函数的优化。

蝙蝠的频率 其中n是网络中的节点数。脉率和响度和在范围内变化 ．

5.结果和讨论

本文考虑了三组测试用例。一个是从[9,10].本文选取了5个网络。在本测试用例中未考虑预算约束。测试用例适用于自适应的16个链接问题20.]。这测试用例是基于Sioux Falls问题改编自[20.,21.]。

5.1.测试用例1

五个测试用例改编自[9,10]对应以下规格的五个不同网络：12节点网络，4个交叉口；16节点网络，6个交叉口；20节点网络，8个交叉口；24节点网络，10个交叉口；28节点网络，12个交叉口。图6.显示一个12节点网络，显示信号值。数字7.显示16-，20，24-和28节点网络。

BA的终止条件被视为100次迭代。通过实验在几个运行时间结果上建立该终止条件。使用带有额外功能的始终存在的额外功能等交叉点，如信号，信号值，链路上的旅行时间，连接的链路上的位置信息，以及其他延迟。

为了简化实施，保持问题的完整性，进行了某些假设。所选网络中的每个起点-终点对通过至少一个交叉点连接。随机生成下层统计信息，以模拟其作为上层输入的功能。表1.显示了在测试用例1中获得的目标函数值（OFV）的结果。

BA的结果与ACO、GA和混合ACO-GA进行权衡[9,10]。数字8.显示了算法的最佳解决方案。与其他三种算法相比，对于12、16和20个节点，BA的结果最好，但对于24个节点和28个节点，ACO和混合算法的性能优于BA。

数字9给出了四种算法中性能最差的一种。实验结果表明，混合算法的性能最好。在大多数情况下，与其他3种算法相比，BA给出了最差的解决方案。

数字10介绍ACO，GA，Hybrid ACO-GA和BA的平均解决方案。观察到杂交ACO-GA优于ACO，GA和BA。除了在许多情况下，它发现BA的平均等待时间高于其他技术，尽管它在许多情况下与其余的技术相比，它得到了最佳解决方案。

图中并列列出了蚁群算法、遗传算法、混合蚁群算法和BA四种算法的取值范围11可以观察到，BA探索了解决方案集的最高范围。

5.2.测试用例2:16链路网络

一些研究人员已经在多个网络上测试了连续网络设计问题的性能。Suwansirikul等人改编了一个广泛使用的6节点16链路网络[20.].测试网络如图所示12．

针对给定网络的不同需求场景，对3个测试用例执行连续网络设计问题。行程需求如表所示2.．

如表中所述，不同的研究人员使用几种技术（如传统的H-J、EDO、SA和CS）来估计16链路网络问题3.．表中给出了两种需求情景下BA的比较分析4.和5.．

5.3.测试案例3：苏福尔斯网络

一个更现实的道路网络数据来自位于美国南达科他州的苏福尔斯市。该网络更加复杂，对研究交通网络问题的研究人员具有吸引力[20.–24.]。它由24个节点和76条连接它们的链路组成。图形13显示从[20.]。测试数据适用于[20.].桌子6.显示了适用于BA比较分析的技术及其相应的参考文献。

苏福尔斯网络的结果如表所示7.图形14表明了苏瀑网络的BA收敛性。

6.结论

为各种尺寸的多种网络进行仿真工作，用于变体测试用例和多次。根据测试案例1的结果，可以得出结论，BA探讨了广泛的解决方案集，而不是GA，ACO和Hybrid Aco-Ga提供了更好的结果。虽然混合ACO-GA优于ACO，GA和BA的平均水溶液。在测试案例中的16个链接问题上比较了BA。在需求情景BA的表现优于MINOS、H-J和CS。虽然SA的结果比BA好，但解决的UE分配数比BA高出数倍。在需求场景BA的性能优于所有比较的技术，尽管CS在UE分配的数量上接近于预期结果。

在第三个测试用例中，BA与H-J、SA、GP、GA、CS、HS、ABC和DE进行比较。对于目标函数值的最佳解，BA优于所有提到的技术。对于HS、ABC和DE之间的平均值，BA给出了更高的目标函数值。BA的解的范围似乎更大。wors值给出了HS的t解，该解优于BA的最差解。在未来，可以对所提出的算法进行更多的改进，并可以实现以给出更好的解

数据可用性

用于支持本研究结果的数据可根据要求从相应作者处获得。

利益冲突

作者声明他们没有利益冲突。

工具书类

1. M. Abdulaal和L. J. LeBlanc：“连续均衡网络设计模型”运输研究第B部分：方法论，第13卷，第1期，第19-32页，1979年。视图:出版商网站|谷歌学术
2. 谢菲，“基于数学规划方法的城市交通网络的均衡分析”，出版交通工程控制，PRENTICE-HALL，1985年。视图:谷歌学术
3. R. E. Allsop和J.A.Charlesworth，“信号控路路网络中的流量：诱导不同途径的不同信号时序的示例”交通工程控制，卷。18，不。5，pp。262-265,1977。视图:谷歌学术
4. B.G.Heydecker和T.K.Khoo，《平衡网络设计问题》，年决策支持模型与方法会议论文集，pp.587-602，索伦托，意大利，1990。视图:谷歌学术
5. H.Ceylan和M.G.H.Bell，“基于遗传算法方法的交通信号配时优化，包括驾驶员路线，”运输研究第B部分：方法论，第38卷，第4期，第329-342页，2004年。视图:出版商网站|谷歌学术
6. A.Koh，“利用差异评估解决运输双层问题”，年IEEE进化计算大会论文集，第2243-2250页，2007年。视图:谷歌学术
7. Ozgur Baskan和Soner Haldenbilen，“蚁群优化方法优化交通信号时机”，在蚁群优化-方法与应用InTech,的哲理,2011。视图:谷歌学术
8. 胡浩，“基于粒子群算法的城市交通平衡网络设计”，《交通工程学报》，第2期第九届中国交通专业人士国际会议记录（ICCTP），第1-7页，中国哈尔滨，2009年。视图:出版商网站|谷歌学术
9. S.Srivastava和S.K.Sahana，“交通信号优化的嵌套混合进化模型”，年应用智能，第46卷，第1-11页，施普林格，2016。视图:谷歌学术
10. S. Srivastava, S. K. Sahana, D. Pant, P. Mahanti，“交通信号优化的混合微观离散进化模型”，下一代信息技术杂志，第6卷，第2期，第1-8页，2015年。视图:谷歌学术
11. G.E.Cantarella、G.Pavone和A.Vitetta，“城市道路网设计的启发式：车道布局和信号设置，”欧洲运筹学杂志，第175卷，第3期，1682-16952006页。视图:出版商网站|谷歌学术
12. G.E.Cantarella和A.Vitteta，“城市地区的多标准道路网设计问题，”运输，第33卷，第6期，第567-588页，2006年。视图:出版商网站|谷歌学术
13. 杨X-S，“一种新的元启发式蝙蝠启发算法”，年自然启发的优化合作战略（NICSO 2010），J.R.冈萨雷斯，D.A.佩尔塔，C.克鲁兹，G.特拉萨斯和N.克拉斯诺格编辑，第284卷，共页计算智能研究，第65-74页，德国柏林斯普林格，2010年。视图:出版商网站|谷歌学术
14. X. S. Yang，自然启发的综合算法，卢尼维尔出版社，英国弗洛姆，2010年，第二版。
15. Yang和A.H.Gandomi，“Bat算法：一种用于全局工程优化的新方法，”工程计算，第29卷，第5期，第464-483页，2012年。视图:出版商网站|谷歌学术
16. K.Kiełkowicz和D. Grela，“用于非线性优化的修改蝙蝠算法”计算机科学与网络安全国际期刊，卷。16，不。10,2016。视图:谷歌学术
17. H. Delkhosh Abatari, M. S. Abad，和H. Seifi，“蝙蝠优化算法在最优潮流中的应用”，在第24届伊朗电气工程会议论文集，ICEE 2016，pp.793-798，伊朗，2016年5月。视图:谷歌学术
18. Y.Saji、M.E.Riffi和B.Ahiod，“旅行商问题的离散蝙蝠启发算法”，年第二届世界复杂系统大会论文集，2014，pp.28-31，摩洛哥，2014年11月。视图:谷歌学术
19. C. Suwansirikul，T.L.Fiesz，以及R. L.托宾，“平衡分解优化：持续均衡网络设计问题的启发式，”交通科学，卷。21，不。4，pp。254-263,1987。视图:出版商网站|谷歌学术
20. T. L.弗里兹，h - j。“基于变分不等式约束的网络设计问题的模拟退火方法”，交通科学，卷。26，不。1，pp。18-26,1992。视图:出版商网站|谷歌学术
21. O.Baskan，“使用布谷鸟搜索算法和Lévy航班确定道路网络中的最佳链路容量扩展，”应用数学学报，第2013卷，文章编号718015，共11页，2013年。视图:出版商网站|谷歌学术
22. 邱绍伟，“连续运输网络设计问题的双层规划，”运输研究第B部分：方法论第39卷第3期4，页361 - 383,2005。视图:出版商网站|谷歌学术
23. T.V.Mathew和S.Sharma，“大型城市交通网络的容量扩张问题，”运输工程学报，第135卷，第7期，第406-415页，2009年。视图:出版商网站|谷歌学术
24. o. Baskan，“评估道路网络上最佳链路容量扩展的启发式方法”，“国际运输杂志，卷。2，不。1，pp。77-94,2014。视图:出版商网站|谷歌学术

版权

版权所有©2019 Sweta Srivastava和Sudip Kumar Sahana。这是一篇发布在知识共享署名许可协议，允许在任何媒介上不受限制地使用、传播和复制，但必须正确引用原作。