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?


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.