In this dissertation we study the routing problem for multi-commodity survivable network ows, with splittable demands, and propose end-to-end path-based solutions where maximum link utilization is minimized, in order to improve resilience in existing telecommunication networks. We develop mixed integer programming models, and demonstrate that, when the selection of disjoint paths is part of the optimization problem (rather than when k-shortest paths are pre-selected, as in earlier works), maximum link utilization is reduced and the overall network also balances out. We find that three paths are usually enough to reap the benefits of a multipath approach. A reduction in maximum link utilization also provides a margin by which demand values can grow without causing congestion. We also prove that the disjoint multipath selection problem is NPcomplete, even for the case of one node-pair. This warrants a recourse to effi- cient solution methods within ILP (such as decomposition), and to matheuristics. Our literature survey of applications of heuristic techniques, and those combining heuristics with exact methods, shows a research gap, which we attempt to bridge through a novel heuristic algorithm. The heuristic works well and, in several cases, yields better solutions than ILP (in a given time limit), or provides solutions for problems where ILP could not even find one valid solution in the given time limit. We also study this problem within a decomposition methods framework: i.e., column generation. The pricing sub-problem is a mixed non-linear programme, for which we propose an ILP formulation. We find some lower bounds for missing dual values and use them as surrogates. We then show that the lower bounds are valid and present examples where the proposed pricing is applied to path generation for self-protecting multipath routing.
| Identifer | oai:union.ndltd.org:bl.uk/oai:ethos.bl.uk:589834 |
| Date | January 2013 |
| Creators | Kazmi, Nayyar A. |
| Publisher | University of Warwick |
| Source Sets | Ethos UK |
| Detected Language | English |
| Type | Electronic Thesis or Dissertation |
| Source | http://wrap.warwick.ac.uk/58426/ |
Page generated in 0.0024 seconds