(57)【要約】【課題】指定された時間内に配送できない荷物が存在する場合、配送コストを考慮して、指定された時間内に配送できない荷物がなくなるように、除外する荷物を決定することにより、配送計画を修正する。【解決手段】指定された時間内に配送できない荷物の中から配送の一番早い荷物Ｘを選定し（Ｓ４）、荷物Ｘと荷物Ｘの前に配送される荷物とを選択し、これらの選択された荷物の中で、いずれか１つの荷物を除外すれば、残りの荷物が指定された時間内に配送でき（Ｓ８）、かつ、その荷物を除外することにより配送コストＰ（Ｙ）が最小となる荷物Ｙ′を１つ決定し（Ｓ９，１０）、その荷物Ｙ′を除外する（Ｓ１３）。【選択図】        図２
2004323229.tif 000002
【特許請求の範囲】
【請求項１】
移動体に搭載する荷物の中で、指定された時間内に配送できない荷物が存在する場合、指定された時間内に配送できない荷物がなくなるように、一部の荷物を除外して配送計画をたてる配送計画立案方法であって、次の（ａ）〜（ｅ）の手順を採用することを特徴とする配送計画立案方法。
（ａ）指定された時間内に配送できない荷物を選択する。
（ｂ）手順（ａ）で選択された荷物の中から配送の一番早い荷物Ｘを選定する。
（ｃ）荷物Ｘと荷物Ｘの前に配送される荷物とを選択する。
（ｄ）手順（ｃ）で選択された荷物の中で、いずれか１つの荷物を除外すれば、残りの荷物が指定された時間内に配送でき、かつ、その荷物を除外することにより配送コストが最小となる荷物を１つ決定する。
（ｅ）決定された荷物を除外する。
【請求項２】
指定された時間内に配送できない荷物が複数ある場合は、指定された時間内に配送できない荷物がなくなるまで、前記手順（ａ）〜（ｅ）を繰り返して実行することを特徴とする請求項１記載の配送計画立案方法。
【請求項３】
前記配送コストは、次の（１）から（４）の中から選ばれる１つ又は複数を変数とする関数で表されることを特徴とする請求項１記載の配送計画立案方法。
（１）当該移動体の配送時間
（２）当該移動体の燃料
（３）当該移動体の荷物積載率
（４）当該移動体の配送距離
【請求項４】
コンピュータに搭載されて実行されるプログラムであって、前記請求項１記載の配送計画立案方法を実現するための配送計画立案プログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、荷物の配送計画を自動的に算出することができる配送計画立案方法及びプログラムに関するものである。
【０００２】
【従来の技術】
多数の荷物を複数の車両で配達する場合、どの車両にどの荷物を積んで、どのようなルートで配送すればよいかを、自動的に計算することのできる配送計画プログラムが知られている。この配送計画プログラムは、各配送先の配送指定時間や車両の最大積載量などの制約に基づき、効率のよい配送ルートを計算するものである。
【０００３】
【特許文献１】特開平１０−６９５９６号公報
【０００４】
【発明が解決しようとする課題】
前記配送計画プログラムは、人間がカンと経験で配送計画を立てるのに比べて、より速くより正確に配送ルートを求めることができる。しかし、常に最良の解が提供されるわけではない。
例えば一台の車両に着目した場合、その車両に積載する荷物の中には、指定された時間内にどうしても配達できない荷物が含まれることがある。
【０００５】
当該車両に積載した全ての荷物を、指定された時間内に配達しようとすれば、「指定された時間内に配達できない荷物」を除外し、他の便で配達するなどの措置をとらなければならない。
ところが、「指定された時間内に配達できない荷物」を除外することが唯一の解とは限らない。場合によっては、指定された時間内に配達することのできる荷物を除外することにより、前記「指定された時間内に配達できない荷物」を指定された時間内に配達することができるようになる可能性がある。
【０００６】
いずれの荷物を除外するかは、配送コスト（例えば、当該車両の配送時間、配送距離、燃料、積載率などを変数とする関数で表される）を考慮して合理的に決定することが望まれる。
そこで、本発明は、指定された時間内に配送できない荷物が存在する場合、配送コストを考慮して、指定された時間内に配送できない荷物がなくなるように、一部の荷物を除外して計画することができる配送計画立案方法及びプログラムを提供することを目的とする。
【０００７】
【課題を解決するための手段】
本発明の配送計画立案方法は、指定された時間内に配送できない荷物を選択し、前記選択された指定された時間内に配送できない荷物の中から配送の一番早い荷物Ｘを選定し、荷物Ｘと荷物Ｘの前に配送される荷物とを選択し、前記選択された荷物の中で、いずれか１つの荷物を除外すれば、残りの荷物が指定された時間内に配送でき、かつ、その荷物を除外することにより配送コストが最小となる荷物を１つ決定し、その荷物を除外する方法である（請求項１）。
【０００８】
この方法によれば、荷物Ｘと荷物Ｘの前に配送される荷物との中から、１つの荷物を除外して残った荷物が指定された時間内に配送でき、かつ、その荷物を除外して配送する場合の各配送コストを算出して互いに比較することにより、配送コストを最小にする荷物を決定することができる。
なお、除外された荷物は、除外された荷物を含む配送計画を別にたてる、別の移動体を調達して配送する、などの任意の措置を行うことができる。
【０００９】
指定された時間内に配送できない荷物が複数ある場合は、指定された時間内に配送できない荷物がなくなるまで、前記手順を繰り返して実行する（請求項２）。これにより、当該移動体で配送される荷物を、すべて指定された時間内に配送できるようになる。
前記配送コストは、当該移動体の配送時間、当該移動体の燃料、当該移動体の荷物積載率、当該移動体の配送距離の中から選ばれる１つ又は複数を変数とする関数で表されるものであってもよい（請求項３）。
【００１０】
また、本発明の配送計画立案プログラムは、請求項１記載の配送計画立案方法と同じ発明に係るプログラムである（請求項４）。
【００１１】
【発明の実施の形態】
以下、トラックなど道路を走行する車両を想定して、本発明の実施の形態を、添付図面を参照しながら詳細に説明する。
図１は、配送計画立案システム全体の概略構成を示すブロック図である。配送計画立案システムは、遺伝子アルゴリズムなど公知の手法を用いて配送計画をたてる際に、車両に搭載する荷物の中で、指定された時間内に配送できない荷物が存在する場合、指定された時間内に配送できない荷物がなくなるように配送計画をたてる配送計画シミュレータ１、配送ルートを探索するための地図データベース２、荷物の配送先、荷物の重量と体積、荷物の配送指定時間等の荷物データが供給される第１入力部３、利用可能な車両の情報（車種や積載量など）が供給される第２入力部４、配送計画算出及びその修正のためのプログラムが格納されたメモリ５、並びに配送計画シミュレータ１により算出された配送計画を、例えば車両ごとのタイムチャートの形で出力する出力部６を備えている。
【００１２】
出力部６から出力される配送計画タイムチャートは、車両ごとに、車両が積載する荷物の荷物コード、荷物の配送先、荷物の重量と体積、荷物の配送指定時間、荷物の配送可能時間などが、配送時間順に記入されているものである。
前記荷物の配送指定時間は、ある荷物を配送先に届けるのに指定されている時間のことである。例えば、１０時から１２時までという指定があれば、その荷物をその日の１０時から１２時までの間に届けてほしいという指定になる。０時から２４時までという指定があれば、その荷物をその日のうち任意の時刻に届ければよいことになる。
【００１３】
公知の手法を用いて算出された配送計画は、全ての荷物が指定された時間内に配送できるように計画されているとは限らない。例えば、多くの荷物がある時間帯に集中して配送指定されている場合、限られた車両では、指定された時間内にどうしても配達できない荷物が発生してしまう。
そこで、一台の車両に着目して、その車両に積載する荷物の中には、指定された時間内に配達できない荷物が含まれる場合、いずれかの荷物を除外するために、配送計画の修正を行う。
【００１４】
図２は、配送計画修正手順を説明するためのフローチャートである。まず、既存の配送計画プログラムによりその日の配送計画を取得する（ステップＳ１）。
以下、各車両ごとに処理をする。
車両の添え字をｉとし、まずｉ＝１とおく（ステップＳ２）。
当該車両ｉの荷物を添え字Ｙで表わし、配送順にＹ＝１，Ｙ＝２，Ｙ＝３，．．．とおく。荷物Ｙの中で指定された時間に配送できない荷物があれば、その荷物の中で最も配送順位が早い荷物をＸとおく（ステップＳ４）。
【００１５】
なお、荷物Ｙがすべて指定された時間に配送できるのであれば（ステップＳ５のＮＯ）、配送計画シミュレータ１は、その車両の処理をせずに、次の車両の処理に入る（ステップＳ６）。
次に、配送順位が最も早い荷物Ｙ＝１について、以下の処理を行う（ステップＳ７）。このとき配送コストＰを無限大としておく。
配送計画シミュレータ１は、荷物Ｙを除外すると、荷物Ｘが指定された時間に配送できるようになるかどうか、又は荷物Ｙが荷物Ｘであるかどうかを調べる（ステップＳ８）。いずれも否定のときは、Ｙを１繰り上げて（ステップＳ１２）、次の荷物を処理する。
【００１６】
いずれかが満たされていれば、その荷物Ｙを除外したときの、他の荷物の配送可能時間を計算し直し、その荷物Ｙを除外したときの配送コストＰ（Ｙ）を求める。
ここで配送コストＰ（Ｙ）は、当該車両が荷物Ｙを除外して他の荷物を配送する場合にかかる配送時間、配送距離、当該車両が消費する燃料、当該車両の荷物積載率の中から選ばれる１つ又は複数を変数とする関数で表される。例えば配送距離、配送時間、燃料を変数とする場合、配送コストは、図３（ａ）に示すように右上がりの曲線又は直線になる。積載率を変数とする場合、配送コストは、図３（ｂ）に示すように右下がりの曲線又は直線になる。配送コストの関数形は、実際には、これら複数の変数に重みをつけて加算した形の関数になることが予想されるが、これに限られるものではなく、任意の関数形を採用してもよいことはもちろんである。
【００１７】
Ｐ（Ｙ）≦Ｐであれば、その荷物Ｙを除外することにより、配送コストＰ（Ｙ）が低下したことを確認できる（ステップＳ９のＹＥＳ）。Ｐ（Ｙ）＞Ｐであれば、その荷物Ｙを除外しても、配送コストＰ（Ｙ）は低下しない。このときは、その荷物Ｙを除外することはせず、Ｙを１繰り上げて（ステップＳ１２）、次の荷物の処理をする。
配送コストＰ（Ｙ）が低下した場合、配送コストＰを改めてＰ（Ｙ）とおき、除外候補の荷物Ｙ′を、その荷物Ｙとする（ステップＳ１０）。
【００１８】
ＹがＸまで到達したかどうかを調べ（ステップＳ１１）、ＹがＸまで到達していなければステップＳ１２で、Ｙを１繰り上げて、次の荷物を処理する。
次の荷物について、ステップＳ８以下の処理を続ける。荷物Ｙを除外することにより、配送コストＰ（Ｙ）がさらに低下すれば、除外候補の荷物Ｙ′を、その荷物Ｙに変更する。
このようにして、Ｙ＝１からＸまでの荷物について、除外することにより配送コストＰ（Ｙ）が最も低下する荷物Ｙ′を特定できる。
【００１９】
そこで、配送計画シミュレータ１は、その荷物Ｙ′を除外することに決定して、車両ｉの配送計画を変更する。
以上の処理を他の車両についても行い、全車両についてチェックが終わると（ステップＳ３のＹＥＳ）、処理を抜ける。
以上で説明した配送計画修正手順を図解すると、図４のようになる。まず、図４（ａ）に示すように、その日の配送計画によれば、ある車両に７つの荷物が搭載されるものとする。荷物にＹ＝１からＹ＝７までの添え字をつける。荷物Ｙ＝３とＹ＝６とが、指定された時間に配送できない荷物であるとする。それらの荷物の中で最も配送順位が早い荷物の添え字３をＸとおく。
【００２０】
荷物Ｙ＝１，２，３を、それぞれ独立に除外したときに、荷物Ｘ及びその前の除外されなかった荷物が指定された時間に配送できるようになるかどうかをチェックし、それが肯定であれば、そのうちで除外すれば最も配送コストが低下する荷物Ｙ′を１つ決定する。いまその荷物Ｙ′が図４（ｂ）に示すように、荷物Ｙ＝１であるとする。
次に、残りの荷物を改めてＹ＝１からＹ＝６までの添え字をつける。図４（ｃ）に示すように、指定された時間に配送できない荷物ＸがＹ＝５であるとする。
【００２１】
荷物Ｙ＝１〜５を、それぞれ独立に除外したときに、荷物Ｘ及びその前の除外されなかった荷物が指定された時間に配送できるようになるかどうかをチェックし、それが肯定であれば、そのうちで除外すれば最も配送コストが低下する荷物Ｙ′を１つ決定する。いまその荷物Ｙ′が図４（ｄ）に示すように、荷物Ｙ＝３であるとする。
このようにして、荷物３が除外され、残った５つの荷物を配送する、修正された配送計画ができあがる。
【００２２】
以上説明したように、本発明の実施形態では、荷物Ｘと荷物Ｘの前に配送される荷物との中から、１つの荷物を除外すると仮定し、残った荷物が指定された時間内に配送でき、かつ、その荷物を除外して配送する場合の配送コストを最小にすることができる荷物を決定することができる。そしてその荷物を除外して、指定された時間内に配送できる荷物だけを配送する修正計画をたてることができる。
【００２３】
除外された荷物は、配送計画シミュレータ１により、当該除外された荷物を対象として配送計画を別にたてるとよい。別に配送計画をたてても、指定された時間に配送できない荷物が含まれてくる場合、別の車両を調達して配送する、次の日の配送に回すなどの措置をとることができる。
以上で、本発明の実施の形態を説明したが、本発明の実施は、前記の形態に限定されるものではない。例えば移動体として、道路を走行する車両以外に、鉄道車両などを想定しても本発明の実施は可能である。その他本発明の範囲内で種々の変更を施すことが可能である。
【００２４】
【発明の効果】
以上のように本発明によれば、配送コストを最小にしながら、移動体に搭載する荷物の中に、指定された時間内に配送できない荷物が存在しなくなるような解を得ることができる。
【図面の簡単な説明】
【図１】配送計画立案システム全体の概略構成を示すブロック図である。
【図２】配送計画修正手順を説明するためのフローチャートである。
【図３】（ａ）は、配送コストと、配送距離、配送時間、燃料との関係を示すグラフ、（ｂ）は配送コストと、積載率との関係を示すグラフである。
【図４】配送計画修正手順の一例を図解した図である。
【符号の説明】
１  配送計画シミュレータ
２  地図データベース
３  第１入力部
４  第２入力部
５  メモリ
６  出力部
【図１】
2004323229.tif 000003
【図２】
2004323229.tif 000004
【図３】
2004323229.tif 000005
【図４】
2004323229.tif 000006