ℓ-CTP: Utilizing Multiple Agents to Find Efficient Routes in Disrupted Networks

<p>Recent hurricane seasons have demonstrated the need for more effective methods of coping with flooding of roadways. A key complaint of logistics managers is the lack of knowledge when developing routes for vehicles attempting to navigate through areas which may be flooded. In particular, it can be difficult to re-route large vehicles upon encountering a flooded roadway. We utilize the Canadian Traveller’s Problem (CTP) to construct an online framework for utilizing multiple vehicles to discover low-cost paths through networks with failed edges unknown to one or more agents a priori. This thesis demonstrates the following results: first, we develop the ℓ-CTP framework to extend a theoretically validated set of path planning policies for a single agent in combination with the iterative penalty method, which incentivizes a group of ℓ > 1 agents to explore dissimilar paths on a graph between a common origin and destination. Second, we carry out simulations on random graphs to determine the impact of the addition of agents on the path cost found. Through statistical analysis of graphs of multiple sizes, we validate our technique against prior work and demonstrate that path cost can be modeled as an exponential decay function on the number of agents. Finally, we demonstrate that our approach can scale to large graphs, and the results found on random graphs hold for a simulation of the Houston metro area during hurricane Harvey. </p>

Name thesis:degree_name

Master of Science in Industrial Engineering (MSIE)

Level thesis:degree_level

Thesis

Year dc:date.available

2020

Author dc:creator

• Alseth, Andrew

Advisor dc:contributor.advisor

• Milburn, Ashlea B.

Contributors dc:contributor

• Eksioglu, Burak
• Sullivan, Kelly M.

• Disaster respone
• Logistics
• Natural Disasters
• Optimization
• Path Generation Methods
• Industrial Technology
• Operational Research

Repository record dc:identifier

https://scholarworks.uark.edu/etd/3949

OAI identifier oai:identifier

oai:scholarworks.uark.edu:etd-5499