On the capacity provisioning on dynamic networks

dc.contributor.authorLijoka, Oluwaseun Francis
dc.contributor.authorUniversity of Lethbridge. Faculty of Arts and Science
dc.contributor.supervisorBenkoczi, Robert
dc.description.abstractIn this thesis, we consider the development of algorithms suitable for designing evacuation procedures in sparse or remote communities. The works are extensions of sink location problems on dynamic networks, which are motivated by real-life disaster events such as the Tohoku Japanese Tsunami, the Australian wildfire and many more. The available algorithms in this context consider the location of the sinks (safe-havens) with the assumptions that the evacuation by foot is possible, which is reasonable when immediate evacuation is needed in urban settings. However, for remote communities, emergency vehicles may need to be dispatched or situated strategically for an efficient evacuation process. With the assumption removed, our problems transform to the task of allocating capacities on the edges of dynamic networks given a budget capacity c. We first of all consider this problem on a dynamic path network of n vertices with the objective of minimizing the completion time (minmax criterion) given that the position of the sink is known. This leads to an O(nlogn + nlog(c/ξ)) time, where ξ is a refinement or precision parameter for an additional binary search in the worst case scenario. Next, we extend the problem to star topologies. The case where the sink is located at the middle of the star network follows the same approach for the path network. However, when the sink is located on a leaf node, the problem becomes more complicated when the number of links (edges) exceeds three. The second phase of this thesis focuses on allocating capacities on the edges of dynamic path networks with the objective of minimizing the total evacuation time (minsum criterion) given the position of the sink and the budget (fixed) capacity. In general, minsum problems are more difficult than minmax problems in the context of sink location problems. Due to few combinatorial properties discovered together with the possibility of changing objective. function configuration in the course of the optimization process, we consider the development of numerical procedure which involves the use of sequential quadratic programming (SQP). The sequential quadratic programming employed allows the specification of an arbitrary initial capacities and also helps in monitoring the changing configuration of the objective function. We propose to consider these problems on more complex topolgies such as trees and general graph in future.en_US
dc.description.sponsorshipNSERC Discovery Grants program. University of Lethbridge Graduate Research Award. Alberta Innovates Awarden_US
dc.publisherLethbridge, Alta. : Dept. of Mathematics and Computer Scienceen_US
dc.publisher.departmentDepartment of Mathematics and Computer Scienceen_US
dc.publisher.facultyArts and Scienceen_US
dc.relation.ispartofseriesThesis (University of Lethbridge. Faculty of Arts and Science)en_US
dc.subjectfacility locationen_US
dc.subjectcapacity schedulingen_US
dc.subjectsink location problemen_US
dc.subjectcapacity allocation problemen_US
dc.subjectevacuation problemen_US
dc.subjectdynamic flow in networksen_US
dc.subjectLocation problems (Programming)en_US
dc.subjectTransportation problems (Programming)en_US
dc.subjectEvacuation of civilians--Mathematical modelsen_US
dc.subjectEmergency management--Mathematical modelsen_US
dc.subjectSparsely populated areasen_US
dc.subjectMathematical optimizationen_US
dc.subjectDissertations, Academicen_US
dc.titleOn the capacity provisioning on dynamic networksen_US
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
1.87 MB
Adobe Portable Document Format
License bundle
Now showing 1 - 1 of 1
Thumbnail Image
3.25 KB
Item-specific license agreed upon to submission