(57)【要約】【課題】複数地点に設けられた自動販売機などの設備を巡回する際の巡回経路を、各設備の稼働状態を考慮してより適切に生成する。【解決手段】複数地点に設けられた設備を巡回する際の巡回経路を生成する巡回経路生成装置であって、前記設備のそれぞれの稼働状態を表す稼働情報を収集する稼働情報収集部と、前記収集した稼働情報をもとに、前記設備の巡回の緊急度を特定する緊急度特定部と、前記巡回経路の複数の候補を生成する候補生成部と、前記複数の候補に対して、緊急度が高い設備が優先的に巡回される度合いを表す第１指標値と、巡回経路の経路長に関する第２指標値と、を算出し、前記第１指標値及び前記第２指標値の算出結果をもとに、前記複数の候補の中から一つの候補を選出することにより、前記巡回経路を生成する巡回経路生成部と、を備える。【選択図】図１９
2019096100.tif 000002
【特許請求の範囲】
【請求項１】
複数地点に設けられた設備を巡回する際の巡回経路を生成する巡回経路生成装置であって、
前記設備のそれぞれの稼働状態を表す稼働情報を収集する稼働情報収集部と、
前記収集した稼働情報をもとに、前記設備の巡回の緊急度を特定する緊急度特定部と、
前記巡回経路の複数の候補を生成する候補生成部と、
前記複数の候補に対して、緊急度が高い設備が優先的に巡回される度合いを表す第１指標値と、巡回経路の経路長に関する第２指標値と、を算出し、前記第１指標値及び前記第２指標値の算出結果をもとに、前記複数の候補の中から一つの候補を選出することにより、前記巡回経路を生成する巡回経路生成部と、
を備える巡回経路生成装置。
【請求項２】
請求項１に記載の巡回経路生成装置であって、
前記複数地点を含む地域を複数の小地域に分割する地域分割部と、
をさらに備え、
前記候補生成部は、前記小地域ごとに、前記小地域内の複数の前記設備を巡回する際の巡回経路の複数の候補を生成し、
前記巡回経路生成部は、前記小地域ごとに、前記複数の候補に対して前記第１指標値及び前記第２指標値を算出することにより前記巡回経路を生成する、
巡回経路生成装置。
【請求項３】
請求項２に記載の巡回経路生成装置であって、
前記各小地域の前記巡回経路に対して算出された前記第２指標値を用いて、前記各小地域の前記巡回経路を巡回するのに要するそれぞれの巡回時間を算出し、前記巡回時間が所定の基準値よりも第１所定値以上となる小地域に対しては、当該小地域内の設備の数を減らし、前記巡回時間が前記基準値よりも前記第１所定値以下となる小地域に対しては、当該小地域内の設備の数を増やすように、前記各小地域の区割りを変更する区割り変更部と、
をさらに備え、
前記巡回経路生成部は、前記区割りの変更前に生成した前記各小地域の前記巡回経路を、前記区割りの変更により追加された設備を新たに経由し、前記区割りの変更により他の小地域に移動した設備を経由しないように修正することにより、前記区割りの変更に対応した巡回経路を生成する、
巡回経路生成装置。
【請求項４】
請求項３に記載の巡回経路生成装置であって、
前記基準値は、前記各小地域の前記巡回経路を巡回するのに要するそれぞれの巡回時間の平均値である、
巡回経路生成装置。
【請求項５】
請求項３に記載の巡回経路生成装置であって、
前記基準値は、前記小地域の担当者ごとに定められる値である、
巡回経路生成装置。
【請求項６】
請求項１〜５のいずれかに記載の巡回経路生成装置であって、
前記巡回経路生成部は、前記巡回経路を生成後に、前記巡回経路内のいずれかの設備の緊急度が第２所定値以上変化した場合には、当該巡回経路の複数の候補に対して、再度、前記第１指標値及び前記第２指標値を算出することにより、新たな巡回経路を生成する、
巡回経路生成装置。
【請求項７】
請求項６に記載の巡回経路生成装置であって、
前記各設備への巡回が完了したか否かを記憶する巡回状態記憶部と、
をさらに備え、
前記巡回経路生成部は、前記巡回経路内のいずれかの設備の緊急度が前記第２所定値以上上昇した場合には、未巡回の設備及び前記緊急度が上昇した前記設備のみを巡回するように、前記新たな巡回経路を生成する、
巡回経路生成装置。
【請求項８】
請求項６に記載の巡回経路生成装置であって、
前記各設備への巡回が完了したか否かを記憶する巡回状態記憶部と、
をさらに備え、
前記巡回経路生成部は、前記巡回経路内のいずれかの設備の緊急度が前記第２所定値以上低下した場合には、前記緊急度が低下した設備が未巡回である場合にのみ、未巡回の設備のみを巡回するように、前記新たな巡回経路を生成する、
巡回経路生成装置。
【請求項９】
複数地点に設けられた設備を巡回する際の巡回経路を生成する巡回経路生成方法であって、
前記各設備と通信可能に接続される巡回経路生成装置が、
前記設備のそれぞれの稼働状態を表す稼働情報を収集し、
前記収集した稼働情報をもとに、前記設備の巡回の緊急度を特定し、
前記巡回経路の複数の候補を生成し、
前記複数の候補に対して、緊急度が高い設備が優先的に巡回される度合いを表す第１指標値と、巡回経路の経路長に関する第２指標値と、を算出し、前記第１指標値及び前記第２指標値の算出結果をもとに、前記複数の候補の中から一つの候補を選出することにより、前記巡回経路を生成する、
巡回経路生成方法。
【請求項１０】
複数地点に設けられた設備を巡回する際の巡回経路を生成するコンピュータに、
前記設備のそれぞれの稼働状態を表す稼働情報を収集する手順と、
前記収集した稼働情報をもとに、前記設備の巡回の緊急度を特定する手順と、
前記巡回経路の複数の候補を生成する手順と、
前記複数の候補に対して、緊急度が高い設備が優先的に巡回される度合いを表す第１指標値と、巡回経路の経路長に関する第２指標値と、を算出し、前記第１指標値及び前記第２指標値の算出結果をもとに、前記複数の候補の中から一つの候補を選出することにより、前記巡回経路を生成する手順と、
を実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、巡回経路生成装置、巡回経路生成方法及びプログラムに関する。
【背景技術】
【０００２】
今日、様々な場所に自動販売機が設置されており、日々の生活を便利なものにしている。一方で、自動販売機は商品の補充や釣銭の回収、清掃、修理などのメンテナンスが欠かせない。
【０００３】
そのため、日々、数多くのルートマンが各地の自動販売機を巡回している。
【０００４】
そして、このような各地に点在する自動販売機を巡回する際の巡回経路の生成を支援し、自動販売機のメンテナンスの効率化を図るための技術も開発されている（例えば特許文献１参照）。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２００２−０４２２１７号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら、各地の自動販売機を効率良く巡回するには、なるべく移動距離が短くなるような巡回経路を選択することが重要である一方で、巡回対象の自動販売機の中には、例えば釣銭が残り少なくなっているものや故障が発生しているものなどが混在している場合があり、そのような自動販売機をなるべく早く巡回した方が好ましい場合もある。
【０００７】
このため、移動距離の短い巡回経路を生成するだけでなく、各自動販売機の稼働状態に応じた、より適切な巡回経路を生成可能とする技術が求められている。
【０００８】
本発明はこのような課題を鑑みてなされたものであり、複数地点に設けられた自動販売機などの設備を巡回する際の巡回経路を、各設備の稼働状態を考慮してより適切に生成することが可能な巡回経路生成装置、巡回経路生成方法及びプログラムを提供する。
【課題を解決するための手段】
【０００９】
本発明の一実施形態に係る巡回経路生成装置は、複数地点に設けられた設備を巡回する際の巡回経路を生成する巡回経路生成装置であって、前記設備のそれぞれの稼働状態を表す稼働情報を収集する稼働情報収集部と、前記収集した稼働情報をもとに、前記設備の巡回の緊急度を特定する緊急度特定部と、前記巡回経路の複数の候補を生成する候補生成部と、前記複数の候補に対して、緊急度が高い設備が優先的に巡回される度合いを表す第１指標値と、巡回経路の経路長に関する第２指標値と、を算出し、前記第１指標値及び前記第２指標値の算出結果をもとに、前記複数の候補の中から一つの候補を選出することにより、前記巡回経路を生成する巡回経路生成部と、を備える。
【００１０】
その他、本願が開示する課題、及びその解決方法は、発明を実施するための形態の欄の記載、及び図面の記載等により明らかにされる。
【発明の効果】
【００１１】
複数地点に設けられた自動販売機などの設備を巡回する際の巡回経路を、各設備の稼働状態を考慮してより適切に生成することが可能となる。
【図面の簡単な説明】
【００１２】
【図１】実施形態に係る巡回経路生成システムの全体構成図である。
【図２】実施形態に係る自動販売機のハードウェア構成を示す図である。
【図３】実施形態に係る巡回経路生成装置のハードウェア構成を示す図である。
【図４】実施形態に係る巡回経路生成装置の記憶装置を示す図である。
【図５】実施形態に係る自動販売機管理テーブルを示す図である。
【図６】実施形態に係る緊急度管理テーブルを示す図である。
【図７】実施形態に係る巡回管理テーブルを示す図である。
【図８】実施形態に係る巡回経路生成装置の機能構成を示す図である。
【図９】シミュレーテッドアニーリング法を説明するための図である。
【図１０】実施形態に係る巡回経路を説明するための図である。
【図１１】実施形態に係る巡回経路を説明するための図である。
【図１２】実施形態に係る処理の流れを説明するためのフローチャートである。
【図１３】実施形態に係る処理の流れを説明するためのフローチャートである。
【図１４】実施形態に係る巡回経路生成装置の記憶装置を示す図である。
【図１５】実施形態に係るエリア管理テーブルを示す図である。
【図１６】実施形態に係るエリア分割を説明するための図である。
【図１７】実施形態に係る巡回経路生成装置の機能構成を示す図である。
【図１８】実施形態に係る巡回経路を説明するための図である。
【図１９】実施形態に係る巡回経路を説明するための図である。
【図２０】実施形態に係る区割り変更を説明するための図である。
【図２１】実施形態に係る区割り変更を説明するための図である。
【図２２】実施形態に係る区割り変更を説明するための図である。
【図２３】実施形態に係る区割り変更を説明するための図である。
【図２４】実施形態に係る区割り変更を説明するための図である。
【図２５】実施形態に係る区割り変更を説明するための図である。
【図２６】実施形態に係る処理の流れを説明するためのフローチャートである。
【図２７】実施形態に係る処理の流れを説明するためのフローチャートである。
【発明を実施するための形態】
【００１３】
本明細書および添付図面の記載により、少なくとも以下の事項が明らかとなる。以下、本発明を実施形態に即して添付図面を参照しつつ説明する。
【００１４】
[第１実施形態]
＝＝全体構成＝＝
図１に、本発明の第１実施形態に係る自動販売機管理システム１０００の全体構成図を示す。
【００１５】
自動販売機管理システム１０００は、巡回経路生成装置１００と、複数の自動販売機３００とがネットワーク５００（図１には不図示）を通じて通信可能に接続されて構成される。ネットワーク５００は、インターネットやＬＡＮ（Local Area Network）、電話網等の各種の情報通信網である。
【００１６】
図１には、所定地域９００内の各所に、巡回経路生成装置１００及び複数台（１８台）の自動販売機３００が点在して設けられている様子が示されている。
【００１７】
自動販売機３００は、利用者から所定金額の金銭が投入されると、飲料などの各種商品を利用者に提供する設備ないし装置である。
【００１８】
巡回経路生成装置１００は、これらの自動販売機３００のメンテナンスを行うルートマンが、複数地点に設けられた自動販売機３００を巡回する際の巡回経路を生成する装置である。
【００１９】
図１には、星印で示した巡回経路生成装置１００が、巡回経路の起点及び終点となるルートマンの職場などの拠点に設けられているとした場合の様子が示されているが、巡回経路生成装置１００の設置場所は地域９００の外部でもよい。
【００２０】
なお詳細は以下に説明するが、本実施形態に係る巡回経路生成装置１００は、総移動距離がなるべく短く、かつ、メンテナンスの緊急度が高い自動販売機３００をなるべく優先的に巡回するような巡回経路を生成することができる。例えば図１０は、総移動距離がなるべく短くなるよう生成された巡回経路を表し、図１１は、これに加えて、緊急度が高い自動販売機３００（図１０及び図１１において「ｚ」と記した自動販売機３００）をなるべく先に巡回するようにした巡回経路を表す。
【００２１】
＝＝自動販売機＝＝
図２は、本実施形態に係る自動販売機３００の構成を示すブロック図である。図２を参照しつつ、自動販売機３００について説明する。
【００２２】
自動販売機３００は、主制御部３１０、コインメック３２０、ビルバリ３３０、自動販売制御部３４１、自動販売機構３４２を備えて構成されている。
【００２３】
主制御部３１０は、コインメック３２０、ビルバリ３３０、及び自動販売制御部３４１と通信可能に接続される。そして主制御部３１０は、コインメック３２０、ビルバリ３３０、及び自動販売制御部３４１と相互に各種の制御情報を授受しながら、自動販売機３００を統括制御する。
【００２４】
主制御部３１０は、ＣＰＵ３１１、ＲＯＭ３１２、ＲＡＭ３１３、及び通信装置３１４を備えて構成されている。
【００２５】
ＣＰＵ３１１は、ＲＯＭ３１２に記憶されている所定のプログラムを実行することにより、主制御部３１０の制御を行う。ＲＡＭ３１３は、コインメック３２０やビルバリ３３０、自動販売制御部３４１などから取得した制御情報などの各種稼働情報を記憶する。通信装置３１４は、コインメック３２０、ビルバリ３３０、及び自動販売制御部３４１との通信を行う。なお通信装置３１４は、さらに、ネットワーク５００を介して接続される巡回経路生成装置１００や不図示のコンピュータとの通信を行うこともできる。
【００２６】
コインメック３２０は、利用者に投入された硬貨の受け入れや選別、貯留等を行う電子機器であり、自動販売機３００内に釣銭用に保有する硬貨の枚数を制御する機能を有する。コインメック３２０は、硬貨処理制御部３２１と硬貨投入機構３２２とを備えて構成される。
【００２７】
硬貨処理制御部３２１は、投入された硬貨の真偽の判別や、投入された硬貨を貯留しておくためのコインチューブ（不図示）に硬貨を種類別に選別するための制御、コインチューブ内の各硬貨の枚数の検出等の制御を行う。
【００２８】
硬貨投入機構３２２は、上記コインチューブや、投入された硬貨がコインチューブに落下するまでの通路、コインチューブから硬貨の返却口（不図示）にいたる通路等により構成される。
【００２９】
コインメック３２０は、自動販売機３００の硬貨投入口（不図示）からの硬貨投入を検出すると、投入金額を算出して主制御部３１０に送信する。またコインメック３２０は、主制御部３１０からの要求に応じて、コインチューブ内に貯留されている硬貨の枚数を種類別に検出し、主制御部３１０に各硬貨の枚数を送信する。またコインメック３２０は、釣銭切れを検出すると主制御部３１０にその旨の情報を送信する。
【００３０】
ビルバリ３３０は、利用者に挿入された紙幣の受け入れや選別、貯留等を行う電子機器である。ビルバリ３３０は、紙幣処理制御部３３１と紙幣挿入機構３３２とを備えて構成される。
【００３１】
紙幣処理制御部３３１は、挿入された紙幣の真偽の判別や、挿入された紙幣を種類別に選別するための制御、各紙幣の枚数の検出等の制御を行う。
【００３２】
紙幣挿入機構３３２は、挿入された紙幣が貯留されるまでの通路等により構成される。
【００３３】
ビルバリ３３０は、紙幣挿入口（不図示）からの紙幣挿入を検出すると、挿入金額を算出して主制御部３１０に送信する。またビルバリ３３０は、内部に貯留されている紙幣の枚数を種類別に検出し、主制御部３１０に各紙幣の枚数を送信する。またビルバリ３３０は、釣銭切れを検出すると主制御部３１０にその旨の情報を送信する。
【００３４】
自動販売機構３４２は、自動販売機３００の内部の商品棚や商品排出機構、さらには、自動販売機３００の外部の商品選択ボタンや支払い用ＩＣカードのリーダライタ、各種表示ランプ及びディスプレイ等の、利用者へ商品を提供するために制御される機構を含む。
【００３５】
自動販売制御部３４１は、上述した自動販売機構３４２を制御する。また、自動販売制御部３４１は商品の在庫量を検出し、主制御部３１０に送信する。また自動販売制御部３４１は、自動販売機構３４２の故障検知を行い、主制御部３１０に送信する。
【００３６】
そして主制御部３１０は、コインメック３２０から取得したコインの枚数や、ビルバリ３３０から取得した紙幣の残量、自動販売制御部３４１から取得した商品の在庫量などの各種情報を、自動販売機３００の稼働状態を表す稼働情報として巡回経路生成装置１００に送信する。
【００３７】
主制御部３１０は、巡回経路生成装置１００からリクエストを受信した際に上記稼働情報を巡回経路生成装置１００に送信するようにしても良いし、リクエストが無くても、所定期間毎（例えば１時間毎）に送信するようにしても良い。また主制御部３１０は、機器の故障を表す稼働情報など緊急度の高い稼働情報については、随時、巡回経路生成装置１００に送信するようにしても良い。
【００３８】
なお詳細は後述するが、主制御部３１０から巡回経路生成装置１００に送信される自動販売機３００の稼働情報には、各稼働情報を一意に識別するためのコード（状態コード）が付与されており、主制御部３１０は、状態コードを巡回経路生成装置１００に送信する。
【００３９】
＝＝巡回経路生成装置＝＝
次に、第１実施形態に係る巡回経路生成装置１００を図３〜図１３を参照しながら説明する。
【００４０】
巡回経路生成装置１００のハードウェア構成を図３に示す。巡回経路生成装置１００は、ＣＰＵ（Central Processing Unit）１１０、メモリ１２０、通信装置１３０、記憶装置１４０、入力装置１５０、出力装置１６０、及び記録媒体読取装置１７０を備えて構成されるコンピュータである。
【００４１】
記憶装置１４０は、ＣＰＵ１１０によって実行される巡回経路生成装置制御プログラム７００等の各種のプログラムやデータを格納する。
【００４２】
記憶装置１４０に記憶されている巡回経路生成装置制御プログラム７００や各種のデータがメモリ１２０に読み出されてＣＰＵ１１０によって実行あるいは処理されることにより、巡回経路生成装置１００の各種機能が実現される。
【００４３】
ここで、記憶装置１４０は例えばハードディスクやＳＳＤ（Solid State Drive）、フラッシュメモリ等の不揮発性の記憶装置である。
【００４４】
記憶装置１４０には、図４に示すように巡回経路生成装置制御プログラム７００、自動販売機管理テーブル６００、緊急度管理テーブル６１０、及び巡回管理テーブル６２０が記憶されている。
【００４５】
記録媒体読取装置１７０は、ＣＤやＤＶＤ、ＳＤカード等の記録媒体８００に記録された巡回経路生成装置制御プログラム７００やデータを読み取り、記憶装置１４０に格納する。
【００４６】
通信装置１３０は、ネットワーク５００を介して、自動販売機３００や不図示の他のコンピュータと各種データや巡回経路生成装置制御プログラム７００の授受を行う。例えば他のコンピュータに上述した巡回経路生成装置制御プログラム７００やデータを格納しておき、巡回経路生成装置１００がこのコンピュータから巡回経路生成装置制御プログラム７００やデータをダウンロードするようにすることができる。あるいは通信装置１３０は、ルートマンが携帯する不図示のスマートフォンやノートパソコン等の携帯端末と通信を行い、種々の情報の授受を行うことも可能である。
【００４７】
入力装置１５０は、ユーザによるコマンドやデータの入力を受け付ける各種ボタンやスイッチ、マウス、キーボードなどの装置である。
【００４８】
また出力装置１６０は、例えばディスプレイなどの表示装置、スピーカなどの装置である。
【００４９】
＜自動販売機管理テーブル＞  
記憶装置１４０に記憶される自動販売機管理テーブル６００を図５に示す。自動販売機管理テーブル６００は、自動販売機３００を一意に特定するための自販機ＩＤと、自動販売機３００の設置場所を示す情報とを対応付けて記憶したテーブルである。
【００５０】
図５に示す例では、自動販売機３００の設置場所は一例として緯度及び経度で特定されている。
【００５１】
＜緊急度管理テーブル＞
緊急度管理テーブル６１０を図６に示す。緊急度管理テーブル６１０は、自動販売機３００から送信されてくる稼働情報と、自動販売機３００の巡回の緊急度と、を対応付けて記憶したテーブルである。
【００５２】
なお上述したように各稼働情報には、稼働情報を一意に識別する状態コードが付与されており、緊急度管理テーブル６１０には、状態コードが記憶されている。
【００５３】
また本実施形態では、緊急度は０〜９の１０段階で示され、数値が大きい程、緊急度が高いことを表す。
【００５４】
図６に示す例では、例えば「Ｋ０００１」で特定される稼働情報は、釣り銭切れが発生中であることを示し、緊急度は「７」とされている。
【００５５】
＜巡回管理テーブル＞
巡回管理テーブル６２０を図７に示す。巡回管理テーブル６２０は、ルートマンが巡回すべき自動販売機３００について、巡回が完了したか否かを記憶するテーブルである。
【００５６】
巡回管理テーブル６２０は、ルートマンが自動販売機３００を巡回する毎に作成され、巡回経路内の自動販売機３００を一つ訪問する毎にその日時が追加されていく。図７に示す例では、自販機ＩＤが「Ａ」と「Ｃ」で特定される自動販売機３００は巡回が完了しており、「Ｂ」で特定される自動販売機３００は未巡回であることが記録されている。
【００５７】
自動販売機３００は、例えばルートマンが保守作業を開始した際、あるいは保守作業を完了した際に、その旨の情報を自販機ＩＤと共に巡回経路生成装置１００に送信するように構成されており、巡回経路生成装置１００は、この情報を受信した日時を巡回管理テーブル６２０に記録する。
【００５８】
＜巡回経路生成装置の機能構成＞
次に、巡回経路生成装置１００の機能構成について、図８に示す機能構成図を参照しながら説明する。
【００５９】
上述したように、巡回経路生成装置１００は、記憶装置１４０に記憶されている巡回経路生成装置制御プログラム７００や各種のデータがメモリ１２０に読み出されてＣＰＵ１１０によって実行あるいは処理されることにより、巡回経路生成装置１００としての各種機能を実現する。
【００６０】
具体的には、巡回経路生成装置１００は、稼働情報収集部１０１、緊急度特定部１０２、巡回状態記憶部１０３、巡回経路生成部１０４、及び候補生成部１０７の各機能を有する。
【００６１】
稼働情報収集部１０１は、各自動販売機３００から、それぞれの稼働状態を表す稼働情報を収集する。具体的には、稼働情報収集部１０１は、各自動販売機３００から状態コードを収集する。
【００６２】
緊急度特定部１０２は、緊急度管理テーブル６１０を参照し、各自動販売機３００から収集した上記稼働情報をもとに、各自動販売機３００の巡回の緊急度を特定する。なお、１台の自動販売機３００から複数の稼働情報を取得した場合には、緊急度特定部１０２は、各稼働情報にそれぞれ対応する緊急度のうち、もっとも高い緊急度をその自動販売機３００の緊急度とする。
【００６３】
巡回状態記憶部１０３は、各自動販売機３００への巡回が完了したか否かを記憶する。本実施形態では、巡回状態記憶部１０３は、上述した巡回管理テーブル６２０として具現化される。
【００６４】
候補生成部１０７は、巡回経路の複数の候補を生成する。候補生成部１０７は、一例として、シミュレーテッドアニーリング法を用いて巡回経路の候補を生成する。シミュレーテッドアニーリング法は、金属の焼きなましを模倣した計算手法である。
【００６５】
シミュレーテッドアニーリング法を用いて巡回経路の候補を生成する場合は、最初に、巡回対象である各自動販売機３００をランダムな順番に巡回するように巡回経路を決めて初期状態とし、その後、それらの自動販売機３００の中からランダムに選択した２つの間の順序を入れ替えることを繰り返すことで、順次、巡回経路の候補を生成していく。
【００６６】
図９には、シミュレーテッドアニーリング法において２つの自動販売機３００を選び、それらの自動販売機３００の間の巡回順序を入れ替える処理が行われる様子を示す。図９は、「５」で示す自動販売機３００を出発して他の自動販売機３００を経由した後、再び「５」の自動販売機３００に戻ってくる場合の巡回経路を生成する場合に、図９（Ａ）で生成される巡回経路の候補における「１」と「３」の２つの自動販売機３００に挟まれる「１」→「４」→「３」の順序を入れ替えて、図９（Ｂ）に示すように「３」→「４」→「１」とすることで、他の候補を生成することが示されている。
【００６７】
巡回経路生成部１０４は、巡回経路の複数の候補に対して、緊急度が高い自動販売機３００が優先的に巡回される度合いを表す第１指標値と、各自動販売機３００を巡回する際の経路長、つまりルートマンの移動距離に関する第２指標値と、を算出し、第１指標値及び第２指標値の算出結果を元に複数の候補の中から一つの候補を選出することにより、巡回経路を生成する。
【００６８】
なお、巡回経路生成部１０４は、候補生成部１０７が巡回経路の複数の候補を一通り生成した後に、各候補に対して指標値の算出処理を行っても良いが、本実施形態では、候補生成部１０７が巡回経路の候補を一つ算出する毎に指標値を算出するようにしている。そして巡回経路生成部１０４は、１つ前に生成された候補の指標値と、今回生成された候補の指標値を比較し、指標値が最適値から遠い方の候補を破棄する処理を行う。このようにして巡回経路生成部１０４は、指標値がその時点で最善の候補を記憶し続けるように処理を行うことで、最終的に、候補生成部１０７が生成する全ての候補の中から、指標値が最善の一つの候補を巡回経路として選出することができる。
【００６９】
本実施形態に係る巡回経路生成部１０４は、上記シミュレーテッドアニーリング法を用いて生成される巡回経路の複数の候補に対して、下記の式（１）〜式（４）に示すコスト関数の値を算出する。
【００７０】
コスト関数＝第１指標値＋第２指標値                                  …（１）
第１指標値＝−α×Σf(自動販売機の緊急度,順番)  α:正の係数          …（２）
f(自動販売機の緊急度,順番)＝max(0,(全自動販売機数/2-順番)×緊急度)  …（３）
第２指標値＝Σ経路上で隣り合う２つの自動販売機間の距離              …（４）
なお、式（３）における「自動販売機の緊急度」は、緊急度管理テーブル６１０に記載される緊急度の値であり、上述したように、緊急度が高いものほど数値が大きい（本実施形態では緊急度は０〜９）。また「順番」は、ルートマンがその自動販売機３００を何番目に訪れるかを示す値である。ただし、本実施形態では、ルートマンが最初に訪れる自動販売機３００を０番目とする。
【００７１】
そのため、式（３）の値は、例えば巡回すべき自動販売機３００が全部で１００台あり、ルートマンが緊急度＝９の自動販売機３００を最初に（０番目に）訪問する場合には、ｆ(９,０)＝max(０，（１００／２−０)×９）＝４５０となる。また、もしこの自動販売機３００を５１番目に訪問する場合には、ｆ(９,５１)＝max(０，（１００／２−５１)×９）＝０となる。
【００７２】
このように、式（３）の値は、巡回経路の前半（０番目〜４９番目）で訪問される自動販売機３００に対しては、緊急度の高い自動販売機３００がより早い順番で訪問されるほど大きな値となるが、巡回経路の後半（５０番目〜９９番目）に訪問される自動販売機３００に対しては０となる。
【００７３】
巡回経路生成部１０４は、式（３）の値を各自動販売機３００に対して計算し、式（２）によりこれらを合計することで第１指標値を計算する。このようにして、第１指標値は、緊急度が高い自動販売機３００が優先的に巡回される度合いを表すことができる。
【００７４】
このように、本実施形態に係る巡回経路生成部１０４は、巡回経路の経路長（移動距離）に関する第２指標値（式（４））のみならず、緊急度が高い自動販売機３００が優先的に巡回される度合いを表す第１指標値も用いて巡回経路を生成している。
【００７５】
式（１）に示す本実施形態に係るコスト関数の値は、巡回経路の総移動距離（経路長）が短い程小さく、かつ、緊急度の高い自動販売機３００がより早い順番で訪問されるほど小さくなる。このため、巡回経路生成部１０４は、巡回経路の各候補のうち、コスト関数の値が最小となった候補を巡回経路として選出する。
【００７６】
このような態様により、各地に設けられる自動販売機３００を巡回する際の巡回経路を、各自動販売機３００の稼働状態に応じて合理的かつ柔軟に生成することが可能となる。
【００７７】
例えば、図１０は、第１指標値を考慮せずに、第２指標値（総移動距離）のみを用いて巡回経路を生成した場合を示すが、この場合は、たとえ、全体の移動距離を短くすることができたとしても、図１０中の「Ｚ」で示される自動販売機３００の緊急度が高く、早急に巡回した方が好ましい場合であっても、この自動販売機３００には、巡回経路の後半（１５番目）まで訪問されないことになる。
【００７８】
これに対し、本実施形態のように、第１指標値と第２指標値とを考慮して巡回経路を生成する場合には、図１１に示す様に、全体としての総移動距離の増加は抑えつつ、「Ｚ」で示される緊急度の高い自動販売機３００を、巡回経路の前半（１番目）に訪問することが可能となる。
【００７９】
なお第２指標値は、式（４）に示したように、経路上で隣り合う２つの自動販売機３００間の距離の総和として算出されるが、自動販売機３００間の距離は、図５に示した自動販売機管理テーブル６００に記録されている緯度経度の差から算出される直線距離としても良いし、各自動販売機３００の位置が不図示の地図上の位置として特定できる場合には、この地図を用いて算出される、道路に沿って移動する場合の距離としても良い。
【００８０】
前者のように距離を算出することにより、距離の計算を簡単に行うことができるため、巡回経路生成装置１００の処理負荷が軽減され、短時間に巡回経路を生成することが可能となる。一方で、後者のように地図上の移動距離を算出する場合には、より正確に距離を計算することができるため、より適切な巡回経路を生成することが可能となる。
【００８１】
なお、巡回経路の候補の生成は、シミュレーテッドアニーリング法を用いる他にも、遺伝的アルゴリズムや山登り法など、様々な手法を用いることが可能である。また巡回経路の候補を評価する際のコスト関数は、自動販売機３００の緊急度が考慮されており、自動販売機３００間の移動距離の総和を短くすることをベースとして、緊急度がより高いものが経路の初めのほうに来ているほどより低いコストを与えるように設定されていれば、式（１）〜式（４）に示した式に限らない。このような態様により、緊急性が高い自動販売機３００をいち早く巡回できるようになる。
【００８２】
また第２指標値は、上述したような各自動販売機３００間の距離を用いて計算される巡回経路の経路長そのものとする他、経路長に関する値であれば他の値でも良い。経路長に関する値としては、例えば、ルートマンの移動速度を用いて移動距離を移動時間に換算することで、巡回経路を巡回するために要する巡回時間とすることができる。
【００８３】
この場合、ルートマンの移動速度は、例えば、過去に自動販売機３００を巡回した際の巡回経路の経路長と、その巡回経路をルートマンが巡回した時に要した時間を利用して計算するか、移動速度に相当する所定の固定値を用いればよい。
【００８４】
＝＝処理の流れ＝＝
次に、本実施形態に係る巡回経路生成装置１００による処理の流れを、図１２及び図１３に示すフローチャートを参照しながら説明する。
【００８５】
まず巡回経路生成装置１００は、各自動販売機３００から稼働情報を収集する（S1000）。そして巡回経路生成装置１００は、緊急度管理テーブル６１０を参照し、各自動販売機３００の稼働情報を元に巡回の緊急度を特定する（S1010）。
【００８６】
そして巡回経路生成装置１００は、巡回経路を生成する（S1020）。具体的には、上述したように、巡回経路生成装置１００は、例えばシミュレーテッドアニーリング法を用いることで巡回経路の複数の候補を生成する。そして巡回経路生成装置１００は、これら複数の候補に対して、各自動販売機３００の緊急度と巡回の順序とを元に算出される第１指標値と、各自動販売機３００を巡回するための移動距離に関する第２指標値と、を算出し、第１指標値及び第２指標値の算出結果を元に複数の候補の中から一つの候補を選出することにより、巡回経路を生成する。
【００８７】
そして巡回経路生成装置１００は、巡回経路を出力し、ルートマンに提示する（S1030）。例えば巡回経路生成装置１００は、液晶ディスプレイ等の出力装置１６０に地図を表示し、この地図の上に重ねて、各自動販売機３００の位置と巡回経路とを表示する。あるいは巡回経路生成装置１００は、ルートマンが携帯するノートパソコン等の携帯端末（不図示）に地図を表示し、この地図の上に重ねて、各自動販売機３００の位置と巡回経路とを表示するようにしても良い。
【００８８】
その後、巡回経路生成装置１００は、いずれかの自動販売機３００から新たな稼働情報を受信していないかどうかを確認する（S1040）。新たな稼働情報を受信していなければ、巡回経路生成装置１００は、S1040において「Ｎｏ」に進む。
【００８９】
この状態で、自動販売機３００を巡回中のルートマンが、自動販売機３００のメンテナンスが１カ所完了する毎に、自動販売機３００あるいはルートマンが携帯する不図示の携帯端末から、巡回経路生成装置１００に自販機ＩＤとともに巡回が完了した旨の通知が送信されてくる。
【００９０】
巡回経路生成装置１００は、この通知を受領すると（S1050）、図７に示す巡回管理テーブル６２０の該当する自動販売機３００に対応する欄に巡回完了日時を記録する（S1060）。
【００９１】
巡回経路生成装置１００は、巡回管理テーブル６２０を参照して、全ての自動販売機３００の巡回が完了したかどうかをチェックし（S1070）、全ての自動販売機３００の巡回が完了していたら、処理を終了する。
【００９２】
一方、未巡回の自動販売機３００がある場合には、巡回経路生成装置１００は、S1070において「Ｎｏ」に進み、S1040に戻る。
【００９３】
巡回経路生成装置１００は、S1040において、いずれかの自動販売機３００から新たな稼働情報を受信した場合には、緊急度管理テーブル６１０を参照し、新たな稼働情報を送信してきた自動販売機３００の緊急度を特定する（S1080）。
【００９４】
そして新たな稼働情報を送信してきた自動販売機３００の緊急度の上昇量が所定値（第２所定値）以上（例えば緊急度が２以上上昇）である場合には（S1090）、巡回経路生成装置１００は、新たな巡回経路を生成する（S1100）。
【００９５】
巡回経路生成装置１００は、新たな巡回経路を生成する際には、巡回管理テーブル６２０を参照し、未巡回の自動販売機３００を特定し、この未巡回の自動販売機３００と、緊急度が所定値以上上昇した自動販売機３００と、のみを巡回するような巡回経路を新たに生成する（S1100）。そして巡回経路生成装置１００は、新たに生成した巡回経路をルートマンに提示する（S1110）。例えば巡回経路生成装置１００は、ルートマンが携帯する不図示の携帯端末に新たな巡回経路を表示する。
【００９６】
なお巡回経路生成装置１００は、新たな巡回経路を生成する場合、緊急度が第２所定値以上上昇した自動販売機３００が未巡回であった場合には、他の未巡回の自動販売機３００を含め、全て未巡回の自動販売機３００のみを巡回するように、新たな巡回経路を生成することができる。一方、緊急度が第２所定値以上上昇した自動販売機３００が巡回済みであった場合には、他の未巡回の自動販売機３００のみならず、緊急度が第２所定値以上上昇した自動販売機３００も再度巡回するように、新たな巡回経路を生成することができる。
【００９７】
このような態様により、緊急度が第２所定値以上上昇した自動販売機３００に対しては、その自動販売機３００をより優先的に巡回するように巡回経路を変更できる。
【００９８】
一方、新たな稼働情報を送信してきた自動販売機３００の緊急度の上昇量が第２所定値以上でない場合には（S1090）、巡回経路生成装置１００は、S1120に進み、その自動販売機３００の緊急度の低下量が第２所定値以上（例えば緊急度が２以上低下）であるかどうかを判定する（S1120）。
【００９９】
そしてこの自動販売機３００の緊急度の低下量が第２所定値未満の場合には（S1120）、巡回経路生成装置１００はS1040に戻り、巡回経路を変更せずに処理を継続する。このような態様により、緊急度の変化量が第２所定値未満（例えば±２未満）の場合は、それまでの巡回経路を継続的に巡回することができ、ルートマンの巡回作業の効率低下を防止することができる。
【０１００】
一方、新たな稼働情報を送信してきた自動販売機３００の緊急度の低下量が第２所定値以上（例えば緊急度が２以上低下）である場合には（S1120）、巡回経路生成装置１００はS1130に進み、その自動販売機３００が未巡回であるか否かを判定する（S1130）。
【０１０１】
もしその自動販売機３００が巡回済みであれば、その緊急度が低下した自動販売機３００を再度訪問する必要はないため、巡回経路生成装置１００はS1040に戻り、巡回経路を変更せずに処理を継続する。このような態様により、緊急度が第２所定値以上低下した自動販売機３００が巡回済みの場合は、それまでの巡回経路を継続的に巡回し、ルートマンの巡回作業の効率低下を防止することができる。
【０１０２】
一方、緊急度が第２所定値以上低下した自動販売機３００が未巡回である場合には（S1130）、巡回経路生成装置１００は、新たな巡回経路を生成する。
【０１０３】
このとき、巡回経路生成装置１００は、巡回管理テーブル６２０を参照し、未巡回の自動販売機３００を特定し、この未巡回の自動販売機３００のみを巡回するような巡回経路を新たに生成する（S1140）。
【０１０４】
このような態様により、緊急度が第２所定値以上低下した未巡回の自動販売機３００に対しては、その自動販売機３００に対する巡回の優先度を下げ、他のより緊急性の高い未巡回の自動販売機３００を先に巡回するように巡回経路を変更することが可能となる。
【０１０５】
なおS1100やS1140において巡回経路生成装置１００が新たな巡回経路を生成する際には、巡回経路生成装置１００は、巡回管理テーブル６２０に記録されている日時情報を元に、ルートマンが最後に訪問した自動販売機３００を特定し、この自動販売機３００の位置（あるいはその次に訪問予定であった自動販売機３００の位置でもよい）をルートマンの現在位置として推定し、このルートマンの現在位置を起点として新たな巡回経路を生成する。あるいは、ルートマンが携帯する携帯端末がＧＰＳ信号を受信可能であり、現在位置情報を随時取得可能である場合には、巡回経路生成装置１００は携帯端末からルートマンの現在位置情報を取得して新たな巡回経路の起点としても良い。
【０１０６】
[第２実施形態]
次に、第２実施形態に係る自動販売機管理システム１０００について説明する。なお以下の説明において、第１実施形態と重複する説明は適宜省略する。
【０１０７】
第２実施形態に係る自動販売機管理システム１０００は、第１実施形態と同様に、巡回経路生成装置１００と、自動販売機３００とがネットワーク５００を通じて通信可能に接続されて構成される。そして第２実施形態に係る巡回経路生成装置１００も、図１に示したように、地域９００内の各自動販売機３００の巡回経路を生成する。
【０１０８】
ただし、第２実施形態では、複数のルートマンが地域９００内の自動販売機３００を分担して巡回する。そのため、第２実施形態に係る巡回経路生成装置１００は、図１６に示す様に、自動販売機３００が設置される複数の地点を含む地域９００を複数の小地域９１０に分割したうえで、各小地域９１０毎にルートマンの巡回経路を生成する。そして巡回経路生成装置１００は、各小地域９１０の巡回経路を回るルートマンの巡回時間にバラつきが生じる場合には、各小地域９１０の区割りを変更して、各ルートマンの巡回時間が均一になるように、再度巡回経路を生成する。以下、詳細に説明する。なお、以下の説明において小地域９１０をエリア９１０とも記す
第２実施形態に係る巡回経路生成装置１００は、第１実施形態に係る巡回経路生成装置１００に対してハードウェア構成は同様であるが、記憶装置１４０に記憶されるプログラム及びデータが一部異なる。
【０１０９】
具体的には、第２実施形態に係る巡回経路生成装置１００は、図１４に示すように巡回経路生成装置制御プログラム７００、自動販売機管理テーブル６００、緊急度管理テーブル６１０、巡回管理テーブル６２０、及びエリア管理テーブル６３０を記憶装置１４０に記憶している。
【０１１０】
自動販売機管理テーブル６００、緊急度管理テーブル６１０、及び巡回管理テーブル６２０は、第１実施形態と同様であるため、説明を省略する。
【０１１１】
＜エリア管理テーブル＞
エリア管理テーブル６３０を図１５に示す。エリア管理テーブル６３０は、全体の地域９００を分割してなる各小地域９１０の識別情報であるエリアＩＤと、各小地域９１０内に設置される自動販売機３００の識別情報である自販機ＩＤと、を対応付けて記憶したテーブルである。
【０１１２】
図１５に示す例では、全体の地域９００が３つの小地域９１０（エリア０、エリア１、エリア２）に分割されており、各小地域９１０には、それぞれ６つの自動販売機３００が設置されていることが示されている。その様子を図１６に示す。
【０１１３】
この場合、３人のルートマンがそれぞれ６つの自動販売機３００を分担して巡回することになる。そして巡回経路生成装置１００は、小地域９１０毎に巡回経路を生成する。巡回経路生成装置１００は、第１実施形態と同様に、式（１）〜式（４）に示したコスト関数を用いて各小地域９１０の巡回経路の生成を行う。
【０１１４】
＜巡回経路生成装置の機能構成＞
次に、第２実施形態に係る巡回経路生成装置１００の機能構成について、図１７に示す機能構成図を参照しながら説明する。
【０１１５】
具体的には、第２実施形態に係る巡回経路生成装置１００は、稼働情報収集部１０１、緊急度特定部１０２、巡回状態記憶部１０３、巡回経路生成部１０４、地域分割部１０５、区割り変更部１０６、及び候補生成部１０７の各機能を有する。
【０１１６】
稼働情報収集部１０１、緊急度特定部１０２、巡回状態記憶部１０３は第１実施形態と同様であるため、説明を省略する。
【０１１７】
地域分割部１０５は、自動販売機３００が設置される複数の地点を含む地域９００を複数の小地域９１０に分割する。例えば地域分割部１０５は、地域９００内の各所に点在する複数の自動販売機３００を、自動販売機管理テーブル６００に記憶されているこれらの自動販売機３００の位置情報を元に、ｋ平均法等のクラスタリング手法を用いて、地域的にまとまりを持った複数のグループに分類し、各グループ内の自動販売機３００が各小地域９１０に含まれるように、地域９００の区割りを行う。ｋ平均法等のクラスタリング手法は公知の技術であるので、説明は省略する。地域分割部１０５が地域９００を３つの小地域９１０に分割した様子を図１６に示す。
【０１１８】
候補生成部１０７は、小地域９１０毎に、小地域９１０内の自動販売機３００を巡回する際の巡回経路の複数の候補を生成する。
【０１１９】
巡回経路生成部１０４は、第１実施形態と同様に、式（１）〜式（４）に示したコスト関数を用いて巡回経路の生成を行う。巡回経路の生成方法は第１実施形態と同様であるが、第２実施形態に係る巡回経路生成部１０４は、小地域９１０毎に巡回経路の生成を行う。巡回経路生成部１０４が小地域９１０毎に巡回経路を生成した様子を図１８に示す。
【０１２０】
また巡回経路生成部１０４は、以下に述べる区割り変更部１０６が地域９００の区割りを変更し、各小地域９１０内の自動販売機３００の構成が変わった場合には、区割り変更後の各小地域９１０毎に、再度、巡回経路の生成を行う。区割り変更後に、巡回経路生成部１０４が再度巡回経路を生成した様子を図１９に示す。
【０１２１】
区割り変更部１０６は、巡回経路生成部１０４によって小地域９１０毎に生成された各巡回経路のそれぞれの第２指標値を用いて、各小地域９１０の巡回経路を巡回するのに要する各巡回時間を算出し、巡回時間が所定の基準値よりも所定値（第１所定値）以上となる小地域９１０に対しては、当該小地域９１０内の自動販売機３００の数を減らし、巡回時間が所定の基準値よりも上記所定値（第１所定値）以下となる小地域９１０に対しては、当該小地域９１０内の自動販売機３００の数を増やすように、各小地域９１０の区割りを変更する。
【０１２２】
例えば本実施形態では、区割り変更部１０６は、各小地域９１０の巡回経路を、それぞれの巡回時間の平均値と比較し、巡回時間が平均値よりも第１所定値以上となる小地域９１０に対しては、当該小地域９１０内の自動販売機３００の数を減らし、巡回時間が平均値よりも第１所定値以下となる小地域９１０に対しては、当該小地域９１０内の自動販売機３００の数を増やすように、各小地域９１０の区割りを変更する。
【０１２３】
このような態様により、各小地域９１０を巡回するルートマンの巡回時間を平準化することが可能となる。
【０１２４】
区割り変更部１０６が小地域９１０の区割りを変更する様子を図１９に示す。図１９には、区割りの変更によって、「Ｌ」で示される自動販売機３００が、エリア１（９１０）からエリア２（９１０）に変更される様子が示されている。
【０１２５】
つまり図１９は、区割り変更前のエリア１の巡回経路（「Ｉ」→「Ｊ」→「Ｌ」→「Ｋ」→「Ｇ」→「Ｈ」）を巡回するのに要する巡回時間が平均値に対して第１所定値以上であり、区割り変更前のエリア２の巡回経路（「Ｍ」→「Ｎ」→「Ｏ」→「Ｐ」→「Ｑ」→「Ｒ」）を巡回するのに要する巡回時間が平均値に対して第１所定値以下となったとした場合に、区割り変更部１０６が、エリア１（９１０）の自動販売機３００の数を一つ減らし、エリア２（９１０）の自動販売機３００の数を一つ増やすように、各エリア（９１０）の区割りを変更する場合の様子を示す。
【０１２６】
つまり、区割り変更部１０６は、各ルートマンの巡回時間を平準化するために、隣接するエリア９１０を巡回するルートマン同士で、それぞれが担当する自動販売機３００を再分配する。区割り変更部１０６は、隣接しているエリア９１０同士で自動販売機３００の再分配を行う。
【０１２７】
このとき、各ルートマンの巡回時間は、下記に示す式（５）のように、各自動販売機３００での作業時間（自動販売機３００での商品補充作業等に要する時間）と、自動販売機３００間の移動時間と、の総和で決まる。
【０１２８】
巡回時間＝Σ各自動販売機での作業時間＋Σ各自動販売機間の移動時間    …（５）
なお、式（５）において、各自動販売機３００での作業時間の総和は、過去の経験を元にして定まる自動販売機３００の１台あたりの作業時間から算出すればよい。また各自動販売機３００間の移動時間の総和は、式（４）の第２指標値の値（巡回経路長）とルートマンの移動速度を用いて算出すればよい。ルートマンの移動速度は、上述したように、例えば、過去の巡回実績から求めるか、所定の固定値を用いればよい。
【０１２９】
図２０を参照しながら具体的に説明する。図２０（Ａ）は、エリア０〜３（９１０）の４つのエリア９１０の各巡回経路について、区割り変更部１０６がそれぞれ巡回時間を計算したところ、エリア０（９１０）では３００分、エリア１（９１０）では２３０分、エリア２（９１０）では２２０分、エリア３（９１０）では２５０分となった場合を示す。この場合、巡回時間の平均値は２５０分((300+230+220+250)/4)となる。
【０１３０】
そしてエリア０（９１０）の巡回時間と平均値との差は＋５０分である。またエリア１（９１０）の巡回時間と平均値との差は−２０分である。エリア２（９１０）の巡回時間と平均値との差は−３０分である。エリア３（９１０）の巡回時間と平均値との差は、±０分である。
【０１３１】
そして区割り変更部１０６は、これらの差を第１所定値と比較する。ここで、第１所定値は、式（６）に示す様に、自動販売機３００を１カ所まわるのに要する平均時間である。
【０１３２】
第１所定値＝１つの自動販売機の平均作業時間＋
隣の自動販売機までの平均移動時間  …（６）
区割り変更部１０６は、式（５）で求めた巡回時間が、平均値よりも第１所定値以上であるエリア９１０については、そのエリア９１０内の自動販売機３００の数を減らすように、区割りを変更する。
【０１３３】
また区割り変更部１０６は、式（５）で求めた巡回時間が、平均値よりも第１所定値以下であるエリア９１０については、そのエリア９１０内の自動販売機３００の数を増やすように、区割りを変更する。
【０１３４】
この際、区割り変更部１０６は、自動販売機３００の増減数を式（７）のようにして決める。
【０１３５】
増減数＝(巡回時間−平均値)/第１所定値    …（７）
例えば第１所定値＝１０分であるとすると、エリア０（９１０）に対しては（３００−２５０）／１０＝＋５となるため、区割り変更部１０６は、エリア０（９１０）から５台の自動販売機３００を減らすように、区割りを変更する。
【０１３６】
同様に、エリア１（９１０）に対しては（２３０−２５０）／１０＝−２となるため、区割り変更部１０６は、エリア１（９１０）に２台の自動販売機３００を増やすように、区割りを変更する。
【０１３７】
またエリア２（９１０）に対しては（２２０−２５０）／１０＝−３となるため、区割り変更部１０６は、エリア２（９１０）に３台の自動販売機３００を増やすように、区割りを変更する。
【０１３８】
エリア３（９１０）に対しては（２５０−２５０）／１０＝０となるため、区割り変更部１０６は、エリア３（９１０）に自動販売機３００の増減は行わない。
【０１３９】
区割り変更部１０６は、以上のようにして各エリア９１０における自動販売機３００の増減台数を求め、区割りの変更を行う。
【０１４０】
図２０（Ｂ）には、区割り変更部１０６が、エリア０（９１０）内の自動販売機３００のうちの２台がエリア１（９１０）の自動販売機３００になるように、エリア０（９１０）とエリア１（９１０）との間の区割りを変更すると共に、エリア０（９１０）の３台の自動販売機３００がエリア２（９１０）の自動販売機３００になるように、エリア０（９１０）とエリア２（９１０）との間の区割りを変更することが示されている。
【０１４１】
この時、区割り変更部１０６が、エリア０（９１０）内のどの自動販売機３００を他のエリア９１０に移動させるかを、図２１を参照しながら説明する。図２１は、エリア０（９１０）内の２つの自動販売機３００をエリア１（９１０）に移動させる様子を示す。
【０１４２】
区割り変更部１０６は、エリア１（９１０）に自動販売機３００を移動させる場合には、エリア１（９１０）内の各自動販売機の位置情報を平均して、エリア１（９１０）の重心位置（図２１に示す「重心１」）を計算する。そして、区割り変更部１０６は、エリア０（９１０）内の自動販売機３００の中から、エリア１（９１０）の重心位置（重心１）に近い順に自動販売機３００を２台選び出す（図２１（Ａ）のエリア０内の「３」「４」で示される自動販売機３００）。そして区割り変更部１０６は、この２台がエリア１（９１０）の自動販売機３００になるように、エリア０（９１０）とエリア１（９１０）との間の境界を変更する（図２１（Ｂ））。
【０１４３】
その後、巡回経路生成部１０４は、各エリア９１０の巡回経路を修正し、区割りの変更に対応した巡回経路を生成する。具体的には、巡回経路生成部１０４は、区割りの変更前に生成した各エリア９１０の巡回経路を、区割りの変更により追加された自動販売機３００を新たに経由し、区割りの変更により他のエリア９１０に移動した自動販売機３００を経由しないように修正する。
【０１４４】
例えば図２１に示す様に、巡回経路生成部１０４は、エリア０（９１０）については、エリア１（９１０）に移動した「３」「４」で示す自動販売機３００を経由しない様に、エリア０（９１０）の巡回経路を修正する。また巡回経路生成部１０４は、エリア１（９１０）については、エリア０（９１０）から移動してきた「３」「４」で示す自動販売機３００を経由する様に、エリア１（９１０）の巡回経路を修正する。
【０１４５】
このとき巡回経路生成部１０４は、区割り変更後の各エリア９１０について、再度、式（１）〜式（４）のコスト関数を計算し直して巡回経路の修正を行っても良いし、図２１に示す様に、他のエリア９１０に移動した自動販売機３００については、その自動販売機３００の前後の自動販売機３００を直接つなげるように巡回経路を修正し（エリア０（９１０）における「２」「５」を直接つなげる）、他のエリア９１０から移動してきた自動販売機３００については、その自動販売機３００との距離が最も近い自動販売機３００（エリア１（９１０）における「８」「９」）から経由するように巡回経路を修正しても良い。
【０１４６】
なお、区割り変更部１０６は、隣接しているエリア９１０同士でのみ自動販売機３００の所属エリア９１０の変更行う。
【０１４７】
そのため、例えば図２２に示す様に、エリア０（９１０）から自動販売機３００を１台減らし、エリア３（９１０）に自動販売機３００を１台増やす場合には、区割り変更部１０６は、エリア０（９１０）内の１台の自動販売機３００を、エリア０（９１０）とエリア３（９１０）の間に介在するエリア２（９１０）に移動するように区割りを変更し、エリア２（９１０）内の１台の自動販売機３００をエリア３（９１０）に移動するように区割りを変更するようにする。
【０１４８】
この結果、エリア０（９１０）、エリア２（９１０）、エリア３（９１０）における自動販売機３００の重心位置は、左上にずれる。
【０１４９】
このような態様により、各エリア９１０の巡回経路の経路長（移動距離）を短くすることが可能となる。
【０１５０】
なおこのような区割りの変更を行うために、区割り変更部１０６は、図２３に示す様に隣接エリア９１０を表現するグラフ構造を生成し、そして、このグラフ構造から図２４に示す様な全域木を生成して、全域木の辺に沿って自動販売機３００の移動（区割り変更）が行われるようにする。
【０１５１】
このような態様により、隣接エリア９１０間で自動販売機３００の移動を行う際に、自動販売機３００の移動がループして永遠に続いてしまう事態を回避することが可能となる。
【０１５２】
なお、図２３に示すグラフ構造及び図２４に示す全域木における各ノードは、各エリア９１０内の自動販売機３００の重心位置としている。
【０１５３】
またグラフ構造の生成方法や全域木の生成方法は公知の技術であるので詳しくは説明しないが、本実施形態では、ｋ平均法で距離を条件とした自動販売機３００のクラスタリングを行っているので、例えばグラフ構造を生成する際に、区割り変更部１０６は、各エリア９１０が隣接しているかどうかを、図２５に示すボロノイ図を作成するなどの数学的手法を用いて判断することができる。この場合、区割り変更部１０６は、任意の３つのエリア９１０を選択し、各エリア９１０の重心を外接円とした円を描く。そして区割り変更部１０６は、その円内に他のエリア９１０の重心が入っていない場合は、３つのエリア９１０が隣接しているものとして、各重心位置（ノード）を結ぶ。
【０１５４】
また区割り変更部１０６は、このようにして生成したグラフ構造から全域木を生成する際は、ダイクストラ法を使用する。
【０１５５】
以上のような方法により、全域木が生成できれば、上述したように、以下の処理が可能となる。
【０１５６】
まず、区割り変更部１０６は、式（５）〜（７）を用いて、各エリア９１０の巡回時間の超過/不足時間から、他エリア９１０とやりとりしたい自動販売機３００の数を求める。なおこのとき、過不足数の総和は、小数点以下を無視すれば理論上０になるはずである。
【０１５７】
次に区割り変更部１０６は、全域木の辺を通るように、各エリア９１０内の自動販売機３００を移動させる。また自動販売機３００を他のエリア９１０に移動させる際には、区割り変更部１０６は、移動先エリア９１０の重心位置に近い自動販売機３００を選択する。
【０１５８】
そして巡回経路生成部１０４は、区割り変更後の各エリア９１０における巡回経路を修正する。
【０１５９】
なおこの場合、巡回経路生成部１０４は、区割りが変更されたエリア９１０における自動販売機３００に対して再度コスト関数を計算して、巡回経路を生成しても良い。
【０１６０】
そして巡回経路生成部１０４は、全エリア９１０の巡回経路の巡回時間と平均値との差が一定以下（第１所定値以下）になるまでこの処理を繰り返すと良い。
【０１６１】
なお区割り変更部１０６は、各小地域９１０の巡回時間を平均値と比較して区割りの変更を行う他に、所定の基準値と比較して区割りの変更を行うようにしても良い。
【０１６２】
例えば区割り変更部１０６は、各小地域９１０を担当するルートマンの労働可能時間（ルートマン毎に異なっても良い）を所定の基準値として考慮して、巡回時間の労働可能時間に対する余裕時間が所定時間未満となっている小地域９１０に対しては、自動販売機３００の数を減らし、巡回時間の労働可能時間に対する余裕時間が所定時間以上となっている小地域９１０に対しては、自動販売機３００の数を増やすようにしても良い。そしてこの場合、各小地域９１０の巡回時間が労働可能時間以内、かつ、各ルートマンの上記余裕時間が所定時間未満となるまで、区割りの変更が繰り返される。
【０１６３】
＝＝処理の流れ＝＝
次に、本実施形態に係る巡回経路生成装置１００による処理の流れを、図２６及び図２７に示すフローチャートを参照しながら説明する。
【０１６４】
まず巡回経路生成装置１００は、各自動販売機３００から稼働情報を収集する（S2000）。そして巡回経路生成装置１００は、緊急度管理テーブル６１０を参照し、各自動販売機３００の稼働情報を元に巡回の緊急度を特定する（S2010）。
【０１６５】
一方、巡回経路生成装置１００は、ｋ平均法等のクラスタリング手法を用いて巡回地域９００を、地域的なまとまりを持った複数の小地域（エリア）９１０に分割する（S2020）。
【０１６６】
そして巡回経路生成装置１００は、各エリア９１０に対して巡回経路を生成する（S2030）。具体的には、巡回経路生成装置１００は、例えばシミュレーテッドアニーリング法を用いることで巡回経路の複数の候補を生成する。そして巡回経路生成装置１００は、これら複数の候補に対して、各自動販売機３００の緊急度と巡回の順序とを元に算出される第１指標値と、各自動販売機３００を巡回するための移動距離に関する第２指標値と、を算出し、第１指標値及び第２指標値の算出結果を元に複数の候補の中から一つの候補を選出することにより、巡回経路を生成する。
【０１６７】
次に巡回経路生成装置１００は、上述した式（５）〜式（７）を用いて、各エリア９１０の区割りを変更する（S2040）。
【０１６８】
そして巡回経路生成装置１００は区割りの変更に対応すべく、各エリア９１０の巡回経路を修正する（S2050）。
【０１６９】
その後、巡回経路生成装置１００は、再度各エリア９１０の巡回経路について式（５）〜式（７）を用いて巡回時間を計算し、全エリア９１０の巡回時間と平均値との差が第１所定値以内になるまで区割りの変更及び巡回経路の修正を繰り返す（S2040〜S2060）。
【０１７０】
全エリア９１０の巡回時間と平均値との差が第１所定値以内になったら、巡回経路生成装置１００は巡回経路を出力し、ルートマンに提示する（S2070）。例えば巡回経路生成装置１００は、液晶ディスプレイ等の出力装置１６０に地図を表示し、この地図の上に重ねて、各自動販売機３００の位置と巡回経路とを表示する。あるいは巡回経路生成装置１００は、ルートマンが携帯するノートパソコン等の携帯端末（不図示）に地図を表示し、この地図の上に重ねて、各自動販売機３００の位置と巡回経路とを表示するようにしても良い。
【０１７１】
その後、ルートマンは各自の担当するエリア９１０内の自動販売機３００をそれぞれの巡回経路に沿って回るため、以下の処理は、各エリア９１０毎に独立した処理となるが、説明の都合上、ある一つのエリア９１０内の巡回経路に対する処理を継続して説明する。
【０１７２】
まず巡回経路生成装置１００は、いずれかの自動販売機３００から新たな稼働情報を受信していないかどうかを確認する（S2080）。新たな稼働情報を受信していなければ、巡回経路生成装置１００は、S2080において「Ｎｏ」に進む。
【０１７３】
この状態で、自動販売機３００を巡回中のルートマンが、自動販売機３００のメンテナンスが１カ所完了する毎に、自動販売機３００あるいはルートマンが携帯する不図示の携帯端末から、巡回経路生成装置１００に自販機ＩＤとともに巡回が完了した旨の通知が送信されてくる。
【０１７４】
巡回経路生成装置１００は、この通知を受領すると（S2090）、図７に示す巡回管理テーブル６２０の該当する自動販売機３００に対応する欄に巡回完了日時を記録する（S2100）。
【０１７５】
巡回経路生成装置１００は、巡回管理テーブル６２０を参照して、全ての自動販売機３００の巡回が完了したかどうかをチェックし（S2110）、全ての自動販売機３００の巡回が完了していたら、処理を終了する。
【０１７６】
一方、未巡回の自動販売機３００がある場合には、巡回経路生成装置１００は、S2110において「Ｎｏ」に進み、S2080に戻る。
【０１７７】
巡回経路生成装置１００は、S2080において、いずれかの自動販売機３００から新たな稼働情報を受信した場合には、緊急度管理テーブル６１０を参照し、新たな稼働情報を送信してきた自動販売機３００の緊急度を特定する（S2120）。
【０１７８】
そして新たな稼働情報を送信してきた自動販売機３００の緊急度の上昇量が所定値（第２所定値）以上（例えば緊急度が２以上上昇）である場合には（S2130）、巡回経路生成装置１００は新たな巡回経路を生成する（S2140）。
【０１７９】
巡回経路生成装置１００は、新たな巡回経路を生成する際には、巡回管理テーブル６２０を参照し、未巡回の自動販売機３００を特定し、この未巡回の自動販売機３００と、緊急度が第２所定値以上上昇した自動販売機３００と、のみを巡回するような巡回経路を新たに生成する（S2140）。そして巡回経路生成装置１００は、新たに生成した巡回経路をルートマンに提示する（S2150）。例えば巡回経路生成装置１００は、ルートマンが携帯する不図示の携帯端末に新たな巡回経路を表示する。
【０１８０】
なお巡回経路生成装置１００は、新たな巡回経路を生成する場合、緊急度が第２所定値以上上昇した自動販売機３００が未巡回であった場合には、他の未巡回の自動販売機３００を含め、全て未巡回の自動販売機３００のみを巡回するように、新たな巡回経路を生成することができる。一方、緊急度が第２所定値以上上昇した自動販売機３００が巡回済みであった場合には、他の未巡回の自動販売機３００のみならず、緊急度が所定以上上昇した自動販売機３００も再度巡回するように、新たな巡回経路を生成することができる。
【０１８１】
このような態様により、緊急度が第２所定値以上上昇した自動販売機３００に対しては、その自動販売機３００をより優先的に巡回するように巡回経路を変更できる。
【０１８２】
一方、新たな稼働情報を送信してきた自動販売機３００の緊急度の上昇量が第２所定値以上でない場合には（S2130）、巡回経路生成装置１００は、S2160に進み、その自動販売機３００の緊急度の低下量が第２所定値以上（例えば緊急度が２以上低下）であるかどうかを判定する（S2160）。
【０１８３】
そしてこの自動販売機３００の緊急度の低下量が第２所定値未満の場合には（S2160）、巡回経路生成装置１００はS2080に戻り、巡回経路を変更せずに処理を継続する。このような態様により、緊急度の変化量が第２所定値未満（例えば±２未満）の場合は、それまでの巡回経路を継続的に巡回することができ、ルートマンの巡回作業の効率低下を防止することができる。
【０１８４】
一方、新たな稼働情報を送信してきた自動販売機３００の緊急度の低下量が第２所定値以上（例えば緊急度が２以上低下）である場合には（S2160）、巡回経路生成装置１００はS2170に進み、その自動販売機３００が未巡回であるか否かを判定する（S2170）。
【０１８５】
もしその自動販売機３００が巡回済みであれば、その緊急度が低下した自動販売機３００を再度訪問する必要はないため、巡回経路生成装置１００はS2080に戻り、巡回経路を変更せずに処理を継続する。このような態様により、緊急度が第２所定値以上低下した自動販売機３００が巡回済みの場合は、それまでの巡回経路を継続的に巡回し、ルートマンの巡回作業の効率低下を防止することができる。
【０１８６】
一方、緊急度が第２所定値以上低下した自動販売機３００が未巡回である場合には（S2170）、巡回経路生成装置１００は、新たな巡回経路を生成する（S2180）。
【０１８７】
このとき、巡回経路生成装置１００は、巡回管理テーブル６２０を参照し、未巡回の自動販売機３００を特定し、この未巡回の自動販売機３００のみを巡回するような巡回経路を新たに生成する（S2180）。
【０１８８】
このような態様により、緊急度が第２所定値以上低下した未巡回の自動販売機３００に対しては、その自動販売機３００に対する巡回の優先度を下げ、他のより緊急性の高い未巡回の自動販売機３００を先に巡回するように巡回経路を変更することが可能となる。
【０１８９】
なおS2140やS2180において巡回経路生成装置１００が新たな巡回経路を生成する際には、巡回経路生成装置１００は、巡回管理テーブル６２０に記録されている日時情報を元に、ルートマンが最後に訪問した自動販売機３００を特定し、この自動販売機３００の位置（あるいはその次に訪問予定であった自動販売機３００の位置でもよい）をルートマンの現在位置として推定し、このルートマンの現在位置を起点として新たな巡回経路を生成する。あるいは、ルートマンが携帯する携帯端末がＧＰＳ信号を受信可能であり、現在位置情報を随時取得可能である場合には、巡回経路生成装置１００は携帯端末からルートマンの現在位置情報を取得して新たな巡回経路の起点としても良い。
【０１９０】
以上、第１実施形態及び第２実施形態について説明したが、本実施形態に係る巡回経路生成装置１００及び巡回経路生成方法及びプログラムによれば、各地に設けられる自動販売機３００などの設備を巡回する際の巡回経路を、各設備の稼働状態を考慮してより適切に生成することが可能となる。
【０１９１】
なお上述した実施の形態は本発明の理解を容易にするためのものであり、本発明を限定して解釈するためのものではない。本発明はその趣旨を逸脱することなく変更、改良され得るとともに、本発明にはその等価物も含まれる。
【０１９２】
例えば、巡回経路の生成対象は自動販売機３００に限らず、各地に設置される機械や工場、さらには農業用給水タンクなどでもよい。農業用給水タンクに対する巡回経路を生成する場合は、巡回経路生成装置１００は、例えば各農業用給水タンクから残水量を稼働情報として収集するようにすればよい。
【符号の説明】
【０１９３】
１００    巡回経路生成装置
１０１    稼働情報収集部
１０２    緊急度特定部
１０３    巡回状態記憶部
１０４    巡回経路生成部
１０５    地域分割部
１０６    区割り変更部
１０７    候補生成部
１１０    ＣＰＵ
１２０    メモリ
１３０    通信装置
１４０    記憶装置
１５０    入力装置
１６０    出力装置
１７０    記録媒体読取装置
３００    自動販売機
３１０    主制御部
３１１    ＣＰＵ
３１２    ＲＯＭ
３１３    ＲＡＭ
３１４    通信装置
３２０    コインメック
３２１    硬貨処理制御部
３２２    硬貨投入機構
３３０    ビルバリ
３３１    紙幣処理制御部
３３２    紙幣挿入機構
３４１    自動販売制御部
３４２    自動販売機構
５００    ネットワーク
６００    自動販売機管理テーブル
６１０    緊急度管理テーブル
６２０    巡回管理テーブル
６３０    エリア管理テーブル
７００    巡回経路生成装置制御プログラム
８００    記録媒体
９００    地域
９１０    小地域
１０００  自動販売機管理システム
【図１】
2019096100.tif 000003
【図２】
2019096100.tif 000004
【図３】
2019096100.tif 000005
【図４】
2019096100.tif 000006
【図５】
2019096100.tif 000007
【図６】
2019096100.tif 000008
【図７】
2019096100.tif 000009
【図８】
2019096100.tif 000010
【図９】
2019096100.tif 000011
【図１０】
2019096100.tif 000012
【図１１】
2019096100.tif 000013
【図１２】
2019096100.tif 000014
【図１３】
2019096100.tif 000015
【図１４】
2019096100.tif 000016
【図１５】
2019096100.tif 000017
【図１６】
2019096100.tif 000018
【図１７】
2019096100.tif 000019
【図１８】
2019096100.tif 000020
【図１９】
2019096100.tif 000021
【図２０】
2019096100.tif 000022
【図２１】
2019096100.tif 000023
【図２２】
2019096100.tif 000024
【図２３】
2019096100.tif 000025
【図２４】
2019096100.tif 000026
【図２５】
2019096100.tif 000027
【図２６】
2019096100.tif 000028
【図２７】
2019096100.tif 000029