Two applications of the shortest path problem

ロジスティクス工学
第6章
動的ロットサイズ決定モデル
東京商船大学
久保 幹雄
Wagner-Whitin(ワグナー・ウィッティン)モデル
動的ロットサイズ決定モデルの古典
例題
在庫費用 = 1円/(個・日)
期(日)
発注固定費用 (円)
1
3
2
3
3
3
4
3
5
3
発注変動費用 (円/個) 1
1
3
3
3
需要量(個) 5
7
3
6
4
仮定:
1. 需要は期(日)によって変動する(動的)
2. 品切れは許さない
3. 初期在庫は 0.
4. 総費用(発注固定費用+発注変動費用+在庫費用)の最小化
Network representation of the
DLSP
Ordering cost
1
1
1
Demand
5
3
1
7
3
3
1
3
1
6
4
Shortest path network
Let Cij of the distance of the SP network be the cost of ordering
at period i+1 satisfying the demands through period i+1 to j.
Node 0 is a dummy node.
0
1
2
3
4
5
Then, solve the shortest path problem using Dijkstra’s algorithm.
Vehicle routing problem
(route-first/cluster second algorithm)
距離行列
0 1 5 4 5
1 0 4 5 6
5 4 0 8 9
4 5 8 0 2
5 6 9 2 0
2 2 7 4 4
3 3 7 5 4
2
2
7
4
4
0
1
3
3
7
5
4
1
0
Capacity of the vehicle is 4.
Each customer has a unit demand.
1
6
0
5
4
3
2
Find a giant tour by solving the
traveling salesman problem
2
1
6
0
5
4
3
Shortest path network
Let Cij of the distance of the SP network be the cost of visiting
customers i+1, i+2,...,j in the order of the given giant tour if the
total demand of these customers does not exceed the capacity of the
vehicle.
Again, 0 is a dummy node.
0
1
2
3
4
5
6
Then, solve the shortest path problem using Dijkstra’s algorithm.