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

Slides:



Advertisements
Similar presentations
1 プリミティブ Web サービスの 入出力データに関する一考察 2005 年 3 月 21 日 松江工業高等専門学校 情報工学科 奈良先端科学技術大学院大学 情報科学研究科 越田高志 電子情報通信学会 2005年総合 大会.
Advertisements

授業展開#12 コンピュータの扱いにくい問 題. 扱いにくい問題  処理時間がかかる。  メモリを大量に必要とする。  プログラムの優劣、アルゴリズムの優劣 を比較するためには、標準的なコン ピュータで比較する必要がある。  処理時間を計るのに、コンピュータのモ デルとして、チューリングマシンを考え、
多目的GAに対する パレート最適個体の分布制御 九州大学大学院工学府知能機械システム専攻徳井 宏司.
©2008 Ikuo Tahara探索 状態空間と探索木 基本的な探索アルゴリズム 横形探索と縦形探索 評価関数を利用した探索アルゴリズム 分岐限定法 山登り法 最良優先探索 A ( A* )アルゴリズム.
情報基盤アルゴリズムとして のメタヒューリスティクスの 研究 茨木俊秀、巳波弘佳、藤原洋志、 千葉英史、関口良行(関西学院大 学)、 藤重悟(京都大学)、 柳浦睦憲(名古屋大学)、 野々部宏司(法政大学)、 梅谷俊治(電気通信大学)
ACM/ICPC と アルゴリズム 「実践的プログラミング」 稲葉 一浩. 自己紹介 ﻪ 理Ⅰ → 理学部情報科学科 → 情報理工学系研究科コンピュータ科学専攻 ﻩ 博士課程1年 ﻩXML を扱う専用言語の研究など ﻪ 個人的には ﻩ ﻯD.
A Simple Constant Time Enumeration Algorithm for Free Trees 中野 眞一 宇野 毅明 群馬大学 情報学研究所 2003 年 9 月 19 日 アルゴリズム研究会.
初歩的情報リテラ シーと アンケート集計のた めの Excel ・ SPSS 講 座 2002 年 5 月 14 日 政策科学部助手 山田 一隆.
三木 光範 (同志社大学工学部) 廣安 知之 (同志社大学工学部) 花田 良子 (同志社大学工学部学部 生) 水田 伯典 (同志社大学大学院) ジョブショップスケジューリング問 題への 分散遺伝的アルゴリズムの適用 Distributed Genetic Algorithm for Job-shop.
1 ネットワークでかわる社会 第1節 社会で利用されている情報シス テム 情報 プレゼン用資料 ( C401 ) 第2章.
交通システム 東京大学交通ラボ:「それは足からはじまっ たーモビリティの科学」,技報堂出版, 人間は「交流する動物」であ る 交流という人間の本質的な活動に伴って生じ る人や物や情報の行き来 <交通> <交通システム> 交通を支える技術的・制度的なしくみ.
サプライ・チェイン最適化 ー収益管理を中心としてー 東京海洋大学 久保 幹雄
事例: 自動販売機に対する在庫配送計画 宮本 裕一郎(発表者) 久保 幹雄 東京商船大学 共同研究:富士電機(株) 2001年3月5日.
到着時刻と燃料消費量を同時に最適化する船速・航路計画
最適化アルゴリズムの動向 ーメタヒューリスティックスを中心としてー (基礎編)
点対応の外れ値除去の最適化によるカメラの動的校正手法の精度向上
工学部 知能情報工学科 准教授 高 尚策 (コウ ショウサク)
データ構造と アルゴリズム 第十二回 知能情報学部 知能情報学科 新田直也.
生産スケジューリング.
近似アルゴリズム 第10章 終了時刻最小化スケジューリング
遺伝的アルゴリズム  新川 大貴.
座席割り当てのアルゴリズム 列車のどこに座りますか: ・山や海など車窓の景色を眺めながら行きたい ・窓側(または通路側)に座りたい ・タバコの煙がないところ(タバコが吸えるところ) ・出入り口の近くには座りたくない ・子どもと一緒なのでトイレの近くに座りたい ・団体客と一緒または近くに座りたくない.
局所探索に基づく 原子炉燃料装荷パターンの最適化
モード付き並列機械における オンラインスケジューリング
サプライ・チェイン最適化の最新動向 久保 幹雄 東京商船大学 江東区越中島2ー1ー6 流通情報工学 流通管理工学講座 流通経営工学 助教授
遺伝アルゴリズムによる NQueen解法 ~遺伝補修飾を用いた解探索の性能評価~
土木計画学 第11回(12月21日) 土木計画と説明責任 計画における代替案の作成1 担当:榊原 弘之.
経済・経営情報コース コース紹介.
配送計画最適化システム WebMETROご紹介
マイクロシミュレーションにおける 可変属性セル問題と解法
データ構造と アルゴリズム 知能情報学部 新田直也.
第7章 データベース管理システム 7.1 データベース管理システムの概要 7.2 データベースの格納方式 7.3 問合せ処理.
算法数理工学 第12回 定兼 邦彦.
大阪教育大学大学院教育学研究科 総合基礎科学専攻 中窪 仁
高山建志 五十嵐健夫 テクスチャ合成の新たな応用と展開 k 情報処理 vol.53 No.6 June 2012 pp
~ 日本の製造業を応援する無料の本格的スケジューラ ~
「コスト削減」「CS向上」「他部門貢献」を支援
早わかりアントコロニー最適化 (ACO: Ant Colony Optimization)
応用社会システム計画 (第10回) ここで、学習すること 学籍番号: 氏名: ■これまでの講義内容の整理 ■計画問題の設定と手法
制約充足と反復改良 (Constraint Satisfaction and Iterative Improvement)
大阪市立大学 学術情報総合センター 大西克実
MPIを用いた並列処理 ~GAによるTSPの解法~
ネットワーク上での社会的効用と個人的効用の対立問題に対するアルゴリズム的研究
決定木とランダムフォレスト 和田 俊和.
グラフアルゴリズムの可視化 数理科学コース 福永研究室 高橋 優子 2018/12/29.
第3回 アルゴリズムと計算量 2019/2/24.
Introduction to Soft Computing (第11回目)
進化的計算手法の並列計算機への実装 三木 光範
早わかりアントコロニー最適化 (Ant Colony Optimization)
組合せ最適化の近似解法 ・ 厳密解法 ・ 近似解法 ・ 発見的解法.
日程計画 (scheduling) 大規模なプロジェクトの日程を計画し、その進行を管理する手法。
GPSを使わないBebop Droneの 自動飛行
連続領域におけるファジィ制約充足問題の 反復改善アルゴリズムによる解法 Solving by heuristic repair Algorithm of the Fuzzy Constraint Satisfaction Problems with Continuous Domains 北海道大学.
ICTを利活用した 安心・元気な町づくり事業
適応的近傍を持つ シミュレーテッドアニーリングの性能
知識科学研究科 知識システム構築論講座 林研究室 佛明 智
ナップサック問題 クマさん人形をめぐる熱いドラマの結末.
第2回  発見的探索(1).
Introduction to Soft Computing
配送計画最適化システム WebMETROのご紹介
ロジスティクスにおける 最適化の応用 東京商船大学   流通システム 久保 幹雄.
第16章 動的計画法 アルゴリズムイントロダクション.
表紙 分散遺伝的アルゴリズムのための 新しい交叉法.
シミュレーテッドアニーリングにおける 重要温度領域に関する考察
平面走査法を使った 一般線分の 交点列挙アルゴリズム
分枝カット法に基づいた線形符号の復号法に関する一考察
コストのついたグラフの探索 分枝限定法 A*アルゴリズム.
演習問題 下記の表は木造家屋建築作業リストである。
原口和也 高橋隆一 丸岡章 石巻専修大学 理工学部 情報電子工学科
第4章 空間解析 2.ネットワーク分析 (2) 最大流問題
Presentation transcript:

配送計画システム

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

幹線輸送計画

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

集合被覆問題

列車 1 列車 2 列車 3 列車 4 列車 5 駅B駅B 駅C駅C 駅C駅C 駅A駅A 駅B駅B 駅B駅B 駅B駅B 駅B駅B 駅A駅A 駅C駅C 最小費用循環流モデル

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

<ビークルルーティング問題 > デポから複数の顧客へのコスト最小 な配送経路を求める問題 顧客 デポ A B C D E F G H I J 車両1 車両2 車両3

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

<セービング法>

<スウィープ法>

解の探索-列挙木- 解法:分枝限定法による解空間の探 索 1

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

組合せ問題の難しさ -ハミルトン経路問題- セールスマンが全ての都市を 1 回ずつ通過して、出 発地に戻って来る経路で最も短いものを捜す問題で す。 セールスマンが全ての都市を 1 回ずつ通過して、出 発地に戻って来る経路で最も短いものを捜す問題で す。・6都市ならば、 5 !/ 2 = 5 × 4 × 3 × 2 / 2 = 60通り 5 !/ 2 = 5 × 4 × 3 × 2 / 2 = 60通り・n都市ならば、 (n-1)! / 2通り (n-1)! / 2通り 近年, 新聞や科学雑誌でも取り上げられて有名になり ました。 TSP ( Traveling Salesman Problem ) 原型:ハミルトン経路問題 東京大学工学部計数工学科 松井知己氏資料から

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

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

<大規模組合せ最適化問題の解法>

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

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

局所探索法 (山登り法) 現在の解 全近傍を探索? 改善? 解の更新 N Y 近傍探索 解の評価 N 近傍での解の修正 評価関数の値の計算 終了 Y ◎初期解 ○ ○ ● 局所解 解空間 山登り法(局所探索法)

改善? 解の更新 N Y 近傍探索 解の評価 ○ ○ ● 局所解 解空間 評価値に対応 した確率で <SA法> ○ ○ ○ ○ ● 局所解 高温 低温 シミュレーテッド・アニーリング法(SA法)

解空間 評 価 関 数 の 値 最適解 遺伝アルゴリズム(GA法)

タブー探索法(TS法) ) 局所探索 局所解を一定期間探索禁止とする(タブーリスト) <タブー探索法> ◎初期解 解空間 局所解 タブーリスト 最適解

2392都市の巡回セールスマン問題

新物流情報システムの構成 カーPC 通信 サーバ DB サーバ 運行管理端末実績管理端末 配車計画端末 < 物流センター > <車両> GPSPCナビ

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

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

<ビークルルーティング問題 > デポから複数の顧客へのコスト最小 な配送経路を求める問題 顧客 デポ A B C D E F G H I J 車両1 車両2 車両3

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

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

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

車両を選択 未割当配 送先有り 割当可能 配送先有り 最も近い配送 先を割当てる Y Y 終了 N N <初期解作成の処理フロー >

配送先 配送センタ A B C D E F G H I J 車両1 車両2 車両3 初期解の例

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

a)配送先の移動(削除・追加 ) b)配送先の交換 車両割当変更操作

<配送先の削除> 元の配送順: A→B→C→D→E→FA→B→C→D→E→F 配送先Cを削除 A→B→D→E→FA→B→D→E→F <配送先の追加> 元の配送順:A→B→D→E→FA→B→D→E→F 配送先Hを追加 A B C D E F A B D E F A B D E F H 新たな配送順:A→B→D→E→H→FA→B→D→E→H→F (最適な位置に追加) (他は元の配送順) 削除 追加 新たな配送順: 配送順序の決定(簡易法)

配送順序の決定(2-opt法) a b c d a b c d 2-opt法 <配送順序の最適化> 0 h i a b e fg c d j k 0 0 h i a c g fe b d j k 0 0:配送センタ

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

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

<標準的な配送計画問題> depot customer garage customer

<複数デポ配送計画問題> depot customer garage customer depot

<集配送計画問題> depot customer garage customer : delivery : pick up