文摘

交通网络设计问题包括确定一定数量的航线操作在市区平衡乘客和运营商的成本。在本文中,我们同时确定每个路由的路由结构和路线的数量在最后的解决方案。小说最初的路径集生成算法和路由设置大小交替启发式嵌入nondominated排序遗传algorithm-II——(NSGA-II)近似的基础解决方案框架产生帕累托。最初的路径集生成算法旨在生成高质量的初始解决方案成功优化程序。探索解空间和与一个不同的数字解决方案的路线,路线设置大小交替启发式发达改变路线的数量在溶液中通过添加或删除一个路线。实验进行Mandl网络和四大芒福德的网络。与一个固定的路线设置大小的方法,提出了NSGA-II-based解决方案方法可以产生一个近似帕累托前质量更高的解决方案以及提高了计算效率。

1。介绍

其次是频率设置,时间表发展,总线调度,和司机安排,交通网络设计问题(TNDP) [1)旨在确定一组线路运营在市区平衡乘客和运营商的成本。接下来的四个阶段的性能高度依赖于交通网络设计的结果的质量。因此,TNDP不断学习在过去的五年。称为TNDP np难问题,是一个困难的组合优化问题,甚至其最优解是很难找到使用超级计算机。

尽管关注TNDP,确定一个合适的路线(或范围)为一个特定的网络却没有得到足够关注。路线设置的交通网络设计是一个重要的参数大小,因为以下原因。首先,路线设置大小隐式地反映了总路径长度,直接影响燃料成本,公共交通的里程和其他操作成本。第二,之间有一个权衡路线设置大小和平均旅行时间,这是一个重要的交通网络性能指标。更大的路线设置大小通常表示更直接的为乘客服务。优化路由设置的大小会导致解决方案与广泛的运营商成本和旅客成本之间的权衡的水平。

Pattnaik et al。2)提出了一个变量的字符串长度编码方法路线设置大小决定连同路线。同样,汤姆和汉(3)合并路线设置大小的变化在编码解决交通网络路由和频率设置问题。然而,提到研究暗示两个局限性:(i)最优路线组只有一个大的子集组候选人候选人路径生成算法生成的路线。这个方法不适合大型网络作为候选路线组尺度与网络规模成倍增长。(2)合成模型只能给每运行一个答案。为了解决这些问题,在这项工作中,我们考虑路线作为一个内生变量的数量和变化在寻找近似帕累托。换句话说,一套路线大小交替启发式NSGA-II一起用于解决同时TNDP和路线设置大小确定问题。

对目标函数,大多数以前的研究(2- - - - - -9]采用加权和的方法来实现不同的目标(即。的加权和运营商成本和旅客成本)。这种方法可以实现一个相对良好的平衡之间的客运成本和操作成本。然而,一套合适的权重的确定通常需要许多实验,这是耗费时间,获得的权重的适用性可能会有所不同从网络到网络。此外,一些研究人员(10- - - - - -18)走到TNDP通过考虑运营商成本或客运成本作为唯一目的是优化。因此,考虑到目标的冲突的性质,获得最优解可能不是实际从其他利益相关者的角度。因此,在这项工作中,我们试图产生一个近似帕累托面前,可以选择所需的解决方案的决策者。

本研究的主要贡献是3倍:(a)一个初始的发展路径集生成算法生成高质量的初始TNDP解决方案;(b)的建议路线设置大小交替启发式替代路线的数量在一个解决方案在优化过程;和(c)的说明建议的解决方案方法的适用性与不同尺度的五个网络。

本文的其余部分组织如下。节2,我们审查现有的工作路线设置初始化和优化方法。节中描述的交通网络设计问题3。部分4阐述了提出初始路径集生成算法和路由设置大小交替启发式。部分5给出了数值结果,我们得出的结论部分6。

2。文献综述

TNDP典型的解决方法包括两个部分:一个初始化程序和优化算法。在本节中,我们从这两个角度系统地回顾相关工作。

2.1。初始化过程

大多数初始化过程可以分为两类:初始路线集生成和候选路径集生成。一个路线集由一个预定义的停止序列可用于定义一个交通网络。是我们的工作重点交通路由问题,有趣的读者对其他交通网络规划问题可以参考Guihaire和郝19],Kepaptsoglou和Karlaftis [20.),Farahani et al。21),阿贝丁et al。22),刘和转让人(23]。

Lampkin和Saalmans24]首先设计了一个启发式算法生成路由组。他们制作了四个节点和骨架的一个接一个可接受的节点插入骨架路线根据预定义的标准,直到获得一个完整的路线。每次插入后,形成需求满意的路线将以指导过程中被淘汰掉。这个框架的构建路线开发初始路径生成算法通过Baaj和Mahmassani5]。Mandl [25]接近城市运输路由问题两个步骤:首先把所有的最短路径连接每一个术语叫做一对被发现产生可行的初始路线集,然后用启发式改进初始路线集的质量。与交通需求的考虑,Baaj和Mahmassani5)设计了一个路线生成算法(RGA)来生成初始路线集。具体地说,高需求选择节点对定义初始骨架在设计师的帮助。一旦骨架被指定,他们进军路线节点选择或插入策略。算法还可以生成不同的航线有不同的乘客和运营商之间的权衡成本。灵感来自RGA [5),Mauttone和厄克特26)提出了另一条路线生成算法称为插入算法。他们使用了新颖的策略插入双节点,而不是最初的扩张路线通过插入单个顶点。他们报告的实验结果证明,对插入算法可以产生更好的解决方案从运营商的角度来看具有相似质量从乘客的角度。

为了避免先定义一个骨架,Chakroborty和Wivedi12)确定每个路线,首先选择起始节点,然后将相邻节点添加到前节点直到满足终止条件。选择一个节点的概率我是由活动水平计算基于旅行来自节点的数量我并从节点我。同样,芒福德(27)构建第一个通过添加相邻节点路由到一个随机选择的开始节点和启动其他路线以同样的方式使用开始节点用于先前生成的路线。Kechagiopoulos和Beligiannis13和欧维斯和奥斯曼28)提出了初始路线集生成一个类似的过程。而不是随机选择节点,尼克里奇和Teodorovic16)开发了一个确定性程序初始路由设置的一代。他们总是生成初始解的选择最短路径的最大数量的乘客享受直接服务到路线生成的数量等于一个预定义的号码。最近,科里奇和完全懂得14)制定一组初始路由过程基于边缘使用统计数据。统计数据是通过计算得到的所有最短路径图,然后计算边缘使用分数基于总交通经过一个边缘。每条边分数加权的逆边的长度和规范化。归一化值设置为离散型概率的优势。每个路线然后扩大通过选择相邻的边缘与预定义的概率。他们的方法改善发表结果芒福德的更大的网络。

在最初的路线设置生成过程中,需要多个初始路径集以人群为基础的优化方法。候选人路线生成方法生成一组候选路线。风扇和Machemehl [7]和风扇和Machemehl [29日)修改日圆的k-shortest路径算法(30.)生成所有可行的路线的距离满足所有非零的最小和最大的长度约束求解算法的需求。同样,Arbex和达(31日)生成路线数据库:为每一对叫做零旅游需求,相关的OD路径对应于理想的最短旅行时间直接添加到数据库作为公交路线,连同那些旅行时间的路线的时间最多不超过最快的路线绕道因素指定的计划。此外,Cipriani et al。6)开发了一种启发式算法来生成三个不同的和补充的理性和现实的路线。一组候选路线是由使用牛顿引力理论和一种特殊的最短路径过程(10]。在Afandizadeh et al。4),路径长度(即在一个理想的极限。,travel time up to 1.2 shortest path travel time) are selected as initial paths. The best subset of the large candidate route set is selected by an optimization procedure.

2.2。优化算法

生成一组初始路线后,启发式或metaheuristics-based优化算法是用来提高解决方案的质量,例如,遗传算法(GA),模拟退火,蜜蜂蜂群算法,人工蜜蜂殖民地,粒子群优化,遗传algorithm-II nondominated排序,禁忌搜索,迷因算法,微分进化,选择hyperheuristics。对候选路线设置方法,最常用的算法是遗传算法。

GA与七个遗传算子提出旨在促进搜索在合理的时间内(8]。在两个阶段:模型设计公交线路路由改进算法利用遗传算子和协调发展来提高网络的效率。结果表明,该模型比二进制编码遗传算法更有效的基准。风扇和Machemehl [7)开发了一种遗传算法选择一组最优的路线从候选路线组解空间。数值结果表明,遗传算法优于局部搜索方法与多个起始点并提供没有糟糕的解决方案比模拟退火和禁忌搜索质量。Cipriani et al。6)提出了一种并行遗传算法寻找一组次优的路线与频率有关。数值实验进行罗马城市的网络显示,可以提供有效的运输需求通过总线网络组成的较低的行数。咀嚼et al。32)开发了一种遗传算法解决biobjective交通路由问题。Mandl网络的计算结果表明,该算法比以前更好的执行最好的结果发表在大多数情况下。Afandizadeh et al。4)应用遗传算法的城市马什哈德,结果表明高效的改进的旅行时间和机队规模。长子et al。15与精英主义)开发了一种遗传算法,优化满足乘客的大小,服务乘客的总旅行时间,并转移的总数。欧维斯和奥斯曼(28)提出了一种遗传算法解决多目标交通网络设计问题通过优化平均旅行时间和所需的公共汽车舰队。

此外,风扇和Machemehl [29日)首次使用模拟退火算法来解决最优公交交通路线在节点级别分布网络设计问题。赵(33)提出了一种基于模拟退火的随机局部搜索方法和快速搜索。数值实验表明,该方法能够解决大规模交通网络设计优化问题,在合理的时间内生产的结果。之后,赵和曾庆红(18)开发了一种metaheuristic搜索方案,结合了模拟退火,禁忌,和贪婪搜索优化运输航线网络结构的方法,汽车进展,和时间表。科里奇和完全懂得14应用爬山算法和禁忌搜索算法,分别在交通网络设计问题。芒福德的四大网络实验结果显示改进结果在芒福德(27]。

在过去的十年中,尼克里奇和Teodorovic16)设计了一个蜜蜂殖民地交通网络设计的优化算法。该算法使用一个相似的蜜蜂在自然界中寻找食物和优化算法的方式寻找一个最佳的组合优化问题。数值实验进行Mandl的网络和一个更大的实例表明,BCO算法与其他方法在文献中有竞争力,它可以生成高质量的解决方案。Szeto和江34)开发了一种混合人工蜂群算法来解决交通路线和频率设计问题。迷因算法(MA)是最近越来越进化计算算法。赵et al。35马)开发了一个算法来设计最优路由配置和服务频率为城市交通网络。马与传统算法相比,所获得的结果表明,该算法可以提高计算性能。Kechagiopoulos和Beligiannis13)开发了一个基于粒子群优化的优化算法。

最近,雅司病和李36应用微分进化算法和多目标交通路由问题的修复机制。数值实验进行Mandl芒福德的网络和四大网络(27]。雅司病和李37)提出了一个混合微分进化粒子群优化设计运输网络结构和相关频率。计算结果表明改进在大多数以前的研究结果。艾哈迈德et al。38)评估一组的性能选择hyperheuristics总线网络的路由设计问题,目标是减少乘客的旅行时间和运营商的成本。

3所示。问题定义

交通网络设计问题(TNDP)可以被定义为一个无向图 和旅游需求矩阵D。V顶点的集合吗 代表预定义上车或下车点。E边的设置吗 站直接运输顶点之间的边。每条边 与旅游有关的时间吗 表示必要的车辆旅行时间从顶点我到顶点j。( ,如果 )。旅游需求矩阵 给每一对顶点之间的旅游需求;表示从顶点旅行每个时间单位的数量我到顶点j。一个路由r可以表示为一个序列相邻顶点吗 。解集由一组路线 。让 子图相应的路由设置R,在那里 路线的顶点集合吗R(|r|是顶点的数量节点序列r)。 表示的集合的边缘路线和 。比较我们的结果与现有的结果,本研究主要关注的是一代的路线集和叶子的频率设置问题未来的研究。

从乘客的角度,旅游时间和数量的转移是主要问题。平均旅行时间丙氨酸(包括车辆旅行时间和传输损失)是选为乘客服务水平的指标来描述成本。因为平均旅行时间包括转移成本、隐式地包含在转移的数量丙氨酸。从乘客的角度目标函数定义如下: 在哪里表示从顶点旅行每个时间单位的数量我到顶点j。p是表示不便的转移成本的车辆从一个到另一个地方,然后呢 代表从顶点的最短旅行时间我到顶点j通过使用路由设置R。是与以前的研究一致,转移成本p是设置为5分钟4,6,16,27,32]。比较我们的结果与现有结果发表,我们假设乘客总是选择最短路径到达目的地。

从运营商的角度来看,所有航线的长度之和路线机队规模成正比,这是一个重要的组件的操作成本(26]。因此,总路径长度(实验室)的一套路线作为一个代理。目标函数从运营商的角度给出如下: 在哪里 代表路线的长度r。

在数学上,这种优化问题可以表示为

约束(5每个路线的)顶点的数量限制。约束(6)确保所有顶点V可以找到至少一个路线。约束(7)确保每个顶点可及于其他顶点定义的子图R(36]。约束(8)确保每个节点最多只能访问的路线。回想一下路线被描述为一个节点序列 ,在哪里问表示节点的节点序列的数量 。约束(9连续)确保所有顶点连接现有的优势( )。路线的独特性r在R确保通过路由组的定义R。

4所示。解决方法

4.1。总体解决方案框架

发达的解决方案的方法,构造一种新型初始路线集生成算法产生高质量的初始路径集,而路由设置大小交替开发启发式切换路线设置大小通过添加或删除整个解决方案的路线。这两个算法嵌入到框架NSGA-II搜索近似帕累托前面的操作符(即成本。,总路径长度,实验室)和客运成本(即。平均旅行时间,丙氨酸)。

多个高质量的初始解决方案是首先由最初的路径集生成算法。图1介绍了拟议中的初始路线集算法的流程图。然后两个客观值计算的初始,每个初始解的适应度评估解决方案。和所有最初的解决方案被认为是父母和用于生成通过遗传算子(即后代。、选择、交叉和变异算子)。在这项工作中,应用程序的交叉算子生成唯一的后代。因此,解决方案的后代的数量仍然是一样的父母。突变后,路由设置大小交替应用启发式后代改变路线的后代的数量通过添加/删除如果解决方案质量没有提高一个预定义的后代的数量。为了选择下一代的个体,NSGA-II随后应用于父母和后代。对于NSGA-II广泛调查,读者被称为Deb et al。39]。重复这个过程,直到满足停止条件。

需要以下三个数据集来执行路由算法组合(RCA): (i)初始候选路线集(包含所有最短路径)用P;(2)交通需求的路线,用每个候选人 ;和(iii)的求解算法为每个候选路线和用P_d。注意,由于需求和旅行时间的对称性,只使用三角形元素。

4.2。初始路径集生成算法

拟议中的初始路线集生成算法是基于观察直接最大化可以满足旅游需求的(没有转移)是一个关键的组件生成的一组初始路线。该算法包括两个过程:吸收和组合。算法是基于组合的路线,它叫做RCA。这些程序生成一个初始路由设置基于以下参数:SP,D,G。SP包含所有最短路径连接的每一个术语叫做一对。G是无向图。一个例子中,一个图形和一个矩阵D用于说明初始路径集生成算法如图2。相邻的数字代表了旅行时间在几分钟内的链接。

表1给出了数据结构,需要生成一个初始路线集,第二列给例子中所有顶点之间的最短路径图。OD对的最短路径第三列所示。和最后一列包含旅游需求直接由每个最短路径。例如,对于第二个路由表1最短路径(1、2、3)从顶点1开始,经过顶点2,终止在顶点3。这条路是一对OD的旅游需求(1 - 3)。

4.2.1。准备吸收过程

如果路线是完全包含在另一个路线,我们认为这条路线可以被另一个路线。吸收的基本原则是消除路线是完全包含在另一条路线。通过这样做,路线的数量R而总路径长度可以有效降低了。吸收过程由四个步骤组成:步骤1。排序的路线R每个订单数量的顶点的路线。的路线,没有需求被排除。让米路线的总数R并设置米= 1。例如,表的路线1排序和给定的图吗3(一个)。尤其是第三路线(1、4)表1取消,因为它没有需求。步骤2。找到所有的路线(除了路线米),能吸收的路线米。让问组可以吸收路线的路线米。如果米=米,停止;否则,进入步骤3。步骤3。如果问是空的,米=米+ 1,返回步骤2;否则,根据旅游需求的路线问,一个概率任命为每个路线问的概率,反映了每个路由选择的路线来吸收路线米。选择路径的概率问通过计算 步骤4。使用轮盘赌选择法选择路线问基于概率的值 。一旦路线选择吸收的路线米ODs和要求的路线米被分配到的路线问。然后,我们需要删除路线米从R并返回到步骤2。

吸收过程的一个例子是图所示3。在图3(一个),第一个路线(1、2)是完全包含在路线6(1、2、3),即第一个路线是吸收路线6和旅游需求的第一个路线可以提供路线6。因此,我们需要消除第一个路线R。

在图3 (b),第二条路线(2,3)可吸收三个路线(路线6、8和9)。根据方程(10),的概率选择三个路线6,8和9是0.5,0.375,和0.125,分别。假设选择路线6。然后,ODs(2 - 3)和(4)要求的路线2分配给路线6。提出了图3 (c)路线6服务三个ODs(1 - 2、1 - 3、2 - 3)和总需求是12。在以下步骤中,路线3、4和5是吸收路线8日9日和7,分别。

从图3,可以看出路线R从9 - 4却降低了,但每个路由服务旅游需求增加。在吸收过程中,3∗路线选择高要求作为下列程序输入数据集,的路线是一个解集(预定义的根据表吗2)。

4.2.2。结合过程

结合过程旨在构建新航线与双路线R。组合过程的基本原理是将双通道高要求。通过这种方式,我们可以同时减少线路的数量,增加旅游需求的一个路线。在构建新航线之前,对路线选择。一条航线的选择依赖于两个通道之间的关系。根据顶点的位置由两个路线,共享两种途径之间的关系可以分为6种类型。图4显示了六个类型及其组合的结果。

如果两种路线分为1、2、3或5,那么这两个路线可以组合。结合过程由五个步骤组成:步骤1。排序的路线R按照降序排列基于每个路线的交通需求。让米路线的总数R并设置米= 1。例如,路线在图3排序和给定的图吗5(一个)。步骤2。找到所有的路线(除了路线米),可以结合路线米。让Z的路线集可以结合路线米。如果米=米,则跳转到步骤5;否则,进入步骤3。步骤3。如果Z是空的,米=米+ 1,返回步骤2;否则,根据旅游需求的路线Z,一个概率分发给每个路线z和描述每个路线的概率被选中的路线结合路线米。选择路径的概率z是计算 步骤4。使用轮盘赌选择法选择路线Z基于概率的值 。一旦路线z被选中时,路线米和路线z根据图组合成一个新的路线4。新的路由服务的旅游需求和ODs路线。然后,我们应该删除路线米和z从R并返回到步骤2。步骤5。再次排序路线R按照降序排列的每个路线的交通需求。最初的路线形成的第一个(一套路线路线的数量)可行的路线R。检查使用设定的初始路线的可行性可行性检查部分中描述4.3。

一个例子使用的输出组合过程吸收的例子是图所示5。首先,路线按降序排序根据旅游需求服务直接由每个路线。第一个路线之间的关系和其他路线的决心,也就是说,路线1和2分为1型,路线1和3属于1型,和路线1和4是2型。借助方程(11),选择这三个路线的概率是0.36,0.33和0.30。我们假设路线2是选择结合路线1,根据构造图和新途径4。应该注意的是,由新路线的需求增加了一倍。的总路径长度R也从36分钟减少到34分钟。路线的数量也从4减少到3,如图5 (b)。同样,在图5 (b)路线1和2相结合。

从图5并不少见,不仅路线的数量R从4减少到2,而且每个路由服务旅游需求增加。因此,结合过程的结果可以作为初始路由优化算法。

4.3。可行性检查

TNDP是multiconstrained问题,应该仔细检查的可行性解决方案。灵感来自[27,31日),我们建议的可行性检查详细如下:(1)路线可行性检查:检查如果每个路线是可行的,也就是说,没有重复的顶点出现在路线,路线的顶点数量必须在一个预定义的范围。(2)路线唯一性检查:如果一个路线是一样的一段另一条路线,或另一个完整的路线,我们认为这条路nonunique。因此,这条路直接淘汰。(3)区域范围检查:检查是否所有的顶点出现在解集至少一次。这个过程构造一个appeared-vertex通过搜索列表的所有路线和检查每个顶点出现在列表中。(4)网络连接检查:这个程序的目的是确定线路是否连接到交通网络。

可行性检查后,修复机制应用于修复不可行的解决方案。应该注意的是,生成的初始解决方案总是可行的前两个可行性检查。只有不可行初始解决方案失败的区域范围检查修理。其他不可行的解决方案(网络连通性检查)只是丢弃在初始解决方案生成和初始路径集生成算法又被称为。修复机制的初步解决方案描述如下。

修复机制的随机选择的路由解决方案,然后应用插入操作。插入操作构造一组候选节点通过搜索所有位置和检查的存在之间的边缘(原点图)的使用和未使用的节点修改路线,然后随机选择的一个候选节点,并将其插入到路线。重复上述过程,直到所有节点可以在路由设置。如果有节点不能插入到初始路线集,这个方案就会被丢弃。请注意,这个过程也适用于输出解决方案路线的设置大小交替启发式。

4.4。线路运营商

由于路线设置的复杂结构,一个交叉和三个变异算子的设计是为了方便代的后代。

路线交叉算子是发达在两个人之间交换两种途径。每个单独的一代被选中作为第一个家长。第二个父母是随机决定的。然后,两条路径从每个父母是随机决定和交换。

三个变异算子,即序列、插入和删除变异算子,提出了本研究变异个体的航线结构。具体来说,开发序列变异算子来取代一个随机序列的一个路线kth最短路径。插入变异算子,将要检查所有线路的位置,以确定是否存在一个顶点,可以连接到两个相邻顶点的路只有两条边。然后,将随机选择一个合适的顶点并插入到路线。比较,删除变异算子构造一个候选顶点列表和随机删除一个顶点。

前交叉/变异操作,交叉/变异的结果将检查路线可行性和独特性。如果这些检查返回true,交叉/变异。前两个检查所有的解决方案是可行的。毕竟解决方案通过交叉和变异,最后两个可行性检查儿童执行解决方案。

如果不满意,区域范围约束孩子的路线方案选择的解决方案,然后插入操作。插入操作构造一组候选节点通过搜索所有位置和检查的存在之间的边缘(原点图)的使用和未使用的节点修改路线,然后随机选择的一个候选节点,并将其插入到路线。重复上述过程,直到所有未使用的节点插入。如果有节点不能插入到孩子的解决方案,这孩子的解决方案是被其母所取代。

如果孩子的解决方案是定义的子图不连接,由母公司代替孩子解决方案。

4.5。路线设置大小交替启发式

如前所述,路线设置规模被认为是一个内生变量。因此,对于每个个体,存活到下一代,血统的路线设置大小交替启发式是用来改变路线组大小。以确保效率和安全的潜在的个人,只有那些没有改善为预定义的后代(本文中设置为5)将通过这种启发式方法。该路线设置大小交替启发式包括两个过程:路由添加和删除。为每一个选定的路线,路线添加或删除路由与相同的概率随机选择。检查解决方案通过这种启发式方法对区域范围约束和修复在必要的时候使用一节中描述的修复机制4.3。如果解决方案不可行的修复后,所做的更改路线设置大小交替启发式的。这种启发式的过程详细如下。

4.5.1。路线之外

为每个路由设置R,偏差率计算每一个非零交通需求估计旅行的质量。然后,OD对选择较低的服务质量。最后,尼克里奇提出的贪婪算法和Teodorovic [16)是用来确定最合适的路径添加到路由设置R。

顶点之间的质量指标为乘客我和j定义如下:

使用线路R,这代表了一个偏差率最低的旅行时间从理论最佳值(仅依赖于道路网络G)。全有全无分配法计算通过使用一个方法,然后呢的车载旅行时间最短路径G顶点之间我和j。根据这个公式,较低的值是理想的。然后,OD对的高价值是不能很好地服务。这些OD对的集合可以如下:

OD对的最高价值 用于生成最合适的路线。这条路线是通过连接这OD对的最短路径。这条路线插入R,我们可以增加的百分比与零转移满足旅游需求。

4.5.2。路线删除

路线删除过程提出删除一个路线的路线R。这个过程是基于每个旅游需求的分配分析。删除程序工作方式以下的路线。为每个路由设置R执行路由选择删除程序,删除的路线从路线集至少影响当前路线设置决定的质量。然后,这条路线应该从路线设置中删除R。分析的基础上的分配每个交通需求,每一个路线分配重量 ,它反映了每个路线的重要性。这个重量是计算如下: 在哪里往返时间的路线 。 从顶点是交通需求单位时间吗我到顶点j。代表了车载途中旅行时间为乘客旅行之间的顶点我和j。的价值得到如下:(1)如果有一个顶点之间的直接服务我和j使用路由 ,的值是车载旅行时间。(2)如果顶点之间的乘客我和j不能完成他们的旅行只有路线 ,的值是车载旅行时间从登机/降落停止传输站的路线 。(3)如果顶点之间的乘客我和j可以完成他们的行程没有路线 ,的值为0。

这个定义有重大影响:(i)更多的乘客和车载旅行途中花费的时间更长意味着更多的贡献权重 ;(2)路线的重量路线长度时迅速减少增加。重量计算方法后,最不重要的路线确定且远离设定的路线R。

5。实验结果

说明提出的初始路径集生成算法的有效性并展示路线设置的有效性大小交替启发式解决方案质量,在本节中,各种实验,这些解决方案系统与现有结果公布。提出的算法是网络上Mandl基准测试(25和四大实例芒福德27]。表2这五个网络的简要描述。满足需求的解决方案评估的百分比与0,1,2转移(d₀,d₁,d₂),不满足需求的百分比(d_联合国),平均旅行时间(丙氨酸),以及总路径长度(实验室)。所有的实验都是上执行一个标准的电脑,有一个英特尔酷睿i5 - 3470和3.20 GHz和8 GB RAM芯片。

一代的个体数量设置为20。所有四个路线的概率运营商设置为1 / |R1 / | |R|、0.005和0.005。NSGA-II终止时的近似帕累托方面没有提高100代。

5.1。的影响提出初始路径集生成算法

说明提出的初始路径集生成算法的有效性,我们比较我们最初的解决方案与报告Mandl初始解决方案的网络(25和芒福德的大型网络27]。

5.1.1。Mandl的网络

在本节中,我们比较我们最初的解决方案与报告初步解决方案在尼克里奇和Teodorovic [14,16]Mandl的网络。最初的路径集,包含4,6,7,8路线Mandl的网络。其他初始化程序中提到的文献综述不是相比,因为他们的方法产生的初始解决方案并没有在他们的作品。二维空间上的解决方案策划定义的目标(丙氨酸和实验室)。尼克里奇和Teodorovic[注意4-route解决方案16不像这不是可行的策划。

在图6可以看出,该算法获得的最初的解决方案有小的值丙氨酸有小的值,而其他解决方案实验室。贪婪算法有更好的权衡的结果方面的目标函数值。然而,贪婪算法只能产生一个特定的网络解决方案和|R|因为它不含随机化。贪婪算法可能不适合人群为基础的优化算法需要多个不同初始解决方案。

表3Mandl比较我们最初的解决方案的网络与其他方法的六个参数(例如,d₀,d₁,d₂,d_联合国,丙氨酸,实验室)。可以看出,最初的解决方案通过RCA有更好的价值丙氨酸比的尼克里奇和Teodorovic [16)和科里奇和完全懂得14]。尼克里奇和Teodorovic 4-route解决方案16)有一个小丙氨酸。然而,6.96%的需求是不满意的解决方案。另一方面,尼克里奇和Teodorovic最初的解决方案16)和科里奇和完全懂得14)的值较低实验室。初始路径集,路线|的数量的增加R|有直接影响的值丙氨酸和实验室。例如,当|R|从4到8,增加的价值丙氨酸的解决方案通过RCA逐渐减少从11.01到10.12,而实验室值从116增加到259。应该注意的是,的值d₂和d_联合国在所有最初的解决方案通过RCA为零。这表明所有的乘客最多只能到达目的地,一个转移。

5.1.2中。芒福德的网络

在本节中,我们进一步比较芒福德我们最初的解决方案的大型网络与现有的初步解决方案(14]。相比其他初始化程序不,因为最初的解决方案的方法是没有报告在他们的作品。我们还在芒福德(情节最后的解决方案27)和科里奇和完全懂得14四大网络。

在图7,该算法生成的初始解决方案比其他初始解决方案方面的目标。该算法生成的初始解决方案类似实验室值,丙氨酸我们的结果通常小于初始值解决方案科里奇和完全懂得14]。注意,对于网络Mumford2和网络Mumford3,最初的解决方案由该算法在芒福德(甚至比最终的解决方案27)和科里奇和完全懂得14),这意味着该初始路线集生成算法可以产生高质量的大型网络的初步解决方案。网络Mumford3,一些最初的解决方案由科里奇和完全懂得14]也主导芒福德(产生的最终解决方案27]。最初的解决方案用于芒福德(27)是随机生成的,鼓励覆盖率和航线网络的连通性。初始路线集生成算法的重要性可能会被忽视。

我们进一步比较初始解决方案科里奇和完全懂得14芒福德的网络),我们的六个参数(例如,d₀,d₁,d₂,d_联合国,丙氨酸,实验室)。结果是集成和展示在表4。路线的数量在一个解决方案是设置为推荐值表2。

从结果表4可以看出,RCA比获得的解决方案通过科里奇和完全懂得的14)的目标(例如,丙氨酸和实验室)。解决方案相比科里奇和完全懂得14的解决方案通过RCA),四个网络可以减少丙氨酸8.23%、8.10%、6.46%和5.88%,分别和减少实验室6.92%、24.06%、6.07%和9.12%,分别。这些结果表明,RCA可以显著提高大型网络的初始解的质量与提出的初始过程相比科里奇和完全懂得14]。因此,RCA用于以下实验生成高质量的初始解决方案优化过程。

我们也比较报告的计算时间科里奇和完全懂得40和我们进一步显示该算法的优越性。相应的结果中描述表5。尽管数据结构和子程序的差异,可以看出,RCA是非常有效的,因为它只需要3秒产生一个初始解决方案(即最大的网络。Mumford3)。相反,网络Mumford3科里奇的计算时间和完全懂得14是8小时。RCA所需的计算资源可以忽略不计。

5.2。设置大小交替启发式效果的途径

这个实验比较了近似从NSGA-II获得帕累托方面有和没有路线设置大小交替启发式。尽可能公平的比较,变量的NSGA-II |R|从相同的初始解NSGA-II固定|R|在表2(Mandl网络|R| = 6)。

5.2.1。Mandl的网络

数据8(一个)- - - - - -8 (e)比较的结果NSGA-II |与变量R|和固定|R|。立即观察是近似帕累托方面都非常接近。当|R|增加,最好的丙氨酸按预期值降低,而相应的实验室价值增加。| NSGA-II的变量R|的理论最佳值丙氨酸当|达到(10.0058)R| = 19,所有乘客可以旅行的最短路径。这是第一次一个交通网络理论丙氨酸提出了Mandl的网络。

此外,图8 (f)比较近似从NSGA-II获得帕累托面前,没有路线设置大小交替启发式。近似与固定|帕累托面前R|通过比较获得的所有近似与|帕累托方面R| | = 4R| = 8。可以看出,与变量NSGA-II |R|执行以及NSGA-II固定|R|。这表明NSGA-II |与变量R|导致相同的解决方案的质量解决方案获得固定|R|。此外,NSGA-II |与变量R|可以产生一个近似帕累托与更广泛的前两个目标之间的权衡。

表6总结了每个NSGA-II的计算时间。注意,计算时间是衡量每个NSGA-II所产生的后代的数量。如表所示6与变量| NSGA-II的计算时间R|相对接近的NSGA-II固定|R|。然而,获得不同的值的近似帕累托方面|R与固定| |,NSGA-IIR|必须执行许多次|的不同的值R|。因此,固定|R|方法,总的计算时间随着|的可能值的数量R|增加。这表明路线设置大小交替启发式可以节省大量的计算时间没有恶化的质量接近帕累托面前。

5.2.2。芒福德的网络

评估我们的路线的优点集大小交替启发式,我们运行的优化算法芒福德的四个网络相同的初始解决方案。做一个公平的比较,每个NSGA-II 3000代生产时终止。|的固定值R|是芒福德(设置为推荐值27]。结果绘制在图二维空间定义为这两个目标9。

在图9,第一次观察到两条曲线在某点联系。联合点代表最好的解决方案与预定义的|从乘客的角度来看R|。操作员与固定|最好的解决方案R| |由结果与主导变量R| Mumford0除了解决方案。具体地说,网络Mumford0(即。,图9(一个)),解决方案与固定|R|配合其它曲线的下方;网络Mumford1(即。,图9 (b)),近似帕累托固定|面前R| |是重叠的变量R|在上半部分。如图9 (c),几乎没有重叠的解决方案。一个有趣的观察数据9 (c)和9 (d)是重叠的解决方案定位上曲线的一部分,而不是在中间区域。这是一个大|的结果R|,也强化了的想法,很难选择一个合适的|RTNDP |最好的解决方案。

通常,NSGA-II固定|R|可以产生高质量的解决方案,但大多数这些解决方案是由解决方案与一个小|R|。因此,NSGA-II固定|R|需要多次执行|的不同的值R|生产相同近似帕累托前| NSGA-II与生成的变量R|。然而,当网络规模增长,一个解决方案的评估将花费大量的时间,和有更多的值|R|搜索。因此,决策者是被迫妥协的解决方案质量和计算资源。注意,所有的结果是由单个NSGA-II的运行。

表7芒福德的网络进一步介绍了计算时间。计算时间与变量|R|通常比的固定|R| |因为NSGA-II变量R|与大|搜索解空间R|值比推荐值。产生相同的帕累托面前,NSGA-II固定|R|是|运行很多次不同的输入值R|。总计算时间尺度与|的范围R|。在实践中,NSGA-II变量|R|更容易实现。

5.3。与现有的发表结果比较

进一步证明该算法的可行性和有效性,我们系统地比较最终的解决方案与现有结果发表Mandl网络和芒福德的大型网络。

5.3.1。Mandl的网络

在图10,我们比较Mandl最终解决方案的网络与以前公布的结果在风扇和芒福德(41],芒福德[27),咀嚼et al。32),尼克里奇和Teodorovic16),科里奇和完全懂得40),科里奇和完全懂得14),科里奇(42),约翰et al。43],Kechagiopoulos和Beligiannis [13),艾哈迈德et al。38雅司病,和李36),和雅司病和李37]。近似的帕累托科里奇(42)和约翰•et al。(43]绘制在图10通过私人交流了。

从图10,可以看出我们的结果取决于不同|的价值R|有竞争力与其他结果。一般来说,我们的研究结果非常类似于组合近似帕累托在科里奇(42),结果在约翰et al。43]。的丙氨酸我们最好的8-route解决方案是10.09,几乎是一样的丙氨酸尼克里奇和Teodorovic中的值16(即。,10。09)和艾哈迈德et al。38(即。,10。08)。然而,他们的实验室值,分别为288和272分钟,比我们大得多(即。233分钟)。表8和9分别比较详细的解决方案的性能指标图10从乘客的角度和运营商。

在表8,我们比较我们的结果与前研究的d₀,d₁,d₂,d_联合国,丙氨酸,实验室。提出的解决方案的选择我们的工作获得近似帕累托前| NSGA-II生成的变量R|。的实验室尼克里奇和Teodorovic[的价值观16]和Kechagiopoulos Beligiannis [13)是通过我们的评估函数,因为他们没有报告这些值。

从表8建议的解决方案方法优于大多数前的结果。的丙氨酸值的方法非常接近最小丙氨酸在四种情况下的值。4-route解决方案,最好的丙氨酸(通过Ahmed et al。38])是10.48比我们略小(即。10.56)。然而,我们的解决方案有一个小得多的实验室值(即。,124)when compared with the result (i.e., 148) in Ahmed et al. [38]。6-route解决方案,最好的丙氨酸(通过雅司病和李36])是10.16,比我们略小(即。10.19)。不同的是不到1%。相反,实验室我们的解决方案是195(即。,比223年低12%)。从乘客的角度来看,我们的解决方案的方法与其他方法在文献中具有竞争力。

在现有12个研究上面提到的,只有芒福德(27),咀嚼et al。32),约翰et al。43),科里奇和完全懂得14雅司病,和李36],艾哈迈德et al。38从运营商的角度来看)报道最好的解决方案。因此,提高兼容性,我们比较我们的结果与现有文献[14,27,32,36,38,43)表9。记得|R|不是预定义值。因此,只有一个最佳解决方案从运营商的角度(在表格的最后一列9)。所以,我们从NSGA-II固定|补充的最佳解决方案R|在图8。

与固定的结果提出NSGA-II |R比其他文学|更令人印象深刻。我们的运营商的成本接近的下界实验室。这是因为我们的搜索算法的目标是寻找近似帕累托面前,而不是优化客运和/或运营商成本。一般来说,最好的实验室值的结果略大于下界实验室(即。,12%). The best result for operator obtained from NSGA-II with variable |R|只包含3路线。

5.3.2。芒福德的网络

图11比较了近似得到帕累托前与最近发表的结果在芒福德(芒福德的更大的网络27),科里奇和完全懂得14),科里奇(42),约翰et al。43雅司病,和李36),长子et al。15],艾哈迈德et al。38]。约翰获得的近似方面等。43)和科里奇(42)获得通过私人通信。请注意,长子的结果等。15)获得的评估报告的最终解决方案的工作(网络Mumford1)的唯一可行路径集。

从图11,可以看出网络Mumford0,前面有一个很大的重复与前得到结果。当网络规模的增长,前面和前获得的结果之间的差距变大。这意味着我们的方法对大型网络的优势。近似帕累托方面获得我们的方法比其他结果覆盖面积较大,因为|R|不是预定义值。表10和11总结的具体性能指标最好的解决方案从乘客和运营商在图11。

在表10从乘客的角度,我们比较我们的结果与其他方法芒福德的四大网络。请注意,长子的结果等。15)获得的评估报告的最终解决方案的工作(网络Mumford1)的唯一可行路径集。

从表10,我们可以看出,该方法与变量|R|优于芒福德的方法(27),长子et al。15),科里奇和完全懂得14),约翰et al。43),科里奇(42雅司病,和李36],艾哈迈德et al。38)的丙氨酸。建议的解决方案还发现最好的方法d₀在一切情况下网络Mumford2除外。需求的百分比最多满意一个传输(d₀+d₁超过99%的所有实例。虽然实验室值的方法通常比其他方法,一个解决方案,主导方面的现有方法的结果目标可以在图中找到11。

此外,表11比较我们的结果从运营商的角度为芒福德的四大网络与最近发表的结果在芒福德(27),约翰et al。43),科里奇(42雅司病,和李36],艾哈迈德et al。38]。我们的方法发现最好的结果在网络Mumford1 Mumford2, Mumford3而言实验室。这并不出人意料,因为我们的方法可以交替的路线路线设置大小交替启发式只要解决方案是可行的。的最佳解决方案网络Mumford0通过艾哈迈德et al。38]。的实验室他们的结果是比我们少一分钟(即。95分钟)。相反,丙氨酸我们的结果比他们小,所有的需求都可以满意我们的路线。一般来说,建议的解决方案方法与现有方法方面的竞争目标大实例。

5.4。推荐值|R|

TNDP,很难状态合适数量的路线最好的解决方案(44]。通过嵌入一组路由生成biobjective中启发式优化框架,我们试图找到近似帕累托前没有预设定|R|。本节的目的是演示|的防治效果R|对客观价值的近似帕累托方面。

图12显示了|R|值的近似帕累托前五的网络解决方案。正如所料,这两个目标通常是相互矛盾的。与|R|增加,丙氨酸减少和实验室同时增加。当|R|达到理论最大值,丙氨酸将收敛于理论最小值(见表2)。当|R|大于理论最大价值,增加|R|只会导致更大实验室但是没有减少丙氨酸。数据显示,当|R|达到一定值,进一步增加|R|几乎导致减少的价值丙氨酸。例如,对于网络Mumford3,丙氨酸当|从27.54分钟减少到27.29分钟R|增加从80年到100年,虽然实验室从6894年到8688年增加。这表明一个大|R|并不总是有利于旅客和运营商。

从图12可以看出,与特定的|解决方案的数量R|在近似帕累托方面相当小了四大网络。这表明,与预定义的|最好的解决方案R|是只有一小部分的近似帕累托。该方法与变量|R|更实用和高效的大型网络的大型网络的搜索过程计算耗时。

基于图的观察12,我们提出一个建议|的范围R为每个实例表|价值12。应该注意,推荐的值只意味着未来研究人员限制线路的数量,以避免浪费计算资源解决方案与极限平衡水平。

6。结论

提出了一个集成的解决方案方法同时解决交通网络设计问题和路由设置的大小确定问题。解决方法包括小说初始路线集生成算法,目标是培养高质量的初始解决方案优化算法和探索解空间的不同数量的路线,它还包含一个集大小交替启发式路由到备用线路的数量在一个解决方案。这两个算法嵌入到NSGA-II-based解决方案框架找到近似帕累托的目标(即前面。平均旅行时间和总路径长度)。

拟议中的初始路线集生成算法是基于直观的观察到最大化的旅游需求可以直接满足(没有转移)是一个关键的组件生成的一组初始路线。最初的解决方案生产表明,该初始路线集生成算法能产生高质量的大型网络的初步解决方案。注意,最初的解决方案获得网络Mumford2和Mumford3主导最终解决方案所产生的一些前研究方面的目标。计算时间的比较也表明,该算法是非常有效的,因为它只需要三秒钟生成一个初始解决方案(即最大的网络。Mumford3)。

分析的基础上的分配每个旅游需求,改善局部最优解和探索解空间有不同的|R|值,一套路线大小交替启发式开发开关线路的数量在一个解决方案。实验结果表明,该路线设置大小交替启发式可以节省大量计算时间没有恶化的质量接近帕累托面前。与固定路线设置大小的方法相比,近似帕累托方面通过不同的路线解决方案可能导致更大范围的取舍,使决策者关注权衡在这个限制的近似帕累托集前面的解决方案,而不是需要专注于固定数量的路线前代的交通网络。对于未来的工作,应该扩展到包括总线解决方案方法进展决心和机队规模约束,我们将扩展我们的研究通过提取可用的动态交通的需求来源。

数据可用性

交通网络实例用于支持这项研究的结果已经存入http://users.cs.cf.ac.uk/C.L.Mumford/Research%20Topics/UTRP/Outline.html。

信息披露

作者在本文负责任何错误。

的利益冲突

作者宣称没有利益冲突。

确认

这项研究得到了国家自然科学基金(没有。71901183),国家工程实验室的开放研究基金综合交通大数据应用技术(CTBDAT201901号和CTBDAT201907),中央大学和基础研究基金。

补充材料

本节包括近似帕累托方面获得的建议的解决方案的方法。对于每个实例,有两种类型的文件:Excel和Txt。Excel文件包含解决方案的性能指标获得近似帕累托。Txt文件包含相应的线路结构。(补充材料)