● マルチスタート(タクシー)/シングルゴール(顧客)の経路探索が望まれている。
● 究極的には、複数の顧客からの呼び出しを一気に解決することが望ましい。
● eREXには、複数の起点及び終点についての経路探索を高速化する方法が2種類存在する
複数タクシー(起点)は「曖昧な指示制御点」、複数顧客(終点)は「終点の複数化」として実現します。
タクシーの重複割り当てが含まれない図1のようなパターンであれば、一括経路探索1回でタクシー数×顧客数回の経路検索と同等の結果が得られ、完全に最適なタクシーの割り当てが求められます。
しかし、この方法の問題点は、タクシーの重複割り当てが発生し得る点です。 (図 2参照)
図 2では、図1と比較してP6が追加されたために、T03の重複割り当てが発生しています。
タクシーの重複割り当てが発生した場合は、次のステップに進みます。
図 2ではP1とP6でT03を取り合っています。
この時、単純にT03はP6の方が近いのでP6に割り当てると、P1があぶれることになります。
そこで今度は、あぶれた顧客を終点、残った(未割り当ての)タクシーを起点として、Step1を実行します。
これをあぶれた顧客がいなくなるまで繰り返します。
図3ではあぶれた顧客はP1、残った(未割り当ての)タクシーはT02、T05、T08です。
この時、T03は既にP6に割り当て済みと考えます。
単純な方法であるStep2aを代替すべく、他の方法として以下が考えられます。
この方法によれば、解の最適性はより高まると思われます。
タクシーの重複割り当てが発生した顧客のP1とP6を起点、残った(未割り当ての)タクシーT02、T05、T08、及びT03(T03も未割り当てと考える)を終点として、一括経路探索を顧客の数分(この場合は2回)実行します(図4及び図5参照、「終点の複数化」の利用)。
すると、未決定顧客と未割り当てタクシーの掛け合わせのコスト(距離/時間)マトリクスが求められます。
このコストマトリクスに基づいて、最適な組み合わせを求めることが出来ます(図6及び図7参照)。
上記の計算では、「終点の複数化」が利用されているため、結果的に複数タクシー(起点)から一人の顧客(終点)ではなく、一人の顧客(起点)から複数タクシー(終点)への経路探索、つまり逆向きの経路探索が行われております。
よって、求められた最適経路(の時間/距離)の精度に疑問が生じますが、以下の理由より精度は余り問題にはならないと考えております。
限定的な利用 | 最適経路探索結果の時間/距離は、あくまで「重複割り当て」と言う限定的なケースにおいてのみ利用されるに過ぎない。 また、その値は単独で利用されることはなく、合計を求めて最小値を選択するという「組み合わせ最適」の中で利用されている。 従って、個々の数値の影響は相対的には低く、概算値でも構わないと考えられる。 ここでの「組み合わせ最適」は寧ろ、高速処理の方が重要目標であるとう考えもある。 |
---|---|
道路ネットワークへの 逆方向設定 |
渋滞や速度規制、一方通行などの方向依存情報について、その向きが真逆となるような道路ネットワークデータを作成しておくことで、逆方向の探索でも正しい結果に近付くと考えられる。 |
最適ルート探索エンジンeREXへのお問い合わせは、メールまたは電話でご連絡頂ければ幸いです。
E-Mail:support@ncm-git.co.jp
TEL:03-6902-9701