0
$\begingroup$

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?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.