Question

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.

Answer 1

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

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