  Task allocation problems have traditionally focused on cost optimization.
However, more and more attention is being given to cases in which cost should
not always be the sole or major consideration. In this paper we study a fair
task allocation problem in transportation where an optimal allocation not only
has low cost but more importantly, it distributes tasks as even as possible
among heterogeneous participants who have different capacities and costs to
execute tasks. To tackle this fair minimum cost allocation problem we analyze
and solve it in two parts using two novel polynomial-time algorithms. We show
that despite the new fairness criterion, the proposed algorithms can solve the
fair minimum cost allocation problem optimally in polynomial time. In addition,
we conduct an extensive set of experiments to investigate the trade-off between
cost minimization and fairness. Our experimental results demonstrate the
benefit of factoring fairness into task allocation. Among the majority of test
instances, fairness comes with a very small price in terms of cost.
