4.4　演習３

　4.4.1　問題１

　実際の問題規模は、その業種および会社の規模によって様々であるが、 大規模な問題では、1日に配送する需要地数が500を超える場合もしばしば見受けられる。 しかし、このような大規模な問題を授業時間内で検討することは難しいので、 規模を小さくした課題をセービング法を使用して解く。

＜本演習の目的関数＞
総走行距離最小化

　4.4.1.1　問題1-1

＜本演習の制約条件＞
  1. 配送センター(デポ)は一ヶ所である
  2. 各需要地の需要は全て満たされる
  3. 配送センター（デポ）及び需要地間の距離はユークリッド距離で与えられる
  4. 配送センター（デポ）及び各需要地間の距離は表の通りである
  5. 各需要地の需要量と座標は表の通りである
  6. 各トラックは出発した配送センター（デポ）に必ず戻る
  7. 各トラックの走行可能距離は100である
  8. 各トラックの積載可能量は65である
  9. 使用できるトラックは4台である
＜本演習の終了条件＞
全ての制約条件を満たした上で、総走行距離が270以下になること

＜配送センターと需要地間の距離＞
表　配送センターと需要地間の距離
  ﾃﾞﾎﾟ A B C D E F G H I J K L M N O
ﾃﾞﾎﾟ                                
A 25                              
B 34 44                            
C 15 40 30                          
D 29 54 46 18                        
E 16 40 44 15 15                      
F 27 50 28 12 20 25                    
G 11 17 30 23 39 27 33                  
H 20 45 31 5 15 17 8 28                
I 20 35 14 16 34 29 18 19 19              
J 7 28 27 12 29 19 21 11 17 12            
K 41 15 57 56 69 54 66 33 61 51 44          
L 32 6 48 46 61 46 56 23 51 41 34 9        
M 16 37 22 8 26 22 13 19 11 8 9 53 43      
N 27 53 42 14 5 16 15 37 11 30 26 68 59 22    
O 17 27 18 21 39 31 26 12 25 8 11 42 32 13 35  

＜各需要地の需要量と座標＞
表　各需要地の需要量と座標
  需要量 Ｘ座標 Ｙ座標
デポ − 30 30
Ａ 17 46 10
Ｂ 11 2 10
Ｃ 3 16 37
Ｄ 11 15 55
Ｅ 6 28 46
Ｆ 8 4 38
Ｇ 16 31 19
Ｈ 26 12 40
Ｉ 29 12 21
Ｊ 17 23 27
Ｋ 5 59 1
Ｌ 9 50 5
Ｍ 2 14 29
Ｎ 20 12 51
Ｏ 13 19 16