配車計画立案装置及び配車計画立案方法
【課題】配車計画において生じた配車車両の「待ち」の時間を低減させた配車計画を立案する。
【解決手段】所定の出発地点から出発して、２以上の訪問地点を巡回するための配車計画を立案する配車計画立案装置１００であって、取得した訪問時間と訪問地点の位置と出発地点の位置とに基づいて、配車計画を立案する配車計画立案手段４０と、立案された配車計画において訪問地点を巡回する配車車両に待ちが生じると判断された場合、待ちが生じる訪問地点と出発地点との位置関係に基づいて配車計画を補正する補正手段５０と、を備えた。
【解決手段】所定の出発地点から出発して、２以上の訪問地点を巡回するための配車計画を立案する配車計画立案装置１００であって、取得した訪問時間と訪問地点の位置と出発地点の位置とに基づいて、配車計画を立案する配車計画立案手段４０と、立案された配車計画において訪問地点を巡回する配車車両に待ちが生じると判断された場合、待ちが生じる訪問地点と出発地点との位置関係に基づいて配車計画を補正する補正手段５０と、を備えた。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、配車計画立案装置及び配車計画立案方法に関し、特に、所定の出発点から複数の地点を巡回する際に発生する「待ち」を短縮乃至解消させるように補正された配車計画を立案する配車計画立案装置及び配車計画立案方法に関する。
【背景技術】
【０００２】
車両により複数の地点に居るユーザを送迎するシステムに関し、予め定められた巡回ルートの随所に設定された送迎場所に接近乃至到達した時に、送迎車両の送迎情報を所定の連絡先に通知するものがある（特許文献１参照）。この送迎支援システムによれば、利用者側及び送迎サービス業者側の送迎場所における待ち時間を軽減させることができる。
【０００３】
しかしながら、条件によっては最適な配車計画（解）を求めることができず、待ちが発生してしまうという問題があった。パラメータが多い巡回配送や巡回送迎などの配車計画の最適化は一般に難しいと言われるが、巡回送迎のように、所定の場所に所定の時間（何時何分から何時何分の間）に訪問しなければならないといった時間的な制約条件が課されると配車計画の最適化がいっそう困難になり、待ちが解消されない配車計画が立案されてしまうという問題があった。
【特許文献１】特開２００２−３１２８９６号公報
【発明の開示】
【０００４】
本発明は、以上の課題を鑑みてなされたものであり、立案された配車計画に待ちが発生している場合に、待ち時間が短縮され又は待ちが解消された最適な配車計画を自動的に立案することを目的とする。
本発明によれば、所定の出発地点から出発して、２以上の訪問地点を巡回するための配車計画を立案する装置等であって、取得した訪問時間と訪問地点の位置と出発地点の位置とに基づいて、配車計画を立案し、立案された配車計画において訪問地点を巡回する配車車両に待ちが生じると判断された場合、待ちが生じる訪問地点と出発地点との位置関係に基づいて配車計画を補正する配車計画立案装置及び配車計画立案方法が提供される。
【０００５】
本発明の配車計画立案装置及び配車計画立案方法によれば、立案された配車計画に「待ち」が含まれる場合であっても、発生する「待ち」が解消され又は待ち時間が短縮されるように補正された最適な配車計画を立案することができる。
【発明を実施するための最良の形態】
【０００６】
以下、図面に基づいて、本発明に係る実施形態の配車計画立案装置１００を説明する。本発明の配車計画立案装置１００は、物品の集荷、配送、人の送迎など広く適用可能である。
【０００７】
図１に配車計画立案装置１００を含む配車支援システム１０００の構成の概要を示した。配車支援システム１０００は、配車を行う（集荷、配送、送迎サービスを行う）配車側の端末４、送迎（又は集荷、配送）サービスを受けるユーザ（被送迎者、配送委託者、荷受者）が利用する訪問ユーザ側端末５、配車計画立案装置１００がアクセス可能な予約情報３ｃ、訪問地点情報３ａ、出発地点情報３ｂその他のデータベース、送迎等に用いられる配車車両に搭載された車両側端末６を備える。
【０００８】
この送迎支援システム１０００は、ＡＳＰ（アプリケーション・サービス・プロバイダ）型のシステムとして構築されるものであり、配車計画立案装置１００、配車側端末４、ユーザ側端末５、車両側端末６は、通信ネットワークであるインターネット１にそれぞれ接続する通信機能を備え、相互に情報の送受信を行うことができる。
【０００９】
図１に示すように、本実施形態の配車計画立案装置１００は、予約情報取得手段１０と、訪問地点情報取得手段２０と、出発遅延情報取得手段３０と、配車計画算出手段４０と、補正手段５０と、出力手段６０と、通信機能７０とを有し、所定の出発地点から出発して、２以上の訪問地点を巡回するための配車計画を立案する。具体的には、少なくとも、配車計画を立案するプログラムを格納したＲＯＭ(Read Only Memory)等と、このＲＯＭ等に格納されたプログラムを実行することで、配車計画算出手段４０、補正手段５０として機能するＣＰＵ（Central Processing Unit）等と、アクセス可能な記憶手段として機能するＲＡＭ(Random Access Memory)等とを備えている。
【００１０】
本実施形態の配車計画立案装置１００の各構成について説明する。
「予約情報取得手段１０」は、通信機能７０を介して被送迎者、集荷依頼者、荷受者等を含むユーザが指定した訪問時間を含む予約情報を取得する。本実施形態では、ユーザ側から入力された予約情報を予約情報データベース３ｃに蓄積する。
【００１１】
「訪問地点情報取得手段２０」は、予約をしたユーザが指定する訪問地点の位置（例えば住所）を特定する情報を含む訪問地点情報を、外部又は内部の訪問地点情報データベース３ａから取得する。訪問地点の位置が予約情報に含まれる場合には、予約情報取得手段１０を介して訪問地点の位置情報を取得してもよい。訪問地点の位置情報は、被送迎者の自宅等の訪問地点の位置を住所又は緯度経度により表現された情報である。訪問地点情報データベース３ａにはユーザと対応づけられた各訪問地点の住所情報が記憶されている。住所は住所名緯度経度データベースを検索することにより経度・緯度の値として訪問地点情報データベース３ａに保存される。住所名緯度経度データベースは、県名、市名、丁目、番地、号数、経度緯度が対応づけられた状態で保存されているため、住所名から経度緯度または緯度経度から住所へ変換できる。なお、ユーザの住所（送迎場所）の道幅が狭い場合などは、小型車指定などの属性を含めてもよい。
【００１２】
「出発地点情報取得手段３０」は、予め記憶された出発地点（例えば施設、貨物集配所等）の所在地を含む出発地点情報を取得する。出発地点情報取得手段３０は、装置内又は装置外に設けられた出発地点情報データベース３ｂに記憶された施設情報を取得する。出発地点情報には送迎又は配送に用いられる配車車両の車両情報も含まれる。車両情報は、車両ＩＤ、定員、出発時間、帰着時間を保存したデータベースである。介護施設への送迎ではこれに車両ごとの属性（車椅子の搭載可能台数など）が追加される。なお、ここでは説明の便宜のため、各データベース３ａ、３ｂ、３ｃを分けて説明しているが、これらはハード的に一体に構成されてもよく、配車計画立案装置１００（情報処理サーバ２）の内部に組み込まれていてもよい。
【００１３】
「配車計画立案手段４０」は、所定の出発地点から出発して、２以上の訪問地点を巡回し、出発地点へ戻るための配車計画を立案する。具体的に、配車計画立案手段４０は、振り分け部４１と、巡回ルート算出部４２と、条件確認部４３とを有し、予約情報取得手段１０により取得された「訪問時間」と、予約をしたユーザが指定する「訪問地点の位置」と、予め記憶された「出発地点の位置」とに基づいて配車計画を立案する。本例の配車計画立案手段４０が立案する「配車計画」は、巡回に用いられる車両が特定され、その車両により訪問される地点が特定され、各地点の巡回ルートが特定された計画である。本実施形態において、配車計画を自動的に作成するためのアルゴリズムは限定されない。配車計画立案手段４０は、送迎サービスの予約締め切り時が経過した後又は各配送事業者が集荷・配送サービスの予約締め切り時が経過した後、受け付けた予約情報に基づいて、予約をしたユーザが訪問を希望する訪問地点を特定した後に配車計画を立案する。
【００１４】
本実施形態の配車計画立案手段４０は、振り分け部４１と、巡回ルート算出部４２と、条件確認部４３とを有する。振り分け部４１は、セービングコスト法を用いて、訪問地点をグループごとに振り分けて最適なグループを生成する。巡回ルート算出部４２は、メタヒューリスティック法を用いて生成されたグループについて最適化されたルートを算出する。条件確認部４３は、生成されたグループ、及び算出されたルートが、各地点の巡回に係る制約条件を満たすか否かを判断する。具体的に、条件確認部４３は、グループを構成する送迎対象者の人数が送迎に用いられる車両の定員以下であるか否か、グループを構成する貨物の体積が配送に用いられる車両の積載制限量以下であるか否か、巡回所要時間が所定の制限時間以内であるか否か、介護者を送迎する場合において、車椅子を利用する乗員数（要介護情報に基づいて判断する）が送迎に用いられる車両の車椅子搭載数（施設情報の車両情報に基づいて判断する）以下であるか否かを判断する。
【００１５】
「補正手段５０」は、配車計画立案手段４０により立案された配車計画において訪問地点を巡回する配車車両に待ちが生じると判断した場合、待ちが生じる地点の位置と出発地点との位置関係に基づいて配車計画を補正する。待ちとは、配車車両が指定された訪問時間よりも訪問地点に早く到着してしまう場合に、指定された訪問時間まで待機することをいう。例えば、巡回時間が９時から１０時と規定されている場合に、９時５５分から１０時を訪問時間として指定する訪問地点Ａがあるとすると、訪問地点Ａ以外の訪問地点の巡回が９：５５以前（例えば９：３０）までに終了しても、訪問地点Ａを訪問するには９：５５まで待機しなければならず、この配車計画には「待ち」が発生する。
【００１６】
補正手段５０は待ち検出部５１と、代替計画立案部５２と、待機地点指定部５３とを有する。待ち検出部５１は、立案された配車計画における巡回において配車車両に待ちが生じるか否かを算出し、その結果を代替計画立案部５２へ送出する。
【００１７】
代替計画立案部５２は、待ち検出部５１が巡回において待ちが生じると判断した場合に起動する。代替計画立案部５２は、待ちが生じる訪問地点の位置と出発地点との位置との位置関係に基づいて、待ちが生じる訪問地点に係る代替計画を立案する。補正手段５０は、この代替計画に応じて配車計画の補正を行う。代替計画の内容は特に限定されないが、本実施形態の代替計画立案部５２は、他の車両の位置情報を取得し、取得した他の車両の位置情報に基づいて、待ちが生じる訪問地点を巡回可能な他の車両であって、待ちの生じる訪問地点に指定された訪問時間に訪問することができる他の車両を検索し、検索された車両に待ちが生じる訪問地点を別途訪問させる代替計画を立案する。代替計画立案部５２は、他の車両に搭載されたＧＰＳ機能を用いて検出された自車位置を、通信機能７０を介して取得する。
【００１８】
また、本実施形態の代替計画立案部５２は、待ちが生じる訪問地点を訪問時間内に訪問可能な他の車両が検索されなかった場合、配車車両が待ちの生じる訪問地点に指定された訪問時間に訪問することを条件に、配車車両を待ちが生じる訪問地点をスキップして出発地点へ帰還させてから、待ちが生じる訪問地点を訪問させる代替計画を立案する。
【００１９】
待機地点指定部５３は、待ちが生じる訪問地点を訪問時間内に訪問可能な他の車両が検出されず、配車車両が出発地に戻ってから待ちの生じる訪問地点を訪問すると、待ちが生じる訪問地点に指定された訪問時間に訪問できない場合、所定の位置に予め設定された待機地点に関する待機地点データを参照し、待ちの生じる訪問地点と所定の位置関係を有する待機地点を検索し、検索された待機地点を指定して配車車両を一時待機させる代替計画を立案する。待機地点と訪問地点との所定の位置関係とは、特に限定されないが、両地点間の経路長が所定値以下である位置関係、両地点間の直線距離が所定値以下である位置関係、又は両地点間の経路長若しくは直線距離が最短の位置関係であることが好ましい。
【００２０】
補正手段５０は、代替計画立案部５２により立案された代替計画及び待機地点指定部５３により地点が指定された待機命令に基づいて、配車計画立案手段４０により算出された配車計画を補正する。具体的に、補正手段５０は、待ちが発生している地点について、他の車両による訪問、配車車両による訪問、又は所定の待機地点における待機により、各地点における待ち時間を短縮乃至消滅させる。
【００２１】
補正手段５０により補正された配車計画は、出力手段６０を介して施設側端末４、車両側端末６、ユーザ側端末５等の外部装置に送出される。
【００２２】
次に、本実施形態の配車計画立案装置１００の動作手順を図面に基づいて説明する。図２は配車計画立案処理全体の制御手順を示すフローチャート図、図３は配車計画立案処理における組み合わせ最適化処理の制御手順を示すフローチャート図、図４（Ａ）（Ｂ）は組み合わせ最適化処理を説明するための図、図５は配車計画立案処理における巡回ルートの最適化処理の制御手順を示すフローチャート図、図６（Ａ）（Ｂ）は巡回ルートの最適化処理を説明するための図、図７は補正処理の制御手順を示すフローチャート図である。
【００２３】
まず、図２に基づいて配車計画立案処理の全体概要を説明する。
予約情報取得手段１０は、ユーザから指定された訪問時間（送迎時間、集荷時間、配達時間など）を含む予約情報を取得する（Ｓ１０）。予約情報の取得は、予約締め切り時まで継続する。予約締め切り時経過後、訪問地点情報取得手段２０は予約のあった訪問地点の位置を含む訪問地点情報を取得する（Ｓ１１）。訪問地点情報取得手段２０は、予約情報中のユーザＩＤに基づいて、訪問地点情報データベース３ｃからユーザの住所を訪問地点の位置として読み出してもよい。出発地点情報取得手段３０は配車車両が出発する位置（巡回後に帰着する位置）を含む出発地点情報を取得する（Ｓ１２）。
【００２４】
配車計画立案手段４０は、訪問時間と訪問地点の位置と出発地点の位置とに基づいて配車計画を立案する（Ｓ２０）。配車計画の立案には、グループの組み合わせを最適化する処理と、グループ内の送迎順序を最適化する処理とが含まれる。
【００２５】
補正手段５０は配車計画立案手段４０により立案された配車計画において訪問地点を巡回する配車車両に待ちが発生すると判断された場合、この待ちが生じる訪問地点の位置と出発地点との位置関係に基づいて配車計画を補正する（Ｓ４０）。出力手段６０は補正手段５０により補正された配車計画を外部へ向けて出力する（Ｓ５０）。
【００２６】
次に、配車計画立案処理（図２のＳ２０）のうち、グループの組み合わせを最適化する処理について説明する。配車計画立案手段４０の振り分け部４１は、セービングマトリックスを用いてグループの最適化を行う。
【００２７】
図３にグループの組み合わせを最適化する処理の制御手順を示した。配車計画立案処理の開始（Ｓ２０）に伴い、セービングコスト法を用いた組み合わせ最適化処理を開始する（Ｓ２１）。まず、振り分け部４１は、セービングマトリックスを用いてセービングコストが最大値Sijとなるユーザiとユーザjを取り出す（Ｓ２２）。
【００２８】
本例で用いるマトリックスは、ユーザＡとユーザＢの距離Ｄijを保存したマトリックスである。距離とは道のり（経路長）が適切であるが、計算量を軽減させる観点から、経度緯度から三平方の定理により直線距離を求め、適当な道のりゲインを乗算したものを用いる。これらの値はあらかじめ計算しておく。 セービングマトリックスは、ユーザiとユーザjに対して、出発地（施設）→ユーザi、出発地(施設)→ユーザjをピストン輸送した場合のコスト（図４（Ａ）参照）と、出発地（施設）→ユーザi→ユーザjと循環した場合のコスト（図４（Ｂ）参照）との差をあらわしたもので、D0i*2+D0j*2-(D0j+Dij+Di0)=D0i-Dij+D0j=Sij（セービングコスト）を保持したマトリックスである。
【００２９】
Ｓ２３において、取り出されたユーザの双方ともが、まだどのグループ（ルート）にも振り分けられていない場合（Ｓ２３にてＹｅｓ）、新たなルートを作成してユーザi及びユーザjを割り当てる（Ｓ２４）。
【００３０】
Ｓ２５において、取り出されたユーザの双方ともが、いずれかのグループ（ルート）に振り分けられているか否かを判断する。取り出されたユーザの双方ともがグループ（ルート）に属している場合（Ｓ２５にてＹｅｓ）、合併処理を行う（Ｓ２６）。合併に際しては、合併した両グループ（ルート）が制限時間、制限航続距離、車両定員等の制限条件を満たすことを確認する。つまり、制限条件を満たすと判断された順にグループの合併を行う。制限条件を満たさない場合はグループの合併は行わない。
【００３１】
Ｓ２３において、取り出されたユーザの双方ともがいずれのグループにも属しておらず、Ｓ２５において、双方ともがいずれかのグループに属している場合、すなわち、取り出されたユーザのいずれか一方のみが、いずれかのグループに属している場合（他方はいずれのグループにも属していない場合）、割り当てたグループが制限時間、制限後続距離、車両定員等の制限条件を満たすことを前提に、ユーザの一方が属しているグループ（ルート）に他方のユーザを加える（Ｓ２７）。制限条件を満たさない場合は何も処理しない。
【００３２】
所属グループが決定したユーザのセービングコストには、Ｓｉｊ＝０を代入して次回処理の対象とならないようにする。セービングコストの最大値がゼロ、すなわちＭａｘ（Ｓｉｊ）＝０ならば終了する（Ｓ２８）。
【００３３】
振り分け部４１により振り分けられたグループについて、制限条件を満たすか否かを判断する際に、巡回ルート算出部４２は算出過程における各グループの暫定的な最適ルートを求めて、そのルート上でノードに待ちが発生しないか、到着時間に遅れが生じないかをチェックする。
【００３４】
本例の巡回ルート算出部４２は、メタヒューリスティック法を用いて巡回ルートの最適化を行う。この制御手順を図５に示した。図５には、振り分け部４１の振り分け処理と、巡回ルート算出部４２との巡回ルート算出処理とを組み合わせたフローチャートを示した。ここでは、巡回ルート算出部４２による巡回ルートの算出処理を中心に説明する。
【００３５】
巡回ルートの最適化処理が機能する場合（Ｓ３０）、振り分け部４１はセービングマトリックスを用いてセービングコストが最大値Sijとなるユーザiとユーザjを取り出し巡回ルートのグループを生成する（Ｓ２２〜Ｓ２７）。Ｓ２６にて合併されたグループについて、ＴSP(ルート(Ni)とルート(Nj)）の近似解を求める（Ｓ３１）。同様に、いずれか一方がいずれかのグループに属している場合に、グループに属していない一方のユーザを他方が属するグループに加えたグループ(Ｓ２７)について、ＴSP(ルート(Ni)とルート(Nj)）の近似解を求める（Ｓ３２）。ここで、ＴＳＰ（Traveling Salesman Problem）とは、ノード数とそれぞれのノード間の道のりが判っているときに、ある者がN個のノードを必ず１回だけ通って巡回したとき、総経路長を最短にするような、都市の巡回経路を見つける問題である。本例では、この近似最適解を求めるためにメタヒューリスティック解法を用いる。
【００３６】
仮の送迎順番が図６（Ａ)に示すものであったとして、本例における解法の一例を以下に説明する。
【００３７】
１）適当な2つのノードを選んでその順番を入れ替える（図６（Ｂ））。
２）遅れが発生していた場合はその遅れがどれだけ小さくなるかのΔｄを計算する。
３）すべての２つのノードの組み合わせに対してΔｄを計算する。
４）Ｍａｘ（Δｄ）を与える２つのノードを実際に取り替える。
５）遅れが発生していない場合は、その２つのノードを取り替えたときに最終到着時間どれだけ早くなるかのΔaを計算する。
６）すべての２つのノードの組み合わせに対してΔaを計算する。
７）Ｍａｘ（Δa）を与える２つのノードを実際に取り替える。
なお、「待ち」は最終到着時間の最小化と言う形で結果的に解消される方向にあるが、もし「待ち」が最後のノードになった場合はそれ以上の短縮は不可能となる。また、この処理により「遅れ」は積極的に解消される。
【００３８】
時間の観点から最適化されたグループについて、訪問時間、車両の定員数、車両の設備（車椅子の搭載能力、車椅子からの搭乗補助機能）に基づく制限が満たされたか否か、つまり巡回ルートが適切であるか否かを判断する（Ｓ３３）。その後、セービングコストの最大値がゼロ、すなわちＭａｘ（Ｓｉｊ）＝０ならば終了する（Ｓ２８）。
【００３９】
配車計画立案手段（４０）により立案された配車計画について、補正手段５０は補正を行う。補正手段５０は、立案された配車計画において訪問地点を巡回する配車車両に待ちが生じると判断された場合、配車計画の補正を行う。本例の補正手段５０は、待ちが生じる訪問地点の位置と出発地点の位置との位置関係に基づいて配車計画を補正する。
【００４０】
図７は補正処理の制御手順を示すフローチャート図である。
補正処理が開始すると（Ｓ４０）、待ち検出部５１は配車計画において配車車両に待ちが発生しているか否かを判断する（Ｓ４１）。待ちが発生していない場合は補正をする必要がないためＳ５０の出力処理へ進む。待ちが発生している場合にはＳ４２に進む。待ちが発生している場合、代替計画立案部５２は待ち時間を短縮乃至消滅させる代替計画を立案する。
【００４１】
Ｓ４２において、代替計画立案部５２は、他の車両の位置情報を取得し、取得した他の車両の位置情報に基づいて、待ちが生じる訪問地点を訪問可能な他の車両であって、待ちの生じる訪問地点に指定された訪問時間に訪問することができる他の車両を検索する(Ｓ４２)。具体的に代替計画立案部５２は、他の車両の位置情報が出発地点の位置である場合、他の車両は出発地点に帰還しており、待ちが生じる訪問地点にすぐに訪問できると判断する。さらに代替計画立案部５２は、他の車両の位置情報と待ちが生じる訪問地点の位置情報との経路長を求め、この経路長と車両の平均速度とから、この他の車両が待ちの生じる訪問地点に指定された訪問時間内に訪問できるか否かを判断する。つまり、他の車両が出発地点に所在し、かつ出発地点から遅れが生じる訪問地点までの所要時間が、現在時刻から訪問時刻までの時間よりも短いか否かを判断する。
【００４２】
Ｓ４２において、条件を満たす他の車両が検索された場合、代替計画立案部５２は検索された車両に待ちが生じる訪問地点を別途訪問させる代替計画を立案する（Ｓ４３）。Ｓ４２にて検索された車両を代替計画用の車両として配車する。この車両に遅れが生じた訪問地点の訪問（送迎、集荷）を任せ、訪問するはずであった配車車両はこの訪問地点をスキップして出発地点（帰着地点）へ戻る。配車車両は待機することなく出発地点（帰着地点）へ戻ることができる。これにより、巡回に要する時間を短縮させることができる。最適化された配車計画では、最後に巡回する訪問地点に待ちが発生する傾向がある。また、最後に巡回する訪問地点は、出発地点に近い位置にある傾向がある。本実施形態の代替計画によれば、遅れの生じる訪問地点近傍（例えば出発地点）に位置する他車両が、出発地点に近い訪問地点へ訪問するため、補正により新たに生じるコストを抑制することができる。つまり、すべての訪問地点を巡回するために要する総コストを低く抑えることができる。Ｓ４２において、条件を満たす他の車両を検索できなかった場合は、Ｓ４４へ進む。
【００４３】
Ｓ４４において、代替計画立案部５２は、配車車両が出発地点へ一度帰着してから待ちが発生している地点に指定された訪問時間内に到着できるか否かを判断する。つまり、代替計画立案部５２は、配車車両が待ちの生じる訪問地点に指定された訪問時間内に戻れるか否か判断する。具体的に、代替計画立案部５２は、遅れが生じる訪問地点から出発地点に一度帰着し再度出発して、訪問地点へ到着する予想到着時間｛ (D0n-1+D0n)/平均時速＋出発地点でユーザを降車させるのに要する時間｝（ただし、Ｄ0nは遅れが生じる訪問地点と出発地点との距離、Ｄ0n-1は遅れが生じる訪問地点の１つ手前の訪問地点と出発地点との距離）が、現在時刻から遅れの生じる訪問地点（ｎ）について指定された訪問時間までの時間以下であるか否かを判断する。配車車両が待ちの生じる訪問地点に訪問時間内に戻れる場合、代替計画立案部５２は、待ちが生じる訪問地点をスキップしてその１つ手前の訪問地点から出発地点へ向かってから、待ちが生じる訪問地点を訪問する代替計画を立案する（Ｓ４５）。これにより、巡回に要する時間を短縮させることができる。最適化された配車計画では、最後に巡回する訪問地点に待ちが発生する傾向がある。また、最後に巡回する訪問地点は、出発地点に近い位置にある傾向がある。本実施形態の代替計画によれば、配車車両が一旦出発地点に戻ってから遅れの生じる訪問地点を巡回するため、補正により新たに生じるコストを抑制することができる。つまり、すべての訪問地点を巡回するために要する総コストを低く抑えることができる。他方、Ｓ４４において、配車車両が条件を満たさない場合は、Ｓ４６へ進む。
【００４４】
Ｓ４６は、待ちが生じる訪問地点を訪問時間内に訪問可能な他の車両が検出されず（Ｓ４２でＮ）、配車車両が出発地点に戻ってから待ちの生じる訪問地点を訪問すると、待ちが生じる訪問地点に指定された訪問時間に訪問できない場合（Ｓ４４でＮ）の処理である。Ｓ４６において、代替計画立案部５２は、待ちが発生している地点の近傍に登録された待機地点があるか否かを判断する。代替計画立案部５２は、所定の位置に予め設定された待機地点に関する待機地点データを参照し、待ちの生じる訪問地点と所定の位置関係を有する待機地点を検索し、検索された待機地点に配車車両を一時待機させるように代替計画を立案する(Ｓ４７)。この代替計画においては、デフォルトの待機地点はノードnであるが、遅れが生じる訪問地点（ノードｎ）とその直前に訪問が計画されている訪問地点（ノードｎ−１）との間に位置する待機地点を検索し、検索された待機地点とその待機地点における待機時間を提示する。訪問地点（ノードｎ）と訪問地点（ノードｎ−１）との間に適当な待機地点がない場合は、ノードｎに最も近い待機地点を検索する。なお、待機地点は、車両が駐停車できる場所であって、待機地点の名称、住所、経度緯度が予め対応づけて記憶されている。
【００４５】
Ｓ４７において立案された代替計画は、出力手段６０へ向けて送出される。出力手段６０は待機地点の名称、地図上の位置と、待機時間（何時何分まで）を配車車両に示す。これにより、待機地点が１つの訪問地点（ノード）として巡回ルートに加えられた配車計画を立案することができる。配車車両の運転者は、自ら待機場所を探さなくても安全な場所で待機することができる。
本実施形態の配車計画立案装置１００によれば、待ちを含む配車計画を補正し、待ち時間が短縮乃至解消された最適な配車計画を立案することができる。これにより、巡回時間を短縮された配車計画を立案することができる。この配車計画が送迎に用いられる場合には、待ちが生じる訪問地点以外の地点から乗車したユーザの乗車時間を短縮させることができる。特に、介護者等の送迎などにおいては、長時間の乗車は身体的な負担となる場合があるが、本実施形態の配車計画では待機時間が無いため送迎におけるユーザの負担を軽減させることができる。
【００４６】
一般的な最適化処理を行い、効率的な巡回経路を算出する場合であっても、ユーザが訪問時間帯を特定する場合、どうしても待ちが発生してしまう場合がある。本実施形態によれば、求められた近似解において一部に待ちが発生した場合であっても、待ちが生じてしまった訪問地点について適切な代替計画を立案することにより、配車計画を補正することができる。
【００４７】
なお、以上説明した実施形態は、本発明の理解を容易にするために記載されたものであって、本発明を限定するために記載されたものではない。したがって、上記の実施形態に開示された各要素は、本発明の技術的範囲に属する全ての設計変更や均等物をも含む趣旨である。
【図面の簡単な説明】
【００４８】
【図１】本実施形態の配車計画支援システムのブロック構成図である。
【図２】配車計画立案処理全体の制御手順を示すフローチャート図である。
【図３】配車計画立案処理における組み合わせ最適化処理の制御手順を示すフローチャート図である。
【図４】（Ａ）（Ｂ）は組み合わせ最適化処理を説明するための図である。
【図５】配車計画立案処理における巡回ルートの最適化処理の制御手順を示すフローチャート図である。
【図６】（Ａ）（Ｂ）は巡回ルートの最適化処理を説明するための図である。
【図７】補正処理の制御手順を示すフローチャート図である。
【符号の説明】
【００４９】
１０００・・・配車計画支援システム
１・・・インターネット
２，１００…配車計画立案装置
１０・・・予約情報取得手段
２０・・・訪問地点情報取得手段
３０・・・出発地点情報取得手段
４０・・・配車計画立案手段
４１・・・振り分け部
４２・・・巡回ルート算出部
４３・・・条件確認部
５０・・・補正手段
５１・・・待ち検出部
５２・・・代替計画立案部
５３・・・待機地点指定部
６０・・・出力手段
７０・・・通信機能
３・・・データベース
３ａ・・・訪問地点情報データベース
３ｂ・・・出発地点情報データベース
３ｃ・・・予約情報データベース
４・・・配車側端末
５・・・訪問ユーザ側端末
６・・・車両側端末
【技術分野】
【０００１】
本発明は、配車計画立案装置及び配車計画立案方法に関し、特に、所定の出発点から複数の地点を巡回する際に発生する「待ち」を短縮乃至解消させるように補正された配車計画を立案する配車計画立案装置及び配車計画立案方法に関する。
【背景技術】
【０００２】
車両により複数の地点に居るユーザを送迎するシステムに関し、予め定められた巡回ルートの随所に設定された送迎場所に接近乃至到達した時に、送迎車両の送迎情報を所定の連絡先に通知するものがある（特許文献１参照）。この送迎支援システムによれば、利用者側及び送迎サービス業者側の送迎場所における待ち時間を軽減させることができる。
【０００３】
しかしながら、条件によっては最適な配車計画（解）を求めることができず、待ちが発生してしまうという問題があった。パラメータが多い巡回配送や巡回送迎などの配車計画の最適化は一般に難しいと言われるが、巡回送迎のように、所定の場所に所定の時間（何時何分から何時何分の間）に訪問しなければならないといった時間的な制約条件が課されると配車計画の最適化がいっそう困難になり、待ちが解消されない配車計画が立案されてしまうという問題があった。
【特許文献１】特開２００２−３１２８９６号公報
【発明の開示】
【０００４】
本発明は、以上の課題を鑑みてなされたものであり、立案された配車計画に待ちが発生している場合に、待ち時間が短縮され又は待ちが解消された最適な配車計画を自動的に立案することを目的とする。
本発明によれば、所定の出発地点から出発して、２以上の訪問地点を巡回するための配車計画を立案する装置等であって、取得した訪問時間と訪問地点の位置と出発地点の位置とに基づいて、配車計画を立案し、立案された配車計画において訪問地点を巡回する配車車両に待ちが生じると判断された場合、待ちが生じる訪問地点と出発地点との位置関係に基づいて配車計画を補正する配車計画立案装置及び配車計画立案方法が提供される。
【０００５】
本発明の配車計画立案装置及び配車計画立案方法によれば、立案された配車計画に「待ち」が含まれる場合であっても、発生する「待ち」が解消され又は待ち時間が短縮されるように補正された最適な配車計画を立案することができる。
【発明を実施するための最良の形態】
【０００６】
以下、図面に基づいて、本発明に係る実施形態の配車計画立案装置１００を説明する。本発明の配車計画立案装置１００は、物品の集荷、配送、人の送迎など広く適用可能である。
【０００７】
図１に配車計画立案装置１００を含む配車支援システム１０００の構成の概要を示した。配車支援システム１０００は、配車を行う（集荷、配送、送迎サービスを行う）配車側の端末４、送迎（又は集荷、配送）サービスを受けるユーザ（被送迎者、配送委託者、荷受者）が利用する訪問ユーザ側端末５、配車計画立案装置１００がアクセス可能な予約情報３ｃ、訪問地点情報３ａ、出発地点情報３ｂその他のデータベース、送迎等に用いられる配車車両に搭載された車両側端末６を備える。
【０００８】
この送迎支援システム１０００は、ＡＳＰ（アプリケーション・サービス・プロバイダ）型のシステムとして構築されるものであり、配車計画立案装置１００、配車側端末４、ユーザ側端末５、車両側端末６は、通信ネットワークであるインターネット１にそれぞれ接続する通信機能を備え、相互に情報の送受信を行うことができる。
【０００９】
図１に示すように、本実施形態の配車計画立案装置１００は、予約情報取得手段１０と、訪問地点情報取得手段２０と、出発遅延情報取得手段３０と、配車計画算出手段４０と、補正手段５０と、出力手段６０と、通信機能７０とを有し、所定の出発地点から出発して、２以上の訪問地点を巡回するための配車計画を立案する。具体的には、少なくとも、配車計画を立案するプログラムを格納したＲＯＭ(Read Only Memory)等と、このＲＯＭ等に格納されたプログラムを実行することで、配車計画算出手段４０、補正手段５０として機能するＣＰＵ（Central Processing Unit）等と、アクセス可能な記憶手段として機能するＲＡＭ(Random Access Memory)等とを備えている。
【００１０】
本実施形態の配車計画立案装置１００の各構成について説明する。
「予約情報取得手段１０」は、通信機能７０を介して被送迎者、集荷依頼者、荷受者等を含むユーザが指定した訪問時間を含む予約情報を取得する。本実施形態では、ユーザ側から入力された予約情報を予約情報データベース３ｃに蓄積する。
【００１１】
「訪問地点情報取得手段２０」は、予約をしたユーザが指定する訪問地点の位置（例えば住所）を特定する情報を含む訪問地点情報を、外部又は内部の訪問地点情報データベース３ａから取得する。訪問地点の位置が予約情報に含まれる場合には、予約情報取得手段１０を介して訪問地点の位置情報を取得してもよい。訪問地点の位置情報は、被送迎者の自宅等の訪問地点の位置を住所又は緯度経度により表現された情報である。訪問地点情報データベース３ａにはユーザと対応づけられた各訪問地点の住所情報が記憶されている。住所は住所名緯度経度データベースを検索することにより経度・緯度の値として訪問地点情報データベース３ａに保存される。住所名緯度経度データベースは、県名、市名、丁目、番地、号数、経度緯度が対応づけられた状態で保存されているため、住所名から経度緯度または緯度経度から住所へ変換できる。なお、ユーザの住所（送迎場所）の道幅が狭い場合などは、小型車指定などの属性を含めてもよい。
【００１２】
「出発地点情報取得手段３０」は、予め記憶された出発地点（例えば施設、貨物集配所等）の所在地を含む出発地点情報を取得する。出発地点情報取得手段３０は、装置内又は装置外に設けられた出発地点情報データベース３ｂに記憶された施設情報を取得する。出発地点情報には送迎又は配送に用いられる配車車両の車両情報も含まれる。車両情報は、車両ＩＤ、定員、出発時間、帰着時間を保存したデータベースである。介護施設への送迎ではこれに車両ごとの属性（車椅子の搭載可能台数など）が追加される。なお、ここでは説明の便宜のため、各データベース３ａ、３ｂ、３ｃを分けて説明しているが、これらはハード的に一体に構成されてもよく、配車計画立案装置１００（情報処理サーバ２）の内部に組み込まれていてもよい。
【００１３】
「配車計画立案手段４０」は、所定の出発地点から出発して、２以上の訪問地点を巡回し、出発地点へ戻るための配車計画を立案する。具体的に、配車計画立案手段４０は、振り分け部４１と、巡回ルート算出部４２と、条件確認部４３とを有し、予約情報取得手段１０により取得された「訪問時間」と、予約をしたユーザが指定する「訪問地点の位置」と、予め記憶された「出発地点の位置」とに基づいて配車計画を立案する。本例の配車計画立案手段４０が立案する「配車計画」は、巡回に用いられる車両が特定され、その車両により訪問される地点が特定され、各地点の巡回ルートが特定された計画である。本実施形態において、配車計画を自動的に作成するためのアルゴリズムは限定されない。配車計画立案手段４０は、送迎サービスの予約締め切り時が経過した後又は各配送事業者が集荷・配送サービスの予約締め切り時が経過した後、受け付けた予約情報に基づいて、予約をしたユーザが訪問を希望する訪問地点を特定した後に配車計画を立案する。
【００１４】
本実施形態の配車計画立案手段４０は、振り分け部４１と、巡回ルート算出部４２と、条件確認部４３とを有する。振り分け部４１は、セービングコスト法を用いて、訪問地点をグループごとに振り分けて最適なグループを生成する。巡回ルート算出部４２は、メタヒューリスティック法を用いて生成されたグループについて最適化されたルートを算出する。条件確認部４３は、生成されたグループ、及び算出されたルートが、各地点の巡回に係る制約条件を満たすか否かを判断する。具体的に、条件確認部４３は、グループを構成する送迎対象者の人数が送迎に用いられる車両の定員以下であるか否か、グループを構成する貨物の体積が配送に用いられる車両の積載制限量以下であるか否か、巡回所要時間が所定の制限時間以内であるか否か、介護者を送迎する場合において、車椅子を利用する乗員数（要介護情報に基づいて判断する）が送迎に用いられる車両の車椅子搭載数（施設情報の車両情報に基づいて判断する）以下であるか否かを判断する。
【００１５】
「補正手段５０」は、配車計画立案手段４０により立案された配車計画において訪問地点を巡回する配車車両に待ちが生じると判断した場合、待ちが生じる地点の位置と出発地点との位置関係に基づいて配車計画を補正する。待ちとは、配車車両が指定された訪問時間よりも訪問地点に早く到着してしまう場合に、指定された訪問時間まで待機することをいう。例えば、巡回時間が９時から１０時と規定されている場合に、９時５５分から１０時を訪問時間として指定する訪問地点Ａがあるとすると、訪問地点Ａ以外の訪問地点の巡回が９：５５以前（例えば９：３０）までに終了しても、訪問地点Ａを訪問するには９：５５まで待機しなければならず、この配車計画には「待ち」が発生する。
【００１６】
補正手段５０は待ち検出部５１と、代替計画立案部５２と、待機地点指定部５３とを有する。待ち検出部５１は、立案された配車計画における巡回において配車車両に待ちが生じるか否かを算出し、その結果を代替計画立案部５２へ送出する。
【００１７】
代替計画立案部５２は、待ち検出部５１が巡回において待ちが生じると判断した場合に起動する。代替計画立案部５２は、待ちが生じる訪問地点の位置と出発地点との位置との位置関係に基づいて、待ちが生じる訪問地点に係る代替計画を立案する。補正手段５０は、この代替計画に応じて配車計画の補正を行う。代替計画の内容は特に限定されないが、本実施形態の代替計画立案部５２は、他の車両の位置情報を取得し、取得した他の車両の位置情報に基づいて、待ちが生じる訪問地点を巡回可能な他の車両であって、待ちの生じる訪問地点に指定された訪問時間に訪問することができる他の車両を検索し、検索された車両に待ちが生じる訪問地点を別途訪問させる代替計画を立案する。代替計画立案部５２は、他の車両に搭載されたＧＰＳ機能を用いて検出された自車位置を、通信機能７０を介して取得する。
【００１８】
また、本実施形態の代替計画立案部５２は、待ちが生じる訪問地点を訪問時間内に訪問可能な他の車両が検索されなかった場合、配車車両が待ちの生じる訪問地点に指定された訪問時間に訪問することを条件に、配車車両を待ちが生じる訪問地点をスキップして出発地点へ帰還させてから、待ちが生じる訪問地点を訪問させる代替計画を立案する。
【００１９】
待機地点指定部５３は、待ちが生じる訪問地点を訪問時間内に訪問可能な他の車両が検出されず、配車車両が出発地に戻ってから待ちの生じる訪問地点を訪問すると、待ちが生じる訪問地点に指定された訪問時間に訪問できない場合、所定の位置に予め設定された待機地点に関する待機地点データを参照し、待ちの生じる訪問地点と所定の位置関係を有する待機地点を検索し、検索された待機地点を指定して配車車両を一時待機させる代替計画を立案する。待機地点と訪問地点との所定の位置関係とは、特に限定されないが、両地点間の経路長が所定値以下である位置関係、両地点間の直線距離が所定値以下である位置関係、又は両地点間の経路長若しくは直線距離が最短の位置関係であることが好ましい。
【００２０】
補正手段５０は、代替計画立案部５２により立案された代替計画及び待機地点指定部５３により地点が指定された待機命令に基づいて、配車計画立案手段４０により算出された配車計画を補正する。具体的に、補正手段５０は、待ちが発生している地点について、他の車両による訪問、配車車両による訪問、又は所定の待機地点における待機により、各地点における待ち時間を短縮乃至消滅させる。
【００２１】
補正手段５０により補正された配車計画は、出力手段６０を介して施設側端末４、車両側端末６、ユーザ側端末５等の外部装置に送出される。
【００２２】
次に、本実施形態の配車計画立案装置１００の動作手順を図面に基づいて説明する。図２は配車計画立案処理全体の制御手順を示すフローチャート図、図３は配車計画立案処理における組み合わせ最適化処理の制御手順を示すフローチャート図、図４（Ａ）（Ｂ）は組み合わせ最適化処理を説明するための図、図５は配車計画立案処理における巡回ルートの最適化処理の制御手順を示すフローチャート図、図６（Ａ）（Ｂ）は巡回ルートの最適化処理を説明するための図、図７は補正処理の制御手順を示すフローチャート図である。
【００２３】
まず、図２に基づいて配車計画立案処理の全体概要を説明する。
予約情報取得手段１０は、ユーザから指定された訪問時間（送迎時間、集荷時間、配達時間など）を含む予約情報を取得する（Ｓ１０）。予約情報の取得は、予約締め切り時まで継続する。予約締め切り時経過後、訪問地点情報取得手段２０は予約のあった訪問地点の位置を含む訪問地点情報を取得する（Ｓ１１）。訪問地点情報取得手段２０は、予約情報中のユーザＩＤに基づいて、訪問地点情報データベース３ｃからユーザの住所を訪問地点の位置として読み出してもよい。出発地点情報取得手段３０は配車車両が出発する位置（巡回後に帰着する位置）を含む出発地点情報を取得する（Ｓ１２）。
【００２４】
配車計画立案手段４０は、訪問時間と訪問地点の位置と出発地点の位置とに基づいて配車計画を立案する（Ｓ２０）。配車計画の立案には、グループの組み合わせを最適化する処理と、グループ内の送迎順序を最適化する処理とが含まれる。
【００２５】
補正手段５０は配車計画立案手段４０により立案された配車計画において訪問地点を巡回する配車車両に待ちが発生すると判断された場合、この待ちが生じる訪問地点の位置と出発地点との位置関係に基づいて配車計画を補正する（Ｓ４０）。出力手段６０は補正手段５０により補正された配車計画を外部へ向けて出力する（Ｓ５０）。
【００２６】
次に、配車計画立案処理（図２のＳ２０）のうち、グループの組み合わせを最適化する処理について説明する。配車計画立案手段４０の振り分け部４１は、セービングマトリックスを用いてグループの最適化を行う。
【００２７】
図３にグループの組み合わせを最適化する処理の制御手順を示した。配車計画立案処理の開始（Ｓ２０）に伴い、セービングコスト法を用いた組み合わせ最適化処理を開始する（Ｓ２１）。まず、振り分け部４１は、セービングマトリックスを用いてセービングコストが最大値Sijとなるユーザiとユーザjを取り出す（Ｓ２２）。
【００２８】
本例で用いるマトリックスは、ユーザＡとユーザＢの距離Ｄijを保存したマトリックスである。距離とは道のり（経路長）が適切であるが、計算量を軽減させる観点から、経度緯度から三平方の定理により直線距離を求め、適当な道のりゲインを乗算したものを用いる。これらの値はあらかじめ計算しておく。 セービングマトリックスは、ユーザiとユーザjに対して、出発地（施設）→ユーザi、出発地(施設)→ユーザjをピストン輸送した場合のコスト（図４（Ａ）参照）と、出発地（施設）→ユーザi→ユーザjと循環した場合のコスト（図４（Ｂ）参照）との差をあらわしたもので、D0i*2+D0j*2-(D0j+Dij+Di0)=D0i-Dij+D0j=Sij（セービングコスト）を保持したマトリックスである。
【００２９】
Ｓ２３において、取り出されたユーザの双方ともが、まだどのグループ（ルート）にも振り分けられていない場合（Ｓ２３にてＹｅｓ）、新たなルートを作成してユーザi及びユーザjを割り当てる（Ｓ２４）。
【００３０】
Ｓ２５において、取り出されたユーザの双方ともが、いずれかのグループ（ルート）に振り分けられているか否かを判断する。取り出されたユーザの双方ともがグループ（ルート）に属している場合（Ｓ２５にてＹｅｓ）、合併処理を行う（Ｓ２６）。合併に際しては、合併した両グループ（ルート）が制限時間、制限航続距離、車両定員等の制限条件を満たすことを確認する。つまり、制限条件を満たすと判断された順にグループの合併を行う。制限条件を満たさない場合はグループの合併は行わない。
【００３１】
Ｓ２３において、取り出されたユーザの双方ともがいずれのグループにも属しておらず、Ｓ２５において、双方ともがいずれかのグループに属している場合、すなわち、取り出されたユーザのいずれか一方のみが、いずれかのグループに属している場合（他方はいずれのグループにも属していない場合）、割り当てたグループが制限時間、制限後続距離、車両定員等の制限条件を満たすことを前提に、ユーザの一方が属しているグループ（ルート）に他方のユーザを加える（Ｓ２７）。制限条件を満たさない場合は何も処理しない。
【００３２】
所属グループが決定したユーザのセービングコストには、Ｓｉｊ＝０を代入して次回処理の対象とならないようにする。セービングコストの最大値がゼロ、すなわちＭａｘ（Ｓｉｊ）＝０ならば終了する（Ｓ２８）。
【００３３】
振り分け部４１により振り分けられたグループについて、制限条件を満たすか否かを判断する際に、巡回ルート算出部４２は算出過程における各グループの暫定的な最適ルートを求めて、そのルート上でノードに待ちが発生しないか、到着時間に遅れが生じないかをチェックする。
【００３４】
本例の巡回ルート算出部４２は、メタヒューリスティック法を用いて巡回ルートの最適化を行う。この制御手順を図５に示した。図５には、振り分け部４１の振り分け処理と、巡回ルート算出部４２との巡回ルート算出処理とを組み合わせたフローチャートを示した。ここでは、巡回ルート算出部４２による巡回ルートの算出処理を中心に説明する。
【００３５】
巡回ルートの最適化処理が機能する場合（Ｓ３０）、振り分け部４１はセービングマトリックスを用いてセービングコストが最大値Sijとなるユーザiとユーザjを取り出し巡回ルートのグループを生成する（Ｓ２２〜Ｓ２７）。Ｓ２６にて合併されたグループについて、ＴSP(ルート(Ni)とルート(Nj)）の近似解を求める（Ｓ３１）。同様に、いずれか一方がいずれかのグループに属している場合に、グループに属していない一方のユーザを他方が属するグループに加えたグループ(Ｓ２７)について、ＴSP(ルート(Ni)とルート(Nj)）の近似解を求める（Ｓ３２）。ここで、ＴＳＰ（Traveling Salesman Problem）とは、ノード数とそれぞれのノード間の道のりが判っているときに、ある者がN個のノードを必ず１回だけ通って巡回したとき、総経路長を最短にするような、都市の巡回経路を見つける問題である。本例では、この近似最適解を求めるためにメタヒューリスティック解法を用いる。
【００３６】
仮の送迎順番が図６（Ａ)に示すものであったとして、本例における解法の一例を以下に説明する。
【００３７】
１）適当な2つのノードを選んでその順番を入れ替える（図６（Ｂ））。
２）遅れが発生していた場合はその遅れがどれだけ小さくなるかのΔｄを計算する。
３）すべての２つのノードの組み合わせに対してΔｄを計算する。
４）Ｍａｘ（Δｄ）を与える２つのノードを実際に取り替える。
５）遅れが発生していない場合は、その２つのノードを取り替えたときに最終到着時間どれだけ早くなるかのΔaを計算する。
６）すべての２つのノードの組み合わせに対してΔaを計算する。
７）Ｍａｘ（Δa）を与える２つのノードを実際に取り替える。
なお、「待ち」は最終到着時間の最小化と言う形で結果的に解消される方向にあるが、もし「待ち」が最後のノードになった場合はそれ以上の短縮は不可能となる。また、この処理により「遅れ」は積極的に解消される。
【００３８】
時間の観点から最適化されたグループについて、訪問時間、車両の定員数、車両の設備（車椅子の搭載能力、車椅子からの搭乗補助機能）に基づく制限が満たされたか否か、つまり巡回ルートが適切であるか否かを判断する（Ｓ３３）。その後、セービングコストの最大値がゼロ、すなわちＭａｘ（Ｓｉｊ）＝０ならば終了する（Ｓ２８）。
【００３９】
配車計画立案手段（４０）により立案された配車計画について、補正手段５０は補正を行う。補正手段５０は、立案された配車計画において訪問地点を巡回する配車車両に待ちが生じると判断された場合、配車計画の補正を行う。本例の補正手段５０は、待ちが生じる訪問地点の位置と出発地点の位置との位置関係に基づいて配車計画を補正する。
【００４０】
図７は補正処理の制御手順を示すフローチャート図である。
補正処理が開始すると（Ｓ４０）、待ち検出部５１は配車計画において配車車両に待ちが発生しているか否かを判断する（Ｓ４１）。待ちが発生していない場合は補正をする必要がないためＳ５０の出力処理へ進む。待ちが発生している場合にはＳ４２に進む。待ちが発生している場合、代替計画立案部５２は待ち時間を短縮乃至消滅させる代替計画を立案する。
【００４１】
Ｓ４２において、代替計画立案部５２は、他の車両の位置情報を取得し、取得した他の車両の位置情報に基づいて、待ちが生じる訪問地点を訪問可能な他の車両であって、待ちの生じる訪問地点に指定された訪問時間に訪問することができる他の車両を検索する(Ｓ４２)。具体的に代替計画立案部５２は、他の車両の位置情報が出発地点の位置である場合、他の車両は出発地点に帰還しており、待ちが生じる訪問地点にすぐに訪問できると判断する。さらに代替計画立案部５２は、他の車両の位置情報と待ちが生じる訪問地点の位置情報との経路長を求め、この経路長と車両の平均速度とから、この他の車両が待ちの生じる訪問地点に指定された訪問時間内に訪問できるか否かを判断する。つまり、他の車両が出発地点に所在し、かつ出発地点から遅れが生じる訪問地点までの所要時間が、現在時刻から訪問時刻までの時間よりも短いか否かを判断する。
【００４２】
Ｓ４２において、条件を満たす他の車両が検索された場合、代替計画立案部５２は検索された車両に待ちが生じる訪問地点を別途訪問させる代替計画を立案する（Ｓ４３）。Ｓ４２にて検索された車両を代替計画用の車両として配車する。この車両に遅れが生じた訪問地点の訪問（送迎、集荷）を任せ、訪問するはずであった配車車両はこの訪問地点をスキップして出発地点（帰着地点）へ戻る。配車車両は待機することなく出発地点（帰着地点）へ戻ることができる。これにより、巡回に要する時間を短縮させることができる。最適化された配車計画では、最後に巡回する訪問地点に待ちが発生する傾向がある。また、最後に巡回する訪問地点は、出発地点に近い位置にある傾向がある。本実施形態の代替計画によれば、遅れの生じる訪問地点近傍（例えば出発地点）に位置する他車両が、出発地点に近い訪問地点へ訪問するため、補正により新たに生じるコストを抑制することができる。つまり、すべての訪問地点を巡回するために要する総コストを低く抑えることができる。Ｓ４２において、条件を満たす他の車両を検索できなかった場合は、Ｓ４４へ進む。
【００４３】
Ｓ４４において、代替計画立案部５２は、配車車両が出発地点へ一度帰着してから待ちが発生している地点に指定された訪問時間内に到着できるか否かを判断する。つまり、代替計画立案部５２は、配車車両が待ちの生じる訪問地点に指定された訪問時間内に戻れるか否か判断する。具体的に、代替計画立案部５２は、遅れが生じる訪問地点から出発地点に一度帰着し再度出発して、訪問地点へ到着する予想到着時間｛ (D0n-1+D0n)/平均時速＋出発地点でユーザを降車させるのに要する時間｝（ただし、Ｄ0nは遅れが生じる訪問地点と出発地点との距離、Ｄ0n-1は遅れが生じる訪問地点の１つ手前の訪問地点と出発地点との距離）が、現在時刻から遅れの生じる訪問地点（ｎ）について指定された訪問時間までの時間以下であるか否かを判断する。配車車両が待ちの生じる訪問地点に訪問時間内に戻れる場合、代替計画立案部５２は、待ちが生じる訪問地点をスキップしてその１つ手前の訪問地点から出発地点へ向かってから、待ちが生じる訪問地点を訪問する代替計画を立案する（Ｓ４５）。これにより、巡回に要する時間を短縮させることができる。最適化された配車計画では、最後に巡回する訪問地点に待ちが発生する傾向がある。また、最後に巡回する訪問地点は、出発地点に近い位置にある傾向がある。本実施形態の代替計画によれば、配車車両が一旦出発地点に戻ってから遅れの生じる訪問地点を巡回するため、補正により新たに生じるコストを抑制することができる。つまり、すべての訪問地点を巡回するために要する総コストを低く抑えることができる。他方、Ｓ４４において、配車車両が条件を満たさない場合は、Ｓ４６へ進む。
【００４４】
Ｓ４６は、待ちが生じる訪問地点を訪問時間内に訪問可能な他の車両が検出されず（Ｓ４２でＮ）、配車車両が出発地点に戻ってから待ちの生じる訪問地点を訪問すると、待ちが生じる訪問地点に指定された訪問時間に訪問できない場合（Ｓ４４でＮ）の処理である。Ｓ４６において、代替計画立案部５２は、待ちが発生している地点の近傍に登録された待機地点があるか否かを判断する。代替計画立案部５２は、所定の位置に予め設定された待機地点に関する待機地点データを参照し、待ちの生じる訪問地点と所定の位置関係を有する待機地点を検索し、検索された待機地点に配車車両を一時待機させるように代替計画を立案する(Ｓ４７)。この代替計画においては、デフォルトの待機地点はノードnであるが、遅れが生じる訪問地点（ノードｎ）とその直前に訪問が計画されている訪問地点（ノードｎ−１）との間に位置する待機地点を検索し、検索された待機地点とその待機地点における待機時間を提示する。訪問地点（ノードｎ）と訪問地点（ノードｎ−１）との間に適当な待機地点がない場合は、ノードｎに最も近い待機地点を検索する。なお、待機地点は、車両が駐停車できる場所であって、待機地点の名称、住所、経度緯度が予め対応づけて記憶されている。
【００４５】
Ｓ４７において立案された代替計画は、出力手段６０へ向けて送出される。出力手段６０は待機地点の名称、地図上の位置と、待機時間（何時何分まで）を配車車両に示す。これにより、待機地点が１つの訪問地点（ノード）として巡回ルートに加えられた配車計画を立案することができる。配車車両の運転者は、自ら待機場所を探さなくても安全な場所で待機することができる。
本実施形態の配車計画立案装置１００によれば、待ちを含む配車計画を補正し、待ち時間が短縮乃至解消された最適な配車計画を立案することができる。これにより、巡回時間を短縮された配車計画を立案することができる。この配車計画が送迎に用いられる場合には、待ちが生じる訪問地点以外の地点から乗車したユーザの乗車時間を短縮させることができる。特に、介護者等の送迎などにおいては、長時間の乗車は身体的な負担となる場合があるが、本実施形態の配車計画では待機時間が無いため送迎におけるユーザの負担を軽減させることができる。
【００４６】
一般的な最適化処理を行い、効率的な巡回経路を算出する場合であっても、ユーザが訪問時間帯を特定する場合、どうしても待ちが発生してしまう場合がある。本実施形態によれば、求められた近似解において一部に待ちが発生した場合であっても、待ちが生じてしまった訪問地点について適切な代替計画を立案することにより、配車計画を補正することができる。
【００４７】
なお、以上説明した実施形態は、本発明の理解を容易にするために記載されたものであって、本発明を限定するために記載されたものではない。したがって、上記の実施形態に開示された各要素は、本発明の技術的範囲に属する全ての設計変更や均等物をも含む趣旨である。
【図面の簡単な説明】
【００４８】
【図１】本実施形態の配車計画支援システムのブロック構成図である。
【図２】配車計画立案処理全体の制御手順を示すフローチャート図である。
【図３】配車計画立案処理における組み合わせ最適化処理の制御手順を示すフローチャート図である。
【図４】（Ａ）（Ｂ）は組み合わせ最適化処理を説明するための図である。
【図５】配車計画立案処理における巡回ルートの最適化処理の制御手順を示すフローチャート図である。
【図６】（Ａ）（Ｂ）は巡回ルートの最適化処理を説明するための図である。
【図７】補正処理の制御手順を示すフローチャート図である。
【符号の説明】
【００４９】
１０００・・・配車計画支援システム
１・・・インターネット
２，１００…配車計画立案装置
１０・・・予約情報取得手段
２０・・・訪問地点情報取得手段
３０・・・出発地点情報取得手段
４０・・・配車計画立案手段
４１・・・振り分け部
４２・・・巡回ルート算出部
４３・・・条件確認部
５０・・・補正手段
５１・・・待ち検出部
５２・・・代替計画立案部
５３・・・待機地点指定部
６０・・・出力手段
７０・・・通信機能
３・・・データベース
３ａ・・・訪問地点情報データベース
３ｂ・・・出発地点情報データベース
３ｃ・・・予約情報データベース
４・・・配車側端末
５・・・訪問ユーザ側端末
６・・・車両側端末
【特許請求の範囲】
【請求項１】
所定の出発地点から出発して、２以上の訪問地点を巡回するための配車計画を立案する配車計画立案装置であって、
前記各訪問地点を訪問する訪問時間を含む予約情報を取得する予約情報取得手段と、
前記各訪問地点の位置を含む情報を取得する訪問地点情報取得手段と、
前記出発地点の位置を含む情報を取得する出発地点情報取得手段と、
前記訪問時間と訪問地点の位置と出発地点の位置とに基づいて、配車計画を立案する配車計画立案手段と、
前記配車計画立案手段により立案された配車計画において前記訪問地点を巡回する配車車両に待ちが生じると判断された場合、当該待ちが生じる訪問地点と前記出発地点との位置関係に基づいて前記配車計画を補正する補正手段と、を有する配車計画立案装置。
【請求項２】
前記補正手段は、前記配車計画立案手段により立案された配車計画において前記訪問地点を巡回する配車車両に待ちが生じると判断した場合、他の車両の位置情報を取得し、取得した他の車両の位置情報に基づいて、当該待ちが生じる訪問地点を訪問可能な他の車両であって、前記待ちの生じる訪問地点に指定された訪問時間に訪問することができる他の車両を検索し、検索された車両に待ちが生じる訪問地点を別途訪問させるように配車計画を補正する請求項１に記載の配車計画立案装置。
【請求項３】
前記補正手段は、前記待ちが生じる訪問地点を訪問時間内に訪問可能な他の車両が検索されなかった場合、前記配車車両が前記待ちの生じる訪問地点に指定された訪問時間に訪問することを条件に、前記待ちが生じる訪問地点をスキップして出発地点へ向かってから、待ちが生じる訪問地点を訪問するように配車計画を補正する請求項２に記載の配車計画立案装置。
【請求項４】
前記補正手段は、前記待ちが生じる訪問地点を訪問時間内に訪問可能な他の車両が検出されず、前記配車車両が出発地点へ戻ってから待ちの生じる訪問地点を再度訪問すると、当該待ちが生じる訪問地点に指定された訪問時間に訪問できない場合、所定の位置に予め設定された待機地点に関する待機地点データを参照し、前記待ちの生じる訪問地点と所定の位置関係を有する待機地点を検索し、検索された待機地点に前記配車車両を一時待機させるように配車計画を補正する請求項３に記載の配車計画立案装置。
【請求項５】
所定の出発地点から出発して、２以上の訪問地点を巡回するための配車計画を立案する配車計画立案方法であって、
前記各訪問地点を訪問する訪問時間を含む予約情報を取得するステップと、
前記各訪問地点の位置を含む情報を取得するステップと、
前記出発地点の位置を含む情報を取得するステップと、
前記訪問時間と訪問地点の位置と出発地点の位置とに基づいて、配車計画を立案するステップと、
前記立案された配車計画において前記訪問地点を巡回する配車車両に待ちが生じると判断された場合、当該待ちが生じる訪問地点と前記出発地点との位置関係に基づいて前記配車計画を補正するステップと、を有する配車計画立案方法。
【請求項６】
前記補正をするステップは、前記立案された配車計画において前記訪問地点を巡回する配車車両に待ちが生じると判断した場合、他の車両の位置情報を取得し、取得した他の車両の位置情報に基づいて、当該待ちが生じる訪問地点を訪問可能な他の車両であって、前記待ちの生じる訪問地点に指定された訪問時間に訪問することができる他の車両を検索し、検索された車両に待ちが生じる訪問地点を別途訪問させるように配車計画を補正する請求項５に記載の配車計画立案方法。
【請求項７】
前記補正をするステップは、前記待ちが生じる訪問地点を訪問時間内に訪問可能な他の車両が検索されなかった場合、前記配車車両が前記待ちの生じる訪問地点に指定された訪問時間に訪問することを条件に、前記待ちが生じる訪問地点をスキップして出発地点へ向かってから待ちが生じる訪問地点を訪問するように配車計画を補正する請求項６に記載の配車計画立案方法。
【請求項８】
前記補正をするステップは、前記待ちが生じる訪問地点を訪問時間内に訪問可能な他の車両が検出されず、前記配車車両が出発地点に戻ってから待ちの生じる訪問地点を訪問すると、当該待ちが生じる訪問地点に指定された訪問時間に訪問できない場合、所定の位置に予め設定された待機地点に関する待機地点データを参照し、前記待ちの生じる訪問地点と所定の位置関係を有する待機地点を検索し、検索された待機地点に前記配車車両を一時待機させるように配車計画を補正する請求項７に記載の配車計画立案方法。
【請求項１】
所定の出発地点から出発して、２以上の訪問地点を巡回するための配車計画を立案する配車計画立案装置であって、
前記各訪問地点を訪問する訪問時間を含む予約情報を取得する予約情報取得手段と、
前記各訪問地点の位置を含む情報を取得する訪問地点情報取得手段と、
前記出発地点の位置を含む情報を取得する出発地点情報取得手段と、
前記訪問時間と訪問地点の位置と出発地点の位置とに基づいて、配車計画を立案する配車計画立案手段と、
前記配車計画立案手段により立案された配車計画において前記訪問地点を巡回する配車車両に待ちが生じると判断された場合、当該待ちが生じる訪問地点と前記出発地点との位置関係に基づいて前記配車計画を補正する補正手段と、を有する配車計画立案装置。
【請求項２】
前記補正手段は、前記配車計画立案手段により立案された配車計画において前記訪問地点を巡回する配車車両に待ちが生じると判断した場合、他の車両の位置情報を取得し、取得した他の車両の位置情報に基づいて、当該待ちが生じる訪問地点を訪問可能な他の車両であって、前記待ちの生じる訪問地点に指定された訪問時間に訪問することができる他の車両を検索し、検索された車両に待ちが生じる訪問地点を別途訪問させるように配車計画を補正する請求項１に記載の配車計画立案装置。
【請求項３】
前記補正手段は、前記待ちが生じる訪問地点を訪問時間内に訪問可能な他の車両が検索されなかった場合、前記配車車両が前記待ちの生じる訪問地点に指定された訪問時間に訪問することを条件に、前記待ちが生じる訪問地点をスキップして出発地点へ向かってから、待ちが生じる訪問地点を訪問するように配車計画を補正する請求項２に記載の配車計画立案装置。
【請求項４】
前記補正手段は、前記待ちが生じる訪問地点を訪問時間内に訪問可能な他の車両が検出されず、前記配車車両が出発地点へ戻ってから待ちの生じる訪問地点を再度訪問すると、当該待ちが生じる訪問地点に指定された訪問時間に訪問できない場合、所定の位置に予め設定された待機地点に関する待機地点データを参照し、前記待ちの生じる訪問地点と所定の位置関係を有する待機地点を検索し、検索された待機地点に前記配車車両を一時待機させるように配車計画を補正する請求項３に記載の配車計画立案装置。
【請求項５】
所定の出発地点から出発して、２以上の訪問地点を巡回するための配車計画を立案する配車計画立案方法であって、
前記各訪問地点を訪問する訪問時間を含む予約情報を取得するステップと、
前記各訪問地点の位置を含む情報を取得するステップと、
前記出発地点の位置を含む情報を取得するステップと、
前記訪問時間と訪問地点の位置と出発地点の位置とに基づいて、配車計画を立案するステップと、
前記立案された配車計画において前記訪問地点を巡回する配車車両に待ちが生じると判断された場合、当該待ちが生じる訪問地点と前記出発地点との位置関係に基づいて前記配車計画を補正するステップと、を有する配車計画立案方法。
【請求項６】
前記補正をするステップは、前記立案された配車計画において前記訪問地点を巡回する配車車両に待ちが生じると判断した場合、他の車両の位置情報を取得し、取得した他の車両の位置情報に基づいて、当該待ちが生じる訪問地点を訪問可能な他の車両であって、前記待ちの生じる訪問地点に指定された訪問時間に訪問することができる他の車両を検索し、検索された車両に待ちが生じる訪問地点を別途訪問させるように配車計画を補正する請求項５に記載の配車計画立案方法。
【請求項７】
前記補正をするステップは、前記待ちが生じる訪問地点を訪問時間内に訪問可能な他の車両が検索されなかった場合、前記配車車両が前記待ちの生じる訪問地点に指定された訪問時間に訪問することを条件に、前記待ちが生じる訪問地点をスキップして出発地点へ向かってから待ちが生じる訪問地点を訪問するように配車計画を補正する請求項６に記載の配車計画立案方法。
【請求項８】
前記補正をするステップは、前記待ちが生じる訪問地点を訪問時間内に訪問可能な他の車両が検出されず、前記配車車両が出発地点に戻ってから待ちの生じる訪問地点を訪問すると、当該待ちが生じる訪問地点に指定された訪問時間に訪問できない場合、所定の位置に予め設定された待機地点に関する待機地点データを参照し、前記待ちの生じる訪問地点と所定の位置関係を有する待機地点を検索し、検索された待機地点に前記配車車両を一時待機させるように配車計画を補正する請求項７に記載の配車計画立案方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【公開番号】特開２００６−２５２０６５（Ｐ２００６−２５２０６５Ａ）
【公開日】平成１８年９月２１日（２００６．９．２１）
【国際特許分類】
【出願番号】特願２００５−６６２２８（Ｐ２００５−６６２２８）
【出願日】平成１７年３月９日（２００５．３．９）
【出願人】（０００００３９９７）日産自動車株式会社 (16,386)
【Ｆターム（参考）】
【公開日】平成１８年９月２１日（２００６．９．２１）
【国際特許分類】
【出願日】平成１７年３月９日（２００５．３．９）
【出願人】（０００００３９９７）日産自動車株式会社 (16,386)
【Ｆターム（参考）】
[ Back to top ]