運搬スケジューリング問題とその周辺

運搬スケジューリング問題と
その周辺
東京商船大学流通情報工学
久保幹雄
本日のメニュー




運搬スケジューリング問題とは
基本モデル
解法（分解原理と分枝価格法）
拡張モデル


タスク遂行条件とリソース拡張関数
応用

航空機産業とトレーラーによるコンテナ輸送
運搬スケジューリング問題とは


（時間枠付き）運搬経路問題
乗務員スケジューリング問題
統一的求解のためのフレームワーク

Dantzig-Wolfeの分解原理
⇒列生成法
分枝価格法（branch and price
method）
運搬経路問題に対する解法の歴史
近似解法
Genetic Algorithm
Tabu Search
Local Search
Simulated Annealing
構築法
(Saving, Insertion)
一般化割当法
下界導出
1960
AMP
(Adaptive Memory
Programming)
GRASP
(Greedy Randomized
Adaptive Search Procedure)
Location Based
Heuristic
ルート選択
Ｈｅｕｒｉｓｔｉｃ
列生成法
State Space Relax.
Cutting Plane
K-Tree Relax.
1970
1980
1990
階層的
積木法
基本モデル
構成要素
運搬車の集合
K
航空機，バス，鉄道，トラック，船，乗務員
 タスクの集合
Task
便，荷
 移動化ネットワーク



点上活動図式（activity-on-node diagram）：
タスクが点
枝上活動図式（activity-on-arc diagram）：
タスクが枝
移動可能ネットワーク（枝上活動図
式）
運搬車
kK
k
k
に対して：
G  (V , E ) V  N  o(k ), d (k )
k
[8:30,9:00]
k
k
8:30発 9:10発
Nk
o(k )
d (k )
発地
着地
移動可能ネットワーク
時空間ネットワーク（枝上活動図式）
8:30
9:00 9:10
時間
待ち
o(k )
d (k )
タスクの処理を表す集合
EKt  {(i, j) :
点iから点jへ運搬車kが移動
⇒タスク t が処理される
}
リソース集合

運搬車kに対するリソース集合
Res
時間枠制約
積載重量（容量）制約
目的関数
運搬車 k，点i，リソース rに対する
下限 RLB
kr
i
上限 RUB
kr
i
R
kr
ij
運搬車k，点iからjへ移動，リソース r の増加量
k
変数
リソース変数
kr
i
Y
運搬車フロー変数
k
ij
Y
X
j
i

Y  max RLB , Yi  R
kr
j
rk
j
kr
j
kr
kr
ij

定式化


1.
2.
3.
4.
最小化総費用
条件
タスク遂行条件
運搬車のフロー整合条件
XとYの繋ぎ条件
リソース量の上下限制約
最小化総費用

費用を表すリソース r=0
総費用 Y
kK
k0
d (k )
タスク遂行条件

すべてのタスクが処理される．
X
( i , j , k )EKt
k
ij
1

t  Task
運搬車のフロー整合条件

運搬車kが発地o(k)を出発し，着地d(k)に
到着することを表す．
1

k
k
 Xk ij   Xk ji   0
j:( i , j )E
j:( j ,i )E
 1

i  o( k )


i  V  o(k ), d (k )
i  d (k )
k
i V , k  K
k
運搬車フロー変数Xと
リソース変数Yの繋ぎ条件

運搬車kが枝(i,j)上を移動 ⇒
リソースrが変化
( X  1)  Yi  R  Y
k
ij
kr

kr
ij
kr
j

r  Res , (i, j )  A , k  K
k
k
リソース量の上下限制約（１）

発地・着地の場合
RLB  Yi  RUB
kr
i
kr

kr
i
i o(k),d(k), r  Res , k  K
k
定式化（構造に対する洞察）
min. Ydk(0k )
kK
sub. to
k
X
 ij  1

t  Task
(i , j ,k )EKt
1

k
k
X

X

 k ij  k ji  0
j:( i , j )E
j:( j ,i )E
 1


i  o( k )

i  V  o(k ), d (k )
i  d (k )
( X ijk  1)  Y kr  Rkr  Y kr
i
ij
j
RLBikr  Yi kr  RUBikr
k

 j:(i , j )E k 
 j:(i , j )E k 




RLBikr   X ijk   Yi kr  RUBikr   X ijk 







i V k , k  K
r  Resk , (i, j )  Ak , k  K
i o(k),d(k), r  Resk , k  K

i  N k , r  Resk , k  K
Dantzig-Wolfeの分解原理
min. Ydk(0k )
kK
sub. to
k
X
 ij  1

(i , j ,k )EKt
t  Task
o(k) から d(k) までのリソース制約を満たすパス  k  K
Pk
多面体の端点（パス）の添え字集合
端点の特性ベクトル
(x , y ) p  P , k  K
k
k
kr
x  ( xijp ) y p  ( yip )
k
p
k
p
k
p
k
リソース量の上下限制約（２）

発地・着地以外の場合




k
kr
kr
k
RLB   X ij   Yi  RUBi   X ij 




k
k
 j:(i , j )E 
 j:(i , j )E 
kr
i

i  N , r  Res , k  K
k
k
Resolution定理(Minkowski-Weyl)
X ijk 
k
k
x

 ijp p

(i, j)  E
k
pP k
Yi 
kr
y 
kr
ip

k
p
pP k

k
p
i V
k
多面体の端点
k
x kp  ( xijp
) ykp  ( yipkr )
1
pP k
 1
k
p

pP
k
k
ij
kr
( X , Yi )
主問題
min.   y
kK pP k
sub. to

k0
d (k ) p
k
p
 x
( i , j ,k )EKt pP k
 0,1
k
p
 1
k
k
ijp p


t  Task
pP ,k K
k
変数の数は入力サイズの指数オーダー
制限付き主問題
~k
k
P  P (k  K ) に対して
min.   y
~
kK pP k
sub. to


k0
d (k ) p
 x  1
~
( i , j ,k )EKt pP k
 0,1
k
p
k
p
k
k
ijp p


t  Task
~k
pP ,k K
制限付き主問題の線形計画緩和
~k
k
P  P (k  K ) に対して
min.   y
~
kK pP k
sub. to


k0
d (k ) p
 x  1
~
( i , j ,k )EKt pP k
 0
k
p
k
p
k
k
ijp p

双対変数

t  Task
~k
pP ,k K
t
パス変数  の被約費用 c
k
p
c y
k
p
k0
d (k ) p


k
p
 x
k
t ijp
(i , j )E k tTask :(i , j ,k )EKt

pP ,k K
k
部分問題 k ( K )
リソース制約付き最短路問題
k0
d (k )
min. Y


 X
k
ij
t
(i , j )E k tTask :( i , j ,k )EKt
1

sub. to  X ijk   X kji   0
j:( i , j )E k
j:( j ,i )E k
 1


i  o( k )

i  V k  o(k ), d (k )
i  d (k )
( X ijk  1)  Yi kr  Rijkr  Yjkr
RLBikr  Yi kr  RUBikr

 j:(i , j )E k 
 j:(i , j )E k 




RLBikr   X ijk   Yi kr  RUBikr   X ijk 







i V k
r  Resk , (i, j )  Ak
i o(k),d(k), r  Resk

i  N k , r  Resk
列生成法
主問題の
線形計画緩和
双対変数
t
部分問題
「目的関数<0」
のパス（列ベクトル）
部分問題
部分問題
k ( K )
すべての部分問題で「目的関数<0」なら終了
部分問題
分枝価格法（パス変数による分枝）
 1
k
p
あるパスを必ず使用する
 0
k
p
あるパス以外の最小費用パス
第Ｌ最適解（Ｌは探索の深さ）
あるパスを使用しない
分枝価格法（原変数による分枝）
X  0.5
k
ij
X 0
X 1
k
ij
k
ij
X  0.5
k'
ij
X 1
k'
ij
X 0
k ''
X ij  0.5
k'
ij
運搬車が同一のとき，下界が改良されない！
分枝価格法
（運搬車が同一のときの分枝ルール１）
 X 1
kK
k
ij


k
k
   X ij  1, J  V 
 kK

k
k

K
 jJ :(i , j )E

X
kK
k
ij
0


k
k
   X ij  0, J  V 
 kK

k
k

K
 jJ :(i , j )E

分枝価格法
（運搬車が同一のときの分枝ルール２）
 X
kK ' k:( i , j )E k
k
ij
 1, K '  K
 X
kK ' k:(i , j )E k
k
ij
 0, K '  K
タスク遂行条件の一般化

すべてのタスクが
X
(i , j ,k )EKt
k
ij
nt 回処理される．

t


t
     nt
超過量
総費用 Y
kK
t  Task
不足量
k0
d (k )

 (P 

tTask
t

t


t
 Pt  )
超過ペナルティ不足ペナルティ
リソース拡張関数
リソース変数ベクトル
k
i
Y
kr
ij
Ext

 
Y  max RLB , Ext Y
kr
j
rk
j
i
kr
ij
k
i
j
リソース制約付き最短路問題の解法
kr
ij
Ext
が非減少関数
動的計画
それ以外
列挙，制約論理，メタ解法
航空機産業における応用
意思決定の階層
便決定問題
機団割当て問題
乗務員スケジューリング問題
1.
2.
3.
1.
2.
3.
任務決定問題
乗務員ペアリング問題（crew paring problem）
月次個別ブロック作成問題
1.
2.
3.
カルタ取り方式（bidline procedure）
勤務名簿作成問題（rostering problem）
優先順序付き勤務名簿作成問題（preferential bidding
problem）
乗務員スケジューリング
タスクの階層 (1)
1.
2.
3.
4.
便（flight, trip）
任務（duty）
ペアリング（paring）
月次個別ブロック（personalized monthly
block）
乗務員スケジューリング
タスクの階層 (2) 便と回送
8:30発 10:30着
便
羽田
11:30発 14:30着
広島
8:30発 10:30着
便
那覇
11:30発 14:30着
便
16:00発 19:00着
便
16:00発 19:00着
便
回送（deadhead）
羽田
乗務員スケジューリング
タスクの階層 (3) 任務
8:30発 10:30着
羽田
便
11:30発 14:30着
広島
便
任務（１日）
16:00発 19:00着
那覇
便
金沢
乗務員スケジューリング
タスクの階層 (4) ペアリング
成田
任務
金沢任務成田
任務
ペアリング（約１週間）
ワシントン
任務
成田
乗務員スケジューリング
タスクの階層 (5) 月次個別ブロック
ペアリング
休暇ペアリング
ﾄﾚｰﾆﾝｸﾞペアリング
月次個別ブロック（約１ヶ月）
待機
コンテナ輸送問題における応用
構成要素
トレーラー
荷
コンテナタイプ
（横開き，冷凍など）
顧客（複数）
コンテナターミナル（複数）
コンテナ輸送問題における応用
仮定１
トレーラーは１つのコンテナを牽引
荷はコンテナタイプを指定
コンテナ輸送問題における応用
仮定２
コンテナターミナルから顧客への荷
顧客からコンテナターミナルへの荷
時間枠
[8:00,10:00]
コンテナターミナルには十分なコンテナ
コンテナ輸送問題
概念図と記号の定義１
リソース
時間
0
1
2

r
コンテナ
積み替え時間
St

移動時間
Tij
| Res |k
コンテナ輸送問題
概念図と記号の定義２
t (i, j )
j
i
t (i, j)  argminTit  St  Tjt
コンテナ輸送問題
kr
リソース拡張関数 Extij
kr 地点iからjへの荷が運搬車ｋ＋コンテナタイプrで
ij 処理可能なとき1，それ以外のとき０
CT
r  0 のとき
k0

Y
 Tij

i
k0
Extij   k 0

Yi  Ti ,t (i , j )  St (i , j )  Tt (i , j ), j
r ( 1) s.t. CTijkr  1 & Yi kr  1
それ以外
r  1のとき
kr
kr

Y

CT
ij
 i
kr
Extij  
kr
CT
ij


r ( 1) s.t. CTijkr  1 & Yi kr  1
それ以外
まとめと課題




種々の実際問題を統一的に解くアルゴリ
ズムの存在から生まれたモデルの提示
実際問題ごとの個別条件（実務家と研究
者のcommunicationが重要！）
システム開発
動的なモデル

Download Report