Graduate Thesis Or Dissertation
 

Efficient Algorithms for Solving the Median Problem on Real Road Networks

Public Deposited

Downloadable Content

Download PDF
https://ir.library.oregonstate.edu/concern/graduate_thesis_or_dissertations/w3763c26k

Descriptions

Attribute NameValues
Creator
Abstract
  • Location theory is a well-established 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 1-median 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 multi-threaded 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 MTD-i algorithm is presented. The MTD-i algorithm preforms less search than the MTD algorithm to find an optimal solution. An experiment is conducted to compare the performance of the MTD-i 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 MTD-i 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.
License
Resource Type
Date Available
Date Issued
Degree Level
Degree Name
Degree Field
Degree Grantor
Commencement Year
Advisor
Committee Member
Academic Affiliation
Non-Academic Affiliation
Subject
Rights Statement
Publisher
Peer Reviewed
Language
Replaces

Relationships

Parents:

This work has no parents.

In Collection:

Items

Thumbnail Title Date Uploaded Visibility Actions
file details GhanbartehraniSaeed2015.pdf 2017-10-27 Public Download