OASIcs.ATMOS.2023.17.pdf
- Filesize: 0.49 MB
- 6 pages
Document
Optimizing Fairness over Time with Homogeneous Workers (Short Paper)
Authors
-
Part of:
Volume:
23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023)
Series: Open Access Series in Informatics (OASIcs)
Conference: Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2023-08-31
Cite As Get BibTex
Bart van Rossum, Rui Chen, and Andrea Lodi. Optimizing Fairness over Time with Homogeneous Workers (Short Paper). In 23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023). Open Access Series in Informatics (OASIcs), Volume 115, pp. 17:1-17:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/OASIcs.ATMOS.2023.17
Abstract
There is growing interest in including fairness in optimization models. In particular, the concept of fairness over time, or, long-term fairness, is gaining attention. In this paper, we focus on fairness over time in online optimization problems involving the assignment of work to multiple homogeneous workers. This encompasses many real-life problems, including variants of the vehicle routing problem and the crew scheduling problem. The online assignment problem with fairness over time is formally defined. We propose a simple and interpretable assignment policy with some desirable properties. In addition, we perform a case study on the capacitated vehicle routing problem. Empirically, we show that the most cost-efficient solution usually results in unfair assignments while much more fair solutions can be attained with minor efficiency loss using our policy.
Subject Classification
ACM Subject Classification
- Mathematics of computing → Combinatorial optimization
Keywords
- Fairness
- Online Optimization
- Combinatorial Optimization
- Vehicle Routing
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
Andrea Lodi, Philippe Olivier, Gilles Pesant, and Sriram Sankaranarayanan. Fairness over time in dynamic resource allocation with an application in healthcare. Mathematical Programming, 2022.
- Andrea Lodi, Sriram Sankaranarayanan, and Guanyi Wang. A framework for fair decision-making over time with time-invariant utilities, 2022. URL: https://arxiv.org/abs/2212.10070.
-
Piotr Matl, Richard F Hartl, and Thibaut Vidal. Workload equity in vehicle routing: The impact of alternative workload resources. Computers & Operations Research, 110:116-129, 2019.
-
Diego Pecin, Artur Pessoa, Marcus Poggi, and Eduardo Uchoa. Improved branch-cut-and-price for capacitated vehicle routing. Mathematical Programming Computation, 9:61-100, 2017.
-
Tareq Si Salem, Georgios Iosifidis, and Giovanni Neglia. Enabling long-term fairness in dynamic resource allocation. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 6(3):1-36, 2022.
- Man Yiu Tsang and Karmel S. Shehadeh. A unified framework for analyzing and optimizing a class of convex inequity measures, 2022. URL: https://arxiv.org/abs/2211.13427.
-
Eduardo Uchoa, Diego Pecin, Artur Pessoa, Marcus Poggi, Thibaut Vidal, and Anand Subramanian. New benchmark instances for the capacitated vehicle routing problem. European Journal of Operational Research, 257(3):845-858, 2017.
-
Bart van Rossum, Twan Dollevoet, and Dennis Huisman. Dynamic railway crew planning with fairness over time. Technical Report EI 2022-10, Economometric Institute, Erasmus University Rotterdam, 2022.