(57)【要約】【課題】複数のポイントの中から所望の条件を満たす複数の代表ポイントを自動的に選択する。【解決手段】配置地点選択部１６は、対象地域に含まれる複数のポイントの中から、初期設定部１４により設定された数の仮代表ポイントを任意に選択する。つづいて、配置地点選択部１６は、仮代表ポイント間の位置情報に基づいて定まる距離パラメータが大きくなるように、複数の仮代表ポイントを選択しなおす処理を繰り返して実行する。その後、配置地点選択部１６は、仮代表ポイントを代表ポイントとして確定する。対象地域をエリア分割する際の起点としてこのような代表ポイントを選択することができる。また、対象地域における設備の配置位置として代表ポイントを選択することもできる。【選択図】　　　図２
2004112256.tif 000002
【特許請求の範囲】
【請求項１】
対象地域に含まれる複数のポイントから複数の代表ポイントを選択する方法であって、
前記複数のポイントの中から複数の仮代表ポイントを選択した後、仮代表ポイント間の位置情報に基づいて定まる距離パラメータが大きくなるように、前記複数の仮代表ポイントを選択しなおす処理を繰り返して実行し、次いで前記仮代表ポイントを代表ポイントとして確定することを特徴とする代表ポイント選択方法。
【請求項２】
対象地域に含まれる複数のポイントから複数の代表ポイントを選択する方法であって、
前記複数のポイントの中から複数の仮代表ポイントを選択した後、
前記仮代表ポイント以外の他のポイントから置換候補ポイントを選択する第一のステップと、
前記仮代表ポイントの位置情報に基づいて定まる第一の距離パラメータを算出し、前記仮代表ポイントを前記置換候補ポイントに置換したときの仮代表ポイントの位置情報に基づいて定まる第二の距離パラメータを算出し、前記第二の距離パラメータが前記第一の距離パラメータよりも大きくなる場合に、前記仮代表ポイントを前記置換候補ポイントに置換する第二のステップと、
を順次繰り返して実行し、次いで前記仮代表ポイントを代表ポイントとして確定することを特徴とする代表ポイント選択方法。
【請求項３】
請求項１または２に記載の代表ポイント選択方法において、前記距離パラメータは、前記仮代表ポイント間距離の最小値であることを特徴とする代表ポイント選択方法。
【請求項４】
請求項１乃至３いずれかに記載の代表ポイント選択方法において、前記距離パラメータは、前記仮代表ポイント間距離の平均値であることを特徴とする代表ポイント選択方法。
【請求項５】
請求項１乃至４いずれかに記載の代表ポイント選択方法において、前記距離パラメータは、前記仮代表ポイント間距離の差の逆数であることを特徴とする代表ポイント選択方法。
【請求項６】
請求項１乃至５いずれかに記載の代表ポイント選択方法において、前記複数のポイントにそれぞれ属性情報を付与し、前記仮代表ポイントの属性情報を考慮して前記距離パラメータを算出することを特徴とする代表ポイント選択方法。
【請求項７】
請求項１乃至５いずれかに記載の代表ポイント選択方法において、前記複数のポイントにそれぞれ属性情報を付与し、各前記仮代表ポイント間を結ぶ線分の距離を算出し、各前記線分の距離に対し、その線分の両端のポイントの属性情報に基づいて定められる重み付け係数を乗算することにより前記距離パラメータを算出することを特徴とする代表ポイント選択方法。
【請求項８】
請求項６または７に記載の代表ポイント選択方法において、前記属性情報は、ポイントの配置された地域の特性に基づくものであることを特徴とする代表ポイント選択方法。
【請求項９】
対象地域に含まれる複数のポイントから複数の代表ポイントを選択する方法であって、
前記複数のポイントから複数の仮代表ポイントを任意に選択した後、
前記仮代表ポイント以外の他のポイントから任意に選択した一のポイントを仮代表ポイントに加える第一のステップと、
前記仮代表ポイントをそれぞれ結ぶ線分のうち最短の線分の両端のポイントのいずれか一方を前記仮代表ポイントから外す第二のステップと、
を順次繰り返して実行し、次いで前記仮代表ポイントを代表ポイントとして確定することを特徴とする代表ポイント選択方法。
【請求項１０】
請求項１乃至９いずれかに記載の代表ポイント選択方法において、
前記代表ポイント以外の他のポイントを前記代表ポイントのいずれかに帰属させるステップと、
各代表ポイントに帰属するポイントの数またはポイントの配置状態を考慮して前記代表ポイントの中から一以上のポイントを削除し、代表ポイントを選別するステップと、
をさらに含むことを特徴とする代表ポイント選択方法。
【請求項１１】
請求項１乃至１０いずれかに記載の代表ポイント選択方法において、
前記対象地域を複数のエリアに分割し前記複数のポイントを各前記エリアに帰属させる際の起点として前記代表ポイントを選択することを特徴とする代表ポイント選択方法。
【請求項１２】
請求項１乃至１０いずれかに記載の代表ポイント選択方法において、
前記対象地域における設備の配置位置として前記代表ポイントを選択することを特徴とする代表ポイント選択方法。
【請求項１３】
複数のポイントを含む対象地域の中から複数の代表ポイントを選択するステップと、
選択された前記代表ポイントを含むエリアを初期値として複数設定するステップと、
各前記エリアに追加するポイントを、各前記エリアの代表点からの距離を考慮して選択する処理を繰り返して各エリアを拡張し、前記複数のポイントをいずれかのエリアに帰属させるステップと、
を含むエリア分割方法であって、
請求項１乃至１０いずれかに記載の代表ポイント選択方法により前記複数の代表ポイントを選択することを特徴とするエリア分割方法。
【請求項１４】
対象地域に含まれる複数の候補地点から、複数の設備の配置地点を選択する方法であって、
請求項１乃至１０いずれかに記載の代表ポイント選択方法により複数の代表ポイントを選択し、選択された代表ポイントを前記複数の設備の配置地点として選択することを特徴とする配置地点の選択方法。
【請求項１５】
コンピュータシステムにより、対象地域に含まれる複数のポイントから複数の代表ポイントを選択する方法であって、
前記コンピュータシステムは、仮代表ポイント選択手段、および距離パラメータ比較手段を備え、
前記仮代表ポイント選択手段が、前記複数のポイントの中から複数の仮代表ポイントを選択した後、
前記距離パラメータ比較手段が、仮代表ポイント間の位置情報に基づいて定まる距離パラメータが大きくなるように、前記複数の仮代表ポイントを選択しなおす処理を繰り返して実行し、次いで前記仮代表ポイントを代表ポイントとして確定することを特徴とする代表ポイント選択方法。
【請求項１６】
コンピュータシステムにより、対象地域に含まれる複数のポイントから複数の代表ポイントを選択する方法であって、
前記コンピュータシステムは、仮代表ポイント選択手段、置換候補ポイント選択手段、および距離パラメータ比較手段を備え、
前記仮代表ポイント選択手段が、前記複数のポイントの中から複数の仮代表ポイントを選択した後、
前記置換候補ポイント選択手段が、前記仮代表ポイント以外の他のポイントから置換候補ポイントを選択する第一のステップと、
前記距離パラメータ比較手段が、前記仮代表ポイントの位置情報に基づいて定まる第一の距離パラメータを算出し、前記仮代表ポイントを前記置換候補ポイントに置換したときの仮代表ポイントの位置情報に基づいて定まる第二の距離パラメータを算出し、前記第二の距離パラメータが前記第一の距離パラメータよりも大きくなる場合に、前記仮代表ポイントを前記置換候補ポイントに置換する第二のステップと、
を繰り返して実行し、次いで前記仮代表ポイントを代表ポイントとして確定することを特徴とする代表ポイント選択方法。
【請求項１７】
請求項１５または１６に記載の代表ポイント選択方法において、
前記距離パラメータ比較手段は、前記仮代表ポイント間距離の最小値を前記距離パラメータとして利用することを特徴とする代表ポイント選択方法。
【請求項１８】
請求項１５乃至１７いずれかに記載の代表ポイント選択方法において、
前記距離パラメータ比較手段は、前記仮代表ポイント間距離の平均値を前記距離パラメータとして利用することを特徴とする代表ポイント選択方法。
【請求項１９】
請求項１５乃至１８いずれかに記載の代表ポイント選択方法において、
前記距離パラメータ比較手段は、前記仮代表ポイント間距離の差の逆数を前記距離パラメータとして利用することを特徴とする代表ポイント選択方法。
【請求項２０】
請求項１５乃至１９いずれかに記載の代表ポイント選択方法において、
前記距離パラメータ比較手段は、前記複数のポイントにそれぞれ属性情報を付与し、前記仮代表ポイントの属性情報を考慮して前記距離パラメータを算出することを特徴とする代表ポイント選択方法。
【請求項２１】
請求項１５乃至１９いずれかに記載の代表ポイント選択方法において、
前記距離パラメータ比較手段は、前記複数のポイントにそれぞれ属性情報を付与し、各前記仮代表ポイント間を結ぶ線分の距離を算出し、各前記線分の距離に対し、その線分の両端のポイントの属性情報に基づいて定められる重み付け係数を乗算することにより前記距離パラメータを算出することを特徴とする代表ポイント選択方法。
【請求項２２】
請求項１５乃至２１いずれかに記載の代表ポイント選択方法において、
前記コンピュータシステムは、代表ポイント選別手段をさらに備え、
前記代表ポイント選別手段が、
前記代表ポイント以外の他のポイントを前記代表ポイントのいずれかに帰属させるステップと、
各代表ポイントに帰属するポイントの数またはポイントの配置状態を考慮して前記代表ポイントの中から一以上のポイントを削除し、代表ポイントを選別するステップと、
をさらに含むことを特徴とする代表ポイント選択方法。
【請求項２３】
請求項１５乃至２２いずれかに記載の代表ポイント選択方法において、
前記対象地域を複数のエリアに分割し前記複数のポイントを各前記エリアに帰属させる際の起点として前記代表ポイントを選択することを特徴とする代表ポイント選択方法。
【請求項２４】
請求項１５乃至２２いずれかに記載の代表ポイント選択方法において、
前記対象地域における設備の配置位置として前記代表ポイントを選択することを特徴とする代表ポイント選択方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、代表ポイント選択方法、エリア分割方法、および配置地点の選択方法に関する。本発明は特に、対象地域に含まれる複数のポイントから、所望の条件を満たす複数の代表ポイントを選択する方法に関する。
【０００２】
【従来の技術】
一つの地域内に分散配置された複数の候補地点から、所望の条件を満たす地点を適切に選択するということは日常生活の様々な場面で必要である。たとえば、ある地域でサービスを提供する場合、その地域全体にサービスが行き渡るように、複数のサービスポイントを好適に配置する試みがなされる。
【０００３】
このような例として、移動体通信の分野では、無線通信網の基地局を適切な位置に設置するのが重要である。基地局の設置計画や基地局の保守計画を作成する場合、サービスエリアのどの位置に基地局を設置すれば効率よく高品質なサービスを提供できるかということを考慮する必要がある。
【０００４】
例えば、所定のサービスエリアに対して、基地局の複数の異なる設置パターンを用意し、設置パターン毎に品質評価値およびコスト評価値を算出し、これらに基づいて設置パターンを決定する方法が提案されている（特許文献１参照）。ここで、品質評価値は、各設置パターンについて、電界強度分布のシミュレーションを行い、設置パターン毎にシミュレーション結果に基づいて、サービスエリアの面積に対する通話可能エリアの面積の比率として算出される。
【０００５】
【特許文献１】
特開平８−３１７４５８号公報
【０００６】
【発明が解決しようとする課題】
しかし、従来の方法では、複数の設置パターンを用意する必要があり、用意されたすべての設置パターンについて品質評価値およびコスト評価値を算出する必要があった。
【０００７】
ここで、無線通信網の基地局にはそれぞれ電波の届く範囲があり、この範囲により各基地局が受け持つエリアが定められる。したがって、あるサービスエリアに経済的に基地局を設置するためには、各基地局が受け持つエリアがなるべく重ならないように基地局の設置位置を適切に選択することが重要である。こうした問題は、上述したように、地域全体にサービスが行き渡るように、地域内に複数のサービスポイントを設定する際にも考慮する必要がある。
【０００８】
また、たとえばある地域にコンビニエンスストア等のチェーン店を展開させる際に、店舗どうしが競合しないように、各店舗の商圏が重ならないような適切な配置を考慮する必要がある。
【０００９】
一方、複数の巡回ポイントを含む営業地域を、複数の作業員の担当エリアに分割するような場合に、巡回作業を効率よく行い、作業員の数を増やすことなく巡回ポイントの数を増やすことは重要な問題である。巡回作業を効率よく行うためには、各担当エリアにおける巡回ポイント間の移動距離が少なくなるように担当エリアを分割するのが好ましい。そのための一例として、複数の巡回ポイントを、互いの距離が短い巡回ポイントの組み合わせが同一のエリアに含まれるように複数のエリアに分類するという手法が挙げられる。しかし、このような処理を無秩序に行ったのでは、営業地域をきれいにエリア分割することはできず、全体としてはかえって効率が悪くなってしまうこともある。そのため、複数の巡回ポイントの中から、各エリアの起点となる巡回ポイントを適切に選択することが重要である。
【００１０】
本発明の目的は、対象地域内に配置された複数の候補地点から、複数の代表地点を適切な配置で選択する技術を提供することである。本発明の別の目的は、対象地域でサービスを提供する場合に、その地域全体にサービスが行き渡るように、地域内に複数のサービスポイントを効率よく配置する技術を提供することである。本発明の別の目的は、対象地域内に複数のサービスポイントを配置する場合に、他のサービスポイントの位置との関係で、各サービスポイントにおける効果が高くなるような配置を選択する技術を提供することである。本発明のまた別の目的は、複数の巡回ポイントを含む対象地域をエリア分割する際に、各エリアの起点となる巡回ポイントを適切に選択する技術を提供することである。
【００１１】
【課題を解決するための手段】
本発明によれば、対象地域に含まれる複数のポイントから複数の代表ポイントを選択する方法であって、複数のポイントの中から複数の仮代表ポイントを選択した後、仮代表ポイント間の位置情報に基づいて定まる距離パラメータが大きくなるように、複数の仮代表ポイントを選択しなおす処理を繰り返して実行し、次いで仮代表ポイントを代表ポイントとして確定することを特徴とする代表ポイント選択方法が提供される。
【００１２】
また、本発明によれば、コンピュータシステムにより、対象地域に含まれる複数のポイントから複数の代表ポイントを選択する方法であって、コンピュータシステムは、仮代表ポイント選択手段、および距離パラメータ比較手段を備え、仮代表ポイント選択手段が、複数のポイントの中から複数の仮代表ポイントを選択した後、距離パラメータ比較手段が、仮代表ポイント間の位置情報に基づいて定まる距離パラメータが大きくなるように、複数の仮代表ポイントを選択しなおす処理を繰り返して実行し、次いで仮代表ポイントを代表ポイントとして確定することを特徴とする代表ポイント選択方法が提供される。
【００１３】
本発明に係る代表ポイントの選択方法は、距離パラメータが大きくなるように仮代表ポイントを選択しなおす処理を繰り返し実行するため、互いに適切に分散された配置の代表ポイントを選択することができる。仮代表ポイントは任意に選択していくことができる。距離パラメータは、たとえば仮代表ポイント間の最小値、仮代表ポイント間の平均値、またはこれらと仮代表ポイント間距離の差の逆数との組み合わせとすることができる。ここで、たとえば、仮代表ポイントを選択しなおす処理を所定回数行った時点において仮代表ポイントとして選択されているポイントを代表ポイントとして確定することができる。また、仮代表ポイントを選択しなおした場合における距離パラメータの変化量が所定の値以下になった時点で選択されているポイントを代表ポイントとして確定することもできる。
【００１４】
本発明によれば、対象地域に含まれる複数のポイントから複数の代表ポイントを選択する方法であって、複数のポイントの中から複数の仮代表ポイントを選択した後、仮代表ポイント以外の他のポイントから置換候補ポイントを選択する第一のステップと、仮代表ポイントの位置情報に基づいて定まる第一の距離パラメータを算出し、仮代表ポイントを置換候補ポイントに置換したときの仮代表ポイントの位置情報に基づいて定まる第二の距離パラメータを算出し、第二の距離パラメータが第一の距離パラメータよりも大きくなる場合に、仮代表ポイントを置換候補ポイントに置換する第二のステップと、を順次繰り返して実行し、次いで仮代表ポイントを代表ポイントとして確定することを特徴とする代表ポイント選択方法が提供される。
【００１５】
また、本発明によれば、コンピュータシステムにより、対象地域に含まれる複数のポイントから複数の代表ポイントを選択する方法であって、コンピュータシステムは、仮代表ポイント選択手段、置換候補ポイント選択手段、および距離パラメータ比較手段を備え、仮代表ポイント選択手段が、複数のポイントの中から複数の仮代表ポイントを選択した後、置換候補ポイント選択手段が、仮代表ポイント以外の他のポイントから置換候補ポイントを選択する第一のステップと、距離パラメータ比較手段が、仮代表ポイントの位置情報に基づいて定まる第一の距離パラメータを算出し、仮代表ポイントを置換候補ポイントに置換したときの仮代表ポイントの位置情報に基づいて定まる第二の距離パラメータを算出し、第二の距離パラメータが第一の距離パラメータよりも大きくなる場合に、仮代表ポイントを置換候補ポイントに置換する第二のステップと、
を順次繰り返し行うことにより、複数の代表ポイントを選択することを特徴とする代表ポイント選択方法が提供される。
【００１６】
本発明に係る代表ポイントの選択方法は、距離パラメータが大きくなる場合に、仮代表ポイントを置換候補ポイントに置換する処理を繰り返し実行するため、互いに適切に分散された配置の代表ポイントを選択することができる。また、置換候補ポイントと置換した場合の距離パラメータと既存の仮代表ポイントの距離パラメータとを比較するので、前回の処理で置換されなかった仮代表ポイントの距離パラメータを改めて算出する必要がなく、距離パラメータの比較を行う際の手順を簡略化することができる。これにより、迅速に代表ポイントを選択することができる。また、置換候補ポイントは、複数のポイントから順次選択していくことができる。これにより、すべてのポイントについて仮代表ポイントと置換するか否かを判断することができるので、好適に分散された配置の代表ポイントを選択することができる。また、このような処理を繰り返して実行することにより、代表ポイントの分散状態を最適化することができる。
【００１７】
本発明の代表ポイント選択方法において、距離パラメータは、仮代表ポイント間距離の最小値とすることができる。
【００１８】
また、本発明の代表ポイント選択方法において、距離パラメータ比較手段は、仮代表ポイント間距離の最小値を距離パラメータとして利用することができる。
【００１９】
このようにすれば、ポイント間距離が小さくなるようなポイントの組み合わせが排除されていくので、最終的に、ポイント間の距離が互いに離れたポイントの組み合わせを代表ポイントとして選択することができる。
【００２０】
本発明の代表ポイント選択方法において、距離パラメータは、仮代表ポイント間距離の平均値とすることができる。
【００２１】
また、本発明の代表ポイント選択方法において、距離パラメータ比較手段は、仮代表ポイント間距離の平均値を距離パラメータとして利用することができる。
【００２２】
このようにすれば、ポイント間距離が大きくなるようなポイントの組み合わせが仮代表ポイントとして選択されていくので、最終的に、ポイント間の距離が互いに離れたポイントの組み合わせを代表ポイントとして選択することができる。
【００２３】
本発明の代表ポイント選択方法において、距離パラメータは、仮代表ポイント間距離の差の逆数とすることができる。また、本発明の代表ポイント選択方法において、距離パラメータ比較手段は、仮代表ポイント間距離の差の逆数を距離パラメータとして利用することができる。
【００２４】
このようにすれば、ポイント間距離の差が小さくなるようなポイントの組み合わせが仮代表ポイントとして選択されていくので、最終的に、ポイント間の距離が均等に近づくポイントの組み合わせを代表ポイントとして選択することができる。これにより、代表ポイントの地域的な偏りを防ぐことができる。
【００２５】
本発明の代表ポイント選択方法において、複数のポイントにそれぞれ属性情報を付与し、仮代表ポイントの属性情報を考慮して距離パラメータを算出することができる。
【００２６】
また、本発明の代表ポイント選択方法において、距離パラメータ比較手段は、複数のポイントにそれぞれ属性情報を付与し、仮代表ポイントの属性情報を考慮して距離パラメータを算出することができる。
【００２７】
このようにすれば、複数のポイント間でそれぞれ属性が異なる場合であっても、属性の違いを考慮して、適切に分散された代表ポイントを選択することができる。
【００２８】
本発明の代表ポイント選択方法において、複数のポイントにそれぞれ属性情報を付与し、各仮代表ポイント間を結ぶ線分の距離を算出し、各線分の距離に対し、その線分の両端のポイントの属性情報に基づいて定められる重み付け係数を乗算することにより距離パラメータを算出することができる。
【００２９】
また、本発明の代表ポイント選択方法において、距離パラメータ比較手段は、複数のポイントにそれぞれ属性情報を付与し、各仮代表ポイント間を結ぶ線分の距離を算出し、各線分の距離に対し、その線分の両端のポイントの属性情報に基づいて定められる重み付け係数を乗算することにより距離パラメータを算出することができる。
【００３０】
本発明の代表ポイント選択方法において、属性情報は、ポイントの配置された地域の特性に基づくものとすることができる。
【００３１】
この場合、複数のポイントが配置された場所によって地域特性に違いがあっても、そのような地域特性の違いを考慮して、適切に分散された代表ポイントを選択することができる。ここで、地域特性とは、代表ポイントを選択する目的に応じて適宜選択される。たとえば人口密度、ポイントの高度、障害物の有無等である。また、たとえばポイントが設備の配置位置である場合、属性情報は、その設備が周囲に及ぼす因子とすることができる。ここで、周囲に及ぼす因子は、代表ポイントを選択する目的に応じて適宜選択される。たとえばポイントが店舗の配置位置である場合の商圏、ポイントが無線通信の基地局等のアンテナである場合の電波の届く範囲等とすることができる。
【００３２】
本発明によれば、対象地域に含まれる複数のポイントから複数の代表ポイントを選択する方法であって、複数のポイントから複数の仮代表ポイントを任意に選択した後、仮代表ポイント以外の他のポイントから任意に選択した一のポイントを仮代表ポイントに加える第一のステップと、仮代表ポイントをそれぞれ結ぶ線分のうち最短の線分の両端のポイントのいずれか一方を仮代表ポイントから外す第二のステップと、を順次繰り返して実行し、次いで仮代表ポイントを代表ポイントとして確定することを特徴とする代表ポイント選択方法が提供される。
【００３３】
また、本発明によれば、コンピュータシステムにより、対象地域に含まれる複数のポイントから複数の代表ポイントを選択する方法であって、コンピュータシステムは、仮代表ポイント選択手段、および距離比較手段を備え、仮代表ポイント選択手段が、複数のポイントから複数の仮代表ポイントを任意に選択した後、仮代表ポイント選択手段が、仮代表ポイント以外の他のポイントから任意に選択した一のポイントを仮代表ポイントに加える第一のステップと、距離比較手段が、仮代表ポイントをそれぞれ結ぶ線分のうち最短の線分の両端のポイントのいずれか一方を仮代表ポイントから外す第二のステップと、を順次繰り返して実行し、次いで仮代表ポイントを代表ポイントとして確定することを特徴とする代表ポイント選択方法が提供される。
【００３４】
この代表ポイント選択方法において、第二のステップにおいて、仮代表ポイントをそれぞれ結ぶ線分の中で最短の線分の両端のポイントのうち、他の仮代表ポイントとの最短距離が短い方のポイントを仮代表ポイントから外すことができる。また、この代表ポイント選択方法において、第二のステップにおいて、仮代表ポイントをそれぞれ結ぶ線分の中で最短の線分の両端のポイントのうち、第一のステップで加えられたポイントからの距離が短い方のポイントを仮代表ポイントから外すことができる。
【００３５】
本発明の代表ポイント選択方法において、代表ポイント以外の他のポイントを代表ポイントのいずれかに帰属させるステップと、各代表ポイントに帰属するポイントの数またはポイントの配置状態を考慮して代表ポイントの中から一以上のポイントを削除し、代表ポイントを選別するステップと、をさらに含むことができる。
【００３６】
また、本発明の代表ポイント選択方法において、コンピュータシステムは、代表ポイント選別手段をさらに備えることができ、代表ポイント選別手段が、代表ポイント以外の他のポイントを代表ポイントのいずれかに帰属させるステップと、各代表ポイントに帰属するポイントの数またはポイントの配置状態を考慮して代表ポイントの中から一以上のポイントを削除し、代表ポイントを選別するステップと、をさらに含むことができる。
【００３７】
このようにすれば、適切に分散された代表ポイントの中から、他のポイントの配置に応じて目的に応じて好適な代表ポイントを選別することができ、所望の条件を満たす代表ポイントを選択することができる。
【００３８】
本発明の代表ポイント選択方法において、対象地域を複数のエリアに分割し、複数のポイントを各エリアに帰属させる際の起点として代表ポイントを選択することができる。
【００３９】
この方法は、適切に分散された代表ポイントを複数のエリアの起点として他のポイントを各エリアに帰属させるので、複数のポイントをブロック状に分割することができる。
【００４０】
本発明の代表ポイント選択方法において、対象地域における設備の配置位置として代表ポイントを選択することができる。
【００４１】
このようにすれば、複数の設備を適切に分散して配置することができる。これにより、各設備がカバーする領域が互いに重ならないように、複数の設備を適切に配置することができるので、効率よく対象領域全体をカバーすることができる。また、たとえば設備が店舗等のように互いに競合する関係にある場合、それぞれの設備が影響を及ぼす範囲が重ならないように配置することにより、互いに効果的に利益をあげることができる。
【００４２】
本発明によれば、複数のポイントを含む対象地域の中から複数の代表ポイントを選択するステップと、選択された代表ポイントを含むエリアを初期値として複数設定するステップと、各エリアに追加するポイントを、各エリアの代表点からの距離を考慮して選択する処理を繰り返して各エリアを拡張し、複数のポイントをいずれかのエリアに帰属させるステップと、を含むエリア分割方法であって、上述した代表ポイント選択方法のいずれかにより複数の代表ポイントを選択することを特徴とするエリア分割方法が提供される。
【００４３】
このようにすれば、適切に分散された代表ポイントの中から、他のポイントの配置に応じて適切に分散された代表ポイントを複数のエリアの起点として他のポイントを各エリアに帰属させるので、複数のポイントをブロック状に分割することができる。
【００４４】
本発明によれば、対象地域に含まれる複数の候補地点から、複数の設備の配置地点を選択する方法であって、上述した代表ポイント選択方法のいずれかにより複数の代表ポイントを選択し、選択された代表ポイントを複数の設備の配置地点として選択することを特徴とする配置地点の選択方法が提供される。
【００４５】
このようにすれば、複数の設備を適切に分散して配置することができる。これにより、各設備がカバーする領域が互いに重ならないように、複数の設備を適切に配置することができるので、効率よく対象領域全体をカバーすることができる。また、たとえば設備が店舗等のように互いに競合する関係にある場合、それぞれの設備が影響を及ぼす範囲が重ならないように配置することにより、互いに効果的に利益をあげることができる。
【００４６】
本発明によれば、コンピュータシステムにより、複数のポイントを含む対象地域を複数のエリアに分割し、それぞれのエリアにポイントを帰属させるエリア分割方法であって、コンピュータシステムは、代表ポイント選択手段、およびエリア分割手段を備え、代表ポイント選択手段が、上述した代表ポイント選択方法のいずれかにより選択された代表ポイントを選択した後、エリア分割手段が、代表ポイントを含むエリアを初期値として複数設定した後、各エリアに追加するポイントを、エリアの代表点からの距離を考慮して選択する処理を繰り返して各エリアを拡張し、複数のポイントをいずれかのエリアに帰属させることを特徴とするエリア分割方法が提供される。
【００４７】
本発明によれば、コンピュータシステムにより、対象地域に含まれる複数の候補地点から、複数の設備の配置地点を選択する方法であって、コンピュータシステムは、代表ポイント選択手段を備え、代表ポイント選択手段が、上述した代表ポイント選択方法のいずれかにより複数の代表ポイントを選択し、選択された代表ポイントを複数の設備の配置地点として選択することを特徴とする配置地点の選択方法が提供される。
【００４８】
従来、複数のポイントの中から複数の代表ポイントを選択する場合、手動で任意に行われていた。しかし、以上で説明した本発明においては、複数のポイントの中から複数の代表ポイントを一定の手順に従って自動的に選択することができる。これにより、複数のポイントの中から所望の条件を満たす複数の代表ポイントを勘や経験に頼ることなく客観的に選択することができる。
【００４９】
こうしたことから、たとえばエリア分割を例として説明すると、従来、エリア分割をする際に起点となる各エリアの代表ポイントを複数のポイントの中から選択するということすら想定されておらず、ましてやこれらの代表ポイントを一定の手順に従って自動的に自動的に選択するという技術については何ら検討されたことがなかった。本発明によれば、対象地域をエリア分割する際に、各エリアの起点となる代表ポイントを適切に選択することができるので、所望の形状のエリア分割を行うことができる。
【００５０】
本発明によれば、複数のポイントの中から代表ポイントを選択する方法であって、複数のポイントから、複数の仮代表ポイントを選択した後、複数のポイントのうち、仮代表ポイントと以外の他のポイントから、置換候補ポイントを任意に選択するステップと、仮代表ポイントをそれぞれ結ぶ線分の中で、最短である第一の線分の長さを算出するステップと、仮代表ポイントのうち、置換候補ポイントから一番目に近い位置にある第一の仮代表ポイントと置換候補ポイントとを結ぶ第二の線分の長さを算出するステップと、を含み、第一の線分および第二の線分の長さを比較する第一の検査を行うステップと、第一の検査において第二の線分が第一の線分よりも長い場合に、第一の線分の両端のポイントのいずれか一方を仮代表ポイントから外して、置換候補ポイントを新たな仮代表ポイントとして選択するステップと、第一の検査において、第二の線分が第一の線分よりも短い場合に、置換候補ポイントから二番目に近い位置にある第二の仮代表ポイントと置換候補ポイントとを結ぶ第三の線分の長さを算出するステップと、仮代表ポイントのうち、第一の仮代表ポイントから最も近い位置にある第三の仮代表ポイントと、第一の仮代表ポイントとを結ぶ第四の線分の長さを算出するステップと、を含み、第三の線分と第四の線分の長さとを比較する第二の検査を行うステップと、第二の検査において、第三の線分が第四の線分よりも長い場合に、第一の仮代表ポイントを仮代表ポイントから外して、置換候補ポイントを新たな仮代表ポイントとして選択するステップと、を順次繰り返して実行し、次いで仮代表ポイントを代表ポイントとして確定することを特徴とする代表ポイント選択方法が提供される。
【００５１】
【発明の実施の形態】
（第一の実施の形態）
本実施の形態において、無線通信網の基地局の候補地点を複数含む営業区域から基地局の配置地点を選択する例を説明する。
図１は、本発明の第一の実施の形態における基地局の配置地点を選択する手順を示すフローチャートである。まず、基地局の配置地点選択に必要な各種データの登録が行われる（Ｓ１）。ここでは、たとえばその営業区域の地図情報データ、基地局の候補地点情報データ、エリア情報データ等が登録される。つづいて、初期設定として、営業区域内に設定する基地局の配置地点数が設定される（Ｓ２）。その後、ステップ２で設定された配置地点数の基地局の配置地点が選択される（Ｓ３）。
【００５２】
図２は、本実施の形態における配置地点選択装置の構成を示すブロック図である。配置地点選択装置１０は、表示処理部１２と、初期設定部１４と、配置地点選択部１６と、地図情報記憶部２０と、候補地点情報記憶部２２と、エリア情報記憶部２４と、初期設定記憶部２５と、ロジック記憶部２６と、配置地点情報記憶部２８とを有する。
【００５３】
地図情報記憶部２０は、基地局を設置する営業区域の地図情報データを記憶する。候補地点情報記憶部２２は、候補地点情報データを記憶する。候補地点情報データは、候補地点の識別コード、候補地点の名称、候補地点の平面位置（緯度および経度、またはＸ座標およびＹ座標）、候補地点の高さ等を含む。エリア情報記憶部２４は、電波状態や人口分布等の営業区域内における地域特性をパラメータ化して記憶する。
【００５４】
表示処理部１２は、各種データを画面（不図示）上に表示する処理を行う。初期設定部１４は、基地局の配置地点を選択するために必要な初期設定を行う。初期設定部１４は、ユーザから、対象の営業区域に設置する基地局の配置地点数を受け付ける。初期設定記憶部２５は、初期設定情報を記憶する。
【００５５】
配置地点選択部１６は、営業区域内の複数の候補地点の中から、初期設定部１４で設定された配置地点数の基地局の配置地点を選択する。配置地点選択部１６は、複数の候補地点の中から仮の配置地点を選択する機能、置換対象となる地点を選択する機能、各ポイント間の距離を比較する機能を有する。ロジック記憶部２６は、配置地点選択部１６が配置地点を選択するのに必要なロジックを記憶する。配置地点情報記憶部２８は、配置地点選択部１６により選択された配置地点情報を記憶する。
【００５６】
図３は、本実施の形態において、配置地点選択部１６が基地局の配置地点を選択する手順を示すフローチャートである。配置地点選択部１６は、営業区域内の複数の候補地点の中から、初期設定部１４が受け付けた基地局の配置地点数の任意の候補地点を初期ポイントとして選択する（Ｓ１２）。配置地点選択部１６は、候補地点情報記憶部２２を参照して、リスト順に初期ポイントを選択していくことができる。配置地点選択部１６は、選択された初期ポイント間の最短距離Ｉ１を検出する（Ｓ１４）。次に、配置地点選択部１６は、候補地点情報記憶部２２のリストの次の候補地点を検査ポイントとして選択する（Ｓ１６）。配置地点選択部１６は、初期ポイントの中で、検査ポイントから最近隣のポイントと検査ポイントとの最短距離Ｉ２を算出する（Ｓ１８）。つづいて、配置地点選択部１６は、第一検査を行う（Ｓ２０）。第一検査において、配置地点選択部１６は、ステップ１４で検出した初期ポイント間の最短距離Ｉ１と、ステップ１８で算出した検査ポイントとの最短距離Ｉ２とを比較する（Ｓ２２）。検査ポイントとの最短距離Ｉ２が最短距離Ｉ１よりも大きい場合（Ｓ２２のＹｅｓ）、配置地点選択部１６は、検査ポイントを初期ポイントのいずれかと置換して新たな選択ポイントとする（Ｓ２４）。ここで置換対象となるのは、初期ポイント間の最短距離Ｉ１を与えるポイントのうち、検査ポイントからの距離が短い方のポイントである。
【００５７】
ステップ２２において、最短距離Ｉ２が最短距離Ｉ１以下の場合（Ｓ２２のＮｏ）、配置地点選択部１６は、検査ポイントから最近隣の初期ポイント以外の初期ポイントへの最短距離Ｉ３を算出する（Ｓ２６）。また、配置地点選択部１６は、最近隣の初期ポイントから他の初期ポイントへの最短距離Ｉ４を算出する（Ｓ２８）。つづいて、配置地点選択部１６は、第二検査を行う（Ｓ３０）。第二検査において、配置地点選択部１６は、ステップ２８で算出された最近隣の初期ポイントと他の初期ポイントとの最短距離Ｉ４とステップ２６で算出された最短距離Ｉ３とを比較する（Ｓ３２）。最短距離Ｉ３が大きい場合（Ｓ３２のＹｅｓ）、ステップ２４に進み、配置地点選択部１６は、検査ポイントを最近隣の初期ポイントと置換して新たな選択ポイントとする（Ｓ２４）。
【００５８】
ステップ３２において、最短距離Ｉ３が最近隣の初期ポイントと他の初期ポイントとの最短距離Ｉ４以下だった場合（Ｓ３２のＮｏ）、初期ポイントの置換は行われない。
【００５９】
以上の処理は、すべてのポイントについて順に所定回数、たとえばここでは１００回行われる。ステップ３４において、ｎが１００以下の場合（Ｓ３４のＮｏ）、ステップ１４に戻り、この段階での選択ポイント間の最短距離Ｉ１が算出される。配置地点選択部１６は、候補地点情報記憶部２２のリストの次の候補地点を検査ポイントとして選択し（Ｓ１６）、以下同様の処理を繰り返す。一方、ステップ３４において、ｎ＞１００の場合（Ｓ３４のＹｅｓ）、ポイントの選択処理は終了する。配置地点選択部１６は、この段階での選択ポイントを配置地点として選択する。
【００６０】
図４は、図３を参照して説明した配置地点の選択処理を具体的に説明する図である。ここでは、基地局の配置地点数を「３」とする。まず、図４（ａ）に示すように、初期ポイントとして候補地点ａ、候補地点ｂ、および候補地点ｃが選択される。配置地点選択部１６は、これらのポイント間の最短距離を検出する。ここでは、候補地点ａおよび候補地点ｂ間が最短距離Ｌ１となる。次に、候補地点情報記憶部２２におけるリストの次のポイントである候補地点ｄが検査ポイントとして選択される。配置地点選択部１６は、候補地点ｄから最近隣の候補地点を検出し、候補地点ｄと最近隣の候補地点との間の最短距離を算出する。ここでは、候補地点ｄおよび候補地点ｃ間が最短距離Ｌ２となる。配置地点選択部１６は、最短距離Ｌ１と最短距離Ｌ２とを比較する。ここで、最短距離Ｌ２＞最短距離Ｌ１となるので、配置地点選択部１６は、候補地点ｄを初期ポイントと置換し、新たな選択ポイントとする。ここで、候補地点ｄとの置換対象となるのは、最短距離Ｌ１を構成する候補地点ａまたは候補地点ｂのいずれかである。初期設定部１４は、候補地点ｄと置換する置換対象の候補地点を決定するために、図４（ｂ）に示すように、候補地点ｄと置換対象の候補地点ａおよび候補地点ｂとの距離Ｌ３およびＬ４をそれぞれ算出する。ここで、Ｌ４＞Ｌ３となるので、候補地点ａが候補地点ｄの置換対象となる。以上の処理により、図４（ｃ）に示すように、候補地点ｂ、候補地点ｃ、および候補地点ｄが新たな選択ポイントとなる。同様の処理を繰り返し、所定回数の処理が終了した時点における選択ポイントが配置地点として選択される。
【００６１】
図５は、配置地点の選択処理の他の例を説明する図である。ここでも、配置地点数を「３」とする。まず、図５（ａ）に示すように、初期ポイントとして候補地点ａ、候補地点ｂ、および候補地点ｃが選択される。配置地点選択部１６は、これらのポイント間の最短距離を検出する。ここでは、候補地点ａおよび候補地点ｂ間が最短距離Ｌ１となる。次に、候補地点情報記憶部２２におけるリストの次のポイントである候補地点ｅが検査ポイントとして選択される。配置地点選択部１６は、候補地点ｅから最近隣の候補地点を検出し、候補地点ｅと最近隣の候補地点との間の最短距離を算出する。ここでは、候補地点ｅおよび候補地点ｂ間が最短距離Ｌ２となる。配置地点選択部１６は、最短距離Ｌ１と最短距離Ｌ２とを比較する。ここで、最短距離Ｌ２＜最短距離Ｌ１となるので、配置地点選択部１６は、図５（ｂ）に示すように、第二検査を行う。配置地点選択部１６は、検査ポイントである候補地点ｅと候補地点ｂの次に候補地点ｅに近い候補地点ａとの間の最短距離Ｌ３を算出する。また、最近隣の候補地点ｂとこの候補地点ｂに最も近い候補地点ａとの間の最短距離Ｌ１を算出する。配置地点選択部１６は、最短距離Ｌ３と最短距離Ｌ１とを比較する。ここでは、最短距離Ｌ３＞最短距離Ｌ１となるので、候補地点ｅを候補地点ｂと置換する。以上の処理により、図５（ｃ）に示すように、候補地点ａ、候補地点ｃ、および候補地点ｅが新たな選択ポイントとなる。同様の処理を繰り返し、所定回数の処理が終了した時点における選択ポイントが配置地点として選択される。
【００６２】
以上の処理において、第一検査では、検査ポイントと既存の選択ポイント間の最短距離が選択ポイント間の最短距離よりも長い場合に選択ポイントの置換が行われるので、ポイント間の距離が短いポイントの組み合わせは排除されていく。また、置換対象の選択ポイントのうち、検査ポイントとの距離が短い方のポイントが置換されるので、新たに選択されたポイント間の距離をより一層長くすることができる。また、第一検査の条件を満たしていなくても、第二検査では、検査ポイントと既存の選択ポイントのいずれかとを置換した場合に、他の選択ポイントとの距離がより長くなる場合に選択ポイントの置換が行われる。したがって、ポイント間の距離がより長くなるようにポイントが置換されていく。また、このような処理を所定回数繰り返すため、ポイント間の距離が短いポイントの組み合わせが排除され、ポイント間の距離の平均値がより大きく、また距離の差がより小さくなるポイントが選択されることになる。本実施の形態における配置地点の選択方法によれば、この段階で選択されているポイントに対応する候補地点が基地局の配置地点として選択される。したがって、複数の候補地点の中から、候補地点間の距離の平均値が大きくまたそれぞれの距離の差が小さくなるような配置地点を選択することができる。
【００６３】
以上の処理により、複数の候補地点の中から、効率よく営業区域全体に電波を発信することができる基地局の配置地点を選択することができる。
【００６４】
次に、営業区域内において、地域特性が異なる場合の処理を説明する。ここでは、地域によって電波状態が異なる場合を例として説明する。
図６は、営業区域内における地域特性に違いがある場合に、基地局の配置地点を選択する手順を示すフローチャートである。配置地点の選択に先立ち、配置地点選択部１６は、エリア情報記憶部２４からエリア情報を、候補地点情報記憶部２２から候補地点情報を読み出す（Ｓ４０）。配置地点選択部１６は、エリア情報に基づき、エリア情報を候補地点情報に反映させて各候補地点への重み付け処理を行う（Ｓ４２）。配置地点選択部１６は、重み付けの結果を候補地点情報記憶部２２に記憶させる。その後、配置地点選択部１６は、図３を参照して説明したのと同様の手法で、複数の候補地点の中から基地局の配置地点を選択する（Ｓ４４）。このとき、配置地点選択部１６は、各候補地点への重み付け処理の結果を考慮してポイントを選択していく。
【００６５】
図７は、図６に示した手順を具体的に説明する図である。
この営業区域は、電波状態が良好な地域１、電波状態が中程度の地域２、電波状態が悪い地域３を含むものとする。たとえば、電波状態が悪い地域では、各基地局から電波が届く範囲が狭くなるので、電波状態が良好な地域に比べて基地局の設置間隔を狭くする必要がある。また、無線通信の利用者が多い地域では、利用者が少ない地域に比べて基地局を多く設置する必要がある。ここで、例として、地域１における基地局の電波範囲が３００ｍ、地域２における基地局の電波範囲が２００ｍ、地域３における基地局の電波範囲が１００ｍであるとする。これらの電波範囲に関する情報は、エリア情報記憶部２４にパラメータとして記憶されている。この場合、地域３を基準とすると、地域２においては地域３の２倍の間隔で基地局を設置すればよく、地域１においては地域３の３倍の間隔で基地局を設置すればよい。
【００６６】
上述したように、本実施の形態における配置地点の選択方法によれば、複数の候補地点の中から、互いの距離の平均値が大きくなるように複数の配置地点が選択される。したがって、互いの距離が短い候補地点がともに配置地点として選択される可能性は低く、互いの距離が長くなるほど、配置地点としてともに選択される可能性は高くなる。配置地点選択部１６は、電波状態の悪い地域でより多くの配置地点が選択されるように各候補地点に重み付け処理を行う。ここで、配置地点選択部１６は、候補地点情報記憶部２２およびエリア情報記憶部２４を参照して、地域１に含まれる候補地点には重み付け係数「１」を、地域２に含まれる候補地点には重み付け係数「２」を、地域３に含まれる候補地点には重み付け係数「３」を対応付ける。
【００６７】
配置地点選択部１６は、図３に示した配置地点の選択処理において、候補地点間の実距離にそれぞれの候補地点に対応付けられた重み付け係数を考慮した値を乗算して仮想距離を算出し、候補地点間の仮想距離の長さに応じて配置地点の選択を行っていく。
【００６８】
ここでも、基地局の配置地点数を「３」とする。まず、図７（ａ）に示すように、初期ポイントとして候補地点ａ、候補地点ｂ、および候補地点ｃが選択される。ここで、候補地点ａと候補地点ｃとの間の実距離はＬ１である。候補地点ａは地域３、候補地点ｃは地域１にそれぞれ含まれるので、候補地点ａと候補地点ｃとの間の仮想距離Ｌ’１＝（１＋３）／２×Ｌ１＝２Ｌ１となる。同様に、候補地点ａと候補地点ｂとの間の実距離はＬ３である。候補地点ａは地域３、候補地点ｂは地域１にそれぞれ含まれるので、候補地点ａと候補地点ｂとの間の仮想距離Ｌ’３＝（１＋３）／２×Ｌ３＝２Ｌ３となる。候補地点ｂと候補地点ｃとの間の実距離はＬ２である。候補地点ｂと候補地点ｃはともに地域１に含まれるので、候補地点ｂと候補地点ｃとの間の仮想距離Ｌ’２＝Ｌ２となる。配置地点選択部１６は、仮想距離Ｌ’１、Ｌ’２、およびＬ’３を比較し、最短距離を検出する。ここでは、候補地点ｂと候補地点ｃとの間の仮想距離Ｌ’２が最短距離となる。
【００６９】
次に、検査ポイントとして候補地点ｄが選択される。図７（ｂ）に示すように、配置地点選択部１６は、候補地点ｄから最近隣の候補地点を検出し、候補地点ｄと最近隣の候補地点との間の最短距離を算出する。ここで、候補地点ｄと候補地点ａとの間の実距離はＬ４である。候補地点ｄおよび候補地点ａはともに地域３に含まれるので、候補地点ｄと候補地点ａとの間の仮想距離Ｌ’４＝（３＋３）／２×Ｌ４＝３Ｌ４となる。候補地点ｄと候補地点ｃとの間の実距離はＬ５である。候補地点ｄは地域３に、候補地点ｃは地域１に含まれるので、候補地点ｄと候補地点ｃとの間の仮想距離距離Ｌ’５＝（１＋３）／２×Ｌ５＝２Ｌ５となる。同様に、候補地点ｄと候補地点ｂとの間の距離はＬ６である。候補地点ｄは地域３に、候補地点ｂは地域１に含まれるので、候補地点ｄと候補地点ｂとの間の仮想距離Ｌ’６＝（１＋３）／２×Ｌ６＝２Ｌ６となる。配置地点選択部１６は、仮想距離Ｌ’４、Ｌ’５、およびＬ’６を比較し、最短距離を検出する。ここでは、候補地点ｄと候補地点ａとの間の仮想距離Ｌ’４が最短距離となる。
【００７０】
配置地点選択部１６は、最短距離Ｌ’２と最短距離Ｌ’４とを比較する。ここで、最短距離Ｌ’４＞最短距離Ｌ’２となるので、配置地点選択部１６は、候補地点ｄを初期ポイントのいずれかと置換し、新たな選択ポイントとする。ここで、候補地点ｄの置換対象となるのは、最短距離Ｌ’２を構成する候補地点ｂまたは候補地点ｃのいずれかである。初期設定部１４は、候補地点ｄと置換する置換対象の候補地点を決定するために、候補地点ｄと置換対象の候補地点ｂとの間の仮想距離Ｌ’５と、候補地点ｄと置換対象の候補地点ｃとの間の仮想距離Ｌ’６を比較する。ここで、Ｌ’５＞Ｌ’６となるため、候補地点ｂが置換対象となる。以上の処理により、図７（ｃ）に示すように、候補地点ａ、候補地点ｃ、および候補地点ｄが選択ポイントとなる。
【００７１】
本実施の形態における配置地点選択方法によれば、複数の候補地点の中から、候補地点間の距離の平均値が大きくまたそれぞれの距離の差が小さくなるような配置地点が選択される。したがって、以上のように地域の電波状態に応じて重み付けを加えた仮想距離に基づき配置地点を選択すると、電波状態の悪い地域では、電波状態の良好な地域に比べて狭い間隔で配置地点を選択することができる。これにより、営業区域全体では、各地域の電波状態を反映させた適切な配置地点が選択される。
【００７２】
図８は、営業区域内における地域特性に違いがある場合に、基地局の配置地点を選択する手順の他の例を示すフローチャートである。ここでは、各候補地点に対応付けられた重み付け係数を考慮して変形地図を作成し、変形地図を用いて配置地点の選択を行う。まず、配置地点の選択に先立ち、配置地点選択部１６は、エリア情報記憶部２４からエリア情報を、候補地点情報記憶部２２から候補地点情報をそれぞれ読み出す（Ｓ５０）。配置地点選択部１６は、エリア情報および候補地点情報を参照して、各候補地点に対応付けられた重み付け係数を考慮して、それぞれの候補地点の位置を変形させた変形地図を作成する（Ｓ５２）。配置地点選択部１６は、変形地図上の候補地点の位置情報等を候補地点情報記憶部２２に記憶させる。その後、配置地点選択部１６は、図３を参照して説明したのと同様の手法で、複数の候補地点の中から基地局の配置地点を選択する（Ｓ５４）。このとき、配置地点選択部１６は、変形地図上の位置情報を用いてポイントを選択していく。
【００７３】
図９は、図８のステップ５２で説明した変形地図の作成方法を具体的に説明する図である。
この営業区域は、図７に示したのと同様、電波状態が良好な地域１、電波状態が中程度の地域２、電波状態が悪い地域３を含むものとする。ここで、たとえば地域１における基地局の電波範囲が３００ｍ、地域２における基地局の電波範囲が２００ｍ、地域３における基地局の電波範囲が１００ｍであるとする。これらの電波範囲に関する情報は、エリア情報記憶部２４にパラメータとして記憶されている。
【００７４】
この方法では、まず基準点Ｇを設定する。以下、図９（ａ）を参照して、基準点Ｇの設定方法の一例を説明する。まず、営業区域内の候補地点をｘｙ座標で表したときに、ｘの値が最小になる候補地点およびｘの値が最大になる候補地点をそれぞれ通るようにｙ軸に平行な直線ｍ１およびｍ２をひく。同様に、ｙの値が最小になる候補地点およびｙの値が最大になる候補地点をそれぞれ通るようにｘ軸に平行な直線ｎ１およびｎ２をひく。つづいて、直線ｍ１および直線ｎ２の交点と直線ｍ２および直線ｎ１の交点を通る直線ｇ１をひく。また、直線ｍ２および直線ｎ２の交点と直線ｍ１および直線ｎ１の交点を通る直線ｇ２をひく。次いで、直線ｇ１と直線ｇ２との交点を基準点Ｇとする。
【００７５】
次に、配置地点選択部１６は、基準点Ｇを中心として、各候補地点の位置座標にそれぞれに対応付けられた重み付け係数を乗算して候補地点の位置座標を変換する。ここで、配置地点選択部１６は、候補地点情報記憶部２２およびエリア情報記憶部２４を参照して、地域１に含まれる候補地点には重み付け係数「１」を、地域２に含まれる候補地点には重み付け係数「２」を、地域３に含まれる候補地点には重み付け係数「３」を対応付ける。たとえば、図９（ｂ）に示すように、候補地点ａは地域３に含まれるので、重み付け係数「３」が対応付けられる。配置地点選択部１６は、候補地点ａを、基準点Ｇと候補地点ａとを結ぶ直線上を基準点Ｇから遠ざかる方向に移動させ、基準点Ｇとの距離が候補地点ａとの実距離Ｌ１の３倍となる位置ａ’を候補地点ａの変換位置座標とする。同様に、候補地点ｂは地域２に含まれるので、重み付け係数「２」が対応付けられる。配置地点選択部１６は、候補地点ｂを、基準点Ｇと候補地点ｂとを結ぶ直線上を基準点Ｇから遠ざかる方向に移動させ、基準点Ｇとの距離が候補地点ｂとの実距離Ｌ２の２倍となる位置ｂ’を候補地点ｂの変換位置座標とする。
【００７６】
図１０は、配置地点選択部１６により作成された変形地図を模式的に示す図である。図１０（ａ）に示すように、各候補地点は、基準点Ｇと各候補地点をそれぞれ結ぶ放射線上で、基準点Ｇとの距離に重み付け係数を乗じた距離となる点に移動される。たとえば地域３に含まれる候補地点はそれぞれ基準点Ｇとの距離が実距離の３倍となるように変換され、地域２に含まれる候補地点はそれぞれ基準点Ｇとの距離が実距離の２倍となるように変換される。ここで、地域１に含まれる候補地点への重み付けは「１」であるので、地域１に含まれる候補地点の位置には変化がない。
【００７７】
図１０（ｂ）は、以上の処理により作成された変形地図を示す。配置地点選択部１６は、この変形地図を用いて図３に示したのと同様の処理を行い、配置地点を選択する。ここで配置地点として選択された候補地点の位置情報は、変換前の位置情報に対応づけられる。表示処理部１２は、選択された配置地点の変換前の位置情報に基づき、配置地点のマークを地図情報とともに画面上（不図示）に表示する。
【００７８】
図２３は、図８から図１０を参照して説明した変形処理を行う前のもとの図と変形処理を行った後の変形地図とを模式的に示す図である。図２３（ａ）がもとの図を示し、図２３（ｂ）が変形地図を示す。たとえば、図２３（ａ）において、地域１にはポイントＰ１、地域２にはポイントＰ２、地域３にはポイントＰ３が含まれる。これらのポイントは、図２３（ｂ）において、ポイントＰ１’、ポイントＰ２’、ポイントＰ３’に変換される。もとの図の地域１に含まれるポイントＰ１には、重み付け係数１が乗算されるので、ポイントＰ１と変形地図に含まれるポイントＰ１’の位置には変化がない。もとの図の地域２に含まれるポイントＰ２には、重み付け係数２が乗算されるので、変形地図におけるポイントＰ２は、もとの図のポイントＰ２に比べて、Ｇ−Ｐ２間の２倍の距離だけ基準点Ｇから遠ざかる方向に移動する。もとの図の地域３に含まれるポイントＰ３には、重み付け係数３が乗算されるので、変形地図におけるポイントＰ３は、もとの図のポイントＰ３に比べて、Ｇ−Ｐ３間の３倍の距離だけ基準点Ｇから遠ざかる方向に移動する。それぞれの地域に含まれるポイントについて同様に変形された結果、図２３（ｂ）に示すように、地域１ではポイント間の距離に変化がないが、地域２および地域３ではポイント間の距離がもとの図に比べて広くなる。
【００７９】
本実施の形態における配置地点選択方法によれば、複数の候補地点の中から、互いの距離が長くなるように配置地点が選択される。したがって、以上のように各候補地点の位置座標に地域の電波状態に応じた重み付け処理を行って作成した変形地図に基づき配置地点を選択すると、電波状態の悪い地域からより多くの配置地点を選択することができる。このようにして選択した配置地点をもとの地図に反映させると、電波状態の悪い地域では、電波状態の良好な地域に比べて狭い間隔で配置地点が選択されていることになる。これにより、営業区域全体では、各地域の電波状態を反映させた適切な配置地点が選択される。また、ここでは、所定の基準点を設定し、その基準点から各ポイントまでの距離に対して重み付け係数を乗算することにより、近似的に変形地図を作成することができる。このような処理により、より少ないデータ量で重み付け処理を行うことができ、迅速に代表ポイントを選択することができる。なお、ここで説明した基準点の設定方法は一例であって、種々の方法で設定することができる。
【００８０】
（第二の実施の形態）
以下、複数の店舗が設置された営業区域をエリア分割する場合に、各エリアの起点となるシードを設定する方法を例に挙げて本発明の第二の実施の形態を説明する。ここでは、分割対象の営業区域に含まれる店舗への商品配送処理を複数の作業員で分担して行う場合に、全体の作業効率が上昇し、かつ各作業員の労力が均等となるようにエリア分割を行う。ここで、店舗は、たとえはコンビニエンスストア等のチェーン店や自動販売機等である。また、各作業員は、毎日在庫センターなどの拠点を出発点として自己の担当エリア内の店舗に商品を配送し、１日の終了時にはまた拠点に戻るという巡回作業を行うものとする。したがって、全体の作業効率を上昇させるためには、各作業員の拠点−店舗間および店舗−店舗間の距離がそれぞれなるべく短くなるようにしてエリア分割を行うのが好ましい。
【００８１】
図１１は、本実施の形態におけるエリア分割処理の手順を示すフローチャートである。まず、エリア分割の処理に必要な各種データの登録が行われる（Ｓ９０）。つづいて、エリア分割に必要なパラメータの設定が行われる（Ｓ９１）。次いで、営業区域のエリア数の設定（Ｓ９２）や各エリアにおける起点となるシードの設定（Ｓ９３）等の初期設定が行われる。つづいて、シードを起点としたエリア分割が行われる（Ｓ９４）。次いで、エリア分割の結果が表示され、評価および調整が行われる（Ｓ９５）。
【００８２】
図１２は、本実施の形態におけるエリア分割処理を行うエリアシュミレータ装置の構成を示すブロック図である。エリアシュミレータ装置１００は、表示処理部１０８と、パラメータ設定部１１０と、初期設定部１１４と、候補選択処理部１１６と、分割制御部１１８と、地図情報記憶部Ｔ１と、拠点情報記憶部Ｔ２と、店舗情報記憶部Ｔ３と、パラメータ記憶部Ｔ４と、初期設定記憶部Ｔ５と、エリア分割情報記憶部Ｔ６と、ロジック記憶部Ｔ７とを有する。
【００８３】
地図情報記憶部Ｔ１は、分割の対象となる営業区域の地図情報データを記憶する。拠点情報記憶部Ｔ２は、拠点情報データを記憶する。拠点情報データは、拠点の識別コード、拠点の名称、拠点の位置（緯度および経度、またはＸ座標およびＹ座標）等を含む。ここで、拠点とは、たとえばその営業区域における在庫センターである。
【００８４】
店舗情報記憶部Ｔ３は、店舗情報データを記憶する。店舗情報データは、拠点の識別コード、店舗の識別コード、店舗の名称、店舗の位置（緯度および経度、またはＸ座標およびＹ座標）、月売上（円）、１回あたりの作業時間（分）、月配送回数、拠点からの移動速度（ｋｍ／時間）、店舗間移動速度（ｋｍ／時間）等を含む。
【００８５】
表示処理部１０８は、各種データを画面（不図示）上に表示する処理を行う。パラメータ設定部１１０は、営業区域をエリア分割するために必要なパラメータの設定を受け付ける。パラメータは、各作業員の１日の標準作業時間、各店舗での標準作業時間、店舗間の標準移動速度、拠点と店舗間の標準移動速度、距離倍率、店舗取得制限距離等を含む。パラメータ記憶部Ｔ４は、これらのパラメータを記憶する。
【００８６】
初期設定部１１４は、営業区域をエリア分割するために必要な初期設定を行う。初期設定部１１４は、ユーザからエリア数（シード数）の設定等を受け付ける。たとえば分割の対象となる営業区域を４つのエリアに分割する場合、４つのシードが設定される。初期設定部１１４は、複数の店舗の中からシードとなる店舗を選択する。初期設定記憶部Ｔ５は、これらの初期設定を記憶する。
【００８７】
候補選択処理部１１６および分割制御部１１８は、初期設定部１１４にて設定された各シードを起点として、分割対象の営業区域のエリア分割を行う。候補選択処理部１１６は、各シードについて、それぞれそのシードから近い位置にある店舗をそのシードと同じエリアに分類する候補として選択する。分割制御部１１８は、複数のエリアのうち、そのエリアにおける統計量が最も小さいエリアが候補の店舗をそのエリア内に取り込むように処理する。分割制御部１１８は、算出されたエリア別の統計量が全エリアにおいてほぼ均等となるように、複数の店舗を順次各エリアに帰属させていく。ここで、統計量とは、たとえば各エリアのコース数（１日毎の作業量）、各エリアに含まれる店舗の数、店舗あたりの平均作業時間、店舗あたりの平均月配送回数、店舗あたりの拠点からの距離平均、店舗間距離平均、コースあたりの店舗数、総売上、店舗あたりの売上平均等、各エリアに含まれる店舗の特性を示す情報である。
【００８８】
ロジック記憶部Ｔ７は、初期設定部１１４、候補選択処理部１１６および分割制御部１１８において、それぞれ、シードの選択、分割処理、統計量の算出等に必要なロジックを記憶する。
【００８９】
候補選択処理部１１６および分割制御部１１８による自動エリア分割処理が終了すると、その結果はエリア分割情報記憶部Ｔ６に記憶される。また、表示処理部１０８は、エリア分割状態を画面（不図示）に表示する。これにより、ユーザはエリア分割状態を把握することができる。パラメータ設定部１１０は再度のパラメータの設定を受け付ける。初期設定部１１４も、再度の初期設定を行う。
【００９０】
本実施の形態においても、第一の実施の形態において、図３を参照して説明したのと同様の手順でシードとなる店舗を選択する。初期設定部１１４は、営業区域内の複数の店舗の中から、ユーザから受け付けたエリア数（シード数）の任意の店舗を初期ポイントとして選択する（Ｓ１２）。初期設定部１１４は、店舗情報記憶部Ｔ３を参照して、リスト順に初期ポイントを選択していくことができる。初期設定部１１４は、選択された初期ポイント間の最短距離Ｉ１を検出する（Ｓ１４）。次に、初期設定部１１４は、店舗情報記憶部Ｔ３のリストの次の店舗を検査ポイントとして選択する（Ｓ１６）。初期設定部１１４は、初期ポイントの中で、検査ポイントから最近隣のポイントと検査ポイントとの最短距離Ｉ２を算出する（Ｓ１８）。つづいて、初期設定部１１４は、第一検査を行う（Ｓ２０）。第一検査において、初期設定部１１４は、ステップ１４で検出した初期ポイント間の最短距離Ｉ１と、ステップ１８で算出した検査ポイントとの最短距離Ｉ２とを比較する（Ｓ２２）。最短距離Ｉ２が最短距離Ｉ１よりも大きい場合（Ｓ２２のＹｅｓ）、初期設定部１１４は、検査ポイントを初期ポイントのいずれかと置換して新たな選択ポイントとする（Ｓ２４）。ここで置換対象となるのは、初期ポイント間の最短距離Ｉ１を与えるポイントのうち、検査ポイントからの距離が短い方のポイントである。
【００９１】
ステップ２２において、最短距離Ｉ２が最短距離Ｉ１以下の場合（Ｓ２２のＮｏ）、初期設定部１１４は、検査ポイントから最近隣の初期ポイント以外の初期ポイントへの最短距離Ｉ３を算出する（Ｓ２６）。また、初期設定部１１４は、最近隣の初期ポイントから他の初期ポイントへの最短距離Ｉ４を算出する（Ｓ２８）。つづいて、初期設定部１１４は、第二検査を行う（Ｓ３０）。第二検査において、初期設定部１１４は、最近隣ポイントと他のポイントとの最短距離Ｉ４とステップ２６で算出された最短距離Ｉ３とを比較する（Ｓ３２）。最短距離Ｉ３が大きい場合（Ｓ３２のＹｅｓ）、ステップ２４に進み、初期設定部１１４は、検査ポイントを最近隣のシードと置換して新たな選択ポイントとする（Ｓ２４）。
【００９２】
ステップ３２において、最短距離Ｉ３が最近隣ポイントと他のポイントとの最短距離Ｉ４以下だった場合（Ｓ３２のＮｏ）、ポイントの置換は行われない。
【００９３】
以上の処理は、すべてのポイントについて順に所定回数、たとえばここでは１００回行われる。ステップ３４において、ｎが１００以下の場合（Ｓ３４のＮｏ）、ステップ１４に戻り、新たに選択されたポイント間の最短距離が選択される。初期設定部１１４は、店舗情報記憶部Ｔ３のリストの次の店舗を検査ポイントとして選択し（Ｓ１６）、以下同様の処理を繰り返す。一方、ステップ３４において、ｎ＞１００の場合（Ｓ３４のＹｅｓ）、ポイントの選択処理は終了し、ここで選択ポイントとされていたポイントがシードとして設定される。
【００９４】
以上の処理において、第一検査では、検査ポイントと既存の選択ポイント間の最短距離が選択ポイント間の最短距離よりも長い場合にポイントの置換が行われるので、ポイント間の距離が短いようなポイントの組み合わせは排除されていく。また、置換対象の選択ポイントのうち、検査ポイントとの距離が短い方のポイントが置換されるので、新たに選択されたポイント間の距離をより一層長くすることができる。また、第一検査の条件を満たしていなくても、第二検査では、検査ポイントと既存の選択ポイントのいずれかとを置換した場合に、他の選択ポイントとの距離がより長くなる場合にポイントの置換が行われる。したがって、ポイント間の距離が長くなるようにポイントが置換されていく。そのため、複数の店舗の中から、互いの距離が均等に長くなるような店舗をシードとして選択することができる。
【００９５】
図１３は、エリア分割処理の手順を示すフローチャートである。
まず、上述したように初期設定部１１４によりシードが設定される（Ｓ１０２）。候補選択処理部１１６は、各シードについて、同じエリアに帰属させる店舗の候補を選択する（Ｓ１０４）。
【００９６】
ここで、図１４を参照して、ステップ１０４の店舗の候補を選択する手順を説明する。各エリアについて同様の処理を行うので、一のエリアについてのみ説明する。
【００９７】
まず、まだいずれのエリアにも属していない無所属の店舗の中から、シードから最短の位置にある店舗を候補として検出する（Ｓ１３２）。つづいて、そのエリアに既に取得されている店舗のうち、検出された店舗の候補から最近隣の店舗と、検出された店舗との最短距離を算出する（Ｓ１３４）。ここで算出された最短距離と、予め設定された店舗取得制限距離とを比較し（Ｓ１３６）、最短距離が制限内の場合（Ｓ１３６のＹｅｓ）、その候補をそのエリアの候補として決定する（Ｓ１３８）。一方、ステップ１３６において、算出された最短距離が制限内でない場合（Ｓ１３６のＮｏ）、無所属の店舗が他にあるか否かを判断する（Ｓ１４０）。無所属の店舗が他にある場合（Ｓ１４０のＹｅｓ）、ステップ１３２に戻り、シードから次に最短の位置にある店舗を候補として検出する。以下、同様の処理を繰り返す。
【００９８】
ステップ１４０において、無所属の店舗が他にない場合（Ｓ１４０のＮｏ）、他のエリアに既に取得されている取得済の店舗の中から、シードから最短の店舗を候補として検出する（Ｓ１４２）。つづいて、そのエリアに既に取得されている店舗のうち、検出された店舗の候補から最短の位置にある店舗と、検出された店舗との距離を算出する（Ｓ１４４）。ここで算出された最短距離と、予め設定された店舗取得制限距離とを比較し（Ｓ１４６）、最短距離が制限内の場合（Ｓ１４６のＹｅｓ）、その候補をそのエリアの候補として決定する（Ｓ１３８）。一方、ステップ１４６において、算出された最短距離が制限内でない場合（Ｓ１４６のＮｏ）、取得済の店舗の中で奪取可能なものが他にあるか否かを判断する（Ｓ１４８）。奪取可能なものがある場合（Ｓ１４８のＹｅｓ）、ステップ１４２に戻り、シードから次に最短の位置にある店舗を候補として検出する。以下、同様の処理を繰り返す。なお、ステップ１４８において、奪取可能な店舗がない場合（Ｓ１３８のＮｏ）、このエリアについての候補の選択処理を終了する。
【００９９】
図１３に戻り、ステップ１０４で候補が選択されたか否かが判断される（Ｓ１０６）。ステップ１０４で候補が選択されている場合（Ｓ１０６のＹｅｓ）、分割制御部１１８は候補の店舗を含めたそのエリアの統計量を算出する（Ｓ１０８）。統計量としてはたとえば合計コース数を挙げることができる。合計コース数の算出方法については後述する。
【０１００】
つづいて、分割制御部１１８は、エリアの統計量が最小となるエリアを検出する（Ｓ１１０）。分割制御部１１８により、統計量が最小であることが検出された場合（Ｓ１１０のＹｅｓ）、そのエリアは候補の店舗を取得する（Ｓ１１２）。つづいて、営業区域内に無所属の店舗があるか否か、またはステップ１１２の候補取得処理が所定回数、たとえば１００回行われたか否かが判断される（Ｓ１１４）。営業区域内に無所属の店舗があるか、またはステップ１１２の候補取得処理の回数が１００回以下の場合（Ｓ１１４のＮｏ）、ステップ１０４に戻り、次の候補を選択する。ステップ１１４において、無所属の店舗がないか、またはステップ１１２の候補取得処理の回数が１００を超えた場合（Ｓ１１４のＹｅｓ）、エリア分割処理は終了する。
【０１０１】
ステップ１１０において、統計量が最小でないことが検出された場合（Ｓ１１０のＮｏ）、ステップ１１６に進み、他のエリアにより候補が取得されるまで待機する（Ｓ１１６のＮｏ）。ステップ１１６において、他のエリアにより候補が取得された場合（Ｓ１１６のＹｅｓ）、自己のエリアで既に取得していた店舗が他のエリアに奪取されたか否かを検出する（Ｓ１１８）。奪取されなかった場合（Ｓ１１８のＮｏ）、このエリアにおける既得の店舗および候補に変動がないということであるので、ステップ１１０に戻り、再び統計量が最小となるか否かが判断される（Ｓ１１０）。
【０１０２】
ステップ１１８において、自己のエリアで既に取得していた店舗が他のエリアに奪取された場合（Ｓ１１８のＹｅｓ）、このエリアにおける既得の店舗に変動があることを意味する。したがって、新たな候補を選択する必要があるため、ステップ１１４に進み、営業区域内に無所属の店舗があるか否か等が判断され、同様の処理が行われる。
【０１０３】
一方、ステップ１１８において、候補の修正が必要ない場合（Ｓ１１８のＮｏ）、ステップ１１０に戻り、他のエリアとの関係で統計量が最小になるまで同様の処理を繰り返す。
【０１０４】
一方、ステップ１０４で候補が選択されなかった場合（Ｓ１０６のＮｏ）、ステップ１２０に進み、他のエリアにより候補が取得されるまで待機する（Ｓ１２０のＮｏ）。ステップ１２０において、他のエリアにより候補が取得された場合（Ｓ１２０のＹｅｓ）、自己のエリアで既に取得していた店舗が他のエリアに奪取されたか否かを検出する（Ｓ１２２）。自己のエリアで既に取得していた店舗が他のエリアに奪取された場合（Ｓ１２２のＹｅｓ）、このエリアにおける既得の店舗に変動があることを意味する。したがって、新たな候補を選択する必要があるため、ステップ１１４に進み、営業区域内に無所属の店舗があるか否かが判断され、同様の処理が行われる。
【０１０５】
一方ステップ１２２において、自己のエリアで既に取得していた店舗が他のエリアに奪取されなかった場合（Ｓ１２２のＮｏ）、ステップ１２４に進み、営業区域内に無所属の店舗があるか否か、またはステップ１１２の候補取得処理が所定回数、たとえば１００回行われたか否かが判断される。ステップ１２４において、営業区域内に無所属の店舗がないと判断された場合（Ｓ１２４のＮｏ）、エリア分割処理は終了する。また、ステップ１２４において、営業区域内に無所属の店舗があるか、またはステップ１１２の候補取得処理の回数が１００回以下の場合（Ｓ１２４のＮｏ）、ステップ１２０に戻り、他のエリアにより候補が取得されるまで待機する（Ｓ１２０）。ステップ１２４において、無所属の店舗がないか、またはステップ１１２の候補取得処理の回数が１００を超えた場合（Ｓ１２４のＹｅｓ）、エリア分割処理は終了する。
【０１０６】
なお、以上の処理において、他のエリアの候補として選択されている店舗については無所属として扱い、複数のエリアの候補の店舗が重複する場合、取得の優先順位の高いエリアがその店舗を取得するものとする。
【０１０７】
図１５は、図１３および図１４に示したエリア分割処理の一例を説明する図である。ここでは、各エリアにおける合計コース数が均等になるように、エリア分割が行われる。図１５（ａ）に示すように、この営業区域には、複数の店舗が設置されている。ここで、エリア数を４とし、店舗ａ、ｂ、ｃ、ｄがそれぞれエリアＡ、Ｂ、Ｃ、およびＤのシードとして設定されたものとする。図１５（ｂ）に示すように、候補選択処理部１１６は、各シード店舗ａ、ｂ、ｃ、ｄと同じエリアに帰属させる店舗の候補を選択していく。候補選択処理部１１６は、各シード店舗ａ、ｂ、ｃ、ｄから最も近い位置にある店舗を順次各エリアＡ、Ｂ、Ｃ、およびＤの候補として選択する。分割制御部１１８は、後述する算定方法に従って、各エリアにおける合計コース数を逐次算出する。分割制御部１１８は、合計コース数が最小となるエリアから候補を取得させ、あるエリアが候補を取得する毎に、合計コース数が最小となるエリアを検出して、候補を取得させる処理を繰り返す。
【０１０８】
このようにして順次店舗を選択させていくと、図１５（ｃ）に示すように、複数の店舗が徐々に各エリアに所属するようになる。表示処理部１０８は、異なるエリアに所属する店舗が異なるマークや異なる色で表示されるように処理を行う。ここで、エリアＣにおける候補は店舗ｅである。候補選択処理部１１６は、エリアＣに既に取得されている店舗のうち、店舗ｅから最も近い位置にある店舗ｆと店舗ｅとの距離を算出し、この距離と予め設定された店舗取得制限距離とを比較する。ここで、算出された距離は制限距離より大きいものとする。この場合、候補として店舗ｅを選択することはできない。候補選択処理部１１６は、この営業区域内の店舗のうち、いずれのエリアにも取得されていない他の店舗について順次シード店舗ｃからの距離が近い順に候補を検出していく。その結果、いずれの店舗も店舗取得制限距離より大きかった場合、候補選択処理部１１６は、既に他のエリアに取得されている店舗の中から候補を検出する。そこで、候補選択処理部１１６は、他のエリアＤに既に取得されている店舗ｇを候補として検出する。候補選択処理部１１６は、エリアＣに既に取得されている店舗のうち、店舗ｇから最も近い位置にある店舗ｆと店舗ｇとの距離を算出する。ここで、算出された距離は制限距離より小さいものとする。この場合、候補選択処理部１１６は、店舗ｇをエリアＣの候補として選択する。なお、直前の処理で他のエリアに奪取された店舗については、たとえばフラグを立てるなどして再奪取が行われないようにしておく。
【０１０９】
本実施の形態におけるエリア分割処理によれば、適切に配置されたシード店舗を起点として、各シード店舗からの位置が近い店舗が次の候補として選択されていくので、各エリアをブロック状に形成していくことができる。また、既にそのエリアに帰属している他の店舗の中で、最短のものからの距離が制限距離を超える場合は候補として取得しないので、営業区域に含まれる複数の店舗を店舗の統計量を考慮しつつ複数のグループに分割するときに、これらの店舗が領域間でまたがることなく、エリアに分割することができる。そのため、グループ分けの状態が把握しやすく、作業員に公平感を持たせることができる。
【０１１０】
本実施の形態におけるエリアシュミレータ装置１００によれば、合計コース数等の統計量が最小となるエリアから順に店舗を取得していくので、すべてのエリアにおける統計量を均等にすることができる。また、各エリアにおいては、店舗間の距離が短くなるように候補の店舗が選択されるので、各エリアにおける移動時間を低減することができ、全エリアにおける移動時間も低く抑えることができる。これにより、営業区域における作業効率を高めることができる。
【０１１１】
図１６は、各分割エリアにおける合計コース数の算出処理の手順を示すフローチャートである。各エリアについて同様の処理を行うので、ここでは一つのエリアについてのみ説明する。
【０１１２】
まず、拠点からそのエリア内で既に取得されている店舗および候補の店舗への平均移動時間Ｍ１を算出する（Ｓ１６０）。拠点から各店舗への合計距離を求めた後、拠点−店舗間移動速度から合計移動時間を求めることができる。この合計移動時間をそのエリア内の全店舗数で除すことによりＭ１が求められる。
【０１１３】
つづいて、店舗間の平均移動時間Ｍ２を算出する（Ｓ１６２）。平均移動時間Ｍ２は、（ｉ）各店舗から直近ｎ個の店舗への合計距離を算出した後、店舗間移動速度から合計移動時間を求める。（ｉｉ）この合計移動時間をｎで除すことにより、各店舗から他の店舗への平均移動時間ｍ１〜ｍｎを得る。（ｉｉｉ）ｍ１〜ｍｎを合計し、そのエリア内の全店舗数で除す、ことにより求められる。ここで、ｎが小さいときはその全店舗数をｎとすることができる。
【０１１４】
次いで、１日で作業可能な店舗数Ｎ１を算出する（Ｓ１６４）。１日で作業可能な店舗数Ｎ１は、（ｉ）１日の合計作業時間Ｔｚ＝Ｍ１×２＋Ｍ２（Ｎ１−１）＋Ｔ×Ｎ１（Ｔは１店舗当たりの平均作業時間）を求め、（ｉｉ）Ｎ１＝（Ｔｚ−Ｍ１×２＋Ｍ２）／（Ｍ２＋Ｔ）から得られる。
【０１１５】
一方、１日あたりの処理が必要な店舗数Ｎ２を算出する（Ｓ１６６）。１日あたりの処理が必要な店舗数Ｎ２は、（ｉ）各店舗毎に月ごとの配送回数を算出して合計することにより、月ごとの配送回数Ｗを算出する。（ｉｉ）各作業員の１月の労働日数を４週間×５日とすると、Ｎ２＝Ｗ／２０から得られる。
【０１１６】
その後、各エリアにおけるコース数＝Ｎ２／Ｎ１が求められる。（Ｓ１６８）
【０１１７】
以上の処理によれば、１日で作業可能な店舗数Ｎ１を算出する際に、拠点から各エリアの店舗までの移動時間をも考慮しているので、各エリアを拠点からの距離がほぼ均等となるように分割することができる。また、コース数は、各エリアにおける店舗間の距離をも考慮して算出されるので、各エリアにおける移動距離が均等となるように営業区域を分割することができる。
【０１１８】
図１７〜図２０は、パラメータの設定および初期設定を行うための画面を示す。図１７は、分割対象の拠点を選択する画面を示す。ここでは、分割対象の拠点として「東京２」が選択されている。
【０１１９】
図１８は、分割のための基礎条件の設定画面を示す。この営業区域において、各作業員の作業時間（オペ時間）、各店舗毎の作業時間、拠点−店舗間の移動速度、店舗−店舗間の移動速度、距離倍率、店舗取得制限距離を設定する。ここでは、各作業員の作業時間が「７時間３０分」、店舗毎の作業時間が「２０分」、拠点−店舗間の移動速度が「５０Ｋｍ／ｈ」、店舗−店舗間の移動速度が「５０Ｋｍ／ｈ」、距離倍率が「１」、店舗取得制限距離が「１０Ｋｍ」と設定されている。これらのパラメータは、図１６を参照して説明した各エリアにおけるコース数を算出する際に用いられる。その際、たとえば距離倍率が「２」と設定されていれば、図１６のステップ１６０およびステップ１６２の処理における拠点から各店舗への合計距離および各店舗から直近ｎ個の店舗への合計距離を２倍としてＭ１およびＭ２が算出される。各エリアのコース数は、拠点−店舗間、店舗−店舗間の移動距離から算出される移動時間と、各店舗における作業時間とから算出されるが、距離倍率を適宜設定することにより、移動時間にウェイトをかけることができる。本実施の形態において、コース数の算出には、拠点−店舗間および店舗−店舗間の直線距離が用いられている。しかし、実際に拠点−店舗間および店舗−店舗間を移動する場合には、曲がりくねった道を通ることや複雑に入り組んだ道を通ることが多い。したがって、営業区域毎の地域特性として所定の距離倍率を設定することにより、実際の移動距離をコース数に反映させることができる。
【０１２０】
また、店舗取得制限距離が「１０Ｋｍ」と設定されていれば、図１４のステップ１３６およびステップ１４６において、既にそのエリアに取得されている店舗のいずれかから１０Ｋｍを超える距離にある店舗はそのエリアに取得されないようにされる。したがって、各エリアにおける店舗間の最長距離を１０Ｋｍ以下とすることができ、営業区域を複数のエリアのブロックに分割することができる。店舗取得制限距離は、分割対象の営業区域の大きさに応じて適宜設定することができる。
【０１２１】
図１９は、エリア数の入力画面を示す。ここで、ユーザは分割対象の拠点配下におけるシード数（エリア数）を入力する。ここでは、シードの数が「６」となるように設定されている。
【０１２２】
次に、図２０に示すように、ウェイトの設定画面が表示される。たとえばエリアが１〜６まである場合、いずれかのエリアのコース数にウェイトをかけることができる。ここで設定されたウェイトは、各エリアにおいて統計量を算出する際に用いられる。たとえば、ここではエリア「４」にウェイト「２」が設定されている。したがって、分割制御部１１８は、図１６に示した合計コース数の算出処理において、エリア「４」で算出されたコース数を２倍したものを他のエリアのコース数と比較する。このようにすれば、最終的にエリア４のコース数は他のエリアの約半分に設定されることになる。たとえば、パートタイムの作業員をエリア４の担当者に割り当てるような場合にこのようなウェイト設定を行うことができる。
【０１２３】
以上のように、本実施の形態におけるエリア分割処理によれば、各エリアにおいて、店舗間の距離が短くなるように順次店舗が取り込まれていくので、最終的に、エリア間の距離が短い店舗が各エリアに分類されることになる。したがって、一つの営業区域をブロック単位のエリアに分割することができるとともに、各エリア内における店舗間の移動距離等を低減することができるので、店舗の巡回作業の効率を高めることができる。また、各エリアに含まれる複数の店舗の統計量が均等になるように各エリアに店舗が取り込まれていくので、作業員に公平感を持たせることができる。さらに、これらの結果は地図情報とともにマッピングされるので、担当者が客観的に公平感を認識することができる。
【０１２４】
（第三の実施の形態）
本実施の形態においては、第二の実施の形態とは異なる方法でシード設定処理を行う。ここでは、まず、実際に必要とされるシード数よりも多い数のシードが選択され、そのシードの中から所定の条件を満たすシードが最終的にシードとして選択される。
【０１２５】
図２１は、本実施の形態におけるシード設定処理の手順を示すフローチャートである。初期設定部１１４は、シード候補数および選択条件の設定を受け付ける（Ｓ２００）。ここで選択条件とは、シード候補数から最終的にいくつのシードをそのような条件で選択するか等である。
【０１２６】
初期設定部１１４は、図３に示したのと同様の手順で、シード候補数として設定された数のシード候補を設定する（Ｓ２０２）。つづいて、初期設定部１１４は、営業区域内の店舗を、ステップ２０２で設定されたシード候補のいずれかに帰属させるグループ分割を行う（Ｓ２０４）。
【０１２７】
グループ分割としては、営業区域内の店舗を、ステップ２０２で設定されたシード候補のうちそれぞれ最も近い位置にあるシード候補に帰属させることができる。また、グループ分割の他の例としては、候補選択処理部１１６および分割制御部１１８に、ステップ２０２で設定されたシード候補を起点として、図１３および図１４に示したのと同様の手順で、予備的なエリア分割を行わせることもできる。
【０１２８】
その後、初期設定部１１４は、グループ分割の結果、各シード候補に分割された店舗の情報を考慮して、選択条件に基づき、いくかのシード候補をシードとして選択する（Ｓ２０６）。
【０１２９】
以上の処理により、実際にエリア分割を行うためのシードが設定され、図１３および図１４に示したのと同様の手順でエリア分割が行われる（Ｓ２０８）。
【０１３０】
図２２は、本実施の形態におけるシード候補数および選択条件の設定画面を示す図である。ここでは、シード候補として「６」が入力されている。また、選択条件としては、「分割結果から、店舗数の多いグループより、いくつをシード候補として選択しますか」という条件と、「分割結果から、店舗数の少ないグループより、いくつをシード候補として選択しますか」という条件が記載されている。ここで、「分割結果から、店舗数の少ないグループより、いくつをシード候補として選択しますか」という条件に対して「３」が入力されている。
【０１３１】
このように入力した場合、まずシード候補として６個の店舗が選択され、他の店舗は、これらの６個の店舗のいずれかに帰属されてグループ分割が行われる。つづいて、各グループにおける店舗の数が検出され、６つのグループのうち、店舗の数が少ない順から３つのグループが選択され、そのグループにおけるシード候補が最終的なシードとして選択される。
【０１３２】
本実施の形態におけるエリア分割処理によれば、グループ分割の結果、各グループに属する店舗の数や配置状態を考慮して所望のシードを選別することができる。そのため、店舗が密集した領域にシードが設定されたり、他の店舗から極端に離れた位置にシードが設定されたりしても、それらを外すようにシードを選択することができる。これにより、複数のエリアにおけるコース数を均等にするとともに、各エリアに含まれる店舗の数も近くなるようにエリア分割をすることができる。そのため、各エリアを担当する作業員の不公平感を低減することができる。
【０１３３】
以上、本発明を実施の形態をもとに説明した。実施の形態は例示であり、それらの各構成要素や各処理プロセスの組み合わせにいろいろな変形例が可能なこと、またそうした変形例も本発明の範囲にあることは当業者に理解されるところである。以下、そのような変形例を説明する。
【０１３４】
第一の実施の形態で説明した配置地点の選択方法は、ある地域に既に複数の設備が配置されている場合に、既存の設備からいくつかの設備を残して設備削減を行う場合に、残すべき設備を選択するのに用いることもできる。また、この配置地点の選択方法は、定点に固定して設置された設備に限られず、移動設備の配置地点を選択するのに用いることもできる。
【０１３５】
また、第一の実施の形態において、図６〜図１０を参照して地域特性に違いがある場合の処理を説明したが、複数の候補地点それぞれの特性が異なる場合にも、同様の重み付け処理を行うことができる。たとえば、電波が届く範囲が異なるアンテナを用いた場合にも同様の重み付け処理を行うことができる。また、たとえば商圏の異なる店舗の配置位置を選択する場合にも、同様の重み付けをすることができる。
【０１３６】
また、第二の実施の形態および第三の実施の形態で説明したエリア分割処理は。種々の手順を用いて行うことができる。たとえば、第二の実施の形態において、図１４のステップ１３２またはステップ１４２を参照して各エリアのシードから最短の位置にある店舗を候補として検出するとして説明したが、各エリアで取得済みの店舗の重心から最短の位置にある店舗を候補として検出するようにしてもよい。この場合も、検出された店舗を候補として決定するか否かの判断は、図１４と同様の処理で行うことができる。
【０１３７】
また、この処理は、ＭＳＴ（ｍｉｎｉｍｕｍ　ｓｐａｎｎｉｎｇ　ｔｒｅｅ）と同様の原理を用いて、各エリアで取得済みの店舗のいずれかから最短の位置にある店舗を候補として検出するようにしてもよい。この場合も、検出された店舗を候補として決定するか否かの判断は、図１４と同様の処理で行うことができる。
【０１３８】
また、第二の実施の形態および第三の実施の形態において、統計量として各エリアの合計コース数を例示して説明したが、各エリアにおいて、たとえば、各エリアに含まれる店舗の数、店舗あたりの平均装填作業時間、店舗あたりの平均月装填回数、店舗あたりの拠点からの距離平均、店舗間距離平均、コースあたりの店舗数、総売上、店舗あたりの売上平均等、コース数以外の統計量が均等となるようにエリア分割を行うこともできる。たとえば、統計量として店舗あたりの売上平均を用いた場合、各エリアにおける売上を均等にすることができる。このような処理を第三の実施の形態において説明したように、実際に必要なシード数より多くのシード候補を設定してグループ分割を行う処理と組み合わせることもできる。この場合、各エリアに含まれる店舗の数が均等になるようなシードを適切に設定することができるので、最終的に各エリアにおけるコース数もある程度均等にしつつ、各エリアにおける売上をも均等にすることもできる。これにより、作業員の公平感をより高めることもできる。
【０１３９】
また、第二の実施の形態および第三の実施の形態において、各店舗を単独に処理するとして説明したが、ユーザは同じエリアに含めたい店舗間の関連付けを手動で行うこともできる。この場合、関連付けられた店舗は一つの店舗として取り扱うことができる。
【０１４０】
さらに、第二の実施の形態および第三の実施の形態において、図１６のステップ１６４で説明したように、各エリアにおけるコース数の算出には、図１８の基礎条件として入力された店舗毎作業時間の平均作業時間が用いられるとして説明したが、店舗情報記憶部Ｔ３に記憶された各店舗毎の実際の作業時間を考慮してコース数を算出するようにすることもできる。このようにすれば、店舗の種類に応じて作業時間が異なる場合であっても、より厳密にコース数を算出することができるので、各エリアにおける作業員の労力を均等にすることができる。
【０１４１】
【発明の効果】
以上、本発明によれば、対象地域内に配置された複数の候補地点から、複数の代表地点を適切な配置で選択することができる。本発明によれば、対象地域でサービスを提供する場合に、その地域全体にサービスが行き渡るように、地域内に複数のサービスポイントを効率よく配置することができる。本発明によれば、対象地域内に複数のサービスポイントを配置する場合に、他のサービスポイントの位置との関係で、各サービスポイントにおける効果が高くなるような配置を選択することができる。本発明によれば、複数の巡回ポイントを含む対象地域をエリア分割する際に、各エリアの起点となる巡回ポイントを適切に選択することができる。
【図面の簡単な説明】
【図１】本発明の第一の実施の形態における基地局の配置地点を選択する手順を示すフローチャートである。
【図２】本発明の第一の実施の形態における配置地点選択装置の構成を示すブロック図である。
【図３】第一の実施の形態において、配置地点選択部が基地局の配置地点を選択する手順を示すフローチャートである。
【図４】図３を参照して説明した配置地点の選択処理を具体的に説明する図である。
【図５】図３を参照して説明した配置地点の選択処理の他の例を説明する図である。
【図６】営業区域内における地域特性に違いがある場合に、基地局の配置地点を選択する手順を示すフローチャートである。
【図７】図６に示した手順を具体的に説明する図である。
【図８】営業区域内における地域特性に違いがある場合に、基地局の配置地点を選択する手順の他の例を示すフローチャートである。
【図９】図８のステップ５２で説明した変形地図の作成方法を具体的に説明する図である。
【図１０】配置地点選択部により作成された変形地図を模式的に示す図である。
【図１１】本発明の第二の実施の形態におけるエリア分割処理の手順を示すフローチャートである。
【図１２】本発明の第二の実施の形態におけるエリア分割処理を行うエリアシュミレータ装置の構成を示すブロック図である。
【図１３】本発明の第二の実施の形態におけるエリア分割処理の手順を示すフローチャートである。
【図１４】図１３に示したステップ１０４の自販機の候補を選択する手順を示すフローチャートである。
【図１５】図１３および図１４に示したエリア分割処理の一例を説明する図である。
【図１６】各分割エリアにおける合計コース数の算出処理の手順を示すフローチャートである。
【図１７】パラメータの設定および初期設定を行うための画面を示す図である。
【図１８】パラメータの設定および初期設定を行うための画面を示す図である。
【図１９】パラメータの設定および初期設定を行うための画面を示す図である。
【図２０】パラメータの設定および初期設定を行うための画面を示す図である。
【図２１】本発明の第三の実施の形態におけるシード設定処理の手順を示すフローチャートである。
【図２２】本発明の第三の実施の形態におけるシード候補数および選択条件の設定画面を示す図である。
【図２３】図８から図１０を参照して説明した変形処理を行う前のもとの図と変形処理を行った後の変形地図とを模式的に示す図である。
【符号の説明】
１０　配置地点選択装置
１２　表示処理部
１４　初期設定部
１６　配置地点選択部
２０　地図情報記憶部
２２　候補地点情報記憶部
２４　エリア情報記憶部
２６　ロジック記憶部
１００　エリアシュミレータ装置
１０８　表示処理部
１１０　パラメータ設定部
１１４　初期設定部
１１６　候補選択処理部
１１８　分割制御部
Ｔ１　地図情報記憶部
Ｔ２　拠点情報記憶部
Ｔ３　店舗情報記憶部
Ｔ４　パラメータ記憶部
Ｔ５　初期設定記憶部
Ｔ６　エリア分割情報記憶部
Ｔ７　ロジック記憶部
【図１】
2004112256.tif 000003
【図２】
2004112256.tif 000004
【図３】
2004112256.tif 000005
【図４】
2004112256.tif 000006
【図５】
2004112256.tif 000007
【図６】
2004112256.tif 000008
【図７】
2004112256.tif 000009
【図８】
2004112256.tif 000010
【図９】
2004112256.tif 000011
【図１０】
2004112256.tif 000012
【図１１】
2004112256.tif 000013
【図１２】
2004112256.tif 000014
【図１３】
2004112256.tif 000015
【図１４】
2004112256.tif 000016
【図１５】
2004112256.tif 000017
【図１６】
2004112256.tif 000018
【図１７】
2004112256.tif 000019
【図１８】
2004112256.tif 000020
【図１９】
2004112256.tif 000021
【図２０】
2004112256.tif 000022
【図２１】
2004112256.tif 000023
【図２２】
2004112256.tif 000024
【図２３】
2004112256.tif 000025