図面 (/)

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

出願人 国立研究開発法人産業技術総合研究所株式会社未来シェア
発明者 査澳龍野田五十樹落合純一
出願日 2019年12月24日 (1年10ヶ月経過) 出願番号 2019-232681
公開日 2021年7月8日 (3ヶ月経過) 公開番号 2021-101286
状態 未査定
技術分野 学習型計算機 交通制御システム
主要キーワード ピックアップ点 乗客定員 論理変数 時間コスト コスト評価 有向辺 経路計画装置 時間超過
関連する未来課題
重要な関連分野

この項目の情報は公開日時点(2021年7月8日)のものです。
また、この項目は機械的に抽出しているため、正しく解析できていない場合があります

図面 (7)

課題

ピックアップ点ドロップオフ点とを指定する乗客に乗合タクシー配車するためのタクシーの経路計画する。

解決手段

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

概要

背景

従来から、ピックアップ点からドロップオフ点まで移動したい乗客に、乗合タクシー配車するためのタクシーの経路計画する技術が提案されている。たとえば、非特許文献1では、SBI(Succesive Best Insertion)と呼ばれる技術が提案されている。

一方、複数の頂点を有するグラフの各頂点を1回だけ訪問するハミルトニアン路(Hamiltonian Path; HP)を求めるため、ハミルトニアン路の制約を連結標準形(conjunctive normal form)の論理式エンコードして、充足問題(boolean SATisfiability problem)として解く技術が提案されている。たとえば、非特許文献2では、relative encodingという技術が提案されている。充足問題を解くためのアルゴリズムプログラムモジュール、あるいは、当該プログラムを実行可能なコンピュータは、SATソルバと呼ばれることがある。

充足問題を解くにあたっては、連結標準形を構成する論理式の各節に重みを付与して擬似論理制約(pseudo-boolean constraints)とし、目的関数(objective function)を最小化する最適解を求める技術も提案されている。たとえば、非特許文献3では、繰り返し計算によって高速に最適解を求めるQMaxSATと呼ばれる技術が提案されている。

概要

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

目的

本発明によれば、ピックアップ点とドロップオフ点とを指定する乗客に乗合タクシーを配車するためのタクシーの経路を計画する経路計画装置、経路計画方法、ならびに、プログラムを提供する

効果

実績

技術文献被引用数
0件
牽制数
0件

この技術が所属する分野

(分野番号表示ON)※整理標準化データをもとに当社作成

ライセンス契約や譲渡などの可能性がある特許掲載中! 開放特許随時追加・更新中 詳しくはこちら

請求項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[λ]を満たすタクシーλ∈Λの経路を、前記最適解に基づいて更新する更新部を備えることを特徴とする経路計画装置

請求項2

前記ハミルトニアン路制約は、前記各タクシーλ∈Λの経路であるハミルトニアン路が満たすべき制約であって、(1)含意則(implication law): 互いに異なる任意の頂点a,b∈V[λ]について 〈a,b〉→ a≫b; (2)鎖遷移則(chain transition law): 互いに異なる任意の頂点a,b,c∈V[λ]についてa≫b ∧ b≫c → a≫c ∧ ¬〈a,c〉; (3)合流則(confluence law): 互いに異なる任意の頂点a,b,c∈V[λ]についてa≫b ∧ c≫b → a≫c ∨ c≫a; (4)分岐則(ramification law):互いに異なる任意の頂点a,b,c∈V[λ]についてa≫b ∧ a≫c → b≫c ∨ c≫b; (5)非巡回則(acyclic law): 互いに異なる任意の頂点a,b∈V[λ]について¬a≫b ∨ ¬b≫a; (6)ピックアップ点およびドロップオフ点の訪問制約: ∧λ∈Λ ∧a∈Φ[λ]∪Ψ[λ] ALO({〈x,a〉| x∈V[λ] }); (7)ピックアップ点からの出発制約: ∧λ∈Λ ∧P∈Φ[λ] ALO({〈P,y〉| y∈V[λ]\{O[λ]} }); (8)新たなピックアップ点の訪問制約: EO(∪λ∈Λ {〈x,L[λ]〉| x∈V[λ] }); (9)新たなドロップオフ点の訪問制約: EO(∪λ∈Λ {〈x,R[λ]〉| x∈V[λ] }); (10)新たなピックアップ点からの出発制約: EO(∪λ∈Λ {〈L[λ],y〉| y∈V[λ]\{O[λ]} }); (11)新たなドロップオフ点からの出発制約: AMO(∪λ∈Λ {〈R[λ],y〉| y∈V[λ]\{O[λ]} }); (12)現在点からの出発制約: ∧λ∈Λ Ψλ≠{} → ALO({〈O[λ],y〉| y∈V[λ]\{O[λ]} }); (13)非反射則(irreflexivity law): ∧λ∈Λ ∧x∈V[λ] ¬〈x,x〉∧ ¬x≫x; (14)始点制約: ∧λ∈Λ ∧x∈V[λ] ¬x≫O[λ]; (15)独占(monopoly)制約: ∧λ∈Λ ¬O[λ]≫L[λ] ∨ L[λ]≫R[λ], ∧λ∈Λ ¬O[λ]≫R[λ] ∨ L[λ]≫R[λ], AMO({L[λ]≫R[λ] | λ∈Λ})を含み、前記ソフト節は、∧λ∈Λ ∧x∈V[λ] ∧y∈V[λ] (¬O[λ]≫L[λ] ∨ ¬〈x,y〉, w〈x,y〉)を含むことを特徴とする請求項1に記載の経路計画装置。

請求項3

前記漸化解が求められる毎に、前記SATソルバ部は、前記求められた漸化解が非HP制約を満たすか否かを判定し、前記非HP制約を満たさない漸化解において、O[λ]≫L[λ]を満たすタクシーλ∈Λの経路の一部または全部であって、前記非HP制約を満たさない非充足経路を抽出し、前記抽出された非従属経路を表す論理式を特定し、前記特定された論理式の否定を、新たなハード節にエンコードし、前記エンコードされた新たなハード節を、以降に求められる漸化解ならびに前記最適解がさらに満たすべきハード節として追加することを特徴とする請求項1または2に記載の経路計画装置。

請求項4

前記各タクシーλには、乗客定員数Cλが定められ、前記求められた漸化解において、O[λ]≫L[λ]を満たすタクシーλの経路を当該タクシーλが終点まで移動する間、ΦλならびにΨλの要素が増減しても、当該タクシーλに乗車する乗客者数制約: |Ψλ|-|Φλ|≦Cλが成立し続ければ、前記非HP制約は満たされることを特徴とする請求項3に記載の経路計画装置。

請求項5

前記ピックアップ点L[λ]には、前記要求にさらに指定された最早ピックアップ時刻Dが対応付けられ、前記ピックアップ点P[λ,1], P[λ,2], …∈Φλのそれぞれには、最早ピックアップ時刻D[λ,1], D[λ,2], …が対応付けられ、前記求められた漸化解において、O[λ]≫L[λ]を満たすタクシーλ∈Λの経路に含まれる各頂点を訪問する訪問時刻を、前記評価されたコスト時間に基づいて推定し、前記経路に含まれるピックアップ点について推定された訪問時刻が、当該ピックアップ点に対応付けられる最早ピックアップ時刻より早いことが、すべてのピックアップ点についてなければ、前記非HP制約は満たされることを特徴とする請求項3または4に記載の経路計画装置。

請求項6

前記ドロップオフ点R[λ]には、前記要求にさらに指定された最遅ドロップオフ時刻Tが対応付けられ、前記ドロップオフ点Q[λ,1], Q[λ,2], …∈Ψλのそれぞれには、最遅ドロップオフ時刻T[λ,1], T[λ,2], …が対応付けられ、前記求められた漸化解において、O[λ]≫L[λ]を満たすタクシーλ∈Λの経路に含まれる各頂点を訪問する訪問時刻を、前記評価されたコスト時間に基づいて推定し、前記経路に含まれるドロップオフ点について推定された訪問時刻が、当該ドロップオフ点に対応付けられる最遅ドロップオフ時刻より遅いことがなければ、前記非HP制約は満たされることを特徴とする請求項3から5のいずれか1項に記載の経路計画装置。

請求項7

経路計画装置が、新たなピックアップ点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[λ]を満たすタクシーλ∈Λの経路を、前記最適解に基づいて更新することを特徴とする経路計画方法

請求項8

コンピュータを、新たなピックアップ点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[λ]を満たすタクシーλ∈Λの経路を、前記最適解に基づいて更新する更新部として機能させることを特徴とするプログラム

技術分野

0001

本発明は、ピックアップ点ドロップオフ点とを指定する乗客に乗合タクシー配車するためのタクシーの経路計画する経路計画装置経路計画方法、ならびに、プログラムに関する。

背景技術

0002

従来から、ピックアップ点からドロップオフ点まで移動したい乗客に、乗合タクシーを配車するためのタクシーの経路を計画する技術が提案されている。たとえば、非特許文献1では、SBI(Succesive Best Insertion)と呼ばれる技術が提案されている。

0003

一方、複数の頂点を有するグラフの各頂点を1回だけ訪問するハミルトニアン路(Hamiltonian Path; HP)を求めるため、ハミルトニアン路の制約を連結標準形(conjunctive normal form)の論理式エンコードして、充足問題(boolean SATisfiability problem)として解く技術が提案されている。たとえば、非特許文献2では、relative encodingという技術が提案されている。充足問題を解くためのアルゴリズム、プログラム、モジュール、あるいは、当該プログラムを実行可能なコンピュータは、SATソルバと呼ばれることがある。

0004

充足問題を解くにあたっては、連結標準形を構成する論理式の各節に重みを付与して擬似論理制約(pseudo-boolean constraints)とし、目的関数(objective function)を最小化する最適解を求める技術も提案されている。たとえば、非特許文献3では、繰り返し計算によって高速に最適解を求めるQMaxSATと呼ばれる技術が提案されている。

先行技術

0005

I. Noda, M. Ohta, K. Shinoda, Y. Kumada, and H. Nakashima. Evaluation of Usability of Dial-a-Ride Systems by Social Simulation. Multi-Agent-Based Simulation III, 4th International Workshop, MABS2003, Melbourne, Australa, July 14th, 2003, Revised Papers, volume 2927 of Lecture Notes in Computer Science, pages 167-181. Springer, 2003年. https://doi.org/10.1007/978-3-540-24613-8_12
S. Prestwich. SAT problems with chains of dependent variables. Discrete Applied Mathematics, vol.130, issue 2, pp.329-350, 2003年. https://doi.org/10.1016/S0166-218X(02)00410-9
A. Zha, M. Koshimura, and H. Fujita. N-level Modulo-Based CNF encodings of Pseudo-Boolean constraints for MaxSAT. Constraints, 2019年1月12日. https://doi.org/10.1007/s10601-018-9299-0

発明が解決しようとする課題

0006

しかしながら、乗合タクシーの配車をするための経路計画においては、従来よりも高速に最適解が得られる技術が強く求められている。

0007

また、当該経路計画においては、乗客定員数を満たすこと、ピックアップ時刻以降にタクシーがピックアップ点を訪問すること、ドロップオフ時刻以前にタクシーがドロップオフ点を訪問することなどの制約が課せられるが、これらは、SAT問題における論理式へのエンコードが難しい。

0008

本発明は、上記の課題を解決するもので、ピックアップ点とドロップオフ点とを指定する乗客に乗合タクシーを配車するためのタクシーの経路を計画する経路計画装置、経路計画方法、ならびに、プログラムに関する。

課題を解決するための手段

0009

本発明に係る乗合タクシーの経路計画装置は、
新たなピックアップ点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ソルバにより求め、
前記求められた最適解においてO[λ]≫L[λ]を満たすタクシーλ∈Λの経路を、前記最適解に基づいて更新する。

発明の効果

0010

本発明によれば、ピックアップ点とドロップオフ点とを指定する乗客に乗合タクシーを配車するためのタクシーの経路を計画する経路計画装置、経路計画方法、ならびに、プログラムを提供することができる。

図面の簡単な説明

0011

本発明の実施形態に係る経路計画装置の構成を示す説明図である。
本発明の実施形態に係る経路計画処理の制御の流れを示すフローチャートである。
本発明の実施形態に係る漸化解のチェック処理の制御の流れを示すフローチャートである。
従来技術と本実施形態との性能を対比する表である。
従来技術と本実施形態との性能をグレイスケール表示により対比するグラフである。
従来技術と本実施形態との性能をモノクロ二値表示により対比するグラフである。

実施例

0012

以下に、本発明の実施形態を説明する。なお、本実施形態は、説明のためのものであり、本発明の範囲を制限するものではない。したがって、当業者であれば、本実施形態の各要素もしくは全要素を、これと均等なものに置換した実施形態を採用することが可能である。また、各実施例にて説明する要素は、用途に応じて適宜省略することも可能である。このように、本発明の原理にしたがって構成された実施形態は、いずれも本発明の範囲に含まれる。

0013

(構成)
図1は、本発明の実施形態に係る経路計画装置の構成を示す説明図である。以下、本図を参照して説明する。

0014

本実施形態に係る経路計画装置101は、典型的には、プログラムをコンピュータが実行することによって実現される。当該コンピュータは、各種の出力装置入力装置に接続され、これらの機器と情報を送受する。

0015

コンピュータにて実行されるプログラムは、当該コンピュータが通信可能に接続されたサーバにより配布販売することができるほか、CD-ROM(Compact Disk Read Only Memory)やフラッシュメモリ、EEPROM(Electrically Erasable Programmable ROM)などの非一時的(non-transitory)な情報記録媒体に記録した上で、当該情報記録媒体を配布、販売等することも可能である。

0016

プログラムは、コンピュータが有するハードディスクソリッドステートドライブ、フラッシュメモリ、EEPROM等などの非一時的な情報記録媒体にインストールされる。すると、当該コンピュータにより、本実施形態における情報処理装置が実現されることになる。一般的には、コンピュータのCPU(Central Processing Unit)は、コンピュータのOS(Operating System)による管理の下、情報記録媒体からRAM(Random Access Memory)へプログラムを読み出してから、当該プログラムに含まれるコードを解釈、実行する。ただし、CPUがアクセス可能メモリ空間内に情報記録媒体をマッピングできるようなアーキテクチャでは、RAMへの明示的なプログラムのロードは不要なこともある。なお、プログラムの実行の過程で必要とされる各種情報は、RAM内に一時的(temporary)に記録しておくことができる。

0017

さらに、コンピュータは、CPUのほか、各種画像処理計算を高速に行うためのGPU(Graphics Processing Unit)を備えることが望ましい。GPUならびにTensorFlow等のライブラリを使うことで、CPUの制御の下、各種の人工知能処理における学習機能分類機能を利用することができるようになる。

0018

なお、汎用のコンピュータにより本実施形態の情報処理装置を実現するのではなく、専用の電子回路を用いて本実施形態の情報処理装置を構成することも可能である。この態様では、プログラムを電子回路の配線図やタイミングチャート等を生成するための素材として利用することもできる。このような態様では、プログラムに定められる仕様を満たすような電子回路がFPGA(Field Programmable Gate Array)やASIC(Application Specific IntegratedCircuit)により構成され、当該電子回路は、当該プログラムに定められた機能を果たす専用機器として機能して、本実施形態の情報処理装置を実現する。

0019

本実施形態に係る経路計画装置101は、典型的には、各種コンピュータ上にてプログラムを実行することにより、もしくは、専用の電子回路により、実現される。たとえば、経路計画装置101は、スーパーコンピュータハイパフォーマンスコンピュータなど、並列計算特化した計算速度が高速なコンピュータにて実現することができる。

0020

以下では、理解を容易にするため、経路計画装置101は、コンピュータがプログラムを実行することによって実現される態様を想定して説明する。

0021

本図に示すように、本実施形態に係る経路計画装置101は、要求受付部102、コスト評価部103、エンコード部104、SATソルバ部105、更新部106を備える。

0022

ここで、要求受付部102は、新たなピックアップ点L、および、新たなドロップオフ点Rを指定する要求を受け付ける。なお、当該要求には、ピックアップやドロップオフに関する時刻の制約、乗車予定の人数などの情報を含めることとしても良い。

0023

一方、コスト評価部103は、
稼働中の複数のタクシーの集合Λにおける各タクシーλ∈Λに対する頂点の集合であって、
当該各タクシーλが現在所在する現在点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〉
を評価する。

0024

すなわち、本実施形態では、各タクシーλについて、既にピックアップ点Φλおよびドロップオフ点Ψλが計画済であり、これらの情報がハードディスクやメモリ等の記憶媒体あるいは他のサーバコンピュータ等に記憶されるとともに、各タクシーλの現在点Oλが、GPS(Global Positioning System)等のジオロケーション技術によって収集されている状況を想定する。

0025

なお、典型的には、各タクシーλについてのピックアップ点Φλおよびドロップオフ点Ψλの情報のほか、各タクシーλの乗客定員数、どのような順に各点を辿るか、の順序や、各点に到達すべき最早時刻・最遅時刻などの情報も、合わせて記憶される。

0026

その上で、要求受付部102により、受け付けられた新たなピックアップ点Lおよびドロップオフ点Rを、どのタクシーが担当すべきか、を決定するため、コスト評価部103は、ある点から別の点までの移動にタクシーが要するコスト時間を評価する。

0027

ここで、本実施形態では、グラフ理論における用語に基づき、タクシーがピックアップもしくはドロップオフのために訪問しうる場所を「頂点」と呼び、ある頂点から別の頂点まで直接移動する経路を「有向辺」と呼ぶ。

0028

なお、ある頂点から別の頂点へ直接移動する経路と、当該別の頂点から当該ある頂点へ直接移動する経路と、は、逆向きの有向辺となるが、たとえば一方通行などの交通規制道路混雑状況等によって、往路と復路でコスト時間が異なることがある。また、現実世界では往路と復路が異なる経路となることもありうる。

0029

また、タクシーλが訪問しうる頂点の集合、すなわち、すでに訪問すると計画されたピックアップ点およびドロップオフ点ならびに新たに受け付けられたピックアップ点およびドロップオフ点の集合を、V[λ]と標記する。

0030

また、互いに異なる頂点a,b∈V[λ]について、頂点aから頂点bへ直接向かう経路の有無を、論理変数〈a,b〉により標記する。〈a,b〉が真であれば、タクシーλは頂点aから頂点bへ直接移動すべきであり、であれば、そうではない(頂点aから頂点bへの有向辺は存在しない)ことになる。

0031

一方、互いに異なる頂点a,b∈V[λ]について、頂点aを経て頂点bへ至る経路の有無は、論理変数a≫bにより標記される。

0032

たとえば、〈a,b〉が真であれば、頂点aから頂点bへの有向辺が存在することになるから、a≫bも真であることになる。

0033

また、このほか、頂点a,b,x∈V[λ]について、〈a,x〉と〈x,b〉がいずれも真であれば、頂点aから頂点bへ頂点xを介した経路が存在することになるから、a≫bも真であることになる。

0034

ここで、〈a,b〉やa≫bとの標記は、一見するとaとbの2項演算であるかのように見えるが、これらは、あくまで論理変数を表現するものである。すなわち、これらは、それぞれ、論理値行列あるいは二次元配列の各要素に相当するものである。

0035

さて、エンコード部104は、論理変数a≫bと、論理変数〈a,b〉と、により表現される
ハミルトニアン路(Hamiltonian path; HP)制約を、ハード節へ、
目的関数Σλ∈Λ Σx∈V[λ] Σy∈V[λ] O[λ]≫L[λ] ・〈x,y〉・w〈x,y〉を、ソフト節へ、
それぞれエンコードする。

0036

ここで、ハード節は、擬似論理制約において必ず充足しなければならない制約に相当し、ソフト節は、擬似論理制約において重みが付与された制約に相当する。

0037

また、上記の目的関数は、全タクシーが現在点から新たなピックアップ点Lに至るまでに要する時間の総和を表現しているが、後述のように、目的関数は最小化されるので、λ∈Λのうち、O[λ]≫L[λ]が真となるλが一つだけ定まり、当該唯一のλに対するタクシーλが、新たなピックアップ点Lに向かうことになる。

0038

本実施形態では、各タクシーλ∈Λの経路であるハミルトニアン路が満たすべき制約をハミルトニアン路制約としており、具体的には、以下のような制約を含むように構成する。

0039

(1)含意則(implication law): 互いに異なる任意の頂点a,b∈V[λ]について
〈a,b〉→ a≫b;
これは、頂点aから頂点bへ直接向かう有向辺が存在するならば、頂点aから頂点bへ至る経路が存在することを表している。

0040

(2)鎖遷移則(chain transition law): 互いに異なる任意の頂点a,b,c∈V[λ]について
a≫b ∧ b≫c → a≫c ∧ ¬〈a,c〉;
これは、頂点aから頂点bへ直接向かう有向辺および頂点bから頂点cへ直接向かう有向辺があるならば、頂点aから頂点cへ至る経路が存在することを表すとともに、頂点aから頂点cへ直接向かう有向辺は存在しない(不要である)ことを表している。すなわち、タクシーλは、間に他の頂点を適宜挟みながら、頂点a, b, cの順に訪問することになる。

0041

(3)合流則(confluence law): 互いに異なる任意の頂点a,b,c∈V[λ]について
a≫b ∧ c≫b → a≫c ∨ c≫a;
これは、頂点aから頂点bへ至る経路、および、頂点cへから頂点bへ至る経路が存在するならば、頂点aから頂点cへ至る経路もしくはその逆の経路があることを表している。タクシーλは、間に他の頂点を適宜挟みながら、前者の場合は、頂点a, c, bの順に訪問することになり、後者の場合は、頂点c, a, bの順に訪問することになる。

0042

(4)分岐則(ramification law): 互いに異なる任意の頂点a,b,c∈V[λ]について
a≫b ∧ a≫c → b≫c ∨ c≫b;
これは、頂点aから頂点bへ至る経路、および、頂点aへから頂点cへ至る経路が存在するならば、頂点bから頂点cへ至る経路もしくはその逆の経路があることを表している。タクシーλは、間に他の頂点を適宜挟みながら、前者の場合は、頂点a, b, cの順に訪問することになり、後者の場合は、頂点a, c, bの順に訪問することになる。

0043

(5)非巡回則(acyclic law): 互いに異なる任意の頂点a,b∈V[λ]について
¬a≫b ∨ ¬b≫a;
これは、
¬(a≫b ∧ b≫a);
同値である。すなわち、「頂点aから頂点bへ至る経路とその逆の経路が両立する」ことはないことを意味する。

0044

(6)ピックアップ点およびドロップオフ点の訪問制約:
∧λ∈Λ ∧a∈Φ[λ]∪Ψ[λ] ALO({〈x,a〉| x∈V[λ] });
ここで、論理変数x1, x2, …, xnの集合X={x1, x2, …, xn}について、
ALO(X)は、x1, x2, …, xnの少なくとも1つ(at least one)が真であること、
AMO(X)は、x1, x2, …, xnの多くとも1つ(at most one)が真であること、
EO(X)は、x1, x2, …, xnの唯1つ(exact one)が真であること
をそれぞれ表す。すなわち、
AMO(X) = ∧i=1n ∧j=i+1n (¬xi ∨ ¬xj);
ALO(X) = ∨i=1n xi;
EO(X) = AMO(X) ∧ ALO(X)
である。
訪問制約は、タクシーλが今後訪問するピックアップ点およびドロップオフ点に向かう有向辺が、少なくとも1つ存在することを意味する。

0045

(7)ピックアップ点からの出発制約:
∧λ∈Λ ∧P∈Φ[λ] ALO({〈P,y〉| y∈V[λ]\{O[λ]} });
ここで、集合X, Yについての演算X\Yは、差集合を意味する。すなわち、
X\Y = {z|x∈X ∧ ¬x∈Y}
である。
出発制約は、タクシーが今後訪問するピックアップ点から発する有向辺が、少なくとも1つ存在することを意味する。

0046

上記(1)-(7)がすべて満たされれば、各タクシーλは、Φλ∪Ψλに含まれる各頂点を唯1回訪問することになり、Φλに含まれる各頂点から唯1回出発することになる。

0047

(8)新たなピックアップ点の訪問制約:
EO(∪λ∈Λ {〈x,L[λ]〉| x∈V[λ] });
(9)新たなドロップオフ点の訪問制約:
EO(∪λ∈Λ {〈x,R[λ]〉| x∈V[λ] });
制約(8)(9)は、新たなピックアップ点および新たなドロップオフ点を訪問するタクシーが唯1つであるための制約である。

0048

(10)新たなピックアップ点からの出発制約:
EO(∪λ∈Λ {〈L[λ],y〉| y∈V[λ]\{O[λ]} });
(11)新たなドロップオフ点からの出発制約:
AMO(∪λ∈Λ {〈R[λ],y〉| y∈V[λ]\{O[λ]} });
制約(10)(11)は、新たなドロップオフ点から出発するタクシーが多くとも1台であることための制約である。

0049

(12)現在点からの出発制約:
∧λ∈Λ Ψλ≠{} → ALO({〈O[λ],y〉| y∈V[λ]\{O[λ]} });
これは、各タクシーについて、訪問すべきであるのに未だ訪問していない点があれば、現在点からその点のいずれかへ向かう有向辺が必要であることを意味する。

0050

(13)非反射則(irreflexivity law):
∧λ∈Λ ∧x∈V[λ] ¬〈x,x〉∧ ¬x≫x;
これは、循環的な経路、同じ点に戻ってくる経路を除去するための制約である。

0051

(14)始点制約:
∧λ∈Λ ∧x∈V[λ] ¬x≫O[λ];
これは、現在点へ向かう経路(現在点へ戻る経路)がないことを保証するための制約である。

0052

(15)独占(monopoly)制約:
∧λ∈Λ ¬O[λ]≫L[λ] ∨ L[λ]≫R[λ],
∧λ∈Λ ¬O[λ]≫R[λ] ∨ L[λ]≫R[λ],
AMO({L[λ]≫R[λ] | λ∈Λ})
これらは、現在点O[λ]からピックアップ点P[λ]とドロップオフ点Q[λ]を訪問するのが、タクシーλの唯1つに限られることを保証するための制約である。

0053

また、本実施形態では、ソフト節として、
∧λ∈Λ ∧x∈V[λ] ∧y∈V[λ] (¬O[λ]≫L[λ] ∨ ¬〈x,y〉, w〈x,y〉)
を含むように構成する。
なお、ソフト節から¬O[λ]≫L[λ]を除去するだけで、全タクシーの時間コストの総量が得られる。したがって、これを目的関数として最小化をすることで、総稼働時間を最適化することができる。

0054

タクシーがm台(すなわち|Λ|=m)であり、未だ訪問していない点の数の最大数がn(maxλ∈Λ|V[λ]|=n, n≧3)であるとき、上記(1)-(15)およびソフト節をエンコードした結果は、総数O(mn2)のオーダーの論理変数を含み、節数O(mn3+m2n2)のオーダーの論理節を含むことになる。現実的な問題におけるm, nを考慮すると、これらのオーダーは、QMaxSAT等の公知技術において、全タクシーの経路計画をまとめて、リアルタイムで処理することが可能なオーダーである。

0055

さて、SATソルバ部105は、エンコードされたハード節を満たし、エンコードされたソフト節に係る目的関数を次第に減少させる漸化解を順次求めることにより、目的関数を最小化する最適解を、SATソルバにより、求める。ここでは、非特許文献3に開示される技術を適用することが可能である。

0056

ここで、SATソルバ部105は、漸化解が求められる毎に、
求められた漸化解が非HP制約を満たすか否かを判定し、
非HP制約を満たさない漸化解において、O[λ]≫L[λ]を満たすタクシーλ∈Λの経路の一部または全部であって、非HP制約を満たさない非充足経路を抽出し、
抽出された非従属経路を表す論理式を特定し、
特定された論理式の否定を、新たなハード節にエンコードし、
エンコードされた新たなハード節を、以降に求められる漸化解ならびに最適解がさらに満たすべきハード節として追加する。

0057

非HP制約とは、上記(1)-(15)ならびにソフト節によっては表現されない制約のことであり、たとえば、タクシーの乗客定員の制約や、ピックアップ点やドロップオフ点に到着すべき時刻の制約をいう。以下、具体例を説明する。

0058

乗客定員数の制約:
各タクシーλには、乗客定員数Cλが定められ、
求められた漸化解において、O[λ]≫L[λ]を満たすタクシーλの経路を当該タクシーλが終点まで移動する間、ΦλならびにΨλの要素が増減しても、当該タクシーλに乗車する乗客者数制約:
|Ψλ|-|Φλ|≦Cλ
成立し続ければ、非HP制約は満たされる。

0059

ピックアップ点に到着する時刻の制約:
ピックアップ点L[λ]には、要求にさらに指定された最早ピックアップ時刻Dが対応付けられ、
ピックアップ点P[λ,1], P[λ,2], …∈Φλのそれぞれには、最早ピックアップ時刻D[λ,1], D[λ,2], …が対応付けられ、
求められた漸化解において、O[λ]≫L[λ]を満たすタクシーλ∈Λの経路に含まれる各頂点を訪問する訪問時刻を、評価されたコスト時間に基づいて推定し、
経路に含まれるピックアップ点について推定された訪問時刻が、当該ピックアップ点に対応付けられる最早ピックアップ時刻より早いことが、すべてのピックアップ点についてなければ、非HP制約は満たされる。

0060

ドロップオフ点に到着する時刻の制約:
ドロップオフ点R[λ]には、要求にさらに指定された最遅ドロップオフ時刻Tが対応付けられ、
ドロップオフ点Q[λ,1], Q[λ,2], …∈Ψλのそれぞれには、最遅ドロップオフ時刻T[λ,1], T[λ,2], …が対応付けられ、
求められた漸化解において、O[λ]≫L[λ]を満たすタクシーλ∈Λの経路に含まれる各頂点を訪問する訪問時刻を、評価されたコスト時間に基づいて推定し、
経路に含まれるドロップオフ点について推定された訪問時刻が、当該ドロップオフ点に対応付けられる最遅ドロップオフ時刻より遅いことがなければ、非HP制約は満たされる。

0061

HP制約は満たすが、非HP制約は満たさない経路計画は、採用することができない。そこで、本実施形態では、HP制約は満たすが、非HP制約は満たさない経路計画の経路の一部または全部を抽出し、当該抽出された経路を否定した論理節を、ハード節としてSATソルバに追加し、再度計算をさせることで、HP制約と非HP制約の両方を満たす経路計画を高速に求めることができるようになる。

0062

そして、更新部106は、求められた最適解においてO[λ]≫L[λ]を満たすタクシーλ∈Λの経路を、最適解に基づいて更新する。上記のように、λ∈Λのうち、O[λ]≫L[λ]を満たすものは、唯一つであり、タクシーλの経路が新たな要求に応じて再計画されたことになる。

0063

以下では、本実施形態に係る経路計画装置101が実行する経路計画処理について説明する。図2は、本発明の実施形態に係る経路計画処理の制御の流れを示すフローチャートである。以下、本図を参照して説明する。

0064

本処理が開始されると、経路計画装置101は、経路計画を初期化する(ステップS301)。典型的には、各タクシーλについて、ピックアップ点およびドロップオフ点が存在しない、すなわち、Φλ = Ψλ = {}のように初期化する。ただし、既に経路計画が存在する状況で、新たに処理を開始する場合には、既存の経路計画により初期化をすることとしても良い。

0065

ついで、経路計画装置101は、外部機器からの連絡を受け付ける(ステップS302)。

0066

受け付けた連絡が、新たなピックアップ点Lおよび新たなドロップオフ点Rを指定する要求であれば(ステップS303;要求)、経路計画装置101は、各タクシーλの現在点Oλを取得する(ステップS304)。

0067

そして、経路計画装置101は、新たなピックアップ点Lおよび新たなドロップオフ点Rを各タクシーλに割り振り、各タクシーλ∈Λが訪問しうる点の集合V[λ]を生成する(ステップS305)。

0068

ついで、経路計画装置101は、集合V[λ]のある要素aから別の要素bへの移動に要するコスト時間w〈a,b〉を評価する(ステップS306)。コスト時間は、従来の実績から推定しても良いし、リアルタイムの交通情報等を参照して推定しても良い。

0069

そして、経路計画装置101は、HP制約および目的関数をハード節およびソフト節へエンコードする(ステップS307)。理解を容易にするため、エンコードされた結果を、
C[1] ∧ … ∧ C[m] ∧ (C[m+1],w[1]) ∧ … ∧ (C[m+n],w[n])
とする。ここで、
C[1], …, C[m]は、ハード節(m個)、
(C[m+1],w[1]), …, (C[m+n],w[n])は、ソフト節(n個)、
w[1], …, w[n]は、各ソフト節の重み(n個)
である。

0070

ついで、経路計画装置101は、漸化値kの繰り返しの初期値を設定する(ステップS308)。初期値は、最も簡単には、
k ← 1 + Σi=1n w[i]
とすることができ、この値は、後述するステップS331において、いわゆる番(sentinel)としても機能する。

0071

そして、経路計画装置101は、SATソルバにハード節C[1], …, C[m]およびソフト節(C[m+1],w[1]), …, (C[m+n],w[n])を与え(ステップS309)、SATソルバに、与えられた節を満たす解A(各論理変数および論理節の真偽)を1つ見つけさせる(ステップS310)。

0072

そして、解Aが見つかったら(ステップS311;Yes)、経路計画装置101は、求められた解Aが、非HP制約を満たすか否かをチェックする(ステップS312)。図3は、本発明の実施形態に係る漸化解のチェック処理の制御の流れを示すフローチャートである。以下、本図を参照して説明する。

0073

チェック処理では、経路計画装置101は、解Aにおいて、要求に応じるタクシー、すなわち、要求に係るピックアップ点およびドロップオフ点を訪問するとされているタクシーと、その乗客数と、を特定する(ステップS401)。具体的には、解Aにおいて、O[λ]≫L[λ]を満たすλを特定すれば良い。

0074

当該タクシーの経路は、有向辺の列、すなわち、真である論理変数の列
〈O[λ],x1〉, 〈x1,x2〉,〈x2,x3〉,…
により、表現することができる。

0075

そこで、経路計画装置101は、タクシーλが訪問する頂点のうち、注目点xをO[λ]に設定してから(ステップS402)、真である論理変数〈x,y〉、すなわち、〈x,y〉=1を満たすyを特定する(ステップS403)。

0076

〈x,y〉=1である論理変数が、解Aから特定できれば、タクシーλが次に訪問すべき点yが見つかった(ステップS404;Yes)ことになる。そこで、経路計画装置101は、タクシーλの稼働時間にコスト時間w〈x,y〉を積算する(ステップS405)。

0077

ついで、経路計画装置101は、現在時刻と、積算された稼働時間と、の和が、タクシーλが点yに到着すべき時刻の条件(最早ピックアップ時刻や最遅ドロップオフ時刻に関する条件)を満たしていなければ、すなわち、時間超過が生じていれば(ステップS406;Yes)、本処理が開始されてからステップS403において順次特定された論理変数の論理積を、非充足経路を表す論理式に設定した上で(ステップS407)、非HP制約を満たさない旨を返す(ステップS408)。

0078

時間超過しておらず(ステップS406;No)、点yがピックアップ点であれば(ステップS409;Yes)、タクシーλの乗客数を増やし(ステップS410)、当該乗客数が乗客定員数Cλを超えていれば(ステップS411;Yes)、処理をステップS407に進め、超えていなければ(ステップS411;No)、処理をステップS403に進める。

0079

点yがピックアップ点でなければ、(ステップS409;No)、点yはドロップオフ点ということになるので、タクシーλの乗客数を減らす(ステップS412)。

0080

ステップS412の後、あるいは、乗客超過していない場合(ステップS411;No)、注目点xを注目点yで再設定して(ステップS413)、制御をステップS403に戻し、上記の処理を繰り返す。

0081

さて、〈x,y〉=1である論理変数が解Aから見つからなければ(ステップS404;No)、タクシーλについて計画された全経路を辿ったことになり、非HP制約が満たされたことになるので、その旨を返す(ステップS414)。

0082

このように、本処理によって、非HP制約が満たされる場合には、その旨が返され、非HP制約が満たされない場合には、その旨ならびに非HP制約を満たさない原因となった非充足経路を表す論理式が得られることになる。

0083

さて、図2に戻って説明を続ける。求められた解が非HP制約を満たすならば(ステップS312;Yes)、経路計画装置101は、当該解Aにおいて偽であるソフト節Cの重みの総和により、漸化値kを再設定する(ステップS313)。すなわち、
k ← ΣA(C[m+i]=0 w[i]

0084

そして、経路計画装置101は、再設定された漸化値kにより表現される擬似論理制約
Σi=1n (w[i]¬C[m+i] < k)
をソフト節にエンコードして(ステップS314)、エンコードされたソフト節をSATソルバに追加して与える(ステップS315)。

0085

そして、経路計画装置101は、SATソルバに、過去(ステップS309、ステップS315および後述するステップS323)に与えられた節を満たす解Aを再度求めさせる(ステップS316)。

0086

解Aが求められれば(ステップS317;Yes)、経路計画装置101は、制御をステップS312に戻し、解Aが求められなければ(ステップS317;No)、経路計画装置101は、繰り返しを終了して、制御をステップS331へ進める。

0087

一方、非HP制約を満たさなければ(ステップS312;No)、経路計画装置101は、非HP制約を満たさない原因となった非充足経路を表す論理式を特定し(ステップS321)、当該特定された論理式の否定を表すハード節にエンコードして(ステップS322)、SATソルバに追加して与える(ステップS323)。

0088

そして、経路計画装置101は、制御をステップS316に進め、SATソルバに解を求めさせる。

0089

このような繰り返しを行うことで、漸化値kは次第に減少し、順次得られる解Aは、最適解に漸近的に近付くことになる。

0090

解が見つからなかった場合(ステップS311;No)や、繰り返しが終了(ステップS317;No)した後、経路計画装置101は、HP制約および非HP制約を満たす解Aが求められているか否かを判定する(ステップS331)。

0091

なお、繰り返しが終了した後、漸化値kが、ステップS307における初期値に等しければ、解が求められなかったことになり、初期値よりも小さければ、解が求められたことになる。したがって、前述のように、ステップS307における初期値は、番兵として機能することになる。

0092

求められていれば(ステップS331;Yes)、最後に求められた解Aのうち、要求に係るピックアップ点およびドロップオフ点を訪問するタクシー、すなわち、O[λ]≫L[λ]を満たすタクシーλのピックアップ点Lλおよびドロップオフ点Rλを、それぞれΦλ, Ψλに追加することによりタクシーλの経路を更新する(ステップS332)。

0093

そして、経路計画装置101は、O[λ]から出る有向辺を辿る経路に沿って移動するように、タクシーλに更新された経路を指示して(ステップS333)、制御をステップS302に戻す。

0094

本処理によれば、各タクシーについて一旦訪問すると決定されたピックアップ点およびドロップオフ点がキャンセルされることはないことになる。

0095

また、
Σi=1nw[i] - k
は、タクシーの総稼働時間に相当する。

0096

さて、経路計画装置101は、HP制約および非HP制を満たす解が求められていなければ(ステップS331;No)、経路計画に失敗した旨を出力して(ステップS334)、制御をステップS302に戻す。

0097

経路計画に失敗した、ということは、タクシーの配車ができないことを意味するため、ユーザは、希望の条件(たとえば、到着時刻の制約等)を変更して再度要求をするか、配車を断念するか、のいずれかを選択することになる。

0098

さて、外部機器から到着した連絡が、タクシーλがいずれかのピックアップ点もしくはドロップオフ点に到着した旨の報告である場合(ステップS303;報告)、経路計画におけるΦλもしくはΨλから、タクシーλが到着した点を除去して(ステップS341)、制御をステップS302に戻す。

0099

上記の説明では、本実施形態に係る主要な制御の流れを説明したが、これ以外の処理を、各ステップの間に適宜追加することとしても良い。

0100

(実験結果)
本実施形態(SAT)を、非特許文献1に開示される技術(SBI)と対比するためのシミュレーション実験を行った。

0101

当該シミュレーション実験では、現実世界のデータをシミュレートするため、オープンソースで提供されている交通シミュレーションパッケージであるSUMO(Simulation of Urban MObility)を利用した。

0102

タクシーの数(#Taxi)nは20, 30, 40, 50のいずれかとし、要求が発生する頻度(Dof;Demand occurence frequency)fを1時間あたり18, 24, 36, 72のいずれかとし、各要求に係る乗客数は1とし、タクシーの乗客定員数は5とし、到着時刻の制約をランダムに定め、シミュレーション時間を42000秒として、乗客の平均移動速度(Avg.speed)、積算シェア率(Cumul.share)、および、要求を処理するための平均計算時間(Avg.runtime)を求めた。

0103

図4は、従来技術と本実施形態との性能を対比する表である。本表では、パラメータ設定(Param.setting)につき、たとえば、「タクシー20台、頻度18回/時間」を「n20-f18」のように標記している。また、SATのAvg.runtimeは、エンコードに要した時間AとSATソルバに要した時間Bを「A+B」の形で標記している。

0104

本表を見ると、SATについては、「n20-f72」を除き、エンコード時間がSATソルバ時間よりも短いことがわかる。したがって、多くの場合、本願に係る擬似論理制約のエンコードは、SATソルバの探査空間を小さくすることに役立っていることがわかる。

0105

「n20-f72」は、タクシーの数に対して要求頻度が高すぎ、サービスの提供が不十分な場合に相当すると考えられ、本実験でも、要求が満たされる割合は、SBIでは27.48%、SATでは29.85%であり、SATの性能が優れていることがわかる。

0106

一方、それ以外のケースでは、要求はすべて満たされており、リアルタイムで対応可能な計算時間で、経路計画を策定することが可能であることが示された。

0107

図5は、従来技術と本実施形態との性能をグレイスケール表示により対比するグラフである。図6は、従来技術と本実施形態との性能をモノクロ二値表示により対比するグラフである。これらのグラフでは、縦軸はDof、横軸は#Taxiであり、プロットされる線の色によってAvg.speedを表現している。

0108

これらのグラフからわかるように、#Taxiが小さくなるにつれ、ならびに、Dofが大きくなるにつれ、Avg.speedが小さくなることがわかる。

0109

また、一般的なグラフの傾きは、SATの方がSBIよりも大きい。

0110

Dofが40を超えると、SBIもSATも下向きのグラフが現れるが、下向きのグラフが出現する局面が、SBIでは#Taxiが40を超えた場合であるのに対し、SATでは#Taxiが40を超えた場合である。したがって、タクシーの数が少ない場合であっても、SATの方がより性能の高い経路計画ができていることがわかる。

0111

(まとめ)

0112

以上説明した通り、本実施形態に係る乗合タクシーの経路計画装置は、
新たなピックアップ点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[λ]を満たすタクシーλ∈Λの経路を、前記最適解に基づいて更新する更新部
を備える。

0113

また、本実施形態に係る経路計画装置において、
前記ハミルトニアン路制約は、前記各タクシーλ∈Λの経路であるハミルトニアン路が満たすべき制約であって、
(1)含意則(implication law): 互いに異なる任意の頂点a,b∈V[λ]について
〈a,b〉→ a≫b;
(2)鎖遷移則(chain transition law): 互いに異なる任意の頂点a,b,c∈V[λ]について
a≫b ∧ b≫c → a≫c ∧ ¬〈a,c〉;
(3)合流則(confluence law): 互いに異なる任意の頂点a,b,c∈V[λ]について
a≫b ∧ c≫b → a≫c ∨ c≫a;
(4)分岐則(ramification law): 互いに異なる任意の頂点a,b,c∈V[λ]について
a≫b ∧ a≫c → b≫c ∨ c≫b;
(5)非巡回則(acyclic law): 互いに異なる任意の頂点a,b∈V[λ]について
¬a≫b ∨ ¬b≫a;
(6)ピックアップ点およびドロップオフ点の訪問制約:
∧λ∈Λ ∧a∈Φ[λ]∪Ψ[λ] ALO({〈x,a〉| x∈V[λ] });
(7)ピックアップ点からの出発制約:
∧λ∈Λ ∧P∈Φ[λ] ALO({〈P,y〉| y∈V[λ]\{O[λ]} });
(8)新たなピックアップ点の訪問制約:
EO(∪λ∈Λ {〈x,L[λ]〉| x∈V[λ] });
(9)新たなドロップオフ点の訪問制約:
EO(∪λ∈Λ {〈x,R[λ]〉| x∈V[λ] });
(10)新たなピックアップ点からの出発制約:
EO(∪λ∈Λ {〈L[λ],y〉| y∈V[λ]\{O[λ]} });
(11)新たなドロップオフ点からの出発制約:
AMO(∪λ∈Λ {〈R[λ],y〉| y∈V[λ]\{O[λ]} });
(12)現在点からの出発制約:
∧λ∈Λ Ψλ≠{} → ALO({〈O[λ],y〉| y∈V[λ]\{O[λ]} });
(13)非反射則(irreflexivity law):
∧λ∈Λ ∧x∈V[λ] ¬〈x,x〉∧ ¬x≫x;
(14)始点制約:
∧λ∈Λ ∧x∈V[λ] ¬x≫O[λ];
(15)独占(monopoly)制約:
∧λ∈Λ ¬O[λ]≫L[λ] ∨ L[λ]≫R[λ],
∧λ∈Λ ¬O[λ]≫R[λ] ∨ L[λ]≫R[λ],
AMO({L[λ]≫R[λ] | λ∈Λ})
を含み、
前記ソフト節は、
∧λ∈Λ ∧x∈V[λ] ∧y∈V[λ] (¬O[λ]≫L[λ] ∨ ¬〈x,y〉, w〈x,y〉)
を含む
ように構成することができる。

0114

また、本実施形態に係る経路計画装置において、
前記漸化解が求められる毎に、前記SATソルバ部は、
前記求められた漸化解が非HP制約を満たすか否かを判定し、
前記非HP制約を満たさない漸化解において、O[λ]≫L[λ]を満たすタクシーλ∈Λの経路の一部または全部であって、前記非HP制約を満たさない非充足経路を抽出し、
前記抽出された非従属経路を表す論理式を特定し、
前記特定された論理式の否定を、新たなハード節にエンコードし、
前記エンコードされた新たなハード節を、以降に求められる漸化解ならびに前記最適解がさらに満たすべきハード節として追加する
ように構成することができる。

0115

また、本実施形態に係る経路計画装置において、
前記各タクシーλには、乗客定員数Cλが定められ、
前記求められた漸化解において、O[λ]≫L[λ]を満たすタクシーλの経路を当該タクシーλが終点まで移動する間、ΦλならびにΨλの要素が増減しても、当該タクシーλに乗車する乗客者数制約:
|Ψλ|-|Φλ|≦Cλ
が成立し続ければ、前記非HP制約は満たされる
ように構成することができる。

0116

また、本実施形態に係る経路計画装置において、
前記ピックアップ点L[λ]には、前記要求にさらに指定された最早ピックアップ時刻Dが対応付けられ、
前記ピックアップ点P[λ,1], P[λ,2], …∈Φλのそれぞれには、最早ピックアップ時刻D[λ,1], D[λ,2], …が対応付けられ、
前記求められた漸化解において、O[λ]≫L[λ]を満たすタクシーλ∈Λの経路に含まれる各頂点を訪問する訪問時刻を、前記評価されたコスト時間に基づいて推定し、
前記経路に含まれるピックアップ点について推定された訪問時刻が、当該ピックアップ点に対応付けられる最早ピックアップ時刻より早いことが、すべてのピックアップ点についてなければ、前記非HP制約は満たされる
ように構成することができる。

0117

また、本実施形態に係る経路計画装置において、
前記ドロップオフ点R[λ]には、前記要求にさらに指定された最遅ドロップオフ時刻Tが対応付けられ、
前記ドロップオフ点Q[λ,1], Q[λ,2], …∈Ψλのそれぞれには、最遅ドロップオフ時刻T[λ,1], T[λ,2], …が対応付けられ、
前記求められた漸化解において、O[λ]≫L[λ]を満たすタクシーλ∈Λの経路に含まれる各頂点を訪問する訪問時刻を、前記評価されたコスト時間に基づいて推定し、
前記経路に含まれるドロップオフ点について推定された訪問時刻が、当該ドロップオフ点に対応付けられる最遅ドロップオフ時刻より遅いことがなければ、前記非HP制約は満たされる
ように構成することができる。

0118

本実施形態に係る経路計画方法は、経路計画装置が、
新たなピックアップ点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[λ]を満たすタクシーλ∈Λの経路を、前記最適解に基づいて更新する
ように構成する。

0119

本実施形態に係るプログラムは、コンピュータを、
新たなピックアップ点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[λ]を満たすタクシーλ∈Λの経路を、前記最適解に基づいて更新する更新部
として機能させる。

0120

本発明は、本発明の広義の精神と範囲を逸脱することなく、様々な実施の形態及び変形が可能とされるものである。また、上述した実施の形態は、この発明を説明するためのものであり、本発明の範囲を限定するものではない。すなわち、本発明の範囲は、実施の形態ではなく、特許請求の範囲によって示される。そして、特許請求の範囲内及びそれと同等の発明の意義の範囲内で施される様々な変形が、この発明の範囲内とみなされる。

0121

本発明によれば、ピックアップ点とドロップオフ点とを指定する乗客に乗合タクシーを配車するためのタクシーの経路を計画する経路計画装置、経路計画方法、ならびに、プログラムを提供することができる。

0122

101経路計画装置
102要求受付部
103コスト評価部
104エンコード部
105 SATソルバ部
106更新部

ページトップへ

この技術を出願した法人

この技術を発明した人物

ページトップへ

関連する挑戦したい社会課題

関連する公募課題

ページトップへ

技術視点だけで見ていませんか?

この技術の活用可能性がある分野

分野別動向を把握したい方- 事業化視点で見る -

(分野番号表示ON)※整理標準化データをもとに当社作成

ページトップへ

おススメ サービス

おススメ astavisionコンテンツ

新着 最近 公開された関連が強い技術

この 技術と関連性が強い人物

関連性が強い人物一覧

この 技術と関連する社会課題

関連する挑戦したい社会課題一覧

この 技術と関連する公募課題

関連する公募課題一覧

astavision 新着記事

サイト情報について

本サービスは、国が公開している情報(公開特許公報、特許整理標準化データ等)を元に構成されています。出典元のデータには一部間違いやノイズがあり、情報の正確さについては保証致しかねます。また一時的に、各データの収録範囲や更新周期によって、一部の情報が正しく表示されないことがございます。当サイトの情報を元にした諸問題、不利益等について当方は何ら責任を負いかねることを予めご承知おきのほど宜しくお願い申し上げます。

主たる情報の出典

特許情報…特許整理標準化データ(XML編)、公開特許公報、特許公報、審決公報、Patent Map Guidance System データ