(57)【要約】【課題】タスクの密度に応じて、ワーカに最適なタスクを割り当てることができる。【解決手段】クラスタリング部３０が、複数のタスクの各々の位置情報に基づいて、複数のタスクを複数のクラスタに分類する。暫定タスク割当部５０が、複数のクラスタの各々について、クラスタに属する全てのタスクを割り当て可能なワーカのうち、必要時間が最小となるワーカに、クラスタに属する全てのタスクを割り当てる。タスク割当部８０が、ワーカに割り当てられていないタスクの各々について、タスクを割り当て可能なワーカのうち、必要時間が最小となるワーカに、タスクを割り当てる。【選択図】図１
2017107385.tif 000002
【特許請求の範囲】
【請求項１】
複数のタスクを、移動する複数のワーカに割り当てるタスク割当装置であって、
前記複数のタスクの各々の位置情報に基づいて、前記複数のタスクを複数のクラスタに分類するクラスタリング部と、
前記複数のワーカの各々について予め求められた前記ワーカが移動する位置の移動系列、及び最大寄り道時間に基づいて、前記複数のクラスタの各々について、前記クラスタに属する全てのタスクを割り当て可能なワーカのうち、前記クラスタに属する全てのタスクを処理するのに必要な必要時間が最小となるワーカに、前記クラスタに属する全てのタスクを割り当てる暫定タスク割当部と、
前記複数のワーカの各々について予め求められた前記ワーカが移動する位置の移動系列、及び最大寄り道時間と、前記クラスタに属する全てのタスクが割り当てられたワーカの前記必要時間とに基づいて、前記ワーカに割り当てられていないタスクの各々について、前記タスクを割り当て可能なワーカのうち、前記タスクを処理するのに必要な必要時間が最小となるワーカに、前記タスクを割り当てるタスク割当部と、
を含むタスク割当装置。
【請求項２】
前記タスク割当部は、特定の人から多く訪問されているエリアである度合いを表すロケーションエントロピーが低いエリアに含まれる位置情報を有するタスクを優先して、前記ワーカに割り当てられていないタスクの各々について、前記タスクを割り当て可能なワーカのうち、前記タスクを処理するのに必要な必要時間が最小となるワーカに、前記タスクを割り当てる請求項１記載のタスク割当装置。
【請求項３】
前記クラスタに属する全てのタスクを処理するのに必要な必要時間は、前記クラスタに属する全てのタスクの各々についての、前記ワーカの移動系列に含まれる位置のうち、前記タスクの位置情報に最も近い位置から計算される、前記タスクの位置との距離が最も短い位置、及び前記タスクの位置の間の移動時間と、前記クラスタに属する全てのタスクを処理するための移動時間との和である請求項１又は２記載のタスク割当装置。
【請求項４】
複数のタスクを、移動する複数のワーカに割り当てるタスク割当装置におけるタスク割当方法であって、
クラスタリング部が、前記複数のタスクの各々の位置情報に基づいて、前記複数のタスクを複数のクラスタに分類するステップと、
暫定タスク割当部が、前記複数のワーカの各々について予め求められた前記ワーカが移動する位置の移動系列、及び最大寄り道時間に基づいて、前記複数のクラスタの各々について、前記クラスタに属する全てのタスクを割り当て可能なワーカのうち、前記クラスタに属する全てのタスクを処理するのに必要な必要時間が最小となるワーカに、前記クラスタに属する全てのタスクを割り当てるステップと、
タスク割当部が、前記複数のワーカの各々について予め求められた前記ワーカが移動する位置の移動系列、及び最大寄り道時間と、前記クラスタに属する全てのタスクが割り当てられたワーカの前記必要時間とに基づいて、前記ワーカに割り当てられていないタスクの各々について、前記タスクを割り当て可能なワーカのうち、前記タスクを処理するのに必要な必要時間が最小となるワーカに、前記タスクを割り当てるステップと、
を含むタスク割当方法。
【請求項５】
前記タスク割当部が割り当てるステップは、特定の人から多く訪問されているエリアである度合いを表すロケーションエントロピーが低いエリアに含まれる位置情報を有するタスクを優先して、前記ワーカに割り当てられていないタスクの各々について、前記タスクを割り当て可能なワーカのうち、前記タスクを処理するのに必要な必要時間が最小となるワーカに、前記タスクを割り当てる請求項４記載のタスク割当方法。
【請求項６】
前記クラスタに属する全てのタスクを処理するのに必要な必要時間は、前記クラスタに属する全てのタスクの各々についての、前記ワーカの移動系列に含まれる位置のうち、前記タスクの位置情報に最も近い位置から計算される、前記タスクの位置との距離が最も短い位置、及び前記タスクの位置の間の移動時間と、前記クラスタに属する全てのタスクを処理するための移動時間との和である請求項４又は５記載のタスク割当方法。
【請求項７】
コンピュータを、請求項１〜請求項３のいずれか１項に記載のタスク割当装置の各部として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、タスク割当装置、方法、及びプログラムに係り、特に、ワーカに最適なタスクを割り当てるためのタスク割当装置、方法、及びプログラムに関する。
【背景技術】
【０００２】
複数の仕事（以下、タスクという）を複数の人（以下、ワーカという）に割り振る際、１人あたりのタスク数の上下限や、1タスクあたりのワーカ数の上下限などの制約条件を満たしながらワーカ対タスクの割り当て数を最大にする最適化計算を行うことで、効率的な割り当てを実現する取組みが行われている。さらに、あるワーカｉがあるタスクｊを受け持つときにコストｃｉｊがかかるとき、総コストが最小となる最適化計算を行うことで効率的な割り当てを実現する取組み行われている。これらのワーカ対タスクの最適な割り当て方法を見つける問題を「割り当て問題」という。
【０００３】
本技術では、クラウドソーシングサービスにおけるワーカ対タスクの割り当て問題を解くことを目的とする。クラウドソーシングとは、不特定多数のワーカにタスクを委託する枠組みのことであり、すでに商用サービス（例えば、ランサーズ（Ｒ）、URL:http://www.lancers.jp)として成立しているものもある。その中でも特に、以下の２つの条件を満たす状況を考える。１つめはタスクに時空間条件が付与されており、ワーカが指定された場所に物理的に移動しなければタスクを完了することができない場合である。２つめはワーカの将来行動の移動系列（時刻と緯度経度の組）が既知である場合である。ワーカの移動系列はＧＰＳセンサなどの測位技術を用いることで記録でき、またそのログを利用して日常生活の移動系列を予測することは可能である（非特許文献１参照）。
【０００４】
以上のような場合、従来技術ではワーカの日常行動のための移動にタスクのための移動を追加することによって、タスク割り当てを行っていた（非特許文献２、及び非特許文献３参照）。非特許文献３の手法を具体的に説明する。この手法はタスクノード集合Ｎｔ、ワーカ集合Ｍ、全ノード間の移動時間ｃｉｊ、ワーカの移動系列ノード集合Ｒｍ、ワーカの最大寄り道時間集合Ｔｍを入力として、ワーカの通常移動時間から最大寄り道時間の分だけ余分に移動ができるという制約条件を設け、その中で割り当てるタスクの数を最大化する最適化計算を行っている。この研究のタスク割り当て例を図８に示す。ワーカの移動系列（白丸と実線矢印）の途中にタスク（黒四角）への移動を挿入することによってタスクを割り当てた結果の移動系列（点線矢印）を出力する。具体的なタスク割り当て手法としては、整数計画問題に定式化して厳密解を求める手法があるものの、この手法は計算コストが高いため、本発明では近似アルゴリズムによって近似解を求める手法に焦点をしぼる。既存の近似アルゴリズムには、貪欲法によって逐次的に最小コストのワーカにタスクを割り当てるというものが存在する（非特許文献３参照）。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】Monreale, A., Pinelli, F., Trasarti, R., & 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.
【非特許文献２】羽田野真由美，中辻真，戸田浩之，小池義昌. (2015). クラウドソーシングの時空間拡張におけるワーカの時間制約を考慮したタスク割当て手法．第7回データ工学と情報マネジメントに関するフォーラム.
【非特許文献３】Chen, C., Cheng, S. F., Gunawan, A., Misra, A., Dasgupta, K., & Chander, D. (2014). TRACCS: Trajectory-Aware Coordinated Urban Crowd-Sourcing. Second AAAI Conference on Human Computation and Crowdsourcing (HCOMP-14).
【非特許文献４】Ester, M., Kriegel, H. P., Sander, J., & Xu, X. (1996). A density-based algorithm for discovering clusters in large spatial databases with noise. Second International conference on Knowledge Discovery and Data Mining (Vol. 96, No. 34, pp. 226-231).
【非特許文献５】Cranshaw, J., Toch, E., Hong, J., Kittur, A., & Sadeh, N. (2010). Bridging the gap between physical location and online social networks. In Proceedings of the 12th ACM international conference on Ubiquitous computing (pp. 119-128).
【発明の概要】
【発明が解決しようとする課題】
【０００６】
従来技術を用い、ワーカの移動系列中にタスク割り当てを行う際、割り当てるタスクの順序によって結果が大きく異なるという問題がある。その結果、割り当てるタスクの順序によっては、あるワーカでなければできないような低密度タスクを割り当て損ねたり、低コストでたくさんのタスクを一度にこなせるような高密集タスクの一部を取りこぼしたりするおそれがある。なお、非特許文献３では、このような貪欲法の改善として、一度貪欲法で解を求めた後に局所探索法によって得られた解を改善していく手法が提案されているが、この手法はランダムに改善候補解を選択するため、対象エリアが広い場合にほとんど効果が得られない。
【０００７】
その結果、割り当てられなかったタスクを次の割り当てのタイミングに繰り越す必要があるため、時間的、又は金銭的なコストが余計にかかるという課題があった。
【０００８】
本発明は、上記問題点を解決するために成されたものであり、タスクの密度に応じて、ワーカに最適なタスクを割り当てることができるタスク割当装置、方法、及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００９】
上記目的を達成するために、第１の発明に係るタスク割当装置は、  複数のタスクを、移動する複数のワーカに割り当てるタスク割当装置であって、前記複数のタスクの各々の位置情報に基づいて、前記複数のタスクを複数のクラスタに分類するクラスタリング部と、前記複数のワーカの各々について予め求められた前記ワーカが移動する位置の移動系列、及び最大寄り道時間に基づいて、前記複数のクラスタの各々について、前記クラスタに属する全てのタスクを割り当て可能なワーカのうち、前記クラスタに属する全てのタスクを処理するのに必要な必要時間が最小となるワーカに、前記クラスタに属する全てのタスクを割り当てる暫定タスク割当部と、前記複数のワーカの各々について予め求められた前記ワーカが移動する位置の移動系列、及び最大寄り道時間と、前記クラスタに属する全てのタスクが割り当てられたワーカの前記必要時間とに基づいて、前記ワーカに割り当てられていないタスクの各々について、前記タスクを割り当て可能なワーカのうち、前記タスクを処理するのに必要な必要時間が最小となるワーカに、前記タスクを割り当てるタスク割当部と、を含んで構成されている。
【００１０】
また、第１の発明に係るタスク割当装置において、前記タスク割当部は、特定の人から多く訪問されているエリアである度合いを表すロケーションエントロピーが低いエリアに含まれる位置情報を有するタスクを優先して、前記ワーカに割り当てられていないタスクの各々について、前記タスクを割り当て可能なワーカのうち、前記タスクを処理するのに必要な必要時間が最小となるワーカに、前記タスクを割り当てるようにしてもよい。
【００１１】
また、第１の発明に係るタスク割当装置において、前記クラスタに属する全てのタスクを処理するのに必要な必要時間は、前記クラスタに属する全てのタスクの各々についての、前記ワーカの移動系列に含まれる位置のうち、前記タスクの位置情報に最も近い位置から計算される、前記タスクの位置との距離が最も短い位置、及び前記タスクの位置の間の移動時間と、前記クラスタに属する全てのタスクを処理するための移動時間との和であるようにしてもよい。
【００１２】
第２の発明に係るタスク割当方法は、複数のタスクを、移動する複数のワーカに割り当てるタスク割当装置におけるタスク割当方法であって、クラスタリング部が、前記複数のタスクの各々の位置情報に基づいて、前記複数のタスクを複数のクラスタに分類するステップと、暫定タスク割当部が、前記複数のワーカの各々について予め求められた前記ワーカが移動する位置の移動系列、及び最大寄り道時間に基づいて、前記複数のクラスタの各々について、前記クラスタに属する全てのタスクを割り当て可能なワーカのうち、前記クラスタに属する全てのタスクを処理するのに必要な必要時間が最小となるワーカに、前記クラスタに属する全てのタスクを割り当てるステップと、タスク割当部が、前記複数のワーカの各々について予め求められた前記ワーカが移動する位置の移動系列、及び最大寄り道時間と、前記クラスタに属する全てのタスクが割り当てられたワーカの前記必要時間とに基づいて、前記ワーカに割り当てられていないタスクの各々について、前記タスクを割り当て可能なワーカのうち、前記タスクを処理するのに必要な必要時間が最小となるワーカに、前記タスクを割り当てるステップと、を含んで実行することを特徴とする。
【００１３】
また、第２の発明に係るタスク割当方法において、前記タスク割当部が割り当てるステップは、特定の人から多く訪問されているエリアである度合いを表すロケーションエントロピーが低いエリアに含まれる位置情報を有するタスクを優先して、前記ワーカに割り当てられていないタスクの各々について、前記タスクを割り当て可能なワーカのうち、前記タスクを処理するのに必要な必要時間が最小となるワーカに、前記タスクを割り当てるようにしてもよい。
【００１４】
また、第２の発明に係るタスク割当方法において、前記クラスタに属する全てのタスクを処理するのに必要な必要時間は、前記クラスタに属する全てのタスクの各々についての、前記ワーカの移動系列に含まれる位置のうち、前記タスクの位置情報に最も近い位置から計算される、前記タスクの位置との距離が最も短い位置、及び前記タスクの位置の間の移動時間と、前記クラスタに属する全てのタスクを処理するための移動時間との和であるようにしてもよい。
【００１５】
第３の発明に係るプログラムは、コンピュータを、上記第１の発明に係るタスク割当装置の各部として機能させるためのプログラムである。
【発明の効果】
【００１６】
本発明のタスク割当装置、方法、及びプログラムによれば、複数のタスクの各々の位置情報に基づいて、複数のタスクを複数のクラスタに分類し、複数のクラスタの各々について、クラスタに属する全てのタスクを割り当て可能なワーカのうち、必要時間が最小となるワーカに、クラスタに属する全てのタスクを割り当て、ワーカに割り当てられていないタスクの各々について、タスクを割り当て可能なワーカのうち、必要時間が最小となるワーカに、タスクを割り当てることにより、タスクの密度に応じて、ワーカに最適なタスクを割り当てることができる、という効果が得られる。
【図面の簡単な説明】
【００１７】
【図１】本発明の実施の形態に係るタスク割当装置の構成を示すブロック図である。
【図２】本発明の実施の形態に係るタスク割当装置におけるタスク割当処理ルーチンを示すフローチャートである。
【図３】本発明の実施の形態に係るタスク割当装置におけるクラスタリング処理ルーチンを示すフローチャートである。
【図４】本発明の実施の形態に係るタスク割当装置における暫定タスク割当処理ルーチンを示すフローチャートである。
【図５】タスク集合を構成するタスクをすべて行う際の移動系列の一例を示す図である。
【図６】本発明の実施の形態に係るタスク割当装置における低密度タスク割当処理ルーチンを示すフローチャートである。
【図７】タスクを行う際の移動系列の一例を示す図である。
【図８】タスク割当の一例を示す図である。
【発明を実施するための形態】
【００１８】
以下、図面を参照して本発明の実施の形態を詳細に説明する。
【００１９】
＜本発明の実施の形態に係るタスク割当装置の構成＞
【００２０】
まず、本発明の実施の形態に係るタスク割当装置の構成について説明する。図１に示すように、本発明の実施の形態に係るタスク割当装置１００は、ＣＰＵと、ＲＡＭと、後述するタスク割当処理ルーチンを実行するためのプログラムや各種データを記憶したＲＯＭと、を含むコンピュータで構成することが出来る。このタスク割当装置１００は、機能的には図１に示すように入力部１０と、演算部２０と、を備えている。
【００２１】
入力部１０は、緯度経度で表された位置情報を含む複数のタスクを受け付け、タスクＤＢ１２に格納する。また、入力部１０は、移動する複数のワーカの日常的な移動系列情報を受け付け、ワーカＤＢ１４に格納する。
【００２２】
演算部２０は、タスクＤＢ１２と、ワーカＤＢ１４と、クラスタリング部３０と、クラスタリングタスクＤＢ４０と、暫定タスク割当部５０と、暫定割当タスクＤＢ６０と、暫定割当ワーカＤＢ７０と、タスク割当部８０と、割当結果ＤＢ９０とを含んで構成されている。
【００２３】
タスクＤＢ１２のデータ構造の例を表１に示す。タスクＤＢ１２には、複数のタスクの緯度経度を表す位置情報が格納される。外部からレコードを指定するために、各レコードにはタスクＩＤが付与されている。
【００２４】
【表１】
2017107385.tif 000003
【００２５】
クラスタリング部３０は、ワーカＤＢ１４に格納された複数のタスクの各々の位置情報に基づいて、タスクＤＢ１２に格納された複数のタスクを、タスク間の距離に応じて複数のクラスタに分類し、クラスタリングタスクＤＢ４０に格納する。
【００２６】
クラスタリングタスクＤＢ４０には、クラスタリング部３０によって分類された複数のクラスタが格納される。クラスタリングタスクＤＢ４０のデータ構造の例を表２に示す。クラスタリングタスクＤＢ４０の各レコードには、タスクＩＤ、タスクの緯度経度情報の他、タスクをタスク間の距離に応じてクラスタリングした結果のクラスＩＤが格納される。
【００２７】
【表２】
2017107385.tif 000004
【００２８】
ワーカＤＢ１４のデータ構造の例を表３に示す。ワーカＤＢ１４には、複数のワーカの各々について、一定時間分の当該ワーカの日常的な移動系列情報が格納されており、具体的には各時刻の緯度経度と、最大寄り道時間の情報が格納されている。表３の例ではワーカの１日分の情報を格納している。なお、ワーカの日常的な移動軌跡は、ＧＰＳログなどから日常生活の移動を抽出する既存研究によって抽出することができる（非特許文献１参照）。また、最大寄り道時間とは、ワーカがタスクのために余分に移動してもよいと考える時間のことを示している。例えば、表３のワーカＩＤ１の最大寄り道時間は６０分であり、タスク遂行のために１日６０分までであれば余分な移動を許容することを示している。なお、外部からレコードを指定するために、各レコードにはワーカＩＤが付与されている。
【００２９】
【表３】
2017107385.tif 000005
【００３０】
暫定タスク割当部５０は、ワーカＤＢ１４に格納された複数のワーカの各々が移動する位置の移動系列、及び最大寄り道時間と、タスクＤＢ１２に格納された複数のタスクの位置情報とに基づいて、クラスタリング部３０で分類された複数のクラスタの各々について、当該クラスタに属する全てのタスクを割り当て可能なワーカのうち、当該クラスタに属する全てのタスクを処理するのに必要な必要時間が最小となるワーカに、当該クラスタに属する全てのタスクを割り当てる。そして、全てのクラスタについての割り当て結果を、暫定的なタスクの割り当て結果として、暫定割当タスクＤＢ６０に格納し、ワーカに対してタスクを割り当てた結果を暫定割当ワーカＤＢ７０に格納する。
【００３１】
ここで、クラスタに属する全てのタスクを処理するのに必要な必要時間は、クラスタに属する全てのタスクの各々についての、ワーカの移動系列に含まれる位置のうち、タスクの位置情報に最も近い位置から計算される、タスクの位置との距離が最も短い位置、及びタスクの位置の間の移動時間と、クラスタに属する全てのタスクを処理するための移動時間との和である。
【００３２】
暫定割当タスクＤＢ６０のデータ構造の例を表４に示す。暫定割当タスクＤＢ６０には、タスクＩＤ、タスクの緯度経度、タスクが属しているクラスＩＤの他、ワーカに割り当てられたかどうかを示す割り当てフラグの情報が格納される。割り当てフラグ情報には、割り当てられたタスクの場合は１が、未割り当てのタスクの場合は０が格納されている。
【００３３】
【表４】
2017107385.tif 000006
【００３４】
暫定割当ワーカＤＢ７０のデータ構造の例を表５に示す。暫定割当ワーカＤＢ７０には、ワーカＤＢ１４と同じ情報に加えて、ワーカに割り当てたタスクの割り当てタスクＩＤを追加したレコードが格納される。
【００３５】
【表５】
2017107385.tif 000007
【００３６】
タスク割当部８０は、暫定割当ワーカＤＢ７０に格納されたワーカが移動する位置の移動系列、及び最大寄り道時間と、タスクＤＢ１２に格納された複数のタスクの位置情報と、クラスタに属する全てのタスクが割り当てられたワーカの必要時間とに基づいて、暫定割当タスクＤＢ６０から得られる、ワーカに割り当てられていないタスクの各々について、当該タスクを割り当て可能なワーカのうち、当該タスクを処理するのに必要な必要時間が最小となるワーカに、当該タスクを割り当てる。ここで、タスク割り当ては、特定の人から多く訪問されているエリアである度合いを表すロケーションエントロピーが低いエリアに含まれる位置情報を有するタスクを優先して、ワーカに割り当てられていないタスクの各々について、当該タスクを割り当て可能なワーカのうち、当該タスクを処理するのに必要な必要時間が最小となるワーカに、当該タスクを割り当てる。そして、すべてのタスクの割り当て結果を割当結果ＤＢ９０に格納する。
【００３７】
割当結果ＤＢ９０のデータ構造の例を表６に示す。割当結果ＤＢ９０は、暫定割当ワーカＤＢ７０の情報に追加でタスクを割り当てた結果が格納される。そのため、データ構造も暫定割当ワーカＤＢ７０と同様であり、ワーカＩＤ、時刻、ワーカ緯度経度情報、タスクＩＤ、及び最大寄り道時間の情報が格納される。
【００３８】
【表６】
2017107385.tif 000008
【００３９】
＜本発明の実施の形態に係るタスク割当装置の作用＞
【００４０】
次に、本発明の実施の形態に係るタスク割当装置１００の作用について説明する。入力部１０において複数のタスク、及び複数のワーカの移動系列情報を受け付け、それぞれをタスクＤＢ１２、及びワーカＤＢ１４に格納すると、タスク割当装置１００は、図２に示すタスク割当処理ルーチンを実行する。
【００４１】
まず、ステップＳ１００では、ワーカＤＢ１４に格納された複数のタスクの各々の位置情報に基づいて、タスクＤＢ１２に格納された複数のタスクを複数のクラスタに分類し、クラスタリングタスクＤＢ４０に格納する。
【００４２】
次に、ステップＳ１０２では、ワーカＤＢ１４に格納された複数のワーカの各々が移動する位置の移動系列、及び最大寄り道時間と、タスクＤＢ１２に格納された複数のタスクの位置情報とに基づいて、クラスタリングタスクＤＢ４０に格納された複数のクラスタの各々について、当該クラスタに属する全てのタスクを割り当て可能なワーカのうち、当該クラスタに属する全てのタスクを処理するのに必要な必要時間が最小となるワーカに、当該クラスタに属する全てのタスクを割り当てる。
【００４３】
ステップＳ１０４では、暫定割当ワーカＤＢ７０に格納されたワーカが移動する位置の移動系列、及び最大寄り道時間と、タスクＤＢ１２に格納された複数のタスクの位置情報と、クラスタに属する全てのタスクが割り当てられたワーカの必要時間とに基づいて、暫定割当タスクＤＢ６０から得られる、ワーカに割り当てられていないタスクの各々について、当該タスクを割り当て可能なワーカのうち、当該タスクを処理するのに必要な必要時間が最小となるワーカに、当該タスクを割り当てる。
【００４４】
上記ステップＳ１００は、図３に示すクラスタリング処理ルーチンによって実現される。
【００４５】
まず、ステップＳ２００では、集合Ｓを用意し、空集合とする。
【００４６】
ステップＳ２０２では、タスクＤＢ１２よりタスクのレコード集合を検索し、タスクの集合Ｔとする。
【００４７】
ステップＳ２０４では、タスクの集合Ｔから緯度経度情報を利用してタスクのクラスタリングを行い、クラスＩＤを集合Ｔに追加した集合を集合Ｓとする。クラスタリングの際は、緯度経度情報を二次元平面として距離を計算するほか、地球の丸みを考慮した大圏距離を利用して距離を求めることも出来る。クラスタリングのアルゴリズムは、例えばＤＢＳＣＡＮ法（非特許文献４参照）などを用いることができるが、他のクラスタリングアルゴリズムを用いても構わない。
【００４８】
ステップＳ２０６では、ステップＳ２０４で得た集合Ｓの情報をクラスタリングタスクＤＢ４０に出力し、処理を終了する。
【００４９】
上記ステップＳ１０２は、図４に示す暫定タスク割当処理ルーチンによって実現される。
【００５０】
まず、ステップＳ３００では、集合Ａを用意し、空集合とする。
【００５１】
ステップＳ３０２では、クラスタリングタスクＤＢ４０、及びワーカＤＢ１４よりレコード集合を検索し、それぞれタスクの集合Ｔ、ワーカの集合Ｗとする。
【００５２】
ステップＳ３０４では、集合Ｔから未割り当てのクラスを選択し、クラスｃとする。また、クラスｃを構成するタスク集合をＴｃとする。また、集合Ｒを用意し、空集合とする。
【００５３】
ステップＳ３０６では、集合Ｗから未選択のワーカを選択し、ワーカｗとする。
【００５４】
ステップＳ３０８では、ワーカｗの最大寄り道時間に余裕がある場合ステップＳ３１０に進み、ワーカｗの最大寄り道時間に余裕がない場合はステップＳ３０６に戻る。
【００５５】
ステップＳ３１０では、ワーカｗがタスク集合Ｔｃを構成するタスクすべてを行う際の必要時間ｔｉｍｅ（ｗ，Ｔｃ）を計算し、ワーカｗ、必要時間ｔｉｍｅ（ｗ，Ｔｃ）、及び移動系列の要素のインデックスの三組み（ｗ，ｔｉｍｅ（ｗ，Ｔｃ），ｋ＊）を集合Ｒに追加する。ここで、移動系列の要素のインデックスの計算方法を示す。まず、タスク集合Ｔｃのｉ番目のタスクの緯度経度を（ｌａｔｉ´，ｌｏｎｉ´）、ワーカｗの移動系列のｋ番目の緯度経度を（ｌａｔｋ，ｌｏｎｋ）とする。また、ある２点（ｌａｔｉ，ｌｏｎｉ），（ｌａｔｊ，ｌｏｎｊ）間の距離をｄｉｓｔ（ｌａｔｉ，ｌｏｎｉ，ｌａｔｊ，ｌｏｎｊ）とする。ワーカｗの移動系列の中でｉ番目のタスクに一番近い要素ｋｉは以下のように計算できる。
【００５６】
【数１】
2017107385.tif 000009
【００５７】
また、２点間の距離の計算はユークリッド距離や道路ネットワーク距離などが利用できる。
【００５８】
上記（１）式のｋｉの計算を、タスク集合Ｔｃの各々のタスクの各々について行う。
【００５９】
次に、タスク集合Ｔｃの各々のタスクについて計算されたｋｉの中で、タスク集合Ｔｃのタスクとの最短距離が最も短いものを以下（２）式のように計算する。
【００６０】
【数２】
2017107385.tif 000010
【００６１】
次に、ｔｉｍｅ（ｗ，Ｔｃ）の計算方法の一例を示す。図５に示すように、ワーカｗの移動速度をｖとし、ワーカｗがタスク集合Ｔｃを構成するすべてのタスクを行った後に元の場所に戻るような移動を考える。その際の必要時間は、ワーカｗの移動系列からタスク集合Ｔｃまでの移動時間とタスク集合Ｔｃ内の移動時間の和で表すことが出来、以下（３）式のように計算できる。
【００６２】
【数３】
2017107385.tif 000011
【００６３】
ここで、ｄｉｓｔ（Ｔｃ，ｉ）はタスク集合Ｔｃ内のｉ番目のタスクを起終点にし、タスク集合Ｔｃ内のすべてのタスクを巡回する際の最短経路の距離を示す。なお、ワーカｗがタスク集合Ｔｃを構成するタスクをすべて行った後に元の位置に戻らず、次に行く予定であった移動系列に移動をする場合でもこのような計算で最小必要時間を計算することができる。
【００６４】
ステップＳ３１２では、集合Ｗに未処理のワーカｗが存在する場合ステップＳ３０６に戻り、集合Ｗに未処理のワーカｗが存在しない場合ステップＳ３１４に進む。
【００６５】
ステップＳ３１４では、集合Ｒより、必要時間が最小となる三組みのワーカｗを選択し、そのワーカｗにタスク集合Ｔｃを構成するタスクすべてを割り当てた結果を集合Ａに追加する。ここで、集合Ａは、ワーカＩＤ、時刻、ワーカ緯度、ワーカ経度、最大寄り道時間、及び割当てタスクＩＤの要素を持ち、タスクのための移動をワーカＤＢ１４に追加した結果が格納される。ここで、必要時間が最小なワーカをｗｍ、そのときの必要時間をｔｉｍｅｍ、元の移動系列の最大寄り道時間をｔｉｍｅｍａｘとすると、ワーカｗｍをタスクｔに割り当てた結果は以下のように計算できる。まず、ワーカｗｍがタスクを行う際の移動系列は、ワーカのもとの移動系列のｋ´＋１番目の要素に挿入される。またｋ´＋１以降の時刻はそれぞれｔｉｍｅｍだけ後ろにずれる。さらに、最大寄り道時間はｔｉｍｅｍａｘ−ｔｉｍｅｍとなる。
【００６６】
ステップＳ３１６では、集合Ｔに未処理のクラスｃがある場合ステップＳ３０４に戻り、集合Ｔに未処理のクラスｃがない場合ステップＳ３１８に進む。
【００６７】
ステップＳ３１８では、ワーカｗｍにタスク集合Ｔｃの各々を割り当てることにより得た集合Ａを利用して、集合Ｔに割当てフラグ、集合Ｗに割当てタスクＩＤをそれぞれ付与した結果を暫定割当タスクＤＢ６０と、暫定割当ワーカＤＢ７０とに出力し、処理を終了する。
【００６８】
上記ステップＳ１０４は、図６に示す低密度タスク割当処理ルーチンによって実現される。
【００６９】
まず、ステップＳ４００では、集合Ｂを用意し、空集合とする。
【００７０】
ステップＳ４０２では、暫定割当タスクＤＢ６０と暫定割当ワーカＤＢ７０よりレコード集合を検索し、それぞれ集合Ｔ´、集合Ｗ´とする。集合Ｔ´はワーカに割り当てられていないタスクの集合である。
【００７１】
ステップＳ４０４では、ワーカＤＢ１４に格納された複数のワーカの各々が移動する位置の移動系列に基づいて、各エリアのロケーションエントロピー値を計算する。ロケーションエントロピー値の計算例を示す。ロケーションエントロピー値とは、人の訪問ログ情報から計算するエリア特性指標として、非特許文献５で提案されたものである。一般に、多くの人が等しく訪問するような繁華街などでは高い値を、特定の人しか訪問しないような住宅街では低い値を示すことが知られている。以下に、ロケーションエントロピー値の計算方法を示す。まず、対象地域をグリッドなどの単位に分割し、分割した各エリアをそれぞれロケーションｌとする。全ワーカがロケーションｌを訪問した回数を｜Ｏｌ｜、ワーカｕがロケーションｌを訪問した回数を｜Ｏｕ，ｌ｜とすると、ワーカｕがロケーションｌを訪問する確率Ｐｌ（ｕ）は以下（４）式のように計算できる。
【００７２】
【数４】
2017107385.tif 000012
【００７３】
ここで、ｌを訪問したワーカ集合をＵｌとすると、ロケーションｌのロケーションエントロピー値は、以下（５）式のように計算される。
【００７４】
【数５】
2017107385.tif 000013
【００７５】
ステップＳ４０６では、集合Ｔ´から未割り当てタスクのうち、タスクの位置を含むエリアのロケーションエントロピー値が最小となるものを１つ選択し、ｔ´とする。また、集合Ｄを用意し、空集合とする。
【００７６】
ステップＳ４０８では、集合Ｗ´から未処理の要素を取り出し、ワーカｗ´とする。
【００７７】
ステップＳ４１０では、ワーカｗ´の最大寄り道時間に余裕がない場合ステップＳ４０８に戻り、ワーカｗ´の最大寄り道時間に余裕がある場合はステップＳ４１２に進む。
【００７８】
ステップＳ４１２では、ワーカｗ´がタスクｔ´を行う際の必要時間ｔｉｍｅ（ｗ´，ｔ´）を計算し、ワーカｗ´、必要時間ｔｉｍｅ（ｗ´，ｔ´）、及び移動系列の要素のインデックスの三組み（ｗ´，ｔ´，ｋ´）を集合Ｄに追加する。ここで、移動系列の要素のインデックスｋ´の計算方法を示す。まず、タスクｔ´の緯度経度を（ｌａｔ´，ｌｏｎ´）、ワーカｗ´の移動系列のｋ番目の緯度経度を（ｌａｔｋ，ｌｏｎｋ）とする。また、２点（ｌａｔｉ，ｌｏｎｉ），（ｌａｔｊ，ｌｏｎｊ）間の距離をｄｉｓｔ（ｌａｔｉ，ｌｏｎｉ，ｌａｔｊ，ｌｏｎｊ）とする。ワーカｗ´の移動系列の中でタスクｔ´に一番近い要素ｋ´は以下（６）式のように計算できる。
【００７９】
【数６】
2017107385.tif 000014
【００８０】
なお、２点間の距離の計算はユークリッド距離や道路ネットワーク距離などが利用できる。次に、ｔｉｍｅ（ｗ、ｔ）の計算方法の一例を示す。図７に示すように、ワーカｗの移動速度をｖとし、ワーカｗがタスクｔを行った後に元の場所に戻るような移動を考える。その際の必要時間は以下（７）式のように計算できる。
【００８１】
【数７】
2017107385.tif 000015
【００８２】
また、ワーカｗがタスクを行った後に元の位置に戻らず、次に行く予定であった移動系列に移動をする場合でもこのような計算で必要時間を計算することができる。
【００８３】
ステップＳ４１４では、集合Ｗ´に未処理のワーカｗ´が存在する場合、ステップＳ４０８に戻り、集合Ｗ´に未処理のワーカｗ´が存在しない場合はステップＳ４１６に進む。
【００８４】
ステップＳ４１６では、集合Ｄより必要時間が最小なワーカｗ´を選択し、そのワーカｗ´にｔ´を割り当てた結果を集合Ｂに追加する。
【００８５】
ステップＳ４１８では、集合Ｔ´に未処理のタスクがある場合、ステップＳ４０６に戻り、Ｔ´に未処理のタスクがない場合はステップＳ４２０に進む。
【００８６】
ステップＳ４２０では、ワーカｗ´に割り当てられていないタスクの各々について割り当てることにより得た集合Ｂを利用して、集合Ｗ´のレコードに割り当て結果を付与した結果を割当結果ＤＢ９０に出力し処理を終了する。
【００８７】
以上説明したように、本発明の実施の形態に係るタスク割当装置によれば、複数のタスクの各々の位置情報に基づいて、複数のタスクを複数のクラスタに分類し、複数のクラスタの各々について、クラスタに属する全てのタスクを割り当て可能なワーカのうち、必要時間が最小となるワーカに、クラスタに属する全てのタスクを割り当て、ワーカに割り当てられていないタスクの各々について、タスクを割り当て可能なワーカのうち、必要時間が最小となるワーカに、タスクを割り当てることにより、タスクの密度に応じて、ワーカに最適なタスクを割り当てることができる。
【００８８】
また、本発明の実施の形態に係る手法によって、まず高密集なタスクをクラスタリングによってまとめ、優先的にワーカに割当てたのちに、ロケーションエントロピーが低い順にタスクを貪欲法で割り当てることで、ワーカへ割当てることができるタスク数を出来るだけ多くすることが可能となる。その結果、従来手法では割当てることが出来なかった追加タスクも割当てることが可能になるため、時間的、金銭的なコストを削減することが可能になり、従来の課題が解決される。
【００８９】
また、上記の効果により、全体で割り当てることができるタスク数を増やすことが可能になる。その結果、従来手法では割り当てることが出来なかったタスクを追加で割り当てる時間的、金銭的なコストを削減することが可能となる。また、再割り当てが必要なくなるため、タスク完了までの納期を削減することにつながり、少しでも早く仕事を終わらせたいと考えているタスク依頼者の満足度向上につながる。
【００９０】
なお、本発明は、上述した実施の形態に限定されるものではなく、この発明の要旨を逸脱しない範囲内で様々な変形や応用が可能である。
【符号の説明】
【００９１】
１０   入力部
１２   タスクＤＢ
１４   ワーカＤＢ
２０   演算部
３０   クラスタリング部
４０   クラスタリングタスクＤＢ
５０   暫定タスク割当部
６０   暫定割当タスクＤＢ
７０   暫定割当ワーカＤＢ
８０   タスク割当部
９０   割当結果ＤＢ
１００ タスク割当装置
【図１】
2017107385.tif 000016
【図２】
2017107385.tif 000017
【図３】
2017107385.tif 000018
【図４】
2017107385.tif 000019
【図５】
2017107385.tif 000020
【図６】
2017107385.tif 000021
【図７】
2017107385.tif 000022
【図８】
2017107385.tif 000023