OR 7310 Logistics, Warehousing, and Scheduling
Fall 2023, Homework 4 Solutions
Problem 1.
𝑠
12
=
𝑐
01
+
𝑐
02
-
𝑐
12
=20+75-35=60
𝑠
13
=
𝑐
01
+
𝑐
03
-
𝑐
13
=20+33-5=48
𝑠
14
=
𝑐
01
+
𝑐
04
-
𝑐
14
=20+10-20=10
𝑠
15
=
𝑐
01
+
𝑐
05
-
𝑐
15
=20+30-15=35
𝑠
23
=
𝑐
02
+
𝑐
03
-
𝑐
23
=75+33-18=90
𝑠
24
=
𝑐
02
+
𝑐
04
-
𝑐
24
=75+10-58=27
𝑠
25
=
𝑐
02
+
𝑐
05
-
𝑐
25
=75+30-42=63
𝑠
34
=
𝑐
03
+
𝑐
04
-
𝑐
34
=33+10-40=3
𝑠
35
=
𝑐
03
+
𝑐
05
-
𝑐
35
=33+30-20=43
𝑠
45
=
𝑐
04
+
𝑐
05
-
𝑐
45
=10+30-25=15
Rank the customer pairs in decreasing order of their savings values: (2, 3); (2, 5); (1, 2); (1, 3); (3,
5); (1, 5); (2, 4); (4, 5); (3, 4)
First, link customer 2 and 3, getting the miles of 75+33+18=126 less than 250, which is feasible.
Then try to combine 2 and 5, equals to include customer 5 in the same route, getting
75+18+20+30=143 (0-2-3-5-0) or 30+42+18+33= 123 (0-5-2-3-0), take the second one which is
still feasible.
Try to combine 1 and 2, equals to include customer 1 in the same route, getting
20+15+42+18+33= 128 (0-1-5-2-3-0) or 30+42+18+5+20= 115 (0-5-2-3-1-0), take the second
one.
Finally try to include customer 4 into the route, getting 10+25+42+18+5+20= 120 (0-4-5-2-3-1-0)
or 30+42+18+5+20+10= 125(0-5-2-3-1-4-0)
The final route is 0-4-5-2-3-1-0 and the total cost is 120.
