# A Study of Problems Modelled as Network Equilibrium Flows

PhD Thesis

O'Neill, S. 2021. A Study of Problems Modelled as Network Equilibrium Flows. PhD Thesis https://doi.org/10.48773/975xv
Authors O'Neill, S. PhD Thesis This thesis presents an investigation into selfish routing games from three main perspectives. These three areas are tied together by a common thread that runs through the main text of this thesis, namely selfish routing games and networkequilibrium flows. First, it investigates methods and models for nonatomic selfish routing and then develops algorithms for solving atomic selfish routing games. A number of algorithms are introduced for the atomic selfish routing problem, including dynamic programming for a parallel network and a metaheuristic tabu search. A piece-wise mixed-integer linear programming problem is also presented which allows standard solvers to solve the atomic selfish routing problem. The connection between the atomic selfish routing problem, mixed-integer linear programming and the multicommodityflow problem is explored when constrained by unsplittable flows or flows that are restricted to a number of paths. Additionally, some novel probabilistic online learning algorithms are presented and compared with the equilibrium solution given by the potential function of the nonatomic selfish routing game. Second, it considers multi-criteria extensions of selfish routing and the inefficiencyof the equilibrium solutions when compared with social cost. Models are presented that allow exploration of the Pareto set of solutions for a weighted sum model (akin to the social cost) and the equilibrium solution. A means by whichthese solutions can be measured based on the Price of Anarchy for selfish routing games is also presented. Third, it considers the importance and criticality of components of the network (edges, vertices or a collection of both) within a selfish routing game and the impact of their removal. Existing network science measures and demand-based measuresare analysed to assess the change in total travel time and issues highlighted. A new measure which solves these issues is presented and the need for such a measure is evaluated.Most of the new findings have been disseminated through conference talks and journal articles, while others represent the subject of papers currently in preparation. selfish routing games; dynamic programming ; commodity flow problem 2021 University of Derby https://doi.org/10.48773/975xv Doctoral_Thesis_Amended_Sam_ONeill.pdfLicenseCC BY-NC-ND 4.0File Access LevelOpen Unpublished 27 Jun 2022

https://repository.derby.ac.uk/item/975xv/a-study-of-problems-modelled-as-network-equilibrium-flows

###### File
 Doctoral_Thesis_Amended_Sam_ONeill.pdf License: CC BY-NC-ND 4.0 File access level: Open

total views