(57)【要約】【課題】複数の配送指定時間を持つ積荷が含まれている配送計画問題に対して、効率的な車両運行計画の作成を可能にする。【解決手段】複数の配送時間が指定された積荷に対して、前処理である部分解作成処理において、積み合せが可能な他の積荷との積み合せパターンを複数作成し、作成されたパターンの中から使用する車両台数が最小となる積み合せを選択する。選択された積み合せに基づいて積荷の配送指定時間を決定し、部分解集合を作成する。作成された部分解集合と残りの積荷とを含めて、最適運行計画作成処理にて、配送コスト最小となる車両運行計画を作成する。【選択図】図４
2013133198.tif 000002
【特許請求の範囲】
【請求項１】
１ヶ所以上の配送拠点で集荷作業を行い、複数の納入先に配送する車両の運行計画を作成する装置であって、
複数の配送時間が指定された積荷を含む積荷に関するデータである配送オーダデータ、配送を行う車両に関する車両マスタデータ、顧客である納入先に関するデータである納入先マスタ、納入先に対して複数の配送時間が定義されているデータである配送枠マスタ、配送拠点から納入先、納入先間、配送拠点間の距離と走行速度に関するデータである距離マスタデータ、配送コストに関するデータである運賃マスタを読み込むデータ読み込み手段と、
複数の配送時間が指定された積荷に対して、予め積み合せが可能な他の積荷との積み合せパターンを複数作成し、作成されたパターンの中から使用する車両台数が最小となる積み合せを選択する部分解作成手段と、
該部分解作成手段で選択された積み合せに基づいて積荷の配送指定時間を決定し、部分解集合を作成する部分解集合作成手段と、
該部分解集合作成手段で求められた部分解集合と残りの積荷とを含めて、配送コスト最小となる車両運行計画を作成する最適運行計画作成手段と、
該最適運行計画作成手段によって作成された運行計画を出力する、結果データ出力手段とを備えたことを特徴とする車両運行計画作成装置。
【請求項２】
１ヶ所以上の配送拠点で集荷作業を行い、複数の納入先に配送する車両の運行計画をコンピュータを用いて作成する方法であって、
データ読み込み手段が、複数の配送時間が指定された積荷を含む積荷に関するデータである配送オーダデータ、配送を行う車両に関する車両マスタデータ、顧客である納入先に関するデータである納入先マスタ、納入先に対して複数の配送時間が定義されているデータである配送枠マスタ、配送拠点から納入先、納入先間、配送拠点間の距離と走行速度に関するデータである距離マスタデータ、配送コストに関するデータである運賃マスタを読み込み、
部分解作成手段が、複数の配送時間が指定された積荷に対して、予め積み合せが可能な他の積荷との積み合せパターンを複数作成し、作成されたパターンの中から使用する車両台数が最小となる積み合せを選択し、
部分解集合作成手段が、前記部分解作成手段で選択された積み合せに基づいて積荷の配送指定時間を決定し、部分解集合を作成し、
最適運行計画作成手段が、前記部分解集合作成手段で求められた部分解集合と残りの積荷とを含めて、配送コスト最小となる車両運行計画を作成し、
結果データ出力手段が、前記最適運行計画作成手段によって作成された運行計画を出力することを特徴とする車両運行計画作成方法。
【請求項３】
１ヶ所以上の配送拠点で集荷作業を行い、複数の納入先に配送する車両の運行計画を作成するためのプログラムであって、
コンピュータに、
複数の配送時間が指定された積荷を含む積荷に関するデータである配送オーダデータ、配送を行う車両に関する車両マスタデータ、顧客である納入先に関するデータである納入先マスタ、納入先に対して複数の配送時間が定義されているデータである配送枠マスタ、配送拠点から納入先、納入先間、配送拠点間の距離と走行速度に関するデータである距離マスタデータ、配送コストに関するデータである運賃マスタを読み込むデータ読み込み処理を行わせ、
複数の配送時間が指定された積荷に対して、予め積み合せが可能な他の積荷との積み合せパターンを複数作成させ、作成されたパターンの中から使用する車両台数が最小となる積み合せを選択する部分解作成処理を行わせ、
該部分解作成処理で選択された積み合せに基づいて積荷の配送指定時間を決定し、部分解集合を作成する部分解集合作成処理を行わせ、
該部分解集合作成処理で求められた部分解集合と残りの積荷とを含めて、配送コスト最小となる車両運行計画を作成する最適運行計画作成処理を行わせ、
該最適運行計画作成処理によって作成された運行計画を出力する、結果データ出力処理を行わせるよう機能させる車両運行計画作成用プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、製造・流通業などにおける配送拠点（倉庫、工場、物流センター）に保管される製品などの運送物を、配送拠点で保有するトラック、トレーラなどの輸送手段により効率的に納入先へ配送するための車両運行計画技術に関するものである。
【背景技術】
【０００２】
近年、物流の効率化・コスト削減を求める気運が高まっている。このような気運の高まりに対して、配車計画の自動作成や作成支援を行う為の技術や装置が、種々見受けられる様になってきている。物流システムでの輸送スケジュール作成技術は、いわゆる巡回セールスマン問題やビークルルーティング問題に相当し、一定地域内に存在する顧客先の効率的な巡回計画を作成する技術がすでに開発されている。
【０００３】
これらの技術の中で特に時間指定配達に対応して効率的な配送を行うものとされている技術として、以下が開示されている。
【０００４】
即ち、特許文献１には、配車計画作成装置の車両情報記録手段が、車両を担当地区と共に記録し、訪問箇所情報記録手段が、主訪問箇所を住所、訪問制限時刻、作業時間、先行箇所の住所、訪問制限時刻及び作業時間と共に記録し、車両抽出手段が、車両情報記録手段から特定の車両を抽出し、配車手段が、訪問箇所情報記録手段から車両の担当地区内に所在する主訪問箇所を１件ずつ先行箇所と共に読み出し、住所に基づいて設定した経路で移動して各訪問箇所で作業を行った場合に主訪問箇所及び先行箇所の訪問制限時刻が満足されるときに主訪問箇所及び先行箇所を配車計画に組み込む作業を繰り返して抽出した車両の配車計画を作成する技術が記載されている。
【０００５】
特許文献２には、集配ルート設定装置が、集配情報テーブルから到着時間指定有の集配物に関する集配情報を抽出し、抽出された集配情報と道路交通情報及び地図情報を用いて、到着時間指定有の集配物が指定された時間前に到着可能なルートを検索し、初期ルートを設定し、次に、集配情報テーブルから到着時間指定無の集配物に関する集配情報を抽出し、抽出された集配情報と道路交通情報及び地図情報を用いて、初期ルート上の各区間の余裕時間を算出し、余裕時間内に配送可能な到着時間指定無の集配物を検索し、検出された集配物の集配を初期ルートに組込み、初期ルートを設定する技術が記載されている。
【０００６】
特許文献３には、配送時刻を設定するための表と作業先を示す表とをクライアントの同一画面に表示させ、マウスの指定で２つの表の中の任意の位置を指定することで、作業先への配送時刻と、作業先とを互いに関連付ける技術が記載されている。
【０００７】
特許文献４には、複数の配送拠点で集荷作業を行い、複数の納入先に配送する車両の運行計画を作成する方法において、運ぶべき荷物に関するデータすなわち配送オーダデータの入力および選択を促す計画作成データの選択処理工程と、前記配送オーダデータ、車両運行計画作成に必要なマスタデータおよび探索順と探索方法を示した探索シナリオを読み込むデータ読み込み処理工程と、各車両が得る車両収入と、各車両を運用する際にかかる車両運用コストとの差を合計したものを目的関数とし、該目的関数を最大化する探索処理を用い、前記配送オーダデータと前記マスタデータから前記探索シナリオに基づき、車両運行計画を作成する最適運行計画作成処理工程と、作成した車両運行計画を出力するための車両運行計画出力工程と、を有する技術が記載されている。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】特許第４５２１００４号公報
【特許文献２】特許第４３２２１５６号公報
【特許文献３】特開２００４−６２６８１号公報
【特許文献４】特開２００５−１２２６７９号公報
【非特許文献】
【０００９】
【非特許文献１】「混合整数計画法（MIP）を使おう：モデル化の実際とその背景」、数理モデル研究所、野末尚次、ILOG Optimization Seminar資料、http://www.math-model.co．jp/ILOG_OPT_Seminer_2006_Rev.pdf
【発明の概要】
【発明が解決しようとする課題】
【００１０】
近年、近隣道路の渋滞緩和、積荷の卸し作業を効率的に行うため、積荷に１つの限定した配送指定時間を付けるのではなく、配送時間枠を指定し、指定された配送時間枠内のいくつかの配送指定時間を、配送側に選択させる納入方法が存在する。
【００１１】
しかしながら、特許文献１〜４に開示されている技術においては、配送指定時間は１つ、もしくは時間帯内に限られており、複数の配送指定時間が指定されている場合に対して対応することが出来ないという問題があった。
【００１２】
ここで、複数の配送時間指定がなされている場合とは、図１に示すような場合である。
【００１３】
図１の例では、各配送枠１、２・・・の中に配送できる時間が３つあり、３つの配送指定時間の何れかの配送時間に納入する。この例では、荷に対しての配送時間指定は配送枠のみが指定される。
【００１４】
以上のような場合で、Ａ社配送枠１指定の荷１０ｔ、Ｂ社配送枠１指定の荷が同様に１０ｔ、それぞれの卸時間が２０分、Ａ社からＢ社までの移動時間が６０分とした場合、積載可能重量が２０ｔのトラック１台で配送することを考えると、図２に示すように、積み合せのパターン１、パターン２の２通りが考えられる。また、１つの配送時間指定がされているＣ社の荷（１０ｔ、配送指定時間９：００、Ｂ社からＣ社までの移動時間６０分）と積み合わせるパターン３も考えられる。
【００１５】
以上の例のように、複数の配送指定時間を持った荷が含まれた配送問題では、配送指定時間の選び方によっては、非効率な配送計画となる場合がある。例えば、「Ａ社の荷７：００、Ｂ社の荷７：３０とした場合、トラックが２台必要となる。」等である。
【００１６】
このように、複数の配送指定時間を持つ荷を含んだ配送問題では、複数の配送指定時間より、効率的な積み合わせパターンを作成する必要があるが、従来は、このような要請を満足することができなかった。
【００１７】
本発明は前記従来の問題を解決するべくなされたもので、複数の配送指定時間を持つ積荷が含まれている配送計画問題に対して、効率的な車両運行計画の作成を可能にすることを課題とする。
【課題を解決するための手段】
【００１８】
本発明は、１ヶ所以上の配送拠点で集荷作業を行い、複数の納入先に配送する車両の運行計画を作成する装置であって、複数の配送時間が指定された積荷を含む積荷に関するデータである配送オーダデータ、配送を行う車両に関する車両マスタデータ、顧客である納入先に関するデータである納入先マスタ、納入先に対して複数の配送時間が定義されているデータである配送枠マスタ、配送拠点から納入先、納入先間、配送拠点間の距離と走行速度に関するデータである距離マスタデータ、配送コストに関するデータである運賃マスタを読み込むデータ読み込み手段と、複数の配送時間が指定された積荷に対して、予め積み合せが可能な他の積荷との積み合せパターンを複数作成し、作成されたパターンの中から使用する車両台数が最小となる積み合せを選択する部分解作成手段と、該部分解作成手段で選択された積み合せに基づいて積荷の配送指定時間を決定し、部分解集合を作成する部分解集合作成手段と、該部分解集合作成手段で求められた部分解集合と残りの積荷とを含めて、配送コスト最小となる車両運行計画を作成する最適運行計画作成手段と、該最適運行計画作成手段によって作成された運行計画を出力する、結果データ出力手段とを備えたことを特徴とする車両運行計画作成装置により前記課題を解決したものである。
【００１９】
本発明は、又、１ヶ所以上の配送拠点で集荷作業を行い、複数の納入先に配送する車両の運行計画をコンピュータを用いて作成する方法であって、データ読み込み手段が、複数の配送時間が指定された積荷を含む積荷に関するデータである配送オーダデータ、配送を行う車両に関する車両マスタデータ、顧客である納入先に関するデータである納入先マスタ、納入先に対して複数の配送時間が定義されているデータである配送枠マスタ、配送拠点から納入先、納入先間、配送拠点間の距離と走行速度に関するデータである距離マスタデータ、配送コストに関するデータである運賃マスタを読み込み、部分解作成手段が、複数の配送時間が指定された積荷に対して、予め積み合せが可能な他の積荷との積み合せパターンを複数作成し、作成されたパターンの中から使用する車両台数が最小となる積み合せを選択し、部分解集合作成手段が、前記部分解作成手段で選択された積み合せに基づいて積荷の配送指定時間を決定し、部分解集合を作成し、最適運行計画作成手段が、前記部分解集合作成手段で求められた部分解集合と残りの積荷とを含めて、配送コスト最小となる車両運行計画を作成し、結果データ出力手段が、前記最適運行計画作成手段によって作成された運行計画を出力することにより前記課題を解決したものである。
【００２０】
本発明は、又、１ヶ所以上の配送拠点で集荷作業を行い、複数の納入先に配送する車両の運行計画を作成するためのプログラムであって、コンピュータに、複数の配送時間が指定された積荷を含む積荷に関するデータである配送オーダデータ、配送を行う車両に関する車両マスタデータ、顧客である納入先に関するデータである納入先マスタ、納入先に対して複数の配送時間が定義されているデータである配送枠マスタ、配送拠点から納入先、納入先間、配送拠点間の距離と走行速度に関するデータである距離マスタデータ、配送コストに関するデータである運賃マスタを読み込むデータ読み込み処理を行わせ、複数の配送時間が指定された積荷に対して、予め積み合せが可能な他の積荷との積み合せパターンを複数作成させ、作成されたパターンの中から使用する車両台数が最小となる積み合せを選択する部分解作成処理を行わせ、該部分解作成処理で選択された積み合せに基づいて積荷の配送指定時間を決定し、部分解集合を作成する部分解集合作成処理を行わせ、該部分解集合作成処理で求められた部分解集合と残りの積荷とを含めて、配送コスト最小となる車両運行計画を作成する最適運行計画作成処理を行わせ、該最適運行計画作成処理によって作成された運行計画を出力する、結果データ出力処理を行わせるよう機能させる車両運行計画作成用プログラムにより前記課題を解決したものである。
【発明の効果】
【００２１】
本発明によれば、複数の配送指定時間を持つ積荷が含まれている配送計画問題に対して、効率的な車両運行計画の作成が可能になる。
【図面の簡単な説明】
【００２２】
【図１】複数配送時刻の指定例を示す図
【図２】積み合わせのパターンの例を示す図
【図３】本発明の実施形態を実施するための装置を示す図
【図４】前記実施形態における処理手順を示す流れ図
【図５】前記実施形態で用いる配送オーダデータ項目例を示す図
【図６】同じく車両マスタ項目例を示す図
【図７】同じく距離マスタ項目例を示す図
【図８】同じく納入先マスタ項目例を示す図
【図９】同じく運賃マスタ項目例を示す図
【図１０】同じく配送枠マスタ項目例を示す図
【図１１】同じく決定変数Ｘ［ｉ］［ｊ］の例を示す図
【図１２】同じく指定時間ＩＤの定義の例を示す図
【図１３】同じく定数行列ｃＦＴ［ｉ］［ｊ］の例を示す図
【図１４】同じく決定変数Ｙ［ｋ］［ｊ］の例を示す図
【図１５】同じく積み合せパターン行列ｃＬＤＰＴ［ｌ］［ｊ］の例を示す図
【図１６】同じく最適運行計画作成処理の処理フローを示す図
【図１７】同じく探索シナリオの一例を記述したプログラムを示す図
【図１８】図１７の探索シナリオの処理フローを示す図
【発明を実施するための形態】
【００２３】
以下、図面を参照して、本発明の実施形態を詳細に説明する。
【００２４】
図３は、本発明の実施形態を実施するための装置を示す図、図４は、本実施形態における全体の処理手順を示す流れ図である。
【００２５】
図３において、１は車両運行計画作成計算機、２はマスタ管理サーバ、３は受発注システム、４はプリンタ、５はコンピュータネットワークを示す。１〜４の装置・システムは、それぞれコンピュータネットワーク５に接続されている。車両運行計画作成計算機１は、データ読み込み手段、最適車両運行計画作成手段及び車両運行計画出力手段とキーボード、マウス、ディスプレイを備えたパーソナル・コンピュータもしくはワークステーションである。なお、本構成例では１台のみ例示であるが、配送する品種毎、支社、配送拠点等に対応して複数台で構成しても構わない。
【００２６】
マスタ管理サーバ２は、車両運行計画作成に必要なマスタ類を記憶、管理するための計算機である。車両運行計画作成計算機１中のデータ読み込み手段からの要求によって、必要なマスタ類を車両運行計画作成計算機１に送信する。また、マスタ類の変更、修正などを行う。
【００２７】
受発注システム３は、車両運行計画作成計算機１中のデータ読み込み手段からの要求によってオーダデータを送信する。また、車両運行計画作成計算機１中の車両運行計画出力手段から送信された車両運行計画を受信し、課金処理、出荷するオーダの確保、倉庫への出荷指示および運送会社への指示等の処理を行う。受発注システム３は、本装置例では独立した外部システムとしているが、車両運行計画作成計算機１、マスタ管理サーバ２などの内部システムとしても構わない。このことは、マスタ管理サーバ２、以下のプリンタ４などについても同様である。
【００２８】
プリンタ４は、車両運行計画作成計算機１で作成された車両運行計画を印刷する。また、受発注システム３およびマスタ管理サーバ２の出力にも利用する。
【００２９】
車両運行計画作成計算機１の内部で行う処理手順を、図４に示す。
【００３０】
まず、ステップ１のデータ読み込み処理では、図５から図１０までに例示したような表形式の必要なデータを読み込む。
【００３１】
ここで、図５に例示した表１は、複数の配送時間が指定された積荷を含む、積荷に関するデータである配送オーダデータである。
【００３２】
図６に例示した表２は、配送を行う車両に関するデータである車両マスタである。
【００３３】
図７に例示した表３は、配送拠点から納入先、納入先間、配送拠点間の距離と走行速度に関するデータである距離マスタである。
【００３４】
図８に例示した表４は、顧客である納入先に関するデータである納入先マスタである。
【００３５】
図９に例示した表５は、配送コストに関するデータである運賃マスタである。
【００３６】
図１０に例示した表６は、納入先に対して複数の配送時間が定義されているデータである配送枠マスタである。
【００３７】
次いで、図４に示したステップ１の後のステップ２の部分解作成処理では、複数の配送時間が指定された積荷に対して、予め積み合せが可能な他の積荷との積み合せパターンを複数作成し、作成されたパターンの中から使用する車両台数が最小となる積み合せを選択する。
【００３８】
次いで、ステップ３の部分解集合作成処理では、ステップ２で選択された積み合せに基づいて積荷の配送指定時間を決定し、部分解集合を作成する。
【００３９】
部分解集合を作成するため、積荷と指定時間、利用する車両と指定時間の関係を以下の様に定義して求める。
【００４０】
Ａ．積荷と指定時間の関係を示す決定変数Ｘ［ｉ］［ｊ］（図１１）。
ここで、添え字ｉ（ｉ＝０，１，２，・・・，Ｎ）は積荷のＩＤを示し、添え字ｊ（ｊ＝０，１，２，・・・，Ｍ）は指定時間のＩＤを示す。積荷ＩＤ＝ｉの積荷が指定時間ＩＤ＝ｊで配送される場合は１、それ以外は０となる。
【００４１】
指定時間のＩＤは図１２に示すように定義する。即ち、複数ある指定時間それぞれ独立したＩＤとし、同じ指定時間で複数台の車両で配送する可能性のある、指定時間は★に示す様、可能性のある回数分だけ、ＩＤを定義する。時間指定の無いものに関しても★★に示す様にＩＤを定義する。
【００４２】
積荷の指定配送時間は予め判っているので、図１３に例示する定数行列ｃＦＴ［ｉ］［ｊ］を決定変数Ｘ［ｉ］［ｊ］に掛けて、無駄な探索を行わないよう枝狩りを行う。
【００４３】
次式に示す如く、決定変数Ｘ［ｉ］［ｊ］に定数行列ｃＦＴ［ｉ］［ｊ］を掛けた物を新たな決定変数ｖＸ［ｉ］［ｊ］と定義する。
ｖＸ［ｉ］［ｊ］＝Ｘ［ｉ］［ｊ］＊ｃＦＴ［ｉ］［ｊ］∀ｉ∈ＬＤ(積荷の集合)，
∀ｊ∈ＴＭ（指定時間の集合）          …（１）
【００４４】
決定変数ｖＸ［ｉ］［ｊ］に対して、以下の制約条件を定める。
（Ａ−１）１つの積荷は１つの指定時間をもつ。指定時間の重複は許さない。
Σｊ∈ＴＭｖＸ［ｉ］［ｊ］＝１∀ｉ∈ＬＤ     （Ａ−１）
【００４５】
Ｂ．配送車両と指定時間の関係を示す決定変数Ｙ［ｋ］［ｊ］（図１４）。ここで、添え字ｋ（ｋ＝０，１，２，・・・，Ｋ）は配送車両のＩＤを示す。
決定変数Ｙ［ｋ］［ｊ］に対して、以下の制約条件を定める。
（Ｂ−１）利用される車両ｋの回数は１回以下。
（Ｂ−２）選択できる指定時間はｃＭｉｘＬＤ（積み合せ可能な顧客数）以下。
Σｊ∈ＴＭＹ［ｋ］［ｊ］≦１∀ｋ∈ＴＫ（車両の集合）       （Ｂ−１）
Σｋ∈ＴＫＹ［ｋ］［ｊ］≦ｃＭｉｘＬＤ１∀ｊ∈ＴＭ         （Ｂ−２）
【００４６】
Ｃ．決定変数ｖＸ［ｉ］［ｊ］とＹ［ｋ］［ｊ］の関係を定義する。
（Ｃ−１）指定時間ｊに決定した積荷の和は決定された車両の積載重量以下。
（Ｃ−１−１）指定時間ｊに決定した積荷の和ｓｕｍＯＷＴ［ｊ］の計算
積荷ｉの重量を示すベクトルをｃｖＷＴ［ｉ］と定義すると、ｓｕｍＯＷＴ［ｊ］は以下になる。
ｓｕｍＯＷＴ［ｊ］
＝Σｉ∈ＬＤｖＸ［ｉ］［ｊ］＊ｃｖＷＴ［ｊ］∀ｊ∈ＴＭ  （Ｃ−１−１）
【００４７】
（Ｃ−１−２）指定時間ｊを運ぶ車両の積載重量ｅｘＤＷＴ［ｊ］の計算。
車両ｋの積載重量を示すベクトルをｃｖＤＷＴ［ｋ］と定義すると、ｅｘＤＷＴ［ｊ］は以下になる。
ｅｘＤＷＴ［ｊ］
＝Σｋ∈ＴＫＹ［ｋ］［ｊ］＊ｃｖＤＷＴ［ｋ］∀ｊ∈ＴＭ  （Ｃ−１−２）
【００４８】
指定時間ｊに決定した積荷の和ｓｕｍＯＷＴ［ｊ］は、指定時間ｊを運ぶ車両の積載重量ｅｘＤＷＴ［ｊ］以下でないと、配送が成立しないため、（Ｃ−１−１）と（Ｃ−１−２）の関係は以下のようになる。
ｓｕｍＯＷＴ［ｊ］≦ｅｘＤＷＴ［ｊ］  （Ｃ−１）
【００４９】
（Ｃ−２）積み合せ可否判別
決定変数Ｙ［ｋ］［ｊ］は車両kの積み合せのパターンを示すことになるため、このパターンの成立可否を判別する。
【００５０】
積み合せのパターンは、表３（図７）の距離マスタ、表４（図８）の納入先マスタでの卸し時間と、車速により容易に決めることが出来る。
【００５１】
積み合せパターンを示す行列をｃＬＤＰＴ［ｌ］［ｊ］∈｛０，１｝、ｌ：積み合せパターン数（ｌ＝０，１，２，・・・，Ｌ）と定義する。積み合せパターンを示す行列ｃＬＤＰＴ［ｌ］［ｊ］を具体的に示した例を図１５に示す。図１５において積み合せパターンＩＤ＝０の例は、Ａ社７：００のみの積み合せ無しの場合を示し、積み合せパターンＩＤ＝１の例は、Ａ社７：００の配送とＢ社９：３０の配送の積み合せが可能であることを示す。使用しない車両のため、すべて０のパターンを含めておく。
【００５２】
決定変数Ｙ［ｋ］［ｊ］とｃＬＤＰＴ［ｌ］［ｊ］を用いて、積み合せパターンの成立可否を判別する。
【００５３】
（Ｃ−２−１）車両ｋ毎のｃＬＤＰＴ［ｌ］［ｊ］との差の絶対値ｄｅＦ［ｋ］［ｌ］を計算する。
ｄｅＦ［ｋ］［ｌ］＝Σｌ∈ＰＴａｂｓ（Ｙ［ｋ］［ｊ］−ｃＬＤＰＴ［ｌ］［ｊ］）
∀ｋ∈ＴＫ、∀ｊ∈ＴＭ、∀ｌ∈ＰＴ（積み合せパターン集合）     …（２）
【００５４】
ｄｅＦ［ｋ］［ｌ］において車両ｋの積み合せのパターンｌが、成立する場合はｄｅＦ［ｋ］［ｌ］＝０となる。行列ｄｅＦ［ｋ］［ｌ］において、ｋにおいてｌ方向の０の数をカウントすることによって、すべての車両の積み合せが成立するかが判別できる。
【００５５】
ここで、以上の処理を行うために新たな決定変数ｖＮｏＺ［ｋ］［ｌ］∈｛０，１｝を導入する。この変数はｄｅＦ［ｋ］［ｌ］＞０の場合にｖＮｏＺ［ｋ］［ｌ］＝１となる変数である。このときの制約条件は定数ＢｉｇＭ＝１０００とすると、以下の式になる。
ｄｅＦ［ｋ］［ｌ］≧ｖＮｏＺ［ｋ］［ｌ］、
ｄｅＦ［ｋ］［ｌ］≦ｖＮｏＺ［ｋ］［ｌ］＊ＢｉｇＭ
∀ｋ∈ＴＫ、∀ｌ∈ＰＴ                                  …（３）
【００５６】
最終的に、積み合せパターンが成立する条件は以下のようになる。
Σｋ∈ＴＫΣｌ∈ＰＴｖＮｏＺ［ｋ］［ｌ］＝０               …（４）
【００５７】
以上で定義された、積荷と指定時間、利用する車両と指定時間の関係に基づき、部分解集合を作成する。
【００５８】
Ｄ．目的関数
目的関数は、使用する指定時間数とし、使用する車両の数を最小とする。
【００５９】
使用する指定時間数は以下の式で計算できる。
使用する指定時間数＝Σｋ∈ＴＫΣｊ∈ＴＭＹ［ｋ］［ｊ］            …（５）
【００６０】
目的関数は使用する指定時間数とし、使用する車両の数を最小とする。
【００６１】
使用する車両の数は、新たな決定変数ｖＮｏＺＬＤ［ｋ］∈｛０，１｝を導入して求める。この変数は、Σｊ∈ＴＭＹ［ｋ］［ｊ］＞０（∀ｋ∈ＴＫ）となる場合にｖＮｏＺＬＤ［ｋ］＝１となる変数である。この変数を用いて、以下のように計算できる。
Σｊ∈ＴＭＹ［ｋ］［ｊ］≧ｖＮｏＺＬＤ［ｋ］、
Σｊ∈ＴＭＹ［ｋ］［ｊ］≦ｖＮｏＺＬＤ［ｋ］＊ＢｉｇＭ  ∀ｋ∈ＴＫ  …（６）
使用する車両台数＝Σｋ∈ＴＫｖＮｏＺＬＤ［ｋ］                      …（７）
目的関数＝Σｋ∈ＴＫΣｊ∈ＴＭＹ［ｋ］［ｊ］＋Σｋ∈ＴＫｖＮｏＺＬＤ［ｋ］
⇒Ｍｉｎ                                                  …（８）
【００６２】
以上を、非特許文献１で示されている商用のソルバ、ＣＯＩＮ−ＯＲ（http://www.coin-or.org/index.html）で提供されているフリーソフトのソルバ等を用いて、部分解集合を作成する。
【００６３】
部分解集合は１つでも良いが、目的関数の少ない順の複数、同値の目的関数の複数などを部分解集合としても良い。
【００６４】
部分解集合が作成できると、複数指定されている配送時間を１つに確定できる。部分解集合で確定された配送時間を、それぞれの積荷の配送指定時間とする。
【００６５】
次いで、図４のステップ４の最適運行計画作成処理では、作成された部分解集合と残りの積荷とを含めて、配送コスト最小となる車両運行計画を作成する。
【００６６】
この最適化アルゴリズムは、例えば特許文献４のアルゴリズムを使用することができる。
【００６７】
図１６は、図４のステップ４の最適運行計画作成処理の処理フローを示す図である。ステップ２０のデータ読込みでは、最適運行計画作成手段で必要なデータを読み込み、最適運行計画作成処理の初期化を行う。読み込まれるデータは、前述した配送オーダデータ（図５）、車両マスタ（図６）、距離マスタ（図７）、納入先マスタ（図８）、運賃マスタ（図９）、配送枠マスタ（図１０）、及び後述する探索シナリオである。
【００６８】
次にステップ２１の探索シナリオ解釈では、読み込まれたデータのうち探索シナリオの解釈を行う。探索シナリオとは、初期解作成、各種探索単位による最適化処理、繰り返し回数、条件分岐、終了条件等を記述したものであり、人が事前に最適化する対象に応じて戦略的に入力・記憶させておく。
【００６９】
各種探索単位による最適化処理には、１オーダ（１つの積荷）と１車両内の１運行サイクル、１車両内の１運行サイクル内の同一納入先のオーダをまとめたものと、１車両内の１運行サイクル、１車両と１車両内の１運行サイクル、１車両と同一ではない１車両、１車両とそれぞれ同一ではない２車両等の探索単位による最適化処理がある。
【００７０】
図１７に探索シナリオの一例を記述したプログラムを示す。この探索シナリオをステップ２１の探索シナリオ解釈では、図１８のように処理フローとして解釈する。この探索シナリオの例では、Ｍ個の初期解を作成し、作成した初期解を探索単位を変えながらの最適化をＮ回行うものである。図１７のＬＯＯＰ内のＣＡＲＧＯは、図１８のステップ３１（積荷を探索単位とした最適化処理）に対応し、以下同様にＤＥＳＴＩＮはステップ３２（納入先を探索単位とした最適化処理）、ＴＲＵＣＫはステップ３３（１車両と１車両を探索単位とした最適化処理）、ＴＲＵＣＫ１ｂｙ２はステップ３４（１車両と２車両を探索単位とした最適化処理）、ＴＲＩＰはステップ３５（運行サイクルを探索単位とした最適化処理）およびＴＲＩＰ＿ＤＩＶはステップ３６（運行サイクルの平準化）にそれぞれ対応している。
【００７１】
図１８の積荷を探索単位とした最適化処理ステップ３１と納入先を探索単位とした最適化処理ステップ３２では、配送ロットの集約、調整を行う。図１８の１車両と１車両を探索単位とした最適化処理ステップ３３と１車両と２車両を探索単位とした最適化処理ステップ３４では、利用する車両の種類の調整を行う。図１８の運行サイクルを探索単位とした最適化処理ステップ３５および運行サイクルの平準化ステップ３６では、運行サイクルの調整を行う。
【００７２】
図１６のステップ２２では、ステップ２１で解釈された最適化方法を実行する。
【００７３】
ステップ２３では、探索シナリオによって探索された中から評価関数の値がもっとも良いものを選択し、最適運行計画作成処理を終了する。
【００７４】
複数の部分解集合を用いた場合、複数の車両運行計画を作成し、その中から最も配送コストが最小な物を最適な配送計画として、図４のステップ４を終了する。
【００７５】
図４のステップ５では、ステップ４で作成された配送計画結果を出力する。
【００７６】
以上説明したように、本実施形態では、最適化処理方法の選択および選択した最適化処理方法の探索順を探索シナリオと呼んでおり、計画対象の違いにより探索シナリオを種々変化させることができる。各最適化処理単体でもよいし、それらいずれかの組合せでも良く、車両運行計画の対象変化に柔軟に対応できる利点がある。さらに、複数配送拠点を計画対象に加えることにより探索範囲が増加するが、計画対象の違いにより最適な探索シナリオを選ぶことにより、計算時間の短縮も期待できる。
【符号の説明】
【００７７】
１…車両運行計画作成計算機
２…マスタ管理サーバ
３…受発注システム
４…プリンタ
５…コンピュータネットワーク
【図１】
2013133198.tif 000003
【図２】
2013133198.tif 000004
【図３】
2013133198.tif 000005
【図４】
2013133198.tif 000006
【図５】
2013133198.tif 000007
【図６】
2013133198.tif 000008
【図７】
2013133198.tif 000009
【図８】
2013133198.tif 000010
【図９】
2013133198.tif 000011
【図１０】
2013133198.tif 000012
【図１１】
2013133198.tif 000013
【図１２】
2013133198.tif 000014
【図１３】
2013133198.tif 000015
【図１４】
2013133198.tif 000016
【図１５】
2013133198.tif 000017
【図１６】
2013133198.tif 000018
【図１７】
2013133198.tif 000019
【図１８】
2013133198.tif 000020