Suppose that one wishes to schedule vehicles from a central depot to five customer locations. The distance of making trips between each pair of locations is given in the following matrix. (The trip distances are symmetrical and the depot is location 0 below). 0 1 2 3 4 5 0 0 20 75 33 10 30 1 0 35 5 20 15 2 0 18 58 42 3 0 40 20 4 0 25 5 0 Assume that each vehicle is constrained to travel no more than 50 miles on each route (for example they are electric and need to return to the depot to be recharged at least every 50 miles of travel). Find the routing suggested by the savings method.

Question

Suzy

Mathematics

10 February, 04:49

Suppose that one wishes to schedule vehicles from a central depot to five customer locations. The distance of making trips between each pair of locations is given in the following matrix. (The trip distances are symmetrical and the depot is location 0 below). 0 1 2 3 4 5 0 0 20 75 33 10 30 1 0 35 5 20 15 2 0 18 58 42 3 0 40 20 4 0 25 5 0 Assume that each vehicle is constrained to travel no more than 50 miles on each route (for example they are electric and need to return to the depot to be recharged at least every 50 miles of travel). Find the routing suggested by the savings method.

+2

Answers (1)

Know the Answer?

Davion · Answer 1

The routing suggested by the savings method is route (3,4)

Step-by-step explanation:

Savings for all trips (i, j), 1 ≤ i ∠ j ≤ 5

Total number of trips to be commuted = 10 trips

S₁₂ = C₀₁ + C₀₂ - C₁₂ = 20 + 75 - 35 = 60

S₁₃ = C₀₁ + C₀₃ - C₁₃ = 20 + 33 - 5 = 48

S₁₄ = C₀₁ + C₀₄ - C₁₄ = 20 + 10 - 20 = 10

S₁₅ = C₀₁ + C₀₅ - C₁₅ = 20 + 30 - 15 = 35

S₂₃ = C₀₂ + C₀₃ - C₂₃ = 75 + 33 - 18 = 90

S₂₄ = C₀₂ + C₀₄ - C₂₄ = 75 + 10 - 58 = 27

S₂₅ = C₀₂ + C₀₅ - C₂₅ = 75 + 30 - 42 = 63

S₃₄ = C₀₃ + C₀₄ - C₃₄ = 33 + 10 - 40 = 3

S₃₅ = C₀₃ + C₀₅ - C₃₅ = 33 + 30 - 20 = 43

S₄₅ = C₀₄ + C₀₅ - C₄₅ = 10 + 30 - 25 = 15