There are four taxicabs A-D and three customers (1-3). Assign a taxi for each customer such that the average waiting time per customer is minimized. This exercise is about local search, so use hill climbing (slides)

 .

Do iterations of hill climbing with pen and paper, or a spreadsheet, until the search stops (

1. write down all the neighbor states of current state
2. calculate the total waiting time for each state
3. select the state with lowest waiting time as the new current state

Start state:

A -> 1
B -> 2
C -> 3
D -> free

We generate neighbors by swapping two taxis in the current state, for example A -> 3 ja C -> 1.

Because the number of customers is constant, you can use total waiting time everywhere - if a state has minimal total waiting time it also has minimal average waiting time.

Waiting times for each taxi and customer:

      1   2   3
A    17  25  10
B    14  12   8
C     8   7   6
D    12   2   7