(57)【要約】【課題】複数の地点を巡回する担当者が所定の時間で戻って来られるような巡回経路を生成する。【解決手段】複数の巡回対象地点のうちの少なくとも一部の地点を巡回する巡回経路を生成する巡回経路生成装置であって、前記巡回経路の複数の候補を生成する候補生成部と、前記複数の候補のそれぞれに対して、巡回を開始してから終了するまでの所要時間と所定の目標時間とのずれの度合いを示す第１指標値と、経路長を示す第２指標値と、を算出し、前記第１指標値及び前記第２指標値の算出結果に基づいて前記複数の候補の中から一つの候補を選出することにより、前記巡回経路を生成する巡回経路生成部と、を備える。【選択図】図１
2020016944.tif 000002
【特許請求の範囲】
【請求項１】
複数の巡回対象地点のうちの少なくとも一部の地点を巡回する巡回経路を生成する巡回経路生成装置であって、
前記巡回経路の複数の候補を生成する候補生成部と、
前記複数の候補のそれぞれに対して、巡回を開始してから終了するまでの所要時間と所定の目標時間とのずれの度合いを示す第１指標値と、経路長を示す第２指標値と、を算出し、前記第１指標値及び前記第２指標値の算出結果に基づいて前記複数の候補の中から一つの候補を選出することにより、前記巡回経路を生成する巡回経路生成部と、
を備える巡回経路生成装置。
【請求項２】
請求項１に記載の巡回経路生成装置であって、
前記巡回対象の各地点における巡回の緊急度を表す緊急度情報を記憶する緊急度情報記憶部と、
を備え、
前記巡回経路生成部は、前記複数の候補のそれぞれに対して、緊急度が高い地点が優先的に巡回される度合いを表す第３指標値をさらに算出し、前記第１指標値、前記第２指標値、及び前記第３指標値に基づいて前記複数の候補の中から一つの候補を選出することにより前記巡回経路を生成する、巡回経路生成装置。
【請求項３】
請求項１に記載の巡回経路生成装置であって、
前記巡回対象の各地点にはそれぞれ設備が設けられており、
前記各設備における物資の補充可能量を記憶する補充可能量記憶部、
を備え、
前記巡回経路生成部は、前記複数の候補のそれぞれに対して、経路内の各設備の前記補充可能量の総量を示す第４指標値をさらに算出し、前記第１指標値、前記第２指標値、及び第４指標値の算出結果に基づいて前記複数の候補の中から一つの候補を選出することにより前記巡回経路を生成する、巡回経路生成装置。
【請求項４】
請求項１に記載の巡回経路生成装置であって、
前記巡回対象の各地点にはそれぞれ設備が設けられており、
前記巡回対象の各地点における巡回の緊急度を表す緊急度情報を記憶する緊急度情報記憶部と、
前記各設備における物資の補充可能量を記憶する補充可能量記憶部と、
を備え、
前記巡回経路生成部は、前記複数の候補のそれぞれに対して、緊急度が高い地点が優先的に巡回される度合いを表す第３指標値、及び経路内の各設備の前記補充可能量の総量を示す第４指標値をさらに算出し、前記第１指標値、前記第２指標値、前記第３指標値、及び第４指標値の算出結果に基づいて前記複数の候補の中から一つの候補を選出することにより前記巡回経路を生成する、巡回経路生成装置。
【請求項５】
請求項１〜４のいずれかに記載の巡回経路生成装置であって、
前記巡回対象の各地点を、必ず巡回するべき巡回必須地点と、必ずしも巡回しなくて良い巡回任意地点と、に分類する地点分類部と、
を備え、
前記候補生成部は、全ての前記巡回必須地点を経路に含むように前記複数の候補を生成する、巡回経路生成装置。
【請求項６】
請求項５に記載の巡回経路生成装置であって、
前記巡回必須地点を指定する情報の入力を受け付けるユーザインタフェースを備え、
前記地点分類部は、前記情報によって指定される地点を前記巡回必須地点に分類し、前記巡回必須地点に分類されない地点を前記巡回任意地点に分類する、巡回経路生成装置。
【請求項７】
請求項５に記載の巡回経路生成装置であって、
前記巡回対象の各地点に対して巡回が行われていない期間を特定可能な巡回履歴情報を記憶する巡回履歴情報記憶部と、
を備え、
前記地点分類部は、前記巡回履歴情報を参照し、前回の巡回からの経過期間が所定期間以上である地点を前記巡回必須地点に分類し、前記巡回必須地点に分類されない地点を前記巡回任意地点に分類する、巡回経路生成装置。
【請求項８】
請求項７に記載の巡回経路生成装置であって、
前記所定期間を示す情報の入力を受け付けるユーザインタフェースを備える、巡回経路生成装置。
【請求項９】
請求項５に記載の巡回経路生成装置であって、
前記巡回対象の各地点にはそれぞれ設備が設けられており、
前記巡回対象の各地点に対して巡回が行われていない期間を特定可能な巡回履歴情報を記憶する巡回履歴情報記憶部と、
前記各設備における物資の残量を示す残量情報を記憶する残量情報記憶部と、
を備え、
前記地点分類部は、前記巡回履歴情報及び前記残量情報を参照し、前回の巡回からの経過期間が所定期間以上である地点、又は前記物資の残量が所定量以下である設備が設けられている地点を前記巡回必須地点に分類し、前記巡回必須地点に分類されない地点を前記巡回任意地点に分類する、巡回経路生成装置。
【請求項１０】
請求項５に記載の巡回経路生成装置であって、
前記巡回対象の各地点にはそれぞれ設備が設けられており、
前記巡回対象の各地点に対して巡回が行われていない期間を特定可能な巡回履歴情報を記憶する巡回履歴情報記憶部と、
前記各設備における物資の残量を示す残量情報を記憶する残量情報記憶部と、
前記地点分類部に対して、巡回が行われていない期間が所定期間以上である地点を前記巡回必須地点に分類させるための第1情報、又は、前記物資の残量が所定量以下である設備が設けられている地点を前記巡回必須地点に分類させるための第２情報の入力を受け付けるユーザインタフェースと、
を備え、
前記地点分類部は、前記第１情報が入力されている場合には、前回の巡回からの経過期間が所定期間以上である地点を前記巡回必須地点に分類し、前記第２情報が入力されている場合には、前記物資の残量が所定量以下である設備が設けられている地点を前記巡回必須地点に分類し、前記巡回必須地点に分類されない地点を前記巡回任意地点に分類する、巡回経路生成装置。
【請求項１１】
請求項９又は１０に記載の巡回経路生成装置であって、
前記所定期間を示す情報及び前記所定量を示す情報の入力を受け付けるユーザインタフェースを備える、巡回経路生成装置。
【請求項１２】
請求項５〜１１のいずれかに記載の巡回経路生成装置であって、
前記巡回経路生成部は、前記複数の候補のそれぞれに対して、前記所要時間が前記目標時間よりも長い場合は、前記所要時間と前記目標時間との時間差と、経路に含まれる前記巡回任意地点の数と、の積を前記第１指標値として算出し、前記所要時間が前記目標時間以下の場合は、所定値を前記第１指標値とする、巡回経路生成装置。
【請求項１３】
請求項１２に記載の巡回経路生成装置であって、
前記所定値は０である、巡回経路生成装置。
【請求項１４】
請求項５〜１１のいずれかに記載の巡回経路生成装置であって、
前記巡回経路生成部は、前記複数の候補のそれぞれに対して、前記所要時間が前記目標時間よりも長い場合は、前記所要時間と前記目標時間との時間差と、経路に含まれる前記巡回任意地点の数と、の積を前記第１指標値として算出し、前記所要時間が前記目標時間以下の場合は、前記時間差と、経路に含まれない前記巡回任意地点の数と、の積を前記第１指標値として算出する、巡回経路生成装置。
【請求項１５】
請求項５〜１４のいずれかに記載の巡回経路生成装置であって、
前記候補生成部は、前記巡回対象の全地点の中から、全ての前記巡回必須地点を含むように複数の地点を選択した上で、前記複数の地点を所定の順序で並べることにより巡回経路の第１候補を生成した後、前記第１候補に含まれる地点の中から選択した２つの地点の順序を入れ替えることにより第２候補を生成する第１処理か、前記第１候補に含まれる前記巡回任意地点から選択した地点を前記第１候補の巡回経路から削除することにより第２候補を生成する第２処理か、前記第１候補に含まれない前記巡回任意地点から選択した地点を前記第１候補の巡回経路に組み込むことにより第２候補を生成する第３処理か、のいずれかの処理を選択して実行し、その後、前記処理において生成された前記第２候補を前記第１候補として新たに第２候補を生成する処理を、前記第１〜第３処理のいずれかを選択しながら繰り返し実行することにより、前記複数の候補を生成する、巡回経路生成装置。
【請求項１６】
請求項１５に記載の巡回経路生成装置であって、
前記候補生成部は、前記第３処理において、前記第１候補に含まれない前記巡回任意地点から選択した前記地点を前記第１候補の巡回経路に追加して前記第２候補を生成する際に、前記地点を追加することによる経路長の増加量が最小となるように前記地点を追加する、巡回経路生成装置。
【請求項１７】
請求項１〜１６のいずれかに記載の巡回経路生成装置であって、
前記目標時間の入力を受け付けるユーザインタフェースをさらに備える、巡回経路生成装置。
【請求項１８】
請求項１〜１７のいずれかに記載の巡回経路生成装置であって、
前記巡回経路生成部によって生成された前記巡回経路を出力するユーザインタフェースをさらに備える、巡回経路生成装置。
【請求項１９】
複数の巡回対象地点のうちの少なくとも一部の地点を巡回する巡回経路を生成する巡回経路生成装置の制御方法であって、
前記巡回経路生成装置が、
前記巡回経路の複数の候補を生成し、
前記複数の候補のそれぞれに対して、巡回を開始してから終了するまでの所要時間と所定の目標時間とのずれの度合いを示す第１指標値と、経路長を示す第２指標値と、を算出し、前記第１指標値及び前記第２指標値の算出結果に基づいて前記複数の候補の中から一つの候補を選出することにより、前記巡回経路を生成する、
巡回経路生成装置の制御方法。
【請求項２０】
複数の巡回対象地点のうちの少なくとも一部の地点を巡回する巡回経路を生成するコンピュータに、
前記巡回経路の複数の候補を生成する手順と、
前記複数の候補のそれぞれに対して、巡回を開始してから終了するまでの所要時間と所定の目標時間とのずれの度合いを示す第１指標値と、経路長を示す第２指標値と、を算出し、前記第１指標値及び前記第２指標値の算出結果に基づいて前記複数の候補の中から一つの候補を選出することにより、前記巡回経路を生成する手順と、
を実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、巡回経路生成装置、巡回経路生成方法、及びプログラムに関する。
【背景技術】
【０００２】
今日、様々な場所に自動販売機が設置されており、日々の生活を便利なものにしている。一方で、自動販売機は商品の補充や釣銭の回収、清掃、修理などのメンテナンスが欠かせない。そのため、日々、数多くの作業員が各地の自動販売機を巡回している。
【０００３】
そして、このような各地に点在する自動販売機を巡回する際の巡回経路の生成を支援し、自動販売機のメンテナンスの効率化を図るための技術も開発されている（例えば特許文献１参照）。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２００２−０４２２１７号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
このようにして生成される巡回経路は、各地に点在する自動販売機をなるべく短い移動距離で効率的に巡回するように生成されるが、作業員が巡回を終了して戻って来られる時間は、生成される巡回経路によって変動する。そのため、作業員の勤務時間や勤務先の営業時間等に合うように修正する必要がある。
【０００６】
またこのことは、自動販売機等の設備を巡回する場合だけでなく、営業担当者が複数の顧客を訪問する場合のように、設備がない複数の地点を巡回する場合でも同様である。
【０００７】
本発明はこのような課題を鑑みてなされたものであり、複数の地点を巡回する担当者が所定の時間で戻って来られるような巡回経路を生成することが可能な巡回経路生成装置、巡回経路生成方法及びプログラムを提供する。
【課題を解決するための手段】
【０００８】
上記目的を達成するための本発明の一つは、複数の巡回対象地点のうちの少なくとも一部の地点を巡回する巡回経路を生成する巡回経路生成装置であって、前記巡回経路の複数の候補を生成する候補生成部と、前記複数の候補のそれぞれに対して、巡回を開始してから終了するまでの所要時間と所定の目標時間とのずれの度合いを示す第１指標値と、経路長を示す第２指標値と、を算出し、前記第１指標値及び前記第２指標値の算出結果に基づいて前記複数の候補の中から一つの候補を選出することにより、前記巡回経路を生成する巡回経路生成部と、を備える。
【０００９】
その他、本願が開示する課題、及びその解決方法は、発明を実施するための形態の欄の記載、及び図面の記載等により明らかにされる。
【発明の効果】
【００１０】
本発明によれば、複数の地点を巡回する担当者が所定の時間で戻って来られるような巡回経路を生成することが可能となる。
【図面の簡単な説明】
【００１１】
【図１】巡回経路生成システムの概略的な構成を示す図である。
【図２】自動販売機の構成を示すブロック図である。
【図３】自動販売機が備える機能を示す図である。
【図４】巡回経路生成装置の構成を示すブロック図である。
【図５】巡回経路生成装置が備える機能を示す図である。
【図６】拠点情報の一例である。
【図７】自動販売機情報の一例である。
【図８】現在経路情報の一例である。
【図９】次経路情報の一例である。
【図１０】巡回経路生成装置の処理の流れを説明するフローチャートである。
【図１１】巡回経路生成装置の処理の流れを説明するフローチャートである。
【発明を実施するための形態】
【００１２】
以下、実施形態について図面を参照しつつ詳細に説明する。
【００１３】
＝＝全体構成＝＝
図１に、実施形態として示す巡回経路生成システム１の概略的な構成を示す。巡回経路生成システム１は、複数地点（図１には一例として１１カ所）に設けられる自動販売機２と、巡回経路生成装置１０と、が通信ネットワーク５（図１には不図示）を介して通信可能に接続されて構成されている。通信ネットワーク５はインターネットやＬＡＮ（Local Area Network）、電話網等の各種の情報通信網である。
【００１４】
自動販売機２は、利用者から所定金額の金銭が投入されると、飲料や食品などの各種商品を利用者に提供する設備ないし装置である。
【００１５】
巡回経路生成装置１０は、自動販売機２のメンテナンスを行う作業員が各地の自動販売機２を巡回する際の巡回経路を生成する情報処理装置である。巡回経路生成装置１０は、後述する本実施形態に係る経路探索アルゴリズムを実行することにより、この巡回経路を生成する。巡回経路生成装置１０は、作業員の職場や営業所などの拠点３を起点及び終点として、総移動距離がなるべく短く、かつ、巡回を開始してから終了するまでの所要時間が所定の目標時間になるような巡回経路を生成する。
【００１６】
このような態様により、例えば、作業員の勤務時間や勤務先の営業時間等に合った適切な巡回経路を生成することが可能となる。
【００１７】
なおこのために、本実施形態に係る巡回経路生成装置１０は、巡回対象の全ての自動販売機２（図１では１１台）を巡回する巡回経路を生成する訳ではなく、そのうちの少なくとも一部の自動販売機２を巡回する巡回経路を生成する。図１に点線で示す巡回経路の場合、作業員は５台の自動販売機２を巡回する。
【００１８】
また本実施形態では、各地に設置される自動販売機２等の設備を作業員が巡回して商品等の物資を補給する際の巡回経路を巡回経路生成装置１０が生成する場合を例に説明するが、営業担当者が複数の顧客を訪問する場合や、水田の監視員が各地の水田の水位を計測する場合のように、設備がない複数の地点を巡回する際の巡回経路を生成する場合も同様である。
【００１９】
＝＝自動販売機＝＝
図２は自動販売機２の主な構成を示すブロック図である。図２に示すように、自動販売機２は、プロセッサ２１、記憶装置２２、通信装置２３、販売制御機構２４、金銭受付機構２５、及び商品残量検出機構２６を備える。
【００２０】
プロセッサ２１は、例えば、ＣＰＵ（Central Processing Unit）やＭＰＵ（Micro Processing Unit）を用いて構成される。記憶装置２２は、プログラムやデータを記憶する装置であり、例えば、ＲＯＭ（Read Only Memory）、ＲＡＭ（Random Access Memory）、不揮発性半導体メモリ（ＮＶＲＡＭ（Non Volatile RAM））等である。プロセッサ２１及び記憶装置２２は、自動販売機２の統括的な制御を行う主制御部を構成する。プロセッサ２１及び記憶装置２２は、例えば、通信装置２３を介して提供される仮想的な情報処理資源（例えば、クラウドシステム（Cloud System）により提供されるクラウドサーバ（Cloud Server）等）を用いて実現されるものであってもよい。
【００２１】
通信装置２３は、例えば、無線通信モジュール、ＮＩＣ（Network Interface Card）等を用いて構成される。通信装置２３は、通信ネットワーク５を介した巡回経路生成装置１０等の他の装置との間の通信を実現する。通信装置２３は、他の装置から情報を受け付ける入力装置として機能させることもできる。
【００２２】
販売制御機構２４は、機械式機構や電子回路等を用いて構成され、自動販売機２の利用者に商品を提供する際に制御される機構を含む。販売制御機構２４は、例えば、自動販売機２の内部の商品棚や商品排出機構、自動販売機２の外部の商品選択ボタンや代金支払い用ＩＣカードのリーダライタ、各種表示ランプ、ディスプレイ等を含む。
【００２３】
金銭受付機構２５は、硬貨選別機（コインメック）や紙幣選別機（ビルバリ）としての機構を含み、例えば、利用者が投入する硬貨や紙幣の受け入れ、選別、貯留、自動販売機２内に釣銭用に保有する硬貨や紙幣の枚数の制御等を行う。
【００２４】
商品残量検出機構２６は、自動販売機２の商品残量を検出する。商品残量検出機構２６は、例えば、機械式または電子式の残量計数機構、光学式センサ、感圧センサ等を用いて構成される。商品残量検出機構２６は、自動販売機２が販売する商品の性質に応じた種々の構成を取り得る。
【００２５】
図３に自動販売機２が備える主な機能を示す。図３に示すように、自動販売機２は、記憶部２１０、販売制御処理部２１１、金銭受付処理部２１２、商品残量取得部２１３、商品補充可能量算出部２１４、緊急度算出部２１５及び通信処理部２１６の各機能を備える。
【００２６】
自動販売機２の機能は、例えば、自動販売機２が備える機構によって実現される。また自動販売機２の機能は、例えば、プロセッサ２１が、記憶装置２２に格納されているプログラムを読み出して実行することにより実現される。上記のプログラムは、例えば、可搬型記録媒体（ＣＤ（Compact Disc）、ＤＶＤ（Digital Versatile Disc）、フラッシュメモリ等）から図示しない可搬型記録媒体の読取装置を介して記憶装置２２にロードされる。また上記のプログラムは、例えば、上記プログラムを蓄積管理する図示しない配信装置から通信ネットワーク５を介して自動販売機２にダウンロードされる。
【００２７】
上記機能のうち、記憶部２１０は、当該自動販売機２の現在の商品の残量である商品残量２５１、当該自動販売機２の在庫可能最大量である在庫可能最大量２５２、当該自動販売機２における商品の補充可能量である商品補充可能量２５３、当該自動販売機２に巡回が行われた日時を示す巡回日時２５４、及び当該自動販売機２への巡回の緊急度を示す緊急度２５５の各情報を記憶する。巡回日時２５４は、自動販売機２に対するメンテナンスが行われた際に作業員が設定する。あるいは巡回日時２５４は、巡回時にリセットされて所定時間ごとにカウントアップあるいはカウントダウンするタイマーカウンタの値等、巡回が行われてからの経過期間ないしは巡回が行われていない期間を特定可能な情報であればどのような情報でもよい。緊急度２５５は、例えば０〜９の範囲の値をとり、自動販売機２に故障が発生した場合や、つり銭切れ、商品の残量が所定値以下になった場合など、自動販売機２のメンテナンスをより早く行った方が良い場合に、より大きな値になるように設定される。
【００２８】
尚、記憶部２１０が記憶するこれらの情報は、通信ネットワーク５を介して巡回経路生成装置１０の自動販売機情報１５２（後述）とリアルタイムにもしくは随時（定期的等）に共有される。記憶部２１０が記憶するこれらの情報は巡回経路生成装置１０において管理してもよいが、例えば、個々の自動販売機２においてこれらの情報を個別に管理し、巡回経路生成装置１０が随時これらの情報を自動販売機２から取得するようにしてもよい。このようにすることで、自動販売機２の増減設時の管理が容易になる。
【００２９】
販売制御処理部２１１は、販売制御機構２４を制御し、自動販売機２の利用者への商品の提供に関する処理を行う。また販売制御処理部２１１は、販売制御機構２４の故障を検知した場合には、故障内容を緊急度算出部２１５に通知する。金銭受付処理部２１２は、金銭受付機構２５に投入された硬貨や紙幣の真偽の判別、硬貨や紙幣を種類別に選別するための制御、紙幣や硬貨の数の検出等の制御を行う。また金銭受付処理部２１２は、つり銭切れや、金銭受付機構２５の故障を検知した場合には、その旨を緊急度算出部２１５に通知する。
【００３０】
商品残量取得部２１３は、商品残量検出機構２６を介して商品残量を取得する。商品残量取得部２１３が取得した商品残量は記憶部２１０が商品残量２５１として記憶する。商品残量取得部２１３は、商品の残量が所定量以下になったことを検知した場合や、商品の減少速度（単位期間あたりの商品販売量）が所定値以上である場合、商品残量検出機構２６の故障を検知した場合には、その旨を緊急度算出部２１５に通知する。
【００３１】
商品補充可能量算出部２１４は、記憶部２１０が記憶している在庫可能最大量２５２と商品残量２５１とに基づき商品補充可能量を求める。本実施形態では、商品補充可能量算出部２１４は、在庫可能最大量２５２と商品残量２５１の差を商品補充可能量として求める。上記の在庫可能最大量２５２は、例えば、自動販売機２の管理者等が通信装置２３を介して設定する。巡回経路生成装置１０が通信ネットワーク５を介して上記の在庫可能最大量２５２を設定するようにしてもよい。商品補充可能量算出部２１４が求めた商品補充可能量は記憶部２１０が商品補充可能量２５３として記憶する。商品補充可能量算出部２１４の機能は巡回経路生成装置１０側で実現するようにしてもよい。
【００３２】
緊急度算出部２１５は、販売制御処理部２１１、金銭受付処理部２１２、及び商品残量取得部２１３から、上述した故障やつり銭切れ等の通知を受けた場合に、通知の内容に応じて緊急度２５５の値を設定する。緊急度算出部２１５は、上記通知の内容と緊急度２５５の値を対応付けた不図示のテーブルを参照することにより、緊急度２５５の値を設定する。緊急度２５５は０〜９であり、値が大きいほど緊急度が高いことを示す。
【００３３】
通信処理部２１６は、通信ネットワーク５を介して巡回経路生成装置１０と通信し、記憶部２１０が記憶する情報等の様々な情報を巡回経路生成装置１０との間で送信または受信する。
【００３４】
＝＝巡回経路生成装置＝＝
図４は巡回経路生成装置１０の主な構成を示すブロック図である。図４に示すように、巡回経路生成装置１０は、プロセッサ１１、主記憶装置１２、補助記憶装置１３、入力装置１４、出力装置１５、及び通信装置１６を備える。これらは図示しないバス等の通信手段を介して互いに通信可能に接続されている。
【００３５】
巡回経路生成装置１０は、例えば、仮想サーバやクラウドシステムにおけるクラウドサーバのように仮想的なリソースを用いて実現されるものでもよい。また巡回経路生成装置１０は、例えば、通信可能に接続された複数の情報処理装置やプロセッサによって実現してもよい。
【００３６】
プロセッサ１１は、例えば、ＣＰＵ、ＭＰＵ、ＧＰＵ（Graphics Processing Unit）等を用いて構成されている。プロセッサ１１が、主記憶装置１２に格納されている本実施形態に係るプログラムを読み出して実行することにより、巡回経路生成装置１０の様々な機能が実現される。主記憶装置１２は、プログラムやデータを記憶する装置であり、例えば、ＲＯＭ、ＲＡＭ、不揮発性半導体メモリ等である。
【００３７】
補助記憶装置１３は、例えば、ハードディスクドライブ、半導体メモリ（ＳＳＤ、ＳＤメモリカード、ＵＳＢメモリ等）、光学式記憶装置（ＣＤ、ＤＶＤ等）の読取／書込装置等）、クラウドサーバの記憶領域等である。補助記憶装置１３に格納されているプログラムやデータは主記憶装置１２に随時ロードされる。補助記憶装置１３は、例えば、ＮＡＳ（Network Attached Storage）のように通信手段を介してプロセッサ１１と通信可能に接続するものであってもよい。
【００３８】
入力装置１４は、外部からの入力を受け付けるユーザインタフェースであり、例えば、キーボード、マウス、タッチパネル、可搬型記録媒体の読取装置等である。出力装置１５は、処理経過や処理結果等の各種情報を外部に提供するユーザインタフェースであり、例えば、画面表示装置（ＬＣＤ（Liquid Crystal Display）、ＧＰＵ等）、印字装置、可搬型記録媒体の書込装置等である。
【００３９】
通信装置１６は、通信ネットワーク５を介して行われる他の装置との間の通信を実現する有線方式または無線方式の通信インタフェースであり、例えば、無線通信モジュールやＮＩＣ等である。尚、例えば、通信装置１６を介して他の装置との間で情報の入力や出力を行う構成、即ち通信装置１６が入力装置１４や出力装置１５として機能する構成としてもよい。
【００４０】
図５に巡回経路生成装置１０が備える主な機能を示す。図５に示すように、巡回経路生成装置１０は、記憶部１１０、通信処理部１１１、経路探索処理部１１２の各機能を備える。
【００４１】
巡回経路生成装置１０の各機能は、例えば、プロセッサ１１が主記憶装置１２に格納されているプログラムを読み出して実行することにより実現される。上記のプログラムは、例えば、可搬型記録媒体から入力装置１４を介して主記憶装置１２にロードされる。また上記のプログラムは、例えば、上記プログラムを蓄積管理する図示しない配信装置から通信ネットワーク５を介して巡回経路生成装置１０にダウンロードされる。
【００４２】
上記の機能のうち、記憶部１１０は、拠点３に関する情報である拠点情報１５１、自動販売機２に関する情報である自動販売機情報１５２、巡回時に作業員が拠点３を出発してから戻ってくるまでの目標時間１５３、後述する現在経路に関する情報である現在経路情報１５４、後述する次経路に関する情報である次経路情報１５５、巡回経路の探索に際して用いるコストの算出式に関する情報であるコスト関数情報１５６、及び巡回経路の探索結果に関する情報である経路探索結果１５７の各情報（データ）を記憶する。
【００４３】
図６に拠点情報１５１の一例を示す。図６に示すように、拠点情報１５１は、拠点ＩＤ１５１１と位置情報１５１２の各項目を有する、拠点３ごとの一つ以上のレコードを含む。拠点ＩＤ１５１１には、拠点３の識別子（以下、拠点ＩＤと称する。）が設定される。位置情報１５１２には、当該拠点３の位置を示す情報（本例では緯度経度）が設定される。
【００４４】
図７に自動販売機情報１５２の一例を示す。図７に示すように、自動販売機情報１５２は、自動販売機ＩＤ１５２１、位置情報１５２２、商品残量１５２３、在庫可能最大量１５２４、補充可能量１５２５、巡回履歴情報１５２６、及び緊急度１５２７の各項目を有する、自動販売機２ごとの複数のレコードを含む。
【００４５】
自動販売機ＩＤ１５２１には、自動販売機２の識別子（以下、自動販売機ＩＤと称する。）が設定される。位置情報１５２２には、当該自動販売機２の位置を示す情報（本例では緯度経度）が設定される。商品残量１５２３には、当該自動販売機２の現在の商品残量を示す残量情報が設定される。在庫可能最大量１５２４には、当該自動販売機２の在庫可能最大量が設定される。補充可能量１５２５には当該自動販売機２に補充が可能な商品の量が設定される。巡回履歴情報１５２６には、各自動販売機２に対して巡回が行われた直近の日時や、巡回時にリセットされて所定時間ごとにカウントアップあるいはカウントダウンするタイマーカウンタの値等の、巡回が行われてからの経過期間ないしは巡回が行われていない期間を特定可能な情報が設定される。緊急度１５２７には、各自動販売機２の緊急度（緊急度２５５）が設定される。
【００４６】
図８に現在経路情報１５４の一例を示す。現在経路情報１５４には、後述する現在経路を示す情報が設定される。本例では、現在経路情報１５４として、「拠点３→自動販売機２Ａ→自動販売機２Ｂ→自動販売機２Ｃ→自動販売機２Ｄ→拠点３」という経路を示す情報が設定されている。
【００４７】
図９に次経路情報１５５の一例を示す。次経路情報１５５には、後述する次経路を示す情報が設定される。本例では、次経路情報１５５として、「拠点３→自動販売機２Ａ→自動販売機２Ｂ→自動販売機２Ｘ→自動販売機２Ｃ→自動販売機２Ｄ→拠点３」という経路を示す情報が設定されている。
【００４８】
図５に戻って、通信処理部１１１は、通信ネットワーク５を介して各地に存在する複数の自動販売機２の夫々と通信し、複数の自動販売機２の夫々との間で情報の送信または受信を行う。
【００４９】
経路探索処理部１１２は、記憶部１１０が記憶している情報を用いて所定の経路探索アルゴリズムを実行することにより巡回経路の探索を行う。経路探索アルゴリズムは、例えば、山登り法、シミュレーテッドアニーリング法、遺伝的アルゴリズム、タブーサーチ等である。本実施形態では、経路探索アルゴリズムは山登り法またはシミュレーテッドアニーリング法であるものとする。
【００５０】
図５に示すように、経路探索処理部１１２は、候補生成部１１２１、地点分類部１１２２、巡回経路生成部１１２３、目標時間受付部１１２４、及び巡回経路出力部１１２５を含む。
【００５１】
地点分類部１１２２は、巡回対象の各地点（図１に示す例では、１１台の自動販売機２が設置されている各地点）を、必ず巡回するべき地点（巡回必須地点）と、必ずしも巡回しなくて良い地点（巡回任意地点）と、に分類する。本実施形態では、地点分類部１１２２は、巡回対象の各自動販売機２が設けられている地点を、巡回必須地点と、巡回任意地点と、に分類する。
【００５２】
例えば、巡回経路生成装置１０に巡回必須地点を指定する情報（巡回必須地点の自動販売機ＩＤ）の入力を受け付けるユーザインタフェースを設け、地点分類部１１２２は、この情報によって指定される自動販売機２が設けられている地点を巡回必須地点に分類し、巡回必須地点に分類されない地点を巡回任意地点に分類する。
【００５３】
あるいは地点分類部１１２２は、自動販売機情報１５２に記録されている巡回履歴情報１５２６を参照し、前回の巡回日時からの経過期間が所定期間以上（例えば２日以上）である自動販売機２が設けられている地点を巡回必須地点に分類し、巡回必須地点に分類されない地点を巡回任意地点に分類するようにしてもよい。このとき、巡回経路生成装置１０に、上記所定期間を示す情報の入力を受け付けるユーザインタフェースを設けておくとよい。
【００５４】
あるいは地点分類部１１２２は、自動販売機情報１５２に記録されている巡回履歴情報１５２６及び商品残量１５２３を参照し、前回の巡回からの経過期間が所定期間以上（例えば２日以上）である自動販売機２、又は商品の残量が所定量以下（例えば飲料の残量が４０本以下、あるいは在庫可能最大量の３０％以下）である自動販売機２が設けられている地点を巡回必須地点に分類し、巡回必須地点に分類されない地点を巡回任意地点に分類するようにしてもよい。このとき、巡回経路生成装置１０に、上記所定期間を示す情報及び所定量を示す情報の入力を受け付けるユーザインタフェースを設けておくとよい。
【００５５】
また、地点分類部１１２２に対して、巡回が行われていない期間が所定期間以上である地点を巡回必須地点に分類させるための第1情報、及び商品の残量が所定量以下である自動販売機２が設けられている地点を巡回必須地点に分類させるための第２情報の入力を受け付けるユーザインタフェースを設けておき、地点分類部１１２２は、第１情報が入力されている場合には、前回の巡回からの経過期間が所定期間以上である地点を巡回必須地点に分類し、第２情報が入力されている場合には、商品の残量が所定量以下である自動販売機２が設けられている地点を巡回必須地点に分類し、巡回必須地点に分類されない地点を巡回任意地点に分類するようにしてもよい。
【００５６】
自動販売機２が設置される各地点をこのように分類しておくことにより、経路探索処理部１１２は、巡回経路を生成する際に、少なくとも巡回必須地点を巡回経路に含む範囲内で経路内の自動販売機２の数を調整できるようになる。これにより、巡回経路を生成する際の自由度が増し、巡回を開始してから終了するまでの所要時間を所定の目標時間に合わせることが容易になる。そして自動販売機２を巡回する作業員の勤務時間に合った巡回経路を生成することができるようになる。
【００５７】
候補生成部１１２１は、巡回経路の複数の候補（候補経路）を生成する。本実施形態では、候補生成部１１２１は、全ての巡回必須地点を経路に含むようにこれらの候補経路を生成する。
【００５８】
具体的には、候補生成部１１２１は、まずは巡回対象の全ての自動販売機２（図１１に示す例では１１台）に対して、これらの自動販売機２を所定の順序で（例えばランダムな順序に）並べることにより巡回経路の候補経路（第１候補）を生成する。
【００５９】
もちろん、第１候補には、全ての巡回任意地点が含まれていなくても良い。この場合は、候補生成部１１２１は、巡回対象の全ての地点の中から、少なくとも全ての巡回必須地点を含むように（巡回任意地点は、０個以上が含まれていれば良い。巡回任意地点は例えばランダムに選ぶ）複数の自動販売機２を選択した上で、これらの自動販売機２を所定の順序で並べることにより巡回経路の第１候補を生成する。
【００６０】
その後候補生成部１１２１は、以下の第１処理か、第２処理か、第３処理のいずれかをランダムに選択しながら繰り返し実行することで、複数の候補経路を順次生成する。
【００６１】
第１処理は、上記第１候補に含まれる自動販売機２の中から選択（例えばランダムに選択）した２つの自動販売機２の順序を入れ替えることにより第２候補を生成する。
【００６２】
第２処理は、上記第１候補に含まれる巡回任意地点から選択（例えばランダムに選択）した自動販売機２を第１候補の巡回経路から削除することにより第２候補を生成する。
【００６３】
第３処理は、上記第１候補に含まれない巡回任意地点から選択（例えばランダムに選択）した自動販売機２を第１候補の巡回経路に組み込むことにより第２候補を生成する。
【００６４】
なおこの際に、候補生成部１１２１は、新たに自動販売機２を経路に追加することによる経路長の増加量が最小となるようにこの自動販売機２を追加する。たとえば第１候補が「拠点３→Ａ→Ｃ→Ｄ→Ｅ→拠点３」である場合に、この経路内に「Ｂ」を追加して第２候補を生成する場合、Ａ、Ｃ、Ｄ、Ｅの前後の任意の位置に挿入可能であるが、それぞれ距離の和「(拠点３→Ｂの距離）＋(Ｂ→Ａの距離）」「(Ａ→Ｂ の距離）＋(Ｂ→Ｃ の距離）」「(Ｃ→Ｂ の距離）＋(Ｂ→Ｄ の距離）」「(Ｄ→Ｂ の距離）＋(Ｂ→Ｅ の距離）」「(Ｅ→Ｂ の距離）＋(Ｂ→拠点３ の距離）」が最小となる位置に挿入する。
【００６５】
その後、候補生成部１１２１は、上記各処理で生成された第２候補を第１候補として再び第１〜第３処理のいずれかをランダムに選択しながら、新たに第２候補を生成する処理を繰り返し実行する。
【００６６】
このような態様により、巡回必須地点を必ず含みつつ、巡回する自動販売機２の数が様々な候補経路を生成することが可能となる。
【００６７】
なお巡回経路生成装置１０は、第１候補（つまり現在注目している候補経路。以下、「現在経路」と称する。）についての情報を現在経路情報１５４として記憶し、第２候補（つまり現在経路に基づき生成される次の候補経路。以下、「次経路」と称する。）についての情報を次経路情報１５５として記憶する。
【００６８】
巡回経路生成部１１２３は、上記候補経路のそれぞれに対して、作業員が巡回を開始してから終了するまでの所要時間と所定の目標時間とのずれの度合いを示す第１指標値と、経路長を示す第２指標値と、緊急度が高い設備が優先的に巡回される度合いを表す第３指標値と、経路内の各自動販売機２の補充可能量の総量を示す第４指標値と、を算出し、これらの各指標値の算出結果に基づいて複数の候補経路の中から一つの候補を選出することにより、巡回経路を生成する。
【００６９】
具体的には、巡回経路生成部１１２３は、以下の（式１）で表されるコスト関数を用いて各候補経路のコストを求め、コストが最小となる候補経路を巡回経路として求める。なおコスト関数は、記憶部１１０がコスト関数情報１５６として記憶している。
【００７０】
コスト関数＝ ｃ×第１指標値＋第２指標値＋第３指標値−ｄ×第４指標値  …（式１）
【００７１】
ここで、第１指標値は、以下の（式２Ａ）、（式２Ｂ）により算出される。
【００７２】
第１指標値＝（所要時間−目標時間）×候補経路に含まれる巡回任意地点の数
（所要時間＞目標時間の場合）  …（式２Ａ）
第１指標値＝（目標時間−所要時間）×候補経路に含まれない巡回任意地点の数
（所要時間≦目標時間の場合）  …（式２Ｂ）
【００７３】
なお（式２Ａ）は、所要時間＞目標時間の場合に用いられる第１指標値の算出式であり、例えば作業員が勤務終了時刻に拠点３に戻ってくるように目標時間が定められている場合は、作業員に残業が発生する場合の算出式である。
【００７４】
また（式２Ｂ）は、所要時間≦目標時間の場合に用いられる第１指標値の算出式である。
【００７５】
第１指標値を算出するにあたって、巡回経路生成部１１２３は、作業員が各自動販売機２を巡回して戻ってくるまでの所要時間をシミュレーションする。
【００７６】
この所要時間は、各候補経路において、隣り合う地点間の距離と、作業員の移動速度と、を用いて算出される隣り合う地点間の移動時間と、各地点での作業時間を、経路全体で積算することにより算出することができる。作業員の移動速度や作業時間は、例えば過去の経験から求めた所定値とすればよい。
【００７７】
ここで第１指標値について補足すると、例えば、残業が発生するにも関わらず巡回任意地点を巡回している場合は、この巡回任意地点を巡回しないようにすることにより、巡回の所要時間を短くできるはずであるから、それを第１指標値によるペナルティとしてコストに加算する。コストへの影響の大きさを係数ｃで調整している。これにより、残業が発生する場合は、巡回任意地点が少ない候補経路の方がよい経路と認識されて残りやすくなる。
【００７８】
逆に、巡回作業が目標時間よりも早く終わるにもかかわらず、巡回していない巡回任意地点が残っている場合は、これらの巡回任意地点を巡回することで作業時間を増やせるはずであるから、巡回していない巡回任意地点の数に比例したペナルティとしてコストに加算する。
【００７９】
ただし、第１指標値は、以下の（式３Ａ）、（式３Ｂ）を用いて算出しても良い。
【００８０】
第１指標値＝所要時間−目標時間  （所要時間＞目標時間の場合）  …（式３Ａ）
第１指標値＝目標時間−所要時間  （所要時間≦目標時間の場合）  …（式３Ｂ）
【００８１】
これらの式であっても、第１指標値は、巡回に要する時間が目標時間とずれている場合には、時間差に比例して大きくなるから、（式１）のコストを増大させることになる。
【００８２】
あるいは、所要時間≦目標時間の場合に（式２Ｂ）（式３Ｂ）に代えて、第１指標値＝所定値（例えば０や１等の固定値）としてもよい。この場合は、目標時間よりも短時間で巡回が終了するような候補経路であっても（式１）のコストをほとんど増加させないため、早めに巡回が終了するような経路が選択されやすくなるため、作業員の業務軽減を図ることが可能となる。あるいは、巡回する地点の数が少ないにもかかわらず目標時間が長すぎるような場合に、所要時間を目標時間に近づけるために無理に遠回りをするような巡回経路が生成されないようにすることが可能となる。
【００８３】
次に巡回経路生成部１１２３は、以下の（式４）を用いて第２指標値を算出する。
【００８４】
第２指標値＝Σ経路上で隣り合う２つの地点間の距離  …（式４）
【００８５】
第２指標値は、候補経路の経路長（総移動距離）を示す。２つの地点間の距離は、自動販売機情報１５２に記載されている各自動販売機２の位置情報１５２２及び拠点情報１５１に記載されている位置情報１５１２から求めることができる。あるいは不図示の地図データを利用して、各地点間の道路に沿った距離を求めるようにしても良い。さらには、第１指標値を算出する際に用いた所要時間うちの移動時間の分だけを経路全体で積算した値を用いてもよい。第２指標値が大きい程、コストは増大する。
【００８６】
次に巡回経路生成部１１２３は、以下の（式５）を用いて第３指標値を算出する。
第３指標値＝−α×Σf(自動販売機の緊急度,順番)   …（式５）
【００８７】
（式５）において、αは正の係数である。また関数ｆは（式６）で表される。
f(自動販売機の緊急度,順番)＝max(0,(全自動販売機数/2-順番)×緊急度)  …（式６） 
【００８８】
（式６）における「順番」は、作業員がその自動販売機２を何番目に寄るかを示す値である。本実施形態では、作業員が最初に訪れる自動販売機２を０番目とする。例えば、巡回すべき自動販売機２が全部で１００台あり、作業員が緊急度＝９の自動販売機２を最初に（０番目に）訪問する場合には、ｆ(９,０)＝max(０，（１００／２−０)×９）＝４５０となる。また、もしこの自動販売機３００を５１番目に訪問する場合には、ｆ(９,５１)＝max(０，（１００／２−５１)×９）＝０となる。
【００８９】
このように、（式６）の値は、候補経路の前半（０番目〜４９番目）で訪問される自動販売機２に対しては、緊急度の高い自動販売機２がより早い順番で訪問されるほど大きな値となるが、候補経路の後半（５０番目〜９９番目）に訪問される自動販売機２に対しては０となる。
【００９０】
巡回経路生成部１１２３は、（式６）の値を各自動販売機２に対して計算し、（式５）によりこれらを合計することで第３指標値を計算する。このようにして、第３指標値は、緊急度が高い自動販売機２が優先的に巡回される度合いを表すことができる。
【００９１】
続いて、巡回経路生成部１１２３は、以下の（式７）を用いて第４指標値を算出する。
【００９２】
第４指標値＝Σ経路内の各自動販売機における商品の補充可能量  …（式７）
【００９３】
各自動販売機２の商品の補充可能量は、自動販売機情報１５２に記載されている各自動販売機２の補充可能量１５２５から求めることができる。
【００９４】
作業員が各自動販売機２を巡回するにあたり、商品の補充可能量が多い自動販売機２を巡回する場合と少ない自動販売機２を巡回する場合とを比較した場合、前者の方が巡回の成果が大きいと言えるため、重要な自動販売機２であると言える。そのためこの第４指標値は、候補経路の中の各自動販売機２の重要度の総和を表す指標となっている。
【００９５】
なお（式１）で算出されるコストは低いほど良いため、第４指標値の符号はマイナスになっている。そして係数ｄによって第４指標値がコストに与える影響の度合いを調整できるようにしている。
【００９６】
なお、第４指標値は、以下の（式８）を用いて算出しても良い。
【００９７】
第４指標値＝Σ経路内の各巡回任意地点における商品の補充可能量  …（式８）
【００９８】
全ての巡回必須地点は必ず候補経路に含まれるから、（式７）により求めた第４指標値には、巡回必須地点における商品の補充可能量の総和が定数成分として含まれることになる。このような定数成分は各候補経路のコストに差を生み出すものではない。そのため、（式８）のように、巡回任意地点における商品の補充可能量の総和を第４指標値として求めるようにすることで、各候補経路を比較する上で無駄な計算を省くことが可能となる。
【００９９】
このように、本実施形態に係る巡回経路生成装置１０は、巡回経路の経路長（移動距離）に関する第２指標値のみならず、巡回を開始してから終了するまでの所要時間と所定の目標時間とのずれの度合いを示す第１指標値を用いて巡回経路を生成している。
【０１００】
このような態様により、複数地点に設けられた自動販売機２を巡回する作業員が所定の時間で戻って来られるような巡回経路を生成することが可能となる。
【０１０１】
さらに本実施形態に係る巡回経路生成装置１０は、上記第１指標値及び第２指標値に加え、緊急度が高い自動販売機２が優先的に巡回される度合いを表す第３指標値も用いて巡回経路を生成している。
【０１０２】
このような態様により、より緊急度の高い自動販売機２をいち早く訪問するような巡回経路を生成することが可能となる。
【０１０３】
またさらに、本実施形態に係る巡回経路生成装置１０は、上記第１指標値及び第２指標値に加え、経路内の各自動販売機２の商品の補充可能量の総量を示す第４指標値を用いて巡回経路を生成している。
【０１０４】
このような態様により、より重要性の高い自動販売機２を優先的に訪問するような巡回経路を生成することが可能となる。
【０１０５】
そして（式１）に示したように第１指標値から第４指標値を用いて巡回経路を生成するようにした場合には、上記各指標値を用いた場合の効果が全体的にバランスされ、最適な巡回経路を生成することが可能となる。
【０１０６】
目標時間受付部１１２４は、入力装置１４あるいは通信装置１６から、作業員が巡回を開始してから終了するまでに要する目標時間の入力を受け付ける。そして目標時間受付部１１２４は、この目標時間を記憶部１１０に目標時間１５３として記憶する。
【０１０７】
巡回経路出力部１１２５は、巡回経路生成部１１２３によって生成された巡回経路（経路探索結果１５７）を、出力装置１５あるいは通信装置１６に出力する。
【０１０８】
＝＝処理の流れ＝＝
続いて、巡回経路生成装置１０により行われる経路探索に関する処理について具体的に説明する。
【０１０９】
図１０は、山登り法により巡回経路生成装置１０が巡回経路を探索する際に行う処理（以下、経路探索処理Ｓ１２００と称する。）を説明するフローチャートである。以下、図１０を参照しながら経路探索処理Ｓ１２００について説明する。
【０１１０】
まず巡回経路生成装置１０は、巡回対象の各自動販売機２が設けられる地点を、巡回必須地点と巡回任意地点に分類しておく。そして巡回経路生成装置１０は、現在経路の初期値を生成する（Ｓ１２１１）。本実施形態では一例として、巡回経路生成装置１０は、全ての自動販売機２（全ての巡回必須地点の自動販売機２及び全ての巡回任意地点の自動販売機２）が経路に含まれるようにし、順序はランダムに設定することで現在経路の初期値を生成する。また巡回経路生成装置１０は、この現在経路を現在経路情報１５４として記憶部１１０に記録するとともに、巡回経路の暫定解として設定しておく。
【０１１１】
続いて巡回経路生成装置１０は、現在経路について、第１指標値から第４指標値を算出し（Ｓ１２１２）、これらの算出結果から現在経路のコストを求める（Ｓ１２１３）。
【０１１２】
そして巡回経路生成装置１０は、現在経路に基づき次経路を生成する（Ｓ１２１４）。このとき巡回経路生成装置１０は、上述した第１処理、第２処理、あるいは第３処理のいずれかをランダムに選んで実行することにより、次経路を生成する。また巡回経路生成装置１０は、この次経路を次経路情報１５５として記憶部１１０に記録する。
【０１１３】
次に巡回経路生成装置１０は、次経路について第１指標値から第４指標値を算出し（Ｓ１２１５）、これらの算出結果から次経路のコストを求める（Ｓ１２１６）。
【０１１４】
そして巡回経路生成装置１０は、次経路のコストが現在経路のコストよりも小さいか否かを判定する（Ｓ１２１７）。次経路のコストが現在経路のコストよりも小さい場合（Ｓ１２１７：ＹＥＳ）、巡回経路生成装置１０は、次経路を暫定解として設定し直す（Ｓ１２１８）。その後、処理はＳ１２１９に進む。一方、次経路のコストが現在経路のコストよりも小さくない場合（Ｓ１２１７：ＮＯ）、処理はＳ１２１９に進む。
【０１１５】
Ｓ１２１９では、巡回経路生成装置１０は、暫定解のコストが予め設定された閾値以下であるか否かを判定する。暫定解のコストが予め設定された閾値以下である場合（Ｓ１２１９：ＹＥＳ）、巡回経路生成装置１０はＳ１２２０を実行する。暫定解のコストが予め設定された閾値以下でない場合（Ｓ１２１９：ＮＯ）、巡回経路生成装置１０は、次経路を現在経路とし、次経路情報１５５を現在経路情報１５４に転記した上で、Ｓ１２１４に戻って処理を続ける。
【０１１６】
Ｓ１２２０では、巡回経路生成装置１０は、暫定解を経路探索結果１５７として記憶する。尚、巡回経路生成装置１０は、経路探索結果１５７を出力装置１５に適宜出力する。
【０１１７】
図１１は、シミュレーテッドアニーリング法により巡回経路生成装置１０が巡回経路を探索する際に行う処理（以下、経路探索処理Ｓ１３００と称する。）を説明するフローチャートである。以下、図１１を参照しながら経路探索処理Ｓ１３００について説明する。
【０１１８】
まず巡回経路生成装置１０は、温度Ｔの初期値を設定する（Ｓ１３１１）。
【０１１９】
続いて巡回経路生成装置１０は、巡回対象の各自動販売機２が設けられる地点を、巡回必須地点と巡回任意地点に分類する。そして巡回経路生成装置１０は、現在経路の初期値を生成する（Ｓ１３１２）。このとき巡回経路生成装置１０は、一例として、全ての自動販売機２（全ての巡回必須地点の自動販売機２及び全ての巡回任意地点の自動販売機２）が経路に含まれるようにし、順序はランダムに設定することにより、現在経路の初期値を生成する。また巡回経路生成装置１０は、この現在経路を現在経路情報１５４として記憶部１１０に記録するとともに、巡回経路の暫定解として設定しておく。
【０１２０】
巡回経路生成装置１０は、現在経路について第１指標値から第４指標値を算出し（Ｓ１３０３）、これらの算出結果に基づき、現在経路のコストを求める（Ｓ１３１４）。
【０１２１】
そして巡回経路生成装置１０は、現在経路に基づき次経路を生成する（Ｓ１３１５）。このとき巡回経路生成装置１０は、上述した第１処理、第２処理、あるいは第３処理のいずれかをランダムに選んで実行することにより、次経路を生成する。また巡回経路生成装置１０は、この次経路を次経路情報１５５として記憶部１１０に記録する。
【０１２２】
続いて、巡回経路生成装置１０は、次経路について第１指標値から第４指標値を算出し（Ｓ１３１６）、これらの算出結果に基づき、次経路のコストを求める（Ｓ１３１７）。
【０１２３】
そして巡回経路生成装置１０は、次経路を受理するか否かを判定する（Ｓ１３１８）。上記判定に際し、巡回経路生成装置１０は、原則として次経路のコストが現在経路のコストよりも小さい場合に次経路を受理するが、次経路のコストが現在経路のコストより小さくない場合でも（即ち改悪となる場合でも）、温度Ｔに依存する確率で次経路を受理する。尚、上記の確率としては、例えば、メトロポリス基準が用いられる。このようにすることで、局所最適解に陥りにくくすることができる。巡回経路生成装置１０は、次経路を受理すると判定した場合（Ｓ１３１８：受理）、次経路を暫定解として設定し直した上で（Ｓ１３１９）、Ｓ１３２０に処理を進める。一方、次経路を受理しないと判定した場合（Ｓ１３１８：不受理）、巡回経路生成装置１０は処理をＳ１３２０に進める。
【０１２４】
Ｓ１３２０では、巡回経路生成装置１０は、温度Ｔを下げるか否かを判定する。巡回経路生成装置１０は、例えば、Ｓ１３１５〜Ｓ１３２０のループ処理を予め設定された回数以上繰り返された場合に温度Ｔを下げると判定する。
【０１２５】
巡回経路生成装置１０は、温度Ｔを下げると判定した場合に（Ｓ１３２０：ＹＥＳ）、温度Ｔを下げ（Ｓ１３２１）、処理をＳ１３２２に進める。例えば、指数型アニーリングの場合、巡回経路生成装置１０は、Ｔｋ＋１＝γ・Ｔｋとする（但しγは冷却速度を決定する係数）。一方、巡回経路生成装置１０は、温度Ｔを下げないと判定した場合（Ｓ１３２０：ＮＯ）、次経路を現在経路とし、次経路情報１５５を現在経路情報１５４に転記した上で、Ｓ１３１５に戻って処理を続ける。
【０１２６】
Ｓ１３２２では、巡回経路生成装置１０は、暫定解のコストが予め設定された閾値以下であるか否かを判定する。暫定解のコストが予め設定された閾値以下である場合（Ｓ１３２２：ＹＥＳ）、巡回経路生成装置１０はＳ１３２３を実行する。暫定解のコストが予め設定された閾値以下でない場合（Ｓ１３２２：ＮＯ）、巡回経路生成装置１０は、次経路を現在経路とし、次経路情報１５５を現在経路情報１５４に転記した上で、Ｓ１３１５に戻って処理を続ける。
【０１２７】
Ｓ１３２３では、巡回経路生成装置１０は、暫定解を経路探索結果１５７として記憶する。尚、巡回経路生成装置１０は、経路探索結果１５７を出力装置１５に適宜出力する。
【０１２８】
以上、本実施形態に係る巡回経路生成装置１０、巡回経路生成装置１０の制御方法及びプログラムについて説明したが、本実施形態に係る巡回経路生成装置１０、巡回経路生成装置１０の制御方法及びプログラムによれば、複数の地点を巡回する作業員が所定の時間で戻って来られるような巡回経路を生成することが可能となる。これにより、例えば、作業員の勤務時間や勤務先の営業時間等に合った適切な巡回経路を生成することが可能となる。また、巡回に使用できる時間と人員が定められている場合であっても、その範囲内で、巡回する地点の方を調整することにより、巡回できる経路を生成することが可能となる。
【０１２９】
尚、上記実施形態は本発明の理解を容易にするためのものであり、本発明を限定して解釈するためのものではない。本発明はその趣旨を逸脱することなく変更、改良され得るとともに、本発明にはその等価物も含まれる。
【０１３０】
例えば、上記実施形態では、自動販売機２の商品を補充する業務を例として説明したが、タンクローリーにより複数のガソリンスタンドを巡回して貯蔵タンクにガソリンを補給する業務や、農地の複数個所に設けられている農業用給水タンクに水を補給する業務、営業担当者による顧客訪問業務、各地の水田の水位計測業務等、様々な場面に適用することができる。
【０１３１】
また上記実施形態では、巡回経路生成装置１０が地点分類部１１２２を備え、巡回対象の各地点を、必ず巡回するべき地点（巡回必須地点）と必ずしも巡回しなくて良い地点（巡回任意地点）とに分類した上で、必ず全ての巡回必須地点を巡回しつつ、作業員が所定の時間で戻って来られるような巡回経路を生成する場合を例に説明したが、地点分類部１１２２を備えない構成でもよい。この場合、巡回経路生成装置１０は、巡回対象の各地点が全て巡回任意地点であるとして、作業員が所定の時間で戻って来られるように、少なくとも一部の地点を巡回する巡回経路を生成する。
【０１３２】
また上記実施形態では、巡回経路生成装置１０が、各地に設けられている自動販売機２から収集した情報を利用して巡回経路の生成を行っているが、例えば、巡回経路生成装置１０が自動販売機２における商品の消費の状況をシミュレーションすることにより巡回経路の生成を行うようにしてもよい。
【符号の説明】
【０１３３】
１  巡回経路生成システム
２  自動販売機
２１０  記憶部
２１１  販売制御処理部
２１２  金銭受付処理部
２１３  商品残量取得部
２１４  商品補充可能量算出部
２１５  緊急度算出部
２１６  通信処理部
２５１  商品残量
２５２  在庫可能最大量
２５３  商品補充可能量
２５４  巡回日時
２５５  緊急度
３  拠点
５  通信ネットワーク
１０  巡回経路生成装置
１１  プロセッサ
１１２  経路探索処理部
１１２１  候補生成部
１１２２  地点分類部
１１２３  巡回経路生成部
１１２４  目標時間受付部
１１２５  巡回経路出力部
１２  主記憶装置
１３  補助記憶装置
１４  入力装置
１５  出力装置
１６  通信装置
１５０  記憶部
１５１  拠点情報
１５２  自動販売機情報
１５３  目標時間
１５４  現在経路情報
１５５  次経路情報
１５６  コスト関数情報
１５７  経路探索結果
Ｓ１２００  経路探索処理
Ｓ１３００  経路探索処理
【図１】
2020016944.tif 000003
【図２】
2020016944.tif 000004
【図３】
2020016944.tif 000005
【図４】
2020016944.tif 000006
【図５】
2020016944.tif 000007
【図６】
2020016944.tif 000008
【図７】
2020016944.tif 000009
【図８】
2020016944.tif 000010
【図９】
2020016944.tif 000011
【図１０】
2020016944.tif 000012
【図１１】
2020016944.tif 000013