如何实现公交（含地铁、步行）多次换乘的高效查询的思路

1 0

如何实现公交（含地铁、步行）多次换乘的高效查询的思路50

各个地图服务商都提供有公交换乘的查询功能。对于直达类型或者一次换乘的算法，应该比较好实现，直接查询的效率也不慢。
但是如果涉及到多次（10次以内）的算法，再加上最快（地铁一般比公交快）、最少换乘（可能会绕路）、最短（距离计算）等条件综合的话，就非常复杂了。
网上有一些例子，但大多都是直接单表查询，非常影响查询效率。
请问如果要实现3-10次换乘左右的查询，如何做才能尽量的快，而且满足一定的访问压力？请高手从数据结构、算法优化方面给出建议。

问题补充：如果当有1000条甚至5000条以上的线路，允许3-10次换乘，整体支持100-500并发以上，是一个相当大的工程了。
这个问题可能比较复杂了，我应该拆分为几部分：数据结构，算法优化，系统架构等。

数据结构算法 GIS

2013年4月15日 10:33

lazy
387
0 0 3

4个答案按时间排序按投票排序

0 0

引用

需要先把实际的交通抽象成点、线、网

数据模型上都是线，比如某城市共有公交+地铁线路50条（中等），平均每条线路的站点有20（+1）个，那么数据库中线路表中共有 50 x 20 x 2（考虑特例，往返算不同） = 2000条记录。

然后线和线之间用端点相连，需要考虑步行距离，时刻等因素。

最后在这个网络中计算。这里不知我们是否一致？

引用

并且赋予各种权重值

是的。比如查询最短距离时，权重取距离；查询最短时间时，时间是权重；麻烦的换乘。

引用

就是公交或地铁线路的走向

假如按上面的模型，线和线是靠端点（和不同线路）连接起来的。
不需要考虑走向，只凭权重值计算结果即可。
特别是公交和地铁，按我上面的模型，去掉同一线路的往返，共有1000（+1）多个点，1000条线路，能够连接上的就更少了，所以数据量虽然不小，但绝对是可容忍范围。

引用

还有就是效率问题

在我看来，“缓存”是必须的。
特别是公交地铁线路基本上是固定的，那么推测99%的换乘都可以事先计算好的。虽然数据量可能较大，但可以用空间换取非常大的效率。
还可以在计算结果上进行人工调整？用户协作？等等...

不是所有可能的换乘组合，而是换乘方案——几条公交地铁线路组成的一条条更大的“线路”。
这些事先计算好的换乘方案一样可以抽象层“线路”，当用户查询时优先使用这些数据。

在城市施工等原因导致线路发生增删改时，再次重新计算即可。

那么，你还是在做主题是线路查询的东东喽？！祝好运！哈哈！

2013年4月16日 10:20

clxy
825
0 3 62

1条评论

0 0

这个问题可以当做一个动态规划问题，求一个最优解。

2013年4月15日 16:22

lovemylover
30
0 0 1

添加评论

0 0

这个时候，分布式并行计算就派上大用场了

map reduce大显身手的时候

2013年4月15日 12:49

月影无痕
45
0 0 1

1条评论

0 0

交通方式通常有步行，公交，地铁，汽车（自驾+出租），火车，飞机，轮船和其他（热气球，滑翔机，航天飞机及人间大炮）等。

首先，这些方式其实都可以抽象概括成“线路”，有如下属性，（除去名称什么无关路径计算的以外）

起点，终点。物理坐标。
实际距离。
花费时间。
花费费用。
最早及最晚有效时刻。早班，末班车次等。

比如步行和汽车1，2上是一样的，通常都是按市区道路来就是了。但还是有些是步行可汽车不可的羊肠小路；汽车可步行不可——高速高架等；还有单向双向及牌号的区分等。

无论哪种方式，数据结构都可以概括成上面的“线路”。
然后剩下的问题就是计算这些线路的组合。

通常的做法是让用户先选择些条件，过滤掉些可能性才好。比如

纯粹的步行和纯粹的汽车要单独计算。且只需计算最短距离就好=最短时间=最少换乘=最少费用。
通常以汽车，地铁，火车，飞机等有固定线路及站点的为主体，步行为辅——最近站点到目的地部分的方式计算。

不然天南海北的是会直接拖垮系统的。（索性都推荐人间大炮好了！哈哈。）

但是，除非你在做线路查询这样的系统，不然的话还是直接“使用”已有的服务吧，比如google，百度等。
都已经是云计算时代了，凡事还要亲力亲为的话比较累。

实在要自己实现，可能选择是网上搜些开源免费的包用。毕竟这个不是什么新鲜前卫的课题了。
网上搜“最短路径算法”shortest path algorithm，算法很多。再找自己要的语言。

2013年4月15日 12:05

clxy
825
0 3 62

2条评论

已解决问题

未解决问题

排行榜

查看全部排名>>