混載輸送ネットワーク設計 上智大学 宮本裕一郎 2002年7月23日 共同研究者：東京商船大学 久保幹雄.

Presentation on theme: "混載輸送ネットワーク設計 上智大学 宮本裕一郎 2002年7月23日 共同研究者：東京商船大学 久保幹雄."— Presentation transcript:

1 混載輸送ネットワーク設計 上智大学 宮本裕一郎 2002年7月23日 共同研究者：東京商船大学 久保幹雄

2 発表の概要 混載輸送ネットワーク設計モデルとは 整数計画問題としての定式化および簡単な計算実験 下界の算出（ラグランジュ緩和法の適用） 上界の算出（メタ解法） より複雑なモデル（時間制約の追加，頻度の考慮） まとめと今後の課題 1時間程度を予定

3 混載輸送とは 混載輸送とは，異なる荷物を一緒に載せて運ぶこと 目的地が異なる荷物を運ぶ場合，それぞれの荷物が小さいならば 途中はまとめて1台のトラックに乗せれば，費用がお得 イメージ的には，郵便や宅配便 ただし，郵便局間や集配所間の輸送ネットワークを考える 顧客への配送，顧客からの集荷は考えない 横浜 神戸 東京 大阪 千葉 京都

4 ことのはじまり 某製造会社の事例 某地区に部品工場と組み立て工場を複数所有 主に部品工場群から組み立て工場群へ， ほぼ毎日部品が輸送される 工場間は定期便（トラック）が毎日運行されている （直通とは限らない，日々の微調整あり） 毎日運ばれる各部品はトラック1台分に満たない 定期便の経路を設計したい （できれば中継点（デポ）の設置も同時に考えたい）

5 混載輸送ネットワークへの対応方法 長期 拠点の配置，拠点の規模の決定 トラックなどの必要量を見積もり 拠点間の定期便を計画 定期便の時間・量・経路を微調整 配送計画ソルバーで対応 短期 配送計画ソルバーを適用するためには， 各荷の積み替え点（クロスドック・ポイント）を決める必要あり この問題をモデル化するために いくつかの仮定を置く 事例より生じた 今回のメインテーマ

6 荷の定義に関する仮定 A 1 異なる荷でも発地・着地の対が同じならば同じ荷と見なす A 1 2 同じ荷でも発地が異なれば違う荷と見なす 各荷は発地・着地の対に対応

7 各荷の経路の仮定 荷の輸送経路はそれぞれ初等的な路(elementary path) 1 2 途中で二つに分かれちゃダメ 1 2 同じ拠点を 何度も通っちゃダメ 1 2

8 ネットワーク設計の仮定 主にトラック輸送を考えるが，トラックの具体的な回し方は考えない （荷を流すためのネットワークを施設すると考える） 2 1 3 中継点 A B

9 ネットワーク設計の仮定 主にトラック輸送を考えるが，トラックの具体的な回し方は考えない （荷を流すためのネットワークを施設すると考える） 2 1 3 中継点 A B 目的は，輸送費用を考慮しつつ各品種の積み替え点を決めること

10 用語・記号 V: 拠点の集合，拠点：工場・物流センターなど E: 有向枝の集合，拠点間を結ぶ（完全グラフではない） K: 品種の集合，品種：発地・着地で区別される荷物 M: モード（輸送手段）の集合， モード：4トントラック，8トントラック，船など

11 品種ごとに通過可能な枝 Ek⊆ E: 品種kが通り得る枝の集合 品種ごとに通過可能な枝（さらには拠点）を設定できる

12 枝ごとに使用可能なモード Me⊆ M: 枝eで使えるモードの集合 全ての拠点で全ての輸送手段が使えるとは限らない トン数による入庫制限などがある p 枝p,qでは しか 通過できないと考える q

13 定数（データ） fk: 品種k∈Kの流量（荷量）（整数） cke: 品種k∈Kを枝e∈Ek上で(fk)運ぶときにかかる費用（実数） （品種に依存する費用） Wm: 輸送手段m∈Mの最大容量（整数） Cme: 枝e∈E上でモードm∈Meを1単位使うときの費用（実数） （モードに依存する費用） q p c赤p＋ Cトラックp c赤q＋ 2Cトラックq

14 変数 xke∈{0, 1}: 品種k∈Kを枝e∈Ek上で運ぶとき1，そうでないとき0 yme∈Z+: 枝e上でモードm∈Meを使う量 非負整数 yトラックq=1 yトラックp=1 q p x赤p=1 x赤q=1 r x赤r=0 yトラックr=0

15 目的は費用の最小化 費用は2種類 モードごとにかかる費用 品種ごとにかかる費用

16 制約は主に2つ 各枝では流量≦容量が成り立つ 各品種ごとの流れはelementary pathになる

17 整数計画問題としての定式化 ただし，head(e):枝eの始点， tail(e):枝eの終点 tail(e) head(e) e

18 問題の難しさ ナップサック問題 ナップサック アイテム 混載ネットワーク設計問題 モード 品種 NP-困難 点彩色問題 点 色数 混載ネットワーク設計問題 品種，拠点 モード 各枝の容量が決まれば，多品種最小費用流問題 拠点配置問題 工場など拠点の生産量決定 需要 混載ネットワーク設計問題 枝の容量決定 品種の流れ

19 簡単に計算実験 とりあえず，市販の整数計画ソルバーとパソコンで どのくらいの大きさまで解けるか実験 実験環境 ソルバー：CPLEX 7.0 CPU:PentiumIII 500MHz RAM: 128MB 問題例 二次元平面上に拠点が（ランダムに）分布 モードは容量10の1種類 モード依存費用Cmeは枝eの長さに比例 全ての拠点間に流量が0でない品種あり k∈Kに対してEkは完全有向グラフ 品種の流量は1～10の一様乱数（混載が起こりやすいように） 品種依存費用は0 品種＝点対

20 計算時間 問題例 計算時間（秒） 壱 弐 参 四 伍 六 七 八 9.4 九 拾 平均 問題の大きさ 点数：5 品種：20 枝数：20 点数が6の場合は断念 現実問題を，厳密に解くのは困難 スピード，使い勝手の面からも高性能ヒューリスティクスがよい

21 変数を整数でなく実数にすると最適値は約30%減
線形緩和 変数を整数でなく実数にすると最適値は約30%減 容量の大きなモード，流量の小さい品種 ↓ 線形緩和とのギャップをいくらでも大きくできる 単純に主双対ヒューリスティックを作っても期待薄 容量と流量に制約を加えれば近似精度保証できる しかし混載ネットワーク設計問題の特徴を損ねることに 下界の評価→ラグランジュ緩和 上界の評価→メタ解法

22 ラグランジュ緩和 λkv フロー整合条件緩和

23 ラグランジュ緩和問題 λに関して劣勾配法を適用する フロー整合条件を緩和したので 子問題は枝eごとに分解できる

24 枝eごとの子問題 枝ごとの子問題は小さいので，分枝限定法で解いても良いが s=1,2,…について ＋ を解けば擬多項式時間で解ける

25 メタ解法 局所探索法 タブーサーチ 初期実行可能解生成 ＋ 実用的にはメタ解法 ラグランジュ緩和の劣勾配法にも上界は必要 初期実行可能解はランダムに生成 各品種ごとにパスをランダムに決める

26 改善近傍 既に実行可能解が得られているとする ある品種に注目する（赤い品種に注目する）

27 改善近傍 注目している（赤い）品種の経路だけを変更し

28 改善近傍 モードを再計算する

29 実際に変更可能な全ての経路を吟味するのは無駄
局所探索法（概念） 【局所探索法の1反復】 各品種k∈Kについて 他の品種K＼{k}の経路を変更せずにkの経路変更を考慮 変更により改善される費用の最大値を計算 費用改善が正の品種があるならば（改善の余地があるならば） 費用改善が最大である品種kのみの経路を変更 モードを再計算 費用改善が正の品種がないならば 探索終了 実際に変更可能な全ての経路を吟味するのは無駄 差分のみを計算する→最短路問題に帰着

30 最短路問題への帰着 品種依存費用 ＋モード増加費用 動的計画法により 求解可能 （表により保存も可）

31 最短路問題への帰着 費用の増分 費用の増分 費用の増分 費用の増分 費用の増分 既存の経路だけ有利

32 最短路問題への帰着 費用の増分 費用の増分 費用の増分 費用の増分 費用の増分 費用の増分 既存の経路については 流れていないと仮定して 費用の増分を見積もる そして最短路問題を解く

33 最短路問題への帰着 経路を変更すると，部分的にモードが変更される 費用の増分 費用の増分 費用の増分 費用の増分 費用の増分 費用の増分

34 最短路問題への帰着 部分的に費用の増分を再計算 各品種の 費用の増分を再計算 費用の増分 費用の増分 費用の増分 費用の増分 費用の増分 費用の増分

35 局所探索法（改訂版） 全ての枝・品種に関して費用の増分を計算 以下を繰り返す 各品種について以下を繰り返す 費用の増分に関する最短路を求める 現在流れている枝の費用の増分の合計－最短路長 が費用改善である 費用改善が正の品種があるならば， その品種の経路を変え，輸送手段を再計算 費用の増分を必要な部分だけ再計算 費用改善が正の品種がないならば， 探索終了

36 現状経路が最短路（最善経路）の場合，第2最短路を選択
タブー探索法 タブー探索法では改悪もあり得る ↓ 現状経路が最短路（最善経路）の場合，第2最短路を選択 何をタブーにするか？ 各品種についてその経路を入れ替えているわけだから 品種と経路の組み合わせ？ その前に，タブー探索の意義を考える

37 タブー探索でうれしい場合 局所最適解がある

38 タブー探索でうれしい場合 黒が無理して改悪

39 タブー探索でうれしい場合 赤が無理して改悪

40 タブー探索でうれしい場合 青が無理して改悪

41 タブー探索でうれしい場合 さらに緑が加わってやっと改善 多品種が混載することの スケールメリット

42 何をタブーにするか？ 大胆な改悪が頻繁に起こる必要あり 品種と経路の組み合わせ ↓ 品種と経路に含まれる枝 品種 きめ細かな探索 粗い探索 実際に計算してみると， 品種をタブーにするのがもっともよい 険しい山岳地帯で低いところを目指すならば 健脚探検家よりも落下傘部隊の方がよさそう

43 マルチスタート マルチスタート局所探索 （凡人による落下傘部隊） 1スタートタブー探索 （健脚探検家1人） VS 同じ歩数で比べた結果， 落下傘部隊の勝ち！ まだまだ，改善の余地は考えられますが， マルチスタートタブー探索で 整数計画として解ける程度であれば最適解が求まった より大きな問題に対しても，上界と下界のギャップは十分小さい

44 範囲が広く，輸送経路が長くなりがちな場合には 「●●時間以内に届けて～」 と言われる． ↓ 費用最小化だけを目指し，遠回りする品種があって
より一般には 範囲が広く，輸送経路が長くなりがちな場合には 「●●時間以内に届けて～」 と言われる． ↓ 費用最小化だけを目指し，遠回りする品種があって 時間がかかりすぎてもだめ 輸送時間指定を絶対制約として費用最小化を目指す 各品種に輸送上限時間を追加Tk 各枝に輸送時間を追加te これにより，積み替え回数（すなわち経由枝数）の制限も可能

45 整数計画問題としての定式化

46 時間制約付き問題のメタ解法 実行可能解の構築は比較的簡単 では，近傍や改善は？ 絶対時間制約により 最短路問題→時間制約付き最短路問題 最短路問題 ダイクストラ法 各点に距離のラベル 多項式時間 時間制約付き最短路問題 動的計画法 各点に（距離，時間）の非劣解集合 擬多項式時間 （距離，時間）の非劣解を 距離でソートすると 時間に関して（逆）ソートされている ↓ ラベルの更新は高速

47 時間制約付き問題のメタ解法 今考えている時間制約付き最短路問題は そもそもメタ解法のサブルーチンなので 最適解の保証は必要ない 時間制約をラグランジュ緩和すれば （ラグランジュ乗数は1つなので） 高速に良い解を得られる 各品種の到達時間を考える際重要なのは， 輸送時間ではなく輸送頻度 ↓ 頻度をモードとして扱う

48 頻度の考慮 ここまでの議論では，積み替えがすぐに行われることを仮定 時速100キロで600キロ運び，中継点が2箇所ある場合 それぞれの区間が1日1便であれば， 荷物は最悪積み替え場所で1日待つことになる． 平均で12時間と考えても，総待ち時間の期待値は24時間． トラックの輸送時間，6時間と比べても格段に多い． 混載輸送ネットワークにおいて 特にトラックなどを用いた輸送の場合には 輸送時間は走行時間よりも輸送頻度に依存する 輸送時間とともに頻度も考慮する

49 頻度の考慮 1日，1週間という具合に単位時間を決める 単位時間あたり1回，2回，．．．という具合に頻度を決める トラックのレンタルにかかる費用は，頻度に依存すると仮定する ×頻度2 ×頻度1 ×頻度1 今まではトラックの容量だけをモードとしてとらえていたが， 今度はトラック容量と頻度の組み合わせをモードとする． このとき各品種の通過経路はelementary pathであるという仮定は そのままであるとする

50 頻度の考慮 頻度を考慮しない場合 各枝に複数のモード 問題として与えられるグラフは有向単純グラフ 頻度を考慮する 頻度を考慮しない 頻度を考慮する場合 各枝に1つのモード 問題として与えられるグラフは有向グラフ ただし，トラック容量と頻度の組み合わせは少ないとは限らない

51 整数計画問題としての定式化 問題を明確にするために定式化 →実は頻度を考慮しない場合と同じ

52 頻度の考慮 頻度を考慮すると 定式化→変化なし 問題データ→単純グラフから一般のグラフに変化 この変化は問題データを作り直すだけなので アルゴリズムを変更することなく対応できる． ただし，トラック容量と頻度の組み合わせは多いので 解くべき問題は大きくなる．（枝の数が多くなる） ↓ 計算時間の増加，計算精度の悪化 特に頻度の設定などはどの程度が妥当であるのかわからないので まだ，計算実験していない．今後の課題といえる．

53 まとめ 混載輸送ネットワークの設計に際して， 各品種の輸送経路を大まかに計画する方法を提案した． 単純なモデルを提案 整数計画問題として定式化 整数計画ソルバーを用いた簡単な計算実験 ラグランジュ緩和問題として下界を算出する方法を提案 最短路問題をサブルーチンとするメタ解法により上界 を算出する方法を提案． 時間制約を考慮したモデルを考察 頻度を考慮したモデルを考察

54 今後の課題 それぞれのモデルおよびアルゴリズムの妥当性を確かめるために， 実用的な問題例で計算実験をすることが考えられる． さらに別の制約が入った問題に対する適用（あるいは拡張） を考えることも課題といえる． ツリー型の輸送形態に対して適用 多品種ロットサイズ決定問題に対して適用

55 ツリー型の輸送形態に対して適用 今回議論したモデルでは各品種の輸送経路はelementary path という制約だけであった． 神戸 名古屋 京都 東京 大阪 よって図のような経路は実行可能解である． しかし，最終目的地が同じ東京であるのに， 京都で一緒になった後でまた分かれるのはおかしい， という場合もあり得る．

56 ツリー型の輸送形態に対して適用 最終目的地が同じ品種が同じ積み替え点に来た場合には その後は同じ経路で輸送することにする． 神戸 名古屋 京都 東京 大阪 最終目的地が同じ品種の輸送経路が入木(in tree)になっている 輸送形態を「ツリー型」と呼ぶことにする． この制約を加えたモデルも，整数計画問題で定式化できるが 今回は割愛する．

57 ツリー型の輸送形態に対して適用 メタ解法を適用する場合，初期解の生成は用意である． 神戸→東京 の・・・ 京都→東京 の・・・ 名古屋→東京 の混載費用を 記憶 神戸 名古屋 京都 東京 大阪 横浜 改善を行う場合はやはり最短路問題に帰着できる すでに入木に含まれている各点で終点までの混載費用を記憶し 入木に含まれない各枝での輸送費用の増分を設定 始点終点を指定した最短路問題→始点から全点への最短路問題

58 （単品種）ロットサイズ決定問題 段取り費用がある場合，まとめて生産・輸送したほうがお得 しかし需要は満たさなければいけない． どの程度まとめて生産・輸送する？ 1日目の生産・輸送 2日 1日 3日 4日 5日 1日目から2日目への在庫 1日目の需要

59 （単品種）ロットサイズ決定問題 需要を満たす最小費用流（枝設置費用あり） が最小費用生産・輸送計画を表す 1日 2日 3日 4日 5日

60 多品種ロットサイズ決定問題 部品A，Bから製品Cが作られる．A，B，Cの生産量を同時に決定 A C B A，Bの需要量はCの生産量に依存

61 多品種ロットサイズ決定問題 1日 2日 3日 4日 5日 1日 2日 3日 4日 5日 需要を満たす，多品種最小費用流（枝設置費用あり） を求めたい． 特定の日の需要を満たすための流れは入木が一般的か？ 混載ネットワーク設計問題とは異なる部分もある

62 おわり