(57)【要約】【課題】  時間指定配達にも対応し、効率的な集配ルートを設定する。【解決手段】  集配ルート設定装置１は、集配情報テーブル２から到着時間指定有の集配物に関する集配情報を抽出し（ステップＳ１）、抽出された集配情報と道路交通情報３および地図情報４を用いて、到着時間指定有の集配物が指定された時間前に到着可能なルートを検索し、初期ルートを設定する（ステップＳ２）。次に、集配情報テーブル２から到着時間指定無の集配物に関する集配情報を抽出し（ステップＳ３）、抽出された集配情報と道路交通情報３および地図情報４を用いて、初期ルート上の各区間の余裕時間を算出し、余裕時間内に配送可能な到着時間指定無の集配物を検索し、検出された集配物の集配を初期ルートに組込み、初期ルートを設定する（ステップＳ４）。【選択図】  図１
2005280972.tif 000002
【特許請求の範囲】
【請求項１】
交通情報および地図情報を取得して最適な集配ルートを設定する集配ルート設定方法において、
時間指定抽出手段が、目的地、到着時間指定の有無および到着時間指定有の場合の到着時間を含む集配情報を集配物に関連づけた集配情報テーブルを格納した集配情報記憶手段から前記到着時間指定有の前記集配情報を抽出し、
初期ルート検索手段が、抽出された前記到着時間指定有の前記集配情報と前記交通情報と前記地図情報を用いて、前記到着時間指定有の前記集配物が指定された時間前に前記目的地に到着可能なルートを検索して初期ルートを設定し、
時間指定無抽出手段が、前記集配情報記憶手段から前記到着時間指定無の前記集配情報を抽出し、
時間指定無割当て手段が、前記初期ルート上の各区間の余裕時間を算出し、前記余裕時間内に配送可能な前記到着時間指定無の前記集配物を検索し、検出された前記到着時間指定無の前記集配物の集配を前記初期ルートに組込み、集配ルートを設定する、
手順を有することを特徴とする集配ルート設定方法。
【請求項２】
前記初期ルートを検索する手順は、
所定の仮余裕時間を設定し、前記到着時間指定有の場合に指定された指定到着時間より前記仮余裕時間前の時点から前記指定到着時間までの間に到着可能な前記集配物を検索することを特徴とする請求項１記載の集配ルート設定方法。
【請求項３】
前記時間指定無割当て手段が前記初期ルート上の余裕時間に前記到着時間指定無の前記集配物の集配を前記初期ルートに組込む手順は、
前記初期ルートの任意の区間の前記到着時間指定有の前記集配物に関する到着予定時間を算出し、前記到着予定時間より新たに前記初期ルートの任意の区間の集配先となる前記到着時間指定有の前記集配物に関する余裕度を算出して前記任意の区間に関する前記到着時間指定無の前記集配物の組込みを行うことを特徴とする請求項１記載の集配ルート設定方法。
【請求項４】
前記時間指定無割当て手段が、前記初期ルート上の余裕時間に前記到着時間指定無の前記集配物の集配を前記初期ルートに組込む手順は、
前記初期ルートの任意の区間の前記到着時間指定有の前記集配物に関する到着予定時間を算出し、前記到着予定時間より新たに前記初期ルートの任意の区間の集配先となる前記到着時間指定有の前記集配物に関する余裕度を算出して、前記余裕度が予め設定された余裕度閾値を超えない場合は、前記初期ルートの前記任意の区間についての前記到着時間指定無の前記集配物の組込み処理を行わないことを特徴とする請求項１記載の集配ルート設定方法。
【請求項５】
交通情報および地図情報を取得して最適な集配ルートの設定処理を行う集配ルート設定プログラムにおいて、
コンピュータを、
目的地、到着時間指定の有無および到着時間指定有の場合の到着時間を含む集配情報を集配物に関連づけた集配情報テーブルを格納した集配情報記憶手段から前記到着時間指定有の前記集配情報を抽出する時間指定抽出手段と、
抽出された前記到着時間指定有の前記集配情報と前記交通情報と前記地図情報を用いて、前記到着時間指定有の前記集配物が指定された時間前に前記目的地に到着可能なルートを検索して初期ルートを設定する初期ルート検索手段と、
前記集配情報記憶手段から前記到着時間指定無の前記集配情報を抽出する時間指定無抽出手段と、
前記初期ルート上の各区間の余裕時間を算出し、前記余裕時間内に配送可能な前記到着時間指定無の前記集配物の有無を検索し、検出された前記到着時間指定無の前記集配物の集配を前記初期ルートに組込み、集配ルートを作成する時間指定無割当て手段と、
して機能させることを特徴とする集配ルート設定プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は集配ルート設定方法および集配ルート設定プログラムに関し、特に交通情報および地図情報を取得して最適な集配ルートを設定する集配ルート設定方法および集配ルート設定プログラムに関する。
【背景技術】
【０００２】
従来、集配センターに集荷された複数の配達物をそれぞれの配送先に配送する際、予め交通情報や地図情報を取得し、これらの情報に基づいて効率的な配送ルートを算出していた。一般に、配送ルートの設定は、集配センターが管轄する地域内を固定的なエリアで区切り、そこへ配送車を割当て、そのエリア内に点在する複数の配送先を経由する配達ルートを見つけ出し、配達ルートの組み合わせを比較し、最適な組み合わせを設定する。たとえば、配達ルートの組み合わせについて距離を算出し、その中から最短の配達ルートを見つけ出す。また、複数の場所を回って荷物を収集する場合についても、同様にして最適な収集ルートを設定することができる。
【０００３】
このような集配ルート設定の際には、多くのルートの組み合わせから最適な組み合わせが求められる。しかしながら、ルートの組み合わせは膨大にあることから、最適なルートの決定は容易ではない。そこで、遺伝子アルゴリズムを用いるなどして、最適な配送ルートを決定する方法が提案されている（たとえば、特許文献１参照）。
【０００４】
このような配送ルート設定方法では、検討対象の配送車へ新たな配送先を割当てる際に、時間的な制約条件または空間的な制約条件を満たす範囲で、所定の経路評価が最適になるような巡回順序決定が行われる。
【特許文献１】特開平１０−５５３４９号公報（段落番号〔００３５〕〜〔００５３〕、図３）
【発明の開示】
【発明が解決しようとする課題】
【０００５】
しかし、従来の集配ルート設定方法では、時間指定配達に適応する集配ルートを設定することが難しいという問題点があった。
近年増加傾向にある時間指定配達サービスでは、予め決められた配達時間を含む所定の範囲内、または、指定された配達時間帯内に配達物を届ける必要がある。
【０００６】
しかしながら、従来の全配送物を対象にして配達ルートを設定し、そのルートの組み合わせを比較して最適なルートを選択する配達ルート設定方法では、時間指定配達の配達物とそうでない配達物が混在する場合には、ルートを決定するための組み合わせが多くなり、計算時間がかかるという問題点がある。たとえば、配達ルートの組み合わせごとに、従来の処理に加えて、時間指定配達の有無を調べ、ある場合には配達予定時間が範囲内かを判定する必要がある。
【０００７】
また、従来の集配ルート設定方法では、配送エリアを固定しているため、エリアごとの偏りが発生し、必ずしも効率的な配送を実施することができていないという問題点がある。たとえば、個人の家に配達する宅配では、日ごとに配送物、配送先が異なる。このような配達業務では、配送エリアを予め固定することにより、エリアごとに偏りが発生してしまう。特に、時間指定配達の配達物とそうでない配達物が混在する場合、配送エリアを固定的にしたままでは、効率的なルートを設定することがより難しくなるという問題点がある。
【０００８】
このように、従来の集配ルート設定方法では、時間指定配達の配送物とそうでない配送物とが混在するような場合、配達ルートを決定するまでの計算時間が多大となるばかりでなく、効率的な配送ルートを設定することが難しかった。
【０００９】
本発明はこのような点に鑑みてなされたものであり、時間指定配達にも対応し、効率的な集配ルートを設定することが可能な集配ルート設定方法および集配ルート設定プログラムを提供することを目的とする。
【課題を解決するための手段】
【００１０】
本発明では上記問題を解決するために、図１に示すような集配ルート設定装置１の集配ルート設定方法が提供される。
集配ルート設定装置１は、集配情報テーブル２、道路交通情報３および地図情報４を用いて集配情報テーブル２に登録された集配物の集配ルートを設定する。
【００１１】
集配情報テーブル２は、集配物を集配する目的地、集配物の到着時間指定の有無と到着時間指定有の場合の到着時間などを含む集配情報が集配物に関連付けられている。道路交通情報３および地図情報４は、道路状況に関する情報、集配車を移動する道路地図情報および地図上の任意の地点から任意の地点への移動に要する距離や所要時間情報を有する。
【００１２】
集配ルート設定装置１は、このような情報に基づき、時間指定抽出手段で、集配情報テーブル２から到着時間指定有の集配物に関する集配情報を抽出する時間指定抽出処理を行う（ステップＳ１）。集配情報テーブル２を順に検索し、到着時間指定有が登録された集配情報をピックアップする。次に、初期ルート検索手段が、抽出された集配情報と道路交通情報３および地図情報４を用いて、到着時間指定有の集配物が指定された時間前に到着可能なルートを検索し、初期ルートを設定する初期ルート検索処理を行う（ステップＳ２）。次に、時間指定無抽出手段が、集配情報テーブル２から到着時間指定無の集配物に関する集配情報を抽出する時間指定無抽出処理を行う（ステップＳ３）。抽出処理は、ステップＳ１と同様に行う。次に、時間指定無割当て手段が、抽出された集配情報と道路交通情報３および地図情報４を用いて、初期ルート上の各区間の余裕時間を算出し、余裕時間内に配送可能な到着時間指定無の集配物を検索し、検出された集配物の集配を初期ルートに組込み、集配ルートを設定する時間指定無割当て処理を行う（ステップＳ４）。初期ルート設定では、指定された到着時間より前に到着するようにルート設定が行われ、初期ルートにおける指定された到着時間と実際の到着時間の差が余裕時間になる。そこで、初期ルートの途中（到着時間指定有の集配物の目的地から次の目的地までの間）に、集配が可能な到着時間指定無の集配物を検索し、検出された集配物を集配するルートを組込み、集配ルートを設定する。
【００１３】
このような集配ルート設定方法によれば、集配情報テーブル２を参照し、到着時間指定有の集配物の集配情報が抽出され、道路交通情報３および地図情報４を用いて、指定された到着時間前に目的地に到着可能なルートが検索され、初期ルートが設定される。これにより、到着時間指定有の集配物を指定された到着時間前に集配する初期ルートが設定される。続いて、集配情報テーブル２より、到着時間指定無の集配物情報が抽出され、初期ルートに到着時間指定無の集配物を集配するルートが加えられるかどうかを検討する。そして、到着時間指定無の集配物を集配するルートを加えても、到着時間指定有の集配物が指定された到着時間前となる場合、このルートを初期ルートに加える。こうして、到着時間指定有の配送物とそうでない配送物とが混在する場合の集配ルートが設定される。
【発明の効果】
【００１４】
本発明では、集配の時間指定がされた時間指定集配物についての集配ルートを初期ルートとして予め設定し、時間指定集配物を基点に時間指定無集配物の集配ルートを配置することにより、効率的な集配ルートを設定することができるという利点がある。
【００１５】
また、集配ルートを時間的な制約条件に基づいて設定するため、最適な組み合わせを求めるための計算時間を低減させることができるという利点もある。
【発明を実施するための最良の形態】
【００１６】
以下、本発明の実施の形態を図面を参照して説明する。まず、実施の形態に適用される発明の概念について説明し、その後、実施の形態の具体的な内容を説明する。
図１は、本発明の集配ルート設定方法の原理図である。
【００１７】
本発明にかかる集配ルート設定装置１は、集配物に関する集配情報が登録された集配情報テーブル２と、道路交通情報３および地図情報４を用いて、効率的な集配ルートを設定する。
【００１８】
集配情報テーブル２は、集配物を集配する目的地の住所などの目的地情報と、集配物が目的地に到着する時間の指定があるかどうかを示した時間指定フラグ、到着時間指定がある場合にはその到着時間を含む集配情報が集配物に関連付けたテーブル情報として集配情報記憶手段に格納される。
【００１９】
道路交通情報３は、所定の道路区間における工事などによる通行規制など道路に関する情報で、道路交通情報記憶手段に格納される。地図情報４は、少なくとも集配が行われる地域を含む地図情報で、地図情報記憶手段に格納される。また、道路交通情報３または地図情報４に、地図上のある地点から他の地点までに配送車が走行した場合に要する時間情報などを備える。
【００２０】
集配ルート設定装置１は、まず、時間指定抽出手段が、集配情報テーブル２の時間指定フラグを参照し、到着時間指定有の集配物に関する集配情報を抽出する時間指定抽出処理を行う（ステップＳ１）。次に、初期ルート検索手段が、到着時間指定有の集配物の集配を行う初期ルートを設定する初期ルート検索処理を行う（ステップＳ２）。初期ルート検索処理では、時間指定抽出処理（ステップＳ１）によって抽出された時間指定有の集配情報と、道路交通情報３および地図情報４とを用いて、集配物が目的地に指定された到着時間前に到着可能なルートを検索し、初期ルートとして設定する。初期ルートの設定は、到着時間指定有の場合の指定到着時間より前に到着可能なルート（到着時間指定有の集配物の組み合わせ）を検索する。たとえば、移動開始の地点から配送先までの所要時間を算出し、移動開始地点の時刻に所要時間を加えた時間が配送先の指定到着時間より前であるかどうかを判断する。こうして、指定到着時間の早い順にルートに時間指定有の集配物が組込めるかどうかを判断し、初期ルートを設定する。また、上記の手順で第１の初期ルートが設定され、第１の初期ルートに組込まれなかった集配物があった場合、同じようにして第２の初期ルートを設定する。
【００２１】
以上の処理手順により、到着時間指定有の集配物を集配する初期ルートが設定される。なお、初期ルートが設定されると、初期ルートから各区間の余裕時間（指定された到着時間と実際の到着時間の差）を算出することができる。
【００２２】
次に、時間指定無抽出手段が、集配情報テーブル２の時間指定フラグを参照し、到着時間指定無の集配物に関する集配情報を抽出する時間指定無抽出処理を行う（ステップＳ３）。次に、時間指定無割当て手段が、初期ルート上の区間ごとの余裕時間を算出し、余裕時間内に配送可能な時間指定無の集配物を集配するルートを初期ルートに組込み、集配ルートを設定する時間指定無割当て処理を行う（ステップＳ４）。時間指定無割当て処理では、時間指定無抽出処理（ステップＳ３）によって抽出された時間指定無の集配情報と、道路交通情報３と地図情報４および初期ルート検索処理（ステップＳ２）で生成された初期ルートを用いて、初期ルート上の各区間の余裕時間を算出する。そして、余裕時間内に集配可能な時間指定無の集配物を検索し、検出された時間指定無の集配物の集配ルートを初期ルートに組込む。このとき、時間指定無の集配物のルートを組込んだことによって変わる次の時間指定有の集配物の配達の集配の開始点となる実際の到着時間を算出し、そこから時間指定有の集配物の指定時間までの残りの余裕時間を算出する。そして、残りの余裕時間がある場合、残りの余裕時間に基づいて余裕時間内に集配可能な時間指定無の集配物の検索からの手順を実行する。
【００２３】
以上の処理手順により、時間指定有の集配物を集配する初期ルートの余裕時間に基づいて時間指定無の集配物の集配が組込まれた集配ルートが設定される。このように、時間的な制約条件に基づいて集配ルートを設定するため、結果として、最適な集配ルートを設定することができる。また、集配ルートを設定するために必要な計算時間を低減させることができる。
【００２４】
以下、本発明の実施の形態を、荷物を配達する配送ルートの設定に適用した場合を例に図面を参照して詳細に説明する。
図２は、本発明の実施の形態の配送ルート設定装置の構成を示すブロック図である。図１と同じものについては同じ番号を付し、説明は省略する。
【００２５】
本発明の実施の形態の配送ルート設定装置１０は、時間指定配送物抽出部１１、初期ルート検索部１２、時間指定無配送物抽出部１３および時間指定無配送物割当て部１４の各処理部と、配送物テーブル記憶装置１５、地図・交通情報記憶装置１６および一時情報格納メモリ１７の各記憶手段を具備する。
【００２６】
時間指定配送物抽出部１１は、時間指定抽出手段で、配送物テーブル記憶装置１５に格納された配送物情報から配達時間指定（到着時間指定）のある配送物の配送物情報を抽出し、一時情報格納メモリ１７に格納する。
【００２７】
初期ルート検索部１２は、初期ルート検索手段であり、地図・交通情報記憶装置１６に保存された道路交通情報３および地図情報４を用いて、一時情報格納メモリ１７に格納された配達時間指定のある配送物を配送するルートを検索する。以下、配送時間指定のある配送物を時間指定有配送物と表記する。ルートは、各配送物が配送時間指定された時間までに到着可能な組み合わせが検索される。検索の詳細については、後述する。この配送時間指定有の配送物の配送を組込んだルートを初期ルートと呼び、一時情報格納メモリ１７に格納する。
【００２８】
時間指定無配送物抽出部１３は、時間指定無抽出手段で、配送テーブル記憶装置１５に格納された配送物情報から配送時間指定のない配送物（以下、時間指定無配送物とする）の配送物情報を抽出し、時間指定無配送物割当て部１４へ送る。
【００２９】
時間指定無配送物割当て部１４は、時間指定無割当て手段で、一時情報格納メモリ１７に格納された初期ルートを読み出し、各区間の余裕時間を算出する。そして、余裕時間内に配達可能な時間指定無配送物を時間指定無配送物抽出部１３の情報に基づいて検索し、検出した時間指定無配送物の配達を初期ルートに組込み、一時情報格納メモリ１７へ保存する。そして、間に時間指定無配送物の配送が組込まれた時間指定有配送物の実際の到着時間を算出し、算出された実際の到着時間から余裕時間を更新し、時間指定無配送物の検索からの処理を行う。時間指定無配送物の組込みの詳細は、後述する。
【００３０】
配送物テーブル記憶装置１５は、配送物の目的地、時間指定の有無、時間指定がある場合はその指定配送時間などの配送物に関する配送物テーブル２０を記憶する。配送物テーブル２０は、配送ルート設定処理開始までに読込まれる。
【００３１】
地図・交通情報記憶装置１６は、道路交通情報３および地図情報４が格納されるメモリで、これらの情報は配送ルート設定処理開始までに読込まれる。
一時情報格納メモリ１７は、各処理部が生成した情報の引渡しや、データ処理を行うためのメモリで、時間指定有の配送物の配送物情報、設定途中の初期ルートや配送ルートが一時的に格納される。
【００３２】
なお、以上の説明の各処理部は、コンピュータが集配ルート設定プログラムを実行することによってその処理機能を実現する。
ここで、本発明の配送ルート設定装置１０のハードウェア構成について説明する。図３は、本実施の形態の配送ルート設定装置のハードウェア構成例を示すブロック図である。
【００３３】
配送ルート設定装置１０は、ＣＰＵ（Central Processing Unit）１０１によって装置全体が制御されている。ＣＰＵ１０１には、バス１０７を介してＲＡＭ（Random Access Memory）１０２、ハードディスクドライブ（ＨＤＤ：Hard Disk Drive）１０３、グラフィック処理装置１０４、入力インタフェース１０５、通信インタフェース１０６が接続されている。
【００３４】
ＲＡＭ１０２には、ＣＰＵ１０１に実行させるＯＳ（Operating System）のプログラムやアプリケーションプログラムの少なくとも一部が一時的に格納される。また、ＲＡＭ１０２には、ＣＰＵ１０１による処理に必要な各種データが格納される。ＨＤＤ１０３には、ＯＳやアプリケーションのプログラムが格納される。グラフィック処理装置１０４には、モニタ１０８が接続されており、ＣＰＵ１０１からの命令に従って画像をモニタ１０８の画面に表示させる。入力インタフェース１０５には、キーボード１０９ａやマウス１０９ｂが接続されており、キーボード１０９ａやマウス１０９ｂから送られてくる信号を、バス１０７を介してＣＰＵ１０１に送信する。通信インタフェース１０６は、ネットワーク１１０に接続されており、ネットワーク１１０を介して配送物テーブル２０、道路交通情報３および地図情報４などを取得する。
【００３５】
このようなハードウェア構成によって、本実施の形態の処理機能を実現することができる。
次に、本発明の実施の形態の配送ルート設定装置１０の動作について説明する。
【００３６】
配送ルート設定処理の開始までに、配送物テーブル２０が配送物テーブル記憶装置１５に読込まれ、道路交通情報３および地図情報４が地図・交通情報記憶装置１６に読込まれる。
【００３７】
配送物テーブルについて説明する。図４は、本発明の実施の形態の配送テーブルの一例である。
配送物テーブル記憶装置１５に保存される配送物テーブルは、配送物テーブル２０の読込み情報部と、組込みフラグ部とを有する。読込み情報部は、配送物を識別する配送物ＩＤ２０１、配送物を配送する送付先を特定する送付先情報２０２、配送物の送付元に関する送付元情報２０３、時間指定有無（有／無＝１／０）を示した時間指定フラグ２０４、時間指定有の場合の指定配送時間２０５を有する。なお、送付先情報２０２や送付元情報２０３には、電話番号や住所など配送先および配送元の位置を特定することができる情報が登録される。組込みフラグ２０６は、この配送物をルートに組込んだかどうかを示す情報で、組込み終了／未完＝１／０で表される。図の例では、配送物ＩＤ「１０１１」の配送物は、配送先が「○○○−△△△△」で、時間指定が「有」、指定配送時間が「１０：００」の登録がされている。
【００３８】
時間指定配送物抽出部１１は、上記の説明の配送物テーブルを検索し、時間指定フラグ２０４の登録に基づいて時間指定有配送物の配送情報を抽出し、時間指定配送物抽出テーブルを作成して一時情報格納メモリ１７へ保存する。図５は、本発明の実施の形態の時間指定配送物抽出テーブルの一例である。
【００３９】
時間指定配送物抽出テーブルは、配送物２１１、指定配送時間２１２および配送位置２１３で構成される。配送物２１１は、配送物を識別する情報であるが、図の例では、便宜的に、指定配送時間の早い順に１からｍ（ｍは任意の整数）が割り振られている。指定配送時間２１２は、指定された配送時間で、配送時間の早い順に並べられている。すなわち、配送物番号ｉ＜ｊのとき、Ｔｉ≦Ｔｊが成立つ（ｉ、ｊは任意の整数）。配送位置２１３は、配送先の位置情報で、送付先情報２０２に基づいて配送先の緯度と経度が設定される。
【００４０】
次に、初期ルート検索部１２は、時間指定配送物抽出部１１で抽出された時間指定無の配送物について、指定配送時間前に配送可能なルートを検索する。指定配送時間の早い順に並べられた時間指定有配送物について順に、前（指定配送時間が早い）の時間指定有配送物から次の時間指定有配送物の配送先までの移動に要する所要時間を算出し、前の時間指定有配送物の指定配送時間に算出された所要時間を加えた時間が次の時間指定有配送物の指定配送時間を超えていないかどうかを判定する。超えていなければ、この配送を初期ルートに組込む。超えていれば、この配送を初期ルートに組込むのをやめ、次の時間指定有配送物で同様の処理を行う。こうして、時間指定有配送物の指定配送時間を守ることができる初期ルートが作成される。この処理において組込まれなかった時間指定有配送物について同様の処理を行い、第２、第３の初期ルートを作成する。作成される初期ルートの数は、たとえば配送車によって限定される。
【００４１】
以上の処理手順によって初期ルートが設定される。図６は、本発明の実施の形態の初期ルートの一例である。
初期ルート１配送物２２１は、初期ルート１に設定された配送物を示しており、図の例では、初期ルート１を用いて配送物１、４、６、・・・、ｍ−１が配送される。同様に、初期ルート２配送物２２２は、初期ルート２に設定された、配送物２、３、５、・・・、ｍが設定される。
【００４２】
次に、時間指定無配送物抽出部１３は、配送物テーブル記憶装置１５から配送テーブルを読み出し、時間指定無配送物に関する配送物情報を抽出する。このとき、組込みフラグがセット（＝１）であれば、ルートに組込み済みであるので抽出しない。
【００４３】
続いて、時間指定無配送物割当て部１４は、初期ルート検索部１２が設定した初期ルートより算出される余裕時間に基づいて、時間指定無配送物が初期ルートに組込めるかどうかを順次判定する。たとえば、スタート地点から時間指定有配送物１の配達の途中に時間指定無配送物１の配達が可能であるかどうかを判断する。時間指定無配送物１を経由して時間指定有配送物１に到着するのに要する所要時間が時間指定有配送物１の余裕時間を超えないかどうかを判定する。時間内であれば、時間指定無配送物１を初期ルートに組込み、組込みフラグをセットする。さらに、残った余裕時間がまだ十分であれば、他の時間指定無配送物が組込み可能であるかを調べる。また、増加分が余裕時間を超えれば、時間指定無配送物１を初期ルートに組込むのをやめ、時間指定無配送物２で同様の判定を行う。同様の手順を初期ルートの各区間で実行し、配送ルートを設定する。
【００４４】
図７は、本発明の実施の形態の配送ルートの一例である。図７は、図６の初期ルートに時間指定無配送物の配送を組込んだもので、時間指定無配送物は（）で示している。配送ルート１配送物２３１は、時間指定有配送物１と時間指定有配送物４の間に時間指定無配送物１、時間指定有配送物ｍ−１の後に時間指定無配送物３が組込まれている。同様に、配送ルート２配送物２３２は、時間指定有配送物３と時間指定有配送物５の間に時間指定無配送物２、時間指定有配送物ｍの前に時間指定無配送物４が組込まれている。
【００４５】
次に、本発明の配送ルート設定方法の処理手順を、フローチャートを用いて説明する。図８は、本発明の実施の形態の配送ルート設定処理の手順を示したフローチャートである。
【００４６】
［ステップＳ１１］  配送物テーブル、道路交通情報および地図情報を用いて、時間指定有配送物を抽出し、時間指定有配送物の初期ルートを検索する処理を行う。
［ステップＳ１２］  ステップＳ１１で設定された初期ルートに時間指定無配送物の組込みを行って配送ルートを設定する。
【００４７】
以下、ステップＳ１１の初期ルート設定処理およびステップＳ１２の時間指定無配送物組込み処理について詳細に説明する。
まず、初期ルート設定処理について説明する。図９は、本発明の実施の形態の初期ルート設定処理の手順を示したフローチャートである。
【００４８】
［ステップＳ２１］  配送物テーブル記憶装置に格納された配送物テーブルの時間指定フラグを参照し、時間指定有（＝１）が設定された時間指定有配送物に関する配送物情報を抽出し、一時情報格納メモリに格納する。抽出した時間指定有配送物は、指定配送時間の早い順に並べる（指定配送時間の一番早い時間指定有配送物を１とする）。
【００４９】
［ステップＳ２２］  ｉ＝１から抽出された時間指定有配送物の総数（ｍ）まで、ステップＳ２３からステップＳ２４の処理を繰返し行う。
［ステップＳ２３］  時間指定有配送物に対し、指定配送時間前に配送先に到着可能な初期ルートを検索する。たとえば、任意の時間指定有配送物（ｉ）の指定配送時間をＴｉ、他の任意の時間指定有配送物（ｊ）の指定配送時間をＴｊとし、配送物（ｉ）の配送地点から配送物（ｊ）の配送地点までの所要時間をｔｉｊとすると、
ｔｉｊ＜Ｔｉ−Ｔｉ                                                ・・・（１）
を満たすルートを検索し、検出されたルートを一時情報格納メモリに格納する。
【００５０】
［ステップＳ２４］  １つのルートが設定された（１つの時間指定有配送物がルートに組込まれた）ので、ｉに１を加え、ｉ＝ｍまで終了したかどうかを判定し、すべての時間指定有配送物のルート設定が終了していなければ、ステップＳ２３に戻って処理を繰り返す。
【００５１】
以上の処理手順が実行されることにより、すべての時間指定有配送物が初期ルートに組込まれる。なお、初期ルートは、いくつか作成される場合がある。
次に、時間指定無配送物の初期ルートへの組込み処理について説明する。図１０は、本発明の実施の形態の初期ルートへの組込み処理手順を示したフローチャートである。
【００５２】
時間指定有配送物を組込んだ初期ルートが設定され、処理が開始される。
［ステップＳ３１］  配送物テーブル記憶装置に格納された配送物テーブルの時間指定フラグを参照し、時間指定無（＝０）が設定された時間指定無配送物に関する配送物情報を取得する。
【００５３】
［ステップＳ３２］  ｉ＝１から初期ルートの区間数（ｍ）まで、ステップＳ３３からステップＳ３９の処理を繰返し行う。なお、初期ルートの区間数は、時間指定有配送物の総数と同じになる。
【００５４】
［ステップＳ３３］  初期ルートの区間、時間指定有配送物（ｉ−１）から時間指定有配送物（ｉ）について、余裕時間（ｔｒ，ｉ）内に配送可能な時間指定無配送物（αと表記する）を検索する。ｉ＝１の場合は、スタート地点からの区間を考える。余裕時間（ｔｒ，ｉ）は、時間指定有配送物（ｉ）の指定配送時間から時間指定有配送物（ｉ−１）の実到着時間との差で算出する。そして、ステップＳ３２で取得した時間指定無配送物をこの区間に組込んだ場合の所要時間Ｐ（ｉ−１）ｉと、余裕時間（ｔｒ，ｉ）とを比較する。なお、所要時間Ｐ（ｉ−１）ｉは、
Ｐ（ｉ−１）ｉ＝ｔ（ｉ−１）α１＋ｔα１α２＋・・・＋ｔαｎ−１αｎ＋ｔαｎｉ                                                                  ・・・（２）
で算出することができる。ここで、ｔ（ｉ−１）α１は、前の時間指定有配送物（ｉ−１）から最初の時間指定無配送物（α１）までの所要時間、ｔαｎｉは、最後の時間指定無配送物（αｎ）から時間指定有配送物（ｉ）までの所要時間を示し、ｔα１α２＋・・・＋ｔαｎ−１αｎは、時間指定無配送物（α１）から時間指定無配送物（αｎ）までの所要時間を表す。ｎは、余裕時間（ｔｒ，ｉ）と時間指定無配送物の配達所要時間によって決まる０以上の任意の数である。
【００５５】
［ステップＳ３４］  時間指定無配送物が初期ルート区間、すなわち、時間指定有配送物（ｉ−１）から時間指定有配送物（ｉ）の配送区間に割当てられるかどうかを判定する。割当てできなかった場合、ステップＳ３７へ処理を進める。
【００５６】
［ステップＳ３５］  時間指定無配送物が割当てできる場合、この時間指定無配送物を該当区間に組込み、配送物テーブルの組込みフラグをセットする。
［ステップＳ３６］  時間指定有配送物（ｉ）への実到着時間（λｉ）を算出する。λｉは、
λｉ＝λｉ−１＋Ｐ（ｉ−１）ｉ                                    ・・・（３）
により算出される。算出後、処理をステップＳ３８へ進める。
【００５７】
［ステップＳ３７］  時間指定無配送物が割当てられなかった場合の時間指定有配送物（ｉ）の実到着時間（λｉ）を算出する。λｉは、
λｉ＝λｉ−１＋ｔ（ｉ−１）ｉ                                    ・・・（４）
により算出される。ここで、ｔ（ｉ−１）ｉは、時間指定有配送物（ｉ−１）から時間指定有配送物（ｉ）の配送先までの所要時間を示す。
【００５８】
［ステップＳ３８］  次時間指定有配送物（ｉ＋１）の余裕時間（ｔｒ，ｉ＋１）を算出する。次時間指定有配送物（ｉ＋１）の余裕時間は、次時間指定有配送物（ｉ＋１）の指定配送時間Ｔｉ＋１と、式（３）または式（４）で算出された時間指定有配送物（ｉ）の実到着時間（λｉ）から、
ｔｒ，ｉ＋１＝Ｔｉ＋１−λｉ                                      ・・・（５）
で算出される。実際の時間指定有配送物（ｉ）の実到着時間を算出し、次の余裕時間を算出することにより、前の初期ルート区間への時間指定無配送物を組込んだ後に残る余裕時間を次の初期ルート区間の時間指定無配送物の組込みで利用することができる。
【００５９】
［ステップＳ３９］  ｉに１を加え、ｉ＝ｍまで終了したかどうか（すべての初期ルート区間について終了したかどうか）を判定し、終了していなければステップＳ３３に戻って処理を繰り返す。
【００６０】
以上の処理手順が実行されることにより、時間指定無配送物が初期ルートに組込まれ、最終の配送ルートが設定される。
なお、実際の配送業務では、到着予定時間が指定配送時間より少し前からの所定の時間帯に収まるように設定する場合がある。この場合、仮余裕時間を用いて、指定配送時間より仮余裕時間前から指定配送時間までの範囲を仮余裕時間で規定する。仮余裕時間を用いて初期ルートを設定する方法について説明する。図１１は、本発明の実施の形態の仮余裕時間を用いた初期ルート検索方法を示した説明図である。ここで、Ｔｉは時刻を表し、Ｔ０はスタート時点、Ｔ１は配送物１の指定配送時間を示す。同様にＴ２、Ｔ３は配送物２、３の指定配送時間を示す。また、ｔｒは仮余裕時間を示し、ｔｉｊは、道路交通情報と地図情報から導き出されるｉからｊ区間までの所要時間を示す。たとえば、ｔ０１は、スタート時点から配送物１の配送先までの所要時間を示す。
【００６１】
初期ルート検索について説明する。初期ルートの検索は、配送指定時間の早い配送物１から順に行われる。まず、仮余裕時間ｔｒが設定される。これにより、配送物１は、指定配送時間Ｔ１も余裕時間ｔｒ前（Ｔ１−ｔｒ）から指定配送時間Ｔ１までの間に配達しなければならないことになる。スタート地点から配送物１の配送先までの所要時間ｔ０１を算出し、スタート地点の時刻Ｔ０に所要時間ｔ０１を加算した配送予想時刻Ｔ０＋ｔ０１がＴ１−ｔｒからＴ１の間になるかどうか照合する。図の例では、範囲内に配達できるため、初期ルートにスタート地点から配送物１までのルートが設定される。次の配送物２についても同様の処理を行い、配送物１の配送先から配送物２の配送先までの所要時間ｔ１２を加えた配送予想時刻Ｔ１＋ｔ１２がＴ２−ｔｒからＴ２の間になるかを照合する。図の例では、配達可であるので、配送物１の配送先から配送物２の配送先までのルートが初期ルートに加えられる。ところが、配送物２の配送先から配送物３の配送先までの所要時間ｔ２３を加えた配送予想時刻Ｔ２＋ｔ２３は、配送物３の配送指定時刻Ｔ３を超えてしまうので、このルートは先程の初期ルートに加えることができない。この場合、新たな配送車で実行される初期ルート２を生成する。
【００６２】
なお、仮余裕時間を変更することができる場合、仮余裕時間を大きくして、初期ルートの検索を行ってもよい。たとえば、配達の時間帯指定がされているような場合、時間帯指定の最後の時間を指定配送時間とし、仮余裕時間の最大を配達時間帯の幅とすることにより、初期ルート設定を実現することができる。
【００６３】
以下、仮余裕時間を用いて初期ルートを設定する初期ルート設定方法について説明する。図１２は、本発明の実施の形態の仮余裕時間を用いた初期ルート設定処理の手順を示したフローチャートである。
【００６４】
［ステップＳ４１］  配送物テーブル記憶装置に格納された配送物テーブルの時間指定フラグを参照し、時間指定有（＝１）が設定された時間指定有配送物に関する配送物情報を抽出する。抽出した時間指定有配送物は、指定配送時間の早い順に並べる（指定配送時間の一番早い配送物を１とする）。
【００６５】
［ステップＳ４２］  仮余裕時間ｔｒを設定する。ｔｒは、たとえば、１５分程度の時間を設定する。
［ステップＳ４３］  ｉ＝１から抽出された時間指定有配送物の総数（ｍ）まで、ステップＳ４４からステップＳ４５の処理を繰返し行う。
【００６６】
［ステップＳ４４］  時間指定有配送物に対し、指定配送時間（Ｔｉ）の仮余裕時間（ｔｒ）前から指定配送時間（Ｔｉ）までの時間範囲で配送先に到着可能な初期ルートを検索する。他の任意の時間指定有配送物（ｊ）の指定配送時間をＴｊとし、配送物（ｉ）の配送地点から配送物（ｊ）の配送地点までの所要時間をｔｉｊとすると、
Ｔｉ＋ｔｉｊ≧Ｔｊ−ｔｒ                                        ・・・（６）
を満たすルートを設定し、一時情報格納メモリに格納する。
【００６７】
［ステップＳ４５］  １つのルートが設定された（１つの時間指定有配送物がルートに組込まれた）ので、ｉに１を加え、ｉ＝ｍまで終了したかどうかを判定し、すべての時間指定有配送物のルート設定が終了していなければ、ステップＳ４４に戻って処理を繰り返す。
【００６８】
［ステップＳ４６］  ステップＳ４５までの処理で初期ルートが設定されたかどうかを判定する。設定されていれば、ステップＳ４８へ処理を進める。
［ステップＳ４７］  初期ルートが設定できなかった場合、条件である仮余裕時間ｔｒを変更し、ステップＳ４３に戻って、ルートの再検索からの処理を行う。この場合、仮余裕時間は、可能な範囲で大きくする。
【００６９】
［ステップＳ４８］  初期ルートが設定されたので、設定された初期ルートを一時情報格納メモリに格納する。
以上の処理手順が実行されることにより、すべての時間指定有配送物がいずれかの初期ルートに組込まれる。
【００７０】
このように仮余裕時間を用いることにより、時間指定有の配送物の配送予想時間が指定配送時間前の所定の範囲内となるように初期ルートを設定することができる。
上記の説明では、時間指定有配送物（ｉ）に余裕時間（ｔｒ，ｉ）が存在する初期ルートの区間すべてについて、時間指定無配送物が組込めるかどうかを判定した。しかしながら、実際には、時間指定無配送物の組込みができない余裕時間が存在する。たとえば、余裕時間と移動時間の差が数分である場合、他の配送地点へ移動することは実際にはできないと考えられる。そこで、余裕度を導入し、余裕度に所定の閾値を設定し、余裕度が閾値を超えない場合は、時間指定無配送物の組込み処理を行わないようにすれば、計算時間を短縮することができる。ここで、時間指定有配送物（ｉ）の指定配送時間（Ｔｉ）に対する余裕度（ｔｓ，ｉ）は、初期ルートより予測される時間指定有配送物（ｉ）の配送予定時間（Ｔｅ，ｉ）を用いて、
ｔｓ，ｉ＝Ｔｉ−Ｔｅ，ｉ                                          ・・・（７）
により算出することができる。
【００７１】
以下、余裕度を用いて時間指定無配送物の組込み処理を行う配送ルート設定方法について説明する。図１３および図１４は、本発明の実施の形態の余裕度を用いた時間指定無配送物の組込み処理の手順を示したフローチャートである。
【００７２】
初期ルートが設定され、処理が開始される。
［ステップＳ５１］  余裕度閾値（ｔｔ）を設定する。余裕度閾値（ｔｔ）は、時間指定無配送物の配送を組込むことができないと考えられる時間が設定される。
【００７３】
［ステップＳ５２］  ｉ＝１から初期ルートに設定された時間指定有配送物の総数、すなわち初期ルートの区間数（ｍ）まで、ステップＳ５３からステップＳ５６の処理を繰返し行う。
【００７４】
［ステップＳ５３］  時間指定有配送物（ｉ）の余裕度（ｔｓ，ｉ）を算出する。余裕度は、式（７）により算出できる。
［ステップＳ５４］  余裕度（ｔｓ，ｉ）を用いて時間指定無配送物の組込み処理を実行する。
【００７５】
ここで、図１４を用いて時間指定無配送物の組込み処理について説明する。
［ステップＳ５４１］  ステップＳ５３で算出された余裕度（ｔｓ，ｉ）が余裕度閾値（ｔｔ）より大きいかどうかを判定する。小さい場合は、組込み不可とし、ステップＳ５４７へ処理を進める。
【００７６】
［ステップＳ５４２］  配送物テーブル記憶装置に格納された配送物テーブルの時間指定フラグを参照し、時間指定無（＝０）が設定された時間指定無配送物に関する配送物情報を取得する。
【００７７】
［ステップＳ５４３］  初期ルートの区間、時間指定有配送物（ｉ−１）から時間指定有配送物（ｉ）について、余裕度（ｔｓ，ｉ）内に配送可能な時間指定無配送物（αと表記する）を検索する。時間指定無配送物αをこの区間に組込んだ場合の所要時間の増加分Ｑ（ｉ−１）ｉを用いて、時間指定有配送物（ｉ）の指定配送時間（Ｔｉ）までの配送が可能な、
Ｔｓ，ｉ＞Ｑ（ｉ−１）ｉ                                          ・・・（８）
を満たす時間指定無配送物を検索する。
【００７８】
なお、増加分Ｑ（ｉ−１）ｉは、
Ｑ（ｉ−１）ｉ＝Ｐ（ｉ−１）ｉ−ｔ（ｉ−１）ｉ                    ・・・（９）
で算出することができる。
【００７９】
［ステップＳ５４４］  時間指定無配送物が割当てられたかどうかを判定する。割当てできなかった場合、ステップＳ５４７へ処理を進める。
［ステップＳ５４５］  時間指定無配送物が割当てられた場合、この時間指定無配送物を初期ルートの該当区間に組込み、配送物テーブルの組込みフラグをセットする。
【００８０】
［ステップＳ５４６］  時間指定有配送物（ｉ）への実到着時間（λｉ）を算出する。λｉは、式（３）で算出される。算出後、組込み処理を終了する。
［ステップＳ５４７］  時間指定無配送物が割当てられなかった場合の時間指定有配送物（ｉ）の実到着時間（λｉ）を算出する。λｉは、式（４）で算出される。算出後、組込み処理を終了する。
【００８１】
以上の処理手順で、時間指定無配送物が初期ルートの時間指定有配送物（ｉ−１）と時間指定有配送物（ｉ）の区間に組込まれる。
図１３へ戻って説明する。
【００８２】
［ステップＳ５５］  次時間指定有配送物（ｉ＋１）の配送予定時間（Ｔｅ，ｉ＋１）を算出する。配送予定時間（Ｔｅ，ｉ＋１）は、
Ｔｅ，ｉ＋１＝λｉ＋ｔｉ（ｉ＋１）                              ・・・（１０）
により算出される。
【００８３】
［ステップＳ５６］  ｉに１を加え、ｉ＝ｍまで終了したかどうか（すべての初期ルート区間について終了したかどうか）を判定し、終了していなければステップＳ５３に戻って処理を繰り返す。
【００８４】
以上の処理手順が実行されることにより、すべての時間指定無配送物が余裕度を参照して初期ルートに組込まれ、最終の配送ルートが設定される。
このように余裕度を用いた時間指定無配送物の組込み処理では、所定の閾値より短い余裕時間についての組込み処理を行わないため、計算時間を早くすることができる。
【００８５】
以下、具体例を用いて本発明の実施の形態を説明する。
図１５は、本発明の実施の形態の時間指定有配送物の指定配送時間の一例である。図１５は、時間指定配送物抽出部１１によって、配送物テーブル２０から時間指定有配送物に関する配送情報の抽出が行われた際に生成されるテーブルを示している。
【００８６】
図の例では、配送物１の指定配送時間は、１０：１０である。同様に、配送物２は１０：３０、配送物３は１０：４５、配送物４は１０：５０、配送物５は１１：００、配送物６は１１：２０、そして最後の配送物ｍは１７：００が指定配送時間である。なお、（配送物０）は、配送開始地点を、その指定配送時間は配送開始時間を示す。
【００８７】
次に、初期ルート検索部１２により初期ルートの検索が行われる。図１６は、本発明の実施の形態の初期ルート設定時に用いる各区間の所要時間を示した図である。ｔｉｊは、時間指定有配送物（ｉ）から時間指定有配送物（ｊ）の配送先まで移動する場合に必要な所要時間である。所要時間は、道路交通情報３および地図情報４から算出される。
【００８８】
図の例では、スタート地点である時間指定有配送物（０）から、時間指定有配送物（１）までの所要時間は１０分、時間指定有配送物（２）までの所要時間は２０分であることが示されている。同様に、時間指定有配送物（１）から、時間指定有配送物（３）までの所要時間は２０分、時間指定有配送物（４）までの所要時間は３０分であることがわかる。他の配送先地点間の所要時間も同様に算出される。
【００８９】
初期ルート検索部１２による初期ルート検索では、たとえば、スタート地点である時間指定有配送物（０）から時間指定有配送物（１）までのルートを考える。時間指定有配送物（１）の配送予定時間（Ｔ１）は、１０：１０であり、スタート地点から時間指定有配送物（１）の間の所要時間は１０分なので、時間指定有配送物（１）の指定配送時間（Ｔ１）に間に合う。そこで、スタート地点から時間指定有配送物（１）のルートが選択される。
【００９０】
次の時間指定有配送物（２）の配送予定時間は、時間指定有配送物（１）から時間指定有配送物（２）の所要時間が２５分であるので、１０：３５になる。これでは、時間指定有配送物（２）の指定配送時間１０：３０に間に合わない。したがって、時間指定有配送物（１）から時間指定有配送物（２）のルートを選択することができない。一方、時間指定有配送物（１）から時間指定有配送物（３）への移動の所要時間は、２０分であるので、時間指定有配送物（３）の配送予定時間は、１０：３０になる。これと時間指定有配送物（３）の指定配送時間１０：４５を比較し、余裕時間範囲内であれば時間指定有配送物（１）から時間指定有配送物（３）のルートを設定する。ここでは、このルートを設定することとする。
【００９１】
以上のようにして、順次初期ルートを設定していく。なお、上記の例で時間指定有配送物（１）から時間指定有配送物（２）のルートは除外されたので、時間指定有配送物（２）を配送する初期ルートを別に作成する。
【００９２】
このようにして作成された初期ルートの一例を示す。図１７は、本発明の実施の形態の初期ルートの一例を示した図である。
図の例では、初期ルート１として、配送物１、配送物３、配送物５、配送物６、配送物７・・・のルートが設定されている。同様に、初期ルート２として、配送物２、配送物４、・・・のルートが設定されている。
【００９３】
このように設定された初期ルートの各区間に対し、時間指定無配送物の組込み処理が行われる。図１８は、本発明の実施の形態の時間指定無配送物の組込み処理に用いるパラメータの一例である。なお、図１８は、余裕度を用いない場合のパラメータの一例である。
【００９４】
余裕度を用いない場合の時間指定無配送物の組込み処理では、初期パラメータの各区間の指定配送時間（Ｔｉ）と、各区間の所要時間ｔｉｊ、時間指定無配送物を組込んだ場合の所要時間Ｐ（ｉ−１）１、時間指定無配送物を組込んだ後の実際の到着時間λｉ、および余裕時間ｔｒ，ｉのパラメータ群により処理を行う。
【００９５】
図の例では、センターから時間指定有配送物１の区間は、余裕時間ｔｒ，ｉがないので、組込みは行われていない。時間指定有配送物１から時間指定有配送物３の区間では余裕時間ｔｒ，ｉは３５分であるが、適当な時間指定無配送物がないので、組込みを行わない。続く、時間指定有配送物３から時間指定有配送物５の区間は、時間指定有配送物３の配送先への到着時間λｉが１０：３０であるので、３０分の余裕時間が発生する。そこで、適当な時間指定無配送物が組込まれ、所要時間１５分を消費する。これにより、時間指定有配送物５の到着時間が１０：４５になる。同様に、時間指定有配送物５と時間指定有配送物６の間の区間も組込み処理を行う。
【００９６】
次に、余裕度を用いた場合のパラメータの一例を説明する。図１９は、本発明の実施の形態の時間指定無配送物を余裕度を用いて組込み処理を行った場合のパラメータの一例である。余裕度を用いた場合の時間指定無配送物の組込み処理では、初期パラメータの各区間の指定配送時間（Ｔｉ）と、各区間の所要時間ｔｉｊ、初期ルートより予測される時間指定有配送部（ｉ）の配送予定時間Ｔｅ，ｉ、時間指定無配送物を組込んだ場合の所要時間Ｐ（ｉ−１）１、時間指定無配送物を組込んだ後の実際の到着時間λｉ、および余裕度ｔｓ，ｉ、所要時間の増加分Ｑ（ｉ−１）ｉのパラメータ群により処理を行う。
【００９７】
この場合も、図１７の場合と同様の結果が得られる。図の例では、時間指定有配送物３から時間指定有配送物５の区間に発生した余裕度（＋１５）が持ち越され、次の区間の余裕度が＋２０となっていることが明確になる。
【００９８】
上記の実施の形態では、荷物を配達する場合について説明したが、本発明は荷物を収集する場合にも適用することができる。
なお、上記の処理機能は、コンピュータによって実現することができる。その場合、集配ルート設定装置が有すべき機能の処理内容を記述したプログラムが提供される。そのプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリなどがある。磁気記録装置には、ハードディスク装置（ＨＤＤ）、フレキシブルディスク（ＦＤ）、磁気テープなどがある。光ディスクには、ＤＶＤ(Digital Versatile Disc)、ＤＶＤ−ＲＡＭ(Random Access Memory)、ＣＤ−ＲＯＭ(Compact Disc Read Only Memory)、ＣＤ−Ｒ(Recordable)／ＲＷ(ReWritable)などがある。光磁気記録媒体には、ＭＯ(Magneto-Optical disk)などがある。
【００９９】
プログラムを流通させる場合には、たとえば、そのプログラムが記録されたＤＶＤ、ＣＤ−ＲＯＭなどの可搬型記録媒体が販売される。また、プログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することもできる。
【０１００】
プログラムを実行するコンピュータは、たとえば、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、自己の記憶装置に格納する。そして、コンピュータは、自己の記憶装置からプログラムを読み取り、プログラムに従った処理を実行する。なお、コンピュータは、可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することもできる。また、コンピュータは、サーバコンピュータからプログラムが転送される毎に、逐次、受け取ったプログラムに従った処理を実行することもできる。
【０１０１】
（付記１）  交通情報および地図情報を取得して最適な集配ルートを設定する集配ルート設定方法において、
時間指定抽出手段が、目的地、到着時間指定の有無および到着時間指定有の場合の到着時間を含む集配情報を集配物に関連づけた集配情報テーブルを格納した集配情報記憶手段から前記到着時間指定有の前記集配情報を抽出し、
初期ルート検索手段が、抽出された前記到着時間指定有の前記集配情報と前記交通情報と前記地図情報を用いて、前記到着時間指定有の前記集配物が指定された時間前に前記目的地に到着可能なルートを検索して初期ルートを設定し、
時間指定無抽出手段が、前記集配情報記憶手段から前記到着時間指定無の前記集配情報を抽出し、
時間指定無割当て手段が、前記初期ルート上の各区間の余裕時間を算出し、前記余裕時間内に配送可能な前記到着時間指定無の前記集配物を検索し、検出された前記到着時間指定無の前記集配物の集配を前記初期ルートに組込み、集配ルートを設定する、
手順を有することを特徴とする集配ルート設定方法。
【０１０２】
（付記２）  前記到着時間指定有の前記集配情報を抽出する手順は、抽出された前記集配情報を前記到着時間の早い順に並び替えを行い、
前記初期ルートを検索する手順は、
前記到着時間の早い順に前記初期ルートに組込み可能かどうかを判定することを特徴とする付記１記載の集配ルート設定方法。
【０１０３】
（付記３）  前記初期ルートを検索する手順は、
所定の仮余裕時間を設定し、前記到着時間指定有の場合に指定された指定到着時間より前記仮余裕時間前の時点から前記指定到着時間までの間に到着可能な前記集配物を検索することを特徴とする付記１記載の集配ルート設定方法。
【０１０４】
（付記４）  前記初期ルートを検索する手順は、
前記仮余裕時間前の時点から前記指定到着時間までの間に到着可能な前記集配物を検索できなかった場合、前記仮余裕時間を増やし、検索を繰り返すことを特徴とする付記３記載の集配ルート設定方法。
【０１０５】
（付記５）  前記初期ルートを検索する手順は、前記指定到着時間を超えてしまう前記集配物を検出した場合、前記集配物に関する新たな初期ルートの検索を行うことを特徴とする付記３記載の集配ルート設定方法。
【０１０６】
（付記６）  前記時間指定無割当て手段が、前記初期ルート上の余裕時間に前記到着時間指定無の前記集配物の集配を前記初期ルートに組込む手順は、
前記到着時間指定無の前記集配物を前記初期ルートに組込んだ後、前記到着時間指定無の前記集配物のルートを組込んだ際の前記余裕時間を更新し、
更新された前記余裕時間が残っている場合には前記余裕時間内に配送可能な前記到着時間指定無の前記集配物の検索からの手順を繰り返す、
ことを特徴とする付記１記載の集配ルート設定方法。
【０１０７】
（付記７）  前記時間指定無割当て手段が前記初期ルート上の余裕時間に前記到着時間指定無の前記集配物の集配を前記初期ルートに組込む手順は、
前記初期ルートの任意の区間の前記到着時間指定有の前記集配物に関する到着予定時間を算出し、前記到着予定時間より新たに前記初期ルートの任意の区間の集配先となる前記到着時間指定有の前記集配物に関する余裕度を算出して前記任意の区間に関する前記到着時間指定無の前記集配物の組込みを行うことを特徴とする付記１記載の集配ルート設定方法。
【０１０８】
（付記８）  前記時間指定無割当て手段が、前記初期ルート上の余裕時間に前記到着時間指定無の前記集配物の集配を前記初期ルートに組込む手順は、
前記初期ルートの任意の区間の前記到着時間指定有の前記集配物に関する到着予定時間を算出し、前記到着予定時間より新たに前記初期ルートの任意の区間の集配先となる前記到着時間指定有の前記集配物に関する余裕度を算出して、前記余裕度が予め設定された余裕度閾値を超えない場合は、前記初期ルートの前記任意の区間についての前記到着時間指定無の前記集配物の組込み処理を行わないことを特徴とする付記１記載の集配ルート設定方法。
【０１０９】
（付記９）  交通情報および地図情報を取得して最適な集配ルートの設定処理を行う集配ルート設定プログラムにおいて、
コンピュータを、
目的地、到着時間指定の有無および到着時間指定有の場合の到着時間を含む集配情報を集配物に関連づけた集配情報テーブルを格納した集配情報記憶手段から前記到着時間指定有の前記集配情報を抽出する時間指定抽出手段と、
抽出された前記到着時間指定有の前記集配情報と前記交通情報と前記地図情報を用いて、前記到着時間指定有の前記集配物が指定された時間前に前記目的地に到着可能なルートを検索して初期ルートを設定する初期ルート検索手段と、
前記集配情報記憶手段から前記到着時間指定無の前記集配情報を抽出する時間指定無抽出手段と、
前記初期ルート上の各区間の余裕時間を算出し、前記余裕時間内に配送可能な前記到着時間指定無の前記集配物の有無を検索し、検出された前記到着時間指定無の前記集配物の集配を前記初期ルートに組込み、集配ルートを作成する時間指定無割当て手段と、
して機能させることを特徴とする集配ルート設定プログラム。
【図面の簡単な説明】
【０１１０】
【図１】本発明の集配ルート設定方法の原理図である。
【図２】本発明の実施の形態の配送ルート設定装置の構成を示すブロック図である。
【図３】本実施の形態の配送ルート設定装置のハードウェア構成例を示すブロック図である。
【図４】本発明の実施の形態の配送テーブルの一例である。
【図５】本発明の実施の形態の時間指定配送物抽出テーブルの一例である。
【図６】本発明の実施の形態の初期ルートの一例である。
【図７】本発明の実施の形態の配送ルートの一例である。
【図８】本発明の実施の形態の配送ルート設定処理の手順を示したフローチャートである。
【図９】本発明の実施の形態の初期ルート設定処理の手順を示したフローチャートである。
【図１０】本発明の実施の形態の初期ルートへの組込み処理手順を示したフローチャートである。
【図１１】本発明の実施の形態の仮余裕時間を用いた初期ルート検索方法を示した説明図である。
【図１２】本発明の実施の形態の仮余裕時間を用いた初期ルート設定処理の手順を示したフローチャートである。
【図１３】本発明の実施の形態の余裕度を用いた時間指定無配送物の組込み処理の手順を示したフローチャートである。
【図１４】本発明の実施の形態の余裕度を用いた時間指定無配送物の組込み処理の手順を示したフローチャートである。
【図１５】本発明の実施の形態の時間指定有配送物の指定配送時間の一例である。
【図１６】本発明の実施の形態の初期ルート設定時に用いる各区間の所要時間を示した図である。
【図１７】本発明の実施の形態の初期ルートの一例を示した図である。
【図１８】本発明の実施の形態の時間指定無配送物の組込み処理に用いるパラメータの一例である。
【図１９】本発明の実施の形態の時間指定無配送物を余裕度を用いて組込み処理を行った場合のパラメータの一例である。
【符号の説明】
【０１１１】
１  集配ルート設定装置
２  集配情報テーブル
３  道路交通情報
４  地図情報
１０  配送ルート設定装置
１１  時間指定配送物抽出部
１２  初期ルート検索部
１３  時間指定無配送物抽出部
１４  時間指定無配送物割当て部
１５  配送物テーブル記憶装置
１６  地図・交通情報記憶装置
１７  一時情報格納メモリ
【図１】
2005280972.tif 000003
【図２】
2005280972.tif 000004
【図３】
2005280972.tif 000005
【図４】
2005280972.tif 000006
【図５】
2005280972.tif 000007
【図６】
2005280972.tif 000008
【図７】
2005280972.tif 000009
【図８】
2005280972.tif 000010
【図９】
2005280972.tif 000011
【図１０】
2005280972.tif 000012
【図１１】
2005280972.tif 000013
【図１２】
2005280972.tif 000014
【図１３】
2005280972.tif 000015
【図１４】
2005280972.tif 000016
【図１５】
2005280972.tif 000017
【図１６】
2005280972.tif 000018
【図１７】
2005280972.tif 000019
【図１８】
2005280972.tif 000020
【図１９】
2005280972.tif 000021