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

発明者： , ,
出願人/特許権者： ,
代理人 (3件)：木村満 , 石井裕一郎 , 森川泰司
公報種別：公開公報
出願番号（国際出願番号）：特願2019-232681
公開番号（公開出願番号）：特開2021-101286
出願日： 2019年12月24日
公開日（公表日）： 2021年07月08日
要約：

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

請求項（抜粋）：

新たなピックアップ点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ターム (10件)：

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

前のページに戻る