配送計画システム. 輸送計画問題 生産計画在庫管理オーダー 輸送計画 輸送需要 配送計画 幹線輸送計画 積載計画配車計画 運行計画 作業計画 物流拠点 工場 需要地 物流拠点 工場 販売店 顧客 品種・量 納期制約 オーダー 在庫制約 拠点間の 長距離輸送 月間・週間計画 デポを中心とした 区域配送.

Presentation on theme: "配送計画システム. 輸送計画問題 生産計画在庫管理オーダー 輸送計画 輸送需要 配送計画 幹線輸送計画 積載計画配車計画 運行計画 作業計画 物流拠点 工場 需要地 物流拠点 工場 販売店 顧客 品種・量 納期制約 オーダー 在庫制約 拠点間の 長距離輸送 月間・週間計画 デポを中心とした 区域配送."— Presentation transcript:

1 配送計画システム

2 輸送計画問題 生産計画在庫管理オーダー 輸送計画 輸送需要 配送計画 幹線輸送計画 積載計画配車計画 運行計画 作業計画 物流拠点 工場 需要地 物流拠点 工場 販売店 顧客 品種・量 納期制約 オーダー 在庫制約 拠点間の 長距離輸送 月間・週間計画 デポを中心とした 区域配送 輸送需要の 車両への割付け 車両手配 輸送ルート 車両運用 荷積・荷卸作業 容量・時刻制約

3

4 幹線輸送計画

5 輸送計画問題（幹線輸送計画） 輸送ルート計画 運用ルート計画 車両割当計画 ルート候補の作成 輸送ルート決定 運用ルート決定 ルート候補の作成 割当可能性判定 最適割当 知識ベース シミュレータ 集合分割モデル マッチングモデル 知識ベース 集合分割モデル 最小費用循環流 知識ベース 割当問題

6

7 集合被覆問題

8 列車 １ 列車 ２ 列車 ３ 列車 ４ 列車 ５ 駅B駅B 駅C駅C 駅C駅C 駅A駅A 駅B駅B 駅B駅B 駅B駅B 駅B駅B 駅A駅A 駅C駅C 最小費用循環流モデル

9 5 トラックの種類 400 トラックの台数 ４日計画期間 383 デマンドの数 25 集配地の数 3.4 分計算時間 6,558 ルート候補の数 796 トリップの数 383 デマンドの数 問題の規模 2.75 分計算時間 659,043 解のコスト 583 ルートの数 1,010,649 コストの初期値 輸送ルート候補の作成 輸送ルート決定

10

11

12

13 ＜ビークルルーティング問題 ＞ デポから複数の顧客へのコスト最小 な配送経路を求める問題 顧客 デポ Ａ Ｂ Ｃ Ｄ Ｅ Ｆ Ｇ Ｈ Ｉ Ｊ 車両１ 車両２ 車両３

14 石田啓一：物流システム構築のための技法，計測と制 御ーミニ特集物を動かす・貯える・仕分ける， vol.37,No.3(1998)

15

16 ＜セービング法＞

17 ＜スウィープ法＞

18

19

20

21

22

23 解の探索－列挙木－ 解法：分枝限定法による解空間の探 索 １

24

25

26 天目健二・山口盛兄：道路網の動的経路誘導システム，計測と制御ーミニ 特集都市道路網の交通流制御システム， vol.41.No.3(2002)

27 組合せ問題の難しさ －ハミルトン経路問題－ セールスマンが全ての都市を 1 回ずつ通過して、出 発地に戻って来る経路で最も短いものを捜す問題で す。 セールスマンが全ての都市を 1 回ずつ通過して、出 発地に戻って来る経路で最も短いものを捜す問題で す。・６都市ならば、 ５ !/ ２ = ５ × ４ × ３ × ２ / ２ = ６０通り ５ !/ ２ = ５ × ４ × ３ × ２ / ２ = ６０通り・ｎ都市ならば、 （ｎ－１）！ / ２通り （ｎ－１）！ / ２通り 近年, 新聞や科学雑誌でも取り上げられて有名になり ました。 TSP （ Traveling Salesman Problem ） 原型：ハミルトン経路問題 東京大学工学部計数工学科 松井知己氏資料から

28 例えば、 1MIPS (mega instructions per second) の計算機では、 1 秒 間に 100 万回の計算ができます。つまり、 1step に 10 -6 秒かかります が、ｎが大きくなると、以下のような計算時間になり、ｎ！通りの 大きさが実感できて、全てのパターンを計算し、その結果を元に最 も良い解を導出することが不可能であることが分かります。 ＜計算時間の実感＞

29 ＜クラス P に属する問題の例 ＞ ・線形計画問 題 ・ネットワーク計画問題 ＜ NP 完全問題の例＞ ・充足可能性問題 ・整数計画問 題 ・巡回セールスマン問題 ・ナップサック問題 ・スケジューリング問題 ・集合分割問 題

30 ＜大規模組合せ最適化問題の解法＞

31 メタヒューリスティクス アニーリング法、遺伝アルゴリズム、 タブーサーチ等の最適化の新解法。 メタ（超）とついているのは、解くべ き問題 に対するヒューリスティクス（発見的 知識） をいかにアルゴリズムにまとめあげる か論じているから。

32 メタヒューリスティクスの方式 ＜遺伝アルゴリズム（ＧＡ法）＞ 生物の集団が自然淘汰により進化していく過程を模したものです。 複数の解（集団）を用意し、それらを組み合わせることにより、より良い解（進化）を求めてい こうという手法です。 複数の解（集団）を用意し、それらを組み合わせることにより、より良い解（進化）を求めてい こうという手法です。＜遺伝アルゴリズム（ＧＡ法）＞ 生物の集団が自然淘汰により進化していく過程を模したものです。 ＜シミュレーテッド・アニーリング（ＳＡ法）＞ 焼きなまし法と呼ばれもので、温度を下げることにより、より強固な固体結晶を得ようとする物 理過程（熱力学）をもしたものです。例えば、刀鍛冶が鉄を熱しては水で冷却する作業を繰り返す （焼きなまし）ことにより、切れ味の良い（強固な）刀を作る過程です。 焼きなまし法と呼ばれもので、温度を下げることにより、より強固な固体結晶を得ようとする物 理過程（熱力学）をもしたものです。例えば、刀鍛冶が鉄を熱しては水で冷却する作業を繰り返す （焼きなまし）ことにより、切れ味の良い（強固な）刀を作る過程です。 最も強固な状態（最適解）に至るには、単に一度に冷却したのでは駄目で、何度も加熱（解の改 悪）と冷却（解の改善）を繰り返す必要があります。 最も強固な状態（最適解）に至るには、単に一度に冷却したのでは駄目で、何度も加熱（解の改 悪）と冷却（解の改善）を繰り返す必要があります。＜シミュレーテッド・アニーリング（ＳＡ法）＞ 焼きなまし法と呼ばれもので、温度を下げることにより、より強固な固体結晶を得ようとする物 理過程（熱力学）をもしたものです。例えば、刀鍛冶が鉄を熱しては水で冷却する作業を繰り返す （焼きなまし）ことにより、切れ味の良い（強固な）刀を作る過程です。 焼きなまし法と呼ばれもので、温度を下げることにより、より強固な固体結晶を得ようとする物 理過程（熱力学）をもしたものです。例えば、刀鍛冶が鉄を熱しては水で冷却する作業を繰り返す （焼きなまし）ことにより、切れ味の良い（強固な）刀を作る過程です。 最も強固な状態（最適解）に至るには、単に一度に冷却したのでは駄目で、何度も加熱（解の改 悪）と冷却（解の改善）を繰り返す必要があります。 最も強固な状態（最適解）に至るには、単に一度に冷却したのでは駄目で、何度も加熱（解の改 悪）と冷却（解の改善）を繰り返す必要があります。 ＜タブーサーチ（ＴＡ）＞ 人間には記憶があり、学習により最適解にたどり着くことができます。山登りに例えれば、一度通 過した頂上（局所解）に逆戻りすることを禁じる（ターブーとする）ことにより、効率的に真の最高 峰に到達できます。 人間には記憶があり、学習により最適解にたどり着くことができます。山登りに例えれば、一度通 過した頂上（局所解）に逆戻りすることを禁じる（ターブーとする）ことにより、効率的に真の最高 峰に到達できます。＜タブーサーチ（ＴＡ）＞ ＜山登り法とメタヒューリスティクス＞ 基本的な探索方法は、通常「山登り法」と呼ばれる局所探索法です。 これは、初期解からスタートして、解を徐々に改善していく手法で、局所解に到達したら探索を 終了するものです。 これは、初期解からスタートして、解を徐々に改善していく手法で、局所解に到達したら探索を 終了するものです。 これに対して、局所解から脱出して、さらに最適に近い解を効率良く探索しようとする手法が幾 つか提案されいます。メタヒューリスティクスあるいは、メタ戦略と呼ばれるもので、遺伝アルゴ リズム（ＧＡ法） 、シミュレーテッド・アニーリング（ＳＡ法）、タブーサーチ（ＴＡ）等があり ます。 これに対して、局所解から脱出して、さらに最適に近い解を効率良く探索しようとする手法が幾 つか提案されいます。メタヒューリスティクスあるいは、メタ戦略と呼ばれるもので、遺伝アルゴ リズム（ＧＡ法） 、シミュレーテッド・アニーリング（ＳＡ法）、タブーサーチ（ＴＡ）等があり ます。＜山登り法とメタヒューリスティクス＞ 基本的な探索方法は、通常「山登り法」と呼ばれる局所探索法です。 これは、初期解からスタートして、解を徐々に改善していく手法で、局所解に到達したら探索を 終了するものです。 これは、初期解からスタートして、解を徐々に改善していく手法で、局所解に到達したら探索を 終了するものです。 これに対して、局所解から脱出して、さらに最適に近い解を効率良く探索しようとする手法が幾 つか提案されいます。メタヒューリスティクスあるいは、メタ戦略と呼ばれるもので、遺伝アルゴ リズム（ＧＡ法） 、シミュレーテッド・アニーリング（ＳＡ法）、タブーサーチ（ＴＡ）等があり ます。 これに対して、局所解から脱出して、さらに最適に近い解を効率良く探索しようとする手法が幾 つか提案されいます。メタヒューリスティクスあるいは、メタ戦略と呼ばれるもので、遺伝アルゴ リズム（ＧＡ法） 、シミュレーテッド・アニーリング（ＳＡ法）、タブーサーチ（ＴＡ）等があり ます。

33 局所探索法 （山登り法） 現在の解 全近傍を探索？ 改善？ 解の更新 Ｎ Ｙ 近傍探索 解の評価 Ｎ 近傍での解の修正 評価関数の値の計算 終了 Ｙ ◎初期解 ○ ○ ● 局所解 解空間 山登り法（局所探索法）

34 改善？ 解の更新 Ｎ Ｙ 近傍探索 解の評価 ○ ○ ● 局所解 解空間 評価値に対応 した確率で ＜ＳＡ法＞ ○ ○ ○ ○ ● 局所解 高温 低温 シミュレーテッド・アニーリング法（ＳＡ法）

35 解空間 評 価 関 数 の 値 最適解 遺伝アルゴリズム（ＧＡ法）

36 タブー探索法（ＴＳ法） ） 局所探索 局所解を一定期間探索禁止とする（タブーリスト） ＜タブー探索法＞ ◎初期解 解空間 局所解 タブーリスト 最適解

37 ２３９２都市の巡回セールスマン問題

38

39 新物流情報システムの構成 カーＰＣ 通信 サーバ ＤＢ サーバ 運行管理端末実績管理端末 配車計画端末 ＜ 物流センター ＞ ＜車両＞ ＧＰＳＰＣナビ

40 新物流情報システムの特徴

41 ＜背景＞ ＜目的＞ ・企業活動全体の効率化、低コスト化 ・物流における輸送の高度化、コスト削減 ・ GPS 、地図情報システム、ナビーゲーションシ ステム 物流における種々の輸送システムに対応可 能な実用的な配送計画システムの開発

42 ＜ビークルルーティング問題 ＞ デポから複数の顧客へのコスト最小 な配送経路を求める問題 顧客 デポ Ａ Ｂ Ｃ Ｄ Ｅ Ｆ Ｇ Ｈ Ｉ Ｊ 車両１ 車両２ 車両３

43 ＜物流における配送計画＞ 種々の複雑な条件を考慮する必要があ る ・車両は均質ではなく、積載量や車種も異なる ・運転手の労働条件による稼動時間や休憩時間の設定 ・顧客による配送時間の指定や、配送可能な車種の制 約 ・車両の回転使用 ・車両の運行形態 ・複数のデポや集荷・配送が混在 例）

44 初期解作成 最適解探索 ヒューリスティック手 法 メタヒューリスティク ス ・タブーサーチ ＜配送計画作成方式＞

45 評 価 関 数 の 値 解空間 初期解 局所解 タブーリスト 最適解 タブーサーチによる解空間の探索

46 車両を選択 未割当配 送先有り 割当可能 配送先有り 最も近い配送 先を割当てる Ｙ Ｙ 終了 Ｎ Ｎ ＜初期解作成の処理フロー ＞

47 配送先 配送センタ Ａ Ｂ Ｃ Ｄ Ｅ Ｆ Ｇ Ｈ Ｉ Ｊ 車両１ 車両２ 車両３ 初期解の例

48 最適解探索処理 修正案作成 修正案評価 配送計画更新 配送計画 記憶 更新判定 探索戦略 ＜最適解探索処理の構成＞

49 ａ）配送先の移動（削除・追加 ） ｂ）配送先の交換 車両割当変更操作

50 ＜配送先の削除＞ 元の配送順： Ａ→Ｂ→Ｃ→Ｄ→Ｅ→ＦＡ→Ｂ→Ｃ→Ｄ→Ｅ→Ｆ 配送先Ｃを削除 Ａ→Ｂ→Ｄ→Ｅ→ＦＡ→Ｂ→Ｄ→Ｅ→Ｆ ＜配送先の追加＞ 元の配送順：Ａ→Ｂ→Ｄ→Ｅ→ＦＡ→Ｂ→Ｄ→Ｅ→Ｆ 配送先Ｈを追加 Ａ Ｂ Ｃ Ｄ Ｅ Ｆ Ａ Ｂ Ｄ Ｅ Ｆ Ａ Ｂ Ｄ Ｅ Ｆ Ｈ 新たな配送順：Ａ→Ｂ→Ｄ→Ｅ→Ｈ→ＦＡ→Ｂ→Ｄ→Ｅ→Ｈ→Ｆ （最適な位置に追加） （他は元の配送順） 削除 追加 新たな配送順： 配送順序の決定（簡易法）

51 配送順序の決定（２－ｏｐｔ法） ａ ｂ ｃ ｄ ａ ｂ ｃ ｄ ２－ｏｐｔ法 ＜配送順序の最適化＞ ０ ｈ ｉ ａ ｂ ｅ ｆｇ ｃ ｄ ｊ ｋ ０ ０ ｈ ｉ ａ ｃ ｇ ｆｅ ｂ ｄ ｊ ｋ ０ ０：配送センタ

52 Ｙ Ｎ Ｙ Ｎ Ｙ Ｎ Ｙ Ｎ これまでの最良の配送 計画よりも改善される 変更操作がタブーリス トに登録されている 更新する 更新しない 現在の配送計画よ りも改善される 現在の配送計画に対す る修正案の中で最善の ものである 変更操作をタブー リストに登録する ＜ タブーサーチの処理フロー ＞

53 配送伝票登録 マスタ整備 自動配車 計画作成 配車計画（仮） 配車計画 変更 配車計画地図データマスタデータ伝票データ 他システム 配車計画サブシステム 運行監視サブシステム運行実績サブシステム 実績データ 計画に沿った運行の監視 および 運行実績の収集 配車計画 出力 配送計画 手入力 伝票ファイル マスタ情報 ファイル 発着地間 所要時間

54

55

56 ＜標準的な配送計画問題＞ depot customer garage customer

57 ＜複数デポ配送計画問題＞ depot customer garage customer depot

58 ＜集配送計画問題＞ depot customer garage customer ： delivery ： pick up