城市公交换乘查询系统的优化枚举算法研究与应用

徐炽

摘 要：该文针对目前我国城市公交查询系统存在的不足，提出了一种便于乘客进行路线选择的优化枚举算法，并探讨了以换乘次数最少为目标的公交查询方案。对n次公交换乘算法进行改进，引入紧邻站点和站站快表，提高公交查询系统的实用性和查询效率，从而吸引出行者优先选择公交车出行方式。

关键词：公交查询 优化枚举算法 Java Applet 最少换乘

中图法分类号：TP391 文献标识码：A 文章编号：1674-098X（2014）09（b）-0195-02

随着我国社会经济的发展，人民出行频率不断增加，交通问题日益突出，而城市公共交通具有运量大、人均占有道路少等优点。城市道路基础建设规模扩大的同时，道路的延伸后，随之满足人民需要的公交线路也在不断地增加。为市民提供便捷的查询系统，为方便地提供给人们出行时选择最优的公交换乘方案。在多种交通出行方式的复杂情况下，如果通过换乘进行协调配合，那么将会提高公共交通的利用率，从而有效减少重复投资建设的现象。

由于我国在公共交通管理方面还处于较低水平，推行公共交通换乘方面没有加强，因此，在公交换乘系统的开发方面，也处于起步阶段。然而，随着信息技术的快速发展，公交换乘查询系统的开发及推广也势在必行。目前，我国公交换乘查询系统仍存在一些问题[1]。

（1）公交线网管理混乱，没有建成换乘枢纽。

（2）公交信息查询系统终端没有普及。

（3）公交查询信息单一，不能满足出行者需求。

（4）查询信息陈旧，没有数据维护管理员。

1 公交换乘理论基础

公交换乘从换乘交通工具的一致性来讲，主要分为多方式换乘和普通换乘。多方式换乘是指换乘前后所采用的交通方式不同；而普通换乘则是指换乘前后的交通方式是一样的。本系统所要设计的换乘系统主要指的是普通换乘，主要针对公交这种特定的交通方式进行设计。

公共交通线路网的结构可按三种不同的线路网组成，分别是：放射形线路网、主干线和驳运线相结合的线路网、带有环线或切线状线路的放射形线路网[2-3]。

公交换乘的特性：

（1）换乘的必要性。

（2）换乘的有效性。

（3）换乘的多功能性。

2 优化枚举快速算法研究

基于距离最短的换乘方式，人们考虑更多的是减少换乘次数，避免换乘频繁带来的麻烦。因此，换乘理论中，基于换乘次数最少的方式，与实际换乘系统的应用联系更为紧密。基于换乘次数最少的换乘算法的算法思想核心是，根据调查显示[4]，出行者出行时对于公交线路的选择时，多数优先考虑是否有直达车，如图1（a）所示。如果没有直达车，则考虑一次换乘的方案，然后考虑中间站的位置，如图1（b）所示。如果没有一次换乘的方案，则考虑多次换乘，二次换乘如图1（c）所示，三次换乘如图1（d）所示。

基于优化枚举快速算法，通常情况下搜索得出的换乘次数要比实际公交换乘次数多。原因是算法理论搜索得出的是只考虑在原地换乘的结果；而在实际生活中，同一区域站点设置有一定的短距离，出行者会通过步行转到换乘点。因此，出现了查询换乘次数较多的现象。所以，在后续设计换乘查询模块时，应考虑到同一区域范围内的所有站点情况。

基于优化枚举快速算法的基本思想：如果确定起始站点Q、终点站Z出发，与数据库中各个线路中的站点相比较，寻找可换乘车站，得出可能的路径。

设S（I）（I=1，2，…，m）为经过起始站Q 的线路集合。

T（J）（J=1，2，…，p）为线路S（I）上的所有站点的集合。

F（J，V）（V=1，2，…，g）为线路T（J）上的所有站点集合。

R（K）（K=1，2，…，g）为经过站点 E（I，U）的线路集合。

Y（O）（O=1，2，…Z）为经过 F（J，V）的线路集合。

G（K，W）（W=1，2，…i）为线路 R（K）上的站点集合。

算法的步骤如下：

根据出行目的确定起始站Q和终点站 Z。

分别求经过起始站Q的所有线路集 S（I），以及经过终点站Z的所有线路集 T（J）。

经过判断条件S（I）与T（J）是否相等。如果相等，即存在直达线路，输出结果T（J）；如果没有则进行下一步。

求线路S（I）上的站点E（I，U）以及线路 T（J）上的站点F（J，V）。

分别求经过E（I，U）的线路集 R（K），和经过 F（J，V）的线路集Y（O）。

经过判断条件R（K）=Y（O）是否相等。如果相等，则得出两次换乘的一条可行路径 S（I），R（K），T（J），经过的中间换乘站点为 E（I，U）和 F（J，V），输出结果，结束运算。

3 查询系统的实现

本公交查询系统的功能主要包括：电子地图绘制和操作、公交线路查询、公交站点查询以及公交换乘的查询等。其公交查询的页面如图2所示。

优化枚举快速算法算法的算法思想核心是，根据调查显示，出行者出行时对于公交线路的选择时，多数优先考虑是否有直达车，如果没有直达车，则考虑一次换乘的方案，然后考虑中间站的位置，如果没有一次换乘的方案，则考虑多次换乘。通常情况下搜索得出的换乘次数要比实际公交换乘次数多。原因是算法理论搜索得出的是只考虑在原地换乘的结果；而在实际生活中，同一区域站点设置有一定的短距离，出行者会通过步行转到换乘点。因此，出现了查询换乘次数较多的现象。

换乘查询模块，进入路径查询时，共有两种选择，一是直达，另一个是换乘一次。进入界面后先在起点站和终点站输入框中点击选择站点，或者输入起点站和终点站的名称，点击“查询”按钮，查询结果显示在下面的列表框中，列表框中结果包括这两点之间的所有路线。查询用户根据出行行为倾向选择其中任一结果，点击显示详细信息。若查询的起终点之间存在直达线路，则系统优先得出直达的查询结果，即显示出经过这两个站点的所有直达线路的所有站点及其详细路径。若查询的起终点之间不存在直达线路，则系统自动进入一次换乘，需要通过输入中间站点名称来得出用户想要经过的中间地点。若查询的起终点之间没有换乘方案，则系统显示出没有查询结果，并且提示用户进行二次换乘，继续输入二次换乘的中间站点名称，或者修改查询的起终点名称。

试验结果表明，用户输入需要查询的公交线路，系统通过相应的线路路段中相应的字段或者车次号，获取该车次所经过的所有站点；也可以根据给出的一个站点，查询出经过该站点的所有公交车，从而为用户提供更多的公交信息。

4 结语

该论文在分析和总结公交站点、公交线路等公交数据的特点基础之上，改进了公交换乘的算法，引入了紧邻站点和站站快表，使算法更符合生活中人们的实际需求和提高了查询的效率。系统实现多种换乘查询的方式，不仅能满足不同乘客的不同需求，在换乘查询过程中，得出的结论也更为合理。因此算法具有很强的实用性和通用性，在公交网络中可以广泛采用。

参考文献

[1] 王建聪，高利平，陈绍宽，等.城市公共交通枢纽换乘组织仿真研究[J].交通运输系统工程与信息，2006，6（6）：68-69.

[2] 赵巧霞，马志强，张发.以最小换乘次数和站数为目标的公交出行算法[J].计算机应用，2004，24（12）：90-92.

[3] 文洪建.小城市公交换乘优化算法设计[J].中国科技信息，2010（13）：11-13.

[4] 胡云峰.公交换乘系统的数据库结构及算法优化[J].文山学院学报，2010（2）：22-25.endprint

摘 要：该文针对目前我国城市公交查询系统存在的不足，提出了一种便于乘客进行路线选择的优化枚举算法，并探讨了以换乘次数最少为目标的公交查询方案。对n次公交换乘算法进行改进，引入紧邻站点和站站快表，提高公交查询系统的实用性和查询效率，从而吸引出行者优先选择公交车出行方式。

关键词：公交查询 优化枚举算法 Java Applet 最少换乘

中图法分类号：TP391 文献标识码：A 文章编号：1674-098X（2014）09（b）-0195-02

随着我国社会经济的发展，人民出行频率不断增加，交通问题日益突出，而城市公共交通具有运量大、人均占有道路少等优点。城市道路基础建设规模扩大的同时，道路的延伸后，随之满足人民需要的公交线路也在不断地增加。为市民提供便捷的查询系统，为方便地提供给人们出行时选择最优的公交换乘方案。在多种交通出行方式的复杂情况下，如果通过换乘进行协调配合，那么将会提高公共交通的利用率，从而有效减少重复投资建设的现象。

由于我国在公共交通管理方面还处于较低水平，推行公共交通换乘方面没有加强，因此，在公交换乘系统的开发方面，也处于起步阶段。然而，随着信息技术的快速发展，公交换乘查询系统的开发及推广也势在必行。目前，我国公交换乘查询系统仍存在一些问题[1]。

（1）公交线网管理混乱，没有建成换乘枢纽。

（2）公交信息查询系统终端没有普及。

（3）公交查询信息单一，不能满足出行者需求。

（4）查询信息陈旧，没有数据维护管理员。

1 公交换乘理论基础

公交换乘从换乘交通工具的一致性来讲，主要分为多方式换乘和普通换乘。多方式换乘是指换乘前后所采用的交通方式不同；而普通换乘则是指换乘前后的交通方式是一样的。本系统所要设计的换乘系统主要指的是普通换乘，主要针对公交这种特定的交通方式进行设计。

公共交通线路网的结构可按三种不同的线路网组成，分别是：放射形线路网、主干线和驳运线相结合的线路网、带有环线或切线状线路的放射形线路网[2-3]。

公交换乘的特性：

（1）换乘的必要性。

（2）换乘的有效性。

（3）换乘的多功能性。

2 优化枚举快速算法研究

基于距离最短的换乘方式，人们考虑更多的是减少换乘次数，避免换乘频繁带来的麻烦。因此，换乘理论中，基于换乘次数最少的方式，与实际换乘系统的应用联系更为紧密。基于换乘次数最少的换乘算法的算法思想核心是，根据调查显示[4]，出行者出行时对于公交线路的选择时，多数优先考虑是否有直达车，如图1（a）所示。如果没有直达车，则考虑一次换乘的方案，然后考虑中间站的位置，如图1（b）所示。如果没有一次换乘的方案，则考虑多次换乘，二次换乘如图1（c）所示，三次换乘如图1（d）所示。

基于优化枚举快速算法，通常情况下搜索得出的换乘次数要比实际公交换乘次数多。原因是算法理论搜索得出的是只考虑在原地换乘的结果；而在实际生活中，同一区域站点设置有一定的短距离，出行者会通过步行转到换乘点。因此，出现了查询换乘次数较多的现象。所以，在后续设计换乘查询模块时，应考虑到同一区域范围内的所有站点情况。

基于优化枚举快速算法的基本思想：如果确定起始站点Q、终点站Z出发，与数据库中各个线路中的站点相比较，寻找可换乘车站，得出可能的路径。

设S（I）（I=1，2，…，m）为经过起始站Q 的线路集合。

T（J）（J=1，2，…，p）为线路S（I）上的所有站点的集合。

F（J，V）（V=1，2，…，g）为线路T（J）上的所有站点集合。

R（K）（K=1，2，…，g）为经过站点 E（I，U）的线路集合。

Y（O）（O=1，2，…Z）为经过 F（J，V）的线路集合。

G（K，W）（W=1，2，…i）为线路 R（K）上的站点集合。

算法的步骤如下：

根据出行目的确定起始站Q和终点站 Z。

分别求经过起始站Q的所有线路集 S（I），以及经过终点站Z的所有线路集 T（J）。

经过判断条件S（I）与T（J）是否相等。如果相等，即存在直达线路，输出结果T（J）；如果没有则进行下一步。

求线路S（I）上的站点E（I，U）以及线路 T（J）上的站点F（J，V）。

分别求经过E（I，U）的线路集 R（K），和经过 F（J，V）的线路集Y（O）。

经过判断条件R（K）=Y（O）是否相等。如果相等，则得出两次换乘的一条可行路径 S（I），R（K），T（J），经过的中间换乘站点为 E（I，U）和 F（J，V），输出结果，结束运算。

3 查询系统的实现

本公交查询系统的功能主要包括：电子地图绘制和操作、公交线路查询、公交站点查询以及公交换乘的查询等。其公交查询的页面如图2所示。

优化枚举快速算法算法的算法思想核心是，根据调查显示，出行者出行时对于公交线路的选择时，多数优先考虑是否有直达车，如果没有直达车，则考虑一次换乘的方案，然后考虑中间站的位置，如果没有一次换乘的方案，则考虑多次换乘。通常情况下搜索得出的换乘次数要比实际公交换乘次数多。原因是算法理论搜索得出的是只考虑在原地换乘的结果；而在实际生活中，同一区域站点设置有一定的短距离，出行者会通过步行转到换乘点。因此，出现了查询换乘次数较多的现象。

换乘查询模块，进入路径查询时，共有两种选择，一是直达，另一个是换乘一次。进入界面后先在起点站和终点站输入框中点击选择站点，或者输入起点站和终点站的名称，点击“查询”按钮，查询结果显示在下面的列表框中，列表框中结果包括这两点之间的所有路线。查询用户根据出行行为倾向选择其中任一结果，点击显示详细信息。若查询的起终点之间存在直达线路，则系统优先得出直达的查询结果，即显示出经过这两个站点的所有直达线路的所有站点及其详细路径。若查询的起终点之间不存在直达线路，则系统自动进入一次换乘，需要通过输入中间站点名称来得出用户想要经过的中间地点。若查询的起终点之间没有换乘方案，则系统显示出没有查询结果，并且提示用户进行二次换乘，继续输入二次换乘的中间站点名称，或者修改查询的起终点名称。

试验结果表明，用户输入需要查询的公交线路，系统通过相应的线路路段中相应的字段或者车次号，获取该车次所经过的所有站点；也可以根据给出的一个站点，查询出经过该站点的所有公交车，从而为用户提供更多的公交信息。

4 结语

该论文在分析和总结公交站点、公交线路等公交数据的特点基础之上，改进了公交换乘的算法，引入了紧邻站点和站站快表，使算法更符合生活中人们的实际需求和提高了查询的效率。系统实现多种换乘查询的方式，不仅能满足不同乘客的不同需求，在换乘查询过程中，得出的结论也更为合理。因此算法具有很强的实用性和通用性，在公交网络中可以广泛采用。

参考文献

[1] 王建聪，高利平，陈绍宽，等.城市公共交通枢纽换乘组织仿真研究[J].交通运输系统工程与信息，2006，6（6）：68-69.

[2] 赵巧霞，马志强，张发.以最小换乘次数和站数为目标的公交出行算法[J].计算机应用，2004，24（12）：90-92.

[3] 文洪建.小城市公交换乘优化算法设计[J].中国科技信息，2010（13）：11-13.

[4] 胡云峰.公交换乘系统的数据库结构及算法优化[J].文山学院学报，2010（2）：22-25.endprint

摘 要：该文针对目前我国城市公交查询系统存在的不足，提出了一种便于乘客进行路线选择的优化枚举算法，并探讨了以换乘次数最少为目标的公交查询方案。对n次公交换乘算法进行改进，引入紧邻站点和站站快表，提高公交查询系统的实用性和查询效率，从而吸引出行者优先选择公交车出行方式。

关键词：公交查询 优化枚举算法 Java Applet 最少换乘

中图法分类号：TP391 文献标识码：A 文章编号：1674-098X（2014）09（b）-0195-02

随着我国社会经济的发展，人民出行频率不断增加，交通问题日益突出，而城市公共交通具有运量大、人均占有道路少等优点。城市道路基础建设规模扩大的同时，道路的延伸后，随之满足人民需要的公交线路也在不断地增加。为市民提供便捷的查询系统，为方便地提供给人们出行时选择最优的公交换乘方案。在多种交通出行方式的复杂情况下，如果通过换乘进行协调配合，那么将会提高公共交通的利用率，从而有效减少重复投资建设的现象。

由于我国在公共交通管理方面还处于较低水平，推行公共交通换乘方面没有加强，因此，在公交换乘系统的开发方面，也处于起步阶段。然而，随着信息技术的快速发展，公交换乘查询系统的开发及推广也势在必行。目前，我国公交换乘查询系统仍存在一些问题[1]。

（1）公交线网管理混乱，没有建成换乘枢纽。

（2）公交信息查询系统终端没有普及。

（3）公交查询信息单一，不能满足出行者需求。

（4）查询信息陈旧，没有数据维护管理员。

1 公交换乘理论基础

公交换乘从换乘交通工具的一致性来讲，主要分为多方式换乘和普通换乘。多方式换乘是指换乘前后所采用的交通方式不同；而普通换乘则是指换乘前后的交通方式是一样的。本系统所要设计的换乘系统主要指的是普通换乘，主要针对公交这种特定的交通方式进行设计。

公共交通线路网的结构可按三种不同的线路网组成，分别是：放射形线路网、主干线和驳运线相结合的线路网、带有环线或切线状线路的放射形线路网[2-3]。

公交换乘的特性：

（1）换乘的必要性。

（2）换乘的有效性。

（3）换乘的多功能性。

2 优化枚举快速算法研究

基于距离最短的换乘方式，人们考虑更多的是减少换乘次数，避免换乘频繁带来的麻烦。因此，换乘理论中，基于换乘次数最少的方式，与实际换乘系统的应用联系更为紧密。基于换乘次数最少的换乘算法的算法思想核心是，根据调查显示[4]，出行者出行时对于公交线路的选择时，多数优先考虑是否有直达车，如图1（a）所示。如果没有直达车，则考虑一次换乘的方案，然后考虑中间站的位置，如图1（b）所示。如果没有一次换乘的方案，则考虑多次换乘，二次换乘如图1（c）所示，三次换乘如图1（d）所示。

基于优化枚举快速算法，通常情况下搜索得出的换乘次数要比实际公交换乘次数多。原因是算法理论搜索得出的是只考虑在原地换乘的结果；而在实际生活中，同一区域站点设置有一定的短距离，出行者会通过步行转到换乘点。因此，出现了查询换乘次数较多的现象。所以，在后续设计换乘查询模块时，应考虑到同一区域范围内的所有站点情况。

基于优化枚举快速算法的基本思想：如果确定起始站点Q、终点站Z出发，与数据库中各个线路中的站点相比较，寻找可换乘车站，得出可能的路径。

设S（I）（I=1，2，…，m）为经过起始站Q 的线路集合。

T（J）（J=1，2，…，p）为线路S（I）上的所有站点的集合。

F（J，V）（V=1，2，…，g）为线路T（J）上的所有站点集合。

R（K）（K=1，2，…，g）为经过站点 E（I，U）的线路集合。

Y（O）（O=1，2，…Z）为经过 F（J，V）的线路集合。

G（K，W）（W=1，2，…i）为线路 R（K）上的站点集合。

算法的步骤如下：

根据出行目的确定起始站Q和终点站 Z。

分别求经过起始站Q的所有线路集 S（I），以及经过终点站Z的所有线路集 T（J）。

经过判断条件S（I）与T（J）是否相等。如果相等，即存在直达线路，输出结果T（J）；如果没有则进行下一步。

求线路S（I）上的站点E（I，U）以及线路 T（J）上的站点F（J，V）。

分别求经过E（I，U）的线路集 R（K），和经过 F（J，V）的线路集Y（O）。

经过判断条件R（K）=Y（O）是否相等。如果相等，则得出两次换乘的一条可行路径 S（I），R（K），T（J），经过的中间换乘站点为 E（I，U）和 F（J，V），输出结果，结束运算。

3 查询系统的实现

本公交查询系统的功能主要包括：电子地图绘制和操作、公交线路查询、公交站点查询以及公交换乘的查询等。其公交查询的页面如图2所示。

优化枚举快速算法算法的算法思想核心是，根据调查显示，出行者出行时对于公交线路的选择时，多数优先考虑是否有直达车，如果没有直达车，则考虑一次换乘的方案，然后考虑中间站的位置，如果没有一次换乘的方案，则考虑多次换乘。通常情况下搜索得出的换乘次数要比实际公交换乘次数多。原因是算法理论搜索得出的是只考虑在原地换乘的结果；而在实际生活中，同一区域站点设置有一定的短距离，出行者会通过步行转到换乘点。因此，出现了查询换乘次数较多的现象。

换乘查询模块，进入路径查询时，共有两种选择，一是直达，另一个是换乘一次。进入界面后先在起点站和终点站输入框中点击选择站点，或者输入起点站和终点站的名称，点击“查询”按钮，查询结果显示在下面的列表框中，列表框中结果包括这两点之间的所有路线。查询用户根据出行行为倾向选择其中任一结果，点击显示详细信息。若查询的起终点之间存在直达线路，则系统优先得出直达的查询结果，即显示出经过这两个站点的所有直达线路的所有站点及其详细路径。若查询的起终点之间不存在直达线路，则系统自动进入一次换乘，需要通过输入中间站点名称来得出用户想要经过的中间地点。若查询的起终点之间没有换乘方案，则系统显示出没有查询结果，并且提示用户进行二次换乘，继续输入二次换乘的中间站点名称，或者修改查询的起终点名称。

试验结果表明，用户输入需要查询的公交线路，系统通过相应的线路路段中相应的字段或者车次号，获取该车次所经过的所有站点；也可以根据给出的一个站点，查询出经过该站点的所有公交车，从而为用户提供更多的公交信息。

4 结语

该论文在分析和总结公交站点、公交线路等公交数据的特点基础之上，改进了公交换乘的算法，引入了紧邻站点和站站快表，使算法更符合生活中人们的实际需求和提高了查询的效率。系统实现多种换乘查询的方式，不仅能满足不同乘客的不同需求，在换乘查询过程中，得出的结论也更为合理。因此算法具有很强的实用性和通用性，在公交网络中可以广泛采用。

参考文献

[1] 王建聪，高利平，陈绍宽，等.城市公共交通枢纽换乘组织仿真研究[J].交通运输系统工程与信息，2006，6（6）：68-69.

[2] 赵巧霞，马志强，张发.以最小换乘次数和站数为目标的公交出行算法[J].计算机应用，2004，24（12）：90-92.

[3] 文洪建.小城市公交换乘优化算法设计[J].中国科技信息，2010（13）：11-13.

[4] 胡云峰.公交换乘系统的数据库结构及算法优化[J].文山学院学报，2010（2）：22-25.endprint