(57)【要約】【課題】大規模な配送問題であっても実用的な時間で配送計画を立案することができる配送計画システムを提供する。【解決手段】配送計画システムは、配送物を需要のある配送拠点に配送する配送問題において、初期条件に含まれる配送拠点ごとの需要および供給の情報、又は、配送物の配送制限時間の情報に基づいて、初期条件が示す配送問題をより規模の小さな配送問題に分割する分割部と、分割部が分割した後の配送問題について配送計画を生成する配送計画生成部と、を備える。【選択図】図１
2018073213.tif 000002
【特許請求の範囲】
【請求項１】
配送物を需要のある配送拠点に配送する配送問題において、初期条件が示す配送問題をより規模の小さな配送問題に分割する分割部と、
前記分割部が分割した後の配送問題について配送計画を生成する配送計画生成部と、
を備える配送計画システム。
【請求項２】
前記分割部は、前記配送物の需要がある配送拠点群に含まれる一つの需要点と、前記配送物の供給元となる配送拠点群に含まれる一つの供給点とを、当該一つの需要点から当該一つの供給点への移動時間が最小となるように対応付け、対応付けた前記需要点および前記供給点の組み合わせの集合を生成し、前記初期条件が示す配送問題を、前記生成した集合内に含まれる需要点群から供給点群への配送問題に分割する、
請求項１に記載の配送計画システム。
【請求項３】
前記分割部は、生成した集合内に含まれる複数の供給点と複数の需要点との対応関係のうち、一つの供給点から一つの需要点への移動時間が所定の値以下となる供給点から需要点への配送ルートを計算し、
前記配送計画生成部は、前記生成した集合内に含まれる供給点群から需要点群への配送ルートのうち移動時間が前記所定の閾値以下となる配送ルートを用いて、前記規模の小さな配送問題に対する配送計画を生成する、
請求項２に記載の配送計画システム。
【請求項４】
前記分割部は、出発拠点を出発して一部の配送拠点間に係る配送を行って前記出発拠点に戻るまでの予め設定された配送ルートとその配送ルートで配送したときのコストとを示す単位経路情報を複数取得し、前記複数の単位経路情報の組み合わせのうち、当該組み合わせに含まれる前記配送拠点の数が所定の数以内で、且つ、前記コストの合計が最小となる組み合わせを算出し、その組み合わせに含まれる出発拠点と配送拠点の集合を生成し、前記初期条件が示す配送問題を、前記生成した出発拠点と配送拠点の集合内に含まれる需要点群から供給点群への配送問題に分割する、
請求項１に記載の配送計画システム。
【請求項５】
前記分割部は、列生成法により、前記単位経路情報の組み合わせを算出する、
請求項４に記載の配送計画システム。
【請求項６】
前記分割部は、前記配送物の配送制限時間を複数の時間に分割することにより前記初期条件が示す配送問題を前記分割した時間ごとの配送問題に分割し、
前記配送計画生成部は、前記分割後の各時間の最初の時刻における前記配送物の配送状況から当該分割後の各時間内に前記配送物がなるべく多く需要のある拠点に配送されるような配送計画を生成する、
請求項１に記載の配送計画システム。
【請求項７】
前記分割部が分割してできた最後の時間に係る配送問題について、
前記配送計画生成部は、前記最後の時間が終了するまでに、前記初期条件で示された需要のある配送拠点の全てに前記配送物が配送されるよう配送計画を生成する、
請求項６に記載の配送計画システム。
【請求項８】
前記分割部は、前記初期条件が示す配送問題を、前記初期条件に含まれる配送制限時間よりも所定の時間だけ短い第一配送制限時間を新たな配送制限時間とする配送問題に分割し、
前記配送計画生成部は、前記第一配送制限時間内に前記配送物がなるべく多く需要のある拠点に配送されるような配送計画を生成する、
請求項１に記載の配送計画システム。
【請求項９】
前記分割部は、前記第一配送制限時間に続く所定長さの時間を第二配送制限時間として設定し、
前記配送計画生成部は、当該第二配送制限時間内に前記配送物がなるべく多く需要のある拠点に配送されるような配送計画を生成する、
請求項８に記載の配送計画システム。
【請求項１０】
前記配送計画生成部は、前記生成した配送計画を実行した場合の完了時点を開始時刻とし、前記第一配送制限時間の開始時刻を基準にして前記初期条件に含まれる配送制限時間が経過する時刻を終了時刻とする最後の時間内に、前記配送計画の実行の結果、配送が完了していない配送物について配送し終える配送計画を生成する、
請求項８または請求項９に記載の配送計画システム。
【請求項１１】
前記配送物がなるべく多く需要がある拠点に配送されるような配送計画の生成にあたり、前記配送計画生成部は、前記配送計画を実行した結果、前記配送計画の実行に必要な配送スタッフと配送手段が前記配送拠点に残らないことを条件に配送計画を生成する、
請求項６から請求項１０の何れか１項に記載の配送計画システム。
【請求項１２】
前記配送計画生成部は、前記配送物を配送する配送主体と前記配送物または前記配送主体を移動する配送手段の初期位置を示す出発拠点および前記配送拠点と配送開始の時を基準とする各時刻とを組にした点情報と、前記点情報のうち前記配送物の配送に係る２つの点情報の間の、前記配送に係る前記配送物および前記配送主体および前記配送手段の流量を示す枝情報と、で構成される時空間ネットワークモデルに基づく整数計画問題を解いて、前記分割部による分割後の配送問題における前記配送に係る枝情報の集合を少なくとも１つ生成する、
請求項１から請求項１１の何れか１項に記載の配送計画システム。
【請求項１３】
前記配送計画生成部は、前記時空間ネットワークモデルにおいて、一つの前記配送拠点について、その配送拠点の入口と時刻とを組にした入口に係る点情報と、その配送拠点の出口と時刻とを組にした出口に係る点情報と、その配送拠点に係る配送物１個ずつに対して時刻を組にした配送物の置き場に係る点情報とを生成し、前記入口に係る点情報と前記配送物に係る点情報との間、前記出口に係る点情報と前記配送物に係る点情報との間、における前記配送主体および前記配送物の流量の値を０または１に設定する、
請求項１２に記載の配送計画システム。
【請求項１４】
配送計画システムが、
配送物を需要のある配送拠点に配送する配送問題において、初期条件が示す配送問題をより規模の小さな配送問題に分割し、
前記分割した後の配送問題について配送計画を生成する、
配送計画方法。
【請求項１５】
配送計画システムのコンピュータを、
配送物を需要のある配送拠点に配送する配送問題において、初期条件が示す配送問題をより規模の小さな配送問題に分割する手段、
前記分割した後の配送問題について配送計画を生成する手段、
として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、配送計画システム、配送計画方法及びプログラムに関する。
【背景技術】
【０００２】
カーシェアリングへのニーズが高まっている。カーシェアリングとは、例えば、会員の間などで車両を共同で利用し、搭乗時間などに応じて料金を負担し、自分の好きな時に車両を利用するシステムである。カーシェアリングの一つの形態として、乗り捨て型（ワンウェイ型）と呼ばれる利用形態が存在する。乗り捨て型のカーシェアリングでは、ユーザは、目的地近くの所定の駐車場まで共同の車両を利用し、その自動車を駐車場にそのまま乗り捨てておくことができる。このような形態のカーシェアリングでは、ユーザが利用し終えた車両を、新たな利用ニーズがある他の駐車場に配送する必要が生じる。
【０００３】
また、顧客が購入した製品に対するアフターサービスを行うために、サービスマンが客先を回る、いわゆるアフターサービス巡回の場合にも、サービスマン及びサービスの提供に必要な部品等の移動について同様の事情が生じる。例えば、複数の客先のそれぞれにアフターサービス対象となる製品が設置されており、サービスマンがその製品のアフターサービスに使う部品をある場所で調達して客先に運んだり、１回の巡回で様々な種類のアフターサービスを行うサービスマンが、サービスの提供に同じ部品を必要とするある客先から他の客先へ移動し、さらに使用後の部品を元へ戻したりといった場面で効率的な巡回方法を選択する必要が生じる。
【０００４】
このような問題に対し、例えば特許文献１には、複数の配送拠点から、複数の輸送手段を用いて、複数の配送先に指定された日時に荷物を輸送する輸送計画を作成する技術について開示がある。この技術を用いれば、カーシェアリングの場合、ユーザが利用する車両をトラック等の輸送手段に積載して各駐車場に輸送する輸送計画を作成することができる。また、アフターサービス巡回においても、サービスに用いる部品を客先に配送する配送計画を作成することができる。
【０００５】
しかし、カーシェアリングで車両を配送する場合、配送スタッフが配送対象の車両に搭乗し、目的の駐車場まで運転するという車両の配送方法も存在する。このように配送物自身に搭乗して配送する方法を搭乗輸送という。搭乗輸送を含む配送において、最適な配送計画を行う技術は提供されていない。
また、アフターサービス巡回においても、サービスマンが部品を持って移動する場合や、ある客先から他の客先へ部品を配送する場合や、余った部品をサービスマンが持って次の客先に向かう場合などについては、搭乗輸送の場合と同様に、サービスマンの最適な巡回計画を行う技術は提供されていない。
また、一般に離散値の組合せ最適化問題は、線形緩和と呼ばれる手法、すなわち一旦、問題を連続値問題に置き換えて解き、得られる緩和解から最適解を求める手法、を用いることが多いが、配送問題のように複雑な制約が多いとそのままでは計算時間が掛かりすぎてしまうため、実用的な時間で解くための工夫が必要となる。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２０１３−１３６４２１号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
ところで、本願の出願人は、上記した搭乗輸送を含む配送において配送計画を行うという課題を解決することができる配送計画システムに関する出願を既に行っている（特願２０１６−０５１５５０）。この配送計画システムを用いると搭乗輸送を含んだ配送問題に対する最適な配送計画を、実用的な時間で求めることができる。
この配送計画システムに関し、配送対象の車両や配送先の増加により問題の規模が大きくなった場合でも、最適な配送計画を実用的な時間で求めることができるよう、計算時間のさらなる短縮化が望まれていた。
【０００８】
そこでこの発明は、上述の課題を解決することのできる配送計画システム、配送計画方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００９】
本発明の第１の態様によれば、配送計画システムは、配送物を需要のある配送拠点に配送する配送問題において、初期条件が示す配送問題をより規模の小さな配送問題に分割する分割部と、前記分割部が分割した後の配送問題について配送計画を生成する配送計画生成部と、を備える。
大規模な配送問題を規模の小さな配送問題に分割し、小さな配送問題の単位で配送計画を算出することで、実用的な時間で配送計画を生成することができる。
【００１０】
本発明の第２の態様における前記分割部は、前記配送物の需要がある配送拠点群に含まれる一つの需要点と、前記配送物の供給元となる配送拠点群に含まれる一つの供給点とを、当該一つの需要点から当該一つの供給点への移動時間が最小となるように対応付け、対応付けた前記需要点および前記供給点の組み合わせの集合を生成し、前記初期条件が示す配送問題を、前記生成した集合内に含まれる需要点群から供給点群への配送問題に分割してもよい。
初期条件に含まれる配送拠点ごとの需要と供給の情報に基づいて、配送エリアを、近距離に存在する配送拠点の集合ごとの配送エリア単位に分割し、分割後の配送エリア単位で配送計画を算出することで、実用的な時間で配送計画を生成することができる。
【００１１】
本発明の第３の態様における前記分割部は、生成した集合内に含まれる複数の供給点と複数の需要点との対応関係のうち、一つの供給点から一つの需要点への移動時間が所定の値以下となる供給点から需要点への配送ルートを計算し、前記配送計画生成部は、前記生成した集合内に含まれる供給点群から需要点群への配送ルートのうち移動時間が前記所定の閾値以下となる配送ルートを用いて、前記規模の小さな配送問題に対する配送計画を生成してもよい。
移動時間が閾値以下となる配送拠点間の配送ルートの情報を用いて配送計画を生成するので、配送計画の生成に必要な計算量を減らすことができる。
【００１２】
本発明の第４の態様における前記分割部は、出発拠点を出発して一部の配送拠点間に係る配送を行って前記出発拠点に戻るまでの予め設定された配送ルートとその配送ルートで配送したときのコストとを示す単位経路情報を複数取得し、前記複数の単位経路情報の組み合わせのうち、当該組み合わせに含まれる前記配送拠点の数が所定の数以内で、且つ、前記コストの合計が最小となる組み合わせを算出し、その組み合わせに含まれる出発拠点と配送拠点の集合を生成し、前記初期条件が示す配送問題を、前記生成した出発拠点と配送拠点の集合内に含まれる需要点群から供給点群への配送問題に分割してもよい。
ある出発拠点を基準に、所定の数以内の複数の配送拠点における需要を満たしつつ配送コストが最小になる配送ルートの組み合わせを算出し、それら複数の配送拠点と出発拠点の集合を１つの配送エリアとする。初期条件で与えられた全ての配送拠点を対象とする配送エリアを、このようにして生成した配送エリアに分割し、配送エリア単位で配送計画を算出することで、実用的な時間で配送計画を生成することができる。
【００１３】
本発明の第５の態様における前記分割部は、列生成法により、前記単位経路情報の組み合わせを算出する。
列生成法を用いることで高速に配送エリアを生成することができる。
【００１４】
本発明の第６の態様における前記分割部は、前記配送物の配送制限時間を複数の時間に分割することにより前記初期条件が示す配送問題を前記分割した時間ごとの配送問題に分割し、前記配送計画生成部は、前記分割後の各時間の最初の時刻における前記配送物の配送状況から当該分割後の各時間内に前記配送物がなるべく多く需要のある拠点に配送されるような配送計画を生成してもよい。
【００１５】
本発明の第７の態様における前記配送計画生成部は、前記分割部が分割してできた最後の時間に係る配送問題について、前記最後の時間が終了するまでに、前記初期条件で示された需要のある配送拠点の全てに前記配送物が配送されるよう配送計画を生成してもよい。
第６、７の態様によれば、初期条件で与えられた配送制限時間を分割し、分割後の時間単位の配送問題について配送計画を算出することで、実用的な時間で配送計画を生成することができる。
【００１６】
本発明の第８の態様における前記分割部は、前記初期条件が示す配送問題を、前記初期条件に含まれる配送制限時間よりも所定の時間だけ短い第一配送制限時間を新たな配送制限時間とする配送問題に分割し、前記配送計画生成部は、前記第一配送制限時間内に前記配送物がなるべく多く需要のある拠点に配送されるような配送計画を生成してもよい。
【００１７】
本発明の第９の態様における前記分割部は、前記第一配送制限時間に続く所定長さの時間を第二配送制限時間として設定し、前記配送計画生成部は、当該第二配送制限時間内に前記配送物がなるべく多く需要のある拠点に配送されるような配送計画を生成してもよい。
【００１８】
本発明の第１０の態様における前記配送計画生成部は、前記生成した配送計画を実行した場合の完了時点を開始時刻とし、前記第一配送制限時間の開始時刻を基準にして前記初期条件に含まれる配送制限時間が経過する時刻を終了時刻とする最後の時間内に、前記配送計画の実行の結果、配送が完了していない配送物について配送し終える配送計画を生成してもよい。
第８〜１０の態様によれば、初期条件で与えられた配送制限時間より短い時間を配送制限時間に設定し、配送制限時間を延長しながら配送計画を生成する。初期条件が示す配送問題を設定または延長した配送制限時間ごとの規模の小さな配送問題に分割することで、実用的な時間で配送計画を生成することができる。
【００１９】
本発明の第１１の態様では、前記配送物がなるべく多く需要のある拠点に配送されるような配送計画の生成にあたり、前記配送計画生成部は、前記配送計画を実行した結果、前記配送計画に必要な配送スタッフと配送手段が前記配送拠点に残らないことを条件に配送計画を生成してもよい。
なるべく多くの配送物を配送するだけではなく、分割後の時間のうち後の時間に使用しない余分な配送スタッフと配送手段が配送拠点に残らないような配送計画を生成することができる。
【００２０】
本発明の第１２の態様における前記配送計画生成部は、前記配送物を配送する配送主体と前記配送物または前記配送主体を移動する配送手段の初期位置を示す出発拠点および前記配送拠点と配送開始の時を基準とする各時刻とを組にした点情報と、前記点情報のうち前記配送物の配送に係る２つの点情報の間の、前記配送に係る前記配送物および前記配送主体および前記配送手段の流量を示す枝情報と、で構成される時空間ネットワークモデルに基づく整数計画問題を解いて、前記分割部による分割後の配送問題における前記配送に係る枝情報の集合を少なくとも１つ生成してもよい。
配送問題を時空間ネットワークモデルでモデル化することで搭乗輸送を含む配送問題について配送計画を生成することができる。
【００２１】
本発明の第１３の態様によれば、前記配送計画生成部は、前記時空間ネットワークモデルにおいて、一つの前記配送拠点について、その配送拠点の入口と時刻とを組にした入口に係る点情報と、その配送拠点の出口と時刻とを組にした出口に係る点情報と、その配送拠点に係る配送物１個ずつに対して時刻を組にした配送物の置き場に係る点情報とを生成し、前記入口に係る点情報と前記配送物に係る点情報との間、前記出口に係る点情報と前記配送物に係る点情報との間、における前記配送主体および前記配送物の流量の値を０または１に設定してもよい。
配送拠点内を入口、出口、配送物一つずつの置き場に分けて扱うことで、それらの場所それぞれの状況を０と１で表すことができるので、配送拠点内を０−１整数計画問題として扱えるようになり計算処理を高速化できる。
【００２２】
本発明の第１４の態様によれば、配送計画システムが、配送物を需要のある配送拠点に配送する配送問題において、初期条件が示す配送問題をより規模の小さな配送問題に分割し、前記分割した後の配送問題について配送計画を生成する、配送計画方法である。
【００２３】
本発明の第１５の態様によれば、プログラムは、配送計画システムのコンピュータを、配送物を需要のある配送拠点に配送する配送問題において、初期条件が示す配送問題をより規模の小さな配送問題に分割する手段、前記分割した後の配送問題について配送計画を生成する手段、として機能させる。
【発明の効果】
【００２４】
本発明によれば、実用的な時間で、大規模な配送問題に対するコストや移動時間を最小にする配送計画を立案することができる。
【図面の簡単な説明】
【００２５】
【図１】本発明の第一実施形態における配送計画システムの一例を示す機能ブロック図である。
【図２】本発明の第一実施形態における配送計画の一例を説明する図である。
【図３】本発明の第一実施形態における配送計画に係る第１の時空間ネットワークモデルを説明する図である。
【図４】本発明の第一実施形態における配送計画に係る第２の時空間ネットワークモデルを説明する第一の図である。
【図５】本発明の第一実施形態における配送計画に係る第２の時空間ネットワークモデルを説明する第二の図である。
【図６】本発明の第一実施形態における配送計画に係る第２の時空間ネットワークモデルを説明する第三の図である。
【図７】本発明の第一実施形態における配送計画に係る第２の時空間ネットワークモデルを説明する第四の図である。
【図８】本発明の第一実施形態における配送計画に係る第２の時空間ネットワークモデルを説明する第五の図である。
【図９】本発明の第一実施形態における配送問題の一例を示す図である。
【図１０】配送問題に対して生成した配送計画の一例を示す図である。
【図１１】本発明の第一実施形態における第一エリア分割処理を説明する第一の図である。
【図１２】本発明の第一実施形態における第一エリア分割処理を説明する第二の図である。
【図１３】本発明の第一実施形態における配送計画の生成処理の一例を示すフローチャートである。
【図１４】本発明の第二実施形態における配送計画システムの一例を示す機能ブロック図である。
【図１５】本発明の第二実施形態における配送問題の第二エリア分割処理を説明する第一の図である。
【図１６】本発明の第二実施形態における配送問題の第二エリア分割処理を説明する第二の図である。
【図１７】本発明の第二実施形態における配送問題の第二エリア分割処理を説明する第三の図である。
【図１８】本発明の第二実施形態における配送計画の生成処理の一例を示すフローチャートである。
【図１９】本発明の第三実施形態における配送計画システムの一例を示す機能ブロック図である。
【図２０】本発明の第三実施形態における配送問題の時間分割処理を説明する第一の図である。
【図２１】本発明の第三実施形態における配送問題の時間分割処理を説明する第二の図である。
【図２２】本発明の第三実施形態における配送計画の生成処理の一例を示すフローチャートである。
【発明を実施するための形態】
【００２６】
＜第一実施形態＞
以下、本発明の一実施形態による配送計画システムを図１〜図１３を参照して説明する。
図１は、本発明の第一実施形態における配送計画システムの一例を示す機能ブロック図である。本実施形態において、配送計画システムは、例えば、１台のＰＣやサーバ装置などのコンピュータ装置によって構成される。コンピュータ装置は、ＣＰＵ（Central Processing Unit）などの演算部、及び、ＲＯＭ（Read Only Memory）、ＲＡＭ（Random Access Memory）、ＨＤＤ（Hard Disk Drive）などの記憶部、および、ネットワークインタフェースなどその他のハードウェアを含んで構成されている。
【００２７】
図１の配送計画装置１０は、配送計画システムの一例である。配送計画装置１０は、搭乗輸送を含めた配送計画に対して、コストを最小にする配送手段、配送ルートなどを算出する装置である。本実施形態では、乗り捨て型のカーシェアリングにおいてユーザが共同で利用する車両をユーザが利用を開始する場所へ配送する場面で、その配送を実現する最適な配送計画を立案する方法を例として取り上げる。配送物を配送する場合、例えば、コストを最小にする配送手段、配送ルートを選択することが求められる。コストを最小にする配送計画の立案については、これまでも様々な方法が提供されてきた。しかし、カーシェアリングにおける車両の配送には、例えば、宅配便等で荷物を配送する場合と異なる点がある。それは、車両を配送する場合には、車両に人が搭乗して移動することができるという点である。例えば、拠点Ａ、拠点Ｂ、拠点Ｃ、拠点Ｄ、拠点Ｅのそれぞれの拠点において、車両が余った状態、または、不足した状態があるとする。このような状態の中、車両が余っている拠点から不足している拠点へ車両を移動し、ユーザのニーズに応えられるようにするためには例えば、以下のような方法が考えられる。（１）一人の配送スタッフが、車両を積載することができるトラックで各拠点を回り、余った車両をトラックに搭載し、不足がある拠点まで配送する。（２）配送車に複数の配送スタッフが搭乗し、各拠点を移動する。配送車に搭乗した配送スタッフの一部は、車両が余っている拠点に到着すると、余剰の車両に乗り換え、その車両を車両が不足している拠点まで運転して配送する（搭乗輸送）。このような場合、どちらの配送手段で配送を行えば良いのか、どのようなルートで配送を行えばコストを最小にできるのかを知ることは容易ではない。本実施形態の配送計画装置１０は、搭乗輸送が可能な場合の配送計画に対して、数学的知見に基づいた数理モデルや制約を導入することで、高速で効率的に例えばコストを最小にする配送計画を生成する方法を提供する。また、本実施形態の配送計画装置１０は、配送物を配送拠点に配送する配送計画を生成するにあたり、当該配送の初期条件として与えられた、配送拠点ごとの配送物の需要数量（不足している数量）および供給数量（余っている数量）に基づいて、初期条件が示す配送問題の全体を部分的な規模の小さな配送問題に分割する。これにより、配送する車両や拠点の数が大規模であっても、実用的な時間（例えば１０分）で配送計画を立案することができる。
【００２８】
図１が示すように、配送計画装置１０は、初期条件設定部１１と、配送計画生成部１２と、入出力部１３と、第一エリア分割部１４と、記憶部１５とを備えている。
初期条件設定部１１は、配送主体（例えば配送スタッフ）が搭乗して移動することが可能な配送物（例えばユーザが利用する車両）、配送主体、配送物または配送主体を移動する配送手段（例えばトラック等の配送車）の何れかが留まる場所である配送拠点ごとの配送物の需要数量および供給数量と、配送主体と配送手段の初期位置を示す一つ又は複数の出発拠点（例えばカーシェアリングのサービスを提供する企業の運用拠点）の情報と、出発拠点における利用可能な配送手段および配送主体の情報と、配送期限の情報、などの情報を、配送計画を生成するうえでの初期条件として設定する。これらのパラメータについては後に詳しく説明する。
配送計画生成部１２は、配送拠点および出発拠点と配送開始の時を基準とする時刻とを組にした点情報と、点情報のうち配送に係る２つの点情報の間の、配送に係る配送物および配送主体および配送手段の流量を示す枝情報を計算し、配送期限内に需要数量を満たす配送物を当該需要数量が設定された配送拠点に配送する場合の枝情報の集合を少なくとも１つ生成する。出発拠点と配送拠点を総称して拠点と呼ぶ。
入出力部１３は、ユーザによる入力操作を受け付ける。また、入出力部１３は、配送計画生成部１２が生成した枝情報の集合に基づく配送計画の情報などをディスプレイ等に出力する。
第一エリア分割部１４は、配送物の需要がある配送拠点群に含まれる一つの需要点と、配送物の供給元となる配送拠点群に含まれる一つの供給点とを、当該一つの需要点から当該一つの供給点への移動時間が最小となるように対応付け、対応付けた需要点および供給点の組み合わせの集合を生成する。つまり、第一エリア分割部１４は、初期条件に基づく配送物の需要がある全ての配送拠点群への配送問題の全体を、生成した集合が示す配送エリア単位の配送問題（集合内に含まれる需要点群から供給点群への配送問題）に分割する。そして、配送計画生成部１２は、分割後の規模の小さな配送問題のそれぞれについて、枝情報の集合を生成する。
記憶部１５は、配送計画の生成に必要な諸々の情報を記憶する。
初期条件設定部１１、配送計画生成部１２、第一エリア分割部１４は、例えば配送計画装置１０が備えるＣＰＵ（Central Processing Unit、中央処理装置）が、記憶部１５からプログラムを読み出して実行することで実現される。
【００２９】
配送計画装置１０は、与えられた配送問題に対して、時空間ネットワークモデルを用いて配送計画を生成する。まず、時空間ネットワークモデルと時空間ネットワークモデルを用いた配送計画の生成方法について説明し、その後、問題が大規模になった場合の配送問題の分割方法について説明する。
【００３０】
図２は、本発明の第一実施形態における配送計画の一例を説明する図である。
図２を用いて、乗り捨て型のカーシェアリングにおける配送物（車両）の配送例について説明する。図２においてセンターとは、配送物の配送スタッフが存在し、配送物の配送を開始する拠点である（出発拠点）。また、駐車場Ａ、駐車場Ｂ、駐車場Ｃは配送物の配送元または配送先となる拠点（配送拠点）である。配送物のユーザは、所定の予約システムなどで配送物の予約を行う。ユーザは、配送物の利用台数、利用開始場所（例えば、駐車場Ｂ）などの情報を予約システムから入力する。ユーザが駐車場Ｂから配送物を利用したい場合、既に駐車場Ｂに配送物が存在すれば、利用者はその配送物を利用することができる。しかし、駐車場Ｂに配送物が存在しない場合、配送スタッフが他の駐車場から駐車場Ｂに配送物を移動する必要がある。乗り捨て型のカーシェアリングにおいては、ユーザは、例えば、駐車場Ｂから駐車場Ａへ配送物を利用すると、駐車場Ａへ配送物をそのまま乗り捨ててしまう。すると、多くのユーザが利用する、例えば、駐車場Ａに配送物が遍在するような状況が生じ得る。センターの配送スタッフは、遍在した配送物をユーザのニーズがある駐車場Ａ〜駐車場Ｃに配送する。図２の例の場合、駐車場Ａでは配送物が２台余り、駐車場Ｂ、駐車場Ｃでは配送物が１台ずつ不足している。センターの配送スタッフは、駐車場Ａで余った２台の配送物を、それぞれ駐車場Ｂ、駐車場Ｃに１台ずつ配送し、ユーザが希望通り配送物を利用できるようにする。図２は、この条件を満たす配送の実現例を示している。
【００３１】
まず、センターから配送スタッフ２名（ｋ、ｌ）が１台の配送車１（配送手段）に搭乗して駐車場Ａへ移動する（１）。駐車場Ａでは、配送スタッフｋが余っている２台のうち１台の配送物に搭乗して駐車場Ｂへ移動する。また、他の配送スタッフｌも、そのまま配送車１に搭乗して駐車場Ｂへ移動する（２）。駐車場Ｂでは、配送スタッフｋが配送物を駐車場Ｂに駐車し、配送スタッフｌの運転する配送車１に搭乗する。配送スタッフｋ、ｌは駐車場Ｂから駐車場Ａへ戻る（３）。駐車場Ａへ戻ると、配送スタッフｋは、余っている１台の配送物に搭乗して駐車場Ｃへ移動する。また、配送スタッフｌは、そのまま配送車１に搭乗して駐車場Ｃへ移動する（４）。駐車場Ｃでは、配送スタッフｋが配送物を駐車場Ｃに駐車し、配送スタッフｌの運転する配送車１に搭乗する。配送スタッフｋ、ｌは駐車場Ｂからセンターへ戻る（５）。このような手順で配送を行うと、ユーザの要求を満たすことができる。本実施形態では、このような状況における配送物の配送方法を、時空間ネットワークモデルの最小コストフロー問題として定式化して、実行可能な配送方法のうちコストが最小になる方法を求める。
【００３２】
＜第１の時空間ネットワークモデル＞
図３は、本発明の第一実施形態における配送計画に係る第１の時空間ネットワークモデルを説明する図である。
図３は、図２で説明した配送の実施例を時空間ネットワークにモデル化した図である。図３の縦軸は時間経過、横軸は各拠点の場所を示している。図中、時空間上の点は、各時刻における各拠点を表したものである。図中、２つの点を結んだ矢印は、配送物、配送車（配送手段）、配送スタッフ（人）の時空間上の移動を示している。各矢印は、移動元拠点と移動先拠点、移動に要する時間を表している。実線矢印は拠点間の移動を表し、二重線矢印は同一拠点に留まる配送物、配送車、配送スタッフを示している（時間を移動）。また、各矢印に添えて表示された行列の各要素は、矢印が示す配送によって移動した配送物、配送車、配送スタッフの数量を表しており、上から順に移動した配送物の数量、移動した配送車の数量、移動した配送スタッフの人数を表す。例えば、実線矢印３１の場合、センターから駐車場Ａへ、配送物が０台、配送車が１台、配送スタッフが２名、時刻ｔ＝０からｔ＝１の間に移動したことを示している。また、二重線矢印３２は、駐車場Ａにおいて、配送物が２台、配送車が０台、配送スタッフが０名、時刻ｔ＝０からｔ＝１の間留まっていたことを示している。また、実線矢印３３の場合、駐車場Ａから駐車場Ｂへ、配送物が１台、配送車が１台、配送スタッフが２名、時刻ｔ＝１からｔ＝２の間に移動したことを示している。また、二重線矢印３４は、駐車場Ａにおいて、配送物が１台、配送車が０台、配送スタッフが０名、時刻ｔ＝１からｔ＝２の間留まっていたことを示している。駐車場Ａにおける配送物が２台から１台に変化したのは、配送スタッフが、２台のうちの配送物１台に搭乗して、駐車場Ｂへ移動したためである。他の矢印についても同様である。なお、一本の矢印を枝と呼ぶ。図３の枝の集合は、図２で説明した配送計画に対応したものである。配送物を配送する場合、どこかの駐車場で配送スタッフや配達手段を待ち合わせるなど時間が関係したアクションが伴う場合がある。配送計画に関する既存の数理モデルでは、拠点を点とし、拠点間の配送車の移動を枝としてモデル化することが多かった。本実施形態では、２次元の時空間ネットワークでモデル化する。これにより、拠点間の空間的な移動だけでなく、時間が介在する車両や人の移動を表すことができる。
【００３３】
＜第１の時空間ネットワークモデルに基づく配送計画の生成方法＞
本実施形態では、図２、図３で説明したような制限時間内に需要を満たすような配送計画配送物において配送に掛かるコストを最小化する配送計画を求める。この問題は、以下に示す整数計画問題として定式化することができる。
［目的関数］
配送に掛かる配送物、配送手段、配送スタッフのコストの合計を最小化
［制約条件］
（１）各拠点の流量は流量保存則を満たす。
（２）駐車場に存在する車両台数は駐車場の駐車スペースは超えない。
（３）配送手段には、出発拠点以外では必ず配送スタッフが乗る。
（４）移動時には配送物または配送手段に必ず配送スタッフが乗り、また、移動時の人数は配送物および配送手段に搭乗可能な人数の合計以下である。
【００３４】
上記の整数計画問題を解くために、配送計画生成部１２は、初期条件設定部１１が受け付けた初期条件の情報に基づいて、図３で例示したような２次元の時空間情報を生成し、配送に係る点の間の枝を生成し、配送期限内に各拠点の需要数量を満たすように、配送物を当該需要数量が設定された拠点に配送できるような枝情報の集合を複数生成する。そして、配送計画生成部１２は、複数の枝情報の集合の中からコストを最小にする枝情報の集合を選択する。
【００３５】
これまでに提供されてきた配送計画の数理モデルやプログラムは、配送物をトラックや鉄道などの輸送手段に積荷して配送する場合に限られている。車両の配送のように、搭乗輸送を含む場合に対しては、既存技術でも制約条件を追加することで解ける可能性があるが、制約条件が複雑になる上に、手段や経路の組合せ数が指数関数的に増大するために実用的ではないと考えられる。本実施形態によれば、搭乗輸送が可能な配送物の配送計画を生成するにあたり、時空間ネットワークモデルの最小コストフロー問題として定式化することで、実行可能な配送方法のうちコストが最小になる配送計画を求めることができる。
【００３６】
＜第２の時空間ネットワークモデル＞
第２の時空間ネットワークモデルでは、第１の時空間ネットワークモデルに対して、さらに配送拠点内のグラフ（点情報と配送スタッフ、配送物、配送手段の移動を表す枝情報）を追加する。これにより、配送拠点内を０−１整数計画問題として扱えるようにする。０−１整数計画問題は、整数計画問題より変数の幅が制限され、タイトな緩和問題を構成することができる。また、それにより、妥当不等式（カット）を入れやすくなり、計算処理の高速化（計算時間の短縮化）が図れる。
【００３７】
配送計画生成部１２が第２の時空間ネットワークモデルを用いて配送計画を生成する場合、第１の時空間ネットワークモデルの場合に説明した時空間情報に加え、一つの配送拠点について、その配送拠点の入口と時刻とを組にした点情報、その配送拠点の出口と時刻とを組にした点情報、その配送拠点に係る配送物１個ずつに対して時刻を組にした点情報を生成する。また、配送計画生成部１２は、入口に係る点情報と配送物に係る点情報との間における配送スタッフおよび配送物の流量の値を０または１に設定する。また、配送計画生成部１２は、出口に係る点情報と配送物に係る点情報との間における配送スタッフおよび配送物の流量の値を０または１に設定する。
【００３８】
ここで、配送計画立案者が、配送計画装置１０へ入力するパラメータについて説明する。入力パラメータには以下の項目がある。
つまり、出発拠点の集合（Ｄｅｐｏｔ）、配送拠点の集合（Ｗ）、配送期限（ｄｌ）、１区間の時間（ｈ）、配送物の種類の集合（Ｐ）、配送手段の種類の集合（Ｄ）、配送手段の積載量（ｃｐ）、配送物のコストｃｘ（円／分）、配送手段のコストｃｙ（円／分）、配送スタッフのコストｃｚ（円／分）、移動時間マトリクスＭ（例えば、配送手段ｄによる配送拠点ｗ１からｗ２への移動時間はｍ［ｄ］［ｗ１］［ｗ２］とする）、各拠点の供給数量ｓｕｐｐｌｙ（例えば、配送拠点ｗにおけるｄの供給数量はｓｕｐｐｌｙ［ｗ、ｄ］とする）、各配送拠点の需要数量ｄｅｍａｎｄ（例えば、配送拠点ｗにおけるｄの需要数量はｄｅｍａｎｄ［ｗ、ｄ］とする）である。初期条件設定部１１は、これらのパラメータを取得し、配送計画の初期条件として設定する。
【００３９】
また、出力項目として、配送計画生成部１２は、最適化された配送計画における時空間ネットワークを流れる配送物の流量ｘ（（ｖ，ｓ），（ｗ，ｔ））、配送手段の流量ｙ（（ｖ，ｓ），（ｗ，ｔ））、配送スタッフの流量ｚ（（ｖ，ｓ），（ｗ，ｔ））を入出力部１３へ出力する。なお、配送拠点ｖを時刻ｓに出発し、配送拠点ｗへ時刻ｔに到着する枝を（（ｖ，ｓ），（ｗ，ｔ））で表すものとする。なお、出力項目には、他に配送に掛かるコストなどがある。
【００４０】
図４は、本発明の第一実施形態における配送計画に係る第２の時空間ネットワークモデルを説明する第一の図である。
図４を用いて第２の時空間ネットワークを説明する。以下、場所集合をＮ、時間集合をＴ、時空間ネットワークのグラフＧ＝（Ｖ、Ｅ）とする。Ｖは点集合、Ｅは枝集合である。点集合Ｖは以下のように定義する。
Ｖ  ＝  ｛（ｗ，ｄ，ｐ，ｔ）｜ｗ∈Ｗ，ｄ∈｛０｝∪Ｐ，ｐ∈Ｓｗｄ，ｔ∈Ｔ｝
ここで、Ｓｗｄ＝｛０，１｝（ｄ＝０），Ｓｗｄ＝｛０，１，．．．，ｍ｝（ｄ≠０）である。ｄ＝０は、配送拠点の出入り口の道を示している。ｄ＝０のとき、Ｓｗｄは０又は１の値を取るが、Ｓｗｄ＝０は入口、Ｓｗｄ＝１は出口を示している。また、ｄ≠０の場合、ｄは配送物の種類を示し、Ｓｗｄは０〜ｍの値を取る。ｍは配送拠点ｗの配送物ｄに対する供給数量−１または需要数量−１である。例えば、配送拠点ｗで配送物ａが３個余っている場合（供給数量＝３）、Ｓｗｄは０、１、２の値を取る。また、例えば、配送拠点ｗで配送物ａが４個足りない場合（需要数量＝４）、Ｓｗｄは０、１、２、３の値を取る。なお、ある配送拠点ｗについて、ｄ＝０の点を道、ｄ≠０の点をポートとも呼ぶ。ポートは、配送物ｄを１個置く場所を示している。
【００４１】
図４は、Ｄｅｐｏｔ＝｛０｝、Ｗ＝｛１，２｝、Ｐ＝｛ａ｝、Ｔ＝｛０，１，２｝、Ｓ１ａ＝｛０｝（配送拠点１で配送物ａに対する供給数量１個）、Ｓ２ａ＝｛０｝（配送拠点２で配送物ａに対する需要数量１個）の場合の時空間ネットワークである。次に枝集合Ｅについて図５を用いて説明する。
【００４２】
図５は、本発明の第一実施形態における配送計画に係る第２の時空間ネットワークモデルを説明する第二の図である。
以下、枝集合Ｅを、Ｅ＝Ｅｘ∪Ｅｙ∪Ｅｚとする。Ｅｘは配送物の枝集合、Ｅｙは配送手段の枝集合、Ｅｚは配送スタッフの枝集合である。
配送物の枝集合Ｅｘは以下のように定義する。
Ｅｘ＝Ｅｗｗｘ∪Ｅｗｘ∪Ｅｗｐｘ∪Ｅｐｗｘ∪Ｅｐｘ
Ｅｗｗｘは配送物の拠点間の移動を示す枝の集合、Ｅｗｘは配送物の配送拠点の道に留まる枝（待ち合わせなど）の集合、Ｅｗｐｘは配送物の道からポートへの移動を示す枝の集合、Ｅｐｗｘは配送物のポートから道への移動を示す枝の集合、Ｅｐｘは配送物がポートに留まる枝の集合である。
【００４３】
配送手段の枝集合Ｅｙは以下のように定義する。
Ｅｙ＝Ｅｗｗｙ∪Ｅｗｙ∪Ｅｗｐｙ∪Ｅｐｗｙ
Ｅｗｗｙは配送手段の拠点間の移動を示す枝の集合、Ｅｗｙは配送手段の配送拠点の道に留まる枝（待ち合わせなど）の集合、Ｅｗｐｙは配送手段の道からポートへの移動を示す枝の集合、Ｅｐｗｙは配送手段のポートから道への移動を示す枝の集合である。
【００４４】
配送スタッフの枝集合Ｅｚは以下のように定義する。
Ｅｚ＝Ｅｗｗｚ∪Ｅｗｚ∪Ｅｗｐｚ∪Ｅｐｗｚ
Ｅｗｗｚは配送スタッフの拠点間の移動を示す枝の集合、Ｅｗｚは配送スタッフの配送拠点の道に留まる枝（待ち合わせなど）の集合、Ｅｗｐｚは配送スタッフの道からポートへの移動を示す枝の集合、Ｅｐｗｚは配送スタッフのポートから道への移動を示す枝の集合である。
【００４５】
図５に、上記で定義した枝集合の表示例を示す。斜め方向の実線矢印は、Ｅｗｗｘ、Ｅｗｗｙ、Ｅｗｗｚの各集合に対応する枝を示している。縦方向の二重線矢印は、Ｅｗｘ、Ｅｗｙ、Ｅｗｚの各集合に対応する枝を示している。横方向の二点鎖線矢印は、Ｅｗｐｘ、Ｅｗｐｙ、Ｅｗｐｚの各集合に対応する枝を示している。斜め方向の一点鎖線矢印は、Ｅｐｗｘ、Ｅｐｗｙ、Ｅｐｗｚの各集合に対応する枝を示している。縦方向の破線矢印は、Ｅｐｘの集合に対応する枝を示している。
第２の時空間ネットワークモデルでは配送拠点内を０−１整数問題として扱うが、横方向の二点鎖線矢印、斜め方向の一点鎖線矢印、縦方向の破線矢印の枝が、この０−１整数問題化に関連して、本実施形態で追加された枝である。
【００４６】
図６は、本発明の第一実施形態における配送計画に係る第２の時空間ネットワークモデルを説明する第三の図である。
図６を用いて、各枝に対して設定される流量ベクトルについて説明する。図６（ａ）に示すように各枝ｅには流量ベクトル
【００４７】
【数１】
2018073213.tif 000003
【００４８】
が設定される。この流量ベクトルのうち、ｘ［ｄ、ｅ］（ｄ∈Ｐ，ｅ∈Ｅｘ）は配送物の流量、ｙ［ｄ、ｅ］（ｄ∈Ｄ，ｅ∈Ｅｙ）は配送手段の流量、ｚ［ｅ］（ｅ∈Ｅｚ）は配送スタッフの流量を示している。いくつか例を挙げる。Ｐ＝｛ａ｝、Ｄ＝｛車｝の場合、流量ベクトルは、
【００４９】
【数２】
2018073213.tif 000004
【００５０】
となる。図６（ｂ）に示す枝ｅは、ａが1個、配送車（車）が1台、配送スタッフ（人）が２人の移動を示す。また、Ｐ＝｛ａ，ｂ｝、Ｄ＝｛車，バイク｝の場合、流量ベクトルは、
【００５１】
【数３】
2018073213.tif 000005
【００５２】
となる。図６（ｃ）に示す枝ｅは、ａが1個、ｂが1個、配送車（車）が1台、バイクが1台、配送スタッフ（人）が２人の移動を示す。
【００５３】
図７は、本発明の第一実施形態における配送計画に係る第２の時空間ネットワークモデルを説明する第四の図である。
図７は、流量ベクトルが以下であって、
【００５４】
【数４】
2018073213.tif 000006
【００５５】
配送物ａを１個、配送拠点１から配送拠点２へ移動させる場合の時空間ネットワークモデルである。まず、配送スタッフ（人）２人と配送車（車）１台がＤｅｐｏｔ出口から配送拠点１へ移動する（実線矢印９１）。配送拠点１では、配送スタッフ１人が配送物ａの置き場（ポート０）へ移動する（２点鎖線矢印９２）。また、配送物ａのポート０では、配送物ａが時刻０〜１まで存在する（破線矢印９３）。続いて配送スタッフ１人と配送物ａ１個が配送拠点１の出口へ移動する（１点鎖線矢印９４）。次に配送物ａが１個、配送車１台、配送スタッフ２人が配送拠点１の出口から配送拠点２の入口へ移動する（実線矢印９５）。次に配送スタッフ１人と配送物ａ１個が配送拠点２のポート０へ移動する（２点鎖線矢印９６）。続いて配送スタッフ１人がポート０から配送拠点２の出口へ移動する（１点鎖線矢印９７）。次に配送スタッフ２人と配送車１台が配送拠点２の出口からＤｅｐｏｔ入口へ移動する（実線矢印９８）。配送拠点２のポート０では配送物ａが時刻２〜３まで存在する（破線矢印１００）。図７に示すように本実施形態では、配送拠点１および配送拠点２において、配送物ａ１個ごとに点を割り当て、また配送拠点の入口、出口それぞれに点を割り当てている。そのため、配送拠点１内および配送拠点２内における流量ベクトルの各要素の値は０か１となる。これにより、配送拠点内を０−１整数計画問題として扱えるようになり、計算時間を短縮化できる。
【００５６】
図８は、本発明の第一実施形態における配送計画に係る第２の時空間ネットワークモデルを説明する第五の図である。
図８は、図３で例示した第１の時空間ネットワークモデルを第２の時空間ネットワークモデルを用いて表したものである。図８では、図３では駐車場Ａの列で表した点集合を、さらに細分化した（１，０，０，０）、（１，ａ，０，０）、（１，ａ，１，０）の各列の点集合で表している。駐車場Ｂ、駐車場Ｃについても同様である。また、センター、駐車場Ａ〜駐車場Ｃのそれぞれには出入口に対応する点集合が与えられている。
【００５７】
＜第２の時空間ネットワークモデルに基づく配送計画の生成方法＞
以上、第２の時空間ネットワークモデルにおける処理の高速化に対する対策として、配送拠点内を０−１整数計画問題とすることについて説明した。次に配送計画の生成方法について説明する。なお、配送手段として、配送車と自転車で配送する場合（配送車だけで配送する場合も含む）、トラックで（配送物を積載して）配送する場合のそれぞれについて説明を行う。なお、配送手段の自転車は、配送スタッフが自転車に乗って供給のある配送拠点へ移動し、そこで余剰の車両に自転車を積んで、配送スタッフが余剰車両を運転して需要のある配送拠点へ移動するといった用いられ方をする。
【００５８】
まず、目的関数について説明する。図３では、コストを最小化する場合を例に説明を行った。ここでは、配送に掛かる移動時間を最小化する場合も含めて説明する。
（配送車と自転車で配送する場合）
１．配送に掛かるコストを最小化する場合の目的関数は、配送物、配送車、配送スタッフそれぞれの時間当たりのコストに移動時間を掛けて足したものとする。
２．配送に掛かる移動時間を最小化する場合の目的関数は配送物、配送車、配送スタッフそれぞれの移動時間を足したものとする。
【００５９】
（トラックで配送する場合）
１．配送に掛かるコストを最小化する場合の目的関数は、配送トラック、配送スタッフそれぞれの時間当たりのコストに移動時間を掛けて足したものとする。
２．配送に掛かる移動時間を最小化する場合の目的関数は、配送トラック、配送スタッフそれぞれの移動時間を足したものとする。
【００６０】
次に制約条件について説明する。
（配送車と自転車で配送する場合とトラックで配送する場合に共通）
１．流量保存則
（１）配送物の流量について
配送開始時点においては、供給が存在するポートから出る流量は１となる。配送完了時点においては、需要が存在するポートに入る流量が１となる。その他の点では、出ていく流量と入る流量は等しい。
【００６１】
（２）配送車の流量について
配送開始時点においては、配送車が存在する道から出る流量は、配送車の存在台数分となる。配送完了時点においては、配送車が存在する道に入る流量は、配送車の存在台数分となる。その他の点では、出ていく流量と入る流量は等しい。
（３）配送スタッフの流量について
配送開始時点においては、配送スタッフが存在する道から出る流量は、配送スタッフの人数分となる。配送完了時点においては、配送スタッフが存在する道に入る流量は、配送スタッフの人数分となる。その他の点では、出ていく流量と入る流量は等しい。
２．容量制約
配送拠点内の配送物、人の移動量は１以下である。
【００６２】
３．配送拠点内の制約１
∀ｅ∈Ｅｗｐ 
（Ｅｗｐは配送物、配送手段、人の道からポートへの移動を示す枝の集合）
（１）ｅの行き先がｄの供給点のとき
配送物は道からポートには入ってこない。
（２）ｅの行き先がｄの需要点のとき
配送物と配送スタッフの流量が同じ値を取る（０または１）。
（３）どちらの場合も
自転車の台数は配送スタッフの人数以下である。
【００６３】
４．配送拠点内の制約２
∀ｅ∈Ｅｐｗ 
（Ｅｐｗは配送物、配送手段、人のポートから道への移動を示す枝の集合）
（１）ｅの出発点がｄの供給点のとき
配送物と配送スタッフの流量が同じ値を取る（０または１）。
（２）ｅの出発点がｄの需要点のとき
配送物はポートから道には出ない。
（３）どちらの場合も
自転車の台数は配送スタッフの人数以下である。
【００６４】
以下、配送車と自転車で配送する場合とトラックで配送する場合に分けて説明する。
（配送車と自転車で配送する場合）
５．拠点から別の拠点へ移動するときの枝に対する制約
∀ｅ∈Ｅｗｗ  
（Ｅｗｗは配送物、配送手段、人の拠点間の移動を示す枝の集合）
（１）ｅが自転車の枝かつ車の枝のとき
自転車と車のそれぞれに配送スタッフが乗って移動している場合と、自転車を車に積載して移動している場合があり、車には必ず配送スタッフが乗ること、配送スタッフの人数は搭乗可能人数以下であること、運転できない自転車の台数は、車に積載可能な台数以下であることを制約とする。
（２）ｅが自転車の枝であるが車の枝ではないとき（自転車で移動している）
自転車の台数と人数が一致する。
【００６５】
６．配送拠点の中で留まる枝に対する制約
車には必ず人が乗ることを制約とする。
【００６６】
（トラックで配送する場合）
５．配送拠点から別の配送拠点へ移動するときの枝に対する制約
トラックには必ず配送スタッフが乗ること、配送スタッフの人数は搭乗可能人数以下であること、配送物の総体積はトラックの積載量以下であることを制約とする。
【００６７】
６．配送拠点の中で留まる枝に対する制約
配送物の総体積はトラックの積載量以下であることを制約とする。
【００６８】
さらに、計算時間を短縮化するためにカットと呼ばれる制約式を適用することができる。整数計画問題において、実行可能領域の点が満たすことができる不等式を妥当不等式と呼ぶ。整数計画問題は、解くのが難しいため、まず整数条件を除いた線形緩和問題として扱うことも多い。線形緩和問題の解空間を削る妥当不等式を追加することをカットの追加と呼ぶ。カットの追加によって、線形緩和解が整数最適解に近づくことから、計算の高速化に強力な効果がある。また、カットの追加によって、実行可能領域は切断されないため、解の最適性は保証される。例えば、配送車は１台以上で来ることを規定するようなカットを加える。すると、配送車が３／４台で来るという現実的ではない場合を計算対象から除外することができ、計算速度を向上することができる。なお、カットの具体例については、本願の出願人による特願２０１６−０５１５５０の明細書に記載されている。カットを追加した場合、カットを追加しない場合で数時間以上を要した整数計画問題について、数分で解くことが可能となった。
【００６９】
配送計画生成部１２は、配送拠点の中を、道（ｄ＝０）と駐車ポート（ｄ≠０）で分割した時空間ネットワークモデルを生成し、さらに上記制約条件、追加されたカットを用いて枝情報を計算する。本実施形態によれば、配送拠点内を０−１整数計画問題としてモデル化することができるので、第１の時空間ネットワークを用いて配送計画を生成する場合の効果に加え、配送計画の計算に要する時間が削減できるという効果が得られる。さらに、カットの追加により計算時間を大幅に短縮することができる。これにより、例えば、様々な初期条件下で生成された配送計画を比較し、より低コストな配送計画の選択を行うことができるようになるなど、計画立案者の利便性が向上する。
【００７０】
次に第２の時空間ネットワークを用いて配送計画を生成する事例について説明する。
図９は、本発明の第一実施形態における配送問題の一例を示す図である。
図１０は、配送問題に対して生成した配送計画の一例を示す図である。
図９の点ｃ０（ｄｅｐｏｔ）は出発拠点である。他の点ｗ１〜ｗ９は配送拠点である。例えば、点ｗ７において「ｄ１：２」とあるのは、配送物ｄ１が２個余っている状態を示し、点ｗ５において「ｄ２：−１」とあるのは、配送物ｄ２が１個不足している状態を示している。また、点ｗ２で「ｄ１：−１、ｄ２：１」とあるのは、配送物ｄ１が１個不足し配送物ｄ２が１個余っている状態を示している。図９が示す配送物ｄ１〜ｄ３が遍在した状態から、各配送拠点で配送物ｄ１〜ｄ３が不足した状態が無くなるように配送物ｄ１〜ｄ３を配送する問題を考える。以下に車と自転車で配送する場合、トラックで配送する場合のそれぞれについて、配送計画装置１０が生成した配送計画の例を挙げる。
【００７１】
１．車と自転車で配送する場合
（１）入力
・ｄｅｐｏｔには、配送車１台、自転車３台、配送スタッフ３人
・配送期限：１２０分
・配送車のコスト：１．５円／分
・配送スタッフのコスト：１７円／分
・ｄ１、ｄ２、ｄ３のコスト：１．５円／分
・配送車の搭乗可能人数：４人、自転車の積載可能台数：１台
・ｄ１の搭乗可能人数：１人、自転車の積載可能台数：０台
・ｄ２の搭乗可能人数：４人、自転車の積載可能台数：１台
・ｄ３の搭乗可能人数：２人、自転車の積載可能台数：０台
（２）目的関数
コスト最小化
【００７２】
この目的関数に対して上述の制約条件、カットを加えて、配送計画装置１０に計算させると次のような出力結果が得られた。
（３）出力
・配送車１台、自転車１台、配送スタッフ２人で図１０に示すようにＳ１〜Ｓ７で示される配送ルートとＴ１〜Ｔ９で示される配送ルートの２ルートに分かれて配送する。
・配送コスト：２７６８円
・必要な時間：６０分
このように、初期条件で設定した配送手段、配送スタッフ、配送期限の条件内でコストを最小化する配送計画を得ることができる。
【００７３】
なお、配送計画装置１０による第１の時空間ネットワーク又は第２の時空間ネットワークを用いた配送計画の生成は、搭乗輸送が可能な配送物の配送、調達、アフターサービス巡回にも適用可能である。例えば、アフターサービスにおいては、アフターサービスに必要な部品等を調達してから客先に向かったり、複数の客先を回ったりしてサービスを提供する必要がある。配送物をアフターサービスに使う部品等、配送主体をサービスマン、配送手段をサービスマンが移動に用いる車両や部品等の運搬に必要な配送車等、拠点を客先やアフターサービスの対象となる製品の設置場所として、上記の数理モデルを適用して整数計画問題を解くことができ、サービスマンが複数の客先でアフターサービスを行う場合に、その巡回コストや巡回時間を最小にする巡回方法（巡回手段、巡回経路）を算出することができる。図２の場合、例えば、駐車場Ａ〜駐車場Ｃ（配送拠点）を、アフターサービスを提供する客先、車両（配送物）を部品、乗用車（配送手段）をサービスマンが移動に用いる手段、配送者（配送主体）をサービスマンとすればよい。また、アフターサービスの場合、単に客先を巡回するだけでなく、客先で点検、修理などの作業を行う。時空間ネットワークモデルを用いた配送計画装置１０、１０Ａ、１０Ｂによれば、サービスマンの巡回行動を、これら作業時間を考慮に入れてモデル化することができる。
【００７４】
また、上記の例以外にも搭乗輸送を行わない配送物の配送に対しても適用することができる。例えば、ミルクランと呼ばれる集荷方法が存在する。ミルクランとは、ある製品のメーカが、その製品に使用する原材料や部品を、複数のサプライヤから仕入れる場合、各サプライヤに搬入させるのではなく、メーカが、各サプライヤを巡回して原材料等を集荷する調達方法のことである。ミルクランによって集荷を行うと、例えば、１台のトラックで集荷することで、各サプライヤに納入させる場合と比べてコスト削減、工場周辺の渋滞軽減、環境の負荷軽減を図ることができる。本実施形態の配送計画装置１０によってミルクランの最適な巡回方法を算出する場合、例えば、製品メーカの納入先の工場等をカーシェアリングにおける需要のある配送拠点とし、原材料や部品の納入業者の工場等を車両が余っている配送拠点とすれば、上述した「トラックで配送する場合」と同様の目的関数、制約条件等を設定することで、配送計画を算出することができる。なお、上記のトラックで配送する場合の「配送物の総体積はトラックの積載量以下であること」との制約条件については、「（原材料の重み×原材料の量＋部品の重み×部品数）はトラックの積載量以下であること」との制約条件に変更する。また、あるサプライヤの集荷時間枠が指定されている場合、制約条件にその指定された集荷時間枠の情報を加えることで対応することができる。例えば、あるサプライヤへの到着時刻を（集荷の開始から）３０分後以降にしなければならない場合、次のような制約条件を追加すれば、当該サプライヤの時間枠制約を守った集荷計画を生成することができる。
あるサプライヤへの到着時刻  ≧  ３０分後    
【００７５】
これまでに本実施形態の配送計画装置１０が、配送計画を生成する処理について説明した。上述した方法によれば、配送計画装置１０は、配送問題における厳密な最適解を求めることができる。しかしながら、上記の方法だけでは、問題の規模が大きくなると（例えば、配送拠点が２０カ所で、配送する車両が２０台）、実用的な時間で解を求めることが難しい場合がある。そこで、第一エリア分割部１４は、配送拠点を配送エリアごとに分割して、与えられた配送問題を分割したエリアごとの配送問題に分割する。次に第一エリア分割部１４によるエリア分割処理（第一エリア分割処理）について説明する。
【００７６】
図１１は、本発明の第一実施形態における第一エリア分割処理を説明する第一の図である。
図１１の左図は、配送計画の対象となる地域に存在する配送拠点と出発拠点の位置を示している。図中、丸点は配送拠点（ｗ１〜ｗ１７）、四角点は出発拠点（ｃ１〜ｃ３）を示している。配送拠点ｗ１〜ｗ１７には、配送物の需要または余剰があり、出発拠点ｃ１〜ｃ３には配送車や配送スタッフが存在している。第一エリア分割部１４は、近隣に存在する需要のある配送拠点（需要点）と余剰がある配送拠点（供給点）とを対応させた組を生成し、さらに需要点と供給点の組を１つ又は複数集めて分割された一つのエリアを生成する。第一エリア分割部１４によるエリアの生成を第一エリア分割処理と呼ぶ。
【００７７】
図１１の右図は、第一エリア分割部１４が第一エリア分割処理を行った結果を示している。配送拠点ｗ１〜ｗ５はエリアｊ１、配送拠点ｗ６〜ｗ９はエリアｊ２、配送拠点ｗ１０〜ｗ１７はエリアｊ３にそれぞれ属している。配送計画生成部１２は、分割後のエリアｊ１〜エリアｊ３それぞれについて上記の方法で配送計画の生成を行う。エリアｊ１〜エリアｊ３には、それぞれ１０個未満の配送拠点しか含まれず、比較的小規模である。その為、配送計画生成部１２は、上記した時空間ネットワークモデルを用いて実用的な時間で配送計画を生成することができる。
【００７８】
次に図１１を用いて第一エリア分割処理の概要を説明する。まず、第一エリア分割部１４は、配送拠点ｗ１〜ｗ１７を需要点と、供給点と、需要点でも供給点でもない配送拠点とに分ける。次に第一エリア分割部１４は、需要点と供給点とを１対１に対応付ける。このとき、第一エリア分割部１４は、需要点と供給点の距離（移動時間）が近いもの同士を対応付ける。例えば、図１１の配送拠点ｗ４では配送物ｄ１が１余り、配送拠点ｗ５では配送物ｄ１が１足りない。また、配送拠点ｗ６では配送物ｄ１が１余り、配送拠点ｗ７では配送物ｄ１が１足りない。また、配送拠点ｗ８では配送物ｄ２が１余り、配送拠点ｗ９では配送物ｄ２が１足りないとする。この場合、第一エリア分割部１４は、需要と供給が一致し、距離が近い配送拠点同士を対応付ける。すなわち、第一エリア分割部１４は、配送拠点ｗ４と配送拠点ｗ５とを対応付け（組１とする）、配送拠点ｗ６と配送拠点ｗ７とを対応付け（組２とする）、配送拠点ｗ８と配送拠点ｗ９とを対応付ける（組３とする）。その他の需要点と供給点についても同様に対応付けを行う。
【００７９】
次に第一エリア分割部１４は、対応付けた需要点と供給点の組について、距離の近い組同士を複数集めて１つのエリアを生成する。このとき、距離の近い組が他に無ければ１つの組を１つのエリアとしてもよい。例えば、上に挙げた例の場合、第一エリア分割部１４は、組１の配送拠点ｗ４と組２の配送拠点ｗ６との距離を計算する。そして、計算した距離が所定の閾値より小さければ、組１と組２とを同じエリアに分類し、計算した距離が所定の閾値より大きければ、組１と組２とは別のエリアとして判定する。組の間の距離の計算については、例えば、組１と組２の距離の場合、配送拠点ｗ４と配送拠点ｗ７の距離を計算してもよいし、配送拠点ｗ４〜配送拠点ｗ６間、配送拠点ｗ４〜配送拠点ｗ７間、配送拠点ｗ５〜配送拠点ｗ６間、配送拠点ｗ５〜配送拠点ｗ７間の距離をそれぞれ計算し、計算した距離の平均を組１と組２との距離としてもよい。あるいは、計算した距離のうち最も大きい（又は最も小さい）距離を組１と組２との距離としてもよい。図１１の例の場合、第一エリア分割部１４は、例えば、組２と組３を同じエリアｊ２に分類し、組１をそれとは別のエリアｊ１に分類する。第一エリア分割部１４は、他の配送拠点についても同様の処理を行い、配送拠点ｗ１〜ｗ１７をエリアごとに分類し、図１１に示すエリアｊ１〜エリアｊ３を生成する。
【００８０】
第一エリア分割処理によってエリアが生成されると、配送計画生成部１２は、エリアｊ１〜エリアｊ３のそれぞれについて、各エリア内の各配送拠点における配送物の供給数量、需要数量などを初期条件とする配送問題に対して、第１の時空間ネットワークモデル又は第２の時空間ネットワークモデルを用いて配送計画の生成を行ってもよいが、全く初期の状態から時空間ネットワークモデルを用いた計算を行わなくても、第一エリア分割処理の際の需要点と供給点の対応付けを枝情報として利用することができる。すなわち、配送計画生成部１２は、対応付けた需要点から供給点への枝情報を生成し、それらを繋ぎ合わせることで全ての需要を満たす配送計画が生成できる。しかし、距離が最も近い配送拠点間を結んだ配送ルートだけでは、余りにも限定され過ぎており、複数の拠点間を移動する配送計画全体から見た場合、最適化された状態から遠ざかってしまう可能性がある。そこで、第一エリア分割部１４は、配送計画生成部１２が枝情報の生成を行う際に選択される可能性がある配送ルートを追加する処理を行う。そして、配送計画生成部１２は、需要と供給を満たす最も近い配送拠点間を結ぶ配送ルートに追加された選択される可能性がある配送ルートを加えた全ての候補となる配送ルートの中から適切な配送ルートを選択して枝情報を生成し、エリアごとの配送計画を生成する。
なお、図１１では、需要点、供給点を配送拠点として説明したが、それぞれ需要のあるポート、供給のあるポートとしてもよい。
【００８１】
次に第一エリア分割処理について詳しく説明する。
図１２は、本発明の第一実施形態における第一エリア分割処理を説明する第二の図である。
以下に本実施形態の第一エリア分割処理のアルゴリズムを説明する。第一エリア分割部１４は、以下の手順で各処理を行う。
１．まず、各配送拠点の各ポート（第１の時空間ネットワークモデルの場合は配送拠点）を供給点と需要点に分け、供給点の集合Ａ、需要点の集合Ｂを生成する。Ｖ１＝Ａ∪Ｂとする。
２．次にＶ１に新しい点ｓ、ｔを加え、Ｖ＝Ｖ１∪｛ｓ，ｔ｝とする。
３．ＡからＢに配送ルートｅ１１〜ｅ１９を作り、各配送ルートに対してその配送ルートが示す経路で配送した場合の移動時間に基づくコスト関数ｃ（ｅ）を定義する。
４．ｓからＡ、Ｂからｔに配送ルートを作りそれらのコストを０とする。ｓからＡ、Ｂからｔの配送ルートの集合をＥ２とし、Ｅ１とＥ２の和集合をＥとする。
５．ここまでの処理で２部グラフＧ＝（Ｖ，Ｅ）を構成する。
６．Ｇの最小重み最大マッチング、すなわちコストが最小となるｓからｔへの経路を算出する。より具体的には、ｓからｔへの経路のうち、集合Ａに含まれる各供給点から出る配送ルートの数が１、集合Ｂに含まれる各需要点に入る配送ルートの数が１という条件の下で、ｓと集合Ａの各供給点と集合Ｂの各需要点とｔとを結ぶ配送ルートのコストの合計が最小となる場合の配送ルートを算出する（主問題）。４．よりｓから集合Ａの各供給点へのコスト、集合Ｂの各需要点からｔへのコストは０であるから、コストが最小となる場合の供給点ａ１〜供給点ａ３と需要点ｂ１〜需要点ｂ３との対応付け方を求めることができる。ここでコストは移動時間に基づく関数であるから、最も距離が近い供給点と需要点との１対１マッチングを求めることができる。図１２の例では、例えばａ１とｂ１とを結ぶ配送ルートｅ１１、ａ２とｂ３とを結ぶ配送ルートｅ１６、ａ３とｂ２とを結ぶ配送ルートｅ１８の組み合わせがコストの合計が最小となる配送ルートであって、その場合、ａ１とｂ１、ａ２とｂ３、ａ３とｂ２が１対１で対応付けられる。
７．次に対応付けられた２つのポートが同じエリアに含まれるように、全てのポートをエリアで分割する。このとき、対応付けられた２つのポート間の移動時間が所定の値以下であれば１つのエリアに分類する。図１２の例では、例えば、対応付けたａ１とｂ１、ａ２とｂ３、ａ３とｂ２のうち、ａ１とｂ１を１つのエリア（ｊ４）、ａ２とｂ３、ａ３とｂ２を１つのエリア（ｊ５）として分類する。
【００８２】
８．次に１．〜５．の手順で作成した２部グラフを再度作成し、６．の双対問題を生成する（双対問題は数学的な操作で生成することができる）。また、枝ｅ＝（ｕ，ｖ）に対して、主問題の最適解Ｘ＊（ｅ）が１であれば、双対問題の最適解をＹとした場合、ｃ（ｅ）−Ｙ＊（ｕ）−Ｙ＊（ｖ）＝０となる（相補性条件：complementary slackness）ところ、ｃ＾（ｅ）をｃ＾（ｅ）＝ｃ（ｅ）−Ｙ＊（ｕ）−Ｙ＊（ｖ）で定義し、
０  ≦  ｃ＾（ｅ）  ≦  ε（εは所定の定数）
の条件により、ｃ＾（ｅ）に幅を持たせる。この条件は、ｃ＾（ｅ）＝０だけでなく、ｃ＾（ｅ）がε以下となる場合も配送ルートの候補として認めることを意味する。つまり、主問題でもコストが最小になる場合だけでなく、幅を持った解が得られる。この解の条件の緩和により、図１２の例では、例えばａ１とｂ１とを結ぶ配送ルートの候補ｅ１９が新たに得られる。
【００８３】
以上で第一エリア分割処理が完了する。第一エリア分割処理が完了すると、配送計画生成部１２が、分割後の各エリアについて配送計画を生成する。その際、配送計画生成部１２は、第一エリア分割処理で得られた配送ルートの候補を使用して条件を満たす配送計画を生成する。具体的には、上述した「１．流量保存則」〜「６．配送拠点の中で留まる枝に対する制約」に加えて、第一エリア分割処理で得られた配送ルートの候補（ｅ１１，ｅ１６，ｅ１８，ｅ１９）を用いることを制約条件に加えて、枝情報の集合を計算する。
【００８４】
次に本実施形態の配送計画の生成処理の流れについて説明する。
図１３は、本発明の第一実施形態における配送計画の生成処理の一例を示すフローチャートである。
まず、配送計画を行う配送スタッフが、配送計画装置１０に配送計画の初期条件を入力する。入出力部１３はその入力を受け付け、受け付けた情報を初期条件設定部１１に出力する。初期条件設定部１１は、配送スタッフが入力した初期条件の情報を取得する（ステップＳ１１）。初期条件設定部１１は、取得した初期条件の情報を配送計画の初期条件に設定する。初期条件とは、例えば、各拠点における配送物の供給数量（余っている数量）、需要数量（不足している数量）、出発拠点にある配送車の台数、配送スタッフの人数、各拠点間の移動時間、配送期限などである。
次に、第一エリア分割部１４は、初期条件の情報に含まれる各配送拠点（又はポート）での配送物の供給数量、需要数量を用いて、第一エリア分割処理を行う（ステップＳ１２）。第一エリア分割処理については図１１，図１２を用いて説明したとおりである。
【００８５】
次に、配送計画生成部１２は、第一エリア分割処理で得られたエリアごとに、図３や図８で例示した時空間ネットワークモデル上で、上記の各制約条件を満たすように枝情報を生成し、配送期限等の条件を満たす枝情報の集合を複数生成する（ステップＳ１３）。具体的には、配送計画生成部１２は、第一エリア分割処理で得られた配送ルートの候補について、配送物の数量、配送車の台数、配送スタッフの人数の情報を付加し、各制約条件（「１．流量保存則」〜「６．配送拠点の中で留まる枝に対する制約」）を満たす枝情報を生成する。また、配送計画生成部１２は、生成した枝情報を組み合わせて、配送期限までに各拠点の需要台数を満たすような配送を示す枝情報の集合を複数生成する。
【００８６】
次に、配送計画生成部１２は、エリアごとに、生成した枝情報の集合ごとに総コストを計算する（ステップＳ１４）。例えば、配送車、配送スタッフ、配送物ごとに単位時間あたりに発生する単位コストが予め記憶部１５に記録されており、配送計画生成部１２は、配送車、配送スタッフ、配送物の単位コストに各枝が示す時間を乗じて枝ごとのコスト（配送車、配送スタッフ、配送物に掛かるコストの合計）を計算する。配送計画生成部１２は、枝情報の集合に含まれる枝ごとのコストを計算してそれらを合計する。合計したコストが１つの枝情報の集合に対するコストである。配送計画生成部１２は、エリアごとに、全ての枝情報の集合それぞれについてコストを計算する。
【００８７】
次に配送計画生成部１２は、エリアごとに、計算した各集合について計算したコストを比較し、総コストが最小となる枝情報の集合を選択する（ステップＳ１５）。選択した枝情報の集合は、初期条件が示す出発拠点や各配送拠点の状態から、時間の経過に伴う配送物、配送手段、配送スタッフの移動を表している（図３、図８）。従って、枝情報の集合に基づいて配送を実行すれば、ユーザからの需要に応じた配送が可能になる。つまり、この枝情報の集合は、分割後の１つのエリアについての求める配送計画である。配送計画生成部１２がエリアごとの配送計画を生成し終えると、初期条件として与えられた全配送拠点に対する配送計画が生成されたことになる。
【００８８】
本実施形態によれば、初期条件で与えられた配送拠点の全体を、近距離にある配送拠点の集合（エリア）に分割することによって、配送問題の規模を小さくすることができ、各エリアでの配送計画の生成処理の計算量を削減することができる。また、エリア分割を行う際に配送ルートの候補を算出し、それらの候補の中から配送ルートを選択して枝情報を生成するのでさらに計算量を削減することができる。これにより、配送物や配送拠点の数が多く、配送問題が大規模になった場合でも、実用的な時間（例えば１０分）で配送計画を生成することができる。
なお、配送計画生成部１２は、ステップＳ１３において配送ルートの候補を用いることなく枝情報を生成し、配送計画を生成してもよい。
また、エリアの配送計画のコストを加味してエリアを再構成してもよい。例えば、配送コストの差が著しく離れているエリアのペアに対して、早めに配送が完了するエリアを大きくし、遅く配送が完了するエリアを小さくすることで、全体のコストを下げることができる場合がある。
【００８９】
＜第二実施形態＞
次に大規模な配送問題について実用的な時間で配送計画を生成する他の方法（第二実施形態）に係る配送計画システムについて図１４〜図１８を参照して説明する。第一実施形態では、比較的近距離に存在する需要点と供給点に注目し、一対の需要点と供給点とを集めて小規模なエリアを生成した。第二実施形態では、出発拠点を中心にエリア分割処理を行い、分割後の各エリア内で配送計画を生成する。なお、第二実施形態におけるエリア分割処理を第二エリア分割処理と呼ぶ。
【００９０】
図１４は、本発明の第二実施形態における配送計画システムの一例を示す機能ブロック図である。
本発明の第二実施形態に係る構成のうち、本発明の第一実施形態に係る配送計画装置１０を構成する機能部と同じものには同じ符号を付し、それぞれの説明を省略する。第二実施形態に係る配送計画装置１０Ａは、第一実施形態の構成における第一エリア分割部１４に代えて、第二エリア分割部１６を備えている。
第二エリア分割部１６は、出発拠点を出発して一部の配送拠点間に係る配送を行って元の出発拠点に戻るまでの予め設定された配送ルートとその配送ルートで配達したときのコストとを示す単位経路情報を複数取得する。また、第二エリア分割部１６は、複数の単位経路情報の組み合わせの中から、当該組み合わせに含まれる、配送拠点の数が所定の数以内となり、且つ、コストが最小となる組み合わせを選択する。この単位経路情報の組み合わせに含まれる出発拠点および配送拠点の集合が分割後のエリアである。
なお、第二エリア分割部１６は、配送計画装置１０Ａが備えるＣＰＵが、記憶部１５からプログラムを読み出して実行することで実現される。
【００９１】
図１５は、本発明の第二実施形態における配送問題の第二エリア分割処理を説明する第一の図である。
図１５において、丸点は配送拠点ｗ１〜配送拠点ｗ１７、四角点は出発拠点ｃ１〜出発拠点ｃ３を示している。本実施形態では、まず、考えうるすべての需要・供給のパターンを列挙した上で、出発拠点ごとに各パターンの需要・供給を満たす単純な配送ルートを多数作成しておく。ここで、出発拠点ｃ１〜出発拠点ｃ３には、十分な量の配送車（トラック）や配送スタッフが存在しており、配送拠点ｗ１，ｗ３，ｗ６，ｗ８，ｗ１０が供給点、配送拠点ｗ２，ｗ５，ｗ７，ｗ９，ｗ１１が需要点であるとする。また、配送に係る配送物の種類は同じであるとする。この場合、出発拠点ごとの需要・供給を満たす単純な配送ルートとは、例えば、出発拠点ｃ１を出発し配送拠点ｗ１に至り（Ｒ１）、配送拠点ｗ１で配送物を取り、配送拠点ｗ２へその配送物を運び（Ｒ２）、配達が終わったら出発拠点ｃ１に戻る（Ｒ３）配送ルート（配送ルート１とする）である。同様に、出発拠点ｃ１から配送拠点ｗ３、配送拠点ｗ５を経由して出発拠点ｃ１に戻るルート（配送ルート２とする）、出発拠点ｃ１から配送拠点ｗ６、配送拠点ｗ７を経由して出発拠点ｃ１に戻る配送ルート（配送ルート３とする）、出発拠点ｃ２から配送拠点ｗ８、配送拠点ｗ９を経由して出発拠点ｃ２に戻る配送ルート（配送ルート４とする）、出発拠点ｃ３から配送拠点ｗ１０、配送拠点ｗ１１を経由して出発拠点ｃ３に戻る配送ルート（配送ルート５とする）などである。これらの単純なルートは予め多数作成され、記憶部１５に記録されている。図示しないが、例えば以下のようなルートも作成され予め記憶部１５に記録されている。出発拠点ｃ１から配送拠点ｗ１と配送拠点ｗ５を経由して出発拠点ｃ１に戻る配送ルート、出発拠点ｃ１から配送拠点ｗ１と配送拠点ｗ７を経由して出発拠点ｃ１に戻る配送ルート、出発拠点ｃ１から配送拠点ｗ３と配送拠点ｗ２を経由して出発拠点ｃ１に戻る配送ルート、出発拠点ｃ１から配送拠点ｗ１０と配送拠点ｗ１１を経由して出発拠点ｃ１に戻る配送ルート、出発拠点ｃ２から配送拠点ｗ１と配送拠点ｗ２を経由して出発拠点ｃ２に戻る配送ルート、出発拠点ｃ３から配送拠点ｗ１と配送拠点ｗ２を経由して出発拠点ｃ３に戻る配送ルート、などである。
【００９２】
また、単純な配送ルートとは、１つの供給点、１つの需要点を経由して元の出発拠点に戻る配送ルート（２つの配送拠点を巡回して元の出発拠点に戻るルート）のことだけを指すのではなく、出発拠点ｃ１を出発して、配送拠点ｗ１にて配送物を２つ取り、配送拠点ｗ２と配送拠点ｗ４に配送物を一つずつ届け出発拠点ｃ１に戻るという配送ルートであってもよい（配送拠点が３つの例）。あるいは、出発拠点ｃ１を出発して、配送拠点ｗ１にて配送物を１つ取り配送拠点ｗ２に届け、続いて配送拠点ｗ３にて配送物を１つ取り配送拠点ｗ４に届け、出発拠点ｃ１に戻るという配送ルートであってもよい（配送拠点が４つの例）。
【００９３】
図１６は、本発明の第二実施形態における配送問題の第二エリア分割処理を説明する第二の図である。
図１６に図示するように記憶部１５には、予め用意された単純な配送ルートが複数記録されている。また、単純な配送ルートに対応付けて、その配送ルートで配送した場合のコストが記録されている。コストは、例えば移動時間の関数として与えられる。予め記録された単純な配送ルートとコストの情報は、多ければ多い程、より精度の高い（厳密な最適解に近い）配送計画を生成することができる。なお、図１６に例示する単純な配送ルートとその配送ルートに対応するコストを含む情報を単位経路情報とよぶ。
【００９４】
図１７は、本発明の第二実施形態における配送問題の第二エリア分割処理を説明する第三の図である。
次に第二エリア分割部１６による第二エリア分割処理について図１５〜図１７を用いて説明する。
前提として、記憶部１５には図１６で例示した単位経路情報が記録されている。また、配送に関する要求事項（配送拠点ごとの需要数量、供給数量、出発拠点の配送車の台数、配送スタッフの人数など）の初期条件が与えられるとする。
１．まず第二エリア分割部１６は、初期条件で与えられる配送要求（需要）のうち、一部を満たす配送ルートを含む単位経路情報を記憶部１５から読み出す。
２．次に第二エリア分割部１６は、読み出した単位経路情報に含まれる配送ルートを組み合わせて、全ての配送要求を満たすルートを作成し、暫定解とする。ここで、予め記録された単純な配送ルートを組み合わせて、全ての要求を満たし且つコストが最も安くなる組み合わせを求める方法として、集合分割アプローチと呼ばれる数学的手法が用いられるが、この手法の場合、単純な配送ルートの数が膨大になると、その組み合わせの最適化問題は実用的な時間では解くことができない場合がある。その為、第二エリア分割部１６は、記憶部１５が記憶する多数の単純な配送ルートのうち、少数の配送ルートを用いて初期解を生成し、列生成法と呼ばれる数学的手法を用いて、単純な配送ルートを追加しながら最適解を求める。なお、初期解を生成するための少数の単純な配送ルートは、任意の方法で選択してよい。また、初期解の生成には、一般的に提供されているソルバーを用いることができる。このとき、１つの出発拠点が担当する配送拠点の数に制約（例えば、需要点と供給点を含め６拠点以内など）を設ける。ここで、配送拠点の数に制約（上限）を設けるのは、計算量を削減し、処理を高速化するためである。制約する配送拠点の数については、例えば、実際に計算を行い、実用的な時間内に解が求められる場合の配送拠点の数を上限として定めてもよい。初期解として、例えば、図１５に示す解（配送ルート１〜配送ルート５）が得られる。
【００９５】
３．次に第二エリア分割部１６は、列生成法（公知の数学的手法）によって未選択の単純な配送ルートの中から１つ又は複数の配送ルートを選択し、既に選択されたある単純な配送ルートと選択した単純な配送ルートを入れ替えた場合の減少コストを計算する。減少コストとは、入れ替えにより新たに解として選択された単純な配送ルートに対応付けられて記録されたコスト（図１６のコスト欄）の合計から、入れ替え前に選択されていた元々の単純な配送ルートに対応付けられて記録されたコストの合計を引いた値である。
【００９６】
４．第二エリア分割部１６は、３．で計算した減少コストが負の値（入れ替え後の方が安い）ならば、３．で選択した単純な配送ルートで既存の全配送ルートの一部を更新する。例えば、配送拠点ｗ７への配送に関して、図１５に示す初期解では、配送ルート３が選択されているが、第二エリア分割部１６は、この配送ルート３に代えて、出発拠点ｃ２から配送拠点ｗ６、配送拠点ｗ７を経由して出発拠点ｃ２へ戻るルート（配送ルート６とする）に入れ替えた場合の減少コストを計算する。図１６により配送ルート３のコストは２５００、配送ルート６のコストは１５００であるから、減少コストは、−１０００である。従って、第二エリア分割部１６は、配送ルート３を配送ルート６で更新する。更新後の単純な配送ルートの組み合わせを図１７に示す。なお、減少コストを計算する場合も、第二エリア分割部１６は、１つの出発拠点が担当する拠点の数が制約内となるように配送ルートを選択する。
【００９７】
また、この例では、単純な配送ルートを出発拠点ｃ１の担当範囲から出発拠点ｃ３の担当範囲へ移す例を挙げたが、配送ルートの更新は、この例に限定されない。例えば、図１５の状態で、出発拠点ｃ１が担当するルート内の配送ルート１と配送ルート２の組み合わせを、出発拠点ｃ１から配送拠点ｗ３、配送拠点ｗ２を経由して出発拠点ｃ１へ戻るルートと出発拠点ｃ１から配送拠点ｗ１、配送拠点ｗ５を経由して出発拠点ｃ１へ戻るルートの組み合わせに更新する方法でもよい。あるいは、配送拠点ｗ１に対象とする配送物が２つあるとして、配送ルート１と配送ルート２の組み合わせを、出発拠点ｃ１から配送拠点ｗ１、配送拠点ｗ２、配送拠点ｗ３、配送拠点ｗ５を経由して出発拠点ｃ１へ戻る配送ルートに更新する方法でもよい。
【００９８】
５．第二エリア分割部１６は、３．〜４．の処理を繰り返し、コストを減少できるルートが無くなった時点で第二エリア分割処理を終了する。第二エリア分割処理が終了すると、出発拠点ごとに制約条件（例えば６拠点）以内の配送拠点が関連付けられることになる。この関連付けられた複数の配送拠点と出発拠点の集合（例えば、エリアｊ６〜エリアｊ８のそれぞれ）が、第二エリア分割処理によって得られるエリアである。
【００９９】
次に本実施形態の配送計画の生成処理の流れについて説明する。
図１８は、本発明の第二実施形態における配送計画の生成処理の一例を示すフローチャートである。図１３と同様の処理については簡単に説明を行う。
まず、初期条件設定部１１は、配送スタッフなどが入力した初期条件の情報を取得する（ステップＳ１１）。
次に、第二エリア分割部１６は、初期条件の情報に含まれる各拠点での配送物の供給数量、需要数量、出発拠点での配送スタッフ数、配送車の種類及び数を用いて、第二エリア分割処理を行う（ステップＳ１２１）。第二エリア分割処理については図１５〜図１７を用いて説明したとおりである。
【０１００】
次に、配送計画生成部１２は、第二エリア分割処理で得られたエリア（第二エリア分割処理で得られた出発拠点とその出発拠点に関連付けられた複数の配送拠点の集合）ごとに、図３や図８で例示した時空間ネットワークモデル上で、上記の各制約条件を満たすように枝情報を生成し、配送期限等の条件を満たす枝情報の集合を複数生成する（ステップＳ１３１）。図１７の例では、配送計画生成部１２は、エリアｊ６〜エリアｊ８のそれぞれについて、枝情報の集合を複数生成する。なお、配送計画生成部１２は、第二エリア分割処理で用いた単純な配送ルート及びその組み合わせに関係なく枝情報の生成を行ってもよいし、単純な配送ルート及びその組み合わせを利用して枝情報の生成を行ってもよい。
【０１０１】
次に、配送計画生成部１２は、生成した枝情報の集合ごとに総コストを計算する（ステップＳ１４）。図１７の例では、配送計画生成部１２は、エリアｊ６〜エリアｊ８のそれぞれについて、生成した枝情報の集合ごとの総コストを計算する。
次に配送計画生成部１２は、計算した総コストを比較し、総コストが最小となる枝情報の集合を選択する（ステップＳ１５）。図１７の例では、配送計画生成部１２は、エリアｊ６〜エリアｊ８のそれぞれについて、総コストが最小となる枝情報の集合を選択する。選択した枝情報の集合は、各エリアにおける配送計画を示している。つまり、配送計画生成部１２がエリアごとの配送計画を生成し終えると、分割前の全配送拠点についての配送計画が生成されたことになる。
【０１０２】
本実施形態によれば、初期条件で与えられた需要や供給のある全ての配送拠点の一つ一つを出発拠点に関連付けることによって出発拠点ごとの配送エリアに分割することができる。小規模な配送エリアに分割し、それらの配送エリアごとに配送計画の生成処理を行うことで、初期条件で与えられた全ての需要のある配送拠点を対象にして配送計画を生成する場合に比べ、配送計画の生成に必要な計算量を削減することができる。これにより、配送物や配送拠点の数が多く、配送問題が大規模になった場合でも、実用的な時間（例えば１０分）で配送計画を立案することができる。
【０１０３】
＜第三実施形態＞
さらに大規模な配送問題について実用的な時間で配送計画を生成する他の方法（第三実施形態）に係る配送計画システムについて図１９〜図２２を参照して説明する。第一実施形態、第二実施形態は、初期条件に含まれる配送拠点ごとの需要および供給の情報に基づいて配送問題を空間的に分割（エリア分割）することにより小規模な配送問題に分割し、小規模な配送問題を解くことにより処理の高速化を実現する方法であった。この第三実施形態では、初期条件に含まれる配送物の配送制限時間の情報に基づいて時間的な分割により配送問題を小問題化し、分割後の各時間ごとに配送計画を生成する。
【０１０４】
図１９は、本発明の第三実施形態における配送計画システムの一例を示す機能ブロック図である。
本発明の第三実施形態に係る構成のうち、本発明の第一実施形態に係る配送計画装置１０Ｂを構成する機能部と同じものには同じ符号を付し、それぞれの説明を省略する。第三実施形態に係る配送計画装置１０Ｂは、第一実施形態の構成における第一エリア分割部１４に代えて、時間分割部１７を備えている。また、配送計画装置１０Ｂは、配送計画生成部１２に代えて、配送計画生成部１２ａを備えている。
時間分割部１７は、初期条件で与えられた配送制限時間を複数の時間に分割することにより配送問題を分割した時間ごとの規模の小さな配送問題に分割する。時間分割部１７が分割して出来た各時間を区間と呼ぶ。
配送計画生成部１２ａは、時間分割部１７が分割してできた区間に応じて、異なる目的関数や制約を設定した配送問題を解いて配送計画を生成する。例えば、配送計画生成部１２ａは、分割後の各区間の最初の時刻における配送物の配送状況（１つ前の区間が終わったときの配送の進捗状況）から配送を開始して、当該区間内に配送物がなるべく多く需要のある配送拠点に配送されるような配送計画を生成する。また、時間分割部１７は、分割してできた区間のうち最後の区間については、その最後の区間内に初期条件で示された需要のある配送拠点の中で未配送となっている配送拠点の全てに配送物が配送される配送計画を生成する。
なお、時間分割部１７、配送計画生成部１２ａは、配送計画装置１０Ｂが備えるＣＰＵが、記憶部１５からプログラムを読み出して実行することで実現される。
【０１０５】
図２０は、本発明の第三実施形態における配送問題の時間分割処理を説明する第一の図である。
図２０の左図は、ある配送問題の初期状態を示している。配送拠点ｗ１では配送物ｄ１が２個余っており、配送拠点ｗ２では配送物ｄ１が３個余っている。また、配送拠点ｗ３では配送物ｄ１が４個不足しており、配送拠点ｗ４では配送物ｄ１が１個不足している。この初期状態から配送物ｄ１を、１２０分以内に配送拠点ｗ３、配送拠点ｗ４における需要を満たすように配送する問題を考える。第一実施形態、第二実施形態では、配送拠点ｗ１〜配送拠点ｗ４をエリアごとに分割した。本実施形態では、初期条件として与えられた配送制限時間１２０分を分割する。
具体的には、時間分割部１７は、配送制限時間１２０分を複数の時間（区間）に分割する。例えば、時間分割部１７は、配送制限時間１２０分を前半６０分、後半６０分の２つの区間に分割する。時間分割部１７が分割してできる１区間の時間の長さや区間の数は任意であってよい。例えば、時間分割部１７は、１２０分を９０分と３０分に分割してもよいし、４０分ごとの３つの区間に分類してもよい。また、時間分割部１７は、初期条件で与えられた配送制限時間よりも所定の時間だけ短い時間を分割後の１番目の区間とし、残りの時間を最後の区間としてもよい。
【０１０６】
図２０の右図は、時間分割部１７が、配送制限時間１２０分を６０分ずつの２つの区間に分割したことを示している。時間分割部１７が配送制限時間の分割を行うと、配送計画生成部１２ａが、分割してできた１つ目の区間について配送計画の生成を行う。このとき、配送計画生成部１２ａは、全ての要求を満たすことを目指すのではなく、１つ目の区間の終了時点にできるだけ多くの要求を満たせるような配送計画を生成する。なお、全ての要求を満たすことを目指すとは、この例の場合、配送拠点ｗ３と配送拠点ｗ４の需要数量を満足するように配送物ｄ１を６０分で配送することである。また、できるだけ多くの要求を満たせるような配送計画とは、例えば、配送を開始してから６０分後に、配送拠点ｗ３での配送物ｄ１の不足が３個、配送拠点ｗ４での配送物ｄ１の不足が０個となる配送計画と、配送拠点ｗ３での配送物ｄ１の不足が２個、配送拠点ｗ４での配送物ｄ１の不足が０個となる配送計画が生成できた場合、後者の配送計画のことをいう。
【０１０７】
次に１つ目の区間について設定する目的関数、制約について説明する。なお、次に説明する目的関数等は、より一般的には、時間分割部１７が、配送制限時間をＮ個に分割した場合、最後の区間（Ｎ番目の区間）を除く、全ての区間（時間の流れに沿って順に１番目の区間からＮ−１番目の区間）について使用する目的関数等である。
【０１０８】
（目的関数）
以下の（１）〜（７）の和を最小化する。
（１）拠点間の移動コスト
拠点間の移動コストを抑制することができる。
（２）需要供給を満たす時刻
需要供給を満たす時刻をなるべく早くするよう促すことで解の選択肢が減る（後の時刻でも同様な配送が可能な場合でも、最先の配送のみを解とすることで選択肢を減らすことができ、計算量の削減につながる）。
（３）需要を満たす場合に供給を行うポート番号
小さい番号のポートから供給を行うよう促すことで解の選択肢が減る（大きい番号のポートに配送しても問題ない場合でも、もっとも小さい番号のポートと定めておくことで解の選択肢を減らし計算量を削減することができる）。
（４）配送拠点に存在する人、配送手段のうち、後の区間で使用しないものの数（ｇ［ｗ］）
計算中の区間の最後の時刻において，次の区間で配送物の配送に用いられない余分な人・配送手段を出発拠点に移動させることを促す。例えば、第一区間の最後の時刻において、自転車を載せて移動できる配送手段が無くなっている場合、第二区間では自転車を配送に使用しないため出発拠点に移動させる。
（５）需要点における需要、供給点における供給が満たされた場合であって、それらの配送拠点に存在する人、配送手段の数
需要供給が満たされた配送拠点において、人や配送手段が残らないようにすることを促す。本実施形態では、時間分割を行ったそれぞれの区間について（一つ前の区間における配送状況の引き継ぎは行うが）、独立して配送計画を算出するので、後の区間で使用しない余分な配送スタッフや配送手段が配送拠点に残ってしまうことも考えられる。そこで（４）、（５）を加えて余分な配送スタッフなどが配送拠点に残らないようにする。
（６）供給点に残っている配送物の数、需要点で足りない配送物の数
（７）配送物が足りない需要点の数
（６）、（７）によって、その区間の最後の時刻において、なるべく需要供給の条件をできるだけ多く満たすことを促すことができる。
なお、目的関数は、各項目（１）〜（７）の各々の内容に対応する関数の和を最小化することとして表されるが、目的関数の各項（各項目の関数）に任意の係数を乗算して重み付けを行ってもよい。
【０１０９】
次に制約について説明する。
１．流量保存則
（ア）分割後の各区間のうち最後の区間以外の区間の場合
（１）配送物の流量について
区間の開始時点においては、供給が存在するポートから出る流量は１、供給が存在しないポートから出る流量は０となる。その他の点で、区間の終了時点でない場合は、出ていく流量と入る流量は等しい。
（２）配送車の流量について
区間の開始時点においては、道から出る流量は、その拠点に存在する配送車の数となる。その他の点で、区間の終了時点でない場合は、出ていく流量と入る流量は等しい。
（３）配送スタッフの流量について
区間の開始時点においては、道から出る流量は、その拠点に存在する配送スタッフの数となる。その他の点で、区間の終了時点でない場合は、出ていく流量と入る流量は等しい。
【０１１０】
（イ）分割後の各区間のうち最後の区間の場合
（１）配送物の流量について
区間の開始時点においては、供給が存在するポートから出る流量は１、供給が存在しないポートから出る流量は０となる。区間の終了時点においては、需要が存在するポートに入る流量は１、需要が存在しないポートに入る流量は０となる。その他の点では、出ていく流量と入る流量は等しい。
（２）配送車の流量について
区間の配送開始時点においては、道から出る流量は、その拠点に存在する配送車の数となる。区間の終了時点においては、道から入る流量は、その拠点で需要がある配送車の数となる。その他の点では、出ていく流量と入る流量は等しい。
（３）配送スタッフの流量について
区間の配送開始時点においては、道から出る流量は、その拠点に存在する配送スタッフの人数となる。区間の終了時点においては、道から入る流量は、その拠点で需要がある配送スタッフの人数となる。その他の点では、出ていく流量と入る流量は等しい。
【０１１１】
２．容量制約
配送拠点内の配送物、人の移動量は１以下である。
【０１１２】
３．配送拠点内の制約１
∀ｅ∈Ｅｗｐ 
（Ｅｗｐは配送物、配送手段、人の道からポートへの移動を示す枝の集合）
（１）ｅの行き先がｄの供給点のとき
配送物は道からポートには入ってこない。
（２）ｅの行き先がｄの需要点のとき
配送物と配送スタッフの流量が同じ値を取る（０または１）。
（３）どちらの場合も
自転車の台数は配送スタッフの人数以下である。
【０１１３】
４．配送拠点内の制約２
∀ｅ∈Ｅｐｗ 
（Ｅｐｗは配送物、配送手段、人のポートから道への移動を示す枝の集合）
（１）ｅの出発点がｄの供給点のとき
配送物と配送スタッフの流量が同じ値を取る（０または１）。
（２）ｅの出発点がｄの需要点のとき
配送物はポートから道には出ない。
（３）どちらの場合も
自転車の台数は配送スタッフの人数以下である。
【０１１４】
５．区間の最後の時刻におけるペナルティに関する変数に対する制約
任意の道ｗに対して、次の区間で使用しない人や配送手段の数をｇ［ｗ］としたとき、ｇ［ｗ］  ≦  ｆ［ｗ］という制約を入れる。
ｆ［ｗ］は任意の数を表す。ｆ［ｗ］の値を調整することで、区間の最後に残存することを許容できる人、配送手段の数を変更することができる。
【０１１５】
６．道から道への枝に対する制約
（１）道から道への枝が、車の枝のとき（自転車を載せる可能性がある）
配送車には必ず配送スタッフが乗ること、配送スタッフの人数は搭乗可能人数以下であること、運転できない自転車の台数は、車に積載可能な台数以下であることを制約とする。
（２）道から道への枝が、自転車の枝かつ徒歩の枝で車の枝ではないとき（自転車または徒歩で移動）
自転車台数と徒歩で移動している人数の和は、その枝を移動している配送スタッフの人数に等しい。
（３）道から道への枝が、自転車の枝であるが車の枝でも徒歩の枝でもないとき（自転車で移動）
自転車台数と、その枝を移動している配送スタッフの人数は等しい。
（４）道から道への枝が、徒歩の枝であるが車の枝でも自転車の枝でもないとき（徒歩で移動）
徒歩で移動している人数と、その枝を移動している配送スタッフの人数は等しい。
【０１１６】
７．配送拠点の中で留まる枝に対する制約
車には必ず人が乗ること、自転車は路駐できないこと、配送物の総体積はトラックの積載量以下であること、を制約とする。
【０１１７】
配送計画生成部１２ａは、これらの目的関数や制約条件で定式化された配送問題（整数計画問題）を、第１または第２の時空間ネットワークを用いて解く。なお、実際の計算においては、カットを加えてさらに高速化を図ってもよい。図２０の右図に、配送計画生成部１２ａが１番目の区間について配送計画を生成した結果の一例を示す。この計画によれば、配送を開始してから６０分後には、配送拠点ｗ１および配送拠点ｗ２では配送物ｄ１が１個余り、配送拠点ｗ３では配送物ｄ１が２個不足しており、配送拠点ｗ４では配送物ｄ１の不足が解消していることが分かる。
【０１１８】
このように時間を分割して計算する方法の利点として、次のような点を挙げることができる。まず、配送制限時間を１２０分から６０分にすることで、計算に必要なパラメータの数を減らし、計算量を削減することができる。図２０では、説明の便宜のため、配送拠点、配送物の数が共に少ない例を挙げているが、２０カ所の配送拠点に、２０個以上の配送物を１２０分以内に配送する問題を計算する場合、例えば、変数が４１０００、制約が６１０００にもなることが分かっている。これに対し、時間を前半の６０分で区切り、上記のできるだけ多くの要求を満たせるような配送計画を生成する場合、例えば、変数の数を１４０００、制約の数は１８０００程度に抑えることができる。このようにパラメータの数を減らすことで計算量を削減し、処理を高速化することができる。次に後半の６０分の配送計画の生成処理について説明する。
【０１１９】
図２１は、本発明の第三実施形態における配送問題の時間分割処理を説明する第二の図である。
図２１に分割後の後半６０分を使って行う配送計画の生成処理を示す。後半６０分の開始時点の各配送拠点における需要数量と供給数量について整理する。後半の開始時点の配送拠点ｗ１および配送拠点ｗ２では配送物ｄ１が１個余り、配送拠点ｗ３では配送物ｄ１が２個不足している。配送計画生成部１２ａが、後半６０分を使って生成しなければならない配送計画は、配送拠点ｗ１および配送拠点ｗ２の配送物ｄ１を、残りの６０分以内に配送拠点ｗ３における需要を満たすように配送する問題である。なお、配送拠点ｗ４については、配送拠点ｗ４の不足は前半６０分で解消しているので後半６０分の配送問題には含まれない。
【０１２０】
次に、配送制限時間をＮ個に分割した場合の最後の区間を対象とする配送問題について設定する目的関数、制約について説明する。この場合の目的関数や制約などは、第１の時空間ネットワークモデル（図３）、第２の時空間ネットワークモデル（図８）を用いて説明したものと同様である。つまり、配送計画生成部１２ａは、最後の区間の最後の時刻までに全ての需要を満たすように配送物を配送し終える配送計画のうち、最もコストや配送に掛かる移動時間を最小化する配送計画を生成する。
【０１２１】
後半の６０分（最後の区間）の処理についての利点を挙げると、まず、前半６０分と同様、配送制限時間を６０分にすることで、パラメータの数を減らし、計算量を削減することで処理の高速化を図ることができる点を挙げることができる。さらに、最後の区間に至るまでの各区間で算出されたなるべく多く要求を満たすような配送計画によって、残っている需要が減少しているため、解かなければならない配送問題の規模が小さくなっていることを挙げることができる。例えば図２０、図２１に示す例では、単に各需要点における需要数量が減るだけではなく、配送拠点ｗ４での需要が満たされているので、配送拠点の数を減らすことに成功している。これによりさらに配送問題の規模を小さくすることができる。２０カ所の配送拠点に２０個以上の配送物を１２０分以内に配送する問題を６０分ごとに分割した場合、後半６０分の区間においては、例えば、変数の数を８０００、制約の数は１２０００程度に減少させることができる。このように、本実施形態によれば、時間の分割によるパラメータの減少と、時間的に先の区間において生成した配送計画によって、後の区間での配送問題の規模を縮小化することができるので、配送計画の生成処理を高速化することができる。また、第三実施形態ではエリア分割を行わない為、第一実施形態、第二実施形態と比べ、配送拠点分布の大域性を確保したまま配送計画を生成することができ、より最適化された配送計画を生成することができる。
【０１２２】
次に本実施形態の配送計画の生成処理の流れについて説明する。
図２２は、本発明の第三実施形態における配送計画の生成処理の一例を示すフローチャートである。図１３、図１８と同様の処理については簡単に説明を行う。
まず、配送計画を行う配送スタッフが、配送計画装置１０Ｂに配送計画の初期条件を入力する。入出力部１３はその入力を受け付け、受け付けた情報を初期条件設定部１１に出力する。初期条件設定部１１は、配送スタッフが入力した初期条件の情報を取得する（ステップＳ１１）。
次に、時間分割部１７は、初期条件の情報に含まれる配送制限時間を用いて、時間分割処理を行う（ステップＳ１２２）。時間分割処理については図２０を用いて説明したとおりである。例えば、時間分割部１７は、初期条件の配送制限時間を２〜３つに分割する。あるいは、経験則などで需要のある配送拠点に対する配送完了が一定の割合で見込める時間（例えば７５分）が分かっている場合、ユーザの設定により、時間分割部１７は、その時間単位（例えば７５分）で元の配送制限時間を分割し、残りの時間を最後の区間としてもよい。あるいは、時間分割部１７は、初期条件で与えられた配送制限時間よりも所定の時間だけ短い時間を分割後の１番目の区間とし、残りの時間を最後の区間としてもよい。次に配送計画生成部１２ａは、分割された各区間に対して時間順に配送計画を生成する。まず、配送計画生成部１２ａは、カウンター変数ｎに１を設定する（ステップＳ１２３）。次に配送計画生成部１２ａは、ｎ番目の区間の配送問題を設定する（ステップＳ１２４）。例えば、１番目の区間であれば、配送計画生成部１２ａは、初期条件の情報に含まれる各配送拠点の需要数量、供給数量、出発拠点に存在する配送手段の数量、配送スタッフの人数、１番目の区間の時間を配送制限時間に用いて、できるだけ多くの要求を満たし、コストが最も安くなる配送計画の生成のための目的関数、制約条件による整数計画問題を定式化する。
【０１２３】
次に、配送計画生成部１２ａは、定式化した整数計画問題に対して、図３や図８で例示した第１または第２の時空間ネットワークモデルを用いて、各制約を満たしつつ、各配送拠点の需要をなるべく満足するような枝情報の集合を複数生成する（ステップＳ１３２）。次に、配送計画生成部１２ａは、生成した枝情報の集合ごとに総コストを計算する（ステップＳ１４）。次に配送計画生成部１２ａは、計算した総コストを比較し、総コストが最小となる枝情報の集合を選択する（ステップＳ１５）。これによって、ｎ番目（今回は１番目）の区間に対する配送計画が生成される。
【０１２４】
次に配送計画生成部１２ａは、ｎがＮと等しいかどうかを判定する（ステップＳ１６）。ｎがＮと等しい場合（ステップＳ１６；Ｙｅｓ）、分割後の全ての区間に対する配送計画が生成されていることになるので、配送計画の生成処理を終了する。ｎがＮと等しくない場合（ステップＳ１６；Ｎｏ）、配送計画生成部１２ａは、ｎに１を加算し（ステップＳ１７）、ステップＳ１２４からの処理を繰り返す。
【０１２５】
具体的には、例えば、１を加算した後のｎの値が２の場合、配送計画生成部１２ａは、ステップＳ１２４において、１番目の区間について生成した配送計画を実行した結果の各配送拠点の需要数量、供給数量、出発拠点に存在する配送手段の数量、配送スタッフの人数、２番目の区間の時間を配送制限時間に用いて、整数計画問題を定式化する。このとき、配送計画生成部１２ａは、ｎがＮと等しければ、全ての要求を満たす配送計画の生成のための目的関数、制約による整数計画問題を定式化する（第一実施形態、第二実施形態と同様の目的関数等）。ｎがＮと等しくない場合、配送計画生成部１２ａはできるだけ多くの要求を満たせる配送計画の生成のための目的関数、制約による整数計画問題を定式化する。配送計画生成部１２ａは、整数計画問題を解いて、ｎ番目の区間の配送計画を生成する。配送計画生成部１２ａは、全ての区間について配送計画を生成するまで（ｎがＮと等しくなるまで）ステップＳ１２４〜ステップＳ１７の処理を繰り返す。１番目の区間からＮ番目（最後）の区間のそれぞれについて順に生成した配送計画の全体が、初期条件で与えられた要求を満たす配送計画である。
【０１２６】
図２２のフローチャートでは、最初に初期条件で与えられた配送制限時間をいくつかの区間に分割したが、例えば、次のように配送計画処理を構成してもよい。
１．まず、初期条件で与えられた配送制限時間より短い区間（第一配送制限時間）を設定し、その区間内になるべく多く、且つ、安く配送できる配送計画を生成する。
２．次にその第一配送制限時間内で配送し終えることができない配送物については、さらに第一配送制限時間に続く所定長さの区間（第二配送制限時間）を設定し、設定した区間内になるべく多くの配送物を配送する配送計画を生成する。
３．１．〜２．のステップを、配送開始からの区間の長さの合計が配送制限時間を超えない間繰り返す。つまり、時間を延長しながら解を見つける（時間展開法）。最初の区間や延長する区間の長さは配送状況に応じて任意に設定してよい。
４．配送開始からの時間の合計が配送制限時間を超えそうになった場合は、次の区間を最後として、最後の区間内（直前に生成した配送計画の完了時点を開始時刻とし、第一配送制限時間の開始時刻を基準にして初期条件に含まれる配送制限時間が経過する時刻を終了時刻とする時間内）に全ての需要を満たしコストが最小となるような配送計画を生成する。
【０１２７】
本実施形態の配送計画生成処理を実際に行ったところ、配送拠点が２０カ所、配送物が２０個程度の配送問題に対して、実用的な時間（１０分以内）で準最適解（厳密な最適解と比べて目的関数の値の差が１０％以下）を算出することができた。
【０１２８】
なお、本実施形態の配送計画生成方法は以下のような場面で用いることもできる。例えば、１２０分間で全ての車両を需要のある駐車場に配送しなければならない場合、まず前半６０分について配送計画を生成する。配送計画を生成し終えると、実際にその配送計画に基づいて、車両の配送を開始する。車両の配送を行っている間、残りの６０分間の配送計画を生成する。このように、配送計画の生成処理と配送とを並行して行うことで、例えばカーシェアリングのサービスを行う現場で、時間を有効に使うことができる。
【０１２９】
なお、上述した配送計画装置１０、１０Ａ、１０Ｂにおける各処理の過程は、プログラムの形式でコンピュータ読み取り可能な記録媒体に記憶されており、このプログラムを配送計画システムのコンピュータが読み出して実行することによって、上記処理が行われる。ここでコンピュータ読み取り可能な記録媒体とは、磁気ディスク、光磁気ディスク、ＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭ、半導体メモリ等をいう。また、このコンピュータプログラムを通信回線によってコンピュータに配信し、この配信を受けたコンピュータが当該プログラムを実行するようにしてもよい。
【０１３０】
また、上記プログラムは、前述した機能の一部を実現するためのものであってもよい。さらに、前述した機能をコンピュータシステムにすでに記録されているプログラムとの組み合わせで実現できるもの、いわゆる差分ファイル（差分プログラム）であってもよい。
また、配送計画装置１０、１０Ａ、１０Ｂは、１台のコンピュータで構成されていても良いし、通信可能に接続された複数のコンピュータで構成されていてもよい。
【０１３１】
その他、本発明の趣旨を逸脱しない範囲で、上記した実施の形態における構成要素を周知の構成要素に置き換えることは適宜可能である。また、この発明の技術範囲は上記の実施形態に限られるものではなく、本発明の趣旨を逸脱しない範囲において種々の変更を加えることが可能である。
【０１３２】
なお、配送スタッフは配送主体の一例であり、配送車、トラック、自転車は配送手段の一例であり、カーシェアリングにおける共用の車両は配送物の一例である。また、第一エリア分割部１４、第二エリア分割部１６、時間分割部１７の各々は分割部の一例である。
【符号の説明】
【０１３３】
１０、１０Ａ、１０Ｂ・・・配送計画装置
１１・・・初期条件設定部
１２、１２ａ・・・配送計画生成部
１３・・・入出力部
１４・・・第一エリア分割部
１５・・・記憶部
１６・・・第二エリア分割部
１７・・・時間分割部
【図１】
2018073213.tif 000007
【図２】
2018073213.tif 000008
【図３】
2018073213.tif 000009
【図４】
2018073213.tif 000010
【図５】
2018073213.tif 000011
【図６】
2018073213.tif 000012
【図７】
2018073213.tif 000013
【図８】
2018073213.tif 000014
【図９】
2018073213.tif 000015
【図１０】
2018073213.tif 000016
【図１１】
2018073213.tif 000017
【図１２】
2018073213.tif 000018
【図１３】
2018073213.tif 000019
【図１４】
2018073213.tif 000020
【図１５】
2018073213.tif 000021
【図１６】
2018073213.tif 000022
【図１７】
2018073213.tif 000023
【図１８】
2018073213.tif 000024
【図１９】
2018073213.tif 000025
【図２０】
2018073213.tif 000026
【図２１】
2018073213.tif 000027
【図２２】
2018073213.tif 000028