Pat

J-GLOBAL ID：202103000954717101

経路計画装置、経路計画方法、ならびに、プログラム

Inventor： 査 澳龍 ,  野田 五十樹 ,  落合 純一
Applicant, Patent owner： 国立研究開発法人産業技術総合研究所 ,  株式会社未来シェア
Agent (3)： 木村 満 ,  石井 裕一郎 ,  森川 泰司
Gazette classification：公開公報
Application number (International application number)：2019232681
Publication number (International publication number)：2021101286
Application date： Dec. 24, 2019
Publication date： Jul. 08, 2021
Summary：

【課題】ピックアップ点とドロップオフ点とを指定する乗客に乗合タクシーを配車するためのタクシーの経路を計画する。【解決手段】経路計画装置101において、要求受付部102は、新たなピックアップ点およびドロップオフ点を指定する要求を受け付ける。コスト評価部103は、各タクシーが訪問しうる点同士を結ぶ有向辺に対するコスト時間を評価する。エンコード部104は、ハミルトニアン路制約をハード節へ、目的関数をソフト節へ、それぞれエンコードする。SATソルバ部105は、ハード節を満たし、目的関数を次第に減少させる漸化解を順次求めて、最適解を得る。更新部106は、最適解におけるソフト節に基づいて、タクシーの経路を更新する。【選択図】図1

Claim (excerpt)：

新たなピックアップ点L、および、新たなドロップオフ点Rを指定する要求を受け付ける要求受付部、 稼働中の複数のタクシーの集合Λにおける各タクシーλ∈Λに対する頂点の集合であって、 当該各タクシーλが現在所在する現在点Oλと、 当該各タクシーλがこれから訪問すべきピックアップ点P[λ,1], P[λ,2], ...∈Φλと、 当該各タクシーλがこれから訪問すべきドロップオフ点Q[λ,1], Q[λ,2], ...∈Ψλと、 前記受け付けられた要求に係るピックアップ点Lを当該各タクシーλが訪問するとした場合のピックアップ点Lλと、 前記受け付けられた要求に係るドロップオフ点Rを当該各タクシーλが訪問するとした場合のドロップオフ点Rλと、 を含む集合V[λ]=Φλ∪Ψλ∪{Lλ, Rλ}={v[λ,1], v[λ,2], ...}に対して、 互いに異なる頂点a,b∈V[λ]について、当該頂点aから当該頂点bへ直に向かう有効辺の有無を表す論理変数〈a,b〉に対するコスト時間w〈a,b〉 を評価するコスト評価部、 互いに異なる頂点a,b∈V[λ]について、当該頂点aを経て当該頂点bへ至る経路の有無を表す論理変数a≫bと、前記論理変数〈a,b〉と、により表現される ハミルトニアン路(Hamiltonian path; HP)制約を、ハード節へ、 目的関数Σλ∈Λ Σx∈V[λ] Σy∈V[λ] O[λ]≫L[λ] ・〈x,y〉・w〈x,y〉を、ソフト節へ、 それぞれエンコードするエンコード部、 前記エンコードされたハード節を満たし、前記エンコードされたソフト節に係る前記目的関数を次第に減少させる漸化解を順次求めることにより、前記目的関数を最小化する最適解を求めるSAT(boolean SATisfiability problem)ソルバ部、 前記求められた最適解においてO[λ]≫L[λ]を満たすタクシーλ∈Λの経路を、前記最適解に基づいて更新する更新部 を備えることを特徴とする経路計画装置。

IPC (3)：

G06Q 50/30 ,  G08G 1/123 ,  G06N 99/00

FI (3)：

G06Q50/30 ,  G08G1/123 A ,  G06N99/00 180

F-Term (10)：

5H181AA14 ,  5H181FF11 ,  5H181FF13 ,  5H181FF17 ,  5H181MA02 ,  5H181MA04 ,  5H181MA07 ,  5H181MA08 ,  5H181MA10 ,  5L049CC42