Answer to Question #194466 in Operations Research for shufer

Question

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 

1. a. Determine the optimal assignment that will minimize the total distance travelled.
2. b. Compute the total minimum distance of the optimal assignment. 

Answer 1

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