(57)【特許請求の範囲】
【請求項１】
巡回開始時刻が与えられるときに、巡回地点間の所要時間が時間帯により変化することを考慮しつつ、各巡回地点の巡回時刻を算出する機能を持つ巡回計画装置において、
処理開始時刻を巡回開始時刻として指定することにより算出される各巡回地点の巡回時刻を初期時刻とする処理時刻と、該処理時刻の所属する上記時間帯に続く次の上記時間帯との時間差を算出する算出手段と、
処理時刻対応に、巡回開始時刻の変化に対する処理時刻の変化を示す感度を算出する計算手段と、
上記算出手段の算出した時間差を上記計算手段の求めた感度で割り算することで得た値に基づいて、処理時刻の内、次の上記時間帯に最も近いものを特定する特定手段と、
処理終了時刻への未到達を判断するときに、上記特定手段の特定した処理時刻の次の上記時間帯への到達を実現する巡回開始時刻を求めて、それを新たな巡回開始時刻として指定して各巡回地点の巡回時刻の算出を指示するとともに、その指示により算出される該巡回時刻を新たな処理時刻として設定して上記算出手段を起動し、到達を判断するときに、処理終了時刻を新たな巡回開始時刻として指定して各巡回地点の巡回時刻の算出を指示する起動手段と、
上記起動手段の指示に応答して算出される巡回時刻から求まる巡回時間の最小値を検出する検出手段とを備えることを、
特徴とする巡回計画装置。
【請求項２】
請求項１記載の巡回計画装置において、
上記検出手段は、検出する最小巡回時間を実現する巡回開始時刻を特定して出力することを、
特徴とする巡回計画装置。
【請求項３】
巡回開始時刻が与えられるときに、巡回地点間の所要時間が時間帯により変化することを考慮しつつ、各巡回地点の巡回時刻を算出する機能を持つ巡回計画装置を実現するプログラムが記録されるプログラム記録媒体であって、
処理開始時刻を巡回開始時刻として指定することにより算出される各巡回地点の巡回時刻を初期時刻とする処理時刻と、該処理時刻の所属する上記時間帯に続く次の上記時間帯との時間差を算出する算出手段と、
処理時刻対応に、巡回開始時刻の変化に対する処理時刻の変化を示す感度を算出する計算手段と、
上記算出手段の算出した時間差を上記計算手段の求めた感度で割り算することで得た値に基づいて、処理時刻の内、次の上記時間帯に最も近いものを特定する特定手段と、
処理終了時刻への未到達を判断するときに、上記特定手段の特定した処理時刻の次の上記時間帯への到達を実現する巡回開始時刻を求めて、それを新たな巡回開始時刻として指定して各巡回地点の巡回時刻の算出を指示するとともに、その指示により算出される該巡回時刻を新たな処理時刻として設定して上記算出手段を起動し、到達を判断するときに、処理終了時刻を新たな巡回開始時刻として指定して各巡回地点の巡回時刻の算出を指示する起動手段と、
上記起動手段の指示に応答して算出される巡回時刻から求まる巡回時間の最小値を検出する検出手段とを実現するプログラムが記録されることを、
特徴とするプログラム記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、巡回開始地点と巡回終了地点との間の巡回時間を最小のものとする巡回開始時刻を簡単に検出できるようにする巡回計画装置と、それを実現するプログラムが記録されるプログラム記録媒体とに関する。
【０００２】
巡回問題を解くためには、大きなメモリ容量と、長い計算時間が要求される。これから、巡回問題の効率的な解法を構築することで、メモリ容量の削減を図るとともに、計算時間の短縮を図る必要がある。
【０００３】
【従来の技術】
従来では、線形計画法を使って巡回問題を解くという方法を採っていた。すなわち、巡回問題を、目的関数と制約式とで表される線形計画問題に帰着させて解くという方法を採っていた。
【０００４】
例えば、配送順ｐi (i＝１〜ｎ）が与えられる場合に、配送開始地点ｐ0 を出発してから、配送終了地点ｐn に到着するまでの時間を計算するという巡回問題がある。
【０００５】
このような巡回問題では、各地点ｉでの配送車の到着時刻をｘia、出発時刻をｘid、到着指定時刻をｏi 〜ｃi 、停止時間をｓi とし、地点(i-1) から地点ｉまでに移動するのに要する時間をｄi とするならば、地点(i-1) を出発する時刻ｘi-1,d と、地点ｉに到着する時刻ｘiaとの間には、
ｘi-1,d ＋ｄi ≦ｘia
という制約が存在し、地点ｉに到着する時刻ｘiaと、地点ｉを出発する時刻ｘidとの間には、
ｘia＋ｓi ＝ｘid
という制約が存在することで、
ｄi ＋ｓi-1 ≦ｘia−ｘi-1,a 
という制約が存在し、更に、地点ｉに到着する時刻ｘiaには、
ｏi ≦ｘia≦ｃi 
という制約が存在する。
【０００６】
これから、配送終了地点ｐn の到着時刻ｘnaを最も小さくするという巡回問題は、図２１（ｂ）に示す制約式の下に、図２１（ａ）に示す目的関数を解くという線形計画問題に帰着される。
【０００７】
従来では、巡回問題を、このような目的関数と制約式とで表される線形計画問題に帰着させて解くという方法を採っていた。
【０００８】
【発明が解決しようとする課題】
しかしながら、従来技術のように、線形計画法を使って巡回問題を解くという方法を採っていると、大きなメモリ容量を要求されるとともに、長い計算時間が要求されるという問題点があった。
【０００９】
例えば、図２１に示す線形計画問題では、線形計画法に与える行列が、(3n+2)×(n+1) となり、大きなメモリ容量を要求されるとともに、長い計算時間が要求されるのである。
【００１０】
しかも、従来では、巡回問題を解くにあたって、問題が複雑になるのを防ぐために、地点(i-1) から地点ｉへの所要時間ｄi が時間帯で変化しないという前提を用いていた。
【００１１】
このような前提は、実用性を欠くものである。すなわち、実際には、地点間の所要時間は、渋滞やそれによる巡回ルートの変更により時間帯の影響を受けるものであることから、所要時間を一定のものとして巡回問題を解く従来技術に従っていたのでは、実用的な解を得られないのである。
【００１２】
このようなことから、従来技術に従っていると、巡回開始地点と巡回終了地点との間の巡回時間を最小のものとする巡回開始時刻を簡単に検出できないという問題がある。
【００１３】
本発明はかかる事情に鑑みてなされたものであって、巡回開始地点と巡回終了地点との間の巡回時間を最小のものとする巡回開始時刻を簡単に検出できるようにする新たな巡回計画装置の提供と、それを実現するプログラムが記録されるプログラム記録媒体の提供とを目的とする。
【００１４】
【課題を解決するための手段】
図１に本発明の原理構成を図示する。
【００１５】
本発明の巡回計画装置１は、巡回開始地点と巡回終了地点との間の巡回時間を最小のものとする巡回開始時刻を検出するものであって、巡回時刻算出手段２０と、算出手段２１と、計算手段２２と、特定手段２３と、起動手段２４と、検出手段２５とを備える。
【００１６】
この巡回時刻算出手段２０は、巡回開始時刻が与えられるときに、巡回地点間の所要時間が時間帯により変化することを考慮しつつ、各巡回地点の巡回時刻を算出する。算出手段２１は、処理時刻と、処理時刻の所属する時間帯に続く次の時間帯との時間差を算出する。
【００１７】
計算手段２２は、処理時刻対応に、巡回開始時刻の変化に対する処理時刻の変化を示す感度を算出する。特定手段２３は、処理時刻の内、次の時間帯に最も近いものを特定する。起動手段２４は、巡回時刻算出手段２０や算出手段２１を起動する。検出手段２５は、巡回時間の最小値を検出するとともに、それを実現する巡回開始時刻を特定して出力する。
このように構成される本発明の巡回計画装置１では、算出手段２１は、先ず最初に、処理開始の各巡回地点の巡回時刻を処理時刻として、処理時刻と、処理時刻の所属する時間帯に続く次の時間帯との時間差を算出する。
ここで、処理開始の各巡回地点の巡回時刻は、処理開始時刻を巡回開始時刻として指定して巡回時刻算出手段２０を起動することで、巡回時刻算出手段２０により算出されることになる。
【００１８】
この時間差が算出されると、計算手段２２は、算出手段２１の処理した処理時刻対応に、処理時刻の持つ感度を算出し、これを受けて、特定手段２３は、算出手段２１の算出した時間差を計算手段２２の算出した感度で割り算することで得た値に基づいて、処理時刻の内、次の時間帯に最も近いものを特定する。
【００１９】
次の時間帯に最も近い処理時刻が特定されると、起動手段２４は、特定された処理時刻の次の時間帯への到達を実現する巡回開始時刻を求めて、それを新たな巡回開始時刻として指定して、巡回時刻算出手段２０を起動することで、その到達状態を実現する各巡回地点の巡回時刻を得て、それを新たな処理時刻として設定して算出手段２１を起動する。
【００２０】
このようにして、処理時刻が更新されていくことで、処理終了時刻への到達を判断すると、起動手段２４は、処理終了時刻を新たな巡回開始時刻として指定して、巡回時刻算出手段２０を起動することで、その処理終了時刻での各巡回地点の巡回時刻を得る。
【００２１】
そして、検出手段２５は、起動手段２４の起動要求に応答して巡回時刻算出手段２０の算出する巡回開始地点の出発時刻と巡回終了地点の到着時刻とから、巡回開始地点と巡回終了地点との間の巡回時間を算出して、その内の最小のものを検出するとともに、それを実現する巡回開始地点の出発時刻を特定して出力する。
【００２２】
このように、本発明の巡回計画装置１によれば、巡回可能時刻の中から、巡回時間の特性を変化させる巡回開始時刻を特定して、その巡回開始時刻での巡回時間のみを算出することで最小巡回時間を算出する構成を採ることから、最小巡回時間とそれを実現する巡回開始時刻とを簡単に検出できるようになる。
【００２３】
【発明の実施の形態】
以下、実施の形態に従って本発明を詳細に説明する。
【００２４】
図２に、商品の配送計画に適用した本発明の巡回計画装置１の一実施形態例を図示する。
【００２５】
この図に示すように、本発明の巡回計画装置１は、配送時刻決定プログラム５０と、所要時間計算プログラム５１と、条件テーブル５２と、所要時間テーブル５３と、時刻テーブル５４とを備える。
【００２６】
ここで、配送時刻決定プログラム５０や所要時間計算プログラム５１は、媒体から提供されることになる。
【００２７】
この条件テーブル５２は、図３に示すように、配送地点の地点番号と、配送地点に設けられる店舗名と、その店舗への到着指定時刻（これよりも前に到着してはならないという指定時刻と、これよりも後に到着してはならないという指定時刻とからなる）と、その店舗での停止時間とを管理する。以下、前者の到着指定時刻（図中の（自）で示すもの）を“ｏi ”、後者の到着指定時刻（図中の（至）で示すもの）を“ｃi ”、停止時間を“ｓi ”で表す。
【００２８】
また、所要時間テーブル５３は、時間帯別に用意される複数のテーブルで構成されて、図４に示すように、各テーブルに、配送地点間の距離と、その時間帯での配送地点間の所要時間とを管理する。時間帯別にテーブルを用意するのは、時間帯に応じて道路の混み具合が異なることで所要時間が変わるからであって、道路の混み具合に応じて移動ルートを変える場合には、配送地点間の距離についても時間帯で変えて管理することになる。
【００２９】
また、時刻テーブル５４は、所要時間テーブル５３の用意する複数のテーブルの内のどれを使用するのかを決定するために用意されるものであって、図５に示すように、時間帯と、所要時間テーブル５３のテーブル番号との対応関係を管理する。
【００３０】
一方、配送時刻決定プログラム５０は、オペレータから、店舗の配送順序が与えられると、所要時間計算プログラム５１を呼び出しながら、条件テーブル５２の管理する到着指定時刻を充足する配送終了店舗の到着可能時刻を算出するとともに、その到着指定時刻を充足する配送開始店舗の出発可能時刻を算出する。
【００３１】
また、所要時間計算プログラム５１は、配送時刻決定プログラム５０から配送前地点と、配送次地点（配送前地点の次の配送先となる地点）と、配送前地点の出発時刻とを指定して呼び出されると、所要時間テーブル５３の管理データを参照しながら、配送次地点までの所要時間を算出して、それを配送時刻決定プログラム５０に通知する。また、配送時刻決定プログラム５０から配送前地点と、配送次地点と、配送次地点の到着時刻とを指定して呼び出されると、所要時間テーブル５３の管理データを参照しながら、配送前地点までの所要時間を算出して、それを配送時刻決定プログラム５０に通知する。
【００３２】
図６に、所要時間計算プログラム５１の実行する処理フローの一例を図示し、図７ないし図９に、配送時刻決定プログラム５０の実行する処理フローの一例を図示する。次に、これらの処理フローに従って、所要時間計算プログラム５１及び配送時刻決定プログラム５０の実行する処理について詳細に説明する。
【００３３】
最初に、図６の処理フローに従って、所要時間計算プログラム５１の処理について説明する。ここで、この処理フローでは、所要時間テーブル５３の管理する配送地点間の距離については時間帯で変化しないことを想定している。
【００３４】
所要時間計算プログラム５１は、配送時刻決定プログラム５０から配送前地点と、配送次地点と、配送前地点の出発時刻とを指定して呼び出されると、図６の処理フローに示すように、先ず最初に、ステップ１で、時刻テーブル５４を参照することで、その出発時刻の指す所要時間テーブル５３のテーブル番号を特定して、そのテーブル番号の指す所要時間テーブル５３の管理データを参照することで、その出発時刻の指す時間帯での配送前地点と配送次地点との間の距離及び所要時間を入手する。
【００３５】
続いて、ステップ２で、その入手した距離及び所要時間から、参照している所要時間テーブル５３の時間帯内で、配送次地点に到着できるのか否かを判断して、到着できることを判断するときには、ステップ３に進んで、その入手した所要時間を、配送前地点と配送次地点との間の所要時間として求めて処理を終了する。
【００３６】
一方、ステップ２で、参照している所要時間テーブル５３の時間帯内では、配送次地点に到着できないことを判断するときには、ステップ４に進んで、参照している所要時間テーブル５３の時間帯内で走れる距離を求め、続くステップ５で、現在の時刻（初期値は、指定される配送前地点の出発時刻）をその時間帯の最終時刻に進める。
【００３７】
続いて、ステップ６で、配送次地点までの残存距離（初期値は、ステップ１で入手した距離）からステップ４で求めた距離を差し引くことで、配送次地点までの残存距離を得て、続くステップ７で、次の時間帯の所要時間テーブル５３を参照するように設定して、その所要時間テーブル５３の管理データを参照することで、配送前地点と配送次地点との間の距離及び所要時間を入手してから、ステップ２に戻っていく。
【００３８】
そして、ステップ２で、ステップ７で入手した距離及び所要時間から、参照している所要時間テーブル５３の時間帯内で、ステップ６で得た配送次地点までの残存距離を進めるのか否かを判断して、進めないことを判断するときには、ステップ４ないしステップ７の処理を繰り返していき、進めることを判断するときには、ステップ３に進んで、現在の時刻に、配送次地点までの残存距離を進むのに要する時間を加算し、その加算値から配送前地点の出発時刻を差し引くことで配送前地点と配送次地点との間の所要時間を求めて処理を終了する。
【００３９】
すなわち、所要時間計算プログラム５１は、図１０に例示するように、現在の時間帯ｉの速度Ｖi でもって配送次地点Ｂまでの残りの距離ｄを移動したとすると、その到着時刻ｔB は、
ｔB ＝ｔ＋ｄ／Ｖi ＝ｔ＋ｄＴi ／Ｄi 
ｔ  ：現在の時刻
Ｔi ：所要時間テーブル５３から読み出す所要時間
Ｄi ：所要時間テーブル５３から読み出す距離
となり、このｔB が、時間帯ｉから時間帯(i+1) に切り替わる時刻ｂi よりも小さいときには、ｔB から配送前地点Ａの出発時刻ｔA を差し引いた（ｔB −ｔA ）を所要時間とし、大きいときには、時間帯の切替えが起こるので、その切替えまでに進む距離ｌi が、
ｌi ＝（ｂi −ｔ）Ｖi ＝（ｂi −ｔ）Ｄi ／Ｔi 
であることで、次の時間帯(i+1) で走らなければならない距離ｌi+1 が、
ｌi+1 ＝ｄ−ｌi 
となることを考慮して、このｌi+1 を次の時間帯(i+1) の残存距離ｄとして設定し、現在の時刻をｂi に設定していくことを繰り返していくことで、配送前地点と配送次地点との間の所要時間を求めていくのである。
【００４０】
この図６の処理フローでは、所要時間テーブル５３の管理する配送地点間の距離が時間帯で変化しないことを想定したが、時間帯で変化する場合には、残存距離の比率を使って、ステップ６で求める残存距離を決定することになる。すなわち、時間帯ｉでの配送地点間の距離が１０ｋｍで、時間帯(i+1) での配送地点間の距離が１５ｋｍである場合にあって、時間帯ｉの終了時刻まで進んだ距離が６ｋｍで残存距離が４ｋｍである場合には、時間帯(i+1) での残存距離は、１５ｋｍの４割である６ｋｍとして決定するのである。
【００４１】
従って、所要時間計算プログラム５１は、時間帯ｉでの残存距離の比率をｆi とするならば、現在の時間帯ｉの速度Ｖi でもって配送次地点Ｂまでの残りの距離ｆi Ｄi （Ｄi ：所要時間テーブル５３から読み出す配送地点間の距離）を移動したとすると、その到着時刻ｔB は、
ｔB ＝ｔ＋ｆi Ｄi ／Ｖi ＝ｔ＋ｆi Ｄi Ｔi ／Ｄi ＝ｔ＋ｆi Ｔi 
となり、このｔB が、時間帯ｉから時間帯(i+1) に切り替わる時刻ｂi よりも小さいときには、ｔB から配送前地点Ａの出発時刻ｔA を差し引いた（ｔB −ｔA ）を所要時間とし、大きいときには、時間帯の切替えが起こるので、その切替えまでに進む距離ｌi が、
ｌi ＝（ｂi −ｔ）Ｖi ＝（ｂi −ｔ）Ｄi ／Ｔi 
であることで、次の時間帯(i+1) で走らなければならない距離ｌi+1 が、
ｌi+1 ＝ｆi Ｄi −ｌi 
となり、新たな残存距離の比率ｆi+1 は、
ｆi+1 ＝ｌi+1 ／Ｄi ＝ｆi −ｌi ／Ｄi 
となることを考慮して、このｆi+1 を次の時間帯(i+1) の残存距離の比率として設定し、現在の時刻をｂi に設定していくことを繰り返していくことで、配送前地点と配送次地点との間の所要時間を求めていくのである。
【００４２】
このようにして、所要時間計算プログラム５１は、配送時刻決定プログラム５０から配送前地点と、配送次地点と、配送前地点の出発時刻とを指定して呼び出されると、図６の処理フローに従って、配送前地点と配送次地点との間の所要時間を求めていくのである。
【００４３】
この図６の処理フローは、配送前地点の出発時間から時刻を進める形で進める形をとったが、配送次地点の到着時刻から時刻を逆に逆上る形をとることで、配送前地点と配送次地点との間の所要時間を求めることができる。
【００４４】
これから、所要時間計算プログラム５１は、配送時刻決定プログラム５０から配送前地点と、配送次地点と、配送次地点の到着時刻とを指定して呼び出されると、図６の処理フローに従って、配送前地点と配送次地点との間の所要時間を求めていくことになる。
【００４５】
次に、図７ないし図９の処理フローに従って、配送時刻決定プログラム５０の実行する処理について説明する。ここで、この処理フローでは、説明の便宜上、オペレータから、店舗の配送順序として、図３に示した条件テーブル５２の地点番号順の配送順序が指定されることを想定している。
【００４６】
配送時刻決定プログラム５０は、オペレータから、店舗の配送順序（配送地点の順序）を指定して配送可能時刻の決定要求があると、図７ないし図９の処理フローに示すように、先ず最初に、ステップ１で、条件テーブル５２を参照することで、配送開始地点に割り付けられている、これよりも前に到着してはならないという到着指定時刻ｏ1 と、これよりも後に到着してはならないという到着指定時刻ｃ1 とを検索し、変数ｆに到着指定時刻ｏ1 をセットするとともに、変数ｒに到着指定時刻ｃ1 をセットし、更に、処理中の配送地点番号を管理する変数ｉに“２”をセットする初期化処理を行う。後述することから分かるように、変数ｆ，ｒにセットされる時刻は、次の配送地点に対する出発可能時刻として用いられる。
【００４７】
続いて、ステップ２で、全ての配送地点の処理を終了したのか否かを判断して、終了していないことを判断するときには、ステップ３に進んで、変数ｉの指す配送地点（以下、処理配送地点と称する）と、処理配送地点の１つ前の配送地点（以下、配送前地点と称する）と、変数ｆにセットされている配送前地点の出発可能時刻（最も早い出発可能時刻）とを指定して、所要時間計算プログラム５１を起動することで、その出発可能時刻に出発するときの配送前地点と処理配送地点との間の所要時間を求めるとともに、配送前地点と、処理配送地点と、変数ｒにセットされている配送前地点の出発可能時刻（最も遅い出発可能時刻）とを指定して、所要時間計算プログラム５１を起動することで、その出発可能時刻に出発するときの配送前地点と処理配送地点との間の所要時間を求める。
【００４８】
続いて、ステップ４で、変数ｆにセットされている出発可能時刻に、ステップ３で求めた変数ｆにセットされている出発可能時刻に出発する場合の所要時間を加算することで、その出発可能時刻に出発する場合の処理配送地点の到着可能時刻を算出して変数ｆにセットするとともに、変数ｒにセットされている出発可能時刻に、ステップ３で求めた変数ｒにセットされている出発可能時刻に出発する場合の所要時間を加算することで、その出発可能時刻に出発する場合の処理配送地点の到着可能時刻を算出して変数ｒにセットする。
【００４９】
すなわち、図１１に示すように、配送地点(i-1) の最早出発可能時刻をｘ(i-1)df 、最遅出発可能時刻をｘ(i-1)dr とするならば、所要時間計算プログラム５１より得られる所要時間ｄi を使って、次の配送地点ｉの最早到着可能時刻ｘ' iaf 、最遅到着可能時刻ｘ' iar を、
ｘ' iaf ＝ｘ(i-1)df ＋ｄi 
ｘ' iar ＝ｘ(i-1)dr ＋ｄi 
に従って求めるのである。
【００５０】
この求めた処理配送地点の到着可能時刻は、条件テーブル５２に格納されている、これよりも前に到着してはならないという処理配送地点の到着指定時刻ｏi と、これよりも後に到着してはならないという処理配送地点の到着指定時刻ｃi とを充足しているとは限らないので、あくまでも仮のものである。
【００５１】
そこで、続いて、ステップ５で、条件テーブル５２を参照することで、処理配送地点に割り付けられている、これよりも前に到着してはならないという処理配送地点の到着指定時刻ｏi と、これよりも後に到着してはならないという処理配送地点の到着指定時刻ｃi とを検索し、これを使って、ステップ４で求めた処理配送地点の到着可能時刻を修正する処理を行う。
【００５２】
この修正処理は、図１２及び図１３に示す形態で行う。
【００５３】
すなわち、図１２（ａ）に示すように、「ｏi ＞ｘ' iaf ，ｘ' iar 」の場合には、到着指定時刻よりも早く到着してしまうので、処理配送地点の到着可能時刻ｘiaf ，ｘiar を、
ｘiaf ＝ｘ' iar ＋ωi ，ｘiar ＝ｘ' iar ＋ωi 
但し、ωi は到着指定時刻ｏi までの待ち時間
に従って求める。すなわち、制約を充足するようにと、ωi だけ待って時刻ｏi に到着したことにする。
【００５４】
また、図１２（ｂ）に示すように、「ｃi ＜ｘ' iaf ，ｘ' iar 」の場合には、到着指定時刻よりも遅く到着してしまい制約を充足できないので、制約違反が最も少なくなるようにと、処理配送地点の到着可能時刻ｘiaf ，ｘiar を、
ｘiaf ＝ｘ' iaf ，ｘiar ＝ｘ' iaf 
に従って求める。すなわち、ｘ' iaf を到着時刻とする。
【００５５】
また、図１２（ｃ）に示すように、「ｏi ＞ｘ' iaf ，ｏi ＜ｘ' iar ＜ｃi 」の場合には、ｘ' iaf のみが制約違反となるので、処理配送地点の到着可能時刻ｘiaf ，ｘiar を、
ｘiaf ＝ｏi ，ｘiar ＝ｘ' iar 
に従って求める。すなわち、制約を充足するようにと、最早到着可能時刻ｘ' iaf を時刻ｏi に修正する。
【００５６】
また、図１３（ｄ）に示すように、「ｏi ＜ｘ' iaf ＜ｃi ，ｃi ＜ｘ' iar 」の場合には、ｘ' iar のみが制約違反となるので、処理配送地点の到着可能時刻ｘiaf ，ｘiar を、
ｘiaf ＝ｘ' iaf ，ｘiar ＝ｃi 
に従って求める。すなわち、制約を充足するようにと、最遅到着可能時刻ｘ' iar を時刻ｃi に修正する。
【００５７】
また、図１３（ｅ）に示すように、「ｏi ＞ｘ' iaf ，ｃi ＜ｘ' iar 」の場合には、ｘ' iaf とｘ' iar が制約違反となるので、処理配送地点の到着可能時刻ｘiaf ，ｘiar を、
ｘiaf ＝ｏi ，ｘiar ＝ｃi 
に従って求める。すなわち、制約を充足するようにと、最早到着可能時刻ｘ' iaf を時刻ｏi に修正し、最遅到着可能時刻ｘ' iar を時刻ｃi に修正する。
【００５８】
また、図１３（ｆ）に示すように、「ｏi ＜ｘ' iaf ，ｘ' iar ＜ｃi 」の場合には、制約を充足しているので、処理配送地点の到着可能時刻ｘiaf ，ｘiar を、
ｘiaf ＝ｘ' iaf ，ｘiar ＝ｘ' iar 
に従って求める。すなわち、ステップ４で求めた到着可能時刻ｘ' iaf ，ｘ' iar をそのまま用いる。
【００５９】
これから、ステップ５では、図９に示す詳細な処理フローに示すように、先ず最初に、ステップ５０で、「ｏi ＞ｘ' iar 」の状態であるのか否かを判断して、「ｏi ＞ｘ' iar 」の状態であることを判断するとき、すなわち、図１２（ａ）に示した状態にあることを判断するときには、ステップ５１に進んで、
ωi ＝ｏi −ｘ' iar 
に従って、待ち時間ωi を求めて、それを記録するとともに、変数ｆにセットされている処理配送地点の最早到着可能時刻を時刻ｏi に修正し、、変数ｒにセットされている処理配送地点の最遅到着可能時刻を時刻ｏi に修正する。
【００６０】
一方、ステップ５０で、「ｏi ＞ｘ' iar 」の状態にないことを判断するときには、ステップ５２に進んで、待ち時間がないことを記録してから、続くステップ５３で、「ｃi ＜ｘ' iaf 」の状態であるのか否かを判断して、「ｃi ＜ｘ' iaf 」の状態であることを判断するとき、すなわち、図１２（ｂ）に示した状態にあることを判断するときには、ステップ５４に進んで、変数ｒにセットされている処理配送地点の最遅到着可能時刻を、変数ｆにセットされている処理配送地点の最早到着可能時刻に修正する。
【００６１】
一方、ステップ５３で、「ｃi ＜ｘ' iaf 」の状態にないことを判断するときには、ステップ５５に進んで、「ｏi ＞ｘ' iaf 」の状態であるのか否かを判断して、「ｏi ＞ｘ' iaf 」の状態であることを判断するとき、すなわち、図１２（ｃ）や図１３（ｅ）に示した状態にあることを判断するときには、ステップ５６に進んで、変数ｆにセットされている処理配送地点の最早到着可能時刻を時刻ｏi に修正し、「ｏi ＞ｘ' iaf 」の状態にないことを判断するときには、このステップ５６の処理を省略する。
【００６２】
続いて、ステップ５７で、「ｘ' iar ＞ｃi 」の状態であるのか否かを判断して、「ｘ' iar ＞ｃi 」の状態であることを判断するとき、すなわち、図１３（ｄ）や図１３（ｅ）に示した状態にあることを判断するときには、ステップ５８に進んで、変数ｒにセットされている処理配送地点の最遅到着可能時刻を時刻ｃi に修正し、「ｘ' iar ＞ｃi 」の状態にないことを判断するときには、このステップ５８の処理を省略する。
【００６３】
このようにして、ステップ４で、処理配送地点の仮の最早到着可能時刻／最遅到着可能時刻を求めると、ステップ５で、処理配送地点の到着指定時刻ｏi , ｃi を使って、この仮の最早到着可能時刻／最遅到着可能時刻を修正することで、処理配送地点の到着指定時刻を可能な限り充足する処理配送地点の最早到着可能時刻／最遅到着可能時刻を求めるのである。
【００６４】
ステップ５での修正処理を終了すると、続いて、ステップ６で、条件テーブル５２を参照することで、処理配送地点に割り付けられている停止時間ｓi を検索し、変数ｆにセットされている最早到着可能時刻に、この検索した停止時間ｓi を加算することで、処理配送地点の最早出発可能時刻を算出して変数ｆにセットするとともに、変数ｒにセットされている最遅到着可能時刻に、この検索した停止時間ｓi を加算することで、処理配送地点の最遅出発可能時刻を算出して変数ｒにセットする。
【００６５】
続いて、ステップ７で、変数ｉの値を１つインクリメントすることで、それまで処理配送地点としていたものを新たに配送前地点とし、その配送前地点の次の配送先となる配送地点を新たな処理配送地点として設定してから、ステップ２に戻っていって、処理配送地点が配送終了地点に到達するまで、ステップ３ないしステップ７の処理を繰り返していく。
【００６６】
そして、ステップ２で、処理配送地点が配送終了地点に到達することを判断すると、ステップ１ないしステップ７で示される前半の処理を終了することになるが、このときには、配送終了地点の停止時間がゼロであると想定していることに対応して、変数ｆには、配送終了地点の最早到着可能時刻が格納され、変数ｒには、配送終了地点の最遅到着可能時刻が格納されることになる。
【００６７】
このように、配送時刻決定プログラム５０は、図７に示す処理フローのステップ１ないしステップ７を実行することで、配送前地点と処理配送地点との間の距離や所要時間が時間帯で変化することを考慮しつつ、配送前地点の出発可能時刻と、配送前地点と処理配送地点との間の所要時間と、処理配送地点の到着指定時刻とから、その到着指定時刻の条件を可能な限り充足する処理配送地点の到着可能時刻を求め、それに処理配送地点の停止時間を加算することで処理配送地点の出発可能時刻を求めて、処理配送地点を次の配送地点に更新していくことを繰り返していくことで、配送終了地点の到着可能時刻を求めていくのである。
【００６８】
図１４及び図１５に、この処理過程の一例を図示する。図中、横軸は時刻、縦軸は配送開始地点から配送終了地点までの距離である。この図では、配送地点として、αという到着指定時刻を持つ配送地点と、βという到着指定時刻を持つ配送地点と、γという到着指定時刻を持つ配送地点と、δという到着指定時刻を持つ配送地点という４つを想定している。なお、この図では、処理途中で求まる各配送地点の到着可能時刻と出発可能時刻を図示してあるが、これらは、配送終了地点の到着可能時刻を求めていく途中の修正処理に従って意味のないものとなることがあるので、実際には記録してはいない。
【００６９】
ステップ２で、処理配送地点が配送終了地点に到達することが判断されることで、配送終了地点の最早到着可能時刻／最遅到着可能時刻（配送終了地点の最早出発可能時刻／最遅出発可能時刻も示している）が求まると、配送時刻決定プログラム５０は、図８に示す処理フローのステップ８ないしステップ１４の処理を実行することで、その配送終了地点の最早到着可能時刻／最遅到着可能時刻を実現する配送開始地点の最早出発可能時刻／最遅出発可能時刻を算出する。
【００７０】
すなわち、先ず最初に、ステップ８で、処理中の配送地点番号を管理する変数ｉに配送終了地点の番号をセットする初期化処理を行う。続いて、ステップ９で、変数ｆにセットされている最早出発可能時刻を読み出して変数ｘidf に記録するとともに、変数ｒにセットされている最遅出発可能時刻を読み出して変数ｘidr に記録する。この記録値は、全配送地点の到着指定時刻を可能な限り充足する正確な値である。
【００７１】
続いて、ステップ１０で、条件テーブル５２を参照することで、変数ｉの指す配送地点（以下、処理配送地点と称する）に割り付けられている停止時間ｓi を検索し、変数ｆにセットされている最早出発可能時刻から、この検索した停止時間ｓi を引算することで、処理配送地点の最早到着可能時刻を算出して変数ｘiaf に記録するとともに、変数ｒにセットされている最遅出発可能時刻から、この検索した停止時間ｓi を引算することで、処理配送地点の最遅到着可能時刻を算出して変数ｘiar に記録する。この記録値は、全配送地点の到着指定時刻を可能な限り充足する正確な値である。
【００７２】
続いて、ステップ１１で、変数ｉの指す処理配送地点が配送開始地点を表示しているのか否かを判断して、表示していることを判断するときは、処理を終了し、表示していないことを判断するときには、ステップ１２に進んで、処理配送地点と、処理配送地点の１つ前の配送地点（以下、配送前地点と称する）と、処理配送地点の最早到着可能時刻から処理配送地点の待ち時間（上述のωi ）を差し引くことで求まる時刻とを指定して、所要時間計算プログラム５１を起動することで、その到着可能時刻に到着するときの配送前地点と処理配送地点との間の所要時間を求めるとともに、配送前地点と、処理配送地点と、処理配送地点の最遅到着可能時刻から処理配送地点の待ち時間（上述のωi ）を差し引くことで求まる時刻とを指定して、所要時間計算プログラム５１を起動することで、その到着可能時刻に到着するときの配送前地点と処理配送地点との間の所要時間を求める。
【００７３】
続いて、ステップ１３で、変数ｆにセットされている最早出発可能時刻から、記録してある処理配送地点の待ち時間（上述のωi ）と、条件テーブル５２から読み出した処理配送地点の停止時間ｓi と、ステップ１２で求めた所要時間との合計値を引算することで、配送前地点の最早出発可能時刻を算出して変数ｆにセットするとともに、変数ｒにセットされている最遅出発可能時刻から、記録してある処理配送地点の待ち時間（上述のωi ）と、条件テーブル５２から読み出した処理配送地点の停止時間ｓi と、ステップ１２で求めた所要時間との合計値を引算することで、配送前地点の最遅出発可能時刻を算出して変数ｒにセットする。
【００７４】
続いて、ステップ１４で、変数ｉの値を１つデクリメントしてからステップ９に戻っていって、変数ｉの指す処理配送地点が配送開始地点に到達するまで、ステップ９ないしステップ１４の処理を繰り返していく。
【００７５】
このように、配送時刻決定プログラム５０は、図８に示す処理フローのステップ８ないしステップ１４を実行することで、図７に示す処理フローのステップ１ないしステップ７で求めた配送終了地点の最早到着可能時刻／最遅到着可能時刻を実現する配送開始地点の最早出発可能時刻／最遅出発可能時刻を算出していくとともに、それ以外の配送地点の最早出発可能時刻／最遅出発可能時刻を算出していくことになる。
【００７６】
このようにして、配送時刻決定プログラム５０は、オペレータから、店舗の配送順序が与えられると、所要時間計算プログラム５１を呼び出しながら、条件テーブル５２の管理する到着指定時刻を充足する配送終了地点の最早到着可能時刻／最遅到着可能時刻を算出するとともに、その到着指定時刻を充足する配送開始地点の最早出発可能時刻／最遅出発可能時刻を算出するのである。
【００７７】
この図７ないし図９の処理フローでは、各配送地点に、これよりも前に到着してはならないという到着指定時刻と、これよりも後に到着してはならないという到着指定時刻とがあることを想定していた。
【００７８】
このような到着指定時刻の制限がない場合には、配送時刻決定プログラム５０は、配送終了地点の到着時刻が与えられると、所要時間計算プログラム５１を起動していくだけで、配送地点間の距離や所要時間が時間帯で変化することを考慮した配送開始地点の出発時刻を算出できるとともに、それ以外の配送地点の出発時刻を算出できることになる。このような巡回計画装置１は、例えば、カーナビに実装すると極めて有用である。
【００７９】
図１６に、これを実現するために配送時刻決定プログラム５０の実行する処理フローの一例を図示する。
【００８０】
配送時刻決定プログラム５０は、この図１６の処理フローに示すように、配送終了地点の到着時刻が与えられると、先ず最初に、ステップ１で、変数ｔに、その到着時刻をセットするとともに、変数ｉに、その配送終了地点の番号をセットする初期化を行う。続いて、ステップ２で、変数ｔにセットされる時刻を記録することで、変数ｉの指す配送地点の通過時刻を記録する。
【００８１】
続いて、ステップ３で、変数ｉの指す配送地点（以下、処理配送地点と称する）が配送開始地点を表示しているのか否かを判断して、表示していることを判断するときは、処理を終了し、表示していないことを判断するときには、ステップ４に進んで、処理配送地点と、処理配送地点の１つ前の配送地点（以下、配送前地点と称する）と、変数ｔにセットされている処理配送地点の到着時刻とを指定して、所要時間計算プログラム５１を起動することで、その到着時間に到着するときの配送前地点と処理配送地点との間の所要時間を求める。
【００８２】
続いて、ステップ５で、変数ｔにセットされている出発時刻から、ステップ５で求めた所要時間を引算することで、配送前地点の出発時刻を算出して変数ｔにセットする。
【００８３】
続いて、ステップ６で、変数ｉの値を１つデクリメントしてからステップ２に戻っていって、変数ｉの指す処理配送地点が配送開始地点に到達するまで、ステップ２ないしステップ６の処理を繰り返していくのである。
【００８４】
このようにして、配送時刻決定プログラム５０は、この図１６の処理フローを実行することで、オペレータから、配送終了地点の到着時刻が与えられると、配送地点間の距離や所要時間が時間帯で変化することを考慮した配送開始地点の出発時刻を算出できるとともに、それ以外の配送地点の出発時刻を算出できることになる。なお、この図１６の処理フローでは、各配送地点での停止時間を考慮しないものを示したが、考慮することも当然のことながら実現可能である。
【００８５】
勿論、配送時刻決定プログラム５０は、図７ないし図９の処理フローに従って、配送開始地点の最早出発可能時刻／最遅出発可能時刻が求められているときに、出発時刻がその出発可能時間帯の中で与えられれば、この処理フローの前半の処理（ステップ１〜ステップ７）を実行することで、配送地点間の距離や所要時間が時間帯で変化することを考慮した各配送地点の到着時刻を算出できることについては言うまでもないことである。
【００８６】
なお、各配送地点の到着指定時刻が存在しない場合には、図７ないし図９の処理フローに従うまでもなく、図１６の処理フローと同様の処理に従って、オペレータから、配送開始地点の出発時刻が与えられると、配送地点間の距離や所要時間が時間帯で変化することを考慮した配送終了地点の到着時刻を算出できるとともに、それ以外の配送地点の到着時刻を算出できるものである。
【００８７】
更に、配送時刻決定プログラム５０は、図７ないし図９の処理フローの実行により得られた配送可能時刻の中から、配送開始地点から配送終了地点までの配送時間が最も短くなる配送時刻を簡単に検出できる機能を持っている。
【００８８】
すなわち、図１７に示すように、このようにして算出した配送可能時刻の中からは、無限に近い配送時刻の選択が可能となるが、それらの配送時刻の配送時間（配送開始地点から配送終了地点までの所要時間）には極小値がある。配送時刻決定プログラム５０は、算出した配送可能時刻の中から、この最小の配送時間を実現する配送時刻を簡単に求める機能を持っているのである。
【００８９】
この最小配送時間を実現する配送時刻の特定処理は、配送時間の特性の変化する原因が、配送時刻の通過する時間帯（所要時間テーブル５３の区画する時間帯）の変化によるものであるという点に着目して実行する。
【００９０】
具体的に説明すると、図１８（ａ）に示すように、配送開始地点から配送終了地点に至る配送時刻の通過する時間帯が、それまでのものと異なるものになると、図１８（ｂ）に示すように、配送時間の傾きが異なるものとなる。これから、配送時刻決定プログラム５０は、そのような状態の起こる配送時刻を検出して、その配送時刻での配送時間のみを算出し、その中の最小値を検出することで、最小配送時間を実現する配送時刻を簡単に求めるという構成を採っている。
【００９１】
図１９に、最小配送時間を検出するために実行する配送時刻決定プログラム５０の処理フローの一実施形態例を図示する。次に、この処理フローに従って、最小配送時間の検出処理について説明する。
【００９２】
配送時刻決定プログラム５０は、最小配送時間の検出要求があると、図１９の処理フローに示すように、先ず最初に、ステップ１で、配送開始時刻を、図７ないし図９の処理フローで求めた配送開始地点の最早出発可能時刻に設定する。続いて、ステップ２で、配送開始時刻が、図７ないし図９の処理フローで求めた配送開始地点の最遅出発可能時刻を超えるならば、配送開始時刻をその最遅出発可能時刻に設定する。
【００９３】
続いて、ステップ３で、設定した配送開始時刻を指定して、図７ないし図９の処理フローの前半の処理（ステップ１ないしステップ７）を実行することで、各配送地点の配送時刻を算出するとともに、算出した配送終了地点の配送時刻と、設定した配送開始時刻との引算を行うことで、その配送開始時刻での配送時間を算出して、その配送時間がこれまでに求めたものよりも小さいときには、配送開始時刻とともに記録する。
【００９４】
続いて、ステップ４で、設定した配送開始時刻が、図７ないし図９の処理フローで求めた配送開始地点の最遅出発可能時刻に到達したのか否かを判断して、到達したことを判断するときには、ステップ３で記録した最小配送時間と、そのときの配送開始時刻とを出力して処理を終了する。
【００９５】
一方、ステップ４で、設定した配送開始時刻が配送開始地点の最遅出発可能時刻に到達していないことを判断するときには、ステップ５に進んで、ステップ２で求めた各配送地点の配送時刻の感度を求める。このとき求める感度とは、例えば配送開始時刻を１分遅らせたときに、各配送地点の配送時刻がどの程度遅れるのかを示すものである。
【００９６】
この感度は、例えば配送開始時刻を１分遅らせる形で設定して、それを指定して図７ないし図９の処理フローの前半の処理（ステップ１ないしステップ７）を実行し、その結果求まる各配送地点の配送時刻と、１分遅らせないで求めたステップ３での各配送地点の配送時刻との差分値を求めることでも算出可能であるが、簡単な比率演算により求めることも可能である。
【００９７】
すなわち、図２０に示すように、時間帯１だけの場合の配送地点Ａから配送地点Ｂまでの所要時間をＴ1 、時間帯２だけの場合の配送地点Ａから配送地点Ｂまでの所要時間をＴ2 とするならば、配送開始時刻ｔ1 がΔｔ1 だけ遅くなり、配送終了時刻ｔ2 がこれに応じてΔｔ2 だけ遅くなるときには、
Δｔ2 ＝Δｔ1 ×Ｔ2 ／Ｔ1 
という関係式が成立するので、この関係式を使うことで簡単に求めることができる。なお、図中のｆは、配送開始時刻ｔ1 で出発した場合の時間帯切替え時の残存距離の比率、ｆ’は、配送開始時刻ｔ1 ' ( ＝ｔ1 ＋Δｔ1 ) で出発した場合の時間帯切替え時の残存距離の比率である。また、３つ以上の時間帯を通過するときには、Ｔ2 に代わり最後の時間帯の所要時間が入ることになる。
【００９８】
ステップ５で、各配送地点の配送時刻の感度を求めると、続いて、ステップ６で、各配送地点の配送時刻と、それが属する時間帯の次の時間帯との時間差を求めて、それをステップ５で求めた感度で割算することで、各配送地点の配送時刻が次の時間帯に到達するまでの時間を求める。例えば、配送地点Ａの配送時刻の感度が“０.6”であるときには、配送開始地点の配送時刻と次の時間帯との時間差が６０分で、配送地点Ａの配送時刻と次の時間帯との時間差が３０分であるときには、配送地点Ａの配送時刻が次の時間帯に到達するには、配送開始地点の時間差に換算して５０分となるというように求めるのである。
【００９９】
続いて、ステップ７で、ステップ６で求めた感度で補正した時間差の中の最も小さいものを特定して、それを配送開始時刻に加算することで配送開始時刻を更新して、ステップ２に戻っていく。すなわち、どれかの配送地点の配送時刻が次の時間帯に到達することになる配送開始時刻を求めて、ステップ２に戻っていくのである。
【０１００】
このようにして、配送時刻決定プログラム５０は、この図１９の処理フローを実行することで、配送可能時刻の中から、配送時間の特性を変化させる配送開始時刻を特定して、その配送開始時刻での配送時間のみを算出することで最小配送時間を検出できるとともに、それを実現する配送開始時刻を検出できるようになる。
【０１０１】
【発明の効果】
以上説明したように、本発明の巡回計画装置によれば、巡回可能時刻の中から、巡回時間の特性を変化させる巡回開始時刻を特定して、その巡回開始時刻での巡回時間のみを算出することで最小巡回時間を算出する構成を採ることから、最小巡回時間とそれを実現する巡回開始時刻とを簡単に検出できるようになる。
【図面の簡単な説明】
【図１】本発明の原理構成図である。
【図２】本発明の一実施形態例である。
【図３】条件テーブルの説明図である。
【図４】所要時間テーブルの説明図である。
【図５】時刻テーブルの説明図である。
【図６】所要時間計算プログラムの実行する処理フローである。
【図７】配送時刻決定プログラムの実行する処理フローである。
【図８】配送時刻決定プログラムの実行する処理フローである。
【図９】配送時刻決定プログラムの実行する処理フローである。
【図１０】所要時間計算プログラムの処理説明図である。
【図１１】配送時刻決定プログラムの処理説明図である。
【図１２】配送時刻決定プログラムの処理説明図である。
【図１３】配送時刻決定プログラムの処理説明図である。
【図１４】配送時刻決定プログラムの実行する処理の説明図である。
【図１５】配送時刻決定プログラムの実行する処理の説明図である。
【図１６】配送時刻決定プログラムの実行する処理フローである。
【図１７】配送時刻の説明図である。
【図１８】配送時間の説明図である。
【図１９】配送時刻決定プログラムの実行する処理フローの一実施形態例である。
【図２０】感度の導出の説明図である。
【図２１】線形計画問題の説明図である。
【符号の説明】
１    巡回計画装置
２０  巡回時刻算出手段
２１  算出手段
２２  計算手段
２３  特定手段
２４  起動手段
２５  検出手段
【図１】
0003908644.tif 000002
【図２】
0003908644.tif 000003
【図３】
0003908644.tif 000004
【図４】
0003908644.tif 000005
【図５】
0003908644.tif 000006
【図６】
0003908644.tif 000007
【図７】
0003908644.tif 000008
【図８】
0003908644.tif 000009
【図９】
0003908644.tif 000010
【図１０】
0003908644.tif 000011
【図１１】
0003908644.tif 000012
【図１２】
0003908644.tif 000013
【図１３】
0003908644.tif 000014
【図１４】
0003908644.tif 000015
【図１５】
0003908644.tif 000016
【図１６】
0003908644.tif 000017
【図１７】
0003908644.tif 000018
【図１８】
0003908644.tif 000019
【図１９】
0003908644.tif 000020
【図２０】
0003908644.tif 000021
【図２１】
0003908644.tif 000022