A car rental company in Crete operates 10 branches located throughout the island. Customers can collect a car at a certain branch and return it at any of the branches.
The dispatcher has the task to plan every evening the overnight transfers of the vehicles between the branches in order to have the requested numbers of cars at every branch on the next morning. The transfers have to be planned in such a way that the total number of traveled kilometers is as small as possible.
The following information is available to the dispatcher: the number of cars at every branch in the evening and the number of requested cars at every branch on the next morning. For simplicity, let us assume that all vehicles are of the same type. Further, the dispatcher has a table of distances (in km) between branches at his disposal.
| Branch | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| Current Stock | 18 | 13 | 8 | 20 | 25 | 13 | 31 | 12 | 8 | 29 |
| Requested Stock | 9 | 22 | 18 | 30 | 14 | 8 | 12 | 15 | 24 | 21 |
