Distributionally Robust Fair Transit Resource Allocation During a Pandemic
46 Pages Posted: 29 Jun 2021 Last revised: 8 Apr 2022
Date Written: June 26, 2021
Abstract
This paper studies Distributionally robust Fair transit Resource Allocation model (DrFRAM) under Wasserstein ambiguity set to optimize the public transit resource allocation during a pandemic. We show that the proposed DrFRAM is highly nonconvex and nonlinear and is, in general, NP-hard. Fortunately, we show that DrFRAM can be reformulated as a mixed-integer linear programming (MILP) by leveraging the equivalent representation of distributionally robust optimization and monotonicity properties, binarizing integer variables, and linearizing nonconvex terms. To improve the proposed MILP formulation, we derive stronger ones and develop valid inequalities by exploiting the model structures. Besides, we develop scenario decomposition methods using different MILP formulations to solve the scenario subproblems and introduce a simple yet effective No-one-left based approximation algorithm with a provable approximation guarantee to solve the model to near optimality. Finally, we numerically demonstrate the effectiveness of the proposed approaches and apply them to real-world data provided by the Blacksburg Transit.
Keywords: Distributionally Robust, Mixed-Integer Programming, Strong Formulations, Valid Inequalities
Suggested Citation: Suggested Citation