Equitable Distribution of Scarce Resources in Transportation Networks (Invited Talk)

1 Introduction

Problem of fair allocation of scarce resources appears in many applications on networks. The basic dilemma is between how much of importance to attribute to individual outcomes and to what extent to prioritize the value of the aggregate outcome. High values of the aggregate outcome are often associated with situations when some individual actors receive no or very little allocation. Conversely, equitable distributions may lead to very low aggregate outcome and thus very low efficiency of the system. In this contribution, we describe the basic optimization framework, alpha-fairness [ 1 ], that allow for trading off the degree of equality for the overall efficiency of the system by capturing the utilities of individual actors by the utility function:

Uj( f j, α) = ( 1f1j−−αα for α ≥ 0, α 6= 1 log( f j) for α = 1, (1) where j = 1, . . . , R is the group of actors and f j is an allocation assigned to the actor j. Then, the aggregate util

R ity U (α) = ∑ j=1 Uj( f j, α) is maximized under the constraints that allocations to all actors are feasible. Value α ≥ 0 is a parameter. When α = 0, we maximize the aggregate utility, obtaining solution known in the literature as utilitarian solution, system optimum or in the context of flow problems it is known as maximum flow. If α → ∞ we obtain equitable solution, known as max-min fairness. Here, the allocation to the actors with the minimum allocation is maximized first, and once these "poor" actors receive the largest possible allocation, the process repeats iteratively for the next more well-off actors. For the intermediate values of α we obtain trade-off solutions. Among them, probably the most prominent is the proportionally fair solution [ 1 ] obtained for α = 1. This framework can be easily applied in environments where all the limitations can be expressed by the set of linear equalities and convex inequalities. Thus, in cases when the convex optimization can be utilized as a basic solving technique. We illustrate the broad applicability of alpha-fairness by briefly introducing three applications. 2

Application 1: Resilience of Natural Gas Networks During Conflicts, Crises and Disruptions Human conflict, geopolitical crises, and natural disasters can turn large parts of energy distribution networks offline. Europe’s current gas supply network is historically largely dependent on deliveries from Russia and North Africa, creating vulnerabilities to social and political instabilities. During crises, less delivery means greater congestion, as the pipeline network is used in ways it has not been designed for. Thus, an approach that can distribute limited capacities among affected countries and cities is needed. Combining three spatial data layers (see Figure 1), gas import and gas export data with a proportionally fair congestion control flow model we created a model of the European gas pipeline network and we analysed large set of crises scenarios [ 2 ].

Application 2: Design of Public Service Systems This application is motivated by problems faced by public authorities when locating facilities, such as schools, branch offices and ambulance, police or fire stations to serve spatially distributed population. These systems are typically operated from public money and they should account for equitable access of customers to services (see Figure 2).

Solution A:

2 7

This problem can be formulated as discrete location problem. We explain how the concept of max-min fairness generalizes in a discrete space to the lexicographic minmax concept. Previous approaches to the lexicographic minimax facility location problem, result in a specific form of the mathematical model that is supposed to be solved by a general purpose solver. This limits the size of solvable problems to approximately 900 customers and 900 candidate facility locations. Building on the concept of unique classes of distances, we proposed approximation algorithm providing high quality equitable solutions for large instances of solved problems [ 3 ]. We used the resulting algorithm to perform extensive study using the wellknown benchmarks and two new large benchmarks derived from the real-world data. 4

Application 3: Coordination of EVs

Charging in the Distribution Networks With the possible uptake of electric vehicles in the near future, we are likely to observe overloading in the local distribution networks more frequently. Such development suggests that a congestion management protocol will be a crucial component of the future technological innovations in low voltage networks. An important property of a suitable network capacity management protocol is to balance the network efficiency and fairness requirements. (a) (b) i

j P (j), Q (j)

Pi Vi Vj Pj

We explored the onset of congestion by analysing the critical arrival rate, i.e. the largest possible vehicle arrival rate that can still be fully satisfied by the network for two basic control strategies: the proportional fairness and the maximum flow [ 4 ]. By numerical simulations on realistic networks (see Figure 3) we showed that proportional fairness leads not only to more equitable distribution of power allocations, but it can also serve slightly larger arrival rate of vehicles. For the simplified setup, where the power allocations are dependent on the occupation of network nodes, but they are independent of the exact number of vehicles, we validated the numerical results, by analysing the critical arrival rate on a network with two edges, where the optimal power allocations can be calculated analytically.

Acknowledgement

This lecture was supported by the research grants VEGA 1/0463/16 "Economically efficient charging infrastructure deployment for electric vehicles in smart cities and communities", APVV-15-0179 "Reliability of emergency systems on infrastructure with uncertain functionality of critical elements" and it was facilitated by the FP 7 project ERAdiate [621386]"Enhancing Research and innovation dimensions of the University of Zilina in Intelligent Transport Systems".

References

[1] Luss , H. : Equitable Resources Allocation: Models, Algorithms and Applications . John Wiley & Sons, New York, NY, USA, ( 2012 )

[2] Carvalho , R. , Buzna , L '., Bono , F. , Masera , M. , Arrowsmith , D. K. , Helbing , D. : Resilience of Natural Gas Networks during Conflicts, Crises and Disruptions . PLoS ONE 9 ( 3 ), ( 2014 ), e90265

[3] Buzna , L. , Koháni , M. , Janácˇek: An Approximation Algorithm for the Facility Location Problem with Lexicographic Minimax Objective , Journal of Applied Mathematics . 2014 ( 2014 ) 562373

[4] Carvalho , R. , Buzna , L '., Gibbens , R. , Kelly , F. : Critical behaviour in charging of electric vehicles . New J. Phys. 17 , ( 2015 ) 095001 .