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