• Navitは、OSMデータを使うことが可能なオープンソースのカーナビソフトウェアです。
• OSM地図データから抽出したbinfileフォーマットを使い、リアルタイムに描画
• 探索、ルーティング、動的リルーティングが可能であることに加え、地図を３D鳥瞰図として表示することも可能
• ~ 参考URL

Navitの限界

• しかし、あくまでこれは、最短ルート検索ができるだけであり、渋滞も、乗車希望人数も、乗車中の人数も一切考慮しない
• ソースコードのハックをすれば不可能ではないが、絶望的に訳が分からん上に、その後の展開がない
• そもそも、今回必要なものは「ナビソフト」ではない

• 始点と終点を指定、あるいは複数の経由点を指定して、任意の重みを付けた有向の経路計算結果を高速で得られる
• DBからデータを取ってきて、パースして、アルゴリズムに食べさせて…　というところを、DBの中のバイナリーで終わらせられる
• アルゴリズムそのものの作成が重要で無い場合は、pgRoutingを使ってしまうのが早い
  • ~ pgRouting Manual (2.0.0)
  • ワーシャルフロイドも入っている

• ~ OSM データを NetworkX へ取り込んで最短経路計算

• ~  NetworkX

• ~ Route. Schedule. Plan. Assign. Pack. Solve.
• ~ About Combinatorial Optimization

• ~ Common Routing Tasks
• 看護婦さんのシフト問題、トラベリングセールスマン等々、NPハード系の数理最適化がひととおりできるようになっていて、公開されたとき物議を醸したやつです。