rrrr 0.2.3

rrrr 0.2.3

测试测试
语言语言 CC
许可证 BSD 2.0
发布上次发布2015年7月

LLC ITS维护。



rrrr 0.2.3

  • abyrd, skinkie, skywave 和 JordenVerwer

RRRR 快速实时路由

介绍

RRRR(通常发音为R4)是RAPTOR公共交通路由算法的C语言实现。它是Bliksem行程规划器和乘客信息系统的基础路由组件。该项目的目标是生成覆盖大地理区域(例如贝奈卢克斯或整个欧洲)的帕累托最优行程方案集,改进现有更灵活替代方案的资源消耗和复杂度。该系统应支持反映在行程计划中的实时车辆/行程更新,并能够在无互联网连接的移动设备上直接运行。

在同一台机器上运行的多个RRRR进程将同一只读数据文件映射到它们的私有地址空间。此文件包含从GTFS数据源(例如) transit时间表和其他信息的结构化和索引表示。额外的处理器进程将仅增加物理内存消耗,以适应搜索状态(大约是16 * num_stops * max_transfers字节,大约几兆字节)。

每个工作进程是单独的进程,并保留一个永久性的临时缓冲区,该缓冲区在请求之间被重复使用,因此内部循环中不执行动态内存分配。公共交通站点是唯一的确切位置。纬度和经度位置搜索映射到最近的地点。在街上的搜索在第一阶段开发中没有被处理,这是我们下一个开发目标之一。

依赖关系

  1. libprotobuf-c:用于解码传入的实时消息。请参阅https://code.google.com/p/protobuf-c/downloads/list,Ubuntu软件包libprotobuf-c0和libprotobuf-c0-dev。

  2. gccclang:clang提供了非常良好的错误消息和警告。目前,当可以使用-lto时,gcc提供最佳的速度,当使用-O3 -flto时。请参阅https://gcc.gnu.org/https://clang.llvm.net.cn/

  3. check:C语言的单元测试框架。请查阅http://check.sourceforge.net/

构建交通数据

导航到rrtimetable/rrtimetable。运行python gtfs2rrrr.py gtfs.zip根据GTFS数据库创建时间表文件timetable4.dat。如果您只想对代码进行实验,请下载:http://1313.nl/timetable4.dat

编码规范

正如ansibranch的名称所暗示的那样,我们构建C89代码,以确保与几乎任何工具链兼容。因此,为了跨平台兼容性,请使用 FROM stdint.h 中的特定类型。绝对时间存储在 uint64 中,并从纪元引用。绝对时间总是禁用夏令时存储,因为在 serviceday 定义了夏令时,而不是常规的凌晨3点。调度中的时间是 uint16,并在午夜引用。2**16 / 60 / 60 仅等于 18 个小时,但通过将所有时间右移一位,我们得到36小时(1.5天),以 2 秒的分辨率。当函数的返回值是数组时,函数应返回数组的指针,并在间接参数中存储元素的数量(而不是反过来)。数据文件主要是列存储。

构建和启动 RRRR

使用 cmake(首选)

rm -r build ; mkdir build && cd build && cmake .. && make

使用 make

make clean && make && ./cli

为移动开发构建 RRRR

请参阅 Makefile,了解作为最低限度的需求所需文件。我们建议您显式阅读 config.h 以禁用所有未使用的功能。

已经历、已完成

  • 我们尝试取消展开由“到达”引起的某些分支。结果代码比我们现有的代码慢不了多少。
  • 我们尝试将journey_pattern_t 分割为核心路由和元数据结构。结果代码慢4%。
  • 路由状态的原始代码包装在一个结构体中。将其分割成单独的列表提高了 10%。
  • 尝试阻止溢出检查(将rtime 迁移到 32 位),结果导致严重的性能下降。