JPH07175504A - 配送問題における最適な配車と配送順序の探索装置および探索方法 - Google Patents
配送問題における最適な配車と配送順序の探索装置および探索方法Info
- Publication number
- JPH07175504A JPH07175504A JP31974393A JP31974393A JPH07175504A JP H07175504 A JPH07175504 A JP H07175504A JP 31974393 A JP31974393 A JP 31974393A JP 31974393 A JP31974393 A JP 31974393A JP H07175504 A JPH07175504 A JP H07175504A
- Authority
- JP
- Japan
- Prior art keywords
- delivery
- order
- vehicle allocation
- cost
- energy function
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Granted
Links
Landscapes
- Feedback Control In General (AREA)
- Traffic Control Systems (AREA)
- Control Of Position, Course, Altitude, Or Attitude Of Moving Bodies (AREA)
- Loading Or Unloading Of Vehicles (AREA)
- Management, Administration, Business Operations System, And Electronic Commerce (AREA)
Abstract
(57)【要約】
【目的】 配送問題における配車と配送順序の２種の問
題を種々の制約条件の下で解き、かつ、コストを抑える
ことができるような配送問題における最適な配車と配送
順序の探索装置および探索方法を提供することである。 【構成】 探索装置は、各行が各車両に対応し、各列が
配送順序に対応する２次元配列の配列計画案を決定する
第１の決定部３と、コストを表わすコスト関数と配送先
等での制約条件を決定する第２の決定部５と、コスト関
数を表わすコスト項と制約条件を表わす制約項の線形和
でエネルギー関数を演算して定義する演算部７と、エネ
ルギー関数を最小化する最小化部９とを備え、データ入
力部１から配送問題に必要なデータがそれぞれ入力さ
れ、演算結果は演算結果出力部１１より出力される。
題を種々の制約条件の下で解き、かつ、コストを抑える
ことができるような配送問題における最適な配車と配送
順序の探索装置および探索方法を提供することである。 【構成】 探索装置は、各行が各車両に対応し、各列が
配送順序に対応する２次元配列の配列計画案を決定する
第１の決定部３と、コストを表わすコスト関数と配送先
等での制約条件を決定する第２の決定部５と、コスト関
数を表わすコスト項と制約条件を表わす制約項の線形和
でエネルギー関数を演算して定義する演算部７と、エネ
ルギー関数を最小化する最小化部９とを備え、データ入
力部１から配送問題に必要なデータがそれぞれ入力さ
れ、演算結果は演算結果出力部１１より出力される。
Description
【０００１】
【産業上の利用分野】この発明は、配送問題における最
適な配車と配送順序の探索装置および探索方法に関し、
特に、配送問題に対して与えられる各種の制約条件が満
たされ、かつコストを極力抑えることができるような最
適な配車と配送順序を探索する配送問題における最適な
配車と配送順序の探索装置および探索方法に関する。
適な配車と配送順序の探索装置および探索方法に関し、
特に、配送問題に対して与えられる各種の制約条件が満
たされ、かつコストを極力抑えることができるような最
適な配車と配送順序を探索する配送問題における最適な
配車と配送順序の探索装置および探索方法に関する。
【０００２】
【従来の技術】複数の車両を用いて多数の荷物をそれぞ
れの配送先に配送するには、どの車両にどの荷物を積込
み（配車）、かつ、各車両が割り当てられた配送先をど
のような順序で回るか（配送順序）という２つの問題が
解かれなければならない。特に、配送先において、配送
時刻の指定や、乗り入れ可能な車両種に関する制限、車
両積載量の上限、車両の出発時刻や帰着点などの種々の
制約条件が課される場合があり、その場合には、それら
の制約条件をすべて満たし、かつ、与えられた目的関数
を最小化にする解が求められる必要がある。目的関数と
しては、各車両が費やした配送時間の総計や偏差、ある
いは、すべての配送が完了する時刻などが実用的には必
要とされている。
れの配送先に配送するには、どの車両にどの荷物を積込
み（配車）、かつ、各車両が割り当てられた配送先をど
のような順序で回るか（配送順序）という２つの問題が
解かれなければならない。特に、配送先において、配送
時刻の指定や、乗り入れ可能な車両種に関する制限、車
両積載量の上限、車両の出発時刻や帰着点などの種々の
制約条件が課される場合があり、その場合には、それら
の制約条件をすべて満たし、かつ、与えられた目的関数
を最小化にする解が求められる必要がある。目的関数と
しては、各車両が費やした配送時間の総計や偏差、ある
いは、すべての配送が完了する時刻などが実用的には必
要とされている。
【０００３】このような配送問題の具体的な例として
は、トラックによる食品、飲料品、衣類、雑貨、部品、
生産物などの荷物を飲食店、商店、工場、一般家庭など
に配送するものが挙げられる。このような配送問題で
は、最適な組合せを探索する必要があり、従来の数理計
画法は、一般的な分岐限定法を用いてきた。この分岐限
定法は、直接解くことが難しい問題をよりやさしい部分
問題に分割（分岐）し、その部分問題を評価して不必要
な部分問題を取り除き（限定）、可能性のある部分問題
をすべて解くという考え方が基本とされている。
は、トラックによる食品、飲料品、衣類、雑貨、部品、
生産物などの荷物を飲食店、商店、工場、一般家庭など
に配送するものが挙げられる。このような配送問題で
は、最適な組合せを探索する必要があり、従来の数理計
画法は、一般的な分岐限定法を用いてきた。この分岐限
定法は、直接解くことが難しい問題をよりやさしい部分
問題に分割（分岐）し、その部分問題を評価して不必要
な部分問題を取り除き（限定）、可能性のある部分問題
をすべて解くという考え方が基本とされている。
【０００４】
【発明が解決しようとする課題】しかしながら、現実の
配送問題においては、制約条件が複雑であったり、目的
関数が単一でない多目的最適化問題である場合が多い。
したがって、分岐限定法では、制約条件や目的関数が変
わるたびにプログラムを書き直す必要があり、実際の配
送の現場で用いられることはほとんどなく、熟練した配
送係の直感と経験に頼っているのが現状である。
配送問題においては、制約条件が複雑であったり、目的
関数が単一でない多目的最適化問題である場合が多い。
したがって、分岐限定法では、制約条件や目的関数が変
わるたびにプログラムを書き直す必要があり、実際の配
送の現場で用いられることはほとんどなく、熟練した配
送係の直感と経験に頼っているのが現状である。
【０００５】しかし、配送先や配送問題などの種類や、
車両走行速度などの道路事情や、配送時刻などの制約条
件も日々変化し、人間がこれらの諸条件を満足する配送
計画案を立案するにはかなりの困難が伴う。実際、短時
間で処理する必要もあり、配送係の精神的負荷は少なか
らないものとなっている。しかも、人間が経験に基づい
て立案した配送計画案が、輸送コストなどの目的関数の
最小値を与えてくれるという保証は少ない。
車両走行速度などの道路事情や、配送時刻などの制約条
件も日々変化し、人間がこれらの諸条件を満足する配送
計画案を立案するにはかなりの困難が伴う。実際、短時
間で処理する必要もあり、配送係の精神的負荷は少なか
らないものとなっている。しかも、人間が経験に基づい
て立案した配送計画案が、輸送コストなどの目的関数の
最小値を与えてくれるという保証は少ない。
【０００６】ゆえに、この発明の目的は、配送時刻の指
定や、乗り入れ可能な車両種に関する制限、積載量の上
限、車両の出発時刻や帰着点などの種々の制約条件が課
された場合に、それらの制約条件をすべて満たし、か
つ、各車両が費やした配送時間の総計や偏差、あるい
は、すべての配送が完了する時刻などの多目的な目的関
数を最小化して、最適な配送と配送順序を探索すること
ができるような配送問題における最適な配車と配送順序
の探索装置および探索方法を提供することである。
定や、乗り入れ可能な車両種に関する制限、積載量の上
限、車両の出発時刻や帰着点などの種々の制約条件が課
された場合に、それらの制約条件をすべて満たし、か
つ、各車両が費やした配送時間の総計や偏差、あるい
は、すべての配送が完了する時刻などの多目的な目的関
数を最小化して、最適な配送と配送順序を探索すること
ができるような配送問題における最適な配車と配送順序
の探索装置および探索方法を提供することである。
【０００７】
【課題を解決するための手段】請求項１の発明に係る配
送問題における最適な配車と配送順序の探索装置は、多
数の荷物等を複数の車両で複数の配送先に配送する配送
問題において、多数の荷物が各車両に割り振られる配車
と、各車両が複数の配送先の中で割り振られた配送先に
各荷物を配送する配送順序とを最適化する配送問題にお
ける最適な配車と配送順序の探索装置であって、配車と
配送順序が示される配送計画案を決定する第１の決定手
段、第１の決定手段で決定された配送計画案が満たすべ
き制約条件および配送計画案を立案するために最小化さ
れるべきコスト関数を決定する第２の決定手段、第２の
決定手段で決定された制約条件から外れるほど増大し、
第２の決定手段で決定されたコスト関数が増大するほど
増大するエネルギー関数を演算する演算手段、および演
算手段で演算されたエネルギー関数を最小化する最小化
手段を備えている。
送問題における最適な配車と配送順序の探索装置は、多
数の荷物等を複数の車両で複数の配送先に配送する配送
問題において、多数の荷物が各車両に割り振られる配車
と、各車両が複数の配送先の中で割り振られた配送先に
各荷物を配送する配送順序とを最適化する配送問題にお
ける最適な配車と配送順序の探索装置であって、配車と
配送順序が示される配送計画案を決定する第１の決定手
段、第１の決定手段で決定された配送計画案が満たすべ
き制約条件および配送計画案を立案するために最小化さ
れるべきコスト関数を決定する第２の決定手段、第２の
決定手段で決定された制約条件から外れるほど増大し、
第２の決定手段で決定されたコスト関数が増大するほど
増大するエネルギー関数を演算する演算手段、および演
算手段で演算されたエネルギー関数を最小化する最小化
手段を備えている。
【０００８】請求項２では、請求項１の第１の決定手段
は、配送計画案を複数行と列で表わされる２次元配列で
表現し、２次元配列における各行は各車両に対応し、各
列は配送順序に対応し、各配列要素は、出発地点を表わ
す記号、各配送先を表わす記号、または列の数を一致さ
せるためのダミー記号であることを特徴としている。
は、配送計画案を複数行と列で表わされる２次元配列で
表現し、２次元配列における各行は各車両に対応し、各
列は配送順序に対応し、各配列要素は、出発地点を表わ
す記号、各配送先を表わす記号、または列の数を一致さ
せるためのダミー記号であることを特徴としている。
【０００９】請求項３では、請求項２の配送順序は、配
送先と他の配送先との間に出発地点に戻る場合も含む。
送先と他の配送先との間に出発地点に戻る場合も含む。
【００１０】請求項４では、請求項１から３いずれかの
演算手段で演算されるエネルギー関数は、制約条件を表
わす項とコスト関数を表わす項との線形和として演算さ
れることを特徴としている。
演算手段で演算されるエネルギー関数は、制約条件を表
わす項とコスト関数を表わす項との線形和として演算さ
れることを特徴としている。
【００１１】請求項５では、請求項４の最小化手段は、
前記制約条件を表わす項と前記コスト関数を表わす項と
の線形和として演算されたエネルギー関数をシミュレー
テッドアニーリング法を用いて最小化することを特徴と
している。
前記制約条件を表わす項と前記コスト関数を表わす項と
の線形和として演算されたエネルギー関数をシミュレー
テッドアニーリング法を用いて最小化することを特徴と
している。
【００１２】請求項６の発明に係る配送問題における最
適な配車と配送順序の探索方法は、多数の荷物を複数の
車両で複数の配送先に配送する配送問題において、多数
の荷物が各車両に割り振られる配車と、各車両が複数の
配送先の中で割り振られた配送先に各荷物を配送する配
送順序とを最適化する配送問題における最適な配車と配
送順序の探索方法であって、配車と配送順序が示される
配送計画案を決定する第１のステップ、第１のステップ
で決定された配送計画案が満たすべき制約条件および配
送計画案を立案するために最小化されるべきコスト関数
を決定する第２のステップ、第２のステップで決定され
た制約条件から外れるほど増大し、第２のステップで決
定されたコスト関数が増大するほど増大するエネルギー
関数を演算する第３のステップ、および第３のステップ
で演算されたエネルギー関数を最小化してそのときの配
送計画案が最適であると判断する第４のステップを含ん
でいる。
適な配車と配送順序の探索方法は、多数の荷物を複数の
車両で複数の配送先に配送する配送問題において、多数
の荷物が各車両に割り振られる配車と、各車両が複数の
配送先の中で割り振られた配送先に各荷物を配送する配
送順序とを最適化する配送問題における最適な配車と配
送順序の探索方法であって、配車と配送順序が示される
配送計画案を決定する第１のステップ、第１のステップ
で決定された配送計画案が満たすべき制約条件および配
送計画案を立案するために最小化されるべきコスト関数
を決定する第２のステップ、第２のステップで決定され
た制約条件から外れるほど増大し、第２のステップで決
定されたコスト関数が増大するほど増大するエネルギー
関数を演算する第３のステップ、および第３のステップ
で演算されたエネルギー関数を最小化してそのときの配
送計画案が最適であると判断する第４のステップを含ん
でいる。
【００１３】請求項７では、請求項６の第１のステップ
で決定される配送計画案は、複数行と列で表わされる２
次元配列で表現され、２次元配列における各行は各車両
に対応し、各列は配送順序に対応し、各配列要素は、出
発地点を表わす記号、各配送先を表わす記号、または列
の数を一致させるためのダミー記号であることを特徴と
している。
で決定される配送計画案は、複数行と列で表わされる２
次元配列で表現され、２次元配列における各行は各車両
に対応し、各列は配送順序に対応し、各配列要素は、出
発地点を表わす記号、各配送先を表わす記号、または列
の数を一致させるためのダミー記号であることを特徴と
している。
【００１４】請求項８では、請求項７の配送順序は、配
送先と他の配送先との間に出発地点に戻る場合も含んで
いる。
送先と他の配送先との間に出発地点に戻る場合も含んで
いる。
【００１５】請求項９では、請求項６から８いずれかの
第３のステップで演算されるエネルギー関数は、制約条
件を表わす項とコスト関数を表わす項との線形和として
演算されることを特徴としている。
第３のステップで演算されるエネルギー関数は、制約条
件を表わす項とコスト関数を表わす項との線形和として
演算されることを特徴としている。
【００１６】請求項１０では、請求項９の第４のステッ
プは、第３のステップで演算されたエネルギー関数をシ
ミュレーテッドアニーリング法を用いて最小化するステ
ップを含んでいる。
プは、第３のステップで演算されたエネルギー関数をシ
ミュレーテッドアニーリング法を用いて最小化するステ
ップを含んでいる。
【００１７】
【作用】請求項１の発明に係る配送問題における最適な
配車と配送順序の探索装置は、配送問題をエネルギー関
数に帰着させ、そのエネルギー関数を最小化して最適な
配車と配送順序を探索できる。
配車と配送順序の探索装置は、配送問題をエネルギー関
数に帰着させ、そのエネルギー関数を最小化して最適な
配車と配送順序を探索できる。
【００１８】請求項２の発明に係る配送問題における最
適な配車と配送順序の探索装置は、配送計画案を２次元
配列で表現し、配車と配送順序という２種類の問題を同
時に解くことができる。
適な配車と配送順序の探索装置は、配送計画案を２次元
配列で表現し、配車と配送順序という２種類の問題を同
時に解くことができる。
【００１９】請求項３の発明に係る配送問題における最
適な配車と配送順序の探索装置は、積載上限量の小さい
車両を２回転以上利用する配送計画案の立案を可能とす
る。
適な配車と配送順序の探索装置は、積載上限量の小さい
車両を２回転以上利用する配送計画案の立案を可能とす
る。
【００２０】請求項４の発明に係る配送問題における最
適な配車と配送順序の探索装置は、エネルギー関数を制
約条件を表わす項とコスト関数を表わす項との線形和と
して演算するので、制約条件やコスト関数の重要度に応
じてエネルギー関数を演算して定義できる。
適な配車と配送順序の探索装置は、エネルギー関数を制
約条件を表わす項とコスト関数を表わす項との線形和と
して演算するので、制約条件やコスト関数の重要度に応
じてエネルギー関数を演算して定義できる。
【００２１】請求項５の発明に係る配送問題における最
適な配車と配送順序の探索装置は、エネルギー関数をシ
ミュレーテッドアニーリング方法を用いて最小化するの
で、エネルギー関数の値が小さい解に重点をおいて確率
的に近似解を求めることができる。
適な配車と配送順序の探索装置は、エネルギー関数をシ
ミュレーテッドアニーリング方法を用いて最小化するの
で、エネルギー関数の値が小さい解に重点をおいて確率
的に近似解を求めることができる。
【００２２】請求項６の発明に係る配送問題における最
適な配車と配送順序の探索方法は、配送問題をエネルギ
関数に帰着させ、そのエネルギ関数を最小化して最適な
配車と配送順序を探索できる。
適な配車と配送順序の探索方法は、配送問題をエネルギ
関数に帰着させ、そのエネルギ関数を最小化して最適な
配車と配送順序を探索できる。
【００２３】請求項７の発明に係る配送問題における最
適な配車と配送順序の探索方法は、配送計画案を２次元
配列で表現し、配車と配送順序という２種の問題を同時
に解くことができる。
適な配車と配送順序の探索方法は、配送計画案を２次元
配列で表現し、配車と配送順序という２種の問題を同時
に解くことができる。
【００２４】請求項８の発明に係る配送問題における最
適な配車と配送順序の探索方法は、積載上限量の小さい
車両を２回転以上利用する配送計画案の立案を可能とす
る。
適な配車と配送順序の探索方法は、積載上限量の小さい
車両を２回転以上利用する配送計画案の立案を可能とす
る。
【００２５】請求項９の発明に係る配送問題における最
適な配車と配送順序の探索方法は、エネルギ関数を制約
条件を表わす項とコスト関数を表わす項との線形和とし
て演算するので、制約条件やコスト関数の重要度に応じ
てエネルギ関数を演算して定義できる。
適な配車と配送順序の探索方法は、エネルギ関数を制約
条件を表わす項とコスト関数を表わす項との線形和とし
て演算するので、制約条件やコスト関数の重要度に応じ
てエネルギ関数を演算して定義できる。
【００２６】請求項１０の発明に係る配送問題における
最適な配車と配送順序の探索方法は、エネルギ関数をシ
ュミレーテッドアニーリング法を用いて最小化するの
で、エネルギ関数の値が小さい解に重点をおいて確率的
な検知から求めることができる。
最適な配車と配送順序の探索方法は、エネルギ関数をシ
ュミレーテッドアニーリング法を用いて最小化するの
で、エネルギ関数の値が小さい解に重点をおいて確率的
な検知から求めることができる。
【００２７】
【実施例】図１は、この発明の一実施例による配送問題
における最適な配車と配送順序の探索装置の概略ブロッ
ク図であり、図２は、図１の演算部の構成を示した概略
ブロック図である。
における最適な配車と配送順序の探索装置の概略ブロッ
ク図であり、図２は、図１の演算部の構成を示した概略
ブロック図である。
【００２８】図１および図２を参照して、探索装置は、
配送問題を解くために必要なデータを入力するデータ入
力部１と、配送計画案を決定する第１の決定部３と、コ
スト関数と制約条件を決定する第２の決定部５と、第１
の決定部３および第２の決定部５の情報を用いてエネル
ギー関数を演算して定義する演算部７と、演算部７で定
義されたエネルギー関数を最小化する最小化部９とを備
え、演算結果が演算結果出力部１１から出力される。さ
らに、データ入力部１、第１の決定部３、第２の決定部
５、演算部７、最小化部９および演算結果出力部１１を
制御するための制御部１３が設けられている。また、特
に最小化部９においては、図２に示すように、エネルギ
ー関数を最小化するために必要な乱数発生部１５と、パ
ラメータ格納部１７と、試行変形の禁則条件格納部１９
とが設けられている。
配送問題を解くために必要なデータを入力するデータ入
力部１と、配送計画案を決定する第１の決定部３と、コ
スト関数と制約条件を決定する第２の決定部５と、第１
の決定部３および第２の決定部５の情報を用いてエネル
ギー関数を演算して定義する演算部７と、演算部７で定
義されたエネルギー関数を最小化する最小化部９とを備
え、演算結果が演算結果出力部１１から出力される。さ
らに、データ入力部１、第１の決定部３、第２の決定部
５、演算部７、最小化部９および演算結果出力部１１を
制御するための制御部１３が設けられている。また、特
に最小化部９においては、図２に示すように、エネルギ
ー関数を最小化するために必要な乱数発生部１５と、パ
ラメータ格納部１７と、試行変形の禁則条件格納部１９
とが設けられている。
【００２９】図３は、図１および図２に示した探索装置
で最適な配車と配送順序が探索される過程を示したフロ
ー図であり、図４は、図１の決定部で決定される配送計
画案を２次元配列で表現した状態を示した図であって、
その初期状態を示した図である。以下、図１および図２
の装置の動作について、図３および図４を参照して詳細
に説明する。
で最適な配車と配送順序が探索される過程を示したフロ
ー図であり、図４は、図１の決定部で決定される配送計
画案を２次元配列で表現した状態を示した図であって、
その初期状態を示した図である。以下、図１および図２
の装置の動作について、図３および図４を参照して詳細
に説明する。
【００３０】基本的には、配送計画案を店舗を表わす記
号等による２次元配列で表現し、２次元配列をシステム
とみなしてその状態におけるエネルギー関数を定義し、
エネルギー関数の最小状態をシミュレーテッドアニーリ
ング法（S.Kirkpatrick,C.D.Gelatt Jr.,M.P.Vecchi:
“Optimization by Simulated Annealing ”,Science,V
ol.220,No.4598,pp.671-680 （1983））により求めるこ
とが概略である。したがって、図３に示すフロー図で
は、次の３つのステップにまとめられる。
号等による２次元配列で表現し、２次元配列をシステム
とみなしてその状態におけるエネルギー関数を定義し、
エネルギー関数の最小状態をシミュレーテッドアニーリ
ング法（S.Kirkpatrick,C.D.Gelatt Jr.,M.P.Vecchi:
“Optimization by Simulated Annealing ”,Science,V
ol.220,No.4598,pp.671-680 （1983））により求めるこ
とが概略である。したがって、図３に示すフロー図で
は、次の３つのステップにまとめられる。
【００３１】ステップ（図面では、Ｓで表わす）１にお
いて、２次元配列で表わされた配送計画案の初期状態を
設定する。そして、２次元配列をシステムとみなしたの
で、２次元配列はエネルギーを有する。
いて、２次元配列で表わされた配送計画案の初期状態を
設定する。そして、２次元配列をシステムとみなしたの
で、２次元配列はエネルギーを有する。
【００３２】そこで、ステップ２において、温度一定の
条件下で、後で詳しく説明するメトロポリス法を用いて
システムを熱平衡状態に到達させる。制約条件がすべて
満たされた状態（実行可能解）の中で、エネルギーの値
が最小である状態が記録される。システムが温度Ｔによ
る所定の確率分布で熱平衡状態になるとすると、温度Ｔ
が低ければ低いエネルギー状態になる確率が高く、温度
Ｔが高ければエネルギー状態が高い状態になる確率は高
い。
条件下で、後で詳しく説明するメトロポリス法を用いて
システムを熱平衡状態に到達させる。制約条件がすべて
満たされた状態（実行可能解）の中で、エネルギーの値
が最小である状態が記録される。システムが温度Ｔによ
る所定の確率分布で熱平衡状態になるとすると、温度Ｔ
が低ければ低いエネルギー状態になる確率が高く、温度
Ｔが高ければエネルギー状態が高い状態になる確率は高
い。
【００３３】そこで、ステップ３において、温度を下げ
ていく。温度を下げるということは、具体的には温度列
｛Ｔi ｝（ｉ＝０，１，…，ｎ）を設定しておき、ｉ→
ｉ＋１として下げていけばよい。そして、ｉ＞ｎならば
終了し、そうでなければステップ２へ戻ってもう一度ス
テップ２の過程が行なわれていく。
ていく。温度を下げるということは、具体的には温度列
｛Ｔi ｝（ｉ＝０，１，…，ｎ）を設定しておき、ｉ→
ｉ＋１として下げていけばよい。そして、ｉ＞ｎならば
終了し、そうでなければステップ２へ戻ってもう一度ス
テップ２の過程が行なわれていく。
【００３４】さらにステップ１〜ステップ３について詳
細に説明すると、まずデータ入力部１から、配送先の店
舗間の最短移動時間とその経路の情報、温度スケジュー
ル、制約項とコスト項の重み、乱数のシードなどの必要
なパラメータの値、システム（２次元配列である行列
Ｘ）の初期値などが読出される。
細に説明すると、まずデータ入力部１から、配送先の店
舗間の最短移動時間とその経路の情報、温度スケジュー
ル、制約項とコスト項の重み、乱数のシードなどの必要
なパラメータの値、システム（２次元配列である行列
Ｘ）の初期値などが読出される。
【００３５】次に、配送計画案を決定する第１の決定部
から現在の２次元配列を表わす行列Ｘが読出される。こ
こで、２次元配列の状態について詳しく説明する。図４
に示すようにＭ×Ｌの行列Ｘを考える。行列Ｘの要素
は、ｘi,j （ｉ＝１，…，Ｍ，ｊ＝１，…，Ｌ）で表わ
される。ｉは、車両を識別し、ｊは配送順序に対応して
いる。Ｍは、配送に利用する車両の台数で定数とする。
Ｌは、Ｌ＝Ｎ＋Ｎrot ＋１で定義される定数とする。た
だし、Ｎは、総店舗数に１を加えた整数であり、Ｎrot
は、第（１）式で定義される定数である。
から現在の２次元配列を表わす行列Ｘが読出される。こ
こで、２次元配列の状態について詳しく説明する。図４
に示すようにＭ×Ｌの行列Ｘを考える。行列Ｘの要素
は、ｘi,j （ｉ＝１，…，Ｍ，ｊ＝１，…，Ｌ）で表わ
される。ｉは、車両を識別し、ｊは配送順序に対応して
いる。Ｍは、配送に利用する車両の台数で定数とする。
Ｌは、Ｌ＝Ｎ＋Ｎrot ＋１で定義される定数とする。た
だし、Ｎは、総店舗数に１を加えた整数であり、Ｎrot
は、第（１）式で定義される定数である。
【００３６】ｘi,j は、｛−１，０，１，…，Ｎ−１｝
のどれかの値をとる。ここで、０は出発点の配送センタ
ーを表わし、１から（Ｎ−１）は、各店舗の番号を表わ
している。たとえば、４６店舗の場合にはＮ＝４７とな
る。
のどれかの値をとる。ここで、０は出発点の配送センタ
ーを表わし、１から（Ｎ−１）は、各店舗の番号を表わ
している。たとえば、４６店舗の場合にはＮ＝４７とな
る。
【００３７】図４において、第１行は、最初の値は０
（配送センター）に固定され、２番目からは、店舗を表
わす番号が１から（Ｎ−１）まで昇順に並べられる。次
に、番号１の車両に指定された最大回転数ｎ(1) rot か
ら１を引いた個数だけ０が並べられる。最後に、−１を
１個だけ並べる。２行目以降は、ｎ(i) rot 個の０が並
べられたすぐ後には、すべて−１を並べる。ただし、探
索結果はこれらの初期状態にあまり依存しない。
（配送センター）に固定され、２番目からは、店舗を表
わす番号が１から（Ｎ−１）まで昇順に並べられる。次
に、番号１の車両に指定された最大回転数ｎ(1) rot か
ら１を引いた個数だけ０が並べられる。最後に、−１を
１個だけ並べる。２行目以降は、ｎ(i) rot 個の０が並
べられたすぐ後には、すべて−１を並べる。ただし、探
索結果はこれらの初期状態にあまり依存しない。
【００３８】１つの配送計画案は、このように２次元行
列で表現される。各行の番号の列は、各車両が行なうべ
き配送順序を左から順に表わしていることになってい
る。ただし、０は配送センターへ戻ること（回転）を表
わしており、−１はダミー記号で配送順序に関係なく読
み飛ばすものとする。−１というダミー記号は、２次元
配列のサイズを固定化し、コンピュータ計算において確
保するメモリ領域が固定化されるために導入されてい
る。また、ある店舗をある車両の配送順序に挿入すると
いう試行変形が、後で詳しく説明する２つの行列要素の
入れ替え（互換）操作により簡単に実現できるという利
点がある。
列で表現される。各行の番号の列は、各車両が行なうべ
き配送順序を左から順に表わしていることになってい
る。ただし、０は配送センターへ戻ること（回転）を表
わしており、−１はダミー記号で配送順序に関係なく読
み飛ばすものとする。−１というダミー記号は、２次元
配列のサイズを固定化し、コンピュータ計算において確
保するメモリ領域が固定化されるために導入されてい
る。また、ある店舗をある車両の配送順序に挿入すると
いう試行変形が、後で詳しく説明する２つの行列要素の
入れ替え（互換）操作により簡単に実現できるという利
点がある。
【００３９】次に、コスト関数と制約条件を決定する第
２の決定部５は、たとえばある配送センターから荷物を
積込み、トラックで複数店舗に配送する場合には、以下
に示すコスト関数と制約条件を決定する。
２の決定部５は、たとえばある配送センターから荷物を
積込み、トラックで複数店舗に配送する場合には、以下
に示すコスト関数と制約条件を決定する。
【００４０】３種類のコスト関数を例に挙げると、第１
は、配送にかかる人件費や燃料代などの配送コストであ
る各車両が配送にかかった所要時間（拘束時間）の総計
である。第２は、生鮮食料品などのように配送時刻が重
要な場合に要求される目的関数であって、すべての配送
や積下ろしが完了する時刻までの時間である。第３は、
労務管理上、ドライバ間での労働時間の均等な割当てが
要求される場合に最初にすべき目的関数であって、指定
された車両が配送にかかった所要時間（拘束時間）の標
準偏差である。 コスト関数は、重要度に応じて重みが
与えられ、複数個のコスト関数が重ねられる場合もあ
る。制約条件としては、たとえば店舗（配送先）に関す
るものと、車両（トラック）に関するものとの２種類が
あり、以下にそれらの例を示す。
は、配送にかかる人件費や燃料代などの配送コストであ
る各車両が配送にかかった所要時間（拘束時間）の総計
である。第２は、生鮮食料品などのように配送時刻が重
要な場合に要求される目的関数であって、すべての配送
や積下ろしが完了する時刻までの時間である。第３は、
労務管理上、ドライバ間での労働時間の均等な割当てが
要求される場合に最初にすべき目的関数であって、指定
された車両が配送にかかった所要時間（拘束時間）の標
準偏差である。 コスト関数は、重要度に応じて重みが
与えられ、複数個のコスト関数が重ねられる場合もあ
る。制約条件としては、たとえば店舗（配送先）に関す
るものと、車両（トラック）に関するものとの２種類が
あり、以下にそれらの例を示す。
【００４１】店舗についての制約条件としては、たとえ
ば軒先条件と到着時間指定条件がある。軒先条件は、各
店舗ごとに設定された車両の停車時間および各店舗ごと
にトン数などで指定された停車可能な車両の上限などが
挙げられる。また、到着時刻指定条件としては、各店舗
ごとに上限時刻と下限時刻で指定される車両の到着時刻
が挙げられる。
ば軒先条件と到着時間指定条件がある。軒先条件は、各
店舗ごとに設定された車両の停車時間および各店舗ごと
にトン数などで指定された停車可能な車両の上限などが
挙げられる。また、到着時刻指定条件としては、各店舗
ごとに上限時刻と下限時刻で指定される車両の到着時刻
が挙げられる。
【００４２】車両についての制約条件は、積載量の上
限、出発地点、出発時刻、終了条件などが挙げられる。
積載量の上限は、各車両ごとに指定されればよい。出発
時点は、たとえば配送センターに固定されればよい。出
発時刻は、各車両ごとに指定されればよい。終了条件と
しては、各車両ごとに指定される配送終了後の帰着地点
などが挙げられる。
限、出発地点、出発時刻、終了条件などが挙げられる。
積載量の上限は、各車両ごとに指定されればよい。出発
時点は、たとえば配送センターに固定されればよい。出
発時刻は、各車両ごとに指定されればよい。終了条件と
しては、各車両ごとに指定される配送終了後の帰着地点
などが挙げられる。
【００４３】次に、エネルギー関数を定義する演算部７
は、第１の決定部３で読出された行列Ｘと第２の決定部
で決定されたコスト関数および制約条件に基づいて、シ
ステムのエネルギー関数Ｅを計算する。ここでエネルギ
ー関数Ｅについて説明する。エネルギー関数Ｅは、第
（２）式に示すように、最小にしたいコスト関数を表わ
したコスト項Ｅcostと、制約条件を表わした制約項Ｅ
cnstとの２種類の項による線形和で表わされる。ここ
で、係数｛ａk ｝（ｋ＝１，２，３），｛ｂk ｝（ｋ＝
１，２，３）は、考慮したいコスト項間や制約項間の重
要度であり、コスト関数および制約条件間の重要度に応
じて予め決定しておくことにする。
は、第１の決定部３で読出された行列Ｘと第２の決定部
で決定されたコスト関数および制約条件に基づいて、シ
ステムのエネルギー関数Ｅを計算する。ここでエネルギ
ー関数Ｅについて説明する。エネルギー関数Ｅは、第
（２）式に示すように、最小にしたいコスト関数を表わ
したコスト項Ｅcostと、制約条件を表わした制約項Ｅ
cnstとの２種類の項による線形和で表わされる。ここ
で、係数｛ａk ｝（ｋ＝１，２，３），｛ｂk ｝（ｋ＝
１，２，３）は、考慮したいコスト項間や制約項間の重
要度であり、コスト関数および制約条件間の重要度に応
じて予め決定しておくことにする。
【００４４】コスト項ＥcostにおけるＥ(1) costは、各
車両に関して出発地点（配送センター）を出発した時刻
から、作業の完了時刻または帰着時刻のいずれかまでの
時間ｔi （拘束時間）を表わす。この拘束時間をすべて
のトラックについて合計して総拘束時間をエネルギーと
みなす。終了条件が自由の場合には、この拘束時間は出
発地点を出発した時刻から最後の配送先における積下ろ
し作業の完了時刻になる。また、終了条件が出発地点で
ある場合には、拘束時間は、出発地点を出発した時刻か
ら出発点への帰着時刻となる。さらに、終了条件がある
店舗である場合には、拘束時間は、出発地点を出発した
時刻から指定された帰着地点への帰着時刻までの時間と
なる。このような３つの場合があり得るが、使用条件に
応じてユーザが自由に選択すればよい。
車両に関して出発地点（配送センター）を出発した時刻
から、作業の完了時刻または帰着時刻のいずれかまでの
時間ｔi （拘束時間）を表わす。この拘束時間をすべて
のトラックについて合計して総拘束時間をエネルギーと
みなす。終了条件が自由の場合には、この拘束時間は出
発地点を出発した時刻から最後の配送先における積下ろ
し作業の完了時刻になる。また、終了条件が出発地点で
ある場合には、拘束時間は、出発地点を出発した時刻か
ら出発点への帰着時刻となる。さらに、終了条件がある
店舗である場合には、拘束時間は、出発地点を出発した
時刻から指定された帰着地点への帰着時刻までの時間と
なる。このような３つの場合があり得るが、使用条件に
応じてユーザが自由に選択すればよい。
【００４５】第２のコスト項であるＥ(2) costは、積下
ろし完了時刻の最も遅い店舗での積下ろし完了時刻とす
る。たとえば、午前零時からの経過時間とすればその時
間の和がエネルギーとみなせる。第３のコスト項である
Ｅ(3) costは、第（３）式に示すように、指定された車
両（ｎ台）における拘束時間ｔi の標準偏差である。
ろし完了時刻の最も遅い店舗での積下ろし完了時刻とす
る。たとえば、午前零時からの経過時間とすればその時
間の和がエネルギーとみなせる。第３のコスト項である
Ｅ(3) costは、第（３）式に示すように、指定された車
両（ｎ台）における拘束時間ｔi の標準偏差である。
【００４６】一方、制約項Ｅcnstの１つであるＥ(1)
cnstは、第（４）式に示すように、配送センターにおけ
る各車両の積載量ｗ(k) i の超過量の総和である。この
総和量としては、たとえばケース数が考えられる。ただ
し、ｋは回転の識別記号であり、ｗ0 i は車両ｉの積載
量の上限を表わしている。
cnstは、第（４）式に示すように、配送センターにおけ
る各車両の積載量ｗ(k) i の超過量の総和である。この
総和量としては、たとえばケース数が考えられる。ただ
し、ｋは回転の識別記号であり、ｗ0 i は車両ｉの積載
量の上限を表わしている。
【００４７】第２の制約項であるＥ(2) cnstは、各配送
先に設定された到着時刻に関する制約条件である。たと
えば配送先ｋの到着時刻をｔk 、到着時刻の制約を下限
ｔl k と上限ｔu k で表わせば、Ｅ(2) cnstは、第
（５）式のように定義される。このようにしておけば、
到着時刻の制約から外れると制約項Ｅ(2) cnstは大きく
なる。
先に設定された到着時刻に関する制約条件である。たと
えば配送先ｋの到着時刻をｔk 、到着時刻の制約を下限
ｔl k と上限ｔu k で表わせば、Ｅ(2) cnstは、第
（５）式のように定義される。このようにしておけば、
到着時刻の制約から外れると制約項Ｅ(2) cnstは大きく
なる。
【００４８】第３の制約項であるＥ(3) cnstは、各配送
先に設定された受入れ車両の重量に関する制約条件であ
る。各車両の重量をｇi 、各配送先ｋで受入れられる車
両の最大重量をＧk 、各配送先ｋに乗り入れられるトラ
ックをｉ（ｋ）で表わすと、制約項Ｅ(3) cnstは、第
（５）式のように定義される。このようにしておけば、
条件から外れると制約項Ｅ(3) cnstは、増大することに
なる。
先に設定された受入れ車両の重量に関する制約条件であ
る。各車両の重量をｇi 、各配送先ｋで受入れられる車
両の最大重量をＧk 、各配送先ｋに乗り入れられるトラ
ックをｉ（ｋ）で表わすと、制約項Ｅ(3) cnstは、第
（５）式のように定義される。このようにしておけば、
条件から外れると制約項Ｅ(3) cnstは、増大することに
なる。
【００４９】結局、最小にしたい複数のコスト項と複数
の制約条件は、エネルギー関数の中で線形和の形で表現
されており、予め予定されたコスト項や制約項以外のも
のも新たに追加することが容易にできる。
の制約条件は、エネルギー関数の中で線形和の形で表現
されており、予め予定されたコスト項や制約項以外のも
のも新たに追加することが容易にできる。
【００５０】次に、エネルギー関数を最小化する最小化
部９は、乱数発生部１５、パラメータ格納部１７、試行
変形の禁則条件格納部１９により発生または格納されて
いる値を基に、シミュレーテッドアニーリング法により
ゆっくり温度を下げながらエネルギーの最小状態を探索
する。ここで、シミュレーテッドアニーリング法とは、
あるシステムのエネルギー最小状態を求める１つの手法
である。
部９は、乱数発生部１５、パラメータ格納部１７、試行
変形の禁則条件格納部１９により発生または格納されて
いる値を基に、シミュレーテッドアニーリング法により
ゆっくり温度を下げながらエネルギーの最小状態を探索
する。ここで、シミュレーテッドアニーリング法とは、
あるシステムのエネルギー最小状態を求める１つの手法
である。
【００５１】今、ｘがシステムの状態を表わし、このと
きのシステムのエネルギーがエネルギー関数Ｅ（ｘ）で
定義されたとする。さらに、システムの確率分布が温度
Ｔを有するＧｉｂｂｓ分布（Ｂｏｌｔｚｍａｎｎ分布）
で与えられる熱平衡状態にあるとする。この熱平衡状態
のシステムの温度Ｔを温度スケジュール｛Ｔi ｝（ｉ＝
０，１，…，ｎ）に沿って、熱平衡状態を保ちながらゆ
っくりと下げていく。一般に、メトロポリス法を用いた
シミュレーテッドアニーリング法は、５つのステップで
まとめられている。
きのシステムのエネルギーがエネルギー関数Ｅ（ｘ）で
定義されたとする。さらに、システムの確率分布が温度
Ｔを有するＧｉｂｂｓ分布（Ｂｏｌｔｚｍａｎｎ分布）
で与えられる熱平衡状態にあるとする。この熱平衡状態
のシステムの温度Ｔを温度スケジュール｛Ｔi ｝（ｉ＝
０，１，…，ｎ）に沿って、熱平衡状態を保ちながらゆ
っくりと下げていく。一般に、メトロポリス法を用いた
シミュレーテッドアニーリング法は、５つのステップで
まとめられている。
【００５２】第１のステップは、システムの状態ｘと、
システムの温度Ｔの初期状態を選ぶ（Ｔ＝Ｔ0 ）。第２
のステップは、状態ｘを試行変形させて状態ｘ′を選
ぶ。第３のステップは、仮にΔＥ＝Ｅ（ｘ′）−Ｅ
（ｘ）＜０のときは、状態ｘ′に遷移させる。その他の
場合は、ｅｘｐ（−ΔＥ／Ｔ）の確率で、状態ｘ′に遷
移させる。第４のステップは、第２のステップと第３の
ステップをシステムが熱平衡状態に達するまで十分繰返
す。第５のステップは、もし、ｉ＝ｎのときには処理を
終了する。その他の場合には、温度Ｔをたとえばｉ→ｉ
＋１，Ｔ＝Ｔi のように１段階上げて、第２のステップ
へ戻る。
システムの温度Ｔの初期状態を選ぶ（Ｔ＝Ｔ0 ）。第２
のステップは、状態ｘを試行変形させて状態ｘ′を選
ぶ。第３のステップは、仮にΔＥ＝Ｅ（ｘ′）−Ｅ
（ｘ）＜０のときは、状態ｘ′に遷移させる。その他の
場合は、ｅｘｐ（−ΔＥ／Ｔ）の確率で、状態ｘ′に遷
移させる。第４のステップは、第２のステップと第３の
ステップをシステムが熱平衡状態に達するまで十分繰返
す。第５のステップは、もし、ｉ＝ｎのときには処理を
終了する。その他の場合には、温度Ｔをたとえばｉ→ｉ
＋１，Ｔ＝Ｔi のように１段階上げて、第２のステップ
へ戻る。
【００５３】このようなアニーリング法による過程で出
現した状態の中で、特に制約条件があればその制約条件
がすべて満たされた状態の中で、最もエネルギー値の低
い状態が最適解と判定される。また、上述の第２のステ
ップの試行変形としては、現在の状態ｘの近傍の状態が
選ばれるのが一般的である。
現した状態の中で、特に制約条件があればその制約条件
がすべて満たされた状態の中で、最もエネルギー値の低
い状態が最適解と判定される。また、上述の第２のステ
ップの試行変形としては、現在の状態ｘの近傍の状態が
選ばれるのが一般的である。
【００５４】次に、シミュレーテッドアニーリング法で
必要とされる試行変形について説明する。
必要とされる試行変形について説明する。
【００５５】配送計画案を決定する第１の決定部３で決
定された１つの行列Ｘの要素をランダムに２つ選び、そ
の値を交換することで試行変形が行なわれる。ただし、
すべての車両の出発点は配送センターであると仮定して
いるので、行列Ｘの第１列の値は０に固定する。さら
に、試行変形においては、処理を高速化するために、試
行変形における禁則条件がある。この禁則条件は、試行
変形の禁則条件格納部１９に格納されている。まず、ラ
ンダムに選ばれた２つの行列要素ｘi,j ，ｘi',j ' に対
して、ｘi,j ＝ｘi,j ＝−１またはｘi,j ＝ｘi',j' ＝
０である場合、または、ｉ≠ｉ′でｘi,j ＝０またはｘ
i',j' ＝０である場合には、試行変形をやり直す。なぜ
ならば、前者の場合は、配送順序が全く変化していない
ことが意味されており、後者の場合は、各車両に与えた
最大回転数の条件が変更されてしまうからである。この
ような試行変形が棄却されれば、より探索空間が制限さ
れ、最適な解が高速に得られることになる。
定された１つの行列Ｘの要素をランダムに２つ選び、そ
の値を交換することで試行変形が行なわれる。ただし、
すべての車両の出発点は配送センターであると仮定して
いるので、行列Ｘの第１列の値は０に固定する。さら
に、試行変形においては、処理を高速化するために、試
行変形における禁則条件がある。この禁則条件は、試行
変形の禁則条件格納部１９に格納されている。まず、ラ
ンダムに選ばれた２つの行列要素ｘi,j ，ｘi',j ' に対
して、ｘi,j ＝ｘi,j ＝−１またはｘi,j ＝ｘi',j' ＝
０である場合、または、ｉ≠ｉ′でｘi,j ＝０またはｘ
i',j' ＝０である場合には、試行変形をやり直す。なぜ
ならば、前者の場合は、配送順序が全く変化していない
ことが意味されており、後者の場合は、各車両に与えた
最大回転数の条件が変更されてしまうからである。この
ような試行変形が棄却されれば、より探索空間が制限さ
れ、最適な解が高速に得られることになる。
【００５６】次に、以上のような試行変形の禁則条件が
与えられた試行変形で最もエネルギー値の低い状態が最
適解として判断され、演算結果出力部１０はその結果を
出力する。
与えられた試行変形で最もエネルギー値の低い状態が最
適解として判断され、演算結果出力部１０はその結果を
出力する。
【００５７】図５は、配送センター（Ｎｏ．０）から４
６店舗へ５台のトラックで品物を配送する問題を説明す
るための各配送センターと４６店舗の状態を示した図で
ある。図６から図８は、配送問題を解くうえで必要な入
力データを示した図であり、特に、図６は、配送先の店
舗に関する入力データを示した図であり、図７は、車両
として用いられるトラックに関する入力データを示した
図であり、図８は、パラメータ等の入力データを示した
図である。図９は、最終的な処理結果を示した図であ
る。
６店舗へ５台のトラックで品物を配送する問題を説明す
るための各配送センターと４６店舗の状態を示した図で
ある。図６から図８は、配送問題を解くうえで必要な入
力データを示した図であり、特に、図６は、配送先の店
舗に関する入力データを示した図であり、図７は、車両
として用いられるトラックに関する入力データを示した
図であり、図８は、パラメータ等の入力データを示した
図である。図９は、最終的な処理結果を示した図であ
る。
【００５８】図６において、各店舗での停車時間、乗り
入れ可能なトラックの種類（積載可能トン数）、荷物量
（ケース数）、到着指定時刻の上限および下限が示され
ている。
入れ可能なトラックの種類（積載可能トン数）、荷物量
（ケース数）、到着指定時刻の上限および下限が示され
ている。
【００５９】図７において、各トラックの種類（積載可
能トン数）、積載可能な荷物量（ケース数）、終了条件
（−１：特定の帰着地点なし，０：出発地点に帰着す
る、ｉ：ある店舗ｉを帰着地点とする。この３つのうち
の１つを指定する）、許容される最大回転数、配送地点
を出発する時刻、拘束時間を均等化する場合に対象とな
るトラックを指定するための識別子（１：対象とする、
０：対象しない）が指定されている。この例では、トラ
ックナンバーＮｏ．１，２，３のトラックだけがその拘
束時間を均等化され、Ｎｏ．４，５のトラックは拘束時
間の均等が行なわれない。
能トン数）、積載可能な荷物量（ケース数）、終了条件
（−１：特定の帰着地点なし，０：出発地点に帰着す
る、ｉ：ある店舗ｉを帰着地点とする。この３つのうち
の１つを指定する）、許容される最大回転数、配送地点
を出発する時刻、拘束時間を均等化する場合に対象とな
るトラックを指定するための識別子（１：対象とする、
０：対象しない）が指定されている。この例では、トラ
ックナンバーＮｏ．１，２，３のトラックだけがその拘
束時間を均等化され、Ｎｏ．４，５のトラックは拘束時
間の均等が行なわれない。
【００６０】図８において、コスト項の重み係数
｛ａk ｝（ｋ＝１，２，３）の値、制約条件項の重み係
数｛ｂk ｝（ｋ＝１，２，３）の値、温度スケジュール
｛ｔi ｝、各温度での試行変形の回数が示されている。
各温度での試行変形の回数は、禁則条件に触れないで実
際にシステムの状態が試行変形された回数を表わしてお
り、この回数だけ試行変形が行なわれれば、各温度でシ
ステムは熱平衡状態に達したとみなされて状態の更新が
打ち切られ、温度は下げられる。この例では、各温度で
２００００回の試行変形が行なわれ、また、温度は２
０．０から０．００１までの１３段階の温度ステップで
アニーリングが行なわれている。
｛ａk ｝（ｋ＝１，２，３）の値、制約条件項の重み係
数｛ｂk ｝（ｋ＝１，２，３）の値、温度スケジュール
｛ｔi ｝、各温度での試行変形の回数が示されている。
各温度での試行変形の回数は、禁則条件に触れないで実
際にシステムの状態が試行変形された回数を表わしてお
り、この回数だけ試行変形が行なわれれば、各温度でシ
ステムは熱平衡状態に達したとみなされて状態の更新が
打ち切られ、温度は下げられる。この例では、各温度で
２００００回の試行変形が行なわれ、また、温度は２
０．０から０．００１までの１３段階の温度ステップで
アニーリングが行なわれている。
【００６１】図９において、図６から図８に示した入力
データの下で、得られた結果は、５台のトラックが配送
すべき店舗の割当てと、配送順序、所要時間（分）、各
トラックが積載する総荷物量（ケース数）、エネルギー
関数の各項ごとの値が示されている。Ｅ(k) cnstの値が
すべて０であることから、この解は与えられた制約条件
をすべて満たしていることがわかる。もし、制約条件が
満たされる解が得られなければ、Ｅ(k) cnstの値に応じ
て、｛ｂk ｝の値を増加させて再実行させればよい。
データの下で、得られた結果は、５台のトラックが配送
すべき店舗の割当てと、配送順序、所要時間（分）、各
トラックが積載する総荷物量（ケース数）、エネルギー
関数の各項ごとの値が示されている。Ｅ(k) cnstの値が
すべて０であることから、この解は与えられた制約条件
をすべて満たしていることがわかる。もし、制約条件が
満たされる解が得られなければ、Ｅ(k) cnstの値に応じ
て、｛ｂk ｝の値を増加させて再実行させればよい。
【００６２】このように、軒先条件、到着時刻指定、積
載荷物量の上限などの複雑な制約条件の下で、重み係数
の調整により種々のコスト関数の重要度が考慮されて、
望ましい最適解が探索される。したがって、このような
複雑な制約条件下での種々の目的に応じて、最適な配送
計画案の立案に大きな効果があり、また、これらの制約
条件やコスト関数の変更や追加も前述したとおり容易に
行なわれるので、配送問題に対してかなりの効果が得ら
れる。
載荷物量の上限などの複雑な制約条件の下で、重み係数
の調整により種々のコスト関数の重要度が考慮されて、
望ましい最適解が探索される。したがって、このような
複雑な制約条件下での種々の目的に応じて、最適な配送
計画案の立案に大きな効果があり、また、これらの制約
条件やコスト関数の変更や追加も前述したとおり容易に
行なわれるので、配送問題に対してかなりの効果が得ら
れる。
【００６３】以上のことを簡単に説明すると、まず、配
送問題に対して、着想することの困難な物理学のエネル
ギーという概念が適用されている。配送問題における制
約条件が外れるほどエネルギーが増大し、目的関数とし
て用いるコスト関数が増大するほどエネルギーも増大す
るエネルギー関数が決定されている。そして、制約条件
が満たされ、かつ、コスト関数が最小解として得られれ
ば、エネルギー関数は最適化されたと判断される。この
コスト関数の最小化、言い換えればエネルギー関数の最
小化として、たとえばシミュレーテッドアニーリング法
が用いられれば、目的関数の値が小さい解に重点をおい
て確率的に近似解が得られる。したがって、従来の分岐
限定法のように基本的に可能性のある組合せがすべて数
えられる必要がなく、高速に処理されて、かつ信頼性の
高い最適な配車と配送順序が得られる。
送問題に対して、着想することの困難な物理学のエネル
ギーという概念が適用されている。配送問題における制
約条件が外れるほどエネルギーが増大し、目的関数とし
て用いるコスト関数が増大するほどエネルギーも増大す
るエネルギー関数が決定されている。そして、制約条件
が満たされ、かつ、コスト関数が最小解として得られれ
ば、エネルギー関数は最適化されたと判断される。この
コスト関数の最小化、言い換えればエネルギー関数の最
小化として、たとえばシミュレーテッドアニーリング法
が用いられれば、目的関数の値が小さい解に重点をおい
て確率的に近似解が得られる。したがって、従来の分岐
限定法のように基本的に可能性のある組合せがすべて数
えられる必要がなく、高速に処理されて、かつ信頼性の
高い最適な配車と配送順序が得られる。
【００６４】さらに、配車と配送順序を個別に扱うこと
なく、複数行と列の２次元配列で配車と配送順序を決定
する。２次元配列における各行を各車両に対応させ、各
列を各配送順序に対応させている。決定される配送計画
案は、この２次元配列により簡潔に表現されているの
で、配車と配送順序という２種類の問題を同時に取り扱
うことができ、エネルギーという概念を用いた方法とと
もに、高速に最適な配車と配送順序が得られる。
なく、複数行と列の２次元配列で配車と配送順序を決定
する。２次元配列における各行を各車両に対応させ、各
列を各配送順序に対応させている。決定される配送計画
案は、この２次元配列により簡潔に表現されているの
で、配車と配送順序という２種類の問題を同時に取り扱
うことができ、エネルギーという概念を用いた方法とと
もに、高速に最適な配車と配送順序が得られる。
【００６５】なお、図１に示した配送計画案を決定する
第１の決定部３で用いられる２次元配列は、実施例に示
したもの以外にも考えることができる。たとえば、列の
長さを可変長にして、配送先と回転を表わす記号間にダ
ミー記号が１つだけ挿入された状態を配送計画案を表現
する２次元配列として考えることもできる。ただし、こ
の場合には、配送先と回転を表わす記号間にダミー記号
が１つだけ挿入された状態になるように、毎回、試行変
形による状態更新の後で、ダミー記号を挿入または削除
する処理が必要である。
第１の決定部３で用いられる２次元配列は、実施例に示
したもの以外にも考えることができる。たとえば、列の
長さを可変長にして、配送先と回転を表わす記号間にダ
ミー記号が１つだけ挿入された状態を配送計画案を表現
する２次元配列として考えることもできる。ただし、こ
の場合には、配送先と回転を表わす記号間にダミー記号
が１つだけ挿入された状態になるように、毎回、試行変
形による状態更新の後で、ダミー記号を挿入または削除
する処理が必要である。
【００６６】また、コスト関数と制約条件を決定する第
２の決定部５およびエネルギー関数を定義する演算部７
としては、実施例で示したコスト項や制約項として用い
た関数以外の関数で、コストや制約条件を表現すること
もできる。さらに、コスト項と制約項の線形和以外の関
数をエネルギー関数として用いることも可能である。
２の決定部５およびエネルギー関数を定義する演算部７
としては、実施例で示したコスト項や制約項として用い
た関数以外の関数で、コストや制約条件を表現すること
もできる。さらに、コスト項と制約項の線形和以外の関
数をエネルギー関数として用いることも可能である。
【００６７】さらに、エネルギー関数を最小化する最小
化部９に対しても、シミュレーテッドアニーリング法の
他に、ランダムに状態を変形させてより低い状態を見つ
けて遷移していく、ランダム法（またはモンテカルロ
法）や、変形の範囲を現在の状態の近傍に限定させた反
復改善法なども考えられる。
化部９に対しても、シミュレーテッドアニーリング法の
他に、ランダムに状態を変形させてより低い状態を見つ
けて遷移していく、ランダム法（またはモンテカルロ
法）や、変形の範囲を現在の状態の近傍に限定させた反
復改善法なども考えられる。
【００６８】さらに、実施例として用いる配送手段とし
てはトラックを用いているが、対象とする問題に応じ
て、トラック以外の自動車、船舶、航空機、鉄道、人間
などの各種の配送手段が用いられる場合においても、有
効な効果が得られる。また、配送先も、会社、公共施
設、一般家庭などのように店舗に限定されるものでな
い。
てはトラックを用いているが、対象とする問題に応じ
て、トラック以外の自動車、船舶、航空機、鉄道、人間
などの各種の配送手段が用いられる場合においても、有
効な効果が得られる。また、配送先も、会社、公共施
設、一般家庭などのように店舗に限定されるものでな
い。
【００６９】さらに、荷物の配送だけでなく、荷物を集
荷する問題や、セールスマンや修理サービスマンなどの
訪問スケジュールの計画問題、スクールバスなどの送迎
ルートの計画問題、ゴミ収集車の経路決定問題、道路清
掃車の計画問題など、本実施例で示した配車と配送順序
から構成される配送問題と同一の構造をもつ問題に対し
て本発明は適用される。
荷する問題や、セールスマンや修理サービスマンなどの
訪問スケジュールの計画問題、スクールバスなどの送迎
ルートの計画問題、ゴミ収集車の経路決定問題、道路清
掃車の計画問題など、本実施例で示した配車と配送順序
から構成される配送問題と同一の構造をもつ問題に対し
て本発明は適用される。
【００７０】
【数１】
【００７１】
【発明の効果】請求項１の発明によれば、配送問題をエ
ネルギー関数に帰着させ、そのエネルギー関数を最小化
して最適な配車と配送順序を探索できたので、配送先や
車両等の制約条件が満たされ、かつコストを抑えること
ができて経済的である。
ネルギー関数に帰着させ、そのエネルギー関数を最小化
して最適な配車と配送順序を探索できたので、配送先や
車両等の制約条件が満たされ、かつコストを抑えること
ができて経済的である。
【００７２】請求項２の発明によれば、配送計画案を２
次元配列で表現して配車と配送順序という２種の問題を
同時に解くことができたので、迅速に配送先へ荷物等を
配送できる。
次元配列で表現して配車と配送順序という２種の問題を
同時に解くことができたので、迅速に配送先へ荷物等を
配送できる。
【００７３】請求項３の発明によれば、積載上限量の小
さい車両を２回転以上利用する配送計画案を立案するこ
とができ、より配送先や車両等の制約条件が満たされる
とともに、コストも考慮された最適な配車と配送順序の
解が得られる。
さい車両を２回転以上利用する配送計画案を立案するこ
とができ、より配送先や車両等の制約条件が満たされる
とともに、コストも考慮された最適な配車と配送順序の
解が得られる。
【００７４】請求項４の発明によれば、エネルギー関数
を制約条件を表わす項とコスト関数を表わす項の線形和
として演算するので、制約条件やコスト関数の重要度に
応じてエネルギー関数を演算でき、さらに、新たな制約
条件やコスト関数を追加することも容易に行なわれる。
そのため、たとえば、コンピュータでエネルギー関数が
演算される場合には、そのプログラム等の書き換えが容
易に行なわれ、応用範囲を広げることができる。
を制約条件を表わす項とコスト関数を表わす項の線形和
として演算するので、制約条件やコスト関数の重要度に
応じてエネルギー関数を演算でき、さらに、新たな制約
条件やコスト関数を追加することも容易に行なわれる。
そのため、たとえば、コンピュータでエネルギー関数が
演算される場合には、そのプログラム等の書き換えが容
易に行なわれ、応用範囲を広げることができる。
【００７５】請求項５の発明によれば、エネルギー関数
をシミュレーテッドアニーリング法で最小化し、エネル
ギー関数の値が小さい解に重点をおいて確率的に近似解
を求めることができるので、高速に最適な配車と配送順
序の解が得られる。
をシミュレーテッドアニーリング法で最小化し、エネル
ギー関数の値が小さい解に重点をおいて確率的に近似解
を求めることができるので、高速に最適な配車と配送順
序の解が得られる。
【００７６】請求項６の発明によれば、配送問題をエネ
ルギー関数に帰着させ、そのエネルギー関数を最小化し
て最適な配車と配送順序を探索できたので、配送先や車
両との制約条件が満たされ、かつ、コストを抑えること
ができて経済的である。
ルギー関数に帰着させ、そのエネルギー関数を最小化し
て最適な配車と配送順序を探索できたので、配送先や車
両との制約条件が満たされ、かつ、コストを抑えること
ができて経済的である。
【００７７】請求項７の発明によれば、配送計画案を２
次元配列で表現して配車と配送順序という２種の問題を
同時に解くことができたので、迅速に配送先へ荷物等を
配送できる。
次元配列で表現して配車と配送順序という２種の問題を
同時に解くことができたので、迅速に配送先へ荷物等を
配送できる。
【００７８】請求項８の発明によれば、積載上限量の小
さい車両を２回転以上利用する配送計画案を立案するこ
とができ、より配送先や車両との制約条件が満たされる
とともに、コストを考慮された最適な配車と配送順序の
解が得られる。
さい車両を２回転以上利用する配送計画案を立案するこ
とができ、より配送先や車両との制約条件が満たされる
とともに、コストを考慮された最適な配車と配送順序の
解が得られる。
【００７９】請求項９の発明によれば、エネルギー関数
を制約条件を表わす項とコスト関数を表わす項の線形和
として演算するので、制約条件やコスト関数の重要度に
応じてエネルギー関数を演算でき、さらに、新たな制約
条件やコスト関数を追加することも容易に行なわれる。
そのため、たとえば、コンピュータでエネルギー関数を
演算する場合には、そのプログラム等の書き換えが容易
に行なわれ、応用範囲を広げることができる。
を制約条件を表わす項とコスト関数を表わす項の線形和
として演算するので、制約条件やコスト関数の重要度に
応じてエネルギー関数を演算でき、さらに、新たな制約
条件やコスト関数を追加することも容易に行なわれる。
そのため、たとえば、コンピュータでエネルギー関数を
演算する場合には、そのプログラム等の書き換えが容易
に行なわれ、応用範囲を広げることができる。
【００８０】請求項１０の発明によれば、エネルギー関
数をシミュレーテッドアニーリング法で最小化し、エネ
ルギー関数の値が小さい解に重点をおいて確率的に近似
解を求めることができるので、高速に最適な配車と配送
順序の解が得られる。
数をシミュレーテッドアニーリング法で最小化し、エネ
ルギー関数の値が小さい解に重点をおいて確率的に近似
解を求めることができるので、高速に最適な配車と配送
順序の解が得られる。
【図１】この発明の一実施例による配送問題における最
適な配車と配送順序の探索装置の概略ブロック図であ
る。
適な配車と配送順序の探索装置の概略ブロック図であ
る。
【図２】図１の最小化部の内部構成を示した概略ブロッ
ク図である。
ク図である。
【図３】図１および図２に示した探索装置で最適な配車
と配送順序が探索される過程を示したフロー図である。
と配送順序が探索される過程を示したフロー図である。
【図４】図１の第１の決定部で決定される配送計画案を
２次元配列で表現した状態を示した図であって、その初
期状態を示した図である。
２次元配列で表現した状態を示した図であって、その初
期状態を示した図である。
【図５】配送センターと配送先の店舗の状態を示した図
である。
である。
【図６】配送先の店舗に関する入力データの一例を示し
た図である。
た図である。
【図７】トラックに関する入力データの一例を示した図
である。
である。
【図８】パラメータ等の入力データの一例を示した図で
ある。
ある。
【図９】図６から図８の入力データに基づいて処理され
た処理結果の一例を示した図である。
た処理結果の一例を示した図である。
３ 第１の決定部 ５ 第２の決定部 ７ 演算部 ９ 最小化部
───────────────────────────────────────────────────── フロントページの続き (51)Int.Cl.6 識別記号 庁内整理番号 ＦＩ 技術表示箇所 Ｇ０６Ｆ 17/60 Ｇ０８Ｇ 1/123 Ａ 7740−3Ｈ
Claims (10)
- 【請求項１】 多数の荷物を複数の車両で複数の配送先
に配送する配送問題において、前記多数の荷物が前記各
車両に割り振られる配車と、前記各車両が前記複数の配
送先の中で割り振られた配送先に各荷物を配送する配送
順序とを最適化する配送問題における最適な配車と配送
順序の探索装置であって、 前記配車と前記配送順序が示される配送計画案を決定す
る第１の決定手段、 前記第１の決定手段で決定された配送計画案が満たすべ
き制約条件および前記配送計画案を立案するために最小
化されるべきコスト関数を決定する第２の決定手段、 前記第２の決定手段で決定された制約条件から外れるほ
ど増大し、前記第２の決定手段で決定されたコスト関数
が増大するほど増大するエネルギー関数を演算する演算
手段、および前記演算手段で演算されたエネルギー関数
を最小化する最小化手段を備えた、配送問題における最
適な配車と配送順序の探索装置。 - 【請求項２】 前記第１の決定手段は、前記配送計画案
を複数行と列で表わされる２次元配列で表現し、 前記２次元配列における各行は各車両に対応し、各列は
配送順序に対応し、各配列要素は、出発地点を表わす記
号、各配送先を表わす記号、または列の数を一致させる
ためのダミー記号であることを特徴とする、請求項１記
載の配送問題における最適な配車と配送順序の探索装
置。 - 【請求項３】 前記配送順序は、配送先と他の配送先と
の間に出発地点に戻る場合も含む、請求項２記載の配送
問題における最適な配車と配送順序の探索装置。 - 【請求項４】 前記演算手段で演算されるエネルギー関
数は、前記制約条件を表わす項と前記コスト関数を表わ
す項との線形和として演算されることを特徴とする、請
求項１から３いずれかに記載の配送問題における最適な
配車と配送順序の探索装置。 - 【請求項５】 前記最小化手段は、前記制約条件を表わ
す項と前記コスト関数を表わす項の線形和として演算さ
れたエネルギー関数をシミュレーテッドアニーリング法
を用いて最小化することを特徴とする、請求項４記載の
配送問題における最適な配車と配送順序の探索装置。 - 【請求項６】 多数の荷物を複数の車両で複数の配送先
に配送する配送問題において、前記多数の荷物が前記各
車両に割り振られる配車と、前記各車両が前記複数の配
送先の中で割り振られた配送先に各荷物を配送する配送
順序とを最適化する配送問題における最適な配車と配送
順序の探索方法であって、 前記配車と前記配送順序が示される配送計画案を決定す
る第１のステップ、 前記第１のステップで決定された配送計画案が満たすべ
き制約条件および前記配送計画案を立案するために最小
化されるべきコスト関数を決定する第２のステップ、 前記第２のステップで決定された制約条件から外れるほ
ど増大し、前記第２のステップで決定されたコスト関数
が増大するほど増大するエネルギー関数を演算する第３
のステップ、および前記第３のステップで演算されたエ
ネルギー関数を最小化してそのときの配送計画案が最適
であると判断する第４のステップを含む、配送問題にお
ける最適な配車と配送順序の探索方法。 - 【請求項７】 前記第１のステップで決定される前記配
送計画案は、複数行と列で表わされる２次元配列で表現
され、 前記２次元配列における各行は各車両に対応し、各列は
配送順序に対応し、各配列要素は、出発地点を表わす記
号、各配送先を表わす記号、または列の数を一致させる
ためのダミー記号であることを特徴とする、請求項６記
載の配送問題における最適な配車と配送順序の探索方
法。 - 【請求項８】 前記配送順序は、配送先と他の配送先と
の間に出発地点に戻る場合も含む、請求項７記載の配送
問題における最適な配車と配送順序の探索方法。 - 【請求項９】 前記第３のステップで演算されるエネル
ギー関数は、前記制約条件を表わす項と前記コスト関数
を表わす項との線形和として演算されることを特徴とす
る、請求項６から８いずれかに記載の配送問題における
最適な配車と配送順序の探索方法。 - 【請求項１０】 前記第４のステップは、前記第３のス
テップで演算されたエネルギー関数をシミュレーテッド
アニーリング法を用いて最小化するステップを含む、請
求項９記載の配送問題における最適な配車と配送順序の
探索方法。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP31974393A JP2816802B2 (ja) | 1993-12-20 | 1993-12-20 | 配送問題における最適な配車と配送順序の探索装置および探索方法 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP31974393A JP2816802B2 (ja) | 1993-12-20 | 1993-12-20 | 配送問題における最適な配車と配送順序の探索装置および探索方法 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPH07175504A true JPH07175504A (ja) | 1995-07-14 |
| JP2816802B2 JP2816802B2 (ja) | 1998-10-27 |
Family
ID=18113679
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP31974393A Expired - Lifetime JP2816802B2 (ja) | 1993-12-20 | 1993-12-20 | 配送問題における最適な配車と配送順序の探索装置および探索方法 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JP2816802B2 (ja) |
Cited By (17)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH0883044A (ja) * | 1994-09-14 | 1996-03-26 | Hitachi Ltd | シミュレーション装置 |
| JPH103492A (ja) * | 1996-03-23 | 1998-01-06 | Stc Internatl Computers Ltd | 約束予約及びスケジューリング装置 |
| JP2001188984A (ja) * | 1999-12-28 | 2001-07-10 | Hitachi Software Eng Co Ltd | 最適配送計画立案方法およびシステム |
| JP2004362070A (ja) * | 2003-06-02 | 2004-12-24 | Idemitsu Kosan Co Ltd | コージェネレーショングリッド燃料自動発注・配送システム |
| JP2010269867A (ja) * | 2009-05-19 | 2010-12-02 | Hitachi Ltd | 輸送計画立案支援システム及び輸送計画立案支援方法 |
| JP2016505927A (ja) * | 2012-11-25 | 2016-02-25 | エネヴォ オーユーＥｎｅｖｏ Ｏｙ | スマート廃棄物収集システム及び方法 |
| WO2017187645A1 (ja) * | 2016-04-28 | 2017-11-02 | 富士通株式会社 | 部材供給方法、部材供給プログラムおよび部材供給システム |
| JP2019016129A (ja) * | 2017-07-06 | 2019-01-31 | 富士通株式会社 | 最適化装置及び最適化装置の制御方法 |
| JP2020194273A (ja) * | 2019-05-27 | 2020-12-03 | 富士通株式会社 | 最適化装置、最適化方法及び最適化プログラム |
| CN113222515A (zh) * | 2021-05-27 | 2021-08-06 | 咪咕文化科技有限公司 | 一种运单分配方法、装置、电子设备和存储介质 |
| EP3862936A1 (en) | 2020-02-05 | 2021-08-11 | Fujitsu Limited | Information processing apparatus, recording medium, information processing method, and information processing system |
| JP2021125178A (ja) * | 2020-02-10 | 2021-08-30 | 富士通株式会社 | 最適化装置、最適化装置の制御方法及び最適化装置の制御プログラム |
| CN113379097A (zh) * | 2020-03-10 | 2021-09-10 | 富士通株式会社 | 信息处理设备、路线生成方法和路线生成程序 |
| CN114186843A (zh) * | 2021-12-09 | 2022-03-15 | 北京京东振世信息技术有限公司 | 确定运单配载的方法、装置、设备及存储介质 |
| CN114930364A (zh) * | 2020-01-15 | 2022-08-19 | 杰富意钢铁株式会社 | 配送计划创建方法、操作方法以及配送计划创建装置 |
| CN115708139A (zh) * | 2021-08-19 | 2023-02-21 | 株式会社电装 | 用于创建车辆调度计划的系统和储存介质 |
| CN116245449A (zh) * | 2023-05-06 | 2023-06-09 | 北京邮电大学 | 低碳物流配送方法、装置及设备 |
Citations (5)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH01231200A (ja) * | 1988-03-11 | 1989-09-14 | Hitachi Ltd | 配車計画方法 |
| JPH03121600A (ja) * | 1989-10-04 | 1991-05-23 | O G Joho Syst Kk | 地理上の最適経路の決定方法 |
| JPH05189451A (ja) * | 1992-01-16 | 1993-07-30 | Nec Corp | 配送計画立案装置 |
| JPH05246193A (ja) * | 1992-03-06 | 1993-09-24 | Tsubakimoto Chain Co | 図形描画装置 |
| JPH05328614A (ja) * | 1992-05-25 | 1993-12-10 | Fuji Electric Co Ltd | 並列プロセッサを用いた経済負荷配分方法 |
-
1993
- 1993-12-20 JP JP31974393A patent/JP2816802B2/ja not_active Expired - Lifetime
Patent Citations (5)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH01231200A (ja) * | 1988-03-11 | 1989-09-14 | Hitachi Ltd | 配車計画方法 |
| JPH03121600A (ja) * | 1989-10-04 | 1991-05-23 | O G Joho Syst Kk | 地理上の最適経路の決定方法 |
| JPH05189451A (ja) * | 1992-01-16 | 1993-07-30 | Nec Corp | 配送計画立案装置 |
| JPH05246193A (ja) * | 1992-03-06 | 1993-09-24 | Tsubakimoto Chain Co | 図形描画装置 |
| JPH05328614A (ja) * | 1992-05-25 | 1993-12-10 | Fuji Electric Co Ltd | 並列プロセッサを用いた経済負荷配分方法 |
Cited By (23)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH0883044A (ja) * | 1994-09-14 | 1996-03-26 | Hitachi Ltd | シミュレーション装置 |
| JPH103492A (ja) * | 1996-03-23 | 1998-01-06 | Stc Internatl Computers Ltd | 約束予約及びスケジューリング装置 |
| JP2001188984A (ja) * | 1999-12-28 | 2001-07-10 | Hitachi Software Eng Co Ltd | 最適配送計画立案方法およびシステム |
| JP2004362070A (ja) * | 2003-06-02 | 2004-12-24 | Idemitsu Kosan Co Ltd | コージェネレーショングリッド燃料自動発注・配送システム |
| JP2010269867A (ja) * | 2009-05-19 | 2010-12-02 | Hitachi Ltd | 輸送計画立案支援システム及び輸送計画立案支援方法 |
| JP2016505927A (ja) * | 2012-11-25 | 2016-02-25 | エネヴォ オーユーＥｎｅｖｏ Ｏｙ | スマート廃棄物収集システム及び方法 |
| US10332197B2 (en) | 2012-11-25 | 2019-06-25 | Enevo Oy | Optimal waste collection routing using smart waste containers and smart waste collection vehicles |
| WO2017187645A1 (ja) * | 2016-04-28 | 2017-11-02 | 富士通株式会社 | 部材供給方法、部材供給プログラムおよび部材供給システム |
| JPWO2017187645A1 (ja) * | 2016-04-28 | 2018-11-22 | 富士通株式会社 | 部材供給方法、部材供給プログラムおよび部材供給システム |
| JP2019016129A (ja) * | 2017-07-06 | 2019-01-31 | 富士通株式会社 | 最適化装置及び最適化装置の制御方法 |
| JP2020194273A (ja) * | 2019-05-27 | 2020-12-03 | 富士通株式会社 | 最適化装置、最適化方法及び最適化プログラム |
| CN114930364A (zh) * | 2020-01-15 | 2022-08-19 | 杰富意钢铁株式会社 | 配送计划创建方法、操作方法以及配送计划创建装置 |
| EP3862936A1 (en) | 2020-02-05 | 2021-08-11 | Fujitsu Limited | Information processing apparatus, recording medium, information processing method, and information processing system |
| CN113298284A (zh) * | 2020-02-05 | 2021-08-24 | 富士通株式会社 | 信息处理设备、记录介质、信息处理方法和信息处理系统 |
| JP2021124978A (ja) * | 2020-02-05 | 2021-08-30 | 富士通株式会社 | 情報処理装置、プログラム、情報処理方法および情報処理システム |
| JP2021125178A (ja) * | 2020-02-10 | 2021-08-30 | 富士通株式会社 | 最適化装置、最適化装置の制御方法及び最適化装置の制御プログラム |
| CN113379097A (zh) * | 2020-03-10 | 2021-09-10 | 富士通株式会社 | 信息处理设备、路线生成方法和路线生成程序 |
| CN113222515A (zh) * | 2021-05-27 | 2021-08-06 | 咪咕文化科技有限公司 | 一种运单分配方法、装置、电子设备和存储介质 |
| CN115708139A (zh) * | 2021-08-19 | 2023-02-21 | 株式会社电装 | 用于创建车辆调度计划的系统和储存介质 |
| JP2023028550A (ja) * | 2021-08-19 | 2023-03-03 | 株式会社デンソー | 配車計画作成システム |
| US12510369B2 (en) | 2021-08-19 | 2025-12-30 | Denso Corporation | System and program product for creating vehicle dispatch plan |
| CN114186843A (zh) * | 2021-12-09 | 2022-03-15 | 北京京东振世信息技术有限公司 | 确定运单配载的方法、装置、设备及存储介质 |
| CN116245449A (zh) * | 2023-05-06 | 2023-06-09 | 北京邮电大学 | 低碳物流配送方法、装置及设备 |
Also Published As
| Publication number | Publication date |
|---|---|
| JP2816802B2 (ja) | 1998-10-27 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JP2816802B2 (ja) | 配送問題における最適な配車と配送順序の探索装置および探索方法 | |
| TWI792873B (zh) | 用於最佳化包裹之分類及載入的電腦實施系統及電腦實施方法 | |
| Agrawal et al. | A genetic algorithm model for optimizing vehicle routing problems with perishable products under time-window and quality requirements | |
| Matusiak et al. | Utilizing individual picker skills to improve order batching in a warehouse | |
| Zhang et al. | An integrated strategy for a production planning and warehouse layout problem: Modeling and solution approaches | |
| Moons et al. | The value of integrating order picking and vehicle routing decisions in a B2C e-commerce environment | |
| JP2000036093A (ja) | 配車装置 | |
| Schubert et al. | Integrated order picking and vehicle routing with due dates | |
| Janinhoff et al. | Multitrip vehicle routing with delivery options: A data-driven application to the parcel industry | |
| JP7175839B2 (ja) | 輸送計画装置、輸送計画システム、及び輸送計画方法 | |
| CN101894311A (zh) | 运输计划制定支援系统以及运输计划制定支援方法 | |
| Karimi et al. | An integrated production-distribution planning with a routing problem and transportation cost discount in a supply chain | |
| JP2004326711A (ja) | 配車計画立案方法および装置 | |
| Chen et al. | Solving a 3-dimensional vehicle routing problem with delivery options in city logistics using fast-neighborhood based crowding differential evolution algorithm | |
| Karels et al. | A vehicle routing problem with multiple service agreements | |
| JPH01231200A (ja) | 配車計画方法 | |
| Alinaghian et al. | A novel mathematical model for cross dock open-close vehicle routing problem with splitting | |
| CN115358480A (zh) | 一种基于成本的电力物资配送路径规划方法、装置、设备及存储介质 | |
| Ahmed et al. | Reorganization of inventory to improve kitting efficiency and maximize space utilization | |
| JP4285232B2 (ja) | 物流費予測装置と予測方法とそのためのプログラム | |
| JP6806885B2 (ja) | 物流支援システム及び物流支援方法 | |
| JPH07219920A (ja) | 最適化問題解決処理方法および装置 | |
| Ho et al. | A comparison of two zone-visitation sequencing strategies in a distribution centre | |
| JPH07230443A (ja) | 染色体の割当て方法および装置 | |
| Al Theeb et al. | Optimization of the heterogeneous vehicle routing problem with cross docking logistic system |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| A01 | Written decision to grant a patent or to grant a registration (utility model) |
Free format text: JAPANESE INTERMEDIATE CODE: A01 Effective date: 19980714 |