The Green Cab Company has a taxi waiting at each of four cabstands in Evanston,
ID: 361453 • Letter: T
Question
The Green Cab Company has a taxi waiting at each of four cabstands in Evanston, Illinois. Four customers have called and requested service. The distances, in miles, from the waiting taxis to the customers are given in the following table.
Customer
Cab Site
A
B
C
D
Stand 1
99
55
66
55
Stand 2
77
66
88
77
Stand 3
88
99
55
88
Stand 4
88
88
99
66
The optimal assignment of taxis to customers that minimizes the distance
is:
Customer A
right arrow
Stand 3
Stand 2
Stand 4
Stand 1
Customer
Cab Site
A
B
C
D
Stand 1
99
55
66
55
Stand 2
77
66
88
77
Stand 3
88
99
55
88
Stand 4
88
88
99
66
Explanation / Answer
The given problem is assignment problem and is solved by Hungarian method as follows:
Customers
Cab Site
A
B
C
D
Row Minima
Stand 1
99
55
66
55
55
Stand 2
77
66
88
77
66
Stand 3
88
99
55
88
55
Stand 4
88
88
99
66
66
Step 1: Matrix reduction
First do row reduction: From each row select lowest element and subtract lowest element from each element of row, matrix obtained is as follows:
Cab Site
A
B
C
D
Stand 1
44
0
11
0
Stand 2
11
0
22
11
Stand 3
33
44
0
33
Stand 4
22
22
33
0
Column Minima
11
0
0
0
Next conduct Column reduction: if any of the column does not include zero, then only do this step. Select lowest element from each column and subtract this element form each element of the column. Reduced column distance matrix is as shown below:
Customer
Cab Site
A
B
C
D
Stand 1
33
0
11
0
Stand 2
0
0
22
11
Stand 3
22
44
0
33
Stand 4
11
22
33
0
Step 2:
Conduct Assignment: in each row or column identify individual zero and assign it to that row or column. If the zero is assigned in row, then cross the other zero in the assigned column and vice versa. Continue till all zeros are marked.
The assignment is shown in following table:
The green color cell represents assignment and red color cell represents elimination for assignment.
Sr. No.
Assignment cell
Elimination Cell
1
3-C
2
4-D
1-D
3
1-B
2-B
4
2-A
Number of assignment = 4
Number of assignee = number of assignment = 4
As number of assignments is equal to number of assignee, optimal solution is reached.
The optimal assignment and cost is as shown below:
Customer
Sites
Distance
A
2
55
B
1
77
C
3
55
D
4
66
Total cumulative Distance
253 miles
Customers
Cab Site
A
B
C
D
Row Minima
Stand 1
99
55
66
55
55
Stand 2
77
66
88
77
66
Stand 3
88
99
55
88
55
Stand 4
88
88
99
66
66
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.