Vehicle Dispatching in a Car Rental Company

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.

Island of Crete

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.

Current Stock181382025133112829
Requested Stock922183014812152421
Available and requested vehicles at locations
Transfer distances (in km) between locations