跨年的时候，我扫了一眼很久没打开的朋友圈，不出所料的发现很多人都在尝试用一两句简短的话总结和挥别2015，再用一两句话寄语2016。为了赶在那一两分钟之内把消息发出去，也只能写的很短。我当时也想写两句，但发现好难。而且，没有仔细的思考，很难客观的评价自己过去的这一年，更难一下子规划出新一年的目标。

跨年，尽管只是一个瞬间，但应该用一段更长的时间沉下来，反思2015，规划2016，就像过去每年这个时候一样。还有一点，2016对我和我们全家来说，必将会成为一生中的重大转折点。

2015，我33，2016，老婆33。常言道：三十三，大转弯。看来，要想全家一起大转弯，必须得从2015开始，然后在2016完成。

其实重构mmspa的想法早已有之，因为那是我2009年4月份开始写的库，后面在2010年集中开发Multimodal Route Planning System for Munich的时候基本就不再动它了，主要是有一种怕一碰就不能用了的心理在作怪。直到去年把上层的wrapper重新用Python写成pymmrouting的时候都没敢大动mmspa的代码，只是稍微添加了几个函数。但实际上，它的代码已经too(不) ugly(忍) to(直) read(视)了，而且现在又有了个改进效率的想法作为契机，那就做个大扫除吧。

之前的代码问题很多，要列清单可以列很长，这里就不详述了，当自己重构的动作提起速度来的时候也是脑子中几条线同时前进，有的问题随着发现就随着解决了，可能都没来得及反映到commit comments中。这里只提纲挈领的记几个要点：

1. 之前的代码组织主要是分成了parser（负责从数据库里读取数据并装配multimodal graph set）、multimodal-twoq（负责最短路径算法）和mmspa4pg（一个…大杂烩，里面既有routing plan的创建，还有最终路径的获取与销毁函数）。这样的组织显然混乱，所以把代码打散并重新组织成了routingplan、routingresult、graphassembler、mmtwoq和mmspa4pg这几个部分，数据结构主要都定义在modegraph.h中。结构比之前清晰了很多
2. 消灭了graphassembler，也就是之前parser中的几个超长函数，提取出了一票小函数
3. 更加合理的使用extern、static等，用以理清全局、局部、公有和私有的关系
4. 规范化命名约定，并且专门写了一个文件，记录Coding standards

这次的重构过程也是一次对C的再学习，《K&R》和《C Interfaces and Implementations》帮了很大的忙。特别是K&R，尽管只是薄薄一本，但其实信息密度很高，在里面总能找到自己的C知识短板。

重构后的版本作为1.1发布了，当然距离一个真正好用的库还差很远，不过总归是迈出了有意义的一步。

下一步，就是2.0。它最大的特点就是会比之前的库快，效率的提升会主要体现在Multimodal Route Planner for Munich的demo中。敬请期待。

O2O产业化的浪潮正在“全民创业，万众创新”、“互联网+”等等大旗的挥舞下席卷着这个处在实体经济萧条、政府债台高筑投资疲软、股市动荡、楼市热浪褪去、货币贬值、外资加速撤离、人口红利消逝、全民焦虑的世界第二大经济体。

从之前的呱呱洗车、1号社区到现在楼下正在拼命吆喝着”首单减10元“的浮点社区。O2O的烧钱之旅在如火如荼的进行着。但是在我看来，他们绝大多数都是在堆积泡沫。没有长期扎实的技术和人才积累，没有雄厚的基础制造业根基，没有让利于民的政策，没有公平的法制环境，也没有对失败者充分包容的氛围，仅凭印出来大把大把的钞票，以及找到的无数”痛点“，就可以完成几十年都没有完成的产业结构调整，实现新的经济腾飞吗？在我看来，这才是梦，是个真的梦，而且又是个十分浮躁的春梦。

都这么多年了，还是没有学会踏踏实实做事，认认真真积累。总想着走捷径，抄近道，多快好省，一夜暴富，点石成金。这样下去是没有希望的，梦就永远是个梦。

正当我看着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信息，然后导入数据库。