Creator 

Abstract or Summary 
 Location theory is a wellestablished and active research area. The main objective in location theory is to find the best locations for facilities to meet supply and demand constraints and minimize total cost. The median problem (also known as the 1median problem) is a special case in location analysis that aims at locating a facility such that the sum of demand weighted distances to a set of demand points is minimized.
This research is composed of three main parts. In the first part, two algorithms for obtaining optimal solutions to the median problem on real road network graphs are proposed. The first algorithm known as the multithreaded Dijkstra’s (MTD) algorithm, is inspired by the bidirectional Dijkstra's algorithm. The second algorithm is based on exhaustive graph search (EGS) and uses Dijkstra's shortest path algorithm to exhaustively calculate the distance from every demand point to all nodes in the graph. The proposed algorithms are used to evaluate several facility location scenarios that vary with respect to the size of the study area and the number of demand points on that network. The results show that both algorithms are capable of obtaining optimal solutions and that their performance is influenced by factors such as the number of demand points and the size of the area in which the demand points are located.
In the second part of this research, an improved variant of the MTD algorithm known as the MTDi algorithm is presented. The MTDi algorithm preforms less search than the MTD algorithm to find an optimal solution. An experiment is conducted to compare the performance of the MTDi algorithm to that of the MTD and EGS algorithms in terms of the average percentage of nodes explored and the average run time. The results show that the MTDi algorithm always outperforms both the MTD and EGS algorithms in terms of the percentage of nodes explored in all scenarios tested. However, the average run time of the algorithms is heavily influenced by the experimental factors.
In the last part of this research, a methodology that applies the MTD algorithm to locate public transit stops on real road network is presented. The proposed methodology finds the optimal location for transit stops so that the total weighted walking distance from the internal point of census blocks to the transit stops is minimized.

Resource Type 

Date Available 

Date Copyright 

Date Issued 

Degree Level 

Degree Name 

Degree Field 

Degree Grantor 

Commencement Year 

Advisor 

Committee Member 

Academic Affiliation 

NonAcademic Affiliation 

Keyword 

Subject 

Rights Statement 

Peer Reviewed 

Language 

Replaces 
