I have $n$ drivers, each one has a balance (in Us dollars), availability status (true if he is not working already) and number of accomplished tasks in the current month.
And I have an estimated number $m$ tasks (rides) per month, each task has a cost (wage) and a type (long ride, short ...). The tasks come one at a time (online).
When a task comes, I have to match it in time to one of the available drivers, according to the following criteria:
- the matching algorithm has to be fair. i.e in the end of the month the balances of the drivers has to be close to each other.
- If the algorithm has to choose between 2 drivers with equal balances it has to be the one with the least number of rides in the current month.
- Tasks are assigned to available drivers only.
In the beginning I thought of a greedy solution which assigns the task to the driver with the least balance. But I realised that it does not work in case the cost of the task is not significant and won't add much to the least driver.
E.g : let's say we have 2 available drivers A(100usd) and B(700usd), and then a 50usd task T1 came, then a 500Usd task one t2.the gready algorithm will assign T1 to A make him busy for quite some time and then the T2 will be assigned to B. Having this the balance gap will be greater.
Can this problem be modeled by a bipartite online matching problem. What is the best solution in this case?
