Below is a table of times for Taxis A to H to reach Customer

Below is a table of times for Taxis (A to H) to reach Customers (1 to 8) who need a ride home after a night on the town. The goal is to Minimize the time it takes for all of the Taxis to reach their Customers. Only one Taxi will be sent to each Customer and each Customer needs only one Taxi.

The optimal solution to this problem requires the following:


Taxi A picks up Customer

Taxi B picks up Customer

Taxi C picks up Customer

Taxi D picks up Customer

Taxi E picks up Customer

Taxi F picks up Customer

Taxi G picks up Customer

Taxi H picks up Customer

Minimum Cost =

Hint: Your cost should be between 43 and 48

Solution

This is the original cost matrix:

Subtract row minima

We subtract the row minimum from each row:

Subtract column minima

We subtract the column minimum from each column:

Cover all zeros with a minimum number of lines

There are 7 lines required to cover all zeros:

Create additional zeros

The number of lines is smaller than 8. The smallest uncovered number is 2. We subtract this number from all uncovered elements and add it to all elements that are covered twice:

Cover all zeros with a minimum number of lines

There are 7 lines required to cover all zeros:

Create additional zeros

The number of lines is smaller than 8. The smallest uncovered number is 1. We subtract this number from all uncovered elements and add it to all elements that are covered twice:

Cover all zeros with a minimum number of lines

There are 8 lines required to cover all zeros:

The optimal assignment

Because there are 8 lines required, the zeros cover an optimal assignment:

This corresponds to the following optimal assignment in the original cost matrix:

The optimal value equals 47.

Taxi A picks up Customer 4

Taxi B picks up Customer 1

Taxi C picks up Customer 7

Taxi D picks up Customer 8

Taxi E picks up Customer 6

Taxi F picks up Customer 2

Taxi G picks up Customer 5

Taxi H picks up Customer 3