Location Problems On Weighted Graphs

Network location problems occur when new facilities are to be located on a network. Thernfacility location problems locate a set of facilities (resources) to minimize the cost of satis-rnfying some set of demands (of customers) with respect to some set of constraints.rnLocating a facility to the best place is a decision making problem. The best place de-rnpends on criteria like the optimal distance, the capacity of the facility, population density,rnand optimal cost etc. so the goal of solving location problems is to nd the best location orrnlocations to t one or more facility which will make the highest utility value.rnIn this project,two sets of location problems such as the median and the center locationrnproblems are presented to locate facilities on weighted graphs(or networks).rnTo solve the optimal solutions that identify the median and center location of the weightedrngraph, we rst compute the all pairs shortest path distance of the weighted graph. thus,thernall pair - label correcting algorithm implemented by the Floyd-Warshals algorithm was ap-rnplied to compute the distance matrix. We also examine some of the heuristic methods andrnbinary search techniques developed to solve the problems.

Get Full Work

Report copyright infringement or plagiarism