(57)【要約】【課題】複数の場所を複数の移動体によって巡回する場合に負荷を小さくしたり各移動体間の負荷の差を小さくする経路を、実用的に決定する装置を提供する。【解決手段】複数の経路データを受け付ける経路データ受付手段と、複数の経路データのうち、負荷が最も軽い経路とは異なる開始経路と、該開始経路よりも負荷が軽い完了経路と、を決定する開始完了決定手段と、複数の経路データの一経路に含まれる地点である選択点と、該選択点と所定の関係を有する他の経路と、を選択すると共に、該一経路から該他の経路へ該選択点を移動させ、初回には該開始経路を該一経路として選択し、次回以降は前回以前の該他の経路又は該開始経路を該一経路として動作を繰り返す所属変更手段と、該他の経路が該完了経路と一致するか否か判断する完了判断手段と、を備え、該所属変更手段が、該完了判断手段が一致すると判断するまで繰り返し動作する。【選択図】　図２
2004062363.tif 000002
【特許請求の範囲】
【請求項１】
始点と、複数の地点を巡る経路と、を含んでなる複数の経路データを受け付ける経路データ受付手段と、
該経路データ受付手段により受け付けられる複数の経路データのうち、負荷が最も軽い経路とは異なる経路である開始経路と、該開始経路よりも負荷が軽い経路である完了経路と、を決定する開始完了決定手段と、
該経路データ受付手段により受け付けられる複数の経路データの一経路に含まれる地点である選択点と、該選択点と所定の関係を有する他の経路と、を選択すると共に、該一経路から該他の経路へ該選択点を移動させるものであり、初回には該開始経路を該一経路として選択し、次回以降は前回以前の該他の経路又は該開始経路を該一経路として該選択と該移動との動作を繰り返す所属変更手段と、
該他の経路が該完了経路と一致するか否か判断する完了判断手段と、を備え、
該所属変更手段が、該完了判断手段が一致すると判断するまで繰り返し動作するものである、経路調整装置。
【請求項２】
前記開始経路が、前記経路データ受付手段により受け付けられる複数の経路データのうち負荷が最も重い経路であり、そして前記完了経路が、該複数の経路データのうち負荷が最も軽い経路である、請求項１に記載の経路調整装置。
【請求項３】
前記所属変更手段が、前記前回以前の他の経路又は前記開始経路に含まれる地点のうち前記完了経路への帰属度が最も高い地点を前記選択点として選択するものである、請求項１又は２に記載の経路調整装置。
【請求項４】
前記所属変更手段が、前記前回以前の他の経路又は前記開始経路以外の経路へ前記選択点が示す帰属度のうち最も高い帰属度を示す経路を前記他の経路として選択するものである、請求項１乃至３のいずれかに記載の経路調整装置。
【請求項５】
前記所属変更手段によって前記選択点が加除され、含まれる地点に変更が生じた経路に所属する地点を巡る順番を決定し経路を形成する経路形成手段を、さらに備えるものである、請求項１乃至４のいずれかに記載の経路調整装置。
【請求項６】
前記経路形成手段によって形成された経路を含む経路データを前記経路データ受付手段が受け付けさらに経路調整するものである、請求項５に記載の経路調整装置。
【請求項７】
前記経路形成手段によって形成された経路における経路毎の負荷のばらつきが所定範囲に収まるまで、繰り返し経路調整するものである、請求項６に記載の経路調整装置。
【請求項８】
前記経路形成手段によって形成された経路における経路毎の負荷のばらつきを示すデータである均等化データを形成する均等化データ形成手段と、
該均等化データを記憶する均等化データ記憶手段と、
該均等化データ形成手段によって形成された直近の均等化データが、該均等化データ記憶手段に記憶された過去の均等化データに比して、改善されているか否か判断する改善判断手段と、をさらに備え、
該改善判断手段が改善されていると判断した場合、前記経路形成手段によって形成された経路に係る経路データを前記経路データ受付手段が受け付けさらに経路調節するものである、請求項６に記載の経路調整装置。
【請求項９】
前記所属変更手段が行う前記選択点の所属変更処理の履歴を記憶する履歴記憶手段と、
直近の選択点の所属変更処理と同一の履歴を該履歴記憶手段が記憶しているか否か判断する収束判断部と、
を、さらに備え、
該収束判断部が、直近の選択点の所属変更処理と同一の履歴を該履歴記憶手段が記憶していると判断しない場合、前記経路形成手段によって形成された経路に係る経路データを前記経路データ受付手段が受け付けさらに経路調節するものである、請求項６又は８に記載の経路調整装置。
【請求項１０】
前記所属変更手段が行う前記選択点の所属変更処理の履歴を記憶する履歴記憶手段と、
前記改善判断手段が、直近の均等化データが改善されていると判断しない場合、直近の均等化データに係る選択点の所属変更処理と同一の履歴を該履歴記憶手段が記憶しているか否か判断する収束判断部と、
を、さらに備え、
該収束判断部が、直近の均等化データに係る選択点の所属変更処理と同一の履歴を該履歴記憶手段が記憶していると判断しない場合、前記経路形成手段によって形成された経路に係る経路データを前記経路データ受付手段が受け付けさらに経路調節するものである、請求項８に記載の経路調整装置。
【請求項１１】
始点と、複数の地点を巡る経路と、を含んでなる複数の経路データを受け付ける経路データ受付手段と、
該経路データ受付手段により受け付けられる複数の経路データに含まれる各地点を、該地点が含まれていない経路に所属させた際に生じる全経路の負荷の変化を評価する全体負荷評価手段と、
該全体負荷評価手段により評価される負荷の変化が、地点の所属が変更される前に比して負荷が低減されることを示す場合における所属が変更される地点と、該所属が変更される地点が所属が変更される前に所属している経路である前所属経路と、該所属が変更される地点が所属が変更される先の経路である後所属経路と、を関連付けられたものを変更候補データとして記憶する負荷変化記憶手段と、
該負荷変化記憶手段に記憶された該変更候補データのうち所定の条件に合致するものを抽出する抽出手段と、
を備えるものである、経路調整装置。
【請求項１２】
前記変更候補データが、全経路の負荷の総和が、地点の所属が変更される前に比してどの程度低減されるかを示す低減度合いをさらに関連付けられた状態で記憶されており、
前記所定の条件が、該低減度合いが最大であるという条件である、請求項１１に記載の経路調整装置。
【請求項１３】
前記抽出手段によって抽出された前記変更候補データに従って経路を形成する経路形成手段を、さらに備えるものである、請求項１１又は１２に記載の経路調整装置。
【請求項１４】
前記経路形成手段によって形成された経路を含む経路データを前記経路データ受付手段が受け付けさらに経路調整するものである、請求項１３に記載の経路調整装置。
【請求項１５】
前記抽出手段により抽出された変更候補データの履歴を記憶する変更候補履歴記憶手段をさらに備え、
前記抽出手段が、前記負荷変化記憶手段に記憶された変更候補データのうち、該変更候補履歴記憶手段に記憶された履歴と同一のものを除いた変更履歴データから抽出するものである、請求項１４に記載の経路調整装置。
【請求項１６】
前記抽出手段が変更履歴データを抽出することができなくなるまで、前記経路形成手段によって形成された経路を含む経路データを前記経路データ受付手段が受け付けさらに経路調整するものである、請求項１５に記載の経路調整装置。
【請求項１７】
複数の地点の位置データを受け付け、該複数の地点全部を巡る全体の負荷を算出する全体負荷算出手段と、
該複数の地点の一部を巡る移動体それぞれが受け持ち可能な負荷の量である負荷許容量を受け付け、全体負荷算出手段により評価された該全体の負荷と該負荷許容量とから該移動体の数を所定の方法により決定する移動体数決定手段と、
該複数の地点を該移動体の数だけ分割する地点分割手段と、
該移動体それぞれの出発位置を示す出発位置情報を受け付ける移動体出発位置情報受付手段と、
該地点分割手段により分割された地点のそれぞれのグループに対し所定の位置関係を有する該出発位置情報に係る該移動体を割り当てる移動体割当手段と、
該移動体割当手段により割当られた移動体の出発位置を始点とし、該移動体に対応する該グループに属する全ての地点を巡る各グループ毎の経路を作成する各グループ原始経路形成手段と、
を備えてなる、経路形成装置。
【請求項１８】
前記各グループ原始経路形成手段によって形成された各グループ毎の経路に関する負荷を全てのグループに関して合計した第１総量と、前記移動体数決定手段によって受け付けられ、各グループに割当られた移動体それぞれの負荷許容量を合計した第２総量と、を比較し、第２総量が第１総量以上であるか否か判断する総量判断手段と、
該総量判断手段が、第２総量が第１総量以上であると判断しない場合、移動体の数を増加させる移動体増加手段と、
を、さらに備え、
前記地点分割手段は該増加された移動体の数に応じて複数の地点を分割し、前記移動体割当手段は、該増加された移動体の数に応じて分割された地点のそれぞれのグループに移動体を割り当て、そして前記各グループ原始経路形成手段は、該増加された移動体の数に応じて分割された地点のそれぞれのグループ毎の経路を作成するものである、請求項１７に記載の経路形成装置。
【請求項１９】
請求項１７又は１８に記載の経路形成装置が形成した前記移動体の出発位置を始点とする前記各グループ毎の経路を、前記経路データ受付手段が前記経路データとして受け付けるものである、請求項１乃至１６のいずれかに記載の経路調整装置。
【請求項２０】
請求項５乃至１０のいずれかに記載の経路調整装置の前記経路形成手段によって形成された経路を、前記経路データ受付手段が前記経路データとして受け付けさらに経路調整するものである、請求項１１乃至１６のいずれかに記載の経路調整装置。
【請求項２１】
請求項１７又は１８に記載の経路形成装置が形成した前記移動体の出発位置を始点とする前記各グループ毎の経路を、請求項５乃至１０のいずれかに記載の経路調整装置の前記経路データ受付手段が前記経路データとして受け付けるものである請求項２０に記載の経路調整装置。
【請求項２２】
請求項１３乃至１６のいずれかに記載の経路調整装置の前記経路形成手段によって形成された経路を、前記経路データ受付手段が前記経路データとして受け付けさらに経路調整するものである、請求項１乃至１０のいずれかに記載の経路調整装置。
【請求項２３】
請求項１７又は１８に記載の経路形成装置が形成した前記移動体の出発位置を始点とする前記各グループ毎の経路を、請求項１３乃至１６のいずれかに記載の経路調整装置の前記経路データ受付手段が前記経路データとして受け付けるものである請求項２２に記載の経路調整装置。
【請求項２４】
請求項１乃至１６及び請求項１９乃至２３のいずれかに記載の前記経路調整装置をコンピュータに実現させるためのプログラム。
【請求項２５】
請求項１乃至１６及び請求項１９乃至２３のいずれかに記載の前記経路調整装置をコンピュータに実現させるためのプログラムを記録したコンピュータ読みとり可能な記憶媒体。
【請求項２６】
請求項１７又は１８に記載の前記経路形成装置をコンピュータに実現させるためのプログラム。
【請求項２７】
請求項１７又は１８に記載の前記経路形成装置をコンピュータに実現させるためのプログラムを記録したコンピュータ読みとり可能な記憶媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、経路調整装置に関し、より詳細には、始点から複数の地点を巡る経路が複数存する系において、各経路の負荷（例えば、距離、時間、費用、稼動率等）の大小を少なくしたり負荷を低減して経路を調整する経路調整装置に関する。
【０００２】
【従来の技術】
複数の場所を複数の移動体によって巡回することは、多くの場合が存在する。例えば、宅配便業者において、１日に配達する必要がある複数の地点（具体的には、企業や家庭等）を複数の移動体（具体的には、担当者が乗車したトラック等）により巡る場合や、郵便を複数地点（具体的には、企業や家庭等）に複数の移動体（具体的には、担当者が乗車した自転車や自動二輪車等）により配達する場合等が挙げられる。
このような複数の場所を複数の移動体によって巡回する場合、負荷（例えば、距離、時間、費用、稼動率等）ができるだけ小さくなるようにすることは無論のことであるが、各移動体それぞれの負荷ができる限り同じ程度になるようにすることが好ましい場合（例えば、宅配便業者において移動体同士間で、配達時間に大きな隔たりがあれば、移動体間に不公平感が生じうる。）が多い。
【０００３】
このような複数の場所を複数の移動体によって巡回する場合の、負荷を小さくしたり、各移動体間の負荷の差を小さくするような経路を決定することは、これまでの経験や勘にたよって人が行ったり、コンピュータを用いた計算によって行われてきた。
【０００４】
【発明が解決しようとする課題】
しかしながら、経験や勘にたよって人が行う方法は、得られる結果がそれを行う人の経験や勘によって大きく影響されることや、たとえ同じ人であっても日時を異にすれば異なる結果が得られるといった問題があった。
一方、コンピュータを用いた計算においては、全ての場合計算を行うような方法では、実際の系に適用しようとすると膨大な計算を要し長い時間を必要とするので実用的でなかった。
【０００５】
そこで、本発明では、複数の場所を複数の移動体によって巡回する場合に負荷を小さくしたり各移動体間の負荷の差を小さくするような経路を、実用的に決定することができる装置を提供することを目的とする。
【０００６】
【課題を解決するための手段】
（第１本装置）
まず、本発明の第１の経路調整装置（以下、「第１本装置」という。）について説明する。
第１本装置は、始点と、複数の地点を巡る経路と、を含んでなる複数の経路データを受け付ける経路データ受付手段と、該経路データ受付手段により受け付けられる複数の経路データのうち、負荷が最も軽い経路とは異なる経路である開始経路と、該開始経路よりも負荷が軽い経路である完了経路と、を決定する開始完了決定手段と、該経路データ受付手段により受け付けられる複数の経路データの一経路に含まれる地点である選択点と、該選択点と所定の関係を有する他の経路と、を選択すると共に、該一経路から該他の経路へ該選択点を移動させるものであり、初回には該開始経路を該一経路として選択し、次回以降は前回以前の該他の経路又は該開始経路を該一経路として該選択と該移動との動作を繰り返す所属変更手段と、該他の経路が該完了経路と一致するか否か判断する完了判断手段と、を備え、該所属変更手段が、該完了判断手段が一致すると判断するまで繰り返し動作するものである、経路調整装置である。
【０００７】
こうすることで経路データ受付手段が、始点と、複数の地点を巡る経路と、を含んでなる複数の経路データを受け付ける。ここで「経路」とは、複数の地点を巡る順序を示すものをいう。
そして、開始完了決定手段が、経路データ受付手段により受け付けられる複数の経路データのうち、負荷が最も軽い経路とは異なる経路である開始経路と、該開始経路よりも負荷が軽い経路である完了経路と、を決定する。ここで「負荷」とは、経路に従って複数の地点を巡る際に必要な時間、経路に従って複数の地点を巡る際の移動距離、そして経路に従って複数の地点を巡る際に必要な費用等のように、経路に従って複数の地点を巡る際に生じる負担すべき事項をいう。このようにすることで開始完了決定手段が、開始経路と、それよりも負荷が小さい完了経路を決定する。
【０００８】
所属変更手段は、経路データ受付手段により受け付けられる複数の経路データの一経路に含まれる地点である選択点と、該選択点と所定の関係を有する他の経路と、を選択すると共に、該一経路から該他の経路へ該選択点を移動させる（該一経路に含まれていた選択点を、該一経路から除き、該他の経路へ含めることをいう。即ち、該一経路に属していた該選択点を、該一経路への所属を解き、該他の経路へ所属させることをいう。）ものであり、初回には該開始経路を該一経路として選択し、次回以降は前回以前の該他の経路又は該開始経路を該一経路として該選択と該移動との動作を繰り返す。
そして、完了判断手段は、該他の経路が該完了経路と一致するか否か判断し、完了判断手段が一致すると判断すると、所属変更手段は、該選択と該移動との動作を繰り返すことを中止する（即ち、完了判断手段が一致すると判断するまで、所属変更手段は、該選択と該移動との動作を繰り返す。）。
【０００９】
こうすることで所属変更手段の動作の初回（１回目）において、負荷が重い開始経路を該一経路とし、該開始経路に含まれる地点である選択点を、該選択点と所定の関係を有する他の経路へ移動させる。
所属変更手段の動作の２回目においては、初回（１回目）の該他の経路又は該開始経路を２回目の該一経路とする。２回目の該一経路（即ち、初回（１回目）の該他の経路又は該開始経路）に含まれる地点である選択点を、該選択点と所定の関係を有する他の経路へ移動させる。
以下、該他の経路が該完了経路と一致するまで、このような動作（一経路から他の経路へ選択点を移動させる動作）を繰り返すので、負荷が重い開始経路に含まれる地点が減少すると共に、負荷が軽い完了経路に含まれる地点が増加し、各経路間の負荷の差を小さくすることができる。このため第１本装置は、複数の場所を複数の移動体によって巡回する場合に各移動体間の負荷の差を小さくするような経路を決定することができる。
なお、一経路から他の経路へ選択点を移動させることは、上述したように、一経路に含まれていた選択点を、一経路から除き、他の経路へ含めることをいう。即ち、一経路に属していた選択点を、一経路への所属を解き、他の経路へ所属させることをいう。
【００１０】
第１本装置においては、前記開始経路が、前記経路データ受付手段により受け付けられる複数の経路データのうち負荷が最も重い経路であり、そして前記完了経路が、該複数の経路データのうち負荷が最も軽い経路であってもよい。
こうすることで複数の経路データのうち負荷が最も重い経路たる開始経路に含まれる地点が減少すると共に、負荷が最も軽い経路たる完了経路に含まれる地点が増加するので、効率的に各経路間の負荷の差を減少させることができる。
【００１１】
第１本装置においては、前記所属変更手段が、前記前回以前の他の経路又は前記開始経路に含まれる地点のうち前記完了経路への帰属度が最も高い地点を前記選択点として選択するものであってもよい。
ここで「帰属度」とは、ファジークラスタリングにおける帰属度をいい、具体的には、それぞれの経路に属する地点を各グループとして各々の地点が各グループにどの程度帰属するかを示した数字である。なお、ファジークラスタリングの処理方法は公知の技術であり、例えば、特開平０５−２７４２９３号に詳細に記載されている（ファジークラスタリングの方法の一つであるファジイｃ−ｍｅａｎｓ法を参考文献を含めて詳述している。これにより各クラスタへの帰属度が計算される。）ので、ここでは説明を省略する。
こうすることで前記前回以前の他の経路又は前記開始経路に属する地点のうち完了経路への帰属度が最も高い地点が他の経路に移動するので、適した位置に存する地点を移動させることができる。
【００１２】
第１本装置においては、前記所属変更手段が、前記前回以前の他の経路又は前記開始経路以外の経路へ前記選択点が示す帰属度のうち最も高い帰属度を示す経路を前記他の経路として選択するものであってもよい。
こうすることで前記前回以前の他の経路又は前記開始経路以外の経路へ選択点が示す帰属度のうち最も高い帰属度を示す経路を前記他の経路として選択するので、選択点が他の経路にうまく所属することができる（即ち、選択点に対しかけはなれた位置に存する経路が他の経路とされることで選択点が所属するのが無理な状態を生じることを、高い帰属度を示す経路を前記他の経路とすることで防止しうる。）。
【００１３】
第１本装置においては、前記所属変更手段によって前記選択点が加除され、含まれる地点に変更が生じた経路に所属する地点を巡る順番を決定し経路を形成する経路形成手段を、さらに備えるもの（以下、「経路形成手段所有第１本装置」という。）であってもよい。
選択点が加除されると、含まれる地点に変更が生じ、これまでの経路をそのまま用いることが困難になる。このため選択点が加除され含まれる地点に変更が生じた経路に所属する地点については、経路形成手段によって、それら地点を巡る順番を再び決定し経路を形成するようにしてもよい。
【００１４】
経路形成手段所有第１本装置においては、前記経路形成手段によって形成された経路を含む経路データを前記経路データ受付手段が受け付けさらに経路調整するもの（以下、「繰り返し第１本装置」という。）であってもよい。
こうすることで経路が、第１本装置によって複数回経路調整されるので、各経路間の負荷の差を一層うまく減少させることができる。
【００１５】
繰り返し第１本装置においては、前記経路形成手段によって形成された経路における経路毎の負荷のばらつきが所定範囲に収まるまで、繰り返し経路調整するものであってもよい。
こうすることで経路毎の負荷のばらつきが所望の所定範囲に収まるまで、経路が第１本装置によって繰り返し経路調整されるので、各経路間の負荷の差を所望の程度までうまく減少させることができる。
【００１６】
繰り返し第１本装置においては、前記経路形成手段によって形成された経路における経路毎の負荷のばらつきを示すデータである均等化データを形成する均等化データ形成手段と、該均等化データを記憶する均等化データ記憶手段と、該均等化データ形成手段によって形成された直近の均等化データが、該均等化データ記憶手段に記憶された過去の均等化データに比して、改善されているか否か判断する改善判断手段と、をさらに備え、該改善判断手段が改善されていると判断した場合、前記経路形成手段によって形成された経路に係る経路データを前記経路データ受付手段が受け付けさらに経路調節するもの（以下、「均等化データ使用第１本装置」という。）であってもよい。
こうすることで繰り返し第１本装置によって経路を複数回経路調整する際、経路毎の負荷のばらつきの低減が進行している状況（即ち、今後、ばらつきの低減の可能性があると考えられる状況）では繰り返し経路調整されるので各経路間の負荷の差をうまく減少させることができる。また、繰り返し第１本装置によって経路を複数回経路調整する際、経路毎の負荷のばらつきの低減がそれ以上進まなくなると（飽和すると）、経路調整の繰り返しが中止されるので、繰り返し第１本装置が無駄な処理をすることを防止することができる。
【００１７】
繰り返し第１本装置においては、前記所属変更手段が行う前記選択点の所属変更処理の履歴を記憶する履歴記憶手段と、直近の選択点の所属変更処理と同一の履歴を該履歴記憶手段が記憶しているか否か判断する収束判断部と、を、さらに備え、該収束判断部が、直近の選択点の所属変更処理と同一の履歴を該履歴記憶手段が記憶していると判断しない場合、前記経路形成手段によって形成された経路に係る経路データを前記経路データ受付手段が受け付けさらに経路調節するものであってもよい。
こうすることで繰り返し第１本装置によって経路を複数回経路調整する際、直近の選択点の所属変更処理と同一の履歴が存しないときは、経路毎の負荷のばらつきを低減する動作がまだ飽和していない（即ち、動作がまだ振動していない）ものと判断し、さらに繰り返し経路調整されるので各経路間の負荷の差をうまく減少させることができる。また、直近の選択点の所属変更処理と同一の履歴が存するときは、経路毎の負荷のばらつきを低減する動作が飽和したもの（即ち、動作が振動しているもの）と判断し、経路調整の繰り返しが中止されるので、繰り返し第１本装置が無駄な処理をすることを防止することができる。
【００１８】
均等化データ使用第１本装置においては、前記所属変更手段が行う前記選択点の所属変更処理の履歴を記憶する履歴記憶手段と、前記改善判断手段が、直近の均等化データが改善されていると判断しない場合、直近の均等化データに係る選択点の所属変更処理と同一の履歴を該履歴記憶手段が記憶しているか否か判断する収束判断部と、を、さらに備え、該収束判断部が、直近の均等化データに係る選択点の所属変更処理と同一の履歴を該履歴記憶手段が記憶していると判断しない場合、前記経路形成手段によって形成された経路に係る経路データを前記経路データ受付手段が受け付けさらに経路調節するものであってもよい。
こうすることで均等化データ使用第１本装置において、改善判断手段が、直近の均等化データが改善されていると判断しない場合であっても、直近の選択点の所属変更処理と同一の履歴が存しないときは、経路毎の負荷のばらつきを低減する動作がまだ飽和していない（即ち、動作がまだ振動していない）ものと判断し、さらに繰り返し経路調整されるので各経路間の負荷の差を一層うまく減少させることができる。
【００１９】
（第２本装置）
次いで、本発明の第２の経路調整装置（以下、「第２本装置」という。）について説明する。
第２本装置は、始点と、複数の地点を巡る経路と、を含んでなる複数の経路データを受け付ける経路データ受付手段と、該経路データ受付手段により受け付けられる複数の経路データに含まれる各地点を、該地点が含まれていない経路に所属させた際に生じる全経路の負荷の変化を評価する全体負荷評価手段と、該全体負荷評価手段により評価される負荷の変化が、地点の所属が変更される前に比して負荷が低減されることを示す場合における所属が変更される地点と、該所属が変更される地点が所属が変更される前に所属している経路である前所属経路と、該所属が変更される地点が所属が変更される先の経路である後所属経路と、を関連付けられたものを変更候補データとして記憶する負荷変化記憶手段と、該負荷変化記憶手段に記憶された該変更候補データのうち所定の条件に合致するものを抽出する抽出手段と、を備えるものである、経路調整装置である。
【００２０】
こうすることで、経路データ受付手段が、始点と、複数の地点を巡る経路と、を含んでなる複数の経路データを受け付ける。
そして、全体負荷評価手段が、経路データ受付手段により受け付けられる複数の経路データに含まれる各地点を、該地点が含まれていない経路に所属させた際に生じる全経路の負荷の変化を評価する。
なお、ここに「経路」及び「負荷」は、前述の第１本装置において説明したのと同様である。
そして、負荷変化記憶手段は、全体負荷評価手段により評価される負荷の変化が、地点の所属が変更される前に比して負荷が低減されることを示す場合における所属が変更される地点と、該所属が変更される地点が所属が変更される前に所属している経路である前所属経路と、該所属が変更される地点が所属が変更される先の経路である後所属経路と、を関連付けられたものを変更候補データとして記憶する。
最後に、抽出手段が、負荷変化記憶手段に記憶された変更候補データのうち所定の条件に合致するものを抽出する。
【００２１】
このため地点を該地点が含まれていない経路に所属させた際に生じる負荷の変化が全体負荷評価手段によって得られ、この負荷の変化が、地点の所属が変更される前に比して負荷が低減されることを示すものであれば変更候補データが負荷変化記憶手段に記憶される。そして、抽出手段が、負荷変化記憶手段に記憶された変更候補データのうち所定の条件に合致するものを抽出するので、経路データ受付手段が受け付けた経路データに比して、負荷が低減される変更候補データを得ることができる。
即ち、第２本装置は、複数の場所を複数の移動体によって巡回する場合に負荷を小さくするような経路を決定する装置である。
【００２２】
第２本装置においては、前記変更候補データが、全経路の負荷の総和が、地点の所属が変更される前に比してどの程度低減されるかを示す低減度合いをさらに関連付けられた状態で記憶されており、前記所定の条件が、該低減度合いが最大であるという条件であってもよい。
こうすることで抽出手段が、負荷変化記憶手段に記憶された変更候補データのうち、全経路の負荷の総和が、地点の所属が変更される前に比してどの程度低減されるかを示す低減度合いが最大のものを抽出するので、最も負荷を低減することができる変更候補データを得ることができる。
【００２３】
第２本装置においては、前記抽出手段によって抽出された前記変更候補データに従って経路を形成する経路形成手段を、さらに備えるもの（以下、「経路形成手段所有第２本装置」という。）であってもよい。
変更候補データは地点の所属を変更することを示すので、この変更を行うと経路に含まれる地点に変更が生じ、これまでの経路をそのまま用いることが困難になる。このため変更候補データに従って経路形成手段により再び経路を形成するようにしてもよい。
【００２４】
経路形成手段所有第２本装置においては、前記経路形成手段によって形成された経路を含む経路データを前記経路データ受付手段が受け付けさらに経路調整するもの（以下、「繰り返し第２本装置」という。）であってもよい。
こうすることで経路が、経路形成手段所有第２本装置によって複数回経路調整されるので、負荷を一層うまく減少させることができる。
【００２５】
繰り返し第２本装置においては、前記抽出手段により抽出された変更候補データの履歴を記憶する変更候補履歴記憶手段をさらに備え、前記抽出手段が、前記負荷変化記憶手段に記憶された変更候補データのうち、該変更候補履歴記憶手段に記憶された履歴と同一のものを除いた変更履歴データから抽出するもの（以下、「重複履歴排除第２本装置」という。）であってもよい。
こうすることで、変更候補履歴記憶手段が、抽出手段により以前に抽出された変更候補データの履歴を記憶しており、抽出手段が、負荷変化記憶手段に記憶された変更候補データのうち、変更候補履歴記憶手段に記憶された以前の履歴と同一のものを除いた変更履歴データから抽出するので、抽出手段により以前に抽出されたものを重複して抽出手段が抽出することを防止することができる。
【００２６】
重複履歴排除第２本装置においては、前記抽出手段が変更履歴データを抽出することができなくなるまで、前記経路形成手段によって形成された経路を含む経路データを前記経路データ受付手段が受け付けさらに経路調整するものであってもよい。
こうすることで負荷を低減することができる変更候補データをもれなく検討することができる。
【００２７】
（第３本装置）
さらに、本発明は経路形成装置も提供する。本発明の経路形成装置（以下、「第３本装置」という。）について説明する。
第３本装置は、複数の地点の位置データを受け付け、該複数の地点全部を巡る全体の負荷を算出する全体負荷算出手段と、該複数の地点の一部を巡る移動体それぞれが受け持ち可能な負荷の量である負荷許容量を受け付け、全体負荷算出手段により評価された該全体の負荷と該負荷許容量とから該移動体の数を所定の方法により決定する移動体数決定手段と、該複数の地点を該移動体の数だけ分割する地点分割手段と、該移動体それぞれの出発位置を示す出発位置情報を受け付ける移動体出発位置情報受付手段と、該地点分割手段により分割された地点のそれぞれのグループに対し所定の位置関係を有する該出発位置情報に係る該移動体を割り当てる移動体割当手段と、該移動体割当手段により割当られた移動体の出発位置を始点とし、該移動体に対応する該グループに属する全ての地点を巡る各グループ毎の経路を作成する各グループ原始経路形成手段と、を備えてなる、経路形成装置である。
【００２８】
ここにいう「負荷」は、前述の第１本装置において説明したのと同様である。
このような第３本装置を用いれば、全体負荷算出手段が、複数の地点の位置データを受け付け、該複数の地点全部を巡る全体の負荷を算出する。
そして、移動体数決定手段が、これら複数の地点の一部を巡る移動体それぞれが受け持ち可能な負荷の量である負荷許容量を受け付ける。さらに、移動体数決定手段が、全体負荷算出手段により評価された該全体の負荷と、該受け付けた該負荷許容量と、から移動体の数を所定の方法により決定する。
さらに、地点分割手段が、これら複数の地点を移動体の数（移動体数決定手段が決定したもの）だけ分割する。
移動体出発位置情報受付手段が、移動体それぞれの出発位置を示す出発位置情報を受け付ける。
そして、移動体割当手段が、地点分割手段により分割された地点のそれぞれのグループに対し所定の位置関係を有する出発位置情報に係る移動体を割り当てる。
最後に、各グループ原始経路形成手段が、移動体割当手段により割当られた移動体の出発位置を始点とし、移動体に対応するグループに属する全ての地点を巡る各グループ毎の経路を作成する。
【００２９】
従って、巡るべき複数の地点の位置データと、これら複数の地点の一部を巡る移動体それぞれが受け持ち可能な負荷許容量と、移動体それぞれの出発位置と、を受け付けることで、第３本装置は、必要な移動体の数に応じて複数の地点をグループに分割し、各グループに移動体を割り当て、そして各グループ毎に該グループに割り当てられた移動体の出発位置を始点とする、該グループに属する全ての地点を巡る経路を作成する。
このため第３本装置は、複数の場所を複数の移動体によって巡回する場合、各移動体がどの場所を受け持ち、さらに各移動体がどのようにこれら受け持ち場所を巡るかを決定することができる。
【００３０】
第３本装置においては、前記各グループ原始経路形成手段によって形成された各グループ毎の経路に関する負荷を全てのグループに関して合計した第１総量と、前記移動体数決定手段によって受け付けられ、各グループに割当られた移動体それぞれの負荷許容量を合計した第２総量と、を比較し、第２総量が第１総量以上であるか否か判断する総量判断手段と、該総量判断手段が、第２総量が第１総量以上であると判断しない場合、移動体の数を増加させる移動体増加手段と、を、さらに備え、前記地点分割手段は該増加された移動体の数に応じて複数の地点を分割し、前記移動体割当手段は、該増加された移動体の数に応じて分割された地点のそれぞれのグループに移動体を割り当て、そして前記各グループ原始経路形成手段は、該増加された移動体の数に応じて分割された地点のそれぞれのグループ毎の経路を作成するものであってもよい。
【００３１】
こうすることで、総量判断手段が、各グループに割当られた移動体それぞれの負荷許容量を合計した第２総量が、各グループ原始経路形成手段によって形成された各グループ毎の経路に関する負荷を全てのグループに関して合計した第１総量以上であるかを判断する。これは受け持つ移動体全ての負荷許容量（能力）が、各グループの経路に関する負荷の総量以上でなければ実行不可能であることによる。
従って、移動体増加手段は、総量判断手段が、第２総量が第１総量以上であると判断しない場合、移動体の数を増加させる。そして、増加した移動体の数によって地点分割手段が複数の地点を分割し、移動体割当手段は、該増加された移動体の数に応じて分割された地点のそれぞれのグループに移動体を割り当て、そして各グループ原始経路形成手段は、該増加された移動体の数に応じて分割された地点のそれぞれのグループ毎の経路を作成する（即ち、移動体の数を増加させ、その増加した移動体の数によって地点分割手段と移動体割当手段と各グループ原始経路形成手段とが動作する。）。
これにより第３本装置により形成される経路が、一層確実に実行可能なものになる。
【００３２】
第３本装置は、それ自身単独で使用できることは言うに及ばないが、第１本装置又は第２本装置と組み合わせて使用されることもできる。この場合、第３本装置が形成した移動体の出発位置を始点とする各グループ毎の経路を、第１本装置又は第２本装置の経路データ受付手段が経路データとして受け付けるようにすればよい。かかるように構成すれば、複数の場所を複数の移動体によって巡回する場合、各移動体がどの場所を受け持ち、さらに各移動体がどのようにこれら受け持ち場所を巡るかについて第３本装置が形成した経路を、うまく調整することができる（第１本装置と組み合わせば各経路間の負荷の差を減少させることができ、第２本装置と組み合わせば負荷を低減することができる。）。
【００３３】
また、第１本装置及び第２本装置も、いずれかを単独で使用できることは言うに及ばないが、第１本装置と第２本装置とを組み合わせて使用することもできる。これら両者を組み合わせる前後は問わないが（即ち、第１本装置によって得られた結果を第２本装置によって調整する場合と、第２本装置によって得られた結果を第１本装置によって調整する場合と、のいずれでもよい。）、前に位置するものは経路データを後に位置するものに引き渡す必要があるので、前に位置するものは経路形成手段を備える必要がある。
即ち、経路形成手段所有第１本装置の経路形成手段によって形成された経路を、第２本装置の経路データ受付手段が経路データとして受け付けさらに経路調整するように構成してもよい。さらに、かかる場合、第３本装置が形成した移動体の出発位置を始点とする各グループ毎の経路を、経路形成手段所有第１本装置の経路データ受付手段が経路データとして受け付けるように構成してもよい。
逆に、経路形成手段所有第２本装置の経路形成手段によって形成された経路を、第１本装置の経路データ受付手段が経路データとして受け付けさらに経路調整するように構成してもよい。さらに、かかる場合、第３本装置が形成した移動体の出発位置を始点とする各グループ毎の経路を、経路形成手段所有第２本装置の経路データ受付手段が経路データとして受け付けるように構成してもよい。
このように第１本装置と第２本装置とを組み合わせることで、各経路間の負荷の差を減少させることと負荷を低減することとを一度に行うことができる。
【００３４】
第１本装置と第２本装置と第３本装置とのいずれも、所定のプログラムをコンピュータに実行させることで実現させることができ、さらに、かかるプログラムはコンピュータ読みとり可能な記憶媒体に記録することができる。
【００３５】
【発明の実施の形態】
以下、本発明の実施の形態を図面を参照して説明する。しかしながら、これらによって本発明は何ら制限されるものではない。
【００３６】
図１は、一実施形態の本発明の経路探索装置（本装置）１１のハードウエア構成を示す概略ブロック図である。図１を参照して、一実施形態の本装置１１のハードウエア構成について説明する。ここでは本装置１１は、複数の配達点を複数の配達車両によって巡る際、それぞれの配達車両（移動体）がどの配達点（地点）を受け持ち、その受け持つ配達点をそれぞれの車両がどのように巡回するかの巡回経路を探索し決定する装置であり、上述の第１本装置、第２本装置及び第３本装置を含んで構成されている。
本実施形態では、本装置１１は、プログラムを内蔵させたコンピュータによって構成されており、本装置１１にはハードディスク１９が接続されている。
本装置１１は、演算処理を行うＣＰＵ１１ａ、ＣＰＵ１１ａの作業領域等となるＲＡＭ１１ｂ、制御プログラム等を記録するＲＯＭ１１ｃ、ハードディスク１９と情報のやり取りを行うためのインターフェイス１１ｄと、を有する。なお、図１には図示していないがこれ以外にも、本装置１１へデータを入力するためのキーボード、本装置１１から情報を表示するためのディスプレイ、そして本装置１１から情報を印刷するためのプリンタ等がインターフェイス１１ｄを介して本装置１１に接続されている。また、ここでは前記プログラム等はＲＯＭ１１ｃに記憶されているが、ハードディスク１９に記憶するようにしてよいことは言うまでもない。
【００３７】
図２に、図１のハードウエアと主としてＲＯＭ１１ｃに記録されるプログラムにより実現される本装置１１の大まかな基本構成を示す概略機能ブロック図を示す。図２を参照して、本装置１１の基本構成について説明する。
本装置１１は、機能的には、本装置１１の初期情報を記憶している初期情報データベース２１と、クラスタ分割部３１と、仮巡回路形成部４１と、所属調整部５１と、稼動率調整部６１と、ランダム挿入部７１と、Ｎ−ｏｐｔ部７３と、巡回時間算出部７５と、初期情報記憶部９１と、車両数記憶部９３と、クラスタ属性値記憶部９５と、経路記憶部９７と、履歴記憶部９８と、所要時間記憶部９９と、を備えている。
【００３８】
初期情報データベース２１は、ハードディスク１９の記憶領域の一部を用いて構成されており、既に、図３に示すようなデータが記憶されている。即ち、図３（ａ）に示された配達点（本発明にいう地点）の座標（地点の位置データ）と、図３（ｂ）に示されたデポ（移動体たる配達車両が出発し帰着する地点であり、出発位置や始点となりうる。）の座標（出発位置情報）と、図３（ｃ）に示された制約条件（負荷許容量）と、が初期情報データベース２１に既に記憶されている。図３（ａ）及び（ｂ）に示された配達点とデポとの座標はいずれも地表面に設定された直交座標たるＸＹ座標によって示されており、例えば、番号３の配達点の位置は（Ｘ，Ｙ）＝（４０１，８４１）によって示されており、番号２のデポの位置は（Ｘ，Ｙ）＝（４２２７，２２５９）によって示されている。そして、図３（ｃ）に示された制約条件は、ここでは配達車両それぞれの一日に移動可能な最大の移動距離（ここでは本発明にいう「負荷」として移動距離を用いている。）を該ＸＹ座標系における座標値として示しており、具体的には、ここでは配達車両０〜３の４台のいずれも１００００（座標）に定められている（なお、図３（ｃ）に示された配達車両の車両番号０〜３はそれぞれ図３（ｂ）のデポの番号０〜３に対応している。例えば、デポ３から出発する配達車両は車両３である。）。
【００３９】
図４は、クラスタ分割部３１の詳細機能ブロック図である。図４を参照して、クラスタ分割部３１の詳細構成について説明する。
クラスタ分割部３１は、機能的には、ファイル読み出し部３３とテーブル初期化部３５とクラスタ数計算部３７とを有してなる。
まず、ファイル読み出し部３３が起動すると（図示していないが、本装置１１に接続された前記キーボード等から所定の起動信号が入力されるとファイル読み出し部３３が起動する。）、ファイル読み出し部３３は初期情報データベース２１にアクセスして配達点の座標（複数の地点の位置データ）を読み込み（図３（ａ）に示したものであり、配達点の番号０〜４７それぞれに対応して（Ｘ，Ｙ）の座標を読み込む）、さらにファイル読み出し部３３は該読み込んだ配達点の座標を初期情報記憶部９１に書き込み記憶させる。次いで、ファイル読み出し部３３は初期情報データベース２１にアクセスしてデポの座標（移動体たる配達車両それぞれの出発位置を示す出発位置情報）を読み込み（図３（ｂ）に示したものであり、デポの番号０〜３それぞれに対応して（Ｘ，Ｙ）の座標を読み込む）、さらにファイル読み出し部３３は該読み込んだデポの座標を初期情報記憶部９１に書き込み記憶させる。さらに、ファイル読み出し部３３は初期情報データベース２１にアクセスして制約条件（移動体たる配達車両それぞれが受け持ち可能な負荷の量である負荷許容量）を読み込み（図３（ｃ）に示したものであり、車両の番号０〜３それぞれに対応して制約条件（ここでは全て１００００であるが、それぞれの車両に応じて異なる値が設定されることもある。）を読み込む）、さらにファイル読み出し部３３は該読み込んだ制約条件を初期情報記憶部９１に書き込み記憶させる。以上のようにして、初期情報データベース２１が記憶していた配達点の座標（図３（ａ））、デポの座標（図３（ｂ））、そして制約条件（図３（ｃ））の全てが、そっくり初期情報記憶部９１にコピーされる。なお、初期情報記憶部９１は、図１にて前述のＲＡＭ１１ｂの記憶領域の一部を用いて構成される。
その後、ファイル読み出し部３３は、テーブル初期化部３５に起動信号を発する。
【００４０】
ファイル読み出し部３３から該起動信号を受信したテーブル初期化部３５は、初期情報記憶部９１にアクセスして初期情報記憶部９１が記憶している配達点の座標（図３（ａ））とデポの座標（図３（ｂ））とを読み出し取得し、配達点０〜４７とデポ０〜３との合計５２の場所それぞれ（起点）から自ら（起点）を除く５１の場所（終点）までの距離を算出し、それら算出された距離を図５に示すような２次元のテーブルとしてまとめる（なお、図５では、図示を容易にすること等のために、テーブル中に書き込まれるべき距離データの記載を省略している。）。なお、ここで行われる距離の算出は、起点の位置と終点の位置との直線距離を算出する（即ち、起点座標（ｘ１，ｙ１）と終点座標（ｘ２，ｙ２）とすると、（（ｘ１−ｘ２）２＋（ｙ１−ｙ２）２）０．５により計算される。）が、配達点及びデポが存する場所の地図情報をテーブル初期化部３５が予め有しておき、テーブル初期化部３５が該地図情報を用いて実際の道路に沿った最短距離（地図情報を用いて実際の道路に沿った２点間の距離を計算することは、車載ナビゲーションシステム等において既に広く行われているので、ここでは説明を省略する。）を計算するようにしてよいことは言うまでもない。
さらに、テーブル初期化部３５は、図５に示すような該まとめた２次元のテーブル（以下、「距離テーブル」という。）を所要時間記憶部９９に書き込み記憶させる。
その後、テーブル初期化部３５は、クラスタ数計算部３７に起動信号を発する。
【００４１】
テーブル初期化部３５から該起動信号を受信したクラスタ数計算部３７は、起動信号をランダム挿入部７１に送信する。
クラスタ数計算部３７から該起動信号を受信したランダム挿入部７１は、初期情報記憶部９１にアクセスして初期情報記憶部９１が記憶している配達点の座標（図３（ａ）：複数の地点の位置データ）を読み出し取得すると共に、所要時間記憶部９９にアクセスして所要時間記憶部９９が記憶している距離テーブル（図５参照）を読み出し取得する。そして、ランダム挿入部７１は、これら読み出し取得した配達点の座標と距離テーブルとを用いてランダム挿入法によって巡回路（即ち、全ての配達点を巡回する順番。具体的には、巡回する順番に従って配達点の番号を並べたもの）を作成し、その巡回路をクラスタ数計算部３７へ送信する。なお、ランダム挿入法とは、複数の地点を巡回するための巡回路を作成する標準的な公知の方法である。また、ここではランダム挿入法によって巡回路を作成しているが、これに限定されるものではなく、巡回路を何らかの方法によって形成するものであればいかなるものを用いてもよく、ランダム挿入法以外のものの一例を挙げれば、最遠挿入法、凸包、空間充填曲線法、バケット法、Ｋａｒｐの分割算法等を例示することができる。
【００４２】
ランダム挿入部７１から巡回路を受信したクラスタ数計算部３７は、該受信した巡回路をＮ−ｏｐｔ部７３に送信する。
クラスタ数計算部３７から該受信した巡回路を受信したＮ−ｏｐｔ部７３は、初期情報記憶部９１にアクセスして初期情報記憶部９１が記憶している配達点の座標（図３（ａ））を読み出し取得し、さらに所要時間記憶部９９にアクセスして所要時間記憶部９９が記憶している距離テーブル（図５参照）を読み出し取得し、これら配達点の座標（図３（ａ））と距離テーブルとを用いて、該受信した巡回路にＮ−ｏｐｔ法（処理時間を考慮すれば２−ｏｐｔ法又は３−ｏｐｔ法としてもよく、ここでは２−ｏｐｔ法を用いる。）を適用して該受信した巡回路を改善する。このときＮ−ｏｐｔ法を実行する際の起点の配達点は、クラスタ数計算部３７から受信した該巡回路の最初の配達点とする。なお、Ｎ−ｏｐｔ法とは、巡回路の局所的な最適化を行う方法であり、経由地（ここでは配達点）の対象を任意の数Ｎで実行できるようにしたものの総称をいう（例えば、「ｈｔｔｐ：／／ｗｗｗ．ｄａｉｓｙ．ａｉ．ｋｙｕｔｅｃｈ．ａｃ．ｊｐ／￣ｓｉｎ／ｄｅｍｏｓ／ＴＳＰ／」参照。このＮ−ｏｐｔ法の中で最も簡単なものが２−ｏｐｔ法である。この「２」は巡回する順序を交換する都市の数である。）。また、ここではＮ−ｏｐｔ法によって巡回路を改善しているが、これに限定されるものではなく、何らかの巡回路があるときに、それをより優れたものに改善する（例えば、巡回路を巡る際のコストを下げること等）ものであればいかなるものを用いてもよく、２−ｏｐｔ法や３−ｏｐｔ法等のＮ−ｏｐｔ法以外のものの一例を挙げれば、ＬｉｎとＫｅｒｎｉｇｈａｍの算法の改善法を例示することができる。
Ｎ−ｏｐｔ部７３は、Ｎ−ｏｐｔ法を適用して改善した巡回路（配達点を巡回する順番）をクラスタ数計算部３７に送信する。
このようにしてＮ−ｏｐｔ部７３からクラスタ数計算部３７が受信した該改善した巡回路の一例（巡回路を座標中に図示したもの）を図６に示した。図６では、Ｎ−ｏｐｔ法を実行する際の起点の配達点を点Ａとして示し、巡回方向を矢印Ｂによって示した。なお、図６の結果は、図３（ａ）に示した配達点の座標を用いて得られた結果である。
【００４３】
Ｎ−ｏｐｔ部７３から前記改善した巡回路（以下、「改善巡回路」という。）を受信したクラスタ数計算部３７は、改善巡回路を巡回時間算出部７５に送信する。
改善巡回路を受信した巡回時間算出部７５は、所要時間記憶部９９が記憶している距離テーブルを読み出し取得し、改善巡回路の全距離（複数の地点全部を巡る全体の負荷）を距離テーブルを用いて算出する。この算出された改善巡回路の全距離は、巡回時間算出部７５からクラスタ数計算部３７へ送信される。なお、図６に示した改善巡回路の全距離は３５５８７と算出される。
以上説明したように、クラスタ数計算部３７とランダム挿入部７１とＮ−ｏｐｔ部７３と巡回時間算出部７５とによって、複数の地点の位置データを受け付け、該複数の地点全部を巡る全体の負荷を算出する（第３本装置の）全体負荷算出手段が構成されている。
【００４４】
改善巡回路の全距離を巡回時間算出部７５から受信したクラスタ数計算部３７は、初期情報記憶部９１にアクセスし初期情報記憶部９１が記憶している制約条件（図３（ｃ）：移動体たる配達車両それぞれが受け持ち可能な負荷の量である負荷許容量であり、具体的には、配達車両それぞれの一日に移動可能な最大の移動距離）を読み出し取得し、各配達車両の制約条件の相加平均値を算出する（ここでは車両０〜３の４台とも１００００であるので相加平均値は１００００（４×１００００／４）となる。）。
次いで、クラスタ数計算部３７は、巡回時間算出部７５から受信した改善巡回路の全距離を該相加平均値によって除し（全距離／該相加平均値）、得られた商の小数部分を切り上げて車両台数とする（例えば、商が３．０００２であれば車両台数を４とし、商が５（割り切れた場合）であれば車両台数を５とする。）。なお、ここでは改善巡回路の全距離は３５５８７であり、各配達車両の制約条件の相加平均値は１００００であるので、（全距離／相加平均値）の商は３．５５８７となり小数部分を切り上げて車両台数４となった。
そして、クラスタ数計算部３７は、得られた車両台数を車両数記憶部９３へ送信し車両数記憶部９３に記憶させる。
以上説明したように、クラスタ数計算部３７によって、複数の地点（配達点）の一部を巡る移動体（配達車両）それぞれが受け持ち可能な負荷の量である負荷許容量（制約条件たる図３（ｃ））を受け付け、（第３本装置の）全体負荷算出手段により評価された該全体の負荷と該負荷許容量とから該移動体の数を所定の方法により決定する（第３本装置の）移動体数決定手段が構成されている。
最後に、クラスタ数計算部３７は、仮巡回路形成部４１（後述のファジークラスタリング計算部４３）に起動信号を発する。
【００４５】
図７は、仮巡回路形成部４１の詳細機能ブロック図である。図７を参照して、仮巡回路形成部４１の詳細構成について説明する。
仮巡回路形成部４１は、機能的には、ファジークラスタリング計算部４３と初期巡回路作成部４５とを有してなる。
まず、クラスタ数計算部３７から前記起動信号を受信したファジークラスタリング計算部４３は、車両数記憶部９３にアクセスして車両数記憶部９３が記憶している車両台数（ここでは４）を読み出し取得する。そして、ファジークラスタリング計算部４３は、初期情報記憶部９１にアクセスして初期情報記憶部９１が記憶している配達点の座標（図３（ａ））を読み出し取得する。さらに、ファジークラスタリング計算部４３は、読み出し取得した車両台数（ここでは４）をクラスタ数として、各配達点の各クラスタへの帰属度を計算する。なお、このファジークラスタリングの処理方法は公知の技術であり、例えば、特開平０５−２７４２９３号に詳細に記載されている（ファジークラスタリングの方法の一つであるファジイｃ−ｍｅａｎｓ法を参考文献を含めて詳述している。これにより各クラスタへの帰属度が計算される。）のでここでは説明を省略する。このようにして計算された各配達点（配達点０〜４７）の各クラスタ（クラスタ０〜３）への帰属度を図８に示す。例えば、番号１０の配達点の帰属度は、クラスタ０には０．４９、クラスタ１には０．０３、クラスタ２には０．３８、クラスタ３には０．１であることが分かる。
そして、ファジークラスタリング計算部４３は、計算した各配達点の各クラスタへの帰属度（図８）をクラスタ属性値記憶部９５に送信しクラスタ属性値記憶部９５に記憶させる。
最後に、ファジークラスタリング計算部４３は、計算した各配達点の各クラスタへの帰属度（図８）を初期巡回路作成部４５へ送信する。
【００４６】
各配達点の各クラスタへの帰属度（図８）をファジークラスタリング計算部４３から受信した初期巡回路作成部４５は、配達点それぞれについて最も帰属度が高いクラスタ（即ち、グループ）に属すると判断し、全ての配達点がいずれのクラスタ（グループ）に属するかを決定する。この配達点の所属クラスタの決定の方法を図９に示した。即ち、初期巡回路作成部４５は、各配達点（配達点０〜４７）それぞれについてクラスタ０、クラスタ１、クラスタ２、クラスタ３への帰属度を比較し、最も帰属度が大きなクラスタに属すると決定する。例えば、番号１０の配達点の帰属度は、クラスタ０には０．４９、クラスタ１には０．０３、クラスタ２には０．３８、クラスタ３には０．１であるので、番号１０の配達点は、最大の帰属度０．４９を与えるクラスタ０に属すると決定されている。この決定を全ての配達点０〜４７について実施し、図９に示すような結果を得る。そして、初期巡回路作成部４５は、図１０に示すような各クラスタに所属する配達点の番号を各クラスタ毎に記載した配達点番号リストを作成し、その配達点番号リストを経路記憶部９７に送信し経路記憶部９７に記憶させる。
以上説明したように、ファジークラスタリング計算部４３と初期巡回路作成部４５とによって、複数の地点（配達点）を該移動体の数（（第３本装置の）移動体数決定手段によって決定された数）だけ分割する（第３本装置の）地点分割手段が構成されている。
【００４７】
次いで、初期巡回路作成部４５は、初期情報記憶部９１にアクセスして初期情報記憶部９１が記憶している配達点の座標（図３（ａ））を読み出し取得すると共に、自らが作成した前述の配達点番号リストと該読み出し取得した配達点の座標とを用いて各クラスタの重心位置（Ｘ，Ｙ）を求める。この重心位置の求め方は、各クラスタに属する各配達点が全て同じ質量を有するとして算出する。
さらに、初期巡回路作成部４５は、初期情報記憶部９１にアクセスして初期情報記憶部９１が記憶しているデポの座標（図３（ｂ）：移動体たる配達車両それぞれの出発位置を示す出発位置情報）を読み出し取得すると共に、先に求めた各クラスタの重心に最も近いデポを選択することで各クラスタにデポを割り当てる。そして、初期巡回路作成部４５は、経路記憶部９７にアクセスし経路記憶部９７が記憶している配達点番号リストの各クラスタに割り当てたデポを図１１に示すように書き込む。なお、ここでは各クラスタの重心に最も近いデポを選択することで各クラスタにデポを割り当てるようにしたが、これに限定されるものではなく、例えば、各クラスタに属する配達点との距離が小さいデポをそのクラスタに割り当てるようにしてもよい。
以上説明したように、初期巡回路作成部４５によって、移動体（配達車両）それぞれの出発位置を示す出発位置情報（図３（ｂ））を受け付ける（第３本装置の）移動体出発位置情報受付手段が構成されている。そして、初期巡回路作成部４５によって、（第３本装置の）地点分割手段により分割された地点（配達点）のそれぞれのグループ（クラスタ）に対し所定の位置関係（ここでは各クラスタの重心に最も近い位置関係）を有する出発位置情報に係る移動体（配達車両）を割り当てる（第３本装置の）移動体割当手段が構成されている。
その後、初期巡回路作成部４５は、既に自らが有している配達点番号リスト（割り当てデポが記載された図１１に示すもの）をランダム挿入部７１に送信する。
【００４８】
配達点番号リストを初期巡回路作成部４５から受信したランダム挿入部７１は、初期情報記憶部９１にアクセスして初期情報記憶部９１が記憶している配達点の座標（図３（ａ））とデポの座標（図３（ｂ））とを読み出し取得すると共に、所要時間記憶部９９にアクセスして所要時間記憶部９９が記憶している距離テーブル（図５参照）を読み出し取得する。そして、ランダム挿入部７１は、これら読み出し取得した配達点の座標、デポの座標及び距離テーブルとを用いて、受信した配達点番号リストの各クラスタ毎に該クラスタに割り当てられたデポ（移動体割当手段により割当られた移動体の出発位置）を始点として該クラスタに属する全ての配達点を巡回する巡回路（以下、「クラスタ別初期巡回路」という。）を前述のランダム挿入法によって作成し、クラスタ別初期巡回路を初期巡回路作成部４５に送信する。
クラスタ別初期巡回路を受信した初期巡回路作成部４５は、クラスタ別初期巡回路をＮ−ｏｐｔ部７３に送信する。
初期巡回路作成部４５からクラスタ別初期巡回路を受信したＮ−ｏｐｔ部７３は、初期情報記憶部９１にアクセスして初期情報記憶部９１が記憶している配達点の座標（図３（ａ））とデポの座標（図３（ｂ））とを読み出し取得し、さらに所要時間記憶部９９にアクセスして所要時間記憶部９９が記憶している距離テーブル（図５参照）を読み出し取得し、これら配達点の座標（図３（ａ））、デポの座標（図３（ｂ））及び距離テーブルを用いて、クラスタ別初期巡回路に前述のＮ−ｏｐｔ法を（各クラスタ毎に）適用してクラスタ別初期巡回路を改善し、改善されたクラスタ別初期巡回路（以下、「改善クラスタ別初期巡回路」という。）を初期巡回路作成部４５へ送信する。
以上説明したように、ランダム挿入部７１とＮ−ｏｐｔ部７３とによって（ランダム挿入部７１からＮ−ｏｐｔ部７３へのクラスタ別初期巡回路の受け渡しを考慮すると初期巡回路作成部４５も含む。）、移動体割当手段により割当られた移動体（配達車両）の出発位置（デポ）を始点とし、それぞれの移動体（配達車両）に対応するグループ（クラスタ）に属する全ての地点を巡る各グループ（クラスタ）毎の経路（改善クラスタ別初期巡回路）を作成する（第３本装置の）各グループ原始経路形成手段が構成されている。
改善クラスタ別初期巡回路を受信した初期巡回路作成部４５は、経路記憶部９７にアクセスし経路記憶部９７が記憶している配達点番号リストの所属配達点の配達点番号の記載順序を改善クラスタ別初期巡回路に従った順序に書き換える（これにより経路記憶部９７が記憶している配達点番号リストの所属配達点の記載の順序が改善クラスタ別初期巡回路を示すことになる。）。このようにして得られた改善クラスタ別初期巡回路を図１２に示した。図１２中、■（黒く塗りつぶした略正方形）がそれぞれのデポを示している。なお、図１２中、クラスタ０〜３それぞれを「Ｎｏ．０」〜「Ｎｏ．３」によって示し、巡回方向は時計回り方向である。
【００４９】
その後、初期巡回路作成部４５は改善クラスタ別初期巡回路を巡回時間算出部７５へ送信する。改善クラスタ別初期巡回路を受信した巡回時間算出部７５は、所要時間記憶部９９が記憶している距離テーブルを読み出し取得し、改善クラスタ別初期巡回路に示される各クラスタ毎の巡回距離を距離テーブルから算出する。この算出された各クラスタ毎の巡回距離は、巡回時間算出部７５から初期巡回路作成部４５へ送信される。なお、図１２に示す改善クラスタ別初期巡回路に応じた各クラスタ毎の巡回距離は、クラスタ０が１０２４１であり、クラスタ１が９５０９であり、クラスタ２が１１３７５であり、クラスタ３が４６４７であった。
改善クラスタ別初期巡回路に応じた各クラスタ毎の巡回距離を受信した初期巡回路作成部４５は、初期情報記憶部９１にアクセスし初期情報記憶部９１が記憶している制約条件（図３（ｃ）：負荷許容量）のうち改善クラスタ別初期巡回路に使用されているデポに対応する車両の制約条件を読み出し取得し、該読み出し取得した制約条件（配達車両それぞれの一日に移動可能な最大の移動距離）の合計値（第２総量）を算出する（ここではデポ０〜３の全てが使用されており、それに対応する車両０〜３の４台とも１００００であるので合計値は４００００となる。）と共に、該受信した各クラスタ毎の巡回距離の合計（第１総量）を算出する（ここでは前述のように１０２４１＋９５０９＋１１３７５＋４６４７＝３５７７２となる。）。そして、初期巡回路作成部４５は、制約条件の合計値（第２総量。ここでは４００００）が巡回距離の合計値（第１総量。ここでは３５７７２）以上か否か判断し、そうであればこの改善クラスタ別初期巡回路は妥当と判断し、所属調整部５１（経路制御部５２）へ起動信号を発する。そして制約条件の合計値が巡回距離の合計値以上でなければ、初期巡回路作成部４５は、この改善クラスタ別初期巡回路は妥当と判断せず、ファジークラスタリング計算部４３に車両台数に１を加える信号を発した後、クラスタ数計算部３７からファジークラスタリング計算部４３に発せられる前記起動信号と同じ信号を送信する（即ち、これにより１増加した車両台数によって上述した仮巡回路形成部４１の動作が繰り返される。）。
以上説明したように、初期巡回路作成部４５によって、各グループ原始経路形成手段によって形成された各グループ（クラスタ）毎の経路（改善クラスタ別初期巡回路）に関する負荷（巡回距離）を全てのグループ（クラスタ）に関して合計した第１総量と、移動体数決定手段によって受け付けられ、各グループ（クラスタ）に割当られた移動体（配達車両）それぞれの負荷許容量（制約条件）を合計した第２総量と、を比較し、第２総量が第１総量以上であるか否か判断する（第３本装置の）総量判断手段が構成されている。そして、総量判断手段たる初期巡回路作成部４５が第２総量が第１総量以上であると判断しない場合、移動体の数を増加させる（第３本装置の）移動体増加手段が、初期巡回路作成部４５によって構成されている。地点分割手段は該増加された移動体の数に応じて複数の地点を分割し、移動体割当手段は、該増加された移動体の数に応じて分割された地点のそれぞれのグループに移動体を割り当て、そして各グループ原始経路形成手段は、該増加された移動体の数に応じて分割された地点のそれぞれのグループ毎の経路を作成する。
【００５０】
図１３は、所属調整部５１の動作を説明するための詳細な機能ブロック図である。図１３を参照して、所属調整部５１の詳細構成について説明する。
所属調整部５１は、機能的には、経路制御部５２と所属変更処理部５３と履歴チェック部５４と都市所属変更処理部５５と所属変更結果設定部５６とを有してなる。
まず、初期巡回路作成部４５から前記起動信号を受信した経路制御部５２は、初期情報記憶部９１にアクセスし初期情報記憶部９１が記憶している制約条件（図３（ｃ））を読み出し取得し（後述の稼動率の算出に用いる。）、所要時間記憶部９９にアクセスし所要時間記憶部９９が記憶している距離テーブルを読み出し取得し、さらに経路記憶部９７にアクセスし経路記憶部９７が記憶している改善クラスタ別初期巡回路（始点と、複数の地点を巡る経路と、を含んでなる複数の経路データ）を読み出し取得する。
次いで、経路制御部５２は、これら読み出し取得した距離テーブル及び改善クラスタ別初期巡回路を用いて改善クラスタ別初期巡回路における各クラスタ毎の巡回距離を算出する。
そして、経路制御部５２は、各配達車両毎の稼動率を算出する。稼動率は、上記のように算出された各クラスタ毎の巡回距離を、該クラスタを担当する配達車両の制約条件（図３（ｃ）、ここでは全て１００００）によって除した商として定義される。
さらに、経路制御部５２は、各配達車両毎の稼動率の平均値（算術）を求め、それを用いて均等化係数を算出する。均等化係数は、それぞれの配達車両について、（該配達車両の稼動率−稼動率の平均値）の絶対値（即ち、｜（各配達車両の稼動率）−（稼動率の平均値）｜）を求め、全ての配達車両について求めた該絶対値を合計して合計値を求め、配達車両の数によって該合計値を除すことによって算出される（即ち、均等化係数＝Σ（｜（各配達車両の稼動率）−（稼動率の平均値）｜）／（配達車両の数）として算出される。）。
最後に、経路制御部５２は、上記のようにして算出した各配達車両毎の稼動率及び均等化係数を、所属変更処理部５３へ送信する。
【００５１】
各配達車両毎の稼動率及び均等化係数を経路制御部５２から受信した所属変更処理部５３は、該受信した均等化係数が、自ら（所属変更処理部５３）が記憶している均等化係数よりも小さいか（後述するように、所属変更処理部５３は、これまでの最小の均等化係数を記憶するようになっているので、該受信した均等化係数が、これまでの最小の均等化係数よりも小さいかどうかを判断することになる。）、又は自ら（所属変更処理部５３）が均等化係数を記憶していないかを判断し、そのいずれかであると判断した場合には、該受信した均等化係数を上書きして記憶した後（即ち、所属変更処理部５３は、それまでに経路制御部５２から受信した均等化係数のうち最小のものを記憶することになる。）、経路制御部５２から受信した各配達車両毎の稼動率を都市所属変更処理部５５へ送信する。一方、所属変更処理部５３が、該受信した均等化係数が、自らが記憶している均等化係数よりも小さいか、又は自らが均等化係数を記憶していないかのいずれでもないと判断した場合（即ち、所属変更処理部５３が均等化係数を記憶しており、かつ該受信した均等化係数が、該記憶している均等化係数以上である場合）には履歴チェック部５４に起動信号を発する。
【００５２】
各配達車両毎の稼動率を所属変更処理部５３から受信した都市所属変更処理部５５は、初期情報記憶部９１にアクセスし初期情報記憶部９１が記憶している配達点の座標（図３（ａ））とデポの座標（図３（ｂ））とを読み出し取得し、クラスタ属性値記憶部９５にアクセスしクラスタ属性値記憶部９５が記憶している各配達点の各クラスタへの帰属度（図８）を読み出し取得し、そして経路記憶部９７にアクセスし経路記憶部９７が記憶している改善クラスタ別初期巡回路（始点（デポ）と、複数の地点（配達点）を巡る経路と、を含んでなる複数の経路データ）を読み出し取得する。即ち、ここでは都市所属変更処理部５５によって、始点と、複数の地点を巡る経路と、を含んでなる複数の経路データを受け付ける（第１本装置の）経路データ受付手段が構成されている。
次いで、都市所属変更処理部５５は、所属変更処理部５３から受信した各配達車両毎の稼動率のうち最も高い稼動率を与える配達車両が担当するクラスタを、提供元のクラスタとして記憶すると共に、クラスタのリスト（都市所属変更処理部５５自身が有する記憶領域）にも記憶する。さらに、都市所属変更処理部５５は、所属変更処理部５３から受信した各配達車両毎の稼動率のうち最も低い稼動率を与える配達車両が担当するクラスタを、提供先のクラスタとして記憶する。このように、都市所属変更処理部５５によって、（第１本装置の）経路データ受付手段により受け付けられる複数の経路データのうち、負荷が最も軽い経路とは異なる経路である開始経路（ここでは負荷が最も重い経路である、提供元のクラスタの経路）と、該開始経路よりも負荷が軽い経路である完了経路（ここでは負荷が最も軽い経路である、提供先のクラスタの経路）と、を決定する（第１本装置の）開始完了決定手段が構成されている。なお、ここでは負荷を稼動率によって評価している。
【００５３】
その後、都市所属変更処理部５５は、クラスタのリストに記憶されたクラスタの経路に属する配達点（上述のように読み出し取得した改善クラスタ別初期巡回路（図１１）から得られる。）のうち、提供先のクラスタへの帰属度が最も高い配達点を選択する（各配達点の帰属度は、上述のように読み出し取得した各配達点の各クラスタへの帰属度（図８）を用いることで得られる。以下、選択された配達点を「選択点」という。）。なお、クラスタのリストに複数のクラスタが記憶されている場合では、複数のクラスタに属する全ての配達点から選択点を選択する（例えば、クラスタ５０、クラスタ６３、クラスタ７８の３つのクラスタがクラスタのリストに記憶されている場合では、クラスタ５０に属する配達点と、クラスタ６３に属する配達点と、クラスタ７８に属する配達点と、の全ての配達点から１の選択点を選択する。）。
例えば、クラスタのリストに記憶されたクラスタがクラスタ２であり、提供先のクラスタが３であれば、図１１及び図８を参照して（図９も同様の結果を示している。）、クラスタのリストに記憶されたクラスタ２に属する配達点のうち、提供先のクラスタ３への帰属度が最も高い配達点４６を選択点として選択する（配達点４６はクラスタ３への帰属度０．１６を与え、これはクラスタ２に属する配達点の中で最も高いクラスタ３への帰属度である。）。
そして、都市所属変更処理部５５は、選択点が所属しているクラスタを所属元クラスタとする。上述の例では、選択点たる配達点４６はクラスタ２に所属しているので、クラスタ２を所属元クラスタとする。
次に、都市所属変更処理部５５は、クラスタのリストに記憶されたクラスタ以外のクラスタ（クラスタのリストに複数のクラスタが記憶されている場合には、その複数のクラスタのいずれでもないクラスタ）へ選択点が示す帰属度のうち最も高い帰属度を示すクラスタを所属変更先クラスタとして選択し記憶する。例えば、上述の例では、クラスタのリストに記憶されたクラスタは２であるのでそのクラスタ以外のクラスタはクラスタ０，１，３であり、クラスタ０，１，３へ選択点４６が示す帰属度はそれぞれ０．３、０．０５、０．１６であるので（図８参照）、最も高い帰属度０．３を示すクラスタ０を所属変更先クラスタとして選択し記憶する。
【００５４】
その後、都市所属変更処理部５５は、自らが有する改善クラスタ別初期巡回路（経路記憶部９７から読み出した図１１に示すようなもの）の中の所属元クラスタの経路に属している選択点を削除する。例えば、上述の例であれば、改善クラスタ別初期巡回路の中の所属元クラスタであるクラスタ２に属している配達点は配達点４、１２、１３、２０、・・・・３８、４０、４６、４７であるので、選択点たる配達点４６を削除し、クラスタ２に属する配達点を配達点４、１２、１３、２０、・・・・３８、４０、４７とする。
さらに、都市所属変更処理部５５は、選択点を削除した自らが有する改善クラスタ別初期巡回路の中の所属変更先クラスタの経路に選択点を加える。例えば、上述の例であれば、改善クラスタ別初期巡回路の中の所属変更先クラスタ０に属している配達点は配達点０、２、７、８・・・・３２、３７、３９、４５であるので、選択点たる配達点４６を加え、クラスタ０に属する配達点を配達点０、２、７、８・・・・３２、３７、３９、４５、４６とする（選択点を加える位置はいずれにしてもよい。）。
最後に、都市所属変更処理部５５は、上述のように所属元クラスタから選択点が削除され所属変更先クラスタに選択点が加えられた自らが有する改善クラスタ別初期巡回路（以下、「選択点加除巡回路」という。）をランダム挿入部７１に送信する。
【００５５】
選択点加除巡回路を受信したランダム挿入部７１は、初期情報記憶部９１にアクセスして初期情報記憶部９１が記憶している配達点の座標（図３（ａ））とデポの座標（図３（ｂ））とを読み出し取得し、所要時間記憶部９９にアクセスし所要時間記憶部９９が記憶している距離テーブルを読み出し取得し、選択点加除巡回路に従って各クラスタ毎に該クラスタに割り当てられたデポを起点として該クラスタに属する全ての配達点を巡回する巡回路（以下、「ランダム挿入選択点加除巡回路」という。）を前述のランダム挿入法によって作成し、ランダム挿入選択点加除巡回路を都市所属変更処理部５５に送信する。
ランダム挿入選択点加除巡回路をランダム挿入部７１から受信した都市所属変更処理部５５は、経路記憶部９７にランダム挿入選択点加除巡回路を上書きし記憶させる。
【００５６】
そして、都市所属変更処理部５５は、ランダム挿入選択点加除巡回路を巡回時間算出部７５に送信する。
都市所属変更処理部５５からランダム挿入選択点加除巡回路を受信した巡回時間算出部７５は、所要時間記憶部９９が記憶している距離テーブルを読み出し取得し、ランダム挿入選択点加除巡回路の各クラスタ毎の距離を距離テーブルから算出する。この算出されたランダム挿入選択点加除巡回路に従った各クラスタ毎の距離は、巡回時間算出部７５から都市所属変更処理部５５へ送信される。
そして、都市所属変更処理部５５が履歴記憶部９８に選択点の加除処理に関する履歴を書き込み記憶させる（履歴は上書きではなく追加的に書き込み記憶される。）。なお、選択点の加除処理に関する履歴は、提供元のクラスタ、提供先のクラスタ、所属元クラスタ、所属変更先クラスタ、選択点たる配達点、各配達車両の稼動率の各項目を含んでいる。なお、図１４には、履歴記憶部９８に書き込まれて記憶されたこの履歴の一例を示している（図１４においては、理解及び説明を容易にするため、作業番号及び図番号を付記している。）。図１４の詳細については後述する。
【００５７】
その後、都市所属変更処理部５５は、所属変更先クラスタと提供先のクラスタとが一致するか否かを判断し、一致すると判断しない場合、このときの所属変更先クラスタを前述のクラスタのリストに記憶し（即ち、このときの所属変更先クラスタがクラスタのリストに追加され、次の処理の所属元クラスタとして選択される候補になる。）、その後、再び、都市所属変更処理部５５は、選択点、所属元クラスタ、所属変更先クラスタを新たに選択し、上述の処理を行う。一方、都市所属変更処理部５５は、所属変更先クラスタと提供先のクラスタとが一致すると判断する場合、ランダム挿入選択点加除巡回路のうちクラスタのリストに含まれている（１又は２以上の）クラスタと提供先のクラスタとの複数のクラスタの巡回路を経路記憶部９７（ランダム挿入選択点加除巡回路を記憶している。）からそれぞれ読み出し取得し、該それぞれ取得された巡回路をＮ−ｏｐｔ部７３に送信する。
都市所属変更処理部５５から複数のクラスタに関する巡回路（ランダム挿入選択点加除巡回路の一部）を受信したＮ−ｏｐｔ部７３は、初期情報記憶部９１にアクセスして初期情報記憶部９１が記憶している配達点の座標（図３（ａ））とデポの座標（図３（ｂ））とを読み出し取得し、さらに所要時間記憶部９９にアクセスして所要時間記憶部９９が記憶している距離テーブル（図５参照）を読み出し取得し、これら配達点の座標（図３（ａ））、デポの座標（図３（ｂ））及び距離テーブルを用いて、それぞれの巡回路に前述のＮ−ｏｐｔ法を（各クラスタ毎に）適用して改善し、改善された巡回路（ランダム挿入選択点加除巡回路の一部）（以下、「改善一部ランダム挿入選択点加除巡回路」という。）を都市所属変更処理部５５へ送信する。
そして、改善一部ランダム挿入選択点加除巡回路を受信した都市所属変更処理部５５は、経路記憶部９７にアクセスし経路記憶部９７が記憶しているランダム挿入選択点加除巡回路のうち改善一部ランダム挿入選択点加除巡回路に該当する部分を書き換える。
その後、都市所属変更処理部５５は、経路制御部５２に起動信号（初期巡回路作成部４５から経路制御部５２へ発せられる起動信号と同じ。）を発し、それを受信した経路制御部５２は、初期巡回路作成部４５から起動信号を受信したときと同様の前述の動作を行う。
【００５８】
以上説明したように、都市所属変更処理部５５によって、（第１本装置の）経路データ受付手段により受け付けられる複数の経路データの一経路（所属元クラスタの経路）に含まれる地点（配達点）である選択点と、該選択点と所定の関係（クラスタのリストに記憶されたクラスタ以外のクラスタへ選択点が示す帰属度のうち最も高い帰属度を示す関係）を有する他の経路（所属変更先クラスタの経路）と、を選択すると共に、該一経路から該他の経路へ該選択点を移動させる（一経路に含まれていた選択点を、一経路から除き、他の経路へ含める。即ち、一経路に属していた選択点を、一経路への所属を解き、他の経路へ所属させる。）ものであり、初回には開始経路を該一経路として選択し、次回以降は前回以前の該他の経路又は開始経路を該一経路として該選択と該移動との動作を繰り返す（第１本装置の）所属変更手段が構成されている。そして、都市所属変更処理部５５によって、該他の経路（所属変更先クラスタの経路）が該完了経路（提供先のクラスタの経路）と一致するか否か判断する（第１本装置の）完了判断手段が構成されている。さらに、（第１本装置の）所属変更手段が、（第１本装置の）完了判断手段が一致すると判断するまで繰り返し動作する。
また、ここでは（第１本装置の）所属変更手段たる都市所属変更処理部５５は、前記前回以前の該他の経路又は開始経路（クラスタのリストに記憶されたクラスタの経路）に含まれる地点のうち前記完了経路（提供先のクラスタの経路）への帰属度が最も高い地点を前記選択点として選択する。
さらに、（第１本装置の）所属変更手段たる都市所属変更処理部５５は、前記前回以前の該他の経路又は開始経路（クラスタのリストに記憶されたクラスタの経路）以外の経路へ前記選択点が示す帰属度のうち最も高い帰属度を示す経路を前記他の経路（所属変更先クラスタの経路）として選択する。
そして、ここではランダム挿入部７１によって、（第１本装置の）所属変更手段によって前記選択点が加除され、含まれる地点に変更が生じた経路に所属する地点を巡る順番を決定し経路を形成する（第１本装置の）経路形成手段が構成されている。
また、（第１本装置の）経路形成手段たるランダム挿入部７１によって形成された経路を含む経路データを、（第１本装置の）経路データ受付手段たる都市所属変更処理部５５が受け付けさらに経路調整する。
さらに、（第１本装置の）経路形成手段たるランダム挿入部７１によって形成された経路における経路毎の負荷のばらつきを示すデータである均等化データたる均等化係数を形成（算出）する（第１本装置の）均等化データ形成手段を経路制御部５２が構成している。そして、所属変更処理部５３が、均等化データたる均等化係数を記憶する（第１本装置の）均等化データ記憶手段を構成している（所属変更処理部５３は、これまでの最小の均等化係数を記憶する。）。さらに、所属変更処理部５３によって、（第１本装置の）均等化データ形成手段によって形成された直近の均等化データ（均等化係数）が、（第１本装置の）均等化データ記憶手段に記憶された過去の均等化データ（均等化係数）に比して、改善されているか否か（ここでは小さくなっているか否か）判断する（第１本装置の）改善判断手段が構成されている。そして（第１本装置の）改善判断手段たる所属変更処理部５３が、改善されていると判断した場合、（第１本装置の）経路形成手段（ランダム挿入部７１）によって形成された経路に係る経路データを（第１本装置の）経路データ受付手段（都市所属変更処理部５５）が受け付けさらに経路調節する。
【００５９】
一方、前述のように、各配達車両毎の稼動率及び均等化係数を経路制御部５２から受信した所属変更処理部５３が、該受信した均等化係数が、自らが記憶している均等化係数よりも小さいか、又は自らが均等化係数を記憶していないかを判断し、そのいずれでもないと判断した場合（即ち、所属変更処理部５３が均等化係数を記憶しており、かつ該受信した均等化係数が、該記憶している均等化係数以上である場合）には履歴チェック部５４に起動信号を発するが、該起動信号を受信した履歴チェック部５４は、履歴記憶部９８にアクセスして履歴記憶部９８が記憶している前記選択点の加除処理に関する履歴を読み込み取得する。そして、履歴チェック部５４は、該読み込み取得した前記選択点の加除処理に関する履歴のうち直近の履歴（例えば、図１４に示したものであれば、作業番号１９にて示された「提供元」（提供元のクラスタ：クラスタ３）、「提供先」（提供先のクラスタ：クラスタ２）、「所属元」（所属元クラスタ：クラスタ３）、「所属変更先」（所属変更先クラスタ：クラスタ２）、「配達点番号」（選択点たる配達点：配達点４６）によるもの。以下、「直近履歴」という。）と、直近履歴以外の履歴（例えば、図１４に示したものであれば、作業番号１〜１８に示されるそれぞれのもの。以下、「その他履歴」という。）と、を比較し、直近履歴と同一のものがその他履歴に存するか否かを判断する。履歴チェック部５４が、直近履歴と同一のものがその他履歴に存すると判断した場合、履歴チェック部５４は所属変更結果設定部５６に起動信号を送信する。履歴チェック部５４が、直近履歴と同一のものがその他履歴に存すると判断しない場合、履歴チェック部５４は、所属変更処理部５３に各配達車両毎の稼動率（所属変更処理部５３が経路制御部５２から受信したもの）を都市所属変更処理部５５へ送信することを命令する信号を発する。即ち、この後は、各配達車両毎の稼動率及び均等化係数を経路制御部５２から受信した所属変更処理部５３が、該受信した均等化係数が、自らが記憶している均等化係数よりも小さいか、又は自らが均等化係数を記憶していないかを判断しそのいずれかであると判断した場合に行われる処理と、該受信した均等化係数を上書きして記憶することを除いて同様の処理が行われる。
【００６０】
即ち、ここでは履歴記憶部９８が、（第１本装置の）所属変更手段が行う前記選択点の所属変更処理の履歴を記憶する（第１本装置の）履歴記憶手段を構成している。そして、履歴チェック部５４によって、直近の選択点の所属変更処理と同一の履歴を（第１本装置の）履歴記憶手段が記憶しているか否か（直近履歴と同一のものがその他履歴に存するか否か）判断する（第１本装置の）収束判断部が構成されている（なお、ここでは（第１本装置の）改善判断手段が、直近の均等化データが改善されていると判断しない場合、収束判断部たる履歴チェック部５４が、直近履歴と同一のものがその他履歴に存するか否かを判断するようにされている。）。さらに、収束判断部たる履歴チェック部５４が、直近の選択点の所属変更処理（直近の均等化データに係る選択点の所属変更処理）と同一の履歴を（第１本装置の）履歴記憶手段が記憶していると判断しない場合、（第１本装置の）経路形成手段によって形成された経路に係る経路データを（第１本装置の）経路データ受付手段が受け付けさらに経路調節する。
【００６１】
上述のように、履歴チェック部５４が直近履歴と同一のものがその他履歴に存すると判断し、履歴チェック部５４が発した起動信号を受信した所属変更結果設定部５６は、履歴記憶部９８にアクセスして履歴記憶部９８が記憶している前記選択点の加除処理に関する履歴を読み込み取得し、その各履歴に含まれる各配達車両の稼動率を用いて各履歴の均等化係数を計算する。次いで、所属変更結果設定部５６は、それら各履歴毎に計算した均等化係数のうち最も小さい値を与える巡回路を選択し、該選択した巡回路を経路記憶部９７に送信し経路記憶部９７に記憶させる。
その後、所属変更結果設定部５６は、稼動率調整部６１（稼動率調整制御部６３）に起動信号を発する。
【００６２】
図１５は、稼動率調整部６１の動作を説明するための詳細な機能ブロック図である。図１５を参照して、稼動率調整部６１の詳細構成について説明する。
稼動率調整部６１は、機能的には、稼動率調整制御部６３と変更試行部６５と結果出力部６７とを有してなる。
まず、所属変更結果設定部５６から前記起動信号を受信した稼動率調整制御部６３（（第２本装置の）経路データ受付手段）は、自らが記憶する後述の組み合わせ履歴リストに記憶されている内容を削除する（組み合わせ履歴リストに何も記憶されていなければ削除不要である）。
次いで、稼動率調整制御部６３は、初期情報記憶部９１にアクセスし初期情報記憶部９１が記憶している制約条件（図３（ｃ））を読み出し取得し（後述の稼動率の算出に用いる。）、さらに経路記憶部９７にアクセスし経路記憶部９７が記憶している巡回路（所属変更結果設定部５６が、最も小さい均等化係数を与える巡回路として選択したもの）を読み出し取得する。
そして、稼動率調整制御部６３は、この読み出し取得した巡回路を巡回時間算出部７５に送信する。
【００６３】
稼動率調整制御部６３から前記巡回路を受信した巡回時間算出部７５は、所要時間記憶部９９が記憶している距離テーブルを読み出し取得し、前記巡回路の各クラスタ毎の巡回距離を距離テーブルから算出する。この算出された前記巡回路に従った各クラスタ毎の巡回距離は、巡回時間算出部７５から稼動率調整制御部６３へ送信される。
前記巡回路に従った各クラスタ毎の巡回距離を巡回時間算出部７５から受信した稼動率調整制御部６３は、その受信した各クラスタ毎の巡回距離と、初期情報記憶部９１から読み出し取得した制約条件（図３（ｃ））と、を用いて各クラスタ毎の稼動率を算出する（なお、稼動率は、前述のように、各クラスタ毎の巡回距離を、該クラスタを担当する配達車両の制約条件（図３（ｃ）、ここでは全て１００００）によって除した商である。）。
次いで、稼動率調整制御部６３は、上記にて算出した各クラスタ毎の稼動率の大きい順番を決し、その大きい順番にクラスタ番号を並べる（例えば、各クラスタ毎の稼動率が、クラスタ３＞クラスタ０＞クラスタ２＞クラスタ１であれば、「３、０、２、１」とする。）。この並べたクラスタ番号（例えば、「３、０、２、１」）を「整列クラスタ番号」という。
【００６４】
その後、稼動率調整制御部６３は、自らが記憶する後述の候補リストに記憶されている内容を削除する（候補リストに何も記憶されていなければ削除不要である）。
次いで、稼動率調整制御部６３は、整列クラスタ番号の先頭に位置するクラスタ番号（整列クラスタ番号が「３、０、２、１」であるときは「３」）によって示されるクラスタ（ここではクラスタ３）を稼動率調整提供元クラスタとして選ぶ。
さらに、稼動率調整制御部６３は、稼動率調整提供元クラスタに属する配達点のいずれかを変更候補配達点ｐとして選択する。なお、後述するように稼動率調整提供元クラスタに属する配達点それぞれを変更候補配達点ｐとして以下の処理を行い稼動率調整提供元クラスタに属する配達点全てが変更候補配達点ｐになるまで処理を行う。具体的には、ここでは稼動率調整提供元クラスタの巡回路の最初に位置する配達点を最初の変更候補配達点ｐとしてまず選択し、その後巡回路の順番に配達点を選択してゆき、巡回路の最後の配達点まで選択し処理を行う。
【００６５】
そして、稼動率調整制御部６３は、全てのクラスタから１のクラスタを稼動率調整提供先クラスタとして選択する。ここではクラスタ番号の最も小さいもの、即ち、クラスタ０を最初に選択する。なお、後述するように、存在するクラスタそれぞれを稼動率調整提供先クラスタとして以下の処理を行い存在するクラスタ全てが稼動率調整提供先クラスタとして処理されるまで処理を行う。具体的には、ここではクラスタ番号の最も小さいもの（ここではクラスタ０）を最初に稼動率調整提供先クラスタとしてまず選択し、その後、クラスタ番号の順番に稼動率調整提供先クラスタを選択してゆき（クラスタ１、クラスタ２、・・）、存するクラスタのうち最大のクラスタ番号のクラスタ（ここではクラスタ３）まで選択し処理を行う。
【００６６】
その後、稼動率調整制御部６３は、稼動率調整提供元クラスタと稼動率調整提供先クラスタとが一致しているか否かを判断し、両クラスタが一致していると判断した場合には稼動率調整制御部６３は稼動率調整提供先クラスタとして次のクラスタを選択する（なお、全てのクラスタが稼動率調整提供先クラスタとして既に選択されており、他のクラスタが稼動率調整提供先クラスタとして選択できない場合には、変更候補配達点ｐとして次の配達点を選択する。）。
稼動率調整制御部６３が、稼動率調整提供元クラスタと稼動率調整提供先クラスタとが一致していないと判断した場合、稼動率調整制御部６３は、経路記憶部９７から読み出し取得した巡回路を変更試行部６５に送信する。
【００６７】
稼動率調整制御部６３から巡回路を受信した変更試行部６５は、変更候補配達点ｐを稼動率調整提供元クラスタ（の経路）から稼動率調整提供先クラスタ（の経路）へ所属を変更した際の巡回距離差を算出する（なお、変更試行部６５は所要時間記憶部９９が記憶している距離テーブルを読み出し取得し、巡回距離差を算出する。）。この巡回距離差の算出方法について図１６を用いて説明する。図１６（ａ）が変更候補配達点ｐの所属を変更する前を示し、図１６（ｂ）が変更候補配達点ｐの所属を変更した後を示している。そして図１６中では稼動率調整提供元クラスタ（の経路）をクラスタ（イ）（の経路）として示し、稼動率調整提供先クラスタ（の経路）をクラスタ（ロ）（の経路）として示し、点ａ、点ｂ、点ｃ、点ｄは配達点を示している。この図１６の例では、（ａ）から（ｂ）のように変更候補配達点ｐの所属がクラスタ（イ）からクラスタ（ロ）に移ることで、巡回距離差は、（（ａｐ＋ｂｐ−ａｂ）−（ｃｐ＋ｄｐ−ｃｄ））として計算される。
以上説明したように、稼動率調整制御部６３と変更試行部６５とによって、（第２本装置の）経路データ受付手段（稼動率調整制御部６３）により受け付けられる複数の経路データに含まれる各地点（配達点）を、該地点（配達点）が含まれていない経路（稼動率調整提供先クラスタの経路）に所属させた際に生じる全経路の負荷（距離）の変化（巡回距離差）を評価する（第２本装置の）全体負荷評価手段が構成されている。
【００６８】
この巡回距離差が正の値か否かを変更試行部６５が判断し（巡回距離差が正の値であれば、変更候補配達点ｐを稼動率調整提供元クラスタから稼動率調整提供先クラスタへ所属を変更する方が巡回距離が短くなることを示す。）、巡回距離差が正の値と判断した場合、そのときの稼動率調整提供元クラスタ、稼動率調整提供先クラスタ、変更候補配達点ｐたる配達点、巡回距離差のデータを関係付けた情報（変更候補データ）を変更試行部６５は稼動率調整制御部６３に送信する。
稼動率調整提供元クラスタ、稼動率調整提供先クラスタ、変更候補配達点ｐたる配達点、巡回距離差のデータを関係付けた情報を変更試行部６５から受信した稼動率調整制御部６３は、該関係付けた情報を候補リストとして記憶する（上書きではなく追加的に記憶する。）。なおこのとき候補リストへの記憶は、該関係付けた情報に含まれる巡回距離差が大きいものから順番に記憶される。即ち、（第２本装置の）全体負荷評価手段により評価される負荷（距離）の変化が、地点（配達点）の所属が変更される前に比して負荷が低減される（距離が短くなる）ことを示す場合における所属が変更される地点（配達点）と、該所属が変更される地点（配達点）が所属が変更される前に所属している経路である前所属経路たる稼動率調整提供元クラスタと、該所属が変更される地点が所属が変更される先の経路である後所属経路たる稼動率調整提供先クラスタと、を関連付けられたものを変更候補データとして記憶する（第２本装置の）負荷変化記憶手段が、稼動率調整制御部６３の候補リストによって構成されている。さらにここでは、変更候補データが、全経路の負荷（距離）の総和が、地点（配達点）の所属が変更される前に比してどの程度低減されるかを示す低減度合いたる巡回距離差のデータをさらに関連付けられた状態で記憶されている。
巡回距離差が正の値と変更試行部６５が判断しない場合には変更試行部６５が稼動率調整制御部６３に稼動率調整提供先クラスタとして次のクラスタを選択することを命令する信号を発する。
【００６９】
次のクラスタを選択することを命令する信号を受信するか又は前記関係付けた情報を候補リストとして記憶した後、稼動率調整制御部６３は稼動率調整提供先クラスタとして次のクラスタを選択する（なお、全てのクラスタが稼動率調整提供先クラスタとして既に選択されており、他のクラスタが稼動率調整提供先クラスタとして選択できない場合には、変更候補配達点ｐとして次の配達点を選択する。）。その後、上記した処理のうち稼動率調整制御部６３が、稼動率調整提供元クラスタと稼動率調整提供先クラスタとが一致しているか否かを判断する動作から繰り返す。
【００７０】
上述のように、全てのクラスタが稼動率調整提供先クラスタとして選択され、上記の処理が行われると（全てのクラスタが稼動率調整提供先クラスタとして既に選択されており、他のクラスタが稼動率調整提供先クラスタとして選択できない場合）、稼動率調整制御部６３は、稼動率調整提供元クラスタの次の配達点（変更候補配達点ｐとして既に選択されている配達点を除いた配達点のうち巡回路内で先頭に位置する配達点）を次の変更候補配達点ｐとして選び、上記した処理のうち稼動率調整制御部６３が稼動率調整提供先クラスタを選択する動作から繰り返す。
このようにして稼動率調整制御部６３が、稼動率調整提供元クラスタの配達点を変更候補配達点ｐとして順次選び、上記した処理のうち稼動率調整制御部６３が稼動率調整提供先クラスタを選択する動作から繰り返すことで、稼動率調整提供元クラスタの配達点の全てが変更候補配達点ｐとして選ばれて該動作が行われることによって、もはや変更候補配達点ｐとして未だ選択されていない配達点が稼動率調整提供元クラスタに存しないと稼動率調整制御部６３が判断すると、稼動率調整制御部６３は、次のクラスタ（整列クラスタ番号の中で、稼動率調整提供元クラスタとして選ばれているクラスタの次のクラスタ）を稼動率調整提供元クラスタとして選ぶ。その後、稼動率調整制御部６３は、上記した動作のうち、稼動率調整提供元クラスタに属する配達点のいずれかを変更候補配達点ｐとして選択する動作以降を繰り返す。
【００７１】
そして同様に、稼動率調整制御部６３が、クラスタを稼動率調整提供元クラスタとして順次選び、上記した処理のうち稼動率調整制御部６３が稼動率調整提供元クラスタに属する配達点のいずれかを変更候補配達点ｐとして選択する動作以降を繰り返すことで、クラスタの全てが稼動率調整提供元クラスタとして選ばれて該動作が行われることによって、もはや稼動率調整提供元クラスタとして未だ選択されていないクラスタが存しないと稼動率調整制御部６３が判断すると、稼動率調整制御部６３は、以下述べる候補チェックを行う。
【００７２】
候補チェックは、稼動率調整制御部６３が有する候補リスト（稼動率調整提供元クラスタ、稼動率調整提供先クラスタ、変更候補配達点ｐたる配達点、巡回距離差のデータを関係付けた情報（以下、「候補」という。）が、該巡回距離差が大きいものから順番に記憶されている。）に記憶される候補と、稼動率調整制御部６３が有し後述するようにこれまで行った所属変更の履歴を記憶している履歴リストに記憶された所属変更履歴（稼動率調整提供元クラスタ、稼動率調整提供先クラスタ、変更候補配達点ｐたる配達点、巡回距離、各配達車両の稼動率、均等化係数が記憶されている。）と、を稼動率調整制御部６３が見比べ、各候補が含む稼動率調整提供元クラスタ、稼動率調整提供先クラスタ、変更候補配達点ｐたる配達点と同じ稼動率調整提供元クラスタ、稼動率調整提供先クラスタ、変更候補配達点ｐたる配達点を含む所属変更履歴が存在すれば稼動率調整制御部６３が候補リストからその候補を削除し、存在しなければ次の候補をチェックする。候補リスト中に未チェックの候補がなくなるまで候補のチェックを行い、その後、稼動率調整制御部６３が候補リスト中に候補が残っているか否か判断し、残っていればその残っている候補のうち先頭に位置する候補を抽出しその候補に従って配達点が属するクラスタを変更する（即ち、先頭の候補に示された変更候補配達点ｐたる配達点を、稼動率調整提供元クラスタから稼動率調整提供先クラスタへ所属を変更する。具体的には、稼動率調整制御部６３は、経路記憶部９７から読み出した巡回路の中の稼動率調整提供元クラスタから変更候補配達点ｐを除き、稼動率調整提供先クラスタに変更候補配達点ｐを加える。）。稼動率調整制御部６３が、候補リスト中に候補が残っていると判断しない場合、稼動率調整制御部６３は結果出力部６７へ巡回路（経路記憶部９７から読み出し取得した巡回路）と履歴リストとを送信する。
従って、ここでは稼動率調整制御部６３によって、（第２本装置の）負荷変化記憶手段に記憶された変更候補データのうち所定の条件に合致するものを抽出する（第２本装置の）抽出手段が構成されている。なお、ここでは前述のように、変更候補データが、全経路の負荷（距離）の総和が、地点（配達点）の所属が変更される前に比してどの程度低減されるかを示す低減度合いたる巡回距離差のデータをさらに関連付けられた状態で記憶されており、（第２本装置の）抽出手段が抽出する際の前記所定の条件が、該低減度合いが最大であるという条件である。さらに、ここでは（第２本装置の）抽出手段により抽出された変更候補データの履歴を記憶する（第２本装置の）変更候補履歴記憶手段が、稼動率調整制御部６３が有する（第２本装置の）履歴リストによって構成されており、かつ（第２本装置の）抽出手段が、（第２本装置の）負荷変化記憶手段（稼動率調整制御部６３の候補リスト）に記憶された変更候補データのうち、（第２本装置の）変更候補履歴記憶手段に記憶された履歴と同一のものを除いた変更履歴データから抽出する。
【００７３】
稼動率調整制御部６３が、上述のように、候補リスト中に候補が残っていると判断し、残っている候補のうち先頭に位置する候補に従って配達点が属するクラスタを変更した後、稼動率調整提供元クラスタと稼動率調整提供先クラスタとのそれぞれに含まれる配達点（変更候補配達点ｐたる配達点が、前者は除かれ後者は加入されている。）をランダム挿入部７１に送信する。
該両方クラスタそれぞれに含まれる配達点を受信したランダム挿入部７１は、初期情報記憶部９１にアクセスして初期情報記憶部９１が記憶している配達点の座標（図３（ａ））とデポの座標（図３（ｂ））とを読み出し取得し、所要時間記憶部９９にアクセスし所要時間記憶部９９が記憶している距離テーブルを読み出し取得し、該両方の巡回路に従って両クラスタ毎に該クラスタに割り当てられたデポを起点として該クラスタに属する全ての配達点を巡回する巡回路を前述のランダム挿入法によって作成し、稼動率調整制御部６３に送信する。
【００７４】
ランダム挿入部７１から巡回路を受信した稼動率調整制御部６３は、該受信した巡回路をＮ−ｏｐｔ部７３に送信する。
稼動率調整制御部６３からその巡回路を受信したＮ−ｏｐｔ部７３は、初期情報記憶部９１にアクセスして初期情報記憶部９１が記憶している配達点の座標（図３（ａ））とデポの座標（図３（ｂ））とを読み出し取得し、さらに所要時間記憶部９９にアクセスして所要時間記憶部９９が記憶している距離テーブル（図５参照）を読み出し取得し、これら配達点の座標（図３（ａ））、デポの座標（図３（ｂ））及び距離テーブルを用いて、その巡回路（稼動率調整提供元クラスタと稼動率調整提供先クラスタとに関する両方の巡回路）に前述のＮ−ｏｐｔ法を（各クラスタ毎に）適用してその巡回路を改善し、改善された巡回路を稼動率調整制御部６３へ送信する。
以上説明したように、ここではランダム挿入部７１とＮ−ｏｐｔ部７３とによって、（第２本装置の）抽出手段によって抽出された変更候補データに従って経路を形成する（第２本装置の）経路形成手段が構成されている。
改善された巡回路をＮ−ｏｐｔ部７３から受信した稼動率調整制御部６３は、該改善された巡回路を巡回時間算出部７５に送信する。
稼動率調整制御部６３から該改善された巡回路を受信した巡回時間算出部７５は、所要時間記憶部９９が記憶している距離テーブルを読み出し取得し、該改善された巡回路の各クラスタ毎の巡回距離を距離テーブルから算出する。この算出された各クラスタ毎の巡回距離は、巡回時間算出部７５から稼動率調整制御部６３へ送信される。
【００７５】
クラスタ毎の巡回距離を巡回時間算出部７５から受信した稼動率調整制御部６３は、全てのクラスタそれぞれの巡回距離と、初期情報記憶部９１から読み出し取得した制約条件（図３（ｃ））と、を用いて各クラスタ毎の稼動率を算出する。さらに、稼動率調整制御部６３は、これら算出した各クラスタの稼動率を用いて均等化係数を算出する。
その後、稼動率調整制御部６３は、自らが有する履歴リストに所属変更履歴（稼動率調整提供元クラスタ、稼動率調整提供先クラスタ、変更候補配達点ｐたる配達点、巡回距離、各配達車両の稼動率、均等化係数が記憶される。）を書き込み記憶させると共に、巡回路（上述のように、Ｎ−ｏｐｔ部７３から受信した改善された巡回路）を経路記憶部９７へ書き込み、そして稼動率調整部６１の処理を始めから行う（具体的には、稼動率調整制御部６３が、自らの履歴リストに記憶されている内容を削除する。）。
このように（第２本装置の）経路形成手段によって形成された経路を含む経路データを、（第２本装置の）経路データ受付手段が受け付けさらに経路調整する。なお、ここでは（第２本装置の）抽出手段が変更履歴データを抽出することができなくなるまで、（第２本装置の）経路形成手段によって形成された経路を含む経路データを（第２本装置の）経路データ受付手段が受け付けさらに経路調整する。
【００７６】
上述のように、稼動率調整制御部６３が候補のチェックを行い、候補リスト中に候補が残っていると判断しない場合に稼動率調整制御部６３が発した巡回路と履歴リストとを受信した結果出力部６７は、受信した履歴リスト中の所属変更履歴のうち稼動率全てが１以下であって巡回距離が最小のものを抽出し、該抽出された所属変更履歴に対応する巡回路を最終決定巡回路として所定の方法（印刷やディスプレイへの表示等）にて出力する。
なお、結果出力部６７が最終決定巡回路を得る方法は、次の（１）〜（４）のようにして行われる。即ち、まず、（１）結果出力部６７は、稼動率調整制御部６３から受信した履歴リストに含まれる所属変更履歴（稼動率調整提供元クラスタ、稼動率調整提供先クラスタ、変更候補配達点ｐたる配達点、巡回距離、各配達車両の稼動率、均等化係数が含まれる。）のうち、稼動率全てが１以下であって巡回距離が最小のもの（以下、「目的所属変更履歴」という。）を抽出する。次いで、（２）結果出力部６７は、稼動率調整制御部６３から受信した履歴リストと、稼動率調整制御部６３から受信した巡回路と、を用いて、目的所属変更履歴に該当する各クラスタに属する配達点のリストを作成する。具体的には、稼動率調整制御部６３から受信した巡回路は、稼動率調整制御部６３から受信した履歴リストの直近の所属変更がなされた後の状態を示しているので、直近の履歴リストから順に目的所属変更履歴までの所属変更履歴が示す所属変更を逆に行うことで、目的所属変更履歴に該当する各クラスタに属する配達点のリスト（具体的には、各クラスタ毎に属する配達点の番号が列記されたもの）を作成する。そして、（３）上記（２）にて得られた目的所属変更履歴に該当する各クラスタに属する配達点のリストを、結果出力部６７がランダム挿入部７１に送信し、これまでと同様、ランダム挿入部７１に該配達点のリストに従った巡回路を作成させる（該配達点のリストに従って、各クラスタに割り当てられたデポを起点として該クラスタに属する全ての配達点を巡回する巡回路をランダム挿入法によって作成する。）。ランダム挿入部７１は、作成した巡回路を結果出力部６７へ送信する。最後に、（４）ランダム挿入部７１から巡回路を受信した結果出力部６７は、該受信した巡回路をＮ−ｏｐｔ部７３に送信し、これまでと同様、Ｎ−ｏｐｔ部７３にその巡回路にＮ−ｏｐｔ法を（各クラスタ毎に）適用してその巡回路を改善させる。Ｎ−ｏｐｔ部７３は、改善された巡回路を結果出力部６７へ送信する。
【００７７】
次いで、本装置１１の動作について説明する。
図１７は、本装置１１のクラスタ分割部３１の動作を示すフローチャートである。図１７を参照して、本装置１１のクラスタ分割部３１の動作について説明する。
まず、起動信号等によって起動されたファイル読み出し部３３は、初期情報データベース２１にアクセスして配達点の座標（図３（ａ））を読み込み、さらにファイル読み出し部３３は該読み込んだ配達点の座標を初期情報記憶部９１に書き込み記憶させる（ｓ３０１）。次いで、ファイル読み出し部３３は初期情報データベース２１にアクセスしてデポの座標（図３（ｂ））を読み込み、さらにファイル読み出し部３３は該読み込んだデポの座標を初期情報記憶部９１に書き込み記憶させる（ｓ３０２）。そして、ファイル読み出し部３３は初期情報データベース２１にアクセスして制約条件（図３（ｃ））を読み込み、さらにファイル読み出し部３３は該読み込んだ制約条件を初期情報記憶部９１に書き込み記憶させる（ｓ３０３）。
その後、ファイル読み出し部３３は、テーブル初期化部３５に起動信号を発する（ｓ３０４）。
【００７８】
ファイル読み出し部３３からｓ３０４にて発せられた該起動信号を受信したテーブル初期化部３５は、初期情報記憶部９１にアクセスして初期情報記憶部９１が記憶している配達点の座標（図３（ａ））とデポの座標（図３（ｂ））とを読み出し取得し（ｓ３０５）、ｓ３０５にて読み出し取得した配達点の座標（図３（ａ））とデポの座標（図３（ｂ））とを用いて配達点０〜４７とデポ０〜３との合計５２の場所それぞれ（起点）から自ら（起点）を除く５１の場所（終点）までの距離を算出しそれら算出された距離を図５に示すような２次元の距離テーブルとしてまとめる（ｓ３０６）。
さらに、テーブル初期化部３５は、図５に示すようなｓ３０６にて作成した２次元の距離テーブルを所要時間記憶部９９に書き込み記憶させる（ｓ３０７）。
その後、テーブル初期化部３５は、クラスタ数計算部３７に起動信号を発する（ｓ３０８）。
【００７９】
テーブル初期化部３５からｓ３０８において発せられた該起動信号を受信したクラスタ数計算部３７は、ランダム挿入部７１にランダム挿入を命令する起動信号をランダム挿入部７１に送信する（ｓ３０９）。
ｓ３０９にて送信された起動信号を受信したランダム挿入部７１は、初期情報記憶部９１にアクセスして初期情報記憶部９１が記憶している配達点の座標（図３（ａ））を読み出し取得すると共に、所要時間記憶部９９にアクセスして所要時間記憶部９９が記憶している距離テーブル（図５参照）を読み出し取得する。そして、ランダム挿入部７１は、これら読み出し取得した配達点の座標と距離テーブルとを用いてランダム挿入法によって巡回路（即ち、全ての配達点を巡回する順番。具体的には、巡回する順番に従って配達点の番号を並べたもの）を作成し、その巡回路をクラスタ数計算部３７へ送信する（ｓ３１０）。
【００８０】
ｓ３１０にてランダム挿入部７１によって作成された巡回路を受信したクラスタ数計算部３７は、該巡回路をＮ−ｏｐｔ部７３に送信する（ｓ３１１）。
クラスタ数計算部３７からｓ３１１にて送信された該巡回路を受信したＮ−ｏｐｔ部７３は、初期情報記憶部９１にアクセスして初期情報記憶部９１が記憶している配達点の座標（図３（ａ））を読み出し取得し、さらに所要時間記憶部９９にアクセスして所要時間記憶部９９が記憶している距離テーブル（図５参照）を読み出し取得し、これら配達点の座標（図３（ａ））と距離テーブルとを用いて、該受信した巡回路にＮ−ｏｐｔ法（ここでは２−ｏｐｔ法）を適用して該受信した巡回路を改善し、該改善された改善巡回路（配達点を巡回する順番）をクラスタ数計算部３７に送信する（ｓ３１２）。
Ｎ−ｏｐｔ部７３からｓ３１２により送信された改善巡回路を受信したクラスタ数計算部３７は、改善巡回路を巡回時間算出部７５に送信する（ｓ３１３）。
ｓ３１３にて送信された改善巡回路を受信した巡回時間算出部７５は、所要時間記憶部９９が記憶している距離テーブルを読み出し取得し、改善巡回路の全距離を距離テーブルから算出し、この算出された改善巡回路の全距離をクラスタ数計算部３７へ送信する（ｓ３１４）。
【００８１】
ｓ３１４にて送信された改善巡回路の全距離を巡回時間算出部７５から受信したクラスタ数計算部３７は、初期情報記憶部９１にアクセスし初期情報記憶部９１が記憶している制約条件（図３（ｃ））を読み出し取得し、該読み出し取得した制約条件を用いて車両台数を算出する（ｓ３１５）。なお、車両台数の算出は、前述のように、巡回時間算出部７５から受信した改善巡回路の全距離（ｓ３１４にて巡回時間算出部７５から送信されたもの）を、各配達車両の制約条件の相加平均値によって除した商の小数部分を切り上げることによって行われる。
そして、クラスタ数計算部３７は、ｓ３１５にて算出された車両台数を車両数記憶部９３へ送信し車両数記憶部９３に記憶させる（ｓ３１６）。
その後、クラスタ数計算部３７は、仮巡回路形成部４１（後述のファジークラスタリング計算部４３）に起動信号を発する（ｓ３１７。なお、ｓ３１７の後、後述のｓ４０１へ行く。）。
【００８２】
図１８及び図１９は、本装置１１の仮巡回路形成部４１の動作を示すフローチャートである。図１８及び図１９を参照して、本装置１１の仮巡回路形成部４１の動作について説明する。
まず、図１８を参照する。クラスタ数計算部３７からｓ３１７にて発せられた前記起動信号を受信したファジークラスタリング計算部４３は、車両数記憶部９３にアクセスして車両数記憶部９３が記憶している車両台数（ここでは４）を読み出し取得すると共に、初期情報記憶部９１にアクセスして初期情報記憶部９１が記憶している配達点の座標（図３（ａ））を読み出し取得する（ｓ４０１）。そして、ファジークラスタリング計算部４３は、ｓ４０１にて読み出し取得した車両台数（ここでは４）をクラスタ数として、各配達点の各クラスタへの帰属度を計算する（ｓ４０２）。なお、このファジークラスタリングの処理方法は、前述のように公知の技術であり、例えば、特開平０５−２７４２９３号に詳細に記載されている。
そして、ファジークラスタリング計算部４３は、ｓ４０２にて計算した各配達点の各クラスタへの帰属度（図８）をクラスタ属性値記憶部９５に送信しクラスタ属性値記憶部９５に記憶させると共に、ｓ４０２にて計算した各配達点の各クラスタへの帰属度（図８）を初期巡回路作成部４５へ送信する（ｓ４０３）。
【００８３】
ｓ４０３にてファジークラスタリング計算部４３から送信された各配達点の各クラスタへの帰属度（図８）を受信した初期巡回路作成部４５は、配達点それぞれについて最も帰属度が高いクラスタに属すると判断し、全ての配達点がいずれのクラスタに属するかを決定する（ｓ４０４）。そして、初期巡回路作成部４５は、図１０に示すような各クラスタに所属する配達点の番号を各クラスタ毎に記載した配達点番号リストを作成し、その配達点番号リストを経路記憶部９７に送信し経路記憶部９７に記憶させる（ｓ４０５）。
【００８４】
次いで、初期巡回路作成部４５は、初期情報記憶部９１にアクセスして初期情報記憶部９１が記憶している配達点の座標（図３（ａ））を読み出し取得すると共に、自らが作成した前述の配達点番号リストと該読み出し取得した配達点の座標とを用いて各クラスタの重心位置（Ｘ，Ｙ）を求める（ｓ４０６）。
さらに、初期巡回路作成部４５は、初期情報記憶部９１にアクセスして初期情報記憶部９１が記憶しているデポの座標（図３（ｂ））を読み出し取得すると共に、先に求めた各クラスタの重心に最も近いデポを選択することで各クラスタにデポを割り当てる（ｓ４０７）。その後、初期巡回路作成部４５は、経路記憶部９７にアクセスし経路記憶部９７が記憶している配達点番号リストの各クラスタに割り当てたデポを図１１に示すように書き込む（ｓ４０８）。
その後、初期巡回路作成部４５は、既に自らが有している配達点番号リスト（割り当てデポが記載された図１１に示すもの）をランダム挿入部７１に送信する（ｓ４０９）。
【００８５】
初期巡回路作成部４５からｓ４０９にて送信された配達点番号リストを受信したランダム挿入部７１は、初期情報記憶部９１にアクセスして初期情報記憶部９１が記憶している配達点の座標（図３（ａ））とデポの座標（図３（ｂ））とを読み出し取得すると共に、所要時間記憶部９９にアクセスして所要時間記憶部９９が記憶している距離テーブル（図５参照）を読み出し取得する。そして、ランダム挿入部７１は、これら読み出し取得した配達点の座標、デポの座標及び距離テーブルとを用いて、該受信した配達点番号リストの各クラスタ毎に該クラスタに割り当てられたデポを起点として該クラスタに属する全ての配達点を巡回する巡回路（クラスタ別初期巡回路）を前述のランダム挿入法によって作成し、クラスタ別初期巡回路を初期巡回路作成部４５に送信する（ｓ４１０）。
ｓ４１０にてランダム挿入部７１から送信されたクラスタ別初期巡回路を受信した初期巡回路作成部４５は、クラスタ別初期巡回路をＮ−ｏｐｔ部７３に送信する（ｓ４１１）。
ｓ４１１にて初期巡回路作成部４５から送信されたクラスタ別初期巡回路を受信したＮ−ｏｐｔ部７３は、初期情報記憶部９１にアクセスして初期情報記憶部９１が記憶している配達点の座標（図３（ａ））とデポの座標（図３（ｂ））とを読み出し取得し、さらに所要時間記憶部９９にアクセスして所要時間記憶部９９が記憶している距離テーブル（図５参照）を読み出し取得し、これら配達点の座標（図３（ａ））、デポの座標（図３（ｂ））及び距離テーブルを用いて、クラスタ別初期巡回路に前述のＮ−ｏｐｔ法を（各クラスタ毎に）適用してクラスタ別初期巡回路を改善し、改善されたクラスタ別初期巡回路（改善クラスタ別初期巡回路）を初期巡回路作成部４５へ送信する（ｓ４１２）。
ｓ４１２により送信された改善クラスタ別初期巡回路を受信した初期巡回路作成部４５は、経路記憶部９７にアクセスし経路記憶部９７が記憶している配達点番号リストの所属配達点の配達点番号の記載順序を改善クラスタ別初期巡回路に従った順序に書き換える（ｓ４１３）（以上、図１８）。
【００８６】
次いで、図１９に移る。ｓ４１３の後、初期巡回路作成部４５は改善クラスタ別初期巡回路を巡回時間算出部７５へ送信する（ｓ４１４）。ｓ４１４にて送信された改善クラスタ別初期巡回路を受信した巡回時間算出部７５は、所要時間記憶部９９が記憶している距離テーブルを読み出し取得し、改善クラスタ別初期巡回路に示される各クラスタ毎の巡回距離を距離テーブルから算出すると共に、この算出した各クラスタ毎の巡回距離を初期巡回路作成部４５へ送信する（ｓ４１５）。
ｓ４１５にて送信された、改善クラスタ別初期巡回路に応じた各クラスタ毎の巡回距離を受信した初期巡回路作成部４５は、初期情報記憶部９１にアクセスし初期情報記憶部９１が記憶している制約条件（図３（ｃ））のうち改善クラスタ別初期巡回路に使用されているデポに対応する車両の制約条件を読み出し取得し、該読み出し取得した制約条件（配達車両それぞれの一日に移動可能な最大の移動距離）の合計値を算出する（ｓ４１６）。そして、初期巡回路作成部４５は、該受信した各クラスタ毎の巡回距離の合計を算出する（ｓ４１７）。その後、初期巡回路作成部４５は、制約条件の合計値が巡回距離の合計値以上か否か判断し（ｓ４１８）、そうであれば（ＹＥＳ）この改善クラスタ別初期巡回路は妥当と判断し、所属調整部５１へ起動信号を発する（ｓ４１９。なお、ｓ４１９の後、後述のｓ５０１へ行く。）。ｓ４１８にて制約条件の合計値が巡回距離の合計値以上でなければ（ＮＯ）、初期巡回路作成部４５は、この改善クラスタ別初期巡回路は妥当と判断せず、ファジークラスタリング計算部４３に車両台数に１を加える信号（車両増加信号）を発する（ｓ４２０）。ｓ４２０の後、初期巡回路作成部４５は、クラスタ数計算部３７からファジークラスタリング計算部４３に発せられる前記起動信号と同じ信号を送信する（ｓ４２１）。ｓ４２１の後、再びｓ４０２に戻る（即ち、前回のｓ４０２以降の処理に用いた車両台数よりも１増加した車両台数によってｓ４０２以降の処理が行われる。）。
【００８７】
図２０〜図２２は、本装置１１の所属調整部５１の動作を示すフローチャートである。図２０〜図２２を参照して、本装置１１の所属調整部５１の動作について説明する。
まず、図２０を参照する。初期巡回路作成部４５からｓ４１９にて発せられた前記起動信号を受信した経路制御部５２は、初期情報記憶部９１にアクセスし初期情報記憶部９１が記憶している制約条件（図３（ｃ））を読み出し取得し（後述の稼動率の算出に用いる。）、所要時間記憶部９９にアクセスし所要時間記憶部９９が記憶している距離テーブルを読み出し取得し、さらに経路記憶部９７にアクセスし経路記憶部９７が記憶している改善クラスタ別初期巡回路を読み出し取得する（ｓ５０１）。
次いで、経路制御部５２は、これら読み出し取得した距離テーブル及び改善クラスタ別初期巡回路を用いて改善クラスタ別初期巡回路における各クラスタ毎の巡回距離を算出する（ｓ５０２）。
そして、経路制御部５２は、各配達車両毎の稼動率を算出する（ｓ５０３）。稼動率は、上記のように、各クラスタ毎の巡回距離を、該クラスタを担当する配達車両の制約条件（図３（ｃ）、ここでは全て１００００）によって除した商として算出される。
さらに、経路制御部５２は、各配達車両毎の稼動率の平均値（算術）を求め、それを用いて均等化係数を算出する（ｓ５０４）。均等化係数は、前述のように、それぞれの配達車両について、（該配達車両の稼動率−稼動率の平均値）の絶対値（即ち、｜（各配達車両の稼動率）−（稼動率の平均値）｜）を求め、全ての配達車両について求めた該絶対値を合計して合計値を求め、配達車両の数によって該合計値を除すことによって算出される（即ち、均等化係数＝Σ（｜（各配達車両の稼動率）−（稼動率の平均値）｜）／（配達車両の数）として算出される。）。
最後に、経路制御部５２は、上記のようにして算出した各配達車両毎の稼動率及び均等化係数を、所属変更処理部５３へ送信する（ｓ５０５）。
【００８８】
経路制御部５２からｓ５０５にて送信された各配達車両毎の稼動率及び均等化係数を受信した所属変更処理部５３は、該受信した均等化係数が、自ら（所属変更処理部５３）が記憶している均等化係数よりも小さいか、又は自ら（所属変更処理部５３）が均等化係数を記憶していないかを判断し（ｓ５０６）、そのいずれかであると判断した場合（ＹＥＳ）には、該受信した均等化係数を上書きして記憶した（ｓ５０７）後（即ち、所属変更処理部５３は、それまでに経路制御部５２から受信した均等化係数のうち最小のものを記憶することになる。）、経路制御部５２から受信した各配達車両毎の稼動率を都市所属変更処理部５５へ送信する（ｓ５５０）。一方、所属変更処理部５３が、ｓ５０６にて該受信した均等化係数が、自らが記憶している均等化係数よりも小さいか、又は自らが均等化係数を記憶していないかのいずれでもないと判断した場合（ＮＯ）（即ち、所属変更処理部５３が均等化係数を記憶しており、かつ該受信した均等化係数が、該記憶している均等化係数以上である場合）には履歴チェック部５４に起動信号を発する（ｓ５５１）。
【００８９】
ｓ５５０にて所属変更処理部５３から送信された各配達車両毎の稼動率を受信した都市所属変更処理部５５は、初期情報記憶部９１にアクセスし初期情報記憶部９１が記憶している配達点の座標（図３（ａ））とデポの座標（図３（ｂ））とを読み出し取得し、クラスタ属性値記憶部９５にアクセスしクラスタ属性値記憶部９５が記憶している各配達点の各クラスタへの帰属度（図８）を読み出し取得し、そして経路記憶部９７にアクセスし経路記憶部９７が記憶している改善クラスタ別初期巡回路を読み出し取得する（ｓ５０８）。
次いで、都市所属変更処理部５５は、所属変更処理部５３から受信した各配達車両毎の稼動率のうち最も高い稼動率を与える配達車両が担当するクラスタを、提供元のクラスタとして記憶すると共に、クラスタのリスト（都市所属変更処理部５５自身が有する記憶領域）にも記憶する（ｓ５０９）。さらに、都市所属変更処理部５５は、所属変更処理部５３から受信した各配達車両毎の稼動率のうち最も低い稼動率を与える配達車両が担当するクラスタを、提供先のクラスタとして記憶する（ｓ５１０）。
【００９０】
その後、都市所属変更処理部５５は、クラスタのリストに記憶されたクラスタに属する配達点（上述のように読み出し取得した改善クラスタ別初期巡回路（図１１）から得られる。）のうち、提供先のクラスタへの帰属度が最も高い配達点（選択点）を選択する（ｓ５１１）（各配達点の帰属度は、上述のように読み出し取得した各配達点の各クラスタへの帰属度（図８）を用いることで得られる。）。なお、クラスタのリストに複数のクラスタが記憶されている場合では、複数のクラスタに属する全ての配達点から選択点を選択する（例えば、クラスタ５０、クラスタ６３、クラスタ７８の３つのクラスタがクラスタのリストに記憶されている場合では、クラスタ５０に属する配達点と、クラスタ６３に属する配達点と、クラスタ７８に属する配達点と、の全ての配達点から１の選択点を選択する。）。
そして、都市所属変更処理部５５は、選択点が所属しているクラスタを所属元クラスタとして記憶する（ｓ５１２）。
次に、都市所属変更処理部５５は、クラスタのリストに記憶されたクラスタ以外のクラスタ（クラスタのリストに複数のクラスタが記憶されている場合には、その複数のクラスタのいずれでもないクラスタ）へ選択点が示す帰属度のうち最も高い帰属度を示すクラスタを所属変更先クラスタとして選択し記憶する（ｓ５１３）。
【００９１】
次いで、図２１を参照する。ｓ５１３の後、都市所属変更処理部５５は、自らが有する改善クラスタ別初期巡回路（ｓ５０８にて経路記憶部９７から読み出したもの）の中の所属元クラスタに属している選択点を削除すると共に、改善クラスタ別初期巡回路の中の所属変更先クラスタに選択点を加える（ｓ５１４）。
ｓ５１４の後、都市所属変更処理部５５は、ｓ５１４にて選択点が削除及び追加された改善クラスタ別初期巡回路（選択点加除巡回路）をランダム挿入部７１に送信する（ｓ５１５）。
【００９２】
選択点加除巡回路を受信したランダム挿入部７１は、初期情報記憶部９１にアクセスして初期情報記憶部９１が記憶している配達点の座標（図３（ａ））とデポの座標（図３（ｂ））とを読み出し取得し、所要時間記憶部９９にアクセスし所要時間記憶部９９が記憶している距離テーブルを読み出し取得し、選択点加除巡回路に従って各クラスタ毎に該クラスタに割り当てられたデポを起点として該クラスタに属する全ての配達点を巡回する巡回路（ランダム挿入選択点加除巡回路）を前述のランダム挿入法によって作成し、ランダム挿入選択点加除巡回路を都市所属変更処理部５５に送信する（ｓ５１６）。
ランダム挿入選択点加除巡回路をランダム挿入部７１から受信した都市所属変更処理部５５は、経路記憶部９７にランダム挿入選択点加除巡回路を上書きし記憶させると共に、ランダム挿入選択点加除巡回路を巡回時間算出部７５に送信する（ｓ５１７）。
【００９３】
ｓ５１７にて都市所属変更処理部５５から送信されたランダム挿入選択点加除巡回路を受信した巡回時間算出部７５は、所要時間記憶部９９が記憶している距離テーブルを読み出し取得し、ランダム挿入選択点加除巡回路の各クラスタ毎の距離を距離テーブルから算出し、その算出した各クラスタ毎の距離を都市所属変更処理部５５へ送信する（ｓ５１８）。
そして、都市所属変更処理部５５が履歴記憶部９８に選択点の加除処理に関する履歴を書き込み記憶させる（ｓ５１９）（履歴は上書きではなく追加的に書き込み記憶される。）。なお、選択点の加除処理に関する履歴は、前述のように、提供元のクラスタ、提供先のクラスタ、所属元クラスタ、所属変更先クラスタ、選択点たる配達点、各配達車両の稼動率の各項目を含んでいる。
【００９４】
その後、都市所属変更処理部５５は、所属変更先クラスタと提供先のクラスタとが一致するか否かを判断し（ｓ５２０）、一致すると判断しない場合（ＮＯ）、このときの所属変更先クラスタを前述のクラスタのリストに記憶し（ｓ５２１）（即ち、このときの所属変更先クラスタがクラスタのリストに追加され、次の処理の所属元クラスタとして選択される候補になる。）、その後、再びｓ５１１へ戻る。
一方、都市所属変更処理部５５が、ｓ５２０において所属変更先クラスタと提供先のクラスタとが一致すると判断する場合（ＹＥＳ）、ランダム挿入選択点加除巡回路のうちクラスタのリストに含まれている（１又は２以上の）クラスタと提供先のクラスタとの複数のクラスタの巡回路を経路記憶部９７（ランダム挿入選択点加除巡回路を記憶している。）からそれぞれ読み出し取得し、該それぞれ取得された巡回路をＮ−ｏｐｔ部７３に送信する（ｓ５２２）。
都市所属変更処理部５５から複数のクラスタに関する巡回路（ランダム挿入選択点加除巡回路の一部）を受信したＮ−ｏｐｔ部７３は、初期情報記憶部９１にアクセスして初期情報記憶部９１が記憶している配達点の座標（図３（ａ））とデポの座標（図３（ｂ））とを読み出し取得し、さらに所要時間記憶部９９にアクセスして所要時間記憶部９９が記憶している距離テーブル（図５参照）を読み出し取得し、これら配達点の座標（図３（ａ））、デポの座標（図３（ｂ））及び距離テーブルを用いて、それぞれの巡回路に前述のＮ−ｏｐｔ法を（各クラスタ毎に）適用して改善し、改善された巡回路（改善一部ランダム挿入選択点加除巡回路）を都市所属変更処理部５５へ送信する（ｓ５２３）。
そして、改善一部ランダム挿入選択点加除巡回路を受信した都市所属変更処理部５５は、経路記憶部９７にアクセスし経路記憶部９７が記憶しているランダム挿入選択点加除巡回路のうち改善一部ランダム挿入選択点加除巡回路に該当する部分を書き換える（ｓ５２４）。
その後、都市所属変更処理部５５は、経路制御部５２に起動信号（初期巡回路作成部４５から経路制御部５２へ発せられる起動信号と同じ。）を発し（ｓ５２５）、再びｓ５０１へ戻る。
【００９５】
続いて、図２２を参照する。ｓ５５１にて所属変更処理部５３が発した起動信号を受信した履歴チェック部５４は、履歴記憶部９８にアクセスして履歴記憶部９８が記憶している前記選択点の加除処理に関する履歴を読み込み取得する（ｓ５２６）。そして、履歴チェック部５４は、該読み込み取得した前記選択点の加除処理に関する履歴のうち直近の履歴（例えば、図１４中では、作業番号１９にて示された「提供元」（提供元のクラスタ：クラスタ３）、「提供先」（提供先のクラスタ：クラスタ２）、「所属元」（所属元クラスタ：クラスタ３）、「所属変更先」（所属変更先クラスタ：クラスタ２）、「配達点番号」（選択点たる配達点：配達点４６）によるもの。以下、「直近履歴」という。）と、直近履歴以外の履歴（例えば、図１４に示したものであれば、作業番号１〜１８に示されるそれぞれのもの。以下、「その他履歴」という。）と、を比較し、直近履歴と同一のものがその他履歴に存するか否かを判断する（ｓ５２７）。ｓ５２７にて履歴チェック部５４が、直近履歴と同一のものがその他履歴に存すると判断した場合、履歴チェック部５４は所属変更結果設定部５６に起動信号を送信する（ｓ５２８）。ｓ５２７にて履歴チェック部５４が、直近履歴と同一のものがその他履歴に存すると判断しない場合（ＮＯ）、履歴チェック部５４は、所属変更処理部５３に各配達車両毎の稼動率（所属変更処理部５３が経路制御部５２から受信したもの）を都市所属変更処理部５５へ送信することを命令する信号を発し（ｓ５２９）、この信号を受信した所属変更処理部５３は各配達車両毎の稼動率を都市所属変更処理部５５へ送信し（ｓ５３０）、前述のｓ５５０へ戻る。
【００９６】
ｓ５２８にて履歴チェック部５４が発した起動信号を受信した所属変更結果設定部５６は、履歴記憶部９８にアクセスして履歴記憶部９８が記憶している前記選択点の加除処理に関する履歴を読み込み取得し、その各履歴に含まれる各配達車両の稼動率を用いて各履歴の均等化係数を計算する（ｓ５３１）。次いで、所属変更結果設定部５６は、それら各履歴毎に計算した均等化係数のうち最も小さい値を与える巡回路を選択し、該選択した巡回路を経路記憶部９７に送信し経路記憶部９７に記憶させる（ｓ５３２）。
その後、所属変更結果設定部５６は、稼動率調整部６１（稼動率調整制御部６３）に起動信号を発し（ｓ５３３）、後述のｓ６０１へ行く。
【００９７】
ここで、前述の図１４について詳しく説明しておく。図１４は、履歴記憶部９８にｓ５１９にて書き込まれて記憶された履歴の一例を示したものであり、具体的には、図３に示したデータを基に本装置を動作させたときに履歴記憶部９８に書き込まれたものを示している。図１４中では、クラスタ番号の欄の「提供元」の位置には「提供元のクラスタ」が示され（例えば、「２」と記載されているのは提供元のクラスタがクラスタ２であることを示している。）、クラスタ番号の欄の「提供先」の位置には「提供先のクラスタ」が示され（例えば、「３」と記載されているのは提供先のクラスタがクラスタ３であることを示している。）、クラスタ番号の欄の「所属元」の位置には「所属元クラスタ」が示され（例えば、「０」と記載されているのは所属元クラスタがクラスタ０であることを示している。）、クラスタ番号の欄の「所属変更先」の位置には「所属変更先クラスタ」が示され（例えば、「１」と記載されているのは所属変更先クラスタがクラスタ１であることを示している。）、「配達点番号」の欄には「選択点たる配達点」が示され（例えば、「４６」と示されているのは、選択点たる配達点が配達点４６であることを示している。）、「稼動率」の欄にはクラスタ０〜３それぞれの稼動率が示されている（例えば、クラスタ１の欄に「０．９６８８」と示されているのは、クラスタ１の稼動率が０．９６８８であることを示している。）。また、図１４中では、説明や理解を容易にするため、作業番号（作業の古いものから順に連番を付している。）及び図番号を付している。そして、稼動率については、上に示された稼動率と同じ稼動率の部分は、図示を容易にするため記載を省略している（例えば、作業番号１及び２の稼動率は、いずれもクラスタ０については１．０５６、クラスタ１については０．９６８８、クラスタ２については１．１６９４、クラスタ３については０．４４０６、と同じである。）。
【００９８】
続いて、図１４に示されたそれぞれの履歴について、図２６〜図４５を参照しつつ説明する。
まず、図２６は、ｓ５０１にて経路制御部５２が、経路記憶部９７にアクセスし経路記憶部９７から読み出し取得した改善クラスタ別初期巡回路を図示したものである。なお、同一のクラスタに属する配達点を線によって結び、クラスタに属する配達点を明確にしている。そして、各クラスタのデポを■（内部が黒く塗りつぶされた略正方形の点）によって示している。
そして、経路制御部５２は、ｓ５０２にて図２６に示された改善クラスタ別初期巡回路における各クラスタ毎の巡回距離を算出し、次いでｓ５０３にて各配達車両毎の稼動率を算出する。具体的には、ここではクラスタ０の稼動率は１．０５６０、クラスタ１の稼動率は０．９６８８、クラスタ２の稼動率は１．１６９４、クラスタ３の稼動率は０．４４０６とそれぞれ計算されている（図１４の「稼動率」の最上欄参照）。
さらに、経路制御部５２は、ｓ５０４にて均等化係数を算出し、ｓ５０４にて算出した各配達車両毎の稼動率及び均等化係数をｓ５０５で所属変更処理部５３へ送信する。なお、ここでは均等化係数（Σ（｜（各配達車両の稼動率）−（稼動率の平均値）｜）／（配達車両の数））は、（｜１．０５６０−０．９０８７｜）／４＋｜０．９６８８−０．９０８７｜／４＋｜１．１６９４−０．９０８７｜／４＋｜０．４４０６−０．９０８７｜／４）＝０．２３４０５のように算出される。
【００９９】
ｓ５０５にて送信された各配達車両毎の稼動率及び均等化係数を受信した所属変更処理部５３は、該受信した均等化係数（ここでは０．２３４０５）が、自らが記憶している均等化係数よりも小さいか、又は自らが均等化係数を記憶していないかを判断するが（ｓ５０６）、ここでは自らが均等化係数を記憶していないのでそのいずれかであると判断し（ＹＥＳ）、該受信した均等化係数（ここでは０．２３４０５）を上書きして記憶した（ｓ５０７）後、経路制御部５２から受信した各配達車両毎の稼動率（ここではクラスタ０：１．０５６０、クラスタ１：０．９６８８、クラスタ２：１．１６９４、クラスタ３：０．４４０６）を都市所属変更処理部５５へ送信する（ｓ５５０）。
ｓ５５０にて所属変更処理部５３から送信された各配達車両毎の稼動率を受信した都市所属変更処理部５５は、ｓ５０８にて必要なデータを読み出し取得すると共に、経路記憶部９７にアクセスし経路記憶部９７が記憶している改善クラスタ別初期巡回路（図２６）を読み出し取得する。そしてｓ５０９にて都市所属変更処理部５５は、所属変更処理部５３から受信した各配達車両毎の稼動率（クラスタ０：１．０５６０、クラスタ１：０．９６８８、クラスタ２：１．１６９４、クラスタ３：０．４４０６）のうち最も高い稼動率（１．１６９４）を与える配達車両が担当するクラスタ（クラスタ２）を、提供元のクラスタとして記憶すると共に、クラスタのリストにも記憶する。さらに、都市所属変更処理部５５は、所属変更処理部５３から受信した各配達車両毎の稼動率のうち最も低い稼動率（０．４４０６）を与える配達車両が担当するクラスタ（クラスタ３）を、提供先のクラスタとして記憶する（ｓ５１０）。これらは図１４に示すように履歴記憶部９８にｓ５１９にて書き込まれるので、図１４中の作業番号１の欄に「提供元」として２が、また「提供先」として３が記憶されている。
【０１００】
その後、都市所属変更処理部５５は、クラスタのリストに記憶されたクラスタ（クラスタ２）に属する配達点のうち、提供先のクラスタ（クラスタ３）への帰属度が最も高い配達点（選択点）として配達点４６（提供先のクラスタ（クラスタ３）への帰属度：０．１６）を選択する（ｓ５１１）。
そして、都市所属変更処理部５５は、選択点たる配達点４６が所属しているクラスタ２を所属元クラスタとして記憶する（ｓ５１２）。
次に、都市所属変更処理部５５は、クラスタのリストに記憶されたクラスタ２以外のクラスタ（即ち、クラスタ０、クラスタ１、クラスタ３）へ選択点たる配達点４６が示す帰属度（クラスタ０：０．３、クラスタ１：０．０５、クラスタ３：０．１６）のうち最も高い帰属度（０．３）を示すクラスタ０を所属変更先クラスタとして選択し記憶する（ｓ５１３）。
これら選択点、所属元クラスタ、所属変更先クラスタは、履歴記憶部９８にｓ５１９にて書き込まれるので、図１４中の作業番号１の欄の「所属元」として２が、また「所属変更先」として０が、そして「配達点番号」として４６が記憶されている。
【０１０１】
その後、都市所属変更処理部５５は、自らが有する改善クラスタ別初期巡回路の中の所属元クラスタたるクラスタ２に属している選択点たる配達点４６を削除すると共に、改善クラスタ別初期巡回路の中の所属変更先クラスタたるクラスタ０に選択点たる配達点４６を加える（ｓ５１４）。
ｓ５１４の後、都市所属変更処理部５５は、ｓ５１４にて選択点たる配達点４６が削除及び追加された改善クラスタ別初期巡回路（選択点加除巡回路）をランダム挿入部７１に送信する（ｓ５１５）。
【０１０２】
選択点加除巡回路を受信したランダム挿入部７１は、選択点加除巡回路に従って各クラスタ毎に該クラスタに割り当てられたデポを起点として該クラスタに属する全ての配達点を巡回する巡回路（ランダム挿入選択点加除巡回路）を前述のランダム挿入法によって作成し、ランダム挿入選択点加除巡回路を都市所属変更処理部５５に送信する。ランダム挿入選択点加除巡回路をランダム挿入部７１から受信した都市所属変更処理部５５は、経路記憶部９７にランダム挿入選択点加除巡回路を上書きし記憶させると共に、ランダム挿入選択点加除巡回路を巡回時間算出部７５に送信する（ｓ５１７）。
図２７に、このとき経路記憶部９７に記憶されたランダム挿入選択点加除巡回路を図示した結果を示す。前述の図２６と図２７とを比較すると、選択点たる配達点４６がクラスタ２からクラスタ０に所属が変更されている。
【０１０３】
ｓ５１７にて都市所属変更処理部５５から送信されたランダム挿入選択点加除巡回路を受信した巡回時間算出部７５は、ランダム挿入選択点加除巡回路の各クラスタ毎の距離を算出し、その算出した各クラスタ毎の距離を都市所属変更処理部５５へ送信する（ｓ５１８）。
そして、都市所属変更処理部５５が履歴記憶部９８に選択点の加除処理に関する履歴を書き込み記憶させる（ｓ５１９）（履歴は上書きではなく追加的に書き込み記憶される。）。なお、選択点の加除処理に関する履歴は、前述のように、提供元のクラスタ（クラスタ２）、提供先のクラスタ（クラスタ３）、所属元クラスタ（クラスタ２）、所属変更先クラスタ（クラスタ０）、選択点たる配達点（配達点４６）、各配達車両の稼動率の各項目を含んでいる。
【０１０４】
その後、都市所属変更処理部５５は、所属変更先クラスタ（クラスタ０）と提供先のクラスタ（クラスタ３）とが一致するか否かを判断し（ｓ５２０）、ここでは一致しないので一致すると判断せず（ＮＯ）、このときの所属変更先クラスタ（クラスタ０）を前述のクラスタのリストに記憶し（ｓ５２１）（即ち、このときの所属変更先クラスタ（クラスタ０）がクラスタのリストに追加され、次の処理の所属元クラスタとして選択される候補になる。）、その後、再びｓ５１１へ戻る。
【０１０５】
ｓ５１１に戻ると、都市所属変更処理部５５は、クラスタのリストに記憶されたクラスタ（クラスタ０とクラスタ２。ｓ５２１にて所属変更先クラスタをクラスタのリストに記憶した。）に属する配達点のうち、提供先のクラスタ（クラスタ３）への帰属度が最も高い配達点（選択点）として配達点３０（提供先のクラスタ（クラスタ３）への帰属度：０．４４）を選択する。
そして、都市所属変更処理部５５は、選択点たる配達点３０が所属しているクラスタ０を所属元クラスタとして記憶する（ｓ５１２）。
次に、都市所属変更処理部５５は、クラスタのリストに記憶されたクラスタ（クラスタ０とクラスタ２）以外のクラスタ（即ち、クラスタ１とクラスタ３）へ選択点たる配達点３０が示す帰属度（クラスタ１：０．０２、クラスタ３：０．４４）のうち最も高い帰属度（０．４４）を示すクラスタ３を所属変更先クラスタとして選択し記憶する（ｓ５１３）。
これら選択点、所属元クラスタ、所属変更先クラスタは、履歴記憶部９８にｓ５１９にて書き込まれるので、図１４中の作業番号２の欄の「所属元」として０が、また「所属変更先」として３が、そして「配達点番号」として３０が記憶されている。
【０１０６】
その後、都市所属変更処理部５５は、自らが有する改善クラスタ別初期巡回路の中の所属元クラスタたるクラスタ０に属している選択点たる配達点３０を削除すると共に、改善クラスタ別初期巡回路の中の所属変更先クラスタたるクラスタ３に選択点たる配達点３０を加える（ｓ５１４）。
ｓ５１４の後、都市所属変更処理部５５は、ｓ５１４にて選択点たる配達点３０が削除及び追加された改善クラスタ別初期巡回路（選択点加除巡回路）をランダム挿入部７１に送信する（ｓ５１５）。
【０１０７】
選択点加除巡回路を受信したランダム挿入部７１は、選択点加除巡回路に従って各クラスタ毎に該クラスタに割り当てられたデポを起点として該クラスタに属する全ての配達点を巡回する巡回路（ランダム挿入選択点加除巡回路）を前述のランダム挿入法によって作成し、ランダム挿入選択点加除巡回路を都市所属変更処理部５５に送信する。ランダム挿入選択点加除巡回路をランダム挿入部７１から受信した都市所属変更処理部５５は、経路記憶部９７にランダム挿入選択点加除巡回路を上書きし記憶させると共に、ランダム挿入選択点加除巡回路を巡回時間算出部７５に送信する（ｓ５１７）。
図２８に、このとき経路記憶部９７に記憶されたランダム挿入選択点加除巡回路を図示した結果を示す。前述の図２７と図２８とを比較すると、選択点たる配達点３０がクラスタ０からクラスタ３に所属が変更されている。
【０１０８】
ｓ５１７にて都市所属変更処理部５５から送信されたランダム挿入選択点加除巡回路を受信した巡回時間算出部７５は、ランダム挿入選択点加除巡回路の各クラスタ毎の距離を算出し、その算出した各クラスタ毎の距離を都市所属変更処理部５５へ送信する（ｓ５１８）。
そして、都市所属変更処理部５５が履歴記憶部９８に選択点の加除処理に関する履歴を書き込み記憶させる（ｓ５１９）（履歴は上書きではなく追加的に書き込み記憶される。）。なお、選択点の加除処理に関する履歴は、前述のように、提供元のクラスタ（クラスタ２）、提供先のクラスタ（クラスタ３）、所属元クラスタ（クラスタ０）、所属変更先クラスタ（クラスタ３）、選択点たる配達点（配達点３０）、各配達車両の稼動率の各項目を含んでいる。
【０１０９】
その後、都市所属変更処理部５５は、所属変更先クラスタ（クラスタ３）と提供先のクラスタ（クラスタ３）とが一致するか否かを判断し（ｓ５２０）、ここでは一致するので一致すると判断し（ＹＥＳ）、ランダム挿入選択点加除巡回路のうちクラスタのリストに含まれている（１又は２以上の）クラスタ（ここではクラスタ０とクラスタ２）と提供先のクラスタ（クラスタ３）との複数のクラスタの巡回路を経路記憶部９７（ランダム挿入選択点加除巡回路を記憶している。）からそれぞれ読み出し取得し、該それぞれ取得された巡回路をＮ−ｏｐｔ部７３に送信する（ｓ５２２）。
都市所属変更処理部５５から複数のクラスタに関する巡回路（ランダム挿入選択点加除巡回路の一部）を受信したＮ−ｏｐｔ部７３は、初期情報記憶部９１にアクセスして初期情報記憶部９１が記憶している配達点の座標（図３（ａ））とデポの座標（図３（ｂ））とを読み出し取得し、さらに所要時間記憶部９９にアクセスして所要時間記憶部９９が記憶している距離テーブル（図５参照）を読み出し取得し、これら配達点の座標（図３（ａ））、デポの座標（図３（ｂ））及び距離テーブルを用いて、それぞれの巡回路に前述のＮ−ｏｐｔ法を（各クラスタ毎に）適用して改善し、改善された巡回路（改善一部ランダム挿入選択点加除巡回路）を都市所属変更処理部５５へ送信する（ｓ５２３）。
そして、改善一部ランダム挿入選択点加除巡回路を受信した都市所属変更処理部５５は、経路記憶部９７にアクセスし経路記憶部９７が記憶しているランダム挿入選択点加除巡回路のうち改善一部ランダム挿入選択点加除巡回路に該当する部分を書き換える（ｓ５２４）。
その後、都市所属変更処理部５５は、経路制御部５２に起動信号（初期巡回路作成部４５から経路制御部５２へ発せられる起動信号と同じ。）を発し（ｓ５２５）、再びｓ５０１へ戻る。
【０１１０】
再びｓ５０１に戻ると、経路制御部５２は、初期情報記憶部９１が記憶している制約条件（図３（ｃ））、所要時間記憶部９９が記憶している距離テーブル、そして経路記憶部９７が記憶している改善クラスタ別初期巡回路（図２８）を読み出し取得する（ｓ５０１）。
そして、経路制御部５２は、ｓ５０２にて図２８に示された改善クラスタ別初期巡回路における各クラスタ毎の巡回距離を算出し、次いでｓ５０３にて各配達車両毎の稼動率を算出する。具体的には、ここではクラスタ０の稼動率は１．０６０９、クラスタ１の稼動率は０．９６８８、クラスタ２の稼動率は１．０７１５、クラスタ３の稼動率は０．５２６９とそれぞれ計算されている（図１４の「稼動率」の上から第２段目参照）。
さらに、経路制御部５２は、ｓ５０４にて均等化係数を算出し、ｓ５０４にて算出した各配達車両毎の稼動率及び均等化係数をｓ５０５で所属変更処理部５３へ送信する。なお、ここでは均等化係数（Σ（｜（各配達車両の稼動率）−（稼動率の平均値）｜）／（配達車両の数））は、（｜１．０６０９−０．９０７０２５｜）／４＋｜０．９６８８−０．９０７０２５｜／４＋｜１．０７１５−０．９０７０２５｜／４＋｜０．５２６９−０．９０７０２５｜／４）＝０．１９００６２５のように算出される。
【０１１１】
ｓ５０５にて送信された各配達車両毎の稼動率及び均等化係数を受信した所属変更処理部５３は、該受信した均等化係数（ここでは０．１９００６２５）が、自らが記憶している均等化係数よりも小さいか、又は自らが均等化係数を記憶していないかを判断するが（ｓ５０６）、ここでは自らが均等化係数（前回の値０．２３４０５）を記憶しているので（ここでは０．１９００６２５）が（前回の値０．２３４０５）よりも小さいと判断し（ＹＥＳ）、該受信した均等化係数（ここでは０．１９００６２５）を上書きして記憶した（ｓ５０７）後、経路制御部５２から受信した各配達車両毎の稼動率（ここではクラスタ０：１．０６０９、クラスタ１：０．９６８８、クラスタ２：１．０７１５、クラスタ３：０．５２６９）を都市所属変更処理部５５へ送信する（ｓ５５０）。
ｓ５５０にて所属変更処理部５３から送信された各配達車両毎の稼動率を受信した都市所属変更処理部５５は、ｓ５０８にて必要なデータを読み出し取得すると共に、経路記憶部９７にアクセスし経路記憶部９７が記憶している改善クラスタ別初期巡回路（図２８）を読み出し取得する。そしてｓ５０９にて都市所属変更処理部５５は、所属変更処理部５３から受信した各配達車両毎の稼動率（クラスタ０：１．０６０９、クラスタ１：０．９６８８、クラスタ２：１．０７１５、クラスタ３：０．５２６９）のうち最も高い稼動率（１．０７１５）を与える配達車両が担当するクラスタ（クラスタ２）を、提供元のクラスタとして記憶すると共に、クラスタのリストにも記憶する。さらに、都市所属変更処理部５５は、所属変更処理部５３から受信した各配達車両毎の稼動率のうち最も低い稼動率（０．５２６９）を与える配達車両が担当するクラスタ（クラスタ３）を、提供先のクラスタとして記憶する（ｓ５１０）。これらは図１４に示すように履歴記憶部９８にｓ５１９にて書き込まれるので、図１４中の作業番号３の欄に「提供先」として２が、また「提供元」として３が記憶されている。
【０１１２】
その後、都市所属変更処理部５５は、クラスタのリストに記憶されたクラスタ（クラスタ２）に属する配達点のうち、提供先のクラスタ（クラスタ３）への帰属度が最も高い配達点（選択点）として配達点２０（提供先のクラスタ（クラスタ３）への帰属度：０．０９。なお、図１４の作業番号１にて配達点４６はクラスタ２から削除されている。なお、ここでは配達点４０も帰属度０．０９であるが、先に見つけたものを優先して選択する。）を選択する（ｓ５１１）。
そして、都市所属変更処理部５５は、選択点たる配達点２０が所属しているクラスタ２を所属元クラスタとして記憶する（ｓ５１２）。
次に、都市所属変更処理部５５は、クラスタのリストに記憶されたクラスタ２以外のクラスタ（即ち、クラスタ０、クラスタ１、クラスタ３）へ選択点たる配達点２０が示す帰属度（クラスタ０：０．１６、クラスタ１：０．０６、クラスタ３：０．０９）のうち最も高い帰属度（０．１６）を示すクラスタ０を所属変更先クラスタとして選択し記憶する（ｓ５１３）。
これら選択点、所属元クラスタ、所属変更先クラスタは、履歴記憶部９８にｓ５１９にて書き込まれるので、図１４中の作業番号３の欄の「所属元」として２が、また「所属変更先」として０が、そして「配達点番号」として２０が記憶されている。
【０１１３】
その後、都市所属変更処理部５５は、自らが有する改善クラスタ別初期巡回路の中の所属元クラスタたるクラスタ２に属している選択点たる配達点２０を削除すると共に、改善クラスタ別初期巡回路の中の所属変更先クラスタたるクラスタ０に選択点たる配達点２０を加える（ｓ５１４）。
ｓ５１４の後、都市所属変更処理部５５は、ｓ５１４にて選択点たる配達点２０が削除及び追加された改善クラスタ別初期巡回路（選択点加除巡回路）をランダム挿入部７１に送信する（ｓ５１５）。
【０１１４】
選択点加除巡回路を受信したランダム挿入部７１は、選択点加除巡回路に従って各クラスタ毎に該クラスタに割り当てられたデポを起点として該クラスタに属する全ての配達点を巡回する巡回路（ランダム挿入選択点加除巡回路）を前述のランダム挿入法によって作成し、ランダム挿入選択点加除巡回路を都市所属変更処理部５５に送信する。ランダム挿入選択点加除巡回路をランダム挿入部７１から受信した都市所属変更処理部５５は、経路記憶部９７にランダム挿入選択点加除巡回路を上書きし記憶させると共に、ランダム挿入選択点加除巡回路を巡回時間算出部７５に送信する（ｓ５１７）。
図２９に、このとき経路記憶部９７に記憶されたランダム挿入選択点加除巡回路を図示した結果を示す。前述の図２８と図２９とを比較すると、選択点たる配達点２０がクラスタ２からクラスタ０に所属が変更されている。
【０１１５】
ｓ５１７にて都市所属変更処理部５５から送信されたランダム挿入選択点加除巡回路を受信した巡回時間算出部７５は、ランダム挿入選択点加除巡回路の各クラスタ毎の距離を算出し、その算出した各クラスタ毎の距離を都市所属変更処理部５５へ送信する（ｓ５１８）。
そして、都市所属変更処理部５５が履歴記憶部９８に選択点の加除処理に関する履歴を書き込み記憶させる（ｓ５１９）（履歴は上書きではなく追加的に書き込み記憶される。）。なお、選択点の加除処理に関する履歴は、前述のように、提供元のクラスタ（クラスタ２）、提供先のクラスタ（クラスタ３）、所属元クラスタ（クラスタ２）、所属変更先クラスタ（クラスタ０）、選択点たる配達点（配達点２０）、各配達車両の稼動率の各項目を含んでいる。
【０１１６】
その後、都市所属変更処理部５５は、所属変更先クラスタ（クラスタ０）と提供先のクラスタ（クラスタ３）とが一致するか否かを判断し（ｓ５２０）、ここでは一致しないので一致すると判断せず（ＮＯ）、このときの所属変更先クラスタ（クラスタ０）を前述のクラスタのリストに記憶し（ｓ５２１）（即ち、このときの所属変更先クラスタ（クラスタ０）がクラスタのリストに追加され、次の処理の所属元クラスタとして選択される候補になる。）、その後、再びｓ５１１へ戻る。
【０１１７】
以下、同様にして、図１４中の作業番号４においては、提供元のクラスタ（クラスタ２）、提供先のクラスタ（クラスタ３）、所属元クラスタ（クラスタ０）、所属変更先クラスタ（クラスタ３）、選択点たる配達点（配達点１９）として動作し、その結果を図３０に示している。前述の図２９と図３０とを比較すると、選択点たる配達点１９がクラスタ０からクラスタ３に所属が変更されている。なお、作業番号４においては、所属変更先クラスタ（クラスタ３）と提供先のクラスタ（クラスタ３）とが一致すると判断され（ｓ５２０、ＹＥＳ）、ｓ５２２以降の処理が行われる。
その後、図１４中の作業番号５においては、提供元のクラスタ（クラスタ０）、提供先のクラスタ（クラスタ３）、所属元クラスタ（クラスタ０）、所属変更先クラスタ（クラスタ３）、選択点たる配達点（配達点４５）として動作し、その結果を図３１に示している。前述の図３０と図３１とを比較すると、選択点たる配達点４５がクラスタ０からクラスタ３に所属が変更されている。なお、作業番号５においては、所属変更先クラスタ（クラスタ３）と提供先のクラスタ（クラスタ３）とが一致すると判断され（ｓ５２０、ＹＥＳ）、ｓ５２２以降の処理が行われる。
【０１１８】
図１４中の作業番号６においては、提供元のクラスタ（クラスタ０）、提供先のクラスタ（クラスタ３）、所属元クラスタ（クラスタ０）、所属変更先クラスタ（クラスタ３）、選択点たる配達点（配達点３２）として動作し、その結果を図３２に示している。前述の図３１と図３２とを比較すると、選択点たる配達点３２がクラスタ０からクラスタ３に所属が変更されている。なお、作業番号６においては、所属変更先クラスタ（クラスタ３）と提供先のクラスタ（クラスタ３）とが一致すると判断され（ｓ５２０、ＹＥＳ）、ｓ５２２以降の処理が行われる。
図１４中の作業番号７においては、提供元のクラスタ（クラスタ０）、提供先のクラスタ（クラスタ３）、所属元クラスタ（クラスタ０）、所属変更先クラスタ（クラスタ３）、選択点たる配達点（配達点３７）として動作し、その結果を図３３に示している。前述の図３２と図３３とを比較すると、選択点たる配達点３７がクラスタ０からクラスタ３に所属が変更されている。なお、作業番号７においては、所属変更先クラスタ（クラスタ３）と提供先のクラスタ（クラスタ３）とが一致すると判断され（ｓ５２０、ＹＥＳ）、ｓ５２２以降の処理が行われる。
【０１１９】
図１４中の作業番号８においては、提供元のクラスタ（クラスタ２）、提供先のクラスタ（クラスタ３）、所属元クラスタ（クラスタ２）、所属変更先クラスタ（クラスタ０）、選択点たる配達点（配達点４０）として動作し、その結果を図３４に示している。前述の図３３と図３４とを比較すると、選択点たる配達点４０がクラスタ２からクラスタ０に所属が変更されている。なお、作業番号８においては、所属変更先クラスタ（クラスタ０）と提供先のクラスタ（クラスタ３）とが一致すると判断されず（ｓ５２０、ＮＯ）、ｓ５２１（所属変更先クラスタ（クラスタ０）を前述のクラスタのリストに記憶する。）以降の処理が行われる。
図１４中の作業番号９においては、提供元のクラスタ（クラスタ２）、提供先のクラスタ（クラスタ３）、所属元クラスタ（クラスタ０）、所属変更先クラスタ（クラスタ３）、選択点たる配達点（配達点４６）として動作し、その結果を図３５に示している。前述の図３４と図３５とを比較すると、選択点たる配達点４６がクラスタ０からクラスタ３に所属が変更されている。なお、作業番号９においては、所属変更先クラスタ（クラスタ３）と提供先のクラスタ（クラスタ３）とが一致すると判断され（ｓ５２０、ＹＥＳ）、ｓ５２２以降の処理が行われる。
【０１２０】
図１４中の作業番号１０においては、提供元のクラスタ（クラスタ０）、提供先のクラスタ（クラスタ２）、所属元クラスタ（クラスタ０）、所属変更先クラスタ（クラスタ２）、選択点たる配達点（配達点２０）として動作し、その結果を図３６に示している。前述の図３５と図３６とを比較すると、選択点たる配達点２０がクラスタ０からクラスタ２に所属が変更されている。なお、作業番号１０においては、所属変更先クラスタ（クラスタ２）と提供先のクラスタ（クラスタ２）とが一致すると判断され（ｓ５２０、ＹＥＳ）、ｓ５２２以降の処理が行われる。
【０１２１】
図１４中の作業番号１１においては、提供元のクラスタ（クラスタ１）、提供先のクラスタ（クラスタ０）、所属元クラスタ（クラスタ１）、所属変更先クラスタ（クラスタ２）、選択点たる配達点（配達点１）として動作し、その結果を図３７に示している。前述の図３６と図３７とを比較すると、選択点たる配達点１がクラスタ１からクラスタ２に所属が変更されている。なお、作業番号１１においては、所属変更先クラスタ（クラスタ２）と提供先のクラスタ（クラスタ０）とが一致すると判断せず（ｓ５２０、ＮＯ）、ｓ５２１（所属変更先クラスタ（クラスタ２）を前述のクラスタのリストに記憶する。）以降の処理が行われる。
図１４中の作業番号１２においては、提供元のクラスタ（クラスタ１）、提供先のクラスタ（クラスタ０）、所属元クラスタ（クラスタ２）、所属変更先クラスタ（クラスタ０）、選択点たる配達点（配達点２２）として動作し、その結果を図３８に示している。前述の図３７と図３８とを比較すると、選択点たる配達点２２がクラスタ２からクラスタ０に所属が変更されている。なお、作業番号１２においては、所属変更先クラスタ（クラスタ０）と提供先のクラスタ（クラスタ０）とが一致すると判断され（ｓ５２０、ＹＥＳ）、ｓ５２２以降の処理が行われる。
【０１２２】
図１４中の作業番号１３においては、提供元のクラスタ（クラスタ２）、提供先のクラスタ（クラスタ１）、所属元クラスタ（クラスタ２）、所属変更先クラスタ（クラスタ１）、選択点たる配達点（配達点１）として動作し、その結果を図３９に示している。前述の図３８と図３９とを比較すると、選択点たる配達点１がクラスタ２からクラスタ１に所属が変更されている。なお、作業番号１３においては、所属変更先クラスタ（クラスタ１）と提供先のクラスタ（クラスタ１）とが一致すると判断され（ｓ５２０、ＹＥＳ）、ｓ５２２以降の処理が行われる。
図１４中の作業番号１４においては、提供元のクラスタ（クラスタ３）、提供先のクラスタ（クラスタ２）、所属元クラスタ（クラスタ３）、所属変更先クラスタ（クラスタ２）、選択点たる配達点（配達点４６）として動作し、その結果を図４０に示している。前述の図３９と図４０とを比較すると、選択点たる配達点４６がクラスタ３からクラスタ２に所属が変更されている。なお、作業番号１４においては、所属変更先クラスタ（クラスタ２）と提供先のクラスタ（クラスタ２）とが一致すると判断され（ｓ５２０、ＹＥＳ）、ｓ５２２以降の処理が行われる。
【０１２３】
図１４中の作業番号１５においては、提供元のクラスタ（クラスタ１）、提供先のクラスタ（クラスタ３）、所属元クラスタ（クラスタ１）、所属変更先クラスタ（クラスタ２）、選択点たる配達点（配達点１）として動作し、その結果を図４１に示している。前述の図４０と図４１とを比較すると、選択点たる配達点１がクラスタ１からクラスタ２に所属が変更されている。なお、作業番号１５においては、所属変更先クラスタ（クラスタ２）と提供先のクラスタ（クラスタ３）とが一致すると判断せず（ｓ５２０、ＮＯ）、ｓ５２１（所属変更先クラスタ（クラスタ２）を前述のクラスタのリストに記憶する。）以降の処理が行われる。
図１４中の作業番号１６においては、提供元のクラスタ（クラスタ１）、提供先のクラスタ（クラスタ３）、所属元クラスタ（クラスタ２）、所属変更先クラスタ（クラスタ０）、選択点たる配達点（配達点４６）として動作し、その結果を図４２に示している。前述の図４１と図４２とを比較すると、選択点たる配達点４６がクラスタ２からクラスタ０に所属が変更されている。なお、作業番号１６においては、所属変更先クラスタ（クラスタ０）と提供先のクラスタ（クラスタ３）とが一致すると判断せず（ｓ５２０、ＮＯ）、ｓ５２１（所属変更先クラスタ（クラスタ０）を前述のクラスタのリストに記憶する。）以降の処理が行われる。
図１４中の作業番号１７においては、提供元のクラスタ（クラスタ１）、提供先のクラスタ（クラスタ３）、所属元クラスタ（クラスタ０）、所属変更先クラスタ（クラスタ３）、選択点たる配達点（配達点４６）として動作し、その結果を図４３に示している。前述の図４２と図４３とを比較すると、選択点たる配達点４６がクラスタ０からクラスタ３に所属が変更されている。なお、作業番号１７においては、所属変更先クラスタ（クラスタ３）と提供先のクラスタ（クラスタ３）とが一致すると判断され（ｓ５２０、ＹＥＳ）、ｓ５２２以降の処理が行われる。
【０１２４】
図１４中の作業番号１８においては、提供元のクラスタ（クラスタ２）、提供先のクラスタ（クラスタ１）、所属元クラスタ（クラスタ２）、所属変更先クラスタ（クラスタ１）、選択点たる配達点（配達点１）として動作し、その結果を図４４に示している。前述の図４３と図４４とを比較すると、選択点たる配達点１がクラスタ２からクラスタ１に所属が変更されている。なお、作業番号１８においては、所属変更先クラスタ（クラスタ１）と提供先のクラスタ（クラスタ１）とが一致すると判断され（ｓ５２０、ＹＥＳ）、ｓ５２２以降の処理が行われる。
【０１２５】
図１４中の作業番号１９においては、提供元のクラスタ（クラスタ３）、提供先のクラスタ（クラスタ２）、所属元クラスタ（クラスタ３）、所属変更先クラスタ（クラスタ２）、選択点たる配達点（配達点４６）として動作し、その結果を図４５に示している。前述の図４４と図４５とを比較すると、選択点たる配達点４６がクラスタ３からクラスタ２に所属が変更されている。なお、作業番号１９においては、所属変更先クラスタ（クラスタ２）と提供先のクラスタ（クラスタ２）とが一致すると判断され（ｓ５２０、ＹＥＳ）、ｓ５２２以降の処理が行われ、再びｓ５０１へ戻る。
このときｓ５０１〜ｓ５０５の動作の後、ｓ５０６にて所属変更処理部５３が、受信した均等化係数が、自らが記憶している均等化係数よりも小さいか、又は自らが均等化係数を記憶していないかのいずれでもないと判断し（ＮＯ）（即ち、所属変更処理部５３が均等化係数を記憶しており、かつ該受信した均等化係数が、該記憶している均等化係数以上である場合）履歴チェック部５４に起動信号を発する（ｓ５５１）。
【０１２６】
ｓ５５１にて所属変更処理部５３が発した起動信号を受信した履歴チェック部５４は、履歴記憶部９８にアクセスして履歴記憶部９８が記憶している選択点の加除処理に関する履歴（即ち、図１４に示すもの）を読み込み取得する（ｓ５２６）。そして、履歴チェック部５４は、該読み込み取得した選択点の加除処理に関する履歴の直近履歴（図１４に示したものであれば、作業番号１９にて示されるもの。）と、直近履歴以外の履歴（その他履歴。図１４に示したものであれば、作業番号１〜１８それぞれにて示されるもの。）と、を比較し、直近履歴と同一のものがその他履歴に存するか否かを判断する（ｓ５２７）。ここでは作業番号１９と作業番号１４とは、提供元のクラスタ（クラスタ３）、提供先のクラスタ（クラスタ２）、所属元クラスタ（クラスタ３）、所属変更先クラスタ（クラスタ２）、選択点たる配達点（配達点４６）の全てが一致しているので、履歴チェック部５４が、直近履歴（作業番号１９）と同一のもの（作業番号１４）がその他履歴に存すると判断し（ＹＥＳ）、履歴チェック部５４は所属変更結果設定部５６に起動信号を送信する（ｓ５２８）。
ｓ５２８にて履歴チェック部５４が発した起動信号を受信した所属変更結果設定部５６は、履歴記憶部９８にアクセスして履歴記憶部９８が記憶している前記選択点の加除処理に関する履歴（図１４）を読み込み取得し、その各履歴（作業番号１〜１９それぞれ）に含まれる各配達車両の稼動率を用いて各履歴（作業番号１〜１９それぞれ）の均等化係数を計算する（ｓ５３１）。次いで、所属変更結果設定部５６は、それら各履歴（作業番号１〜１９それぞれ）毎に計算した均等化係数のうち最も小さい値を与える巡回路（作業番号１〜１９のいずれか）を選択し、該選択した巡回路を経路記憶部９７に送信し経路記憶部９７に記憶させる（ｓ５３２）。
その後、所属変更結果設定部５６は、稼動率調整部６１（稼動率調整制御部６３）に起動信号を発し（ｓ５３３）、後述のｓ６０１へ行く。
【０１２７】
図２３〜図２５は、本装置１１の稼動率調整部６１の動作を示すフローチャートである。図２３〜図２５を参照して、本装置１１の稼動率調整部６１の動作について説明する。
まず、図２３を参照する。
前述のｓ５３３にて所属変更結果設定部５６から発せられた前記起動信号を受信した稼動率調整制御部６３は、自らが記憶する組み合わせ履歴リストに記憶されている内容を削除する（ｓ６０１）。
次いで、稼動率調整制御部６３は、初期情報記憶部９１にアクセスし初期情報記憶部９１が記憶している制約条件（図３（ｃ））を読み出し取得し（後述の稼動率の算出に用いる。）、さらに経路記憶部９７にアクセスし経路記憶部９７が記憶している巡回路（所属変更結果設定部５６が、最も小さい均等化係数を与える巡回路として選択したもの）を読み出し取得する（ｓ６０２）。そして、稼動率調整制御部６３は、この読み出し取得した巡回路を巡回時間算出部７５に送信する（ｓ６０３）。
【０１２８】
ｓ６０３にて稼動率調整制御部６３から送信された前記巡回路を受信した巡回時間算出部７５は、所要時間記憶部９９が記憶している距離テーブルを読み出し取得し、前記巡回路の各クラスタ毎の巡回距離を距離テーブルから算出し、そしてこの算出された前記巡回路に従った各クラスタ毎の巡回距離を稼動率調整制御部６３へ送信する（ｓ６０４）。
ｓ６０４にて巡回時間算出部７５から送信された前記巡回路に従った各クラスタ毎の巡回距離を受信した稼動率調整制御部６３は、その受信した各クラスタ毎の巡回距離と、初期情報記憶部９１から読み出し取得した制約条件（図３（ｃ））と、を用いて各クラスタ毎の稼動率を算出する（ｓ６０５）（なお、稼動率は、前述のように、各クラスタ毎の巡回距離を、該クラスタを担当する配達車両の制約条件（図３（ｃ）、ここでは全て１００００）によって除した商である。）。
次いで、稼動率調整制御部６３は、ｓ６０５にて算出した各クラスタ毎の稼動率の大きい順番を決し、その大きい順番にクラスタ番号を並べて整列クラスタ番号を作成する（ｓ６０６）。
【０１２９】
その後、稼動率調整制御部６３は、自らが記憶する後述の候補リストに記憶されている内容を削除する（ｓ６０７）（候補リストに何も記憶されていなければ削除不要である）。
次いで、稼動率調整制御部６３は、整列クラスタ番号の先頭に位置するクラスタ番号（整列クラスタ番号が「３、０、２、１」であるときは「３」）によって示されるクラスタ（ここではクラスタ３）を稼動率調整提供元クラスタとして選ぶ（ｓ６０８）。
さらに、稼動率調整制御部６３は、稼動率調整提供元クラスタに属する配達点のいずれかを変更候補配達点ｐとして選択する（ｓ６０９）。
【０１３０】
そして、稼動率調整制御部６３は、全てのクラスタから１のクラスタを稼動率調整提供先クラスタとして選択する（ｓ６１０）。ここではクラスタ番号の最も小さいもの、即ち、クラスタ０を最初に選択する。
その後、稼動率調整制御部６３は、稼動率調整提供元クラスタと稼動率調整提供先クラスタとが一致しているか否かを判断し（ｓ６１１）、両クラスタが一致していると判断した場合（ＹＥＳ）には後述のｓ６１６へ行く。ｓ６１１にて稼動率調整制御部６３が、稼動率調整提供元クラスタと稼動率調整提供先クラスタとが一致していないと判断した場合（ＮＯ）、稼動率調整制御部６３は、経路記憶部９７からｓ６０２にて読み出し取得した巡回路を変更試行部６５に送信する（ｓ６１２）。
【０１３１】
次いで、図２４を参照する。
ｓ６１２にて稼動率調整制御部６３から送信された巡回路を受信した変更試行部６５は、変更候補配達点ｐを稼動率調整提供元クラスタから稼動率調整提供先クラスタへ所属を変更した際の巡回距離差を算出する（ｓ６１３）（なお、変更試行部６５は所要時間記憶部９９が記憶している距離テーブルを読み出し取得し、巡回距離差を算出する。）。
ｓ６１３にて算出した巡回距離差が正の値か否かを変更試行部６５が判断し（ｓ６１４）、巡回距離差が正の値と判断した場合（ＹＥＳ）、そのときの稼動率調整提供元クラスタ、稼動率調整提供先クラスタ、変更候補配達点ｐたる配達点、巡回距離差のデータを関係付けた情報を変更試行部６５は稼動率調整制御部６３に送信し、該情報を稼動率調整制御部６３に候補リストとして上書きではなく追加的に記憶させる（ｓ６１５）。なおこのとき候補リストへの記憶は、該関係付けた情報に含まれる巡回距離差が大きいものから順番に記憶される。
一方、ｓ６１４にて変更試行部６５が巡回距離差が正の値と判断しない場合（ＮＯ）、変更試行部６５が稼動率調整制御部６３に稼動率調整提供先クラスタとして次のクラスタを選択することを命令する信号を発する（ｓ６１６）。
【０１３２】
ｓ６１６にて発せられた信号を受信するか又はｓ６１５の後、稼動率調整制御部６３は稼動率調整提供先クラスタとして次のクラスタが選択可能か否か判断し（ｓ６１７）、稼動率調整提供先クラスタとして次のクラスタが選択可能と判断した場合（ＹＥＳ）には稼動率調整提供先クラスタとして次のクラスタを選択し（ｓ６１８）、再びｓ６１１に戻る。
ｓ６１７にて稼動率調整制御部６３が稼動率調整提供先クラスタとして次のクラスタが選択可能と判断しない場合（ＮＯ）（全てのクラスタが稼動率調整提供先クラスタとして既に選択されており、他のクラスタが稼動率調整提供先クラスタとして選択できない場合）には、稼動率調整制御部６３は変更候補配達点ｐとして次の配達点が選択可能か否か判断する（ｓ６１９）。
ｓ６１９にて稼動率調整制御部６３が変更候補配達点ｐとして次の配達点が選択可能であると判断した場合（ＹＥＳ）、稼動率調整制御部６３は、稼動率調整提供元クラスタの次の配達点（変更候補配達点ｐとして既に選択されている配達点を除いた配達点のうち巡回路内で先頭に位置する配達点）を次の変更候補配達点ｐとして選び（ｓ６２０）、ｓ６１０へ戻る。
ｓ６１９にて稼動率調整制御部６３が変更候補配達点ｐとして次の配達点が選択可能であると判断しない場合（ＮＯ）、稼動率調整制御部６３は、稼動率調整提供元クラスタとして次のクラスタが選択可能か否か判断し（ｓ６２１）、稼動率調整提供元クラスタとして次のクラスタが選択可能と判断した場合（ＹＥＳ）には稼動率調整提供元クラスタとして次のクラスタ（整列クラスタ番号の中で、稼動率調整提供元クラスタとして選ばれているクラスタの次のクラスタ）を選択し（ｓ６２２）、再びｓ６０９に戻る。
【０１３３】
ｓ６２１にて、稼動率調整制御部６３が、稼動率調整提供元クラスタとして次のクラスタが選択可能と判断しない場合（ＮＯ）（即ち、もはや稼動率調整提供元クラスタとして未だ選択されていないクラスタが存しない場合）には、稼動率調整制御部６３は候補チェックを行う（ｓ６２３）。候補チェックは、前述したように、稼動率調整制御部６３が有する候補リスト（稼動率調整提供元クラスタ、稼動率調整提供先クラスタ、変更候補配達点ｐたる配達点、巡回距離差のデータを関係付けた情報（候補）が、該巡回距離差が大きいものから順番に記憶されている。）に記憶される候補と、稼動率調整制御部６３が有するこれまで行った所属変更の履歴を記憶している履歴リストに記憶された所属変更履歴（稼動率調整提供元クラスタ、稼動率調整提供先クラスタ、変更候補配達点ｐたる配達点、巡回距離、各配達車両の稼動率、均等化係数が記憶されている。）と、を稼動率調整制御部６３が見比べ、各候補が含む稼動率調整提供元クラスタ、稼動率調整提供先クラスタ、変更候補配達点ｐたる配達点と同じ稼動率調整提供元クラスタ、稼動率調整提供先クラスタ、変更候補配達点ｐたる配達点を含む所属変更履歴が存在すれば稼動率調整制御部６３が候補リストからその候補を削除し、存在しなければ次の候補をチェックする。候補リスト中に未チェックの候補がなくなるまでこれを行う。
【０１３４】
さらに、図２５を参照する。
ｓ６２３の後、稼動率調整制御部６３が候補リスト中に候補が残っているか否か判断し（ｓ６２４）、残っていれば（ＹＥＳ）その残っている候補のうち先頭に位置する候補に従って配達点が属するクラスタを変更する（ｓ６２５）（即ち、先頭の候補に示された変更候補配達点ｐたる配達点を、稼動率調整提供元クラスタから稼動率調整提供先クラスタへ所属を変更する。具体的には、稼動率調整制御部６３は、ｓ６０２にて経路記憶部９７から読み出した巡回路の中の稼動率調整提供元クラスタから変更候補配達点ｐを除き、稼動率調整提供先クラスタに変更候補配達点ｐを加える。）。ｓ６２４にて稼動率調整制御部６３が、候補リスト中に候補が残っていると判断しない場合（ＮＯ）、稼動率調整制御部６３は結果出力部６７へ巡回路（ｓ６０２にて経路記憶部９７から読み出し取得したもの）と履歴リストとを送信する（ｓ６２６）。
【０１３５】
ｓ６２５の後、稼動率調整制御部６３は、稼動率調整提供元クラスタと稼動率調整提供先クラスタとに関する両方の巡回路（変更候補配達点ｐたる配達点が、前者は除かれ後者は加入されている。）をランダム挿入部７１に送信する（ｓ６２７）。ｓ６２７にて稼動率調整制御部６３から送信された該両方の巡回路を受信したランダム挿入部７１は、初期情報記憶部９１にアクセスして初期情報記憶部９１が記憶している配達点の座標（図３（ａ））とデポの座標（図３（ｂ））とを読み出し取得し、所要時間記憶部９９にアクセスし所要時間記憶部９９が記憶している距離テーブルを読み出し取得し、該両方の巡回路に従って両クラスタ毎に該クラスタに割り当てられたデポを起点として該クラスタに属する全ての配達点を巡回する巡回路を前述のランダム挿入法によって作成し、稼動率調整制御部６３に送信する（ｓ６２８）。
【０１３６】
ｓ６２８にてランダム挿入部７１から送信された巡回路を受信した稼動率調整制御部６３は、該受信した巡回路をＮ−ｏｐｔ部７３に送信する（ｓ６２９）。
ｓ６２９にて稼動率調整制御部６３から送信されたその巡回路を受信したＮ−ｏｐｔ部７３は、初期情報記憶部９１にアクセスして初期情報記憶部９１が記憶している配達点の座標（図３（ａ））とデポの座標（図３（ｂ））とを読み出し取得し、さらに所要時間記憶部９９にアクセスして所要時間記憶部９９が記憶している距離テーブル（図５参照）を読み出し取得し、これら配達点の座標（図３（ａ））、デポの座標（図３（ｂ））及び距離テーブルを用いて、その巡回路（稼動率調整提供元クラスタと稼動率調整提供先クラスタとに関する両方の巡回路）に前述のＮ−ｏｐｔ法を（各クラスタ毎に）適用してその巡回路を改善し、改善された巡回路を稼動率調整制御部６３へ送信する（ｓ６３０）。
改善された巡回路をＮ−ｏｐｔ部７３から受信した稼動率調整制御部６３は、該改善された巡回路を巡回時間算出部７５に送信する（ｓ６３１）。
ｓ６３１にて稼動率調整制御部６３から送信された該改善された巡回路を受信した巡回時間算出部７５は、所要時間記憶部９９が記憶している距離テーブルを読み出し取得し、該改善された巡回路の各クラスタ毎の巡回距離を距離テーブルから算出し、この算出された各クラスタ毎の巡回距離を稼動率調整制御部６３へ送信する（ｓ６３２）。
【０１３７】
ｓ６３２にて巡回時間算出部７５から送信されたクラスタ毎の巡回距離を受信した稼動率調整制御部６３は、全てのクラスタそれぞれの巡回距離と、初期情報記憶部９１から読み出し取得した制約条件（図３（ｃ））と、を用いて各クラスタ毎の稼動率を算出すると共に、稼動率調整制御部６３は、これら算出した各クラスタの稼動率を用いて均等化係数を算出する（ｓ６３３）。
ｓ６３３の後、稼動率調整制御部６３は、自らが有する履歴リストに所属変更履歴（稼動率調整提供元クラスタ、稼動率調整提供先クラスタ、変更候補配達点ｐたる配達点、巡回距離、各配達車両の稼動率、均等化係数が記憶される。）を書き込み記憶させると共に、巡回路（上述のように、Ｎ−ｏｐｔ部７３から受信した改善された巡回路）を経路記憶部９７へ書き込み（ｓ６３４）、そして、ｓ６０１へ戻る。
【０１３８】
なお、ｓ６２６にて稼動率調整制御部６３が発した巡回路と履歴リストとを受信した結果出力部６７は、受信した履歴リスト中の所属変更履歴のうち稼動率全てが１以下であって巡回距離が最小のものを抽出し、該抽出された所属変更履歴に対応する巡回路を最終決定巡回路として所定の方法（印刷やディスプレイへの表示等）にて出力する（ｓ６３５）。
なお、結果出力部６７が最終決定巡回路を得る方法は、前述したように次の（１）〜（４）のようにして行われる。即ち、まず、（１）結果出力部６７は、稼動率調整制御部６３から受信した履歴リストに含まれる所属変更履歴（稼動率調整提供元クラスタ、稼動率調整提供先クラスタ、変更候補配達点ｐたる配達点、巡回距離、各配達車両の稼動率、均等化係数が含まれる。）のうち、稼動率全てが１以下であって巡回距離が最小のもの（以下、「目的所属変更履歴」という。）を抽出する。次いで、（２）結果出力部６７は、稼動率調整制御部６３から受信した履歴リストと、稼動率調整制御部６３から受信した巡回路と、を用いて、目的所属変更履歴に該当する各クラスタに属する配達点のリストを作成する。具体的には、稼動率調整制御部６３から受信した巡回路は、稼動率調整制御部６３から受信した履歴リストの直近の所属変更がなされた後の状態を示しているので、直近の履歴リストから順に目的所属変更履歴までの所属変更履歴が示す所属変更を逆に行うことで、目的所属変更履歴に該当する各クラスタに属する配達点のリスト（具体的には、各クラスタ毎に属する配達点の番号が列記されたもの）を作成する。そして、（３）上記（２）にて得られた目的所属変更履歴に該当する各クラスタに属する配達点のリストを、結果出力部６７がランダム挿入部７１に送信し、これまでと同様、ランダム挿入部７１に該配達点のリストに従った巡回路を作成させる（該配達点のリストに従って、各クラスタに割り当てられたデポを起点として該クラスタに属する全ての配達点を巡回する巡回路をランダム挿入法によって作成する。）。ランダム挿入部７１は、作成した巡回路を結果出力部６７へ送信する。最後に、（４）ランダム挿入部７１から巡回路を受信した結果出力部６７は、該受信した巡回路をＮ−ｏｐｔ部７３に送信し、これまでと同様、Ｎ−ｏｐｔ部７３にその巡回路にＮ−ｏｐｔ法を（各クラスタ毎に）適用してその巡回路を改善させる。Ｎ−ｏｐｔ部７３は、改善された巡回路を結果出力部６７へ送信する。
【０１３９】
以上説明したように、本装置１１は、本発明にいう第３本装置、第１本装置及び第２本装置を含んでいる。
まず、本装置１１が含む第３本装置は次のように構成されている。
第３本装置は、クラスタ数計算部３７とランダム挿入部７１とＮ−ｏｐｔ部７３と巡回時間算出部７５とによって構成される全体負荷算出手段（複数の地点（配達点）の位置データを受け付け、該複数の地点全部を巡る全体の負荷を算出する手段）と、クラスタ数計算部３７によって構成される移動体数決定手段（複数の地点（配達点）の一部を巡る移動体（配達車両）それぞれが受け持ち可能な負荷の量である負荷許容量（制約条件たる図３（ｃ））を受け付け、全体負荷算出手段により評価された該全体の負荷と該負荷許容量とから該移動体の数を所定の方法により決定する手段）と、ファジークラスタリング計算部４３と初期巡回路作成部４５とによって構成される地点分割手段（複数の地点（配達点）を該移動体の数（移動体数決定手段によって決定された数）だけ分割する手段）と、初期巡回路作成部４５によって構成される移動体出発位置情報受付手段（移動体（配達車両）それぞれの出発位置を示す出発位置情報（図３（ｂ））を受け付ける手段）と、初期巡回路作成部４５によって構成される移動体割当手段（地点分割手段により分割された地点（配達点）のそれぞれのグループ（クラスタ）に対し所定の位置関係（ここでは各クラスタの重心に最も近い位置関係）を有する出発位置情報に係る移動体（配達車両）を割り当てる手段）と、ランダム挿入部７１とＮ−ｏｐｔ部７３（と初期巡回路作成部４５）とによって構成される各グループ原始経路形成手段（移動体割当手段により割当られた移動体（配達車両）の出発位置（デポ）を始点とし、それぞれの移動体（配達車両）に対応するグループ（クラスタ）に属する全ての地点を巡る各グループ（クラスタ）毎の経路（改善クラスタ別初期巡回路）を作成する手段）と、を備えてなる、経路形成装置である。
【０１４０】
そして、本装置１１が含む第３本装置は、初期巡回路作成部４５によって構成される総量判断手段（各グループ原始経路形成手段によって形成された各グループ（クラスタ）毎の経路（改善クラスタ別初期巡回路）に関する負荷（巡回距離）を全てのグループ（クラスタ）に関して合計した第１総量と、移動体数決定手段によって受け付けられ、各グループ（クラスタ）に割当られた移動体（配達車両）それぞれの負荷許容量（制約条件）を合計した第２総量と、を比較し、第２総量が第１総量以上であるか否か判断する手段）と、初期巡回路作成部４５によって構成される移動体増加手段（総量判断手段たる初期巡回路作成部４５が第２総量が第１総量以上であると判断しない場合、移動体（配達車両）の数を増加させる手段）と、をさらに備えている。さらに、地点分割手段は該増加された移動体（配達車両）の数に応じて複数の地点（配達点）を分割し、移動体割当手段は、該増加された移動体（配達車両）の数に応じて分割された地点（配達点）のそれぞれのグループに移動体（配達車両）を割り当て、そして各グループ原始経路形成手段は、該増加された移動体（配達車両）の数に応じて分割された地点（配達点）のそれぞれのグループ毎の経路を作成する。
【０１４１】
次いで、本装置１１が含む第１本装置は次のように構成されている。
第１本装置は、都市所属変更処理部５５によって構成される経路データ受付手段（始点と、複数の地点を巡る経路と、を含んでなる複数の経路データを受け付ける手段）と、都市所属変更処理部５５によって構成される開始完了決定手段（第１本装置の経路データ受付手段により受け付けられる複数の経路データのうち、負荷が最も軽い経路とは異なる経路である開始経路（ここでは負荷が最も重い経路である、提供元のクラスタの経路）と、該開始経路よりも負荷が軽い経路である完了経路（ここでは負荷が最も軽い経路である、提供先のクラスタの経路）と、を決定する手段）と、都市所属変更処理部５５によって構成される所属変更手段（第１本装置の経路データ受付手段により受け付けられる複数の経路データの一経路（所属元クラスタの経路）に含まれる地点（配達点）である選択点と、該選択点と所定の関係（クラスタのリストに記憶されたクラスタ以外のクラスタへ選択点が示す帰属度のうち最も高い帰属度を示す関係）を有する他の経路（所属変更先クラスタの経路）と、を選択すると共に、該一経路から該他の経路へ該選択点を移動させるものであり、初回には開始経路（提供元のクラスタの経路）を該一経路として選択し、次回以降は前回以前の該他の経路又は開始経路を該一経路として該選択と該移動との動作を繰り返す手段）と、都市所属変更処理部５５によって構成される完了判断手段（該他の経路（所属変更先クラスタの経路）が該完了経路（提供先のクラスタの経路）と一致するか否か判断する手段）と、を備えており、所属変更手段が、完了判断手段が一致すると判断するまで繰り返し動作するものである、経路調整装置である。
【０１４２】
そして、本装置１１が含む第１本装置においては、上述のように、開始経路が、経路データ受付手段により受け付けられる複数の経路データのうち負荷が最も重い経路であり、そして完了経路が、該複数の経路データのうち負荷が最も軽い経路である。
さらに、本装置１１が含む第１本装置においては、所属変更手段たる都市所属変更処理部５５は、前記前回以前の該他の経路又は開始経路（クラスタのリストに記憶されたクラスタの経路）に含まれる地点のうち前記完了経路（提供先のクラスタの経路）への帰属度が最も高い地点を前記選択点として選択する。
また、本装置１１が含む第１本装置においては、所属変更手段たる都市所属変更処理部５５は、前記前回以前の該他の経路又は開始経路（クラスタのリストに記憶されたクラスタの経路）以外の経路へ前記選択点が示す帰属度のうち最も高い帰属度を示す経路を前記他の経路（所属変更先クラスタの経路）として選択する。
【０１４３】
本装置１１が含む第１本装置は、ランダム挿入部７１によって構成される経路形成手段（（第１本装置の）所属変更手段によって前記選択点が加除され、含まれる地点に変更が生じた経路に所属する地点を巡る順番を決定し経路を形成する手段）を、さらに備える。
また、本装置１１が含む第１本装置においては、第１本装置の経路形成手段たるランダム挿入部７１によって形成された経路を含む経路データを、第１本装置の経路データ受付手段たる都市所属変更処理部５５が受け付けさらに経路調整する。
なお、ここではそうしていないが、経路形成手段によって形成された経路における経路毎の負荷のばらつきが所定範囲に収まるまで、繰り返し経路調整するようにしてもよい。
【０１４４】
加えて、本装置１１が含む第１本装置は、経路制御部５２によって構成される均等化データ形成手段（第１本装置の経路形成手段たるランダム挿入部７１によって形成された経路における経路毎の負荷のばらつきを示すデータである均等化データ（均等化係数）を形成（算出）する手段）と、所属変更処理部５３によって構成される均等化データ記憶手段（均等化データたる均等化係数を記憶する手段。所属変更処理部５３は、これまでの最小の均等化係数を記憶する。）と、所属変更処理部５３によって構成される改善判断手段（第１本装置の均等化データ形成手段によって形成された直近の均等化データ（均等化係数）が、第１本装置の均等化データ記憶手段に記憶された過去の均等化データ（均等化係数）に比して、改善されているか否か（ここでは小さくなっているか否か）判断する手段）と、をさらに備え、改善判断手段たる所属変更処理部５３が、改善されていると判断した場合、第１本装置の経路形成手段（ランダム挿入部７１）によって形成された経路に係る経路データを、第１本装置の経路データ受付手段（都市所属変更処理部５５）が受け付けさらに経路調節する。
【０１４５】
本装置１１が含む第１本装置においては、履歴記憶部９８によって構成される履歴記憶手段（第１本装置の所属変更手段が行う前記選択点の所属変更処理の履歴を記憶する手段）と、履歴チェック部５４によって構成される収束判断部（直近の選択点の所属変更処理と同一の履歴を、第１本装置の履歴記憶手段が記憶しているか否か（直近履歴と同一のものがその他履歴に存するか否か）判断する収束判断部）と、さらに備える。そして、収束判断部たる履歴チェック部５４が、直近の選択点の所属変更処理（直近の均等化データに係る選択点の所属変更処理）と同一の履歴を、第１本装置の履歴記憶手段が記憶していると判断しない場合、第１本装置の経路形成手段によって形成された経路に係る経路データを第１本装置の経路データ受付手段が受け付けさらに経路調節する。なお、ここでは第１本装置の改善判断手段が、直近の均等化データが改善されていると判断しない場合、収束判断部たる履歴チェック部５４が、直近履歴と同一のものがその他履歴に存するか否かを判断するようにされている。
【０１４６】
次いで、本装置１１が含む第２本装置は次のように構成されている。
第２本装置は、稼動率調整制御部６３によって構成される経路データ受付手段（始点と、複数の地点を巡る経路と、を含んでなる複数の経路データを受け付ける手段）と、稼動率調整制御部６３と変更試行部６５とによって構成される全体負荷評価手段（第２本装置の経路データ受付手段（稼動率調整制御部６３）により受け付けられる複数の経路データに含まれる各地点（配達点）を、該地点（配達点）が含まれていない経路（稼動率調整提供先クラスタの経路）に所属させた際に生じる全経路の負荷（距離）の変化（巡回距離差）を評価する手段）と、稼動率調整制御部６３の候補リストによって構成される負荷変化記憶手段（全体負荷評価手段により評価される負荷（距離）の変化が、地点（配達点）の所属が変更される前に比して負荷が低減される（距離が短くなる）ことを示す場合における所属が変更される地点（配達点）と、該所属が変更される地点（配達点）が所属が変更される前に所属している経路である前所属経路たる稼動率調整提供元クラスタ（の経路）と、該所属が変更される地点が所属が変更される先の経路である後所属経路たる稼動率調整提供先クラスタ（の経路）と、を関連付けられたものを変更候補データとして記憶する手段）と、稼動率調整制御部６３によって構成される抽出手段（負荷変化記憶手段に記憶された変更候補データのうち所定の条件に合致するものを抽出する手段）と、を備えるものである、経路調整装置である。
【０１４７】
そして、本装置１１が含む第２本装置においては、変更候補データが、全経路の負荷（距離）の総和が、地点（配達点）の所属が変更される前に比してどの程度低減されるかを示す低減度合いたる巡回距離差のデータをさらに関連付けられた状態で記憶されており、抽出手段が抽出する際の前記所定の条件が、該低減度合いが最大であるという条件である。
本装置１１が含む第２本装置は、ランダム挿入部７１とＮ−ｏｐｔ部７３とによって構成される（第２本装置の）経路形成手段（抽出手段によって抽出された変更候補データに従って経路を形成する手段）を、さらに備えている。
また、本装置１１が含む第２本装置においては、（第２本装置の）経路形成手段によって形成された経路を含む経路データを、（第２本装置の）経路データ受付手段が受け付けさらに経路調整する。
【０１４８】
本装置１１が含む第２本装置は、稼動率調整制御部６３が有する履歴リストによって構成される変更候補履歴記憶手段（抽出手段により抽出された変更候補データの履歴を記憶する手段）をさらに備え、抽出手段が、第２本装置の負荷変化記憶手段（稼動率調整制御部６３の候補リスト）に記憶された変更候補データのうち、変更候補履歴記憶手段に記憶された履歴と同一のものを除いた変更履歴データから抽出する。
そして、本装置１１が含む第２本装置においては、抽出手段が変更履歴データを抽出することができなくなるまで、（第２本装置の）経路形成手段によって形成された経路を含む経路データを（第２本装置の）経路データ受付手段が受け付けさらに経路調整する。
【０１４９】
また、本装置１１においては、第３本装置が形成した移動体（配達車両）の出発位置（デポ）を始点とする各グループ毎の経路を、第１本装置の経路データ受付手段が経路データとして受け付ける。そして、第１本装置の経路形成手段によって形成された経路を、第２本装置の経路データ受付手段が経路データとして受け付けさらに経路調整する。
【図面の簡単な説明】
【図１】一実施形態の本発明の経路探索装置（本装置）のハードウエア構成を示す概略ブロック図である。
【図２】本装置の大まかな基本構成を示す概略機能ブロック図である。
【図３】初期情報データベースが予め記憶しているデータの一例を示す図である。
【図４】クラスタ分割部の詳細機能ブロック図である。
【図５】テーブル初期化部３５が作成する距離テーブルの一例である。
【図６】Ｎ−ｏｐｔ部７３からクラスタ数計算部３７が受信した巡回路の一例（巡回路を座標中に図示したもの）である。
【図７】仮巡回路形成部４１の詳細機能ブロック図である。
【図８】計算された各配達点の各クラスタへの帰属度を示す図である。
【図９】配達点の所属クラスタの決定方法を示す図である。
【図１０】各クラスタに所属する配達点の番号を各クラスタ毎に記載した配達点番号リストの一例である。
【図１１】経路記憶部９７が記憶している配達点番号リストの各クラスタに割り当てたデポを書き込んだものを示す図である。
【図１２】改善クラスタ別初期巡回路の一例を示す図である。
【図１３】所属調整部５１の詳細機能ブロック図である。
【図１４】履歴記憶部９８に書き込まれて記憶された履歴の一例を示す図である。
【図１５】稼動率調整部６１の詳細機能ブロック図である。
【図１６】巡回距離差の算出方法について説明する図である。
【図１７】クラスタ分割部３１の動作を示すフローチャートである。
【図１８】仮巡回路形成部４１の動作を示すフローチャートである。
【図１９】仮巡回路形成部４１の動作を示すフローチャートである。
【図２０】所属調整部５１の動作を示すフローチャートである。
【図２１】所属調整部５１の動作を示すフローチャートである。
【図２２】所属調整部５１の動作を示すフローチャートである。
【図２３】稼動率調整部６１の動作を示すフローチャートである。
【図２４】稼動率調整部６１の動作を示すフローチャートである。
【図２５】稼動率調整部６１の動作を示すフローチャートである。
【図２６】ｓ５０１にて経路制御部５２が、経路記憶部９７から読み出し取得した改善クラスタ別初期巡回路を示す図である。
【図２７】ランダム挿入選択点加除巡回路を示す図である。
【図２８】ランダム挿入選択点加除巡回路を示す図である。
【図２９】ランダム挿入選択点加除巡回路を示す図である。
【図３０】ランダム挿入選択点加除巡回路を示す図である。
【図３１】ランダム挿入選択点加除巡回路を示す図である。
【図３２】ランダム挿入選択点加除巡回路を示す図である。
【図３３】ランダム挿入選択点加除巡回路を示す図である。
【図３４】ランダム挿入選択点加除巡回路を示す図である。
【図３５】ランダム挿入選択点加除巡回路を示す図である。
【図３６】ランダム挿入選択点加除巡回路を示す図である。
【図３７】ランダム挿入選択点加除巡回路を示す図である。
【図３８】ランダム挿入選択点加除巡回路を示す図である。
【図３９】ランダム挿入選択点加除巡回路を示す図である。
【図４０】ランダム挿入選択点加除巡回路を示す図である。
【図４１】ランダム挿入選択点加除巡回路を示す図である。
【図４２】ランダム挿入選択点加除巡回路を示す図である。
【図４３】ランダム挿入選択点加除巡回路を示す図である。
【図４４】ランダム挿入選択点加除巡回路を示す図である。
【図４５】ランダム挿入選択点加除巡回路を示す図である。
【符号の説明】
１１　　　　　本装置
１１ａ　　　　ＣＰＵ
１１ｂ　　　　ＲＡＭ
１１ｃ　　　　ＲＯＭ
１１ｄ　　　　インターフェイス
１９　　　　　ハードディスク
２１　　　　　初期情報データベース
３１　　　　　クラスタ分割部
３３　　　　　ファイル読み出し部
３５　　　　　テーブル初期化部
３７　　　　　クラスタ数計算部
４１　　　　　仮巡回路形成部
４３　　　　　ファジークラスタリング計算部
４５　　　　　初期巡回路作成部
５１　　　　　所属調整部
５２　　　　　経路制御部
５３　　　　　所属変更処理部
５４　　　　　履歴チェック部
５５　　　　　都市所属変更処理部
５６　　　　　所属変更結果設定部
６１　　　　　稼動率調整部
６３　　　　　稼動率調整制御部
６５　　　　　変更試行部
６７　　　　　結果出力部
７１　　　　　ランダム挿入部
７３　　　　　Ｎ−ｏｐｔ部
７５　　　　　巡回時間算出部
９１　　　　　初期情報記憶部
９３　　　　　車両数記憶部
９５　　　　　クラスタ属性値記憶部
９７　　　　　経路記憶部
９８　　　　　履歴記憶部
９９　　　　　所要時間記憶部
【図１】
2004062363.tif 000003
【図２】
2004062363.tif 000004
【図３】
2004062363.tif 000005
【図４】
2004062363.tif 000006
【図５】
2004062363.tif 000007
【図６】
2004062363.tif 000008
【図７】
2004062363.tif 000009
【図８】
2004062363.tif 000010
【図９】
2004062363.tif 000011
【図１０】
2004062363.tif 000012
【図１１】
2004062363.tif 000013
【図１２】
2004062363.tif 000014
【図１３】
2004062363.tif 000015
【図１４】
2004062363.tif 000016
【図１５】
2004062363.tif 000017
【図１６】
2004062363.tif 000018
【図１７】
2004062363.tif 000019
【図１８】
2004062363.tif 000020
【図１９】
2004062363.tif 000021
【図２０】
2004062363.tif 000022
【図２１】
2004062363.tif 000023
【図２２】
2004062363.tif 000024
【図２３】
2004062363.tif 000025
【図２４】
2004062363.tif 000026
【図２５】
2004062363.tif 000027
【図２６】
2004062363.tif 000028
【図２７】
2004062363.tif 000029
【図２８】
2004062363.tif 000030
【図２９】
2004062363.tif 000031
【図３０】
2004062363.tif 000032
【図３１】
2004062363.tif 000033
【図３２】
2004062363.tif 000034
【図３３】
2004062363.tif 000035
【図３４】
2004062363.tif 000036
【図３５】
2004062363.tif 000037
【図３６】
2004062363.tif 000038
【図３７】
2004062363.tif 000039
【図３８】
2004062363.tif 000040
【図３９】
2004062363.tif 000041
【図４０】
2004062363.tif 000042
【図４１】
2004062363.tif 000043
【図４２】
2004062363.tif 000044
【図４３】
2004062363.tif 000045
【図４４】
2004062363.tif 000046
【図４５】
2004062363.tif 000047