I having trouble finding some starting points for solving an occupancy problem which seems like a good candidate for ai.
Assume the following situation: In a company I have n cars and m employees. Not every employee can drive any car (f. e. a special driving license is required). A car can only be used by one employee at a specific point in time.
There is a plan which states which employee must be somewhere within some time (therefor they must use a car, so the car is blocked for that amount of time).
The goal is to find a near optimal occupancy of the cars according to that plan.
This problem is easy to specify, but I'm stumped as to which methods to implement.
As it can be represented by a graph I think the right way to solve such a problem is using searching techniques, but a problem here is that I don't know the goal state (and there is no efficient way to compute it - thats the task I want the ai to do...). Neither finding the goal state is in fact part of the problem.
So my question is: What ai techniques could be used to solve such a problem ?
Edit: Some clarification:
Assmume we have two sets - one of the employees (E) and one of cars (C). |C| < |E| is most likely true.
Each car has an assigned priority which corresponds to the costs of using it (for example using a Ferrari costs more than using a Dacia, therefore a Dacia has a higher priority (ex. 1) compred to the Ferrari (ex. 10))).
Assume further that having employees which are not using a car at a specific time slice are a bad thing - they cost an individual penalty (you want the employeed to be at the customer and sell things etc.).
The goal is to find the occupation of employees and cars which has a low total cost.
One Example: If you assign an employee to a car at a specific time slice it may turn out that another employee gets no car within that time slice. This can be either because
- a car is free, but he has no license for it
- because a car is free, but the costs of using this car would be higher than having the employee staing at the head quater
- because no car is free anymore
Of cause it could be better in terms of costs to change the occupation and give that employee which got no car in this solution a car and therefore having another employee getting no car or not using all cars or ...
Note: There is no need to find an exact optimal solution (=lowest total cost of all possible occupations), as this would require checking out all possible occupations of the exponential solution space. Insetad finding a more or less good approximation of a near-optimal low total cost is sufficent.