(57)【要約】【課題】配送先間が遠距離となる組み合わせを排除し、広域で低密度な複数の配送先に積み荷を配送する配送計画を可能とする配送計画立案方法およびその装置を提供する。【解決手段】各オーダの情報および配送計画立案に関わるマスターデータの情報を入力する入力装置と、複数の配送車輌が複数の配送先に積み荷を配送する配送計画を作成する処理装置と、作成された配送計画を出力する出力装置と、配送先間の距離データに基づいて、オーダを分割してグループを作成するオーダグループ化手段とを備え、分割されたオーダグループごとに配送計画の立案処理を実行させる配送計画立案装置。配送先間の距離データマスターに基づいて、あらかじめ指定した距離以下の配送先間の組み合わせｘ１〜ｘ８を抽出して配送先をグループ化し（Ｇｒ−１，３，７）、それに基づきオーダのグループを作成する配送計画立案方法。【選択図】  図５
2004238129.tif 000002
【特許請求の範囲】
【請求項１】
各オーダの情報および配送計画立案に関わるマスターデータの入力情報を入力する入力装置と、入力された情報によって、複数の配送車輌が物流拠点を出発し複数の配送先に積み荷を配送する配送計画を作成する処理装置と、作成された配送計画を出力する出力装置と、配送先間の距離データのマスターに基づいてオーダを分割してグループを作成するオーダグループ化手段とを備え、分割されたオーダグループごとに配送計画の立案処理を実行させることを特徴とする配送計画立案装置。
【請求項２】
各オーダの情報は、各オーダの配送先、荷物、重量、荷卸し指定時間、配送車輌指定の内１つ以上を含み、配送計画立案に関わるマスターデータは少なくとも、物流拠点から配送先までの距離、配送先間の距離データ、速度パターンの内１つ以上を含み、配送計画を作成する処理装置は、配送経路で総走行距離が最短となる配送計画を作成することを特徴とする請求項１記載の配送計画立案装置。
【請求項３】
請求項１又は請求項２記載の配送計画立案装置を用いて、各オーダの配送先を配送先間の距離データマスターに基づいて、あらかじめ指定した距離以下の配送先間の組み合わせを抽出して配送先をグループ化し、グループ化された配送先に基づき、前記オーダのグループを作成することを特徴とする配送計画立案方法。
【発明の詳細な説明】
【０００１】
【発明の属する分野】
本発明は、物流システムにおける物流拠点または倉庫を出発し、広域で低密度な複数の配送先についても積み荷を配送する配送計画を作成することが可能な配送計画立案方法およびその装置に関する。
【０００２】
【従来の技術】
物流システムにおける配送計画の問題は、複数の車輌が共通の物流拠点を出発し、複数の配送先に積み荷を配送して、総走行距離が最短になるようなものを求めるものである。各車輌には積載量の上限、ユニックを装備した車輌、可能積載重量が指定された車輌等の車輌指定、荷卸しの時刻指定等の制約がある。
【０００３】
例えば、車輌指定が発生する場合は、積み荷の受け入れ現場が狭い、現場までの道路が狭い等の理由で大きい車輌で配送できない場合等であり、現場に積み荷を卸す装置がない場合に、ユニック車指定がある。また、荷卸しの時刻指定は、現場に荷物の置き場がなく、工事の進捗に合わせて荷物の到着時刻を指定する場合や、指定時刻よりも早く現場に到着したトラックが路上駐車して交通渋滞を発生させること等を防ぐために行われる。
【０００４】
このような制約のもとで作成する配送計画の作成ステップは、通常、２段階の処理に分かれる。１つは、配送先の荷物を各車輌に振り分ける処理である。他の１つは、各車輌に積まれた荷物を車輌がどの順序で巡るかというルートの最適化を行う処理である。通常、これらの２つの処理を、配送の制約条件を守りながら、使用する車輌台数が少なくなるように積載率のアップをねらい、更に、車輌が配送先を回るときの走行距離が短くなるように配送順序を決定している。
【０００５】
特許文献１には、あらかじめ配送先を地図の２次元の平面で表し、配送拠点を中心に扇型の部分空間を作り、その部分空間の方面ごとに配車計画を実施する方法が記載されている。その方法は、遠方優先法や方面分割法その他、立案戦略が異なるアルゴリズムの複数の配送計画立案処理を単一の処理装置内で時分割または複数の処理装置で並行に実行させ、その実行結果のうち総走行距離が最短になる処理結果を選択し、前記出力装置から出力するというものである。
【０００６】
その中の、方面分割（法）では、空間（配送対象地域）をいくつかの物流拠点を通る直線で分割して生成される扇形の部分空間ごとに、その方面内に位置する配送先の荷物量の和に比例する数のシードをその方面に割り当てている。
【０００７】
【特許文献１】
特開２００１−１８８９８４号公報
【０００８】
【発明が解決しようとする課題】
しかしながら、従来における配送計画方法にあっては、配送先の荷物を各車輌に振り分ける処理と各車輌に積まれた荷物を車輌がどの順序で巡るかというルートの最適化を求める処理を交互に行い最終的な最適解を求めている。
【０００９】
各オーダの荷物の配送先が全国に渡るときに、この二つの処理をオーダの全荷物を一括で扱って処理を行う場合、例えば、配送先が全国に渡るときに、関東と関西地方の荷物を同じトラックで配送するのは効率的でない。そのため、最終的な配送計画では、なるべく同じ地域の荷物が１台のトラックに積まれるよう計画を立てる。
【００１０】
このとき、全荷物を一括で処理し探索を行うと、１台のトラックに載せる荷物で効率的でない組み合わせが発生し、計画策定の処理時間が増大し、また探索回数が増えるために、局所解に陥り最適解にたどり着けない可能性がある。
【００１１】
また、特許文献１記載の技術のように、あらかじめ配送先を地図の２次元の平面で表し、配送拠点を中心に扇型の部分空間を作り、その部分空間の方面ごとに配車計画を実施する方法の場合、隣り合ったそれぞれの扇型の境界近傍にそれぞれ配送先がある場合には、これらの配送先は、それぞれの方面ごとで配車されてしまうため、同一の車輌に荷物が積載されずに配車される問題がある。
【００１２】
あるいは、無駄な探索を減らすために、例えば都道府県単位でオーダを分割すると、県境に面した配送先の越境を最初から排除し、配送計画立案の対象とならなくなってしまい、効率的な配送のチャンスを逃す可能性がある。
【００１３】
本発明は、配車計画の処理にかける前に、配送先間が遠距離となる組み合わせを排除し、物流システムにおける物流拠点または倉庫を出発し、広域で低密度な複数の配送先に積み荷を配送する配送計画を可能とする配送計画立案方法およびその装置を提供することを目的とする。
【００１４】
【課題を解決するための手段】
上記の課題は、次の発明により解決される。その発明は、各オーダの情報および配送計画立案に関わるマスターデータの入力情報を入力する入力装置と、入力された情報によって、複数の配送車輌が物流拠点を出発し複数の配送先に積み荷を配送する配送計画を作成する処理装置と、作成された配送計画を出力する出力装置と、配送先間の距離データのマスターに基づいてオーダを分割してグループを作成するオーダグループ化手段とを備え、分割されたオーダグループごとに配送計画の立案処理を実行させることを特徴とする配送計画立案装置である。
【００１５】
この発明においてさらに、各オーダの情報は、各オーダの配送先、荷物、重量、荷卸し指定時間、配送車輌指定の内１つ以上を含み、配送計画立案に関わるマスターデータは少なくとも、物流拠点から配送先までの距離、配送先間の距離データ、速度パターンの内１つ以上を含み、配送計画を作成する処理装置は、配送経路で総走行距離が最短となる配送計画を作成することを特徴とする配送計画立案装置とすることもできる。
【００１６】
さらにこれらの発明の配送計画立案装置を用いて、各オーダの配送先を配送先間の距離データマスターに基づいて、あらかじめ指定した距離以下の配送先間の組み合わせを抽出して配送先をグループ化し、グループ化された配送先に基づき、前記オーダのグループを作成することを特徴とする配送計画立案方法の発明とすることもできる。
【００１７】
これらの発明は、まず、オーダを配送先に応じて分割しているので、配送計画の立案処理を分割されたオーダグループごとに実行させることができる。その結果、探索に要する計算量を大幅に削減することができる。例えば、配送計画を立案するオーダの中に、青森と福岡のような長距離の配送先が含まれる場合に、これらのオーダを同じ車輌で配送することは実用上はありえない。しかし、これらの配送先を含んだオーダを一括して配送計画の立案を行うと、立案途中の計算過程では、これらの組み合わせが発生する可能性があるために、無駄な探索が発生している。
【００１８】
ここで、本来、配送先間の距離データのマスターは、配送時間、配送順を決定するために必要なマスターであるが、配送先間の分割を行う際のマスターとしても使用することができ、本目的のために新たなマスターを準備しないで実現することができる。
【００１９】
各オーダの配送先を配送先間の距離データマスターに基づいて、あらかじめ指定した距離以下の配送先間の組み合わせを抽出し、抽出された組み合わせの中で、同じ配送先があるものをグループ化することで、探索空間を狭めることができ、探索の高速化につなげることができる。
【００２０】
例えば、３００件のオーダの３件を１台のトラックに積載する場合の組み合わせは、１０グループにオーダ分割した場合では、以下に示すように、分割しない場合の約１／１００の組み合わせで済む。
▲１▼オーダ分割なしの場合の組み合わせ：
（３００×２９９×２９８）／（３×２×１）＝４，４５５，１００通り
▲２▼オーダ分割した場合の組み合わせ：
（３０×２９×２８）／（３×２×１）×１０＝４０，６００通り
このように、組み合わせの中で、同じ配送先があるものをグループ化し、オーダを分割することにより、自分自身のグループ以外に近距離の配送先のオーダが存在しないように、オーダをあらかじめ分割することができる。その結果、狭められた探索による配送計画の立案となるために、高速化することが可能となる。
【００２１】
また、距離データとしては、全国一律の尺度の距離では、地方に比べ、都市部のように交通渋滞がある場合には、配送先間の移動時間が長くなり、車輌の移動範囲が狭くなる。そこで、都市部での配送間距離は、地方に比べて短くなるようにして対象となる探索領域を絞り込めば、更に探索時間の高速化に繋がる。
【００２２】
【発明の実施の形態】
以下、本発明を図示する実施の形態に基づいて詳細に説明する。図１は本発明の最適配送計画立案システム構成の一実施形態を示す。
【００２３】
配車計画に必要なオーダ情報は、工場・営業所の操作端末から入力され、サーバーに送信される。オーダ情報には、オーダの配送先、品目の重量、数量等、また、納入日時、指定車輌の有無等の情報が添付されている。サーバーに集約されたオーダ情報のオーダ情報ＤＢ、およびマスターＤＢに基づいて、配車計画策定部署端末から、配車計画策定操作が実行される。
【００２４】
配車計画策定の手順を図２に示す。図２に示すように、まず、Ｓ１で配車計画対象オーダデータを取り込む。次いで、Ｓ２でオーダ情報に基づき、マスターＤＢ（納入先マスター、配送先距離、配送先間データなど）から、配車計画の対象部分のマスターデータを取り込む。自動配車計画を実行前に、Ｓ３で、積み合わせ、車輌指定、納入日時等の計画策条件に修正があれば、配車計画実行条件設定にて修正処理を行う。
【００２５】
自動配車計画に必要な条件が揃った状態で、Ｓ４の配車計画を実行する。まず、配送エリア分割に必要な距離計算（ｓｔｅｐ１）を実行する。そのフローチャートを図３に示す。例えば、ｓｔｅｐ１によって、配送先の都市が図５に示すようにＡ〜Ｊの１０箇所あり、それぞれの都市間の距離を算出する。その結果、実際の地図上の道路距離に基づいた都市間距離（図３  ｄ（ｉ，ｊ））があらかじめ指定した距離（図３  ｄ＃ｐａｒａｍ）以下となる組み合わせが、図３のｃｅｌｌ（ｉ，ｊ）に距離ｘ１〜ｘ８として格納される。
【００２６】
都市間の距離は、例えば、固定の顧客であればそれぞれの顧客間の距離データをマスターとする。また、顧客が常に変化する場合は、納入先の住所の市区町村を代表値とし、全国の市区町村ＪＩＳコードで管理する。
【００２７】
オーダグループ化手段では、図５（ａ）に示す都市間距離のテーブルに基づき、配送エリア分割、即ち配送先（都市、固定顧客）のグループ化（ｓｔｅｐ２）を行う。そのフローチャートを図４に示す。ここでは、テーブルのｉ行ｊ列のセル（ｃｅｌｌ）について、都市間距離の有無を判定し、都市間距離ｘ１〜ｘ８が記載されているセルの中で行又は列を共有する都市間距離をグループ化する。
【００２８】
図５に示すテーブルでは配送先がＡからＪまでの１０都市が存在するので、Ａ〜ＪをＧｒ−１〜Ｇｒ−１０と割り付ける（図４  ｇｒｏｕｐ＃ｉｄ（ｉ）＝ｉ  ）。グループ化の処理は、図５の左側の列から順に、列ごとに、行の上段から下段に向けて空欄（ヌル）でないセルを探す。まず、ｊ（列）＝２，ｉ（行）＝１（Ｂ列Ａ行）のときセル（図４  ｃｅｌｌ（ｉ，ｊ））が空欄でなく、都市間距離ｘ１が存在するため、配送先ＡとＢは同じグループとなる。このとき、配送先Ｂは、配送先ＡのグループＩＤにそろえる（図４  ｇｒｏｕｐ＃ｉｄ（ｊ）＝ｇｒｏｕｐ＃ｉｄ（ｉ））。従って、この段階でのそれぞれのグループの集合は（１）式となる。
【００２９】
Ｇｒ−１＝｛Ａ、Ｂ｝、Ｇｒ−３＝｛Ｃ｝、Ｇｒ−４＝｛Ｄ｝、
Ｇｒ−５＝｛Ｅ｝、Ｇｒ−６＝｛Ｆ｝、Ｇｒ−７＝｛Ｇ｝、
Ｇｒ−８＝｛Ｈ｝、Ｇｒ−９＝｛Ｉ｝、Ｇｒ−１０＝｛Ｊ｝      （１）
次いで、ｊ＝３（Ｃ列）では、都市間距離ｘ１〜ｘ８の記載が無いのでグループ化は行われない。ｊ＝４（Ｄ列）では、ｉ＝３（Ｃ行）に都市間距離ｘ２が有るので、これをグループ化する。この場合、配送先Ｄは、配送先ＣのグループＩＤにそろえる。従って、この段階でのそれぞれのグループの集合は（２）式となる。
【００３０】
Ｇｒ−１＝｛Ａ、Ｂ｝、Ｇｒ−３＝｛Ｃ、Ｄ｝、Ｇｒ−５＝｛Ｅ｝、
Ｇｒ−６＝｛Ｆ｝、Ｇｒ−７＝｛Ｇ｝、Ｇｒ−８＝｛Ｈ｝、
Ｇｒ−９＝｛Ｉ｝、Ｇｒ−１０＝｛Ｊ｝                          （２）
さらに、ｊ＝５（Ｅ列）ではｉ＝１，２に都市間距離ｘ３，ｘ４が有るため、配送先Ａ、Ｂとグループ化されるため、配送先Ｅは、Ｇｒ−１となる。従って、それぞれのグループの集合は（３）式となる。
【００３１】
Ｇｒ−１＝｛Ａ、Ｂ、Ｅ｝、  Ｇｒ−３＝｛Ｃ、Ｄ｝、
Ｇｒ−６＝｛Ｆ｝、Ｇｒ−７＝｛Ｇ｝、Ｇｒ−８＝｛Ｈ｝、
Ｇｒ−９＝｛Ｉ｝、Ｇｒ−１０＝｛Ｊ｝              （３）
上記の処理をｊ＝１０（Ｊ列）まで続けると、グループの集合は（４）式となる。
【００３２】
Ｇｒ−１＝｛Ａ、Ｂ、Ｅ｝、Ｇｒ−３＝｛Ｃ、Ｄ、Ｆ、Ｊ｝、
Ｇｒ−７＝｛Ｇ、Ｈ、Ｉ｝                    （４）
以上の方法により、都市数をｎとすると、都市間距離の演算はｎ（ｎ−１）／２回、グループＩＤの有無の判定はｎ（ｎ−１）／２回、グループＩＤの付与はｎ個となり、全体の計算量はｎ２回のオーダで済むことになる。
【００３３】
このように、ｓｔｅｐ２の処理（図４）によって、図５（ａ）の状態から、図５（ｂ）のように１０都市を３つのグループに分割することができる。その結果、Ｇｒ−１がＡ、Ｂ、Ｅとなり、Ｇｒ−３がＣ、Ｄ、Ｆ、Ｊとなり、Ｇｒ−７がＧ、Ｈ、Ｉとなる。
【００３４】
これにより、配送エリアが３分割され、それぞれのグループごとで配車計画を策定することができる。この配送エリアのグループへの分割に基づき、オーダについてもグループ化を行う。それぞれのグループごとで、オーダの情報（配送時刻指定、車種指定等）による制約条件、また、計画策定上の制約条件（積載率、同一荷主のオーダ集約等）を考慮し、積載率もしくは車輌台数、走行距離を評価関数とする探索問題として、配車計画の解を求める。解の探索方法としては、遺伝的アルゴリズム、一般化割り当て問題などを適用する。
【００３５】
それぞれのグループごとに計算された配車計画結果は、すべて図１の配車計画策定部署端末から確認することが可能であり、計画結果の内容の修正が可能なインターフェイスも備えている。図１の配車計画策定部署端末で配車計画の内容の確認、修正（図２のＳ５）後、問題が無ければ（図２のＳ６）、確定、送信（図２のＳ７）を端末上から操作する。
【００３６】
【発明の効果】
本発明は、オーダを配送先に応じて分割しているので、配送計画の立案処理を分割されたオーダグループごとに実行させることができる。さらに、所定距離以下の配送先間の組み合わせを抽出する配送先グループ化手段を備え、それに基づき抽出されたオーダのグループを作成することにより、探索に要する計算量を大幅に削減できる。その結果、広域で低密度な複数の配送先に積み荷を配送する配送計画が可能となる。
【図面の簡単な説明】
【図１】本発明の配送計画立案システムの一実施形態を示す構成図である。
【図２】本発明の計画策定手順を示すフローチャートである。
【図３】配送先間が指定した距離以下の組み合わせを算出するフローチャートである。
【図４】配送先エリアの分割アルゴリズムを示すフローチャートである。
【図５】配送先エリアの都市の分割の例を示す図である。（ａ）分割前の状態      （ｂ）分割後の状態
【図１】
2004238129.tif 000003
【図２】
2004238129.tif 000004
【図３】
2004238129.tif 000005
【図４】
2004238129.tif 000006
【図５】
2004238129.tif 000007