正当我看着Marienplatz那里一坨乱麻般的GPX思考该如何把它们match并snap到road network上去的时候，Mapbox的matching API在7月8日发布了。真是不得不佩服Mapbox，想人所想，及人所及，太善解人意了。

另外的感觉呢，就是像matching、routing，还有map generalization这样的问题，看起来好像都研究了很久了，但其实历久弥新，还是有很多可以做的地方。这也算是让自己坚持下去的一个理由吧。

尽管还是算的很慢（平均一次请求的处理时间要10s左右），而且bug也不少，但这个三年前就应该上线的多模式路径规划演示系统Multimodal route planner demo for Munich还是可以用了。除了核心算法库（mmspa）几乎没变以外，其它部分全都重写了。前端部分的代码大量参考了Mapbox的mapbox.directions.js项目，但我并没有fork它，而是基于它的代码进行了修改，这在它的license中是允许的。另外，从底图到样式，也都利用了Mapbox提供的多个服务和开源项目，所以这里这里要特别对Mapbox的开发人员们致以诚挚的谢意。
我还会继续不断改善它，改善它的性能、规划质量、稳定性、交互体验等等，要让它变得越来越好用，因为，它主要是

• 给我自己用的
• 给我自己用的
• 给我自己用的
  对，重要的事情要多说几遍。
  后面用于验证新想法的实验都会基于这个演示平台来做，希望能有些收获。

Single Page Web Applications

在第二章中把JavaScript中的几个我认为最基本、最重要、最容易让人混淆和出现理解偏差的地方讲的都很清楚，包括变量的作用域、上下文对象、作用域链、基于原型的对象、原型链、函数、闭包等等，基本上每个都直戳我的痛点。这一章非常值得反复阅读。

这里记一个对象创建的最佳实践，利用了Object.create和工厂函数：

1
2
3
4
5
6
7
8
9
10
11
12

var proto = {
  sentence: 4,
  probation: 2,
};
var makePrisoner = function( name, id ) {
  var prisoner = Object.create( proto );
  prisoner.name = name;
  prisoner.id = id;
  return prisoner;
};
var firstPrisoner = makePrisoner( 'Joe', '12A' );
var secondPrisoner = makePrisoner( 'Sam', '2BC' );

After large amount of data cleaning, preprocessing and integrating work on the datasets from OpenStreetMap, UnitedMaps and the Munich underground station platform data collected by myself, a multimodal graph dataset for Munich area is finally ready to use. The data processing scripts are in the mmgraphdb-builder project on github.

With the testbed prepared, I improved the pymmrouting (python wrapper of multimodal shortest path algorithms library) with a lot of refactoring and rewriting, did some slight improvement w.r.t the stablity and error handling on the C library mmspa (multimodal shortest path algorithms) I implemented in TUM, and then implemented an JSON RPC style API service for multimodal path finding. The API service is hosted just here on my website, the URL is:

http://luliu.me/mmrp/api/v1

The related open source projects are:

• mmspa
• pymmrouting
• mmgraphdb-builder
• mmrp-jsonrpc

The usage of the API can be found in the README of mmrp-jsonrpc. Here I paste the usage section:

Sample usage

The API service provides two methods accepting POST requests:

• mmrp.index: return a welcome message
• mmrp.findMultimodalPaths: do the multimodal route planning with given routing options

Sample request on mmrp.index

Send a request via curl:

1

curl -i -X POST  -H "Content-Type: application/json" -d '{"jsonrpc": "2.0", "method": "mmrp.index", "params": {}, "id": "1"}' http://luliu.me/mmrp/api/v1

Response:

1
2
3
4
5
6
7
8
9
10
11

HTTP/1.1 200 OK
Date: Sat, 13 Jun 2015 10:55:30 GMT
Server: Apache/2.4.7 (Ubuntu)
Content-Type: application/json
Content-Length: 111

{
  "id": "1",
  "jsonrpc": "2.0",
  "result": "Welcome using Multimodal Route Planner (mmrp) JSON-RPC API"
}

Sample request on mmrp.findMultimodalPaths

Both the request and response are too long to write here. The request can be found in sample_request.sh. And the response containing the feasible multimodal paths as well as switch points is in the sample_response.json.

IMPORTANT NOTES

1. The testbed at the backend is just for Munich, Germany. The concrete bounding box is 11.360796,48.061602,11.722875,48.248220. So please make sure the source and target in your request are both within the bbox.
2. I am sure that you will feel that “WTF, the service is damn slow!”. Yes, your feeling is correct because NO optimization on data preparation for each multimodal path finding process is applied yet. On average, the multimodal network assembling will take 3~5 seconds for each path searching plan while the pure path calculation will take around 0.5 seconds. Usually, a request may result in executing multiple path searching plans infered by a rule engine, so it is normal to have the feeling of slowness. However, it won’t take more than one minute to get the response in the worst case.
3. Traffic rules like turning restrictions are not included for the moment.
4. Bus lines are not included for the moment.
5. Time tables for public transits are not included for the moment.
6. Station platform data are only available in underground network. Those in the suburban and tram stations have not yet been collected.

The limitation list is, well, not short. Why do I develop and release it? The only reason is there is NO practical multimodal routing engine can be found across the whole Internet that can provide such routing results:

• Drive to a parking lot with available positions, park the car there and walk to the destination
• Drive a car which can only run 10 km due to gas limit to a park and ride lot, park there and take public transit to go to the destination, but keep in mind that there should be enough gas left for you to drive the car back at least to a nearby gas station
• I am a passenger this time, my wife drives. She takes me to a kiss and ride lot, I get off the car and take the underground line (I like underground more than other sort of public transits) to go to my destination, while she drives away back home or for work

At present, I am doing some multimodal path analysis work, and need a practical system/library/service being able to give routing results like above. But unfortunately I cannot find one. So I have to reorganize my phd work and use my own library although it is a little bit slow.

In next steps, I may do some improvement work aiming at the above limitation list. But there is no scheduled plan yet. Now I am implementing a simple web demo - mmrp-web. It will be online within one month hopefully.

There is already a Chinese version of this post.

这篇帖子我已经写了中文版，需要的话请移步这里。

在对OpenStreetMap数据、UnitedMaps数据还有我自己采集的数据进行一系列处理之后，把去年写的pymmrouting进行了大幅修正，然后又基于flask-jsonrpc实现了JSON RPC风格的API service，现在多模式路径规划API服务mmrp-jsonapi已经上线了，就在我的这个网站上，地址为：

http://luliu.me/mmrp/api/v1

与之相关的项目有这些：

• mmspa
• pymmrouting
• mmgraphdb-builder
• mmrp-jsonrpc

API服务的使用方法可以在mmrp-jsonrpc的README中找到，我这里再贴一份：

对 mmrp.index接口的范例请求

通过curl发送POST请求:

1

curl -i -X POST  -H "Content-Type: application/json" -d '{"jsonrpc": "2.0", "method": "mmrp.index", "params": {}, "id": "1"}' http://luliu.me/mmrp/api/v1

响应:

1
2
3
4
5
6
7
8
9
10
11

HTTP/1.1 200 OK
Date: Sat, 13 Jun 2015 10:55:30 GMT
Server: Apache/2.4.7 (Ubuntu)
Content-Type: application/json
Content-Length: 111

{
  "id": "1",
  "jsonrpc": "2.0",
  "result": "Welcome using Multimodal Route Planner (mmrp) JSON-RPC API"
}

对mmrp.findMultimodalPaths接口的范例请求

同样也可以通过curl来发送POST请求，但无论是请求还是响应都比较长，不写在这里了，大家可以参考mmrp-jsonrpc中的sample_request.sh和sample_response.json。在响应中包含了搜索到的多模式路径座标序列（以GeoJSON表示），以及不同模式路径之间的切换点（switch point）信息。

特别注意

1. 目前后端的测试数据集是慕尼黑市及周边部分地区，具体范围为：11.360796,48.061602,11.722875,48.248220。所以注意你送进去的source和target，超出了这个范围是肯定没结果的
2. 如果你试用了mmrp的这个API服务，那么恐怕最大的感受就是“慢”。没错，它就是慢，慢，慢，重要的事情说三遍。因为在数据层面，我还没做任何优化，所以每次计算路径的时候装配多模式网络的时间会比较长，对于每个路径搜索计划，大约需要3到5秒左右，然后计算路径的时间在0.5秒以内，而且又因为每次搜索路径很可能包括多个搜索计划，所以总体感觉会比较慢，但最差的情况1分钟之内是会有结果的
3. 交通规则暂时没有考虑
4. 公交系统中暂时只有S-bahn（suburban，轻轨）、U-bahn（underground，ditie）和Tram（有轨电车）。Bus（公交车）线路数据尚未提取和纳入规划范围
5. 公交系统的时刻表数据尚未采集处理
6. 只有U-bahn（underground，地铁）系统可以具体到站台和线路，S-bahn（suburban，轻轨）和Tram（有轨电车）的站台数据尚未采集

是的，它很慢，而且功能十分有限。但即便如此，目前全网之内都还找不到一个能实现真正给出诸如“先开车，然后停在某个停车场，再步行到目的地”，或者“考虑到汽车的剩余油量只能跑10公里，那么就先开到一个临近的P+R，停在那里，换乘公交系统到目的地，当然还要保证回来的时候汽车还有剩油能开走”，或者“我不是司机，别人开车把我送到一个Kiss+R的地方，我去坐地铁前往目的地，然后他开走”这样规划结果的实用系统。所以我只能把自己博士论文的东西重新整理，然后全部以开源项目的形式发布。

我后面可能会考虑对性能进行优化，对功能进行扩展，融合更详细的数据以及时刻表等动态信息，但暂时没有详细的日程表。现在，我正在实现一个web前端作为demo，估计一个月之内可以与大家见面。

这篇post我会再写份英文版的。

I will write an English version of this post to introduce mmrp (multimodal route planner) related projects.

OS X系统自带的Python会预装nose，但这个nose的coverage插件是用不了的，尽管可以通过nosetests –plugins看到Plugin coverage在列表中。万能的Google加Stackoverflow只找到一个问题，是通过pip install coverage解决的，但居然在我这里无效，而且如果pip install nose也不会有任何反应，因为pip会认为Requirement already satisfied。那么最后怎么解决呢？只能pip install –upgrade nose，把它升到最新的1.3.7，然后就ok了。大胆猜测，应该通过pip uninstall再重新install一遍也可以解决。

随手记的东西，就不整理格式了。

数据准备

1
2
3
4

$ dropdb yourdatabase
$ createdb -O youruser yourdatabase
$ psql -d yourdatabase -c "CREATE EXTENSION postgis;"
$ postgis_restore.pl "yourdatabase_backup_data.backup" | psql -h localhost -p 5432 -U youruser yourdatabase 2> errors.txt

在使用pgis_fn_nn进行最近邻搜索的时候，有个问题需要fix，就是它先创建了一个pgis_nn类型，用于保存查找到的要素id和距离值：

1
2

CREATE TYPE pgis_nn AS
   (nn_gid integer, nn_dist numeric(16,5));

但是其中的nn_gid被定义成integer类型在目前的很多情况下都太短了，比如在处理OSM数据的时候，osm_id就都是64位的bigint，所以这里需要把nn_gid的类型改成bigint，否则会在运行时报类似这样的错误：

1
2
3
4

ERROR: value "2714664549" is out of range for type integer
SQL 状态: 22003
上下文:PL/pgSQL function _pgis_fn_nn(geometry,double precision,integer,integer,character varying,character varying,character varying,character varying) line 15 at FOR over EXECUTE statement
SQL function "pgis_fn_nn" statement 1

通过osm2pgsql导入postgis的OSM数据表osm_line和osm_point其实并不能直接等同于直接支持路径规划选点和结果显示的street_lines和street_junctions。osm2pgsql文档中说的很明白：

This table (指planet_osm_point) contains all nodes with tags which were imported. Nodes without tags (as those whose only purpose is to define the position of a way) are not imported.

也就是说，在osm_point中找最近邻的路径起止点是不科学的。所以需要自己在构造multimodal网络的同时记录下所有street_junction信息，然后导入数据库。

刚刚完成了《CartoCSS指南》的第一遍翻译校对整理工作。主要是对其中的翻译进行了梳理，统一了大部分术语和格式，删除了不存在翻译异议的原文。但粗略浏览了一下，发现还有个别原文段落忘了删掉，会在第二遍校对的时候进行处理。

下面会随即启动第二遍审校整理工作，主要是对目前还存在较多翻译异议的部分（主要是3.7节-关于合成操作和4.2节-地图配色技巧）敲定内容。并且需要把概述部分尽量完成。这部分工作需要辛苦Anran Yang同学帮忙了。

第二遍审校之后，1.0版即可发布。

Mapbox真是个快速变化的公司，还没几个月呢，Mapbox Studio的文档就又来了一次翻天覆地的大改版。给《CartoCSS中文指南》的编译工作带来了不小的冲击。目前，还是立足于完成之前的计划，然后再根据最新的变化来修订内容。毕竟现在一份内容完整，结构合理，思路清晰的稿子还没有出来。我相信后面的工作主要都是小修小补，除非Mapnik和CartoCSS又出现重大更新。

关于“大数据”，我认为就像当年“云计算”一样，很多人在还没有弄清楚其背后的相关技术之前就纷纷义无反顾的跳进去了。最近准备做一些multimodal routing的后续工作，仅仅是出于兴趣，发现需要用到一些data science领域的东西，产生了一些疑惑，然后翻出了一篇stackoverflow上What is the difference between Big Data and Data Mining问题的回复，说的挺好，要点如下：

Big data is everything

大数据是一个商业术语。现在什么都是大数据，一个U盘可以是一个“私有云”，一块硬盘就可以装下“大数据”。

Data mining is the old big data

在大数据这个词出现以前，同样的东西和事情叫做“数据挖掘”。数据挖掘这个术语也是一个曾经被过度使用的词，但它所用到的具体技术和现在的大数据没什么区别。只是现在市场、销售和推广部门又需要新的概念去忽悠客户了，所以出现了“大数据”，一如曾经出现的商业智能（BI）什么的一样。

Most “big” data mining isn’t big

绝大多数的所谓“大”数据，其实一点也不大。KDnuggets的调查结果是目前进行分析的最大数据集大小平均仅为1到10GB。这比10年前做分析用的数据集当然已经大了很多，但距离EB（等于1024PB，等于1024*1024TB）级还差好远。这样规模的数据集对于很多复杂分析方法来说，已经不小了。

Most “big data” isn’t data mining

现在经常谈论的“大数据”其实都无关数据挖掘，而仅仅是在数据的存储和管理层面。目前，数据量意义上的大数据是真实存在的，比如Google，CERN都拥有巨大规模的数据。大数据的相关技术也是真实存在的，比如Hadoop。但人们通常在使用这些技术的时候头脑并不清醒，缺乏理智。如果规模达不到100个节点，那完全可以不用Hadoop，有的是其它更好的替代方案。目前的绝大多数应用场景只能称为Extract, Transform, Load (ETL)。不同的地方仅仅是它们把数据抽到Hadoop，而不是传统的数据仓库里而已。

Data quality suffers with size

大量数据中的偏见和噪声问题是大数据应用中的两个基本问题。修正偏见、清洗数据都是在开始后面的分析之前先要做的重要任务，但人们却往往忽略它们，而它们本身也的确都是难度很大的工作。

Hadoop != data mining

Hadoop本身不做数据挖掘。但有一些工具尝试对Hadoop中存储的数据进行挖掘和分析，例如Apache的Mahout项目。但实际上Mahout更多的是一个机器学习工具，而机器学习也不等于数据挖掘，它们俩的关系是数据挖掘有时会用到一些机器学习中的方法。Mahout中的一些部分（例如聚类）还远未成熟。关键的原因在于（注意，重点来了）：Hadoop适用于线性问题，而绝大多数数据挖掘问题都是非线性的。非线性算法很难不加修改就直接用于处理规模巨大的数据集——你需要仔细设计一种近似的线性算法，并且在近似所带来的精确性降低与可计算性之间寻找平衡。而数据挖掘里面这种非线性问题相当的多，所以目前可以说在Hadoop上进行数据挖掘的实质性工作尚未开始。尽管现在有很多人在做这个，也有很多公司在卖相关的产品，但目前还没见到哪个打上“大数据”标签的版本比“不大数据“的版本更好用。但既然有人想买，那么就会有公司继续卖；既然搞这个能赚学术分，那就会有人继续写paper，无论这些东西是不是真的有用。这就是生活。

当然也有一些成功的例子，比如Google search，CERN，以及图像识别等等。但这些成功案例中无一例外都是基于清洗过的数据来进行挖掘和分析的，这一点请务必注意。