混載輸送ネットワーク設計問題に対するLagrange緩和法

混載輸送ネットワーク設計問題に対する Lagrange 緩和法
A Lagrange Relaxation Method for the Less-Than-Truckload Network Design Problem
片山 直登*
By Naoto KATAYAMA
1.
路設計を扱い，路線の最低便数，木条件および積換え
はじめに
近年，物流の小口輸送化・多頻度輸送化が進み，小
口輸送・多頻度輸送を効率的に処理するための混載・
共同化輸送の取り組みが行われている．これらを効率
回数を制約とし，混載輸送費用と積替えターミナルに
おける費用の和を最小化する混載輸送ネットワークを
設計する問題に対する定式化および Lagrange 緩和問
題を示し，この緩和問題に対する解法を提案する．
混載輸送ネットワークは問題は，Less-Than- Truck-
的に実施するためには，混載輸送ネットワークの設計・
構築が重要な課題の一つとなっている．
混載輸送ネットワーク設計問題では，対象をどこま
でとするかによって様々なモデルを構築することがで
きる．一般的に，混載輸送ネットワーク設計問題 6) は，
1) 混載輸送路線設計，2) 貨物輸送経路設計，3) 空ト
ラック回送路線設計などの問題から構成されている．
考慮すべき費用としては，1) 混載輸送費用，2) ターミ
ナル費用，3) 空トラック回送費用などが挙げられる．
また，制約条件として，1) 混載輸送路線の最低便数制
約，2) 同一着地貨物の木制約，3) 積替えターミナルの
load (LTL) 問題として数多くの研究が行われている．
Powell-Sheffi6) ，Powell4) はアド・ドロップ型のヒュー
リスティック解法，Crainic–Roy1) は集合被覆問題を
用いた定式化と解法を示している．Roy-Delorme7) は
NETPLAN と事例分析を示し，Powell–Koskosidis5)
は勾配を用いたローカルサーチ法と最低便数制約に対
する Lagrange 緩和法を提案している．また，Hoppe–
Klample–McZeal–Rich2) は，ラベリング法とアド・ド
ロップ解法を組合わせた解法を提案している．
2.
定式化
処理能力制約，4) 発地・着地ターミナル間の積替え回
数や輸送時間制約，5) トラックの均衡制約などが挙げ
られる．
これらの組合せである混載輸送ネットワーク設計問
題は大規模で複雑な混合整数計画問題となり，すべて
輸送貨物の発地・着地ターミナルや積替えターミナ
ルを表すターミナル集合を N ，ターミナル間の混載輸
送路線の候補集合を A，ターミナル i に入る路線候補
の終点をもつターミナルの集合を Ni− ，ターミナル i か
の問題や条件を同時に考慮することは困難である．一
ら出る路線候補の始点をもつターミナルの集合を Ni+
方，一般的に組合せ最適化問題の最適解を求めるため
とする．路線 (i, j) の輸送費用を zij ，(i, j) を混載輸送
には分枝限定法などの解法が用いられ，そのために良
路線とするか否かを表す 0-1 変数を yij ，発地 o(∈ N )・
い下界値が必要となる．また，近似解法を用いる場合
着地 d(∈ N ) 間の貨物を路線 (i, j) で輸送するか否か
には，下界値を用いることによって，近似値と最適値
との差の上限を定めることができる．この下界値は，
を表す 0-1 変数を xod
ij とし，着地 d の貨物に対して路
d とする．
線 (i, j) で輸送するか否かを表す 0-1 変数を yij
緩和問題を最適に解くことによって求めることができ
ターミナル n が発地 o・着地 d 間の貨物の発地 o であ
る．一方，Lagrange 緩和解を初期解として実行可能解
れば-1，着地 d であれば 1，それ以外であれば 0 であ
を探索する Lagrange ヒューリスティック法を用いる
と，近似解を効率的に探索することが可能となる．
そこで，本研究では混載輸送路線設計と貨物輸送経
る定数を δnod とおく．ターミナル i における発地 o・着
地 d 間の貨物の単位当たりの積替え費用を hod
i ，路線
(i, j) の輸送車 1 便当りの費用を aij とする．路線 (i, j)
の輸送車 1 便当りの積載量を eij ，単位期間当りの最
キーワーズ：物流計画, ターミナル計画, 経路選択
*正員，工修, 流通経済大学流通情報学部
(竜ヶ崎市平畑 120,Tel0297-64-0001,[email protected])
低便数を fij とする．また，発地 o・着地 d 間の貨物量
を q od ，貨物の積換え回数の上限を pod とする．
このとき，本研究で対象とする混載輸送ネットワー
ク設計問題 LT L は，次のように表すことができる．
(LT L) min
+
i∈N
st
i∈Nn−
xod
in
−
j∈Ni+
d∈N
j∈Nn+
xod
nj
=
od od od
o∈N hi q xij (1)
d
yij
≤ yij
+
min
(i,j)∈A zij yij
j∈Ni+
i∈N
(i,j)∈A
+
δnod
n ∈ N, o ∈ N, d ∈ N
d
xod
ij ≤ yij
(LG)
+
(i,j)∈A zij yij
tod ≥ 0(o ∈ N, d ∈ N ) である．
d∈N {
d∈N [
d∈N
od
o∈N (vi
od
o∈N {vd
o∈N
od od
hod
i q xij
d d
− vjod + tod )xod
ij + wi yij }
− vood − (pod − 1)tod }
−
(2)
i∈N \{d}
wid ] (12)
(i, j) ∈ A, o ∈ N, d ∈ N
(3)
st (3)∼(4), (8)∼(11)
(i, j) ∈ A, d ∈ N
(4)
v ，w および t が与えられたときに目的関数の第 4
(5)
項は定数項となるので，LG は路線 (i, j) ごとの独立し
(6)
た問題 LGij に分割できる．
d
j∈N yij
≤ 1 i ∈ N \{d}, d ∈ N
d
j∈N ydj
=0
od
(i,j)∈A xij
d∈N
≤ pod − 1 o ∈ N, d ∈ N

od od

 aij /eij d∈N o∈N q xij
od od
zij =
if
d∈N
o∈N q xij ≥ fij eij


aij fij
xod
ij ∈ {0, 1}
otherwise
(7)
d
st xod
ij ≤ yij
(9)
d ∈ {0, 1}
yij
(i, j) ∈ A, d ∈ N
(10)
yij ∈ {0, 1}
(i, j) ∈ A
(11)
(1) 式の第 1 項は混載輸送便にかかる費用の合計，第
d∈N {
od od
o∈N (hi q
d d
+viod − vjod + tod )xod
ij + wi yij } (13)
(8)
(i, j) ∈ A
(i, j) ∈ A, o ∈ N, d ∈ N
(LGij ) min zij yij +
d ≤y
yij
ij
o ∈ N, d ∈ N
(14)
d∈N

od od

o∈N q xij
 aij /eij d∈N
od od
zij =
if
d∈N
o∈N q xij ≥ fij eij (15)


aij fij
xod
ij ∈ {0, 1}
otherwise
o ∈ N, d ∈ N
(16)
d∈N
(17)
2 項はターミナルにおける積替え費用の合計であり，こ
d ∈ {0, 1}
yij
れらの合計の最小化する．(2) 式はフロー保存条件で
yij ∈ {0, 1}
あり，与えられた貨物を発地・着地間に輸送すること
LGij は yij = 0 と yij = 1 の場合の 2 つの問題 LG0ij
を表す．(3) 式は，路線 (i, j) に着地 d 宛ての経路が開
設されないと発地 o，着地 d 間の貨物を路線 (i, j) で
輸送できないことを表す．(4) 式は，路線 (i, j) が開設
されないと着地 d 宛ての経路を路線 (i, j) に開設でき
ないことを表す．(5) 式と (6) 式は木制約であり，着地
以外のターミナルでは着地が同一である貨物が同一の
と LG1ij に分離でき，最適値は 2 つの問題の最適値の小
d = 0(d ∈ N )，
さい方となる．LG0ij では，明らかに yij
xod
ij = 0(o ∈ N, d ∈ N ) が最適となり，最適値は 0 と
なる．一方，LG1ij は次のように表される．
(LG1ij ) min zij +
路線 (i, j) の輸送量が最低便数の輸送量以上であれば
輸送量に比例した便数に設定し，未満であれば最低便
数に設定することを表す．(9)，(10) および (11) 式は
変数の 0-1 条件を表す．
3.
Lagrange 緩和問題
フロー保存式 (2) に対する Lagrange 乗数v ，木制約
d∈N {
od od
o∈N (hi q
d d
+viod − vjod + tod )xod
ij + wi yij }
ターミナル宛てに輸送されることを表す．(7) 式は，積
換え回数の制限を表す．(8) 式は最低便数制約であり，
st (14)∼(17)
(15) 式に注目すると，LG1ij は輸送量が最低便数以
1L
上と未満の場合の 2 つの問題 LG1U
ij ，LGij に分離す
ることができ，最適値は 2 つの問題の最適値の小さい
1L
方となる．LG1U
ij および LGij は，次のように表すこ
とができる．
(LG1U
ij ) min
式 (5)，(6) に対する乗数w，積換え回数制約式 (7) に
対する乗数tを用いて，LT L を Lagrange 緩和した問題
st
LG を作成する．ここで，wid ≥ 0(i ∈ N \{d}, d ∈ N )，
(14), (16), (17)
d∈N
o∈N
d∈N {
o∈N (aij q
od /e
ij
+ q od hod
i
d d
+viod − vjod + tod )xod
ij + wi yij }
q od xod
ij ≥ fij eij
(18)
(LG1L
ij ) min
st
d∈N {
o∈N (q
d = 0 の場合，xod = 0(o ∈ N ) が最適となり，最
yij
ij
od hod
i
d d
+viod − vjod + tod )xod
ij + wi yij }
d∈N
aij fij +
o∈N
q od xod
ij < fij eij
(19)
さらに，LG1U
ij において，Lagrange 乗数 uij (≥ 0) を
1U を作
用いて (18) 式を Lagrange 緩和した問題 LGRij
od
成する．ここで，Uijod = aij q od /eij + q od hod
i + vi −
+
−
tod
q od uij
φ1U
ij =
d∈N (
Uijod xod
ij
o∈N
おいて，Lagrange 乗数 sij (≥ 0) を用
1L を作成
いて，(19) 式を Lagrange 緩和した問題 LGRij
od od
od
od
od
od
する．ここで，Lod
ij = q hi + vi − vj + t + q sij
とおく．
d∈N (
o∈N
od
Lod
ij xij
d
+wid yij
) − fij eij sij (21)
となり，最適値は min{0, Uijod } となる．
U 1d の最適値が 0 であることを考慮すると，次
の LGRij
U 1d をまとめることができる．
のように LGRij
U 1d
(LGRij
)
min {
o∈N
d
min(0, Uijod ) + wid }yij
LGij の下界値は
解くことができ，最適解は
1U
LG0ij ，LGRij
および
1U
LGRij
d
yij
−
vood
−
U 1d の最適値は
となり，LGRij
min{0,
o∈N
min(0, Uijod ) + wid } となる．
の最適値 φ̂1U
ij は次のような変数を含まない式として表
1U
1L
(i,j)∈A min(0, φ̂ij , φ̂ij )
od
o∈N {vd
od
d
1 if
o∈N min{0, Uij } + wi ≤ 0
0 otherwise
1U
さらに，この最適値を (20) 式に代入すると，LGRij
値 LB は次のように表すことができる．
=
の
1U の最適値を
最適値の中の最小値となるため，LGRij
1L
1L
φ̂1U
ij ，LGRij の最適値を φ̂ij と置けば，LT L の下界
d∈N [
d の最小化問題であるので容易に
この問題は 1 変数 yij
st (14), (16), (17)
+
1 if Uijod ≤ 0
0 otherwise
d
st yij
∈ {0, 1}
1L
(LGRij
) min φ1L
ij = aij fij +
=
d = 0 の場合
この最適値を (23) 式に代入し，かつ yij
st (14), (16), (17)
LB =
解くことができ，その最適解は
xod
ij ∈ {0, 1}
st
この問題は 1 変数 xod
ij の最小化問題であるので容易に
xod
ij
d
+wid yij
) + fij eij uij (20)
min Uijod xod
ij
とおく．
1U
(LGRij
) min
同様に，LG1L
ij
U 1d はさらに発地 o ごとの
は定数項となるため，LGRij
独立した問題に分割できる．
(14), (16), (17)
vjod
d = 1 の場合，目的関数の第 2 項
適値は 0 になる．yij
現することができる．
(pod
−
−
1)tod }
d
i∈N \{d} wi ] (22)
φ̂1U
ij =
d∈N
min{0,
o∈N
min(0, Uijod ) + wid }
+fij eij uij
4.
Lagrange 緩和問題の解法
1L の最適値 φ̂1L は次のように表すこ
同様に，LGRij
ij
1U
v ，w，t，u および s が与えられたときに，LGRij
1L を最適に解くことができれば，LT L の
および LGRij
下界値 LB を求めることができる．
とができる．
φ̂1L
ij = aij fij +
U 1d
した問題 LGRij
U 1d
(LGRij
) min
d
st xod
ij ≤ yij
d ∈ {0, 1}
yij
に分割できる．
o∈N
o∈N
d d
Uijod xod
ij + wi yij
xod
ij ∈ {0, 1}
d∈N
min{0,
o∈N
min(0, Lod
ij )
+wid } − fij eij sij
1U の目的関数の第 2
uij が与えられたときに，LGRij
1U は着地 d ごとの独立
項は定数項となるので，LGRij
1L
LT L の下界値 LB は，最適値 φ̂1U
ij および φ̂ij を (22)
式に代入することによって求めることができる．なお，
(23)
o∈N
緩和問題の最適解 yij は次のようになる．
yij =
1L
1 if φ̂1U
ij ≤ 0 or φ̂ij ≤ 0
0 otherwise
5.
Lagrange 乗数の設定
以上のように，LG の解から劣勾法によって La-
問題 LT L の良い下界値を求めるためには，緩和問
題の目的関数 (12)，(20) および (21) 式の値を最大に
するように Lagrange 乗数を設定する必要がある．ま
ず，v ，w および t が与えられたときの u および s の
1U を u に関する問題と
設定法を示す．ここで，LGRij
ij
grange 乗数 v ，w および t を更新し，u および s を
求め，LG を解いて y および x を求め直すという手順
を繰り返すことによって，LT L の下界値を改善してい
くことができる．
6.
おわりに
して整理しておく．
maxuij ≥0
+
d∈N {
(fij eij −
od
o∈N (aij q /eij
+viod
−
本研究では，混載輸送路線設計と貨物輸送経路設計
d∈N
vjod
o∈N
+
q od xod
ij )uij
q od hod
i
+t
od
)xod
ij
を扱い，路線の最低便数，木条件および積換え回数を
制約とし，混載輸送費用と積替え費用の和を最小にす
d
+ wid yij
}
この問題は 1 変数 uij に関する最大化問題であるが，
uij の値によって最適解 y および x が離散的に変化す
るので，微分不可能な目的関数をもつ問題となる．し
かし，uij に関する凸問題となるため，目的関数値を
最大にする uij は 2 分探索を用いて設定することがで
きる．uij の探索の範囲は，uij に関する劣勾配によっ
て限定することができる．sij の場合も同様である．
る混載輸送ネットワーク設計を対象とした．この問題
に対して定式化を行い，フロー保存式，木条件および
積換え回数制約を Lagrange 緩和した問題を示した．こ
の Lagrange 緩和問題は路線ごと，着地ごと，発地ご
との問題に分割することができ，分割した問題が 0 と
係数値との比較によって容易に解くことができること
を示した．また，Lagrange 乗数が 2 分探索法および劣
勾配法によって設定できることを示した．
一方，v ，w および t を設定する方法として，標準
緩和問題の解法を提案したが，最適解や良い近似解
的な劣勾配法 3) を利用する．v ，w と t に対する劣勾
を求めることが本来の目的であり，劣勾配法を行うた
配をそれぞれ次のように定義する．ここで，ノード i
が発地 o・着地 d 間の貨物の着地 d であれば 0，それ
以外であれば 1 である定数を ∆di とおく．
od
pod
n = δn −
i∈Nn−
xod
in +
j∈Nn+
xod
nj
n ∈ N, d ∈ N, o ∈ N
めには良い上界値が必要である．したがって，今後，
効率的な Lagrange ヒューリスティック解法やタブー
サーチ法などのメタ解法を開発する必要がある．
参考文献
1) Crainic, T. G. and Roy, J.: Design of Regular Intercity
Driver Routes for the LTL Motor Carrier Industry,
d
i ∈ N, d ∈ N
rid = −∆di + j∈N yij
Transportation Science, Vol. 26.pp280–295,1992.
2)
Hoppe, B., Klampfl, E. Z., McZeal, C. and Rich, J.:
d ∈ N, o ∈ N
q od = −pod + 1 + (i,j)∈A xod
ij
Strategic Load-Planning for Less-Than-Truckload
Trucking, Technical Report CRPC-TR99812-S, Cenv，w と t が与えられたとき，y ，x，p，r および q が
ter for Research on Parallel Computation, Rice University, 1999.
求められたとする．このとき，次の v ，w，t として，
3) 久保幹雄, 田村明久, 松井知己：応用数理計画ハンドブッ
ク, 朝倉書店, 2002.
vnod := vnod + θ k pod
n ∈ N, o ∈ N, d ∈ N
n
4)
Powell, W. B.: A local Improvement Heuristic for the
wid + θ k rid
if i = d, d ∈ N
Design of Less-Than-Truckload Motor Carrier Netwid :=
max(0, wid + θ k rid ) otherwise
works, Transportation Science, Vol. 20, pp246–257,
1986.
od
od
k
od
t := max(0, t + θ q ) o ∈ N, d ∈ N
5) Powell, W. B. and Koskosidis, I. A.: Shipment Routing Algorithms with Tree Constraints, Transportation
を採用する．ここで，θ k は，k 回目の繰り返しにおけ
Science, Vol. 26, pp230–245, 1992.
るステップサイズであり，次のように定義される．
6) Powell, W. B. and Sheffi, Y.: Design and Implementation of an Interactive Optimization System for Netρ(上界値 − 下界値)
(24)
θ k := work design in the Motor Carrier industry, Operations
od
2
d
2
od
2
d∈N
o∈N { n∈N (pn ) + (ro ) + (q ) }
Research, Vol. 37, pp12–29, 1989.
k
limk→∞ θ k → 0 and ∞
7) Roy, J. and Delorme, L.: NETPLAN: A Netk=0 θ → ∞
work Optimization Model for Tactical Planning in
ここで，ρ は (0, 2) のパラメータ，下界値は (k − 1) 回
the Less-Than-Truckload Motor-Carrier Industry, INFOR, Vol. 27, pp22–35, 1989.
目の下界値 LB である．ただし，上界値は別途求める
必要がある．