Return to search

Characteristics of Optimal Solutions to the Sensor Location Problem

Congestion and oversaturated roads pose significant problems and create delays in every major city in the world. Before this problem can be addressed, we must know how much traffic is flowing over the links in the network. We transform a road network into a directed graph with a network flow function, and ask the question, “What subset of vertices (intersections) should be monitored such that knowledge of the flow passing through these vertices is sufficient to calculate the flow everywhere in the graph?” To minimize the cost of placing sensors, we seek the smallest number of monitored vertices. This is known as the Sensor Location Problem (SLP). We explore conditions under which a set of monitored vertices produces a unique solution to the problem and disprove a previous result published on the problem. Finally, we explore a matrix formulation of the problem and present cases when the flow can or cannot be calculated on the graph.

Identiferoai:union.ndltd.org:CLAREMONT/oai:scholarship.claremont.edu:hmc_theses-1213
Date01 May 2008
CreatorsMorrison, David
PublisherScholarship @ Claremont
Source SetsClaremont Colleges
Detected LanguageEnglish
Typetext
Formatapplication/pdf
SourceHMC Senior Theses

Page generated in 0.0018 seconds