タクシー配車でeREXができること

ニーズ

●　マルチスタート（タクシー）／シングルゴール（顧客）の経路探索が望まれている。
●　究極的には、複数の顧客からの呼び出しを一気に解決することが望ましい。

シーズ

●　eREXには、複数の起点及び終点についての経路探索を高速化する方法が2種類存在する

顧客に最適な車両の検索

● Step1　一括経路探索を１回だけ実行

複数タクシー（起点）は「曖昧な指示制御点」、複数顧客（終点）は「終点の複数化」として実現します。

タクシーの重複割り当てが含まれない図１のようなパターンであれば、一括経路探索１回でタクシー数×顧客数回の経路検索と同等の結果が得られ、完全に最適なタクシーの割り当てが求められます。

しかし、この方法の問題点は、タクシーの重複割り当てが発生し得る点です。 （図 2参照）
図 2では、図1と比較してP6が追加されたために、T03の重複割り当てが発生しています。

タクシーの重複割り当てが発生した場合は、次のステップに進みます。

● Step2a　一括経路探索を最低１回実行

図 2ではP1とP6でT03を取り合っています。
この時、単純にT03はP6の方が近いのでP6に割り当てると、P1があぶれることになります。

そこで今度は、あぶれた顧客を終点、残った（未割り当ての）タクシーを起点として、Step1を実行します。

これをあぶれた顧客がいなくなるまで繰り返します。
図３ではあぶれた顧客はP1、残った（未割り当ての）タクシーはT02、T05、T08です。
この時、T03は既にP6に割り当て済みと考えます。

● Step2b　一括経路探索を未決定顧客数回実行

単純な方法であるStep2aを代替すべく、他の方法として以下が考えられます。
この方法によれば、解の最適性はより高まると思われます。

タクシーの重複割り当てが発生した顧客のP1とP6を起点、残った（未割り当ての）タクシーT02、T05、T08、及びT03（T03も未割り当てと考える）を終点として、一括経路探索を顧客の数分（この場合は２回）実行します（図４及び図５参照、「終点の複数化」の利用）。

すると、未決定顧客と未割り当てタクシーの掛け合わせのコスト（距離／時間）マトリクスが求められます。
このコストマトリクスに基づいて、最適な組み合わせを求めることが出来ます（図６及び図７参照）。

上記の計算では、「終点の複数化」が利用されているため、結果的に複数タクシー（起点）から一人の顧客（終点）ではなく、一人の顧客（起点）から複数タクシー（終点）への経路探索、つまり逆向きの経路探索が行われております。

よって、求められた最適経路（の時間／距離）の精度に疑問が生じますが、以下の理由より精度は余り問題にはならないと考えております。

限定的な利用	最適経路探索結果の時間／距離は、あくまで「重複割り当て」と言う限定的なケースにおいてのみ利用されるに過ぎない。 また、その値は単独で利用されることはなく、合計を求めて最小値を選択するという「組み合わせ最適」の中で利用されている。 従って、個々の数値の影響は相対的には低く、概算値でも構わないと考えられる。 ここでの「組み合わせ最適」は寧ろ、高速処理の方が重要目標であるとう考えもある。
道路ネットワークへの 逆方向設定	渋滞や速度規制、一方通行などの方向依存情報について、その向きが真逆となるような道路ネットワークデータを作成しておくことで、逆方向の探索でも正しい結果に近付くと考えられる。

お問い合わせ

最適ルート探索エンジンeREXへのお問い合わせは、メールまたは電話でご連絡頂ければ幸いです。

E-Mail:support@ncm-git.co.jp
TEL:03-6902-9701