小白涨姿势之gis系统

好久没写blog，最近去知乎问了这样一个问题

有现成的 GIS 系统能处理 河流、立交桥、单行道、限行 等限制条件下求最近距离叫车的问题吗？

终于把心中的疑惑解决了。也怪自己笨，导航问题跟游戏寻路算法不一回事嘛！

参考ArcGIS的文档（英文，中文）：

网络分析主要解决下列几个问题：

• 导航 routing：
• 单行道限制 one-way restrictions
• 转弯限制 turn restrictions
• 交汇点阻抗 junction impedance
• 障碍 barriers
• 街边约束 side-of-street constraints
• 最近设施点 Closest facility 这个好像就是已知多家医院和多起事故，如何找最短路径把尽量多的伤者送到最近的医院？
• OD矩阵 (origin-destination matrix)：多个出发地和多个目的地，形成一个“价格阶梯表”
• 服务区分析 service area 。这个是我想了很久的。一个外勤警察5分钟能到达的区域范围是那些？算法涉及到一个概念叫不规则三角网 (TIN - triangulated irregular network)
• 流动推销员问题 (TSP - Traveling salesman problem)：第一步是在有待排序的所有停靠点之间生成OD成本矩阵，然后通过基于禁忌搜索的算法查找访问停靠点的最佳顺序。禁忌搜索(Tabu Search)是求解组合问题的元启发式算法。该算法属于局部搜索算法的范畴。
• 有时间窗的多路车辆配送(VRP - vehicle routing problem)。VRP是TSP的超集。加上车辆性能参数，配送时间窗口，特殊配送要求等限制。算法也是先建立OD矩阵，然后通过在最合适路径中一次插入一个停靠点的方式构建初步解决方案。随后可通过以下方式改进初步解决方案：对各路径中的停靠点重新进行排序、将停靠点从一个路径移至另一个路径，或在路径之间交换停靠点。ArcGIS在这方面有私有算法。
• 位置分配(Location-allocation)：多个相邻的连锁店如何保证覆盖面最大，重叠面积最小？即，给定具有权重的 N 候选设施点和 M 请求点，可选择设施点的子集 P，从而使每个 M 到最近的 P 之间的加权距离总和最短。这属于 N 选 P 的组合问题，解空间极大。无法通过检验所有组合获得最优解。

前三者都采用的是 Dijkstra 算法。

网络分析的限制条件：

• 时间窗口(time window)
• U字调头限制
• 障碍
• 道路分级(hierarchy)，比如高速优先。分级网络创建完成后，将使用双向 Dijkstra 改进算法计算起始点和目的地之间的路径。
• 驾驶方向和方向容宽度(Bearing & BearingTol)

还可以参考pg的pgRouting Workshop “FOSS4G routing with pgRouting, OpenStreetMap road data and OpenLayers 3”.：