運搬スケジューリング問題と その周辺 東京商船大学　流通情報工学 久保　幹雄

本日のメニュー 運搬スケジューリング問題とは 基本モデル 解法（分解原理と分枝価格法） 拡張モデル 応用 タスク遂行条件とリソース拡張関数 航空機産業とトレーラーによるコンテナ輸送

運搬スケジューリング問題とは （時間枠付き）運搬経路問題 乗務員スケジューリング問題 Dantzig-Wolfeの分解原理 ⇒列生成法 分枝価格法（branch and price method） 統一的求解のためのフレームワーク

運搬経路問題に対する解法の歴史 近似解法 AMP Tabu Search Local Search GRASP 階層的 積木法 構築法 Genetic Algorithm AMP (Adaptive Memory Programming) Tabu Search Local Search Simulated Annealing GRASP (Greedy Randomized Adaptive Search Procedure) 階層的 積木法 構築法 (Saving, Insertion) ルート選択 Ｈｅｕｒｉｓｔｉｃ Location Based Heuristic 一般化割当法 下界導出 列生成法 State Space Relax. Cutting Plane K-Tree Relax. 1960 1970 1980 1990

基本モデル 構成要素 運搬車の集合 航空機，バス，鉄道，トラック，船，乗務員 タスクの集合 便，荷 移動化ネットワーク 　航空機，バス，鉄道，トラック，船，乗務員 タスクの集合 便，荷 移動化ネットワーク 点上活動図式（activity-on-node diagram）： タスクが点 枝上活動図式（activity-on-arc diagram）： タスクが枝

　移動可能ネットワーク（枝上活動図式） 運搬車 に対して： [8:30,9:00] 9:10発 発地 着地 8:30発

移動可能ネットワーク 時空間ネットワーク （枝上活動図式） 　移動可能ネットワーク 時空間ネットワーク （枝上活動図式） 時間 8:30 9:00 9:10 待ち

タスクの処理を表す集合 点iから点jへ運搬車kが移動 　　　　　　　　⇒タスク t が処理される

リソース集合 運搬車kに対するリソース集合 時間枠制約 積載重量（容量）制約 目的関数 運搬車 k，点i，リソース rに対する 運搬車k，点iからjへ移動，リソース r の増加量

変数 リソース変数 運搬車フロー変数 i j

定式化 最小化　総費用 条件　　　 タスク遂行条件 運搬車のフロー整合条件 XとYの繋ぎ条件 リソース量の上下限制約

最小化　総費用 費用を表すリソース　r=0

タスク遂行条件 すべてのタスクが処理される．

運搬車のフロー整合条件 運搬車kが発地o(k)を出発し，着地d(k)に到着することを表す．

運搬車フロー変数Xと リソース変数Yの繋ぎ条件 運搬車kが枝(i,j)上を移動　⇒ 　　　　　　　　　　　　　　　　リソースrが変化

リソース量の上下限制約（１） 発地・着地の場合

定式化（構造に対する洞察）

Dantzig-Wolfeの分解原理 o(k) から d(k) までのリソース制約を満たすパス 端点の特性ベクトル 多面体の端点（パス）の添え字集合 端点の特性ベクトル

リソース量の上下限制約（２） 発地・着地以外の場合

Resolution定理(Minkowski-Weyl) 多面体の端点

主問題 変数の数は入力サイズの指数オーダー

制限付き主問題 に対して

制限付き主問題の線形計画緩和 に対して 双対変数

パス変数　　の被約費用

部分問題　　　　 リソース制約付き最短路問題

列生成法 主問題の 線形計画緩和 「目的関数<0」 のパス（列ベクトル） 双対変数 部分問題 部分問題 部分問題 部分問題 すべての部分問題で「目的関数<0」なら終了

分枝価格法（パス変数による分枝） あるパス以外の最小費用パス 第Ｌ最適解（Ｌは探索の深さ） あるパスを必ず使用する あるパスを使用しない

分枝価格法（原変数による分枝） 運搬車が同一のとき，下界が改良されない！

分枝価格法 （運搬車が同一のときの分枝ルール１）

分枝価格法 （運搬車が同一のときの分枝ルール２）

タスク遂行条件の一般化 すべてのタスクが 回処理される． 超過量 不足量 超過ペナルティ 不足ペナルティ

リソース拡張関数 リソース変数ベクトル i j リソース制約付き最短路問題の解法 が非減少関数 動的計画 それ以外 列挙，制約論理，メタ解法

航空機産業における応用 意思決定の階層 便決定問題 機団割当て問題 乗務員スケジューリング問題 任務決定問題 乗務員ペアリング問題（crew paring problem） 月次個別ブロック作成問題 カルタ取り方式（bidline procedure） 勤務名簿作成問題（rostering problem） 優先順序付き勤務名簿作成問題（preferential bidding problem）

乗務員スケジューリング タスクの階層 (1) 便（flight, trip） 任務（duty） ペアリング（paring） 月次個別ブロック（personalized monthly block）

乗務員スケジューリング タスクの階層 (2) 便と回送 乗務員スケジューリング タスクの階層 (2)　便と回送 便 11:30発 10:30着 8:30発 14:30着 16:00発 19:00着 羽田 那覇 羽田 広島 8:30発 10:30着 11:30発 14:30着 16:00発 19:00着 便 便 回送（deadhead）

乗務員スケジューリング タスクの階層 (3) 任務 乗務員スケジューリング タスクの階層 (3)　任務 8:30発 10:30着 11:30発 14:30着 16:00発 19:00着 便 便 便 羽田 広島 那覇 金沢 任務（１日）

乗務員スケジューリング タスクの階層 (4) ペアリング 乗務員スケジューリング タスクの階層 (4)　ペアリング 任務 任務 任務 任務 成田 金沢 成田 ワシントン 成田 ペアリング（約１週間）

乗務員スケジューリング タスクの階層 (5) 月次個別ブロック 乗務員スケジューリング タスクの階層 (5)　月次個別ブロック ペアリング ペアリング ペアリング 休暇 ﾄﾚｰﾆﾝｸﾞ 待機 月次個別ブロック（約１ヶ月）

コンテナ輸送問題における応用 構成要素 トレーラー 荷 コンテナタイプ （横開き，冷凍など） 顧客（複数） コンテナターミナル（複数）

コンテナ輸送問題における応用 仮定１ トレーラーは１つのコンテナを牽引 荷はコンテナタイプを指定

コンテナ輸送問題における応用 仮定２ コンテナターミナルから顧客への荷 顧客からコンテナターミナルへの荷 時間枠 [8:00,10:00] コンテナターミナルには十分なコンテナ

コンテナ輸送問題 概念図と記号の定義１ リソース 時間 コンテナ 積み替え時間 移動時間

コンテナ輸送問題 概念図と記号の定義２

コンテナ輸送問題 リソース拡張関数 地点iからjへの荷が運搬車ｋ＋コンテナタイプrで 処理可能なとき1，それ以外のとき０

まとめと課題 種々の実際問題を統一的に解くアルゴリズムの存在から生まれたモデルの提示 実際問題ごとの個別条件（実務家と研究者のcommunicationが重要！） システム開発 動的なモデル