Location Problems on Weighted Graphs
No Thumbnail Available
Date
2015-10-16
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Addis Ababa University
Abstract
Network location problems occur when new facilities are to be located on a network. The
facility location problems locate a set of facilities (resources) to minimize the cost of satis-
fying some set of demands (of customers) with respect to some set of constraints.
Locating a facility to the best place is a decision making problem. The best place de-
pends on criteria like the optimal distance, the capacity of the facility, population density,
and optimal cost etc. so the goal of solving location problems is to nd the best location or
locations to t one or more facility which will make the highest utility value.
In this project,two sets of location problems such as the median and the center location
problems are presented to locate facilities on weighted graphs(or networks).
To solve the optimal solutions that identify the median and center location of the weighted
graph, we rst compute the all pairs shortest path distance of the weighted graph. thus,the
all pair - label correcting algorithm implemented by the Floyd-Warshals algorithm was ap-
plied to compute the distance matrix. We also examine some of the heuristic methods and
binary search techniques developed to solve the problems.
Description
Keywords
Location Problems on Weighted Graphs