主题没有,内容瞎写

芳草伴青山， 雲影入湖心， 松梢鶴嘯長， 蘆屋酣夢沉。

发表于 本文字数： 273 阅读时长 ≈ 1 分钟

全球化的时代，经济好与不好都是联动的，很难有哪个国家或地区能独善其身。区别只是在差的时期谁能不那么差；在好的时期谁能更好而已。而且不仅是经济层面，大众情绪、社会思潮都会与之联动，这些再进而影响政治，逐渐演变成波及世界各地、影响各个社会阶层的历史大事件。这是在宏观层面。

而在微观层面，每个工作团队、每个家庭、每个个体的情况又会表现出巨大的差异。他们有的可能深受宏观层面事件的影响而随之潮起潮落，也有的似乎事不关己，还有的甚至能逆势而动。

有趣的是，无数这些微观的个体又共同组成了宏观的图景。然而，在这幅壮丽图景上，又有哪些微观个体能跳出自己那方寸之地，以上帝视角看清整体的样貌，甚至是大潮前进的方向呢？

发表于 本文字数： 883 阅读时长 ≈ 3 分钟

这个工作缘于我在指导实验室今年的一篇硕士论文时蹦出来的一个想法。本来，我是想在这篇论文中把CH应用到mmrp中，通过减少IO来提高mmspa的整体性能。但后来我发现我想错了，因为我错误的理解了CH。CH并不是把道路网进行类似影像金字塔那样的多层次组织，尽管它的名字叫“分层压缩”，而是通过在原始网络中增加很多的“快捷边”，让后续的路径搜索算法可以“绕过”很多不必要去考察的顶点，从而大幅减少松弛操作的次数，达到加速最短路径搜索的目的。当然了，这种加速是有代价的，那就是在事先寻找、确定并建立这些“捷径边”所需的时间开销，以及增加了这些捷径边所带来的空间开销。

虽然应用CH来改善mmspa的IO看来暂时无望，但我在去年年底又想到了另一个可以改善目前每次计算都慢得要命的办法，尽管有点简单粗暴。那就是在程序启动时就把所有mode的图都读进来，然后后面针对每次routing plan进行graph装配的时候都不要再去访问数据库了（那个读graph的sql着实费时），而是从内存里的这个graph cache中取数据，装配成临时的graph集合，然后计算结束后再释放掉这些临时图。

顺着这个思路，我就开始着手于去年12月中旬实现这个feature，顺便也把mmspa这个老库好好整理了一下，动了动手术。最终在1月5号发布了2.0版本的mmspa，在增加了内存开销的代价下，把单次路径规划的性能提升了大约10倍，但到了http服务的层次，这个提升被打折到了5倍左右。

这次改造，对代码的结构进行了大幅调整，但仍然保留了原来的主要实现方式，没有动基础的算法和数据结构。尽管如此，过程也并不是一帆风顺。最主要的障碍就是装配公交系统graph，因为按照新方法组装起来的graph中的vertex不再是按照id排序的。所以只能又加入了一个快排函数，专门为公交graph进行顶点排序。这里费了一点时间。最后，用valgrind彻底清理了一遍所有内存泄漏的问题，确实找到了好几个，而且其中还有当年留下的千年老bug。昨天，我又发布了一个2.1.0版本，删除了对原来1.x版本的接口兼容（因为我知道受影响的只有我自己的pymmrouting），但也保留了能兼容1.x版本接口的2.0.1版本。

至此，虽然还有很多可以改进的东西（都写在issues里面了），但这次的工作暂时告一段落。路径规划，multimodal路径规划，是个永无止境的工作，而且就如杨剑说的，后面的优化工作量会非常大，而带来的收益会越来越小。这也算是一种边际效应递减吧。不知道今后是否还有机会继续3.0的工作，抑或把它变成未来某块工作的基础，那也算是幸事一件。

发表于 本文字数： 240 阅读时长 ≈ 1 分钟

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

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

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

发表于 本文字数： 609 阅读时长 ≈ 2 分钟

其实重构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中。敬请期待。

发表于 本文字数： 353 阅读时长 ≈ 1 分钟

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

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

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

发表于 本文字数： 146 阅读时长 ≈ 1 分钟

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

Road network around Marieplatz, Munich from OSM

with GPX tracks overlaid...

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

发表于 本文字数： 289 阅读时长 ≈ 1 分钟

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

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

发表于 本文字数： 159 阅读时长 ≈ 1 分钟

Single Page Web Applications

SPA

在第二章中把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' );

发表于 本文字数： 772 阅读时长 ≈ 3 分钟

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:

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.

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

发表于 本文字数： 963 阅读时长 ≈ 4 分钟

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

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

与之相关的项目有这些：

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.

0%