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
AuthorsO'Neill, S.
TypePhD Thesis
Abstract

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 network
equilibrium 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 multicommodity
flow 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 inefficiency
of 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 which
these 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 measures
are 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.

Keywordsselfish routing games; dynamic programming ; commodity flow problem
Year2021
PublisherUniversity of Derby
Digital Object Identifier (DOI)https://doi.org/10.48773/975xv
File
License
File Access Level
Open
Output statusUnpublished
Publication process dates
Deposited27 Jun 2022
Permalink -

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

Download files


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

  • 93
    total views
  • 124
    total downloads
  • 0
    views this month
  • 3
    downloads this month

Export as