【手続補正書】
【提出日】平成30年12月20日(2018.12.20)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
配送物を需要のある配送拠点に配送する配送問題において、初期条件が示す配送問題をより規模の小さな配送問題に分割する分割部と、
前記分割部が分割した後の配送問題について配送計画を生成する配送計画生成部と、
を備え、
前記分割部は、前記配送物の需要がある配送拠点群に含まれる一つの需要点と、前記配送物の供給元となる配送拠点群に含まれる一つの供給点とを、当該一つの需要点から当該一つの供給点への移動時間が最小となるように対応付け、対応付けた前記需要点および前記供給点の組み合わせの集合を生成し、前記初期条件が示す配送問題を、前記生成した集合内に含まれる需要点群から供給点群への配送問題に分割する、
配送計画システム。
【請求項２】
前記分割部は、生成した集合内に含まれる複数の供給点と複数の需要点との対応関係のうち、一つの供給点から一つの需要点への移動時間が所定の値以下となる供給点から需要点への配送ルートを計算し、
前記配送計画生成部は、前記生成した集合内に含まれる供給点群から需要点群への配送ルートのうち移動時間が前記所定の閾値以下となる配送ルートを用いて、前記規模の小さな配送問題に対する配送計画を生成する、
請求項１に記載の配送計画システム。
【請求項３】
配送物を需要のある配送拠点に配送する配送問題において、初期条件が示す配送問題をより規模の小さな配送問題に分割する分割部と、
前記分割部が分割した後の配送問題について配送計画を生成する配送計画生成部と、
を備え、
前記分割部は、出発拠点を出発して一部の配送拠点間に係る配送を行って前記出発拠点に戻るまでの予め設定された配送ルートとその配送ルートで配送したときのコストとを示す単位経路情報を複数取得し、前記複数の単位経路情報の組み合わせのうち、当該組み合わせに含まれる前記配送拠点の数が所定の数以内で、且つ、前記コストの合計が最小となる組み合わせを算出し、その組み合わせに含まれる出発拠点と配送拠点の集合を生成し、前記初期条件が示す配送問題を、前記生成した出発拠点と配送拠点の集合内に含まれる需要点群から供給点群への配送問題に分割する、
配送計画システム。
【請求項４】
前記分割部は、列生成法により、前記単位経路情報の組み合わせを算出する、
請求項３に記載の配送計画システム。
【請求項５】
配送物を需要のある配送拠点に配送する配送問題において、初期条件が示す配送問題をより規模の小さな配送問題に分割する分割部と、
前記分割部が分割した後の配送問題について配送計画を生成する配送計画生成部と、
を備え、
前記分割部は、前記配送物の配送制限時間を複数の時間に分割することにより前記初期条件が示す配送問題を前記分割した時間ごとの配送問題に分割し、
前記配送計画生成部は、前記分割後の各時間の最初の時刻における前記配送物の配送状況から当該分割後の各時間内に前記配送物がなるべく多く需要のある拠点に配送されるような配送計画を生成する、
配送計画システム。
【請求項６】
前記分割部が分割してできた最後の時間に係る配送問題について、
前記配送計画生成部は、前記最後の時間が終了するまでに、前記初期条件で示された需要のある配送拠点の全てに前記配送物が配送されるよう配送計画を生成する、
請求項５に記載の配送計画システム。
【請求項７】
配送物を需要のある配送拠点に配送する配送問題において、初期条件が示す配送問題をより規模の小さな配送問題に分割する分割部と、
前記分割部が分割した後の配送問題について配送計画を生成する配送計画生成部と、
を備え、
前記分割部は、前記初期条件が示す配送問題を、前記初期条件に含まれる配送制限時間よりも所定の時間だけ短い第一配送制限時間を新たな配送制限時間とする配送問題に分割し、
前記配送計画生成部は、前記第一配送制限時間内に前記配送物がなるべく多く需要のある拠点に配送されるような配送計画を生成する、
配送計画システム。
【請求項８】
前記分割部は、前記第一配送制限時間に続く所定長さの時間を第二配送制限時間として設定し、
前記配送計画生成部は、当該第二配送制限時間内に前記配送物がなるべく多く需要のある拠点に配送されるような配送計画を生成する、
請求項７に記載の配送計画システム。
【請求項９】
前記配送計画生成部は、前記生成した配送計画を実行した場合の完了時点を開始時刻とし、前記第一配送制限時間の開始時刻を基準にして前記初期条件に含まれる配送制限時間が経過する時刻を終了時刻とする最後の時間内に、前記配送計画の実行の結果、配送が完了していない配送物について配送し終える配送計画を生成する、
請求項７または請求項８に記載の配送計画システム。
【請求項１０】
前記配送物がなるべく多く需要がある拠点に配送されるような配送計画の生成にあたり、前記配送計画生成部は、前記配送計画を実行した結果、前記配送計画の実行に必要な配送スタッフと配送手段が前記配送拠点に残らないことを条件に配送計画を生成する、
請求項５から請求項９の何れか１項に記載の配送計画システム。
【請求項１１】
前記配送計画生成部は、前記配送物を配送する配送主体と前記配送物または前記配送主体を移動する配送手段の初期位置を示す出発拠点および前記配送拠点と配送開始の時を基準とする各時刻とを組にした点情報と、前記点情報のうち前記配送物の配送に係る２つの点情報の間の、前記配送に係る前記配送物および前記配送主体および前記配送手段の流量を示す枝情報と、で構成される時空間ネットワークモデルに基づく整数計画問題を解いて、前記分割部による分割後の配送問題における前記配送に係る枝情報の集合を少なくとも１つ生成する、
請求項１から請求項１０の何れか１項に記載の配送計画システム。
【請求項１２】
前記配送計画生成部は、前記時空間ネットワークモデルにおいて、一つの前記配送拠点について、その配送拠点の入口と時刻とを組にした入口に係る点情報と、その配送拠点の出口と時刻とを組にした出口に係る点情報と、その配送拠点に係る配送物１個ずつに対して時刻を組にした配送物の置き場に係る点情報とを生成し、前記入口に係る点情報と前記配送物に係る点情報との間、前記出口に係る点情報と前記配送物に係る点情報との間、における前記配送主体および前記配送物の流量の値を０または１に設定する、
請求項１１に記載の配送計画システム。
【請求項１３】
配送計画システムが、
配送物を需要のある配送拠点に配送する配送問題において、初期条件が示す配送問題をより規模の小さな配送問題に分割するステップと、
前記分割した後の配送問題について配送計画を生成するステップと、
を有し、
前記分割するステップでは、前記配送物の需要がある配送拠点群に含まれる一つの需要点と、前記配送物の供給元となる配送拠点群に含まれる一つの供給点とを、当該一つの需要点から当該一つの供給点への移動時間が最小となるように対応付け、対応付けた前記需要点および前記供給点の組み合わせの集合を生成し、前記初期条件が示す配送問題を、前記生成した集合内に含まれる需要点群から供給点群への配送問題に分割する、
配送計画方法。
【請求項１４】
配送計画システムのコンピュータを、
配送物を需要のある配送拠点に配送する配送問題において、初期条件が示す配送問題をより規模の小さな配送問題に分割する手段、
前記分割した後の配送問題について配送計画を生成する手段、
として機能させ、
前記分割する手段は、前記配送物の需要がある配送拠点群に含まれる一つの需要点と、前記配送物の供給元となる配送拠点群に含まれる一つの供給点とを、当該一つの需要点から当該一つの供給点への移動時間が最小となるように対応付け、対応付けた前記需要点および前記供給点の組み合わせの集合を生成し、前記初期条件が示す配送問題を、前記生成した集合内に含まれる需要点群から供給点群への配送問題に分割する、
プログラム。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】０００９
【補正方法】変更
【補正の内容】
【０００９】
本発明の第１〜第１２の態様によれば、配送計画システムは、配送物を需要のある配送拠点に配送する配送問題において、初期条件が示す配送問題をより規模の小さな配送問題に分割する分割部と、前記分割部が分割した後の配送問題について配送計画を生成する配送計画生成部と、を備える。
大規模な配送問題を規模の小さな配送問題に分割し、小さな配送問題の単位で配送計画を算出することで、実用的な時間で配送計画を生成することができる。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】００１０
【補正方法】変更
【補正の内容】
【００１０】
本発明の第１の態様における前記分割部は、前記配送物の需要がある配送拠点群に含まれる一つの需要点と、前記配送物の供給元となる配送拠点群に含まれる一つの供給点とを、当該一つの需要点から当該一つの供給点への移動時間が最小となるように対応付け、対応付けた前記需要点および前記供給点の組み合わせの集合を生成し、前記初期条件が示す配送問題を、前記生成した集合内に含まれる需要点群から供給点群への配送問題に分割してもよい。
初期条件に含まれる配送拠点ごとの需要と供給の情報に基づいて、配送エリアを、近距離に存在する配送拠点の集合ごとの配送エリア単位に分割し、分割後の配送エリア単位で配送計画を算出することで、実用的な時間で配送計画を生成することができる。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】００１１
【補正方法】変更
【補正の内容】
【００１１】
本発明の第２の態様における前記分割部は、生成した集合内に含まれる複数の供給点と複数の需要点との対応関係のうち、一つの供給点から一つの需要点への移動時間が所定の値以下となる供給点から需要点への配送ルートを計算し、前記配送計画生成部は、前記生成した集合内に含まれる供給点群から需要点群への配送ルートのうち移動時間が前記所定の閾値以下となる配送ルートを用いて、前記規模の小さな配送問題に対する配送計画を生成してもよい。
移動時間が閾値以下となる配送拠点間の配送ルートの情報を用いて配送計画を生成するので、配送計画の生成に必要な計算量を減らすことができる。
【手続補正５】
【補正対象書類名】明細書
【補正対象項目名】００１２
【補正方法】変更
【補正の内容】
【００１２】
本発明の第３の態様における前記分割部は、出発拠点を出発して一部の配送拠点間に係る配送を行って前記出発拠点に戻るまでの予め設定された配送ルートとその配送ルートで配送したときのコストとを示す単位経路情報を複数取得し、前記複数の単位経路情報の組み合わせのうち、当該組み合わせに含まれる前記配送拠点の数が所定の数以内で、且つ、前記コストの合計が最小となる組み合わせを算出し、その組み合わせに含まれる出発拠点と配送拠点の集合を生成し、前記初期条件が示す配送問題を、前記生成した出発拠点と配送拠点の集合内に含まれる需要点群から供給点群への配送問題に分割してもよい。
ある出発拠点を基準に、所定の数以内の複数の配送拠点における需要を満たしつつ配送コストが最小になる配送ルートの組み合わせを算出し、それら複数の配送拠点と出発拠点の集合を１つの配送エリアとする。初期条件で与えられた全ての配送拠点を対象とする配送エリアを、このようにして生成した配送エリアに分割し、配送エリア単位で配送計画を算出することで、実用的な時間で配送計画を生成することができる。
【手続補正６】
【補正対象書類名】明細書
【補正対象項目名】００１３
【補正方法】変更
【補正の内容】
【００１３】
本発明の第４の態様における前記分割部は、列生成法により、前記単位経路情報の組み合わせを算出する。
列生成法を用いることで高速に配送エリアを生成することができる。
【手続補正７】
【補正対象書類名】明細書
【補正対象項目名】００１４
【補正方法】変更
【補正の内容】
【００１４】
本発明の第５の態様における前記分割部は、前記配送物の配送制限時間を複数の時間に分割することにより前記初期条件が示す配送問題を前記分割した時間ごとの配送問題に分割し、前記配送計画生成部は、前記分割後の各時間の最初の時刻における前記配送物の配送状況から当該分割後の各時間内に前記配送物がなるべく多く需要のある拠点に配送されるような配送計画を生成してもよい。
【手続補正８】
【補正対象書類名】明細書
【補正対象項目名】００１５
【補正方法】変更
【補正の内容】
【００１５】
本発明の第６の態様における前記配送計画生成部は、前記分割部が分割してできた最後の時間に係る配送問題について、前記最後の時間が終了するまでに、前記初期条件で示された需要のある配送拠点の全てに前記配送物が配送されるよう配送計画を生成してもよい。
第５、６の態様によれば、初期条件で与えられた配送制限時間を分割し、分割後の時間単位の配送問題について配送計画を算出することで、実用的な時間で配送計画を生成することができる。
【手続補正９】
【補正対象書類名】明細書
【補正対象項目名】００１６
【補正方法】変更
【補正の内容】
【００１６】
本発明の第７の態様における前記分割部は、前記初期条件が示す配送問題を、前記初期条件に含まれる配送制限時間よりも所定の時間だけ短い第一配送制限時間を新たな配送制限時間とする配送問題に分割し、前記配送計画生成部は、前記第一配送制限時間内に前記配送物がなるべく多く需要のある拠点に配送されるような配送計画を生成してもよい。
【手続補正１０】
【補正対象書類名】明細書
【補正対象項目名】００１７
【補正方法】変更
【補正の内容】
【００１７】
本発明の第８の態様における前記分割部は、前記第一配送制限時間に続く所定長さの時間を第二配送制限時間として設定し、前記配送計画生成部は、当該第二配送制限時間内に前記配送物がなるべく多く需要のある拠点に配送されるような配送計画を生成してもよい。
【手続補正１１】
【補正対象書類名】明細書
【補正対象項目名】００１８
【補正方法】変更
【補正の内容】
【００１８】
本発明の第９の態様における前記配送計画生成部は、前記生成した配送計画を実行した場合の完了時点を開始時刻とし、前記第一配送制限時間の開始時刻を基準にして前記初期条件に含まれる配送制限時間が経過する時刻を終了時刻とする最後の時間内に、前記配送計画の実行の結果、配送が完了していない配送物について配送し終える配送計画を生成してもよい。
第７〜９の態様によれば、初期条件で与えられた配送制限時間より短い時間を配送制限時間に設定し、配送制限時間を延長しながら配送計画を生成する。初期条件が示す配送問題を設定または延長した配送制限時間ごとの規模の小さな配送問題に分割することで、実用的な時間で配送計画を生成することができる。
【手続補正１２】
【補正対象書類名】明細書
【補正対象項目名】００１９
【補正方法】変更
【補正の内容】
【００１９】
本発明の第１０の態様では、前記配送物がなるべく多く需要のある拠点に配送されるような配送計画の生成にあたり、前記配送計画生成部は、前記配送計画を実行した結果、前記配送計画に必要な配送スタッフと配送手段が前記配送拠点に残らないことを条件に配送計画を生成してもよい。
なるべく多くの配送物を配送するだけではなく、分割後の時間のうち後の時間に使用しない余分な配送スタッフと配送手段が配送拠点に残らないような配送計画を生成することができる。
【手続補正１３】
【補正対象書類名】明細書
【補正対象項目名】００２０
【補正方法】変更
【補正の内容】
【００２０】
本発明の第１１の態様における前記配送計画生成部は、前記配送物を配送する配送主体と前記配送物または前記配送主体を移動する配送手段の初期位置を示す出発拠点および前記配送拠点と配送開始の時を基準とする各時刻とを組にした点情報と、前記点情報のうち前記配送物の配送に係る２つの点情報の間の、前記配送に係る前記配送物および前記配送主体および前記配送手段の流量を示す枝情報と、で構成される時空間ネットワークモデルに基づく整数計画問題を解いて、前記分割部による分割後の配送問題における前記配送に係る枝情報の集合を少なくとも１つ生成してもよい。
配送問題を時空間ネットワークモデルでモデル化することで搭乗輸送を含む配送問題について配送計画を生成することができる。
【手続補正１４】
【補正対象書類名】明細書
【補正対象項目名】００２１
【補正方法】変更
【補正の内容】
【００２１】
本発明の第１２の態様によれば、前記配送計画生成部は、前記時空間ネットワークモデルにおいて、一つの前記配送拠点について、その配送拠点の入口と時刻とを組にした入口に係る点情報と、その配送拠点の出口と時刻とを組にした出口に係る点情報と、その配送拠点に係る配送物１個ずつに対して時刻を組にした配送物の置き場に係る点情報とを生成し、前記入口に係る点情報と前記配送物に係る点情報との間、前記出口に係る点情報と前記配送物に係る点情報との間、における前記配送主体および前記配送物の流量の値を０または１に設定してもよい。
配送拠点内を入口、出口、配送物一つずつの置き場に分けて扱うことで、それらの場所それぞれの状況を０と１で表すことができるので、配送拠点内を０−１整数計画問題として扱えるようになり計算処理を高速化できる。
【手続補正１５】
【補正対象書類名】明細書
【補正対象項目名】００２２
【補正方法】変更
【補正の内容】
【００２２】
本発明の第１３の態様によれば、配送計画システムが、配送物を需要のある配送拠点に配送する配送問題において、初期条件が示す配送問題をより規模の小さな配送問題に分割するステップと、前記分割した後の配送問題について配送計画を生成するステップと、を有し、前記分割するステップでは、前記配送物の需要がある配送拠点群に含まれる一つの需要点と、前記配送物の供給元となる配送拠点群に含まれる一つの供給点とを、当該一つの需要点から当該一つの供給点への移動時間が最小となるように対応付け、対応付けた前記需要点および前記供給点の組み合わせの集合を生成し、前記初期条件が示す配送問題を、前記生成した集合内に含まれる需要点群から供給点群への配送問題に分割する、配送計画方法である。
【手続補正１６】
【補正対象書類名】明細書
【補正対象項目名】００２３
【補正方法】変更
【補正の内容】
【００２３】
本発明の第１４の態様によれば、プログラムは、配送計画システムのコンピュータを、配送物を需要のある配送拠点に配送する配送問題において、初期条件が示す配送問題をより規模の小さな配送問題に分割する手段、前記分割した後の配送問題について配送計画を生成する手段、として機能させ、前記分割する手段は、前記配送物の需要がある配送拠点群に含まれる一つの需要点と、前記配送物の供給元となる配送拠点群に含まれる一つの供給点とを、当該一つの需要点から当該一つの供給点への移動時間が最小となるように対応付け、対応付けた前記需要点および前記供給点の組み合わせの集合を生成し、前記初期条件が示す配送問題を、前記生成した集合内に含まれる需要点群から供給点群への配送問題に分割する。