Question

1.       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. Find the optimal assignment of taxis to customers so as to minimize total driving distances to the customers. Please show all steps/work

Cab site	Customer
	A	B	C	D
Stand 1	8	3	4	8
Stand 2	5	4	6	7
Stand 3	7	7	9	6
Stand 4	8	6	6	4

Answer 1

This is an integer programming question.

Let a₁, a₂, a₃, a₄ be the cases where Customer A is assigned Stand 1, 2, 3, 4 respectively. Since customer will go in only one taxi, only one of a₁, a₂, a₃, a₄ will be equal to 1, rest 3 will be equal to 0

Let b₁, b₂, b₃, b₄ be the cases where Customer B is assigned Stand 1, 2, 3, 4 respectively. Since customer will go in only one taxi, only one of b₁, b₂, b₃, b₄  will be equal to 1, rest 3 will be equal to 0

Let c₁, c₂, c₃, c₄ be the cases where Customer C is assigned Stand 1, 2, 3, 4 respectively. Since customer will go in only one taxi, only one of c₁, c₂, c₃, c₄ will be equal to 1, rest 3 will be equal to 0

Let d₁, d₂, d₃, d₄ be the cases where Customer D is assigned Stand 1, 2, 3, 4 respectively. Since customer will go in only one taxi, only one of d₁, d₂, d₃, d₄ will be equal to 1, rest 3 will be equal to 0

The objective function is to minimize the distance between the customer and the stand -

Min Z = 8a₁ + 5a₂ + 7a₃ + 8a₄ + 3b₁ + 4b₂ + 7b₃ + 6b₄ + 4c₁ + 6c₂ + 9c₃ + 6c₄ + 8d₁ + 7d₂ + 6d₃ + 4d₄

Constraints -

a₁ + a₂ + a₃ + a₄ = 1 .. constraint on Customer A choosing one taxi stand

b₁ + b₂ + b₃ + b₄ = 1 .. constraint on Customer B choosing one taxi stand

c₁ + c₂ + c₃ + c₄ = 1 .. constraint on Customer C choosing one taxi stand

d₁ + d₂ + d₃ + d₄ = 1 .. constraint on Customer D choosing one taxi stand

a₁ + b₁ + c₁ + d₁ = 1 .. constraint on Stand 1 selected for a customer

a₂ + b₂ + c₂ + d₂ = 1 .. constraint on Stand 2 selected for a customer

a₃ + b₃ + c₃ + d₃ = 1 .. constraint on Stand 3 selected for a customer

a₄ + b₄ + c₄ + d₄ = 1 .. constraint on Stand 4 selected for a customer

a₁, a₂, a₃, a₄, b₁, b₂, b₃, b₄, c₁, c₂, c₃, c₄, d₁, d₂, d₃, d₄ <=1

Let us solve this using Excel Solver -

Let none of the taxi stands be selected inititally (indicated in grey cells)

We will need to calculate the values in the grey cells to minimize the cost. Put in the constraints and solve to get -

Hence, Customer A should be assigned Taxi from Stand 2, Customer B should be assigned taxi from Stand 2, Customer C should be assigned taxi from Stand 1 and Customer D should be assigned taxi from Stand 4 to minimize the total distance to 19 miles