配送計画システム 輸送計画問題 工場 工場 工場 物流拠点 物流拠点 物流拠点 生産計画 販売店 顧客 需要地 需要地 需要地 在庫管理 オーダー 輸送需要 品種・量 納期制約 オーダー 在庫制約 月間・週間計画 輸送計画 デポを中心とした 区域配送 配送計画 幹線輸送計画 拠点間の 長距離輸送 積載計画 配車計画 車両手配 輸送需要の 車両への割付け 運行計画 作業計画 荷積・荷卸作業 容量・時刻制約 輸送ルート 車両運用 幹線輸送計画 輸送計画問題（幹線輸送計画） 知識ベース ルート候補の作成 輸送ルート計画 輸送ルート決定 ルート候補の作成 運用ルート計画 運用ルート決定 割当可能性判定 シミュレータ 集合分割モデル マッチングモデル 知識ベース 集合分割モデル 最小費用循環流 知識ベース 車両割当計画 最適割当 割当問題 集合被覆問題 最小費用循環流モデル 列車１ 列車２ 列車３ 列車４ 列車５ 駅B 駅C 駅A 駅B 駅B 駅C 駅B 駅B 駅A 駅C 問題の規模 集配地の数 25 デマンドの数 383 計画期間 ４日 トラックの台数 400 トラックの種類 5 輸送ルート候補の作成 デマンドの数 383 トリップの数 796 ルート候補の数 6,558 計算時間 3.4分 輸送ルート決定 コストの初期値 1,010,649 ルートの数 583 解のコスト 659,043 計算時間 2.75分 ＜ビークルルーティング問題＞ デポから複数の顧客へのコスト最小な 配送経路を求める問題 車両３ Ｃ Ｂ 顧客 Ｄ Ａ Ｅ Ｊ デポ Ｆ 車両１ Ｇ Ｈ Ｉ 車両２ 石田啓一：物流システム構築のための技法，計測と制御ーミ ニ特集物を動かす・貯える・仕分ける，vol.37,No.3(1998) ＜セービング法＞ ＜スウィープ法＞ 解の探索－列挙木－ １ 解法：分枝限定法による解空間の探索 天目健二・山口盛兄：道路網の動的経路誘導システム，計測と制御ーミニ特集 都市道路網の交通流制御システム，vol.41.No.3(2002) 組合せ問題の難しさ －ハミルトン経路問題－ セールスマンが全ての都市を1回ずつ通過して、出発 地に戻って来る経路で最も短いものを捜す問題です。 ・６都市ならば、 ５!/２= ５×４×３×２ / ２ =６０通り ・ｎ都市ならば、 （ｎ－１）！/２通り 近年, 新聞や科学雑誌でも取り上げられて有名になりま した。 TSP（Traveling Salesman Problem） 原型：ハミルトン経路問題 東京大学工学部計数工学科 松井知己氏資料から ＜計算時間の実感＞ 例えば、1MIPS (mega instructions per second)の計算機では、1秒間に 100万回の計算ができます。つまり、1step に 10-6秒かかりますが、ｎが大 きくなると、以下のような計算時間になり、ｎ！通りの大きさが実感できて、 全てのパターンを計算し、その結果を元に最も良い解を導出することが不 可能であることが分かります。 ｎ 10 100 1,000 10,000 ｎ １０－５秒 １０－４秒 ０．００１秒 ０．０１秒 ｎ２ １０－４秒 ０．０１秒 １秒 １００秒 ｎ３ ０．００１秒 １秒 １６．６分 ２７７時間 ２ｎ ０．００１秒 １０１４世紀 １０２８４世紀 ？∞？ ｎ！ ０．０３６秒 １０１４１世紀 １０２５５１世紀 ？∞？ ＜クラスPに属する問題の例＞ ・線形計画問題 ・ネットワーク計画問題 ＜NP完全問題の例＞ ・充足可能性問題 ・整数計画問題 ・ナップサック問題 ・巡回セールスマン問題 ・スケジューリング問題 ・集合分割問題 ＜大規模組合せ最適化問題の解法＞ 大規模システムの計画運用 産業社会システム 生産スケジューリング VLSI設計 列車ダイヤ、乗務員運用 組合せ最適化問題 人工知能の基本問題 人間の問題解決能力 厳密解法 数理計画法 分枝限定法,分枝カット法 近似解法 ヒューリスティクス エキスパートシステム 1960年代～ 1980年代～ ＮＰ完全性 知識獲得ボトルネック メタ戦略 物理現象、生物機能 ＳＡ，ＧＡ，タブーサーチ ＮＮ，等 1990年代～ 実験的解析 メタヒューリスティクス • アニーリング法、遺伝アルゴリズム、 タブーサーチ等の最適化の新解法。 • メタ（超）とついているのは、解くべき問題 に対するヒューリスティクス（発見的知識） をいかにアルゴリズムにまとめあげるか論 じているから。 メタヒューリスティクスの方式 ＜山登り法とメタヒューリスティクス＞ 基本的な探索方法は、通常「山登り法」と呼ばれる局所探索法です。 これは、初期解からスタートして、解を徐々に改善していく手法で、局所解に到達したら探索を終了するも のです。 これに対して、局所解から脱出して、さらに最適に近い解を効率良く探索しようとする手法が幾つか提案さ れいます。メタヒューリスティクスあるいは、メタ戦略と呼ばれるもので、遺伝アルゴリズム（ＧＡ法） 、シミュ レーテッド・アニーリング（ＳＡ法）、タブーサーチ（ＴＡ）等があります。 ＜遺伝アルゴリズム（ＧＡ法）＞ 生物の集団が自然淘汰により進化していく過程を模したものです。 複数の解（集団）を用意し、それらを組み合わせることにより、より良い解（進化）を求めていこうという手法 です。 ＜シミュレーテッド・アニーリング（ＳＡ法）＞ 焼きなまし法と呼ばれもので、温度を下げることにより、より強固な固体結晶を得ようとする物理過程（熱 力学）をもしたものです。例えば、刀鍛冶が鉄を熱しては水で冷却する作業を繰り返す（焼きなまし）ことによ り、切れ味の良い（強固な）刀を作る過程です。 最も強固な状態（最適解）に至るには、単に一度に冷却したのでは駄目で、何度も加熱（解の改悪）と冷却 （解の改善）を繰り返す必要があります。 ＜タブーサーチ（ＴＡ）＞ 人間には記憶があり、学習により最適解にたどり着くことができます。山登りに例えれば、一度通過した頂 上（局所解）に逆戻りすることを禁じる（ターブーとする）ことにより、効率的に真の最高峰に到達できます。 局所探索法 （山登り法） 現在の解 近傍探索 解の評価 改善？ 近傍での解の修正 評価関数の値の計算 Ｎ 全近傍 を探索？ Ｙ 解の更新 評 価 関 数 の 値 Ｎ ◎初期解 ○ ○ ● 局所解 Ｙ 終了 解空間 山登り法（局所探索法） ＜ＳＡ法＞ 高温 近傍探索 評 価 関 数 の 値 解の評価 改善？ Ｙ Ｎ 評価値に対応 した確率で ◎初期解 低温 ○ ○ ○ ○ ○ ○ ● 局所解 ● 解の更新 局所解 解空間 シミュレーテッド・アニーリング法（ＳＡ法） 評 価 関 数 の 値 最適解 解空間 遺伝アルゴリズム（ＧＡ法） ＜タブー探索法＞ 局所探索 局所解を一定期間 探索禁止とする （タブーリスト） ◎初期解 評 価 関 数 の 値 局所解 タブーリスト 最適解 解空間 タブー探索法（ＴＳ法） ） 新物流情報システムの構成 ＜ 物流センター ＞ 運行管理端末 配車計画端末 実績管理端末 通信 サーバ ＤＢ サーバ ＜車両＞ カーＰＣ ＰＣナビ ＧＰＳ 新物流情報システムの特徴 【物流センタ】 ・DSRCの活用 ・最新移動体通信の活用 【管理トラック】 計算結果（配送計画） 計画 物流 D/B 配車効率 車両ｵﾝﾗｲﾝ 化支援 運行管理 システム ｼｽﾃﾑ ・運行計画ﾃﾞｰﾀ ・配送計画ﾃﾞｰﾀ 運行実績ﾃﾞｰﾀ のﾌｨｰﾄﾞﾊﾞｯｸ ・配車計画の最適化 ・積載効率の向上 ・車両数削減、等 ・位置・動態情報 ・配送情報 実績 物流 D/B ・運行実績ﾃﾞｰﾀ ・配送実績ﾃﾞｰﾀ ・貨物の追跡 ・業務効率化 ・勤怠管理、等 ・配送計画・実績の表示 ・配送ルートナビゲーション ・配送先情報の提供 ・センタとのコミュニケーション ＜背景＞ ・企業活動全体の効率化、低コスト化 ・物流における輸送の高度化、コスト削減 ・GPS、地図情報システム、ナビーゲーションシステム ＜目的＞ 物流における種々の輸送システムに対応可能な 実用的な配送計画システムの開発 ＜ビークルルーティング問題＞ デポから複数の顧客へのコスト最小な 配送経路を求める問題 車両３ Ｃ Ｂ 顧客 Ｄ Ａ Ｅ Ｊ デポ Ｆ 車両１ Ｇ Ｈ Ｉ 車両２ ＜物流における配送計画＞ 種々の複雑な条件を考慮する必要がある 例） ・車両は均質ではなく、積載量や車種も異なる ・運転手の労働条件による稼動時間や休憩時間の設定 ・顧客による配送時間の指定や、配送可能な車種の制約 ・車両の回転使用 ・車両の運行形態 ・複数のデポや集荷・配送が混在 ＜配送計画作成方式＞ 初期解作成 最適解探索 ヒューリスティック手法 メタヒューリスティクス ・タブーサーチ 評 価 関 数 の 値 初期解 局所解 タブーリスト 最適解 解空間 タブーサーチによる解空間の探索 ＜初期解作成の処理フロー ＞ 車両を選択 未割当配 送先有り Ｙ 割当可能 配送先有り Ｙ 最も近い配送 先を割当てる Ｎ Ｎ 終了 車両３ Ｃ 配送先 Ｂ Ｄ Ａ Ｅ Ｊ 配送センタ Ｆ 車両１ Ｇ Ｈ 初期解の例 Ｉ 車両２ ＜最適解探索処理の構成＞ 最適解探索処理 修正案作成 修正案評価 探索戦略 更新判定 配送計画更新 配送計画 記憶 ａ）配送先の移動（削除・追加） ｂ）配送先の交換 車両割当変更操作 Ａ Ｂ ＜配送先の削除＞ 元の配送順： Ｃ Ａ→Ｂ→Ｃ→Ｄ→Ｅ→Ｆ 配送先Ｃを削除 Ｄ 新たな配送順： Ａ→Ｂ→Ｄ→Ｅ→Ｆ （他は元の配送順） Ｆ Ｅ 削除 Ｄ ＜配送先の追加＞ 元の配送順： Ａ→Ｂ→Ｄ→Ｅ→Ｆ Ｆ Ｅ Ａ Ｂ 追加 配送先Ｈを追加 新たな配送順： Ａ→Ｂ→Ｄ→Ｅ→Ｈ→Ｆ Ｄ （最適な位置に追加） Ａ Ｂ Ｆ Ｅ Ｈ 配送順序の決定（簡易法） ＜配送順序の最適化＞ ２－ｏｐｔ法 ａ ｃ ａ ｃ ｄ ｂ ｄ ｂ ０ ｈ ｉ ａ ｂ ｅ ｆｇ ｃ ｄ ｊ ｋ ０ ０：配送センタ ０ ｈ ｉ ａ ｃ ｇ ｆｅ ｂ ｄ ｊ ｋ ０ 配送順序の決定（２－ｏｐｔ法） ＜ タブーサーチの処理フロー ＞ Ｙ これまでの最良の配送 計画よりも改善される Ｎ 変更操作がタブーリス Ｙ トに登録されている Ｎ 更新する Ｙ 現在の配送計画よ りも改善される 更新しない Ｎ Ｙ 変更操作をタブー リストに登録する 現在の配送計画に対す Ｎ る修正案の中で最善の ものである マスタ整備 マスタ情報 ファイル 手入力 マスタデータ 他システム 発着地間 所要時間 配車計画サブシステム 自動配車 計画作成 配車計画 変更 配車計画（仮） 配車計画 配車計画 出力 配送計画 地図データ 配送伝票登録 実績データ 伝票ファイル 伝票データ 手入力 計画に沿った運行の監視 および 運行実績の収集 運行監視サブシステム 運行実績サブシステム ＜標準的な配送計画問題＞ customer garage depot garage customer ＜複数デポ配送計画問題＞ customer garage depot garage depot depot customer ＜集配送計画問題＞ customer ：delivery ：pick up garage depot garage customer
© Copyright 2024 ExpyDoc
