Fair task allocation in transportation

Qing Chuan Ye, Yingqian Zhang, Rommert Dekker

Abstract

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.

Introduction

In modern logistics, particularly within Inter-Terminal Transport (ITT) hubs like the Port of Rotterdam, task allocation has traditionally been driven by cost minimization. However, a strict "winner-takes-all" approach—where the cheapest company always receives the work—can lead to market "starvation." Smaller or slightly more expensive participants are consistently excluded, eventually shrinking the pool of available carriers and reducing system resilience. To address this, we propose a framework for Max-min Fair Minimum Cost Allocation (MFMCA), which balances operational efficiency with equitable work distribution.

Problem Formulation

The MFMCA problem aims to maximize the total number of completed tasks, distribute them as evenly as possible among heterogeneous companies (considering their varying capacities and costs), and finally minimize the total cost of this fair distribution. This requires handling complex constraints where fairness and cost-minimization often conflict.

Example of a task allocation problem instance across multiple time points and companies.

As illustrated in the table above, different companies ($k_n$) face different costs for the same jobs ($j_m$) at various time points. A fair allocation must navigate these differences to ensure no company is unfairly sidelined while keeping total costs manageable.

Methodology

We solve the MFMCA problem using two novel polynomial-time algorithms that treat the challenge as a two-level optimization problem:

  1. Iterative Max Flow (IMaxFlow): This algorithm addresses the fairness component using a "progressive filling" technique to lexicographically maximize the fairness vector. By incrementally increasing company capacities and running a max-flow algorithm at each step, it ensures that companies with the fewest jobs receive as many as possible before others.
  2. FairMinCost: Once the fair distribution is set, this algorithm finds the least expensive assignment. It utilizes a modified flow network with horizontal dummy layers. By introducing "dummy jobs" with zero cost, the system can apply standard minimum-cost maximum-flow techniques to find the optimal assignment that respects the fairness constraints established in the first stage.

Experimental Evaluation

We evaluated our approach using synthetic datasets modeled after real-world operations at the Port of Rotterdam, involving 250 jobs and 50 companies over a 10-hour window. We tested various scenarios crossing competition levels with cost structures (homogeneous vs. heterogeneous).

Key Results

  • The Price of Fairness (POF): In scenarios with homogeneous costs, the POF—the additional cost incurred by prioritizing fairness—was minimal, ranging from 0% to 2.42%. In highly heterogeneous scenarios, the POF reached up to 17.27%, representing the "tax" required to maintain a diverse and resilient bidder market.
  • Scalability: The algorithms are computationally efficient, with the first stage solving in $O(J^4 K^3 T^3)$ time, making them suitable for real-time industrial applications.
  • Distribution Quality: Visual analysis confirmed that the "Fair" solution produced significantly smoother allocation curves than traditional "Min-cost" methods, which often left many participants with zero work.

Conclusion

This research demonstrates that fairness in logistics does not have to come at a prohibitive cost. By framing fairness as a sustainability tool, ports can maintain a robust ecosystem of carriers without needing to maintain their own dedicated fleets. Future work will explore combinatorial bidding and mechanism design to ensure truthful participation in these fair allocation systems.

Summary updated

Abstract

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.
BibTeX
@inproceedings{ye2016fair,
  author = {Qing Chuan Ye and Yingqian Zhang and Rommert Dekker},
  title = {{Fair task allocation in transportation}},
  booktitle = {Omega},
  year = {2016},
  doi = {10.1016/j.omega.2016.05.005},
}
Figure