A dispatcher for a City’s Taxi Association has five taxi cabs at different locations and four customers who have called for transportation service. The distance (in km) from each taxi’s present location to each customer is shown in the following table. (3 points)
Cab
Customer I II III IV A 7 2 4 10 B 5 1 5 6 C 8 7 6 5 D 2 5 2 4 E 3 3 5 8
Consider driver C. He is as far away as possible from 1, 2, 3 passengers. For minimization, he either does not participate (point a) or only participates for 4 (for the rest, you can find a closer driver) (point b).
For point b where there are 3 passengers and 4 drivers, the minimum 2 + 1 + 2 is obviously not reached, since all the numbers are integers, then the attainable minimum should be 6, it is reached at 3 + 1 + 2, that is, the final minimum for point b 3+ 1 + 2 + 5 = 11 (1E, 2B, 3D, 4C).
For point a, we have 4 drivers and 4 passengers left. Consider driver A, he cannot drive 1 and 4 drivers, since the sum will obviously be more than in point b (for 1 more than 7 + 1 + 2 + 4 = 14 for 4 more than 2 + 1 + 2 + 10 = 15) consider driver E, he cannot drive 4 for a similar reason (more than 2 + 1 + 2 + 8 = 13) and for driver B 4 the problem (more than 11 (2 + 1 + 2 + 6 = 11 but this case is not achievable)) ...
So the 4th passenger can only be driven by driver D. For the remaining 3 passengers and 3 drivers
minimum 3 + 1 + 4 = 8
and for point a the minimum value is 12. So the final minimum is 11 and the distribution is 1E, 2B, 3D, 4C
Comments
Leave a comment