(57)【要約】【課題】タスクが動的に発生する場合であっても追加タスクを効率的及び低廉に割当てる。【解決手段】タスク割当て装置１は、地理的位置におけるタスク出現確率に基づき取得されたタスクの集合と未割当てのタスクの集合との和集合から未割当てのタスクを選択し、タスクが未割当てのワーカの集合においてタスクを行う際の最小必要時間が最小となるワーカに対してタスクを割当てた際の最大寄り道時間が算出されたワーカの集合から前記タスク出現確率に基づき取得されたタスクに対応したワーカの集合を削除して、ワーカに対してタスクが暫定的に割当てられたワーカの集合を得る。そして、この暫定的に割当てられたワーカの集合のワーカが新たに追加されたタスクの集合のタスクを行う際の最小必要時間が最小となるワーカに対してタスクを割当てた場合の最大寄り道時間が算出されたワーカの集合を当該暫定的に割当てられたワーカの集合に追加する。【選択図】図１
2017010136.tif 000002
【特許請求の範囲】
【請求項１】
ワーカにタスクを割当てるタスク割当て装置であって、
地理的位置におけるタスク出現確率に基づき取得されたタスクの集合と未割当てのタスクの集合との和集合から地理的位置とその位置での最大寄り道時間とが対応付けられたワーカの集合のワーカに対して未割当てのタスクを選択し、
前記ワーカの集合において前記選択されたタスクを行う際の最小必要時間が最小となるワーカに対してタスクを割当てた際の最大寄り道時間を算出し、
この最大寄り道時間が算出されたワーカの集合から前記タスク出現確率に基づき取得されたタスクに対応したワーカの集合を削除することにより、
ワーカに対してタスクが暫定的に割当てられたワーカの集合を得る割当て最適化計算部と、
前記暫定的に割当てられたワーカの集合のワーカが新たに追加されたタスクの集合のタスクを行う際の最小必要時間が最小となるワーカに対してタスクを割当てた場合の最大寄り道時間を算出し、
この最大寄り道時間が算出されたワーカの集合を前記暫定的に割当てられたワーカの集合に追加することにより、
当該暫定的に割当てられたワーカの集合を更新する追加割当て部と
を備えたことを特徴とするタスク割当て装置。
【請求項２】
ワーカにタスクを割当てるタスク割当て装置であって、
地理的位置におけるタスク出現確率に基づき取得されたタスクの集合と未割当てのタスクの集合との和集合から地理的位置とその位置での最大寄り道時間とが対応付けられたワーカの集合のワーカに対して未割当てのタスクを選択し、
前記ワーカの集合において前記選択されたタスクを行う際の最小必要時間が最小となるワーカに対してタスクを割当てた際の最大寄り道時間を算出し、
この最大寄り道時間が算出されたワーカの集合において前記タスク出現確率に基づき取得されたタスクに対してフラグを付与することにより、
ワーカに対してタスクが暫定的に割当てられたワーカの集合を得る割当て最適化計算部と、
前記新たに追加されたタスクのレコードと前記フラグが付与されたタスクのレコードとが一致しない場合に、前記暫定的に割当てられたワーカの集合から前記フラグが付与されたタスクに対応したワーカの集合を削除し、このフラグが付与されたタスクに対応したワーカの集合が削除されたワーカの集合のワーカが当該新たに追加されたタスクの集合のタスクを行う際の最小必要時間が最小となるワーカに対してタスクを割当てた場合の最大寄り道時間を算出し、この最大寄り道時間を算出したワーカの集合を前記暫定的に割当てられたワーカの集合に追加することにより、当該暫定的に割当てられたワーカの集合を更新する一方で、
前記新たに追加されたタスクのレコードと前記フラグが付与されたタスクのレコードとが一致する場合に、前記暫定的に割当てられたワーカの集合のワーカが当該新たに追加されたタスクの集合のタスクを行う際の最小必要時間が最小となるワーカに対してタスクを割当てた場合の最大寄り道時間を算出し、この最大寄り道時間を算出したワーカの集合を前記暫定的に割当てられたワーカの集合に追加することにより、当該暫定的に割当てられたワーカの集合を更新する追加割当て部と
を備えたことを特徴とするタスク割当て装置。
【請求項３】
コンピュータがワーカへのタスクの割当てを行うタスク割当て方法であって、
地理的位置におけるタスク出現確率に基づき取得されたタスクの集合と未割当てのタスクの集合との和集合から地理的位置とその位置での最大寄り道時間とが対応付けられたワーカの集合のワーカに対して未割当てのタスクを選択し、
前記ワーカの集合において前記選択されたタスクを行う際の最小必要時間が最小となるワーカに対してタスクを割当てた際の最大寄り道時間を算出し、
この最大寄り道時間が算出されたワーカの集合から前記タスク出現確率に基づき取得されたタスクに対応したワーカの集合を削除することにより、
ワーカに対してタスクが暫定的に割当てられたワーカの集合を得る割当て最適化計算ステップと、
前記暫定的に割当てられたワーカの集合のワーカが新たに追加されたタスクの集合のタスクを行う際の最小必要時間が最小となるワーカに対してタスクを割当てた場合の最大寄り道時間を算出し、
この最大寄り道時間が算出されたワーカの集合を前記暫定的に割当てられたワーカの集合に追加することにより、
当該暫定的に割当てられたワーカの集合を更新する追加割当てステップと
を有することを特徴とするタスク割当て方法。
【請求項４】
コンピュータがワーカへのタスクの割当てを行うタスク割当て方法であって、
地理的位置におけるタスク出現確率に基づき取得されたタスクの集合と未割当てのタスクの集合との和集合から地理的位置とその位置での最大寄り道時間とが対応付けられたワーカの集合のワーカに対して未割当てのタスクを選択し、
前記ワーカの集合において前記選択されたタスクを行う際の最小必要時間が最小となるワーカに対してタスクを割当てた際の最大寄り道時間を算出し、
この最大寄り道時間が算出されたワーカの集合において前記タスク出現確率に基づき取得されたタスクに対してフラグを付与することにより、
ワーカに対してタスクが暫定的に割当てられたワーカの集合を得る割当て最適化計算ステップと、
前記新たに追加されたタスクのレコードと前記フラグが付与されたタスクのレコードとが一致しない場合に、前記暫定的に割当てられたワーカの集合から前記フラグが付与されたタスクに対応したワーカの集合を削除し、このフラグが付与されたタスクに対応したワーカの集合が削除されたワーカの集合のワーカが当該新たに追加されたタスクの集合のタスクを行う際の最小必要時間が最小となるワーカに対してタスクを割当てた場合の最大寄り道時間を算出し、この最大寄り道時間を算出したワーカの集合を前記暫定的に割当てられたワーカの集合に追加することにより、当該暫定的に割当てられたワーカの集合を更新する一方で、
前記新たに追加されたタスクのレコードと前記フラグが付与されたタスクのレコードとが一致する場合に、前記暫定的に割当てられたワーカの集合のワーカが当該新たに追加されたタスクの集合のタスクを行う際の最小必要時間が最小となるワーカに対してタスクを割当てた場合の最大寄り道時間を算出し、この最大寄り道時間を算出したワーカの集合を前記暫定的に割当てられたワーカの集合に追加することにより、当該暫定的に割当てられたワーカの集合を更新する追加割当てステップと
を有することを特徴とするタスク割当て方法。
【請求項５】
コンピュータを請求項１または２に記載のタスク割当て装置を構成する各手段として機能させるタスク割当てプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は複数の仕事（以下、タスク）を複数の者（以下、ワーカ）に効率的に割当てる装置とその方法の技術分野に関する。
【背景技術】
【０００２】
複数のタスクを複数のワーカに割り振る際、１人あたりのタスク数の上下限や、１タスクあたりのワーカ数の上下限などの制約条件を満たしながらワーカ対タスクの割当て数を最大にする最適化計算を行うことで、効率的な割当てを実現する取組みが行われている。さらに、あるワーカｉがあるタスクｊを受け持つときにコストＣijがかかるとき、総コストが最小となる最適化計算を行うことで効率的な割当てを実現する取組みが行われている。これらのワーカ対タスクの最適な割当て方法を見つける問題を「割当て問題」という。
【０００３】
本発明の技術分野では、クラウドソーシングサービスにおけるワーカ対タスクの割当て問題を解くことを目的とする（クラウドソーシングとは、不特定多数のワーカにタスクを委託する枠組みのことであり、既に商用サービスとして成立しているものもある）。その中でも特に以下の２つの条件を満たす状況を考える。
【０００４】
１つめはタスクに時空間条件が付与されており、ワーカが指定された場所に物理的に移動しなければタスクを完了することができない場合である。２つめはワーカの将来行動の移動系列（時刻と緯度経度の組）が既知である場合である。ワーカの移動系列はGPSセンサなどの測位技術を用いることで記録でき、またそのログを利用して日常生活の移動系列を予測することは可能である（非特許文献１）。
【０００５】
以上のような場合、従来技術ではワーカの日常行動のための移動にタスクのための移動を追加することによって，タスク割当てを行っていた（非特許文献２，非特許文献３）。非特許文献３の手法を具体的に説明する。この手法はタスクノード集合Ｎt，ワーカ集合Ｍ，全ノード間の移動時間Ｃij，ワーカの移動系列ノード集合Ｒm，ワーカの最大寄り道時間集合Ｔmを入力として、ワーカの通常移動時間から最大寄り道時間の分だけ余分に移動ができるという制約条件を設け、その中で割当てるタスクの数を最大化する最適化計算を行っている。この研究のタスク割当て例を図７に示す。ワーカの移動系列（白丸と実線矢印）の途中にタスク（黒四角）への移動を挿入することによってタスクを割当てた結果の移動系列（点線矢印）を出力する。具体的な割当て手法としては、整数計画問題に定式化して厳密解を求める手法や、近似アルゴリズムによって近似解を求める手法が提案されている（非特許文献３）。しかし、この技術は、タスク割当て前に全タスクが分かっている場合を想定しており、タスクが動的に発生する場合、追加分のタスクを再割当てし直す必要がある。
【０００６】
一方、配送計画問題において、タスクが動的に発生する場合の割当てアルゴリズムを研究している従来技術も存在する（非特許文献４）。これは、複数の運搬車がデポと呼ばれる特定の地点を出発し、複数の顧客を経由しながらもとのデポに戻るまでのルートを求めるものである。この従来技術では、顧客が動的に発生する場合、顧客の出現確率をランダムサンプリングしてから最適化計算に用いる技術が提案されている。しかしながら、この技術は運搬車のルートを自由に決められる場合にのみ対応しているため、移動系列の順番を守るべき場合には対応していない。本技術は、ワーカの日常生活の移動系列の順番を守りながら、タスクを割当てることを可能にするものである。
【先行技術文献】
【非特許文献】
【０００７】
【非特許文献１】Monreale, A., Pinelli, F., Trasarti, R., and Giannotti, F. (2009, June). Wherenext: a location predictor on trajectory pattern mining. In Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining (pp. 637-646). ACM.
【非特許文献２】羽田野真由美，中辻真，戸田浩之，小池義昌，（２０１５），「クラウドソーシングの時空間拡張におけるワーカの時間制約を考慮したタスク割当て手法」，第７回データ工学と情報マネジメントに関するフォーラム，DEIM Forum 2015 C6-4
【非特許文献３】Chen, C., Cheng, S. F., Gunawan, A., Misra, A., Dasgupta, K., and Chander, D. (2014). TRACCS: Trajectory-Aware Coordinated Urban Crowd-Sourcing. Second AAAI Conference on Human Computation and Crowdsourcing (HCOMP-14).
【非特許文献４】Pillac, V., Gueret, C., and Medaglia, A. L. (2012). An event-driven optimization framework for dynamic vehicle routing. Decision Support Systems, 54(1), 414-423.
【発明の概要】
【発明が解決しようとする課題】
【０００８】
従来技術を用い、ワーカの移動系列の順番を守りながらタスク割当てを行う際、タスクが後で追加されてもワーカの寄り道時間が十分に残っていないために、追加タスクを割当てられないおそれがある。さらに、実務上、タスクは発生しやすい場所とそうでない場所がありうるが、従来技術ではその差異を区別しないため、追加タスクを効率的に割当てられないおそれがある。
【０００９】
その結果、割当てられなかった追加タスクを次の割当てのタイミングに繰り越す必要があるため、時間的及び金銭的なコストが余計にかかるという課題があった。
【００１０】
本発明は、上記の事情に鑑み、タスクが動的に発生する場合であっても追加タスクを効率的及び低廉に割当てることを課題とする。
【課題を解決するための手段】
【００１１】
そこで、本発明は、タスクの発生確率を用いて発生させた仮のタスクと実際に生じているタスクを合わせてタスクの割当てをおこない、ワーカに通知する割当ては、当該仮のタスクを除いた割当てとする。
【００１２】
本発明の装置としての態様は、ワーカにタスクを割当てるタスク割当て装置であって、地理的位置におけるタスク出現確率に基づき取得されたタスクの集合と未割当てのタスクの集合との和集合から地理的位置とその位置での最大寄り道時間とが対応付けられたワーカの集合のワーカに対して未割当てのタスクを選択し、前記ワーカの集合において前記選択されたタスクを行う際の最小必要時間が最小となるワーカに対してタスクを割当てた際の最大寄り道時間を算出し、この最大寄り道時間が算出されたワーカの集合から前記タスク出現確率に基づき取得されたタスクに対応したワーカの集合を削除することにより、ワーカに対してタスクが暫定的に割当てられたワーカの集合を得る割当て最適化計算部と、前記暫定的に割当てられたワーカの集合のワーカが新たに追加されたタスクの集合のタスクを行う際の最小必要時間が最小となるワーカに対してタスクを割当てた場合の最大寄り道時間を算出し、この最大寄り道時間が算出されたワーカの集合を前記暫定的に割当てられたワーカの集合に追加することにより、当該暫定的に割当てられたワーカの集合を更新する追加割当て部を備える。
【００１３】
本発明の装置としての他の態様は、ワーカにタスクを割当てるタスク割当て装置であって、地理的位置におけるタスク出現確率に基づき取得されたタスクの集合と未割当てのタスクの集合との和集合から地理的位置とその位置での最大寄り道時間とが対応付けられたワーカの集合のワーカに対して未割当てのタスクを選択し、前記ワーカの集合において前記選択されたタスクを行う際の最小必要時間が最小となるワーカに対してタスクを割当てた際の最大寄り道時間を算出し、この最大寄り道時間が算出されたワーカの集合において前記タスク出現確率に基づき取得されたタスクに対してフラグを付与することにより、ワーカに対してタスクが暫定的に割当てられたワーカの集合を得る割当て最適化計算部と、前記新たに追加されたタスクのレコードと前記フラグが付与されたタスクのレコードとが一致しない場合に、前記暫定的に割当てられたワーカの集合から前記フラグが付与されたタスクに対応したワーカの集合を削除し、このフラグが付与されたタスクに対応したワーカの集合が削除されたワーカの集合のワーカが当該新たに追加されたタスクの集合のタスクを行う際の最小必要時間が最小となるワーカに対してタスクを割当てた場合の最大寄り道時間を算出し、この最大寄り道時間を算出したワーカの集合を前記暫定的に割当てられたワーカの集合に追加することにより、当該暫定的に割当てられたワーカの集合を更新する一方で、前記新たに追加されたタスクのレコードと前記フラグが付与されたタスクのレコードとが一致する場合に、前記暫定的に割当てられたワーカの集合のワーカが当該新たに追加されたタスクの集合のタスクを行う際の最小必要時間が最小となるワーカに対してタスクを割当てた場合の最大寄り道時間を算出し、この最大寄り道時間を算出したワーカの集合を前記暫定的に割当てられたワーカの集合に追加することにより、当該暫定的に割当てられたワーカの集合を更新する追加割当て部を備える。
【００１４】
本発明の方法としての態様は、コンピュータがワーカへのタスクの割当てを行うタスク割当て方法であって、地理的位置におけるタスク出現確率に基づき取得されたタスクの集合と未割当てのタスクの集合との和集合から地理的位置とその位置での最大寄り道時間とが対応付けられたワーカの集合のワーカに対して未割当てのタスクを選択し、前記ワーカの集合において前記選択されたタスクを行う際の最小必要時間が最小となるワーカに対してタスクを割当てた際の最大寄り道時間を算出し、この最大寄り道時間が算出されたワーカの集合から前記タスク出現確率に基づき取得されたタスクに対応したワーカの集合を削除することにより、ワーカに対してタスクが暫定的に割当てられたワーカの集合を得る割当て最適化計算ステップと、前記暫定的に割当てられたワーカの集合のワーカが新たに追加されたタスクの集合のタスクを行う際の最小必要時間が最小となるワーカに対してタスクを割当てた場合の最大寄り道時間を算出し、この最大寄り道時間が算出されたワーカの集合を前記暫定的に割当てられたワーカの集合に追加することにより、当該暫定的に割当てられたワーカの集合を更新する追加割当てステップを有する。
【００１５】
本発明の方法としての他の態様は、コンピュータがワーカへのタスクの割当てを行うタスク割当て方法であって、地理的位置におけるタスク出現確率に基づき取得されたタスクの集合と未割当てのタスクの集合との和集合から地理的位置とその位置での最大寄り道時間とが対応付けられたワーカの集合のワーカに対して未割当てのタスクを選択し、前記ワーカの集合において前記選択されたタスクを行う際の最小必要時間が最小となるワーカに対してタスクを割当てた際の最大寄り道時間を算出し、この最大寄り道時間が算出されたワーカの集合において前記タスク出現確率に基づき取得されたタスクに対してフラグを付与することにより、ワーカに対してタスクが暫定的に割当てられたワーカの集合を得る割当て最適化計算ステップと、前記新たに追加されたタスクのレコードと前記フラグが付与されたタスクのレコードとが一致しない場合に、前記暫定的に割当てられたワーカの集合から前記フラグが付与されたタスクに対応したワーカの集合を削除し、このフラグが付与されたタスクに対応したワーカの集合が削除されたワーカの集合のワーカが当該新たに追加されたタスクの集合のタスクを行う際の最小必要時間が最小となるワーカに対してタスクを割当てた場合の最大寄り道時間を算出し、この最大寄り道時間を算出したワーカの集合を前記暫定的に割当てられたワーカの集合に追加することにより、当該暫定的に割当てられたワーカの集合を更新する一方で、前記新たに追加されたタスクのレコードと前記フラグが付与されたタスクのレコードとが一致する場合に、前記暫定的に割当てられたワーカの集合のワーカが当該新たに追加されたタスクの集合のタスクを行う際の最小必要時間が最小となるワーカに対してタスクを割当てた場合の最大寄り道時間を算出し、この最大寄り道時間を算出したワーカの集合を前記暫定的に割当てられたワーカの集合に追加することにより、当該暫定的に割当てられたワーカの集合を更新する追加割当てステップを有する。
【００１６】
尚、本発明は上記装置の各手段としてコンピュータを機能させるプログラム若しくは上記方法の各ステップをコンピュータに実行させるプログラムの態様とすることもできる。
【発明の効果】
【００１７】
以上の発明によれば、タスクが動的に発生する場合であっても追加タスクを効率的及び低廉に割当てることができる。
【図面の簡単な説明】
【００１８】
【図１】本発明の実施形態におけるタスク割当て装置の概略構成図。
【図２】同実施形態におけるタスクサンプリングのフローチャート。
【図３】同実施形態における割当て最適化計算のフローチャート。
【図４】同実施形態においてサンプリングタスクフラグを付与する場合の割当て最適化計算のフローチャート。
【図５】同実施形態における追加割当てのフローチャート。
【図６】（ａ）タスクを行う際の移動系列（ワーカがタスクを行った後に元の場所に戻る場合）の一例、（ｂ）タスクを行う際の移動系列（ワーカがタスクを行った後に元の場所に戻らない場合）の一例。
【図７】従来のタスク割当ての一例。
【発明を実施するための形態】
【００１９】
以下、図面を参照しながら本発明の実施の形態について説明するが本発明はこの実施形態に限定されるものではない。
【００２０】
≪概要≫
図１に示された本実施形態のタスク割当て装置１は、タスク発生確率を利用してランダムサンプリングした結果をタスク割当てに利用することにより、将来追加が期待されるタスクの情報を含めた暫定的なタスク割当てを行う。また、前記ランダムサンプリングした結果と既に発生しているタスクを合わせて割当て、その結果からサンプリングされたタスクにフラグを付与することにより、ワーカの寄り道時間を残しながら暫定的なタスク割当てを行う。そして、暫定的なタスク割当ての際に予め最小必要時間を計算することにより、追加タスクが発生した際の最小必要時間の計算コストを削減する。
【００２１】
≪本実施形態の装置構成例≫
図１に例示されたタスク割当て装置１は、タスクサンプリング部０２０、サンプリングタスクＤＢ（データベース）０３０，割当て最適化計算部０６０、暫定割当て結果ＤＢ０７０Ａまたは０７０Ｂ、追加割当て部０９０を備える。
【００２２】
前記機能部０２０〜０９０はコンピュータのハードウェアリソースによって実現される。すなわち、タスク割当て装置１は、少なくとも演算装置（ＣＰＵ）、記憶装置（メモリ、ハードディスク装置等）、通信インタフェース等のコンピュータに係るハードウェアリソースを備える。そして、これらのハードウェアリソースがソフトウェアリソース（ＯＳ、アプリケーション等）と協働することにより機能部０２０〜０９０が実装される。なお、タスク割当て装置１は、単一のコンピュータ若しくは複数のコンピュータから構成してもよいものとする。
【００２３】
以下、前記各機能部の詳細を説明する。
【００２４】
≪タスクサンプリング部０２０≫
タスクサンプリング部０２０は、タスク出現確率ＤＢ０１０を入力として、サンプリングタスクＤＢ０３０を出力とする。
【００２５】
タスク出現確率ＤＢ０１０のデータ構造の例を表１に示す。タスク出現確率ＤＢ０１０には、タスクの緯度経度（地理的位置）及びこの位置において将来出現する確率情報が格納されている。タスクの出現確率情報は過去の統計情報から計算するなどの手段によって事前に分かっているものとする。尚、外部からレコードを指定するために、各レコードにはタスクＩＤが付与されている。
【００２６】
サンプリングタスクＤＢ０３０のデータ構造の例を表２に示す。サンプリングタスクＤＢ０３０は、タスク出現確率ＤＢ０１０から事前に決められた数だけランダムサンプリングされたタスクの緯度経度情報が格納されている。
【００２７】
【表１】
2017010136.tif 000003
【００２８】
【表２】
2017010136.tif 000004
【００２９】
タスクサンプリング部０２０は、タスク出現確率を用いて将来出現するタスクをランダムサンプリングする機能部であり、図２のステップＳ１−１〜Ｓ１−４を実行する。
【００３０】
［Ｓ１−１］集合Ｓを用意し、空集合とする。
【００３１】
［Ｓ１−２］タスク出現確率ＤＢ０１０からレコード集合を検索し、集合Ｐとする。
【００３２】
［Ｓ１−３］集合Ｐから出現確率の要素を利用してランダムサンプリングを行い、取得されたレコード集合をＳとする。ここで、ランダムサンプリングで取り出すデータサイズｓｉｚｅの設定方法として、例えば、過去の追加タスクの出現数Ｎをそのまま利用することができる。他にも、追加割当てよりも暫定割当て結果を重要視する場合は、ｓｉｚｅ＝０．７Ｎなど重みを付けて調整することができる。
【００３３】
［Ｓ１−４］集合Ｓの情報をサンプリングタスクＤＢ０３０に出力し、処理を終了する。
【００３４】
≪割当て最適化計算部０６０≫
割当て最適化計算部０６０は、サンプリングタスクＤＢ０３０とタスクＤＢ０４０，ワーカＤＢ０５０とを入力として、暫定割当て結果ＤＢ０７０を出力とする。
【００３５】
タスクＤＢ０４０のデータ構造の例を表３に示す。タスクＤＢ０４０には、既に出現している未割当てタスクの緯度経度情報が格納されている。尚、外部からレコードを指定するために、各レコードにはタスクＩＤが付与されている。
【００３６】
ワーカＤＢ０５０のデータ構造の例を表４に示す。ワーカＤＢ０５０には、一定時間分のワーカの日常的な移動系列情報が格納されており、具体的には時刻，緯度経度，最大寄り道時間の情報が格納されている。表４の例ではワーカの１日分の情報を格納している。ワーカの日常的な移動軌跡は、ＧＰＳログなどから日常生活の移動を抽出する既存研究によって抽出することができる（非特許文献１）。また、最大寄り道時間とは、ワーカがタスクのために余分に移動してもよいと考える時間のことを示している。例えば、表４のワーカＩＤ１の最大寄り道時間は６０分であり、タスク遂行のために１日６０分までであれば余分な移動を許容することを示している。尚、外部からレコードを指定するために、各レコードにはワーカＩＤが付与されている。
【００３７】
暫定割当て結果ＤＢ０７０のデータ構造の例を表５，表６に示す。本態様では、暫定割当て結果ＤＢ０７０の実現方法として、最小必要時間の計算方法に応じて２種類のものを用意する。表５に示した一つ目の暫定割当て結果ＤＢ０７０Ａには、暫定的なタスク割当て結果としてのワーカの移動系列情報（ワーカＩＤ、時刻、緯度経度、最大寄り道時間）が格納されている。ここで、最大寄り道時間のレコードは割当てによって更新された値が格納されている。また、割当てられたタスクのＩＤ情報を示すレコードが追加されている。表６に示した二つ目の暫定割当て結果ＤＢ０７０Ｂには、ＤＢ０７０Ａにサンプリングタスクフラグというレコードが追加されている。
【００３８】
【表３】
2017010136.tif 000005
【００３９】
【表４】
2017010136.tif 000006
【００４０】
【表５】
2017010136.tif 000007
【００４１】
【表６】
2017010136.tif 000008
【００４２】
割当て最適化計算部０６０は、サンプリングタスクと既に出現したタスクの和集合を、ワーカに出来るだけ多く割当てた結果を出力するものであり、図３のステップＳ２−１〜Ｓ２−１１Ａまたは図４のステップＳ２−１〜Ｓ２−１１Ｂを実行する。なお、本態様に適用された最適化手法（ステップＳ２−４〜Ｓ２−１０）は、計算コストが少ない近似アルゴリズムであるため必ずしも割当てタスク数を最大化できるとは限らない。割当てタスク数を厳密に最大化したい場合はステップＳ２−４〜Ｓ２−１０の処理を非特許文献３に記載の整数計画問題に定式化する手法と代えることもできる。
【００４３】
［Ｓ２−１］集合Ａを用意し、空集合とする。
【００４４】
［Ｓ２−２］サンプリングタスクＤＢ０３０とタスクＤＢ０４０，ワーカＤＢ０５０とからレコード集合を検索し、それぞれ集合Ｓ，Ｔ，Ｗとする。
【００４５】
［Ｓ２−３］集合ＳとＴの和集合Ｓ＋Ｔから未割当てのタスクを選択し、ｔとする。
【００４６】
［Ｓ２−４］集合Ｒを用意し、空集合とする。
【００４７】
［Ｓ２−５］集合Ｗから未選択のワーカを選択し、ｗとする。
【００４８】
［Ｓ２−６］ｗの最大寄り道時間に余裕がある場合、Ｓ２−７に進み、そうでない場合はＳ２−５に戻る。
【００４９】
［Ｓ２−７］ワーカｗがタスクｔを行う際の最小必要時間ｔｉｍｅ（ｗ，ｔ）を計算し、 ワーカと最小必要時間，移動系列のインデックスの三組み（ｗ，ｔｉｍｅ（ｗ，ｔ），ｋ’）を集合Ｒに追加する。
【００５０】
ここで、移動系列のインデックスの計算方法を示す。まず、タスクｔの緯度経度を（ｌａｔ’，ｌｏｎ’）、ワーカの移動系列のｋ番目の緯度経度を（ｌａｔk，ｌｏｎk）とする。また、２点（ｌａｔi，ｌｏｎi），（ｌａｔj，ｌｏｎj）間の距離をｄｉｓｔ（ｌａｔi，ｌｏｎi，ｌａｔj，ｌｏｎj）とする。ワーカの移動系列の中でタスクｔに一番近い要素ｋ’は以下の式により計算できる。
【００５１】
ｋ’＝ａｒｇｍｉｎk ｄｉｓｔ（ｌａｔk，ｌｏｎk，ｌａｔ’，ｌｏｎ’）
なお、２点間の距離の計算はユークリッド距離や道路ネットワーク距離などが利用できる。次に、ｔｉｍｅ（ｗ，ｔ）の計算方法の一例を示す。ワーカの移動速度をｖとし、ワーカｗがタスクｔを行った後に元の場所に戻るような移動を考える（図６（ａ））その際の最小必要時間は以下の式により計算できる。
【００５２】
【数１】
2017010136.tif 000009
【００５３】
また、ワーカｗがタスクｔを行った後に元の位置に戻らず、次に行く予定であった移動系列に移動をする場合を考える（図６（ｂ））。この際の最小必要時間は以下の式により計算できる。
【００５４】
【数２】
2017010136.tif 000010
【００５５】
［Ｓ２−８］ｗに未処理の要素がある場合、Ｓ２−５に戻り、そうでない場合、Ｓ２−９に進む。
【００５６】
［Ｓ２−９］集合Ｒより最小必要時間が最小なワーカを選択し、そのワーカにタスクｔを割当てた結果を集合Ａに追加する。
【００５７】
ここで、集合Ａは、ワーカＩＤ，時刻，ワーカ緯度，ワーカ経度，タスクＩＤ，最大寄り道時間の要素を持ち，タスクのための移動をワーカＤＢ０５０に追加した結果が格納される。ここで、最小必要時間が最小なワーカをｗm、そのときの最小必要時間をｔｉｍｅm、元の移動系列の最大寄り道時間をｔｉｍｅmaxとすると、ワーカｗmをタスクｔに割当てた結果は以下のように計算できる。まず、ワーカｗmがタスクを行う際の移動系列は，ワーカのもとの移動系列のｋ’＋１番目の要素に挿入される。また、ｋ’＋１以降の時刻はそれぞれｔｉｍｅmだけ後ろにずれる。さらに、最大寄り道時間はｔｉｍｅmax−ｔｉｍｅmとなる。
【００５８】
［Ｓ２−１０］ｔに未処理の要素がある場合、Ｓ２−３に戻り、そうでない場合、Ｓ２−１１に進む。
【００５９】
［Ｓ２−１１］本態様では、暫定割当て結果ＤＢ０７０の実現方法として、最小必要時間の計算方法に応じて以下の図３のＳ２−１１Ａと図４のＳ２−１１Ｂのいずれかのステップを実行する。
【００６０】
（Ｓ２−１１Ａ）集合Ａから集合Ｓに含まれるサンプリングタスクのレコードを削除した結果を暫定割当て結果ＤＢ０７０Ａに出力し、処理を終了する。この処理は、割当てたタスクの中に含まれる未出現のタスクｔ∈Ｓを削除するためのものである。その削除方法は、Ｓ２−９にてタスクを追加した方法の逆の処理を行えばよい。
【００６１】
（Ｓ２−１１Ｂ）集合Ａから集合Ｓに含まれるサンプリングタスクのレコードのみフラグを付与した結果を暫定割当て結果ＤＢ０７０Ｂに出力し、処理を終了する。この処理は、割当てたタスクの中で出現済みタスクと未出現のタスクｔ∈Ｓを区別するためのものである。
【００６２】
≪追加割当て部０９０≫
追加割当て部０９０は、暫定割当て結果ＤＢ０７０と追加タスクＤＢ０８０を入力として追加割当て結果ＤＢ１００を出力とする。
【００６３】
追加タスクＤＢ０８０のデータ構造の例を表７に示す。追加タスクＤＢ０８０は、追加で発生したタスクの情報が格納されており、そのデータ形式はタスクＤＢ０４０と同様にタスクＩＤ，タスクの緯度経度情報が格納されている。
【００６４】
追加割当て結果ＤＢ１００のデータ構造の例を表８に示す。追加割当て結果ＤＢ１００は、暫定割当て結果ＤＢ０７０に追加タスクを割当てた結果が格納されている。そのため、データ構造も暫定割当て結果ＤＢ０７０と同様に、ワーカＩＤ，時刻，ワーカ緯度経度情報，タスクＩＤ，最大寄り道時間の情報が格納されている。
【００６５】
【表７】
2017010136.tif 000011
【００６６】
【表８】
2017010136.tif 000012
【００６７】
追加割当て部０９０は、追加で発生したタスクをワーカへ割当てるものであり、図５のステップＳ３−１〜Ｓ３−１０を実行する。
【００６８】
［Ｓ３−１］集合Ｂを用意し、空集合とする。
【００６９】
［Ｓ３−２］暫定割当て結果ＤＢ０７０と追加タスクＤＢ０８０よりレコード集合を検索し、それぞれ集合Ａ，Ｃとする。
【００７０】
［Ｓ３−３］集合Ｃより未処理の要素を取り出し、ｃとする。
【００７１】
［Ｓ３−４］集合Ａより未処理のワーカ要素を取り出し、ａとする。
【００７２】
［ＳＳ−５］本態様では、追加割当て結果ＤＢ１００の実現方法として、最小必要時間の計算方法に応じて以下のＳ３−５ＡとＳ３−５Ｂのいずれかのステップを実行する。
【００７３】
（Ｓ３−５Ａ）ａにｃを割当てた際にかかる最小必要時間を計算する。この際、最小必要時間の計算はＳ２−７に記載した方法と同じ方法で計算することができる。
【００７４】
（Ｓ３−５Ｂ）ａにｃを割当てた際にかかる最小必要時間を計算する。この際、最小必要時間の計算方法は以下のように行う。
【００７５】
（１）ｃが暫定割当て結果ＤＢ０７０（例えば０７０Ｂ）のサンプリングタスクフラグが１のレコードと一致しない場合
まず、暫定割当て結果ＤＢ０７０からサンプリングタスクフラグが１のレコードを消去する。この際、最大寄り道時間をＳ２−７に記載した方法の逆計算を行うことで再計算する。次に、ａにｃを割当てた際の最小必要時間は、Ｓ２−７に記載した方法と同じ方法で計算する。
【００７６】
（２）ｃが暫定割当て結果ＤＢ０７０（例えば０７０Ｂ）のサンプリングタスクフラグが１のレコードと一致する場合
最小必要時間は、予め計算した最小必要時間をそのまま利用することができる。Ｓ２−７で予め最小必要時間を計算しておくことで、追加タスクが発生した際の計算コストを減らすことが可能となる。
【００７７】
［Ｓ３−６］ａの最大寄り道時間に余裕がある場合、Ｓ３−４に戻り、そうでない場合はＳ３−７に進む。
【００７８】
［Ｓ３−７］集合Ａにタスクｃを追加した結果を集合Ｂに追加する。集合Ａの最大寄り道時間を更新する。この際、ワーカの移動系列にタスクの移動を追加する方法は、Ｓ２−９と同様の方法で計算することができる。
【００７９】
［Ｓ３−８］ａに未処理の要素がある場合、［Ｓ３−４］に戻り、そうでない場合は［Ｓ３−９］に進む。
【００８０】
［Ｓ３−９］ｃに未処理の要素がある場合、［Ｓ３−３］に戻り、そうでない場合は［Ｓ３−１０］に進む。
【００８１】
［Ｓ３−１０］集合Ｂの情報を追加割当て結果ＤＢ１００に出力し、処理を終了する。
【００８２】
≪本実施形態の効果≫
タスク割当て装置１によれば、タスク発生確率を利用してランダムサンプリングした結果と既に発生しているタスクを合わせて割当て、その結果からサンプリングされたタスクを削除することで、ワーカの寄り道時間を残しながら暫定的なタスクの割当てを行える。その結果、のちにタスクが出現する可能性が高い場所にワーカを誘導することができるため、タスクが追加で発生した場合に効率的に割当てることが可能となる。そして、これにより、従来手法では割当てることが出来なかった追加タスクも割当てることが可能となるため、時間的，金銭的なコストを削減することが可能になる。
【００８３】
≪産業上のメリット≫
また、上記の効果により、タスクが動的に発生する場合であっても、追加タスクを効率的に割当てることが可能になる。追加タスクを割当てられることにより、再割当てが必要なくなるため時間的，金銭的なコストを削減することが可能となる。また、再割当てが必要なくなるため、タスク完了までの納期を削減することにつながり、少しでも早く仕事を終わらせたいと考えているタスク依頼者の満足度向上につながる。この技術は、タスクが動的に発生する場合が多く、その発生確率が事前に分かっているような場合に特に有効である。
【００８４】
≪本発明の他の態様≫
本発明は、タスク割当て装置１を構成する機能部０２０，０３０，０６０，０７０，０９０の一部若しくは全てとしてコンピュータを機能させるプログラムで構成しこれを当該コンピュータに実行させることにより実現できる。または、同装置１が実行するステップＳ１−１〜Ｓ１−４，Ｓ２−１〜Ｓ２−１１，Ｓ３−１〜Ｓ３−１０の一部若しくは全てをコンピュータに実行させるプログラムで構成しこれを当該コンピュータに実行させることにより実現できる。そして、このプログラムをそのコンピュータが読み取り可能な周知の記録媒体（例えば、ハードディスク、フレキシブルディスク、ＣＤ−ＲＯＭ等）に格納して提供できる。または、前記プログラムをインターネットや電子メール等でネットワークを介して提供できる。
【００８５】
尚、本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において種々変更、応用が可能である。
【符号の説明】
【００８６】
１…タスク割当て装置
０２０…タスクサンプリング部
０３０…サンプリングタスクＤＢ
０６０…割当て最適化計算部
０７０Ａ，０７０Ｂ…暫定割当て結果ＤＢ
０９０…追加割当て部
１００…追加割当て結果ＤＢ
【図１】
2017010136.tif 000013
【図２】
2017010136.tif 000014
【図３】
2017010136.tif 000015
【図４】
2017010136.tif 000016
【図５】
2017010136.tif 000017
【図６】
2017010136.tif 000018
【図７】
2017010136.tif 000019