Princeton FRS 142 - Applications of GPS to Shortest Path Algorithms

Unformatted text preview:

Applications of GPS to Shortest Path Algorithms and Automatic Vehicle Location SystemsEvery wonder what the world would be like with little to no congestion, improved safety and efficiency on all roads? Automated Vehicle Location systems and shortest path algorithms are steps in this direction…Automatic Vehicle Location (AVL) SystemsHistory and Development of AVL SystemsPotential Applications of AVL SystemsPublic Transit SystemsDisaster RecoveryLaw Enforcement and Medical Response SystemsTraffic and Fleet Management SystemsBut how do we get there faster, safer, and more efficiently?Shortest Path Algorithms!!!What is a shortest path algorithm?Why do we need shortest path algorithms?Time Dependent Shortest Path AlgorithmsSlide 15Slide 16What does it all mean?Applications of GPS to Shortest Path Algorithms and Automatic Vehicle Location SystemsA Project for FRS 142 – Where’s Waldo? The Science and Application of GPSWills Sweney4.5.03Every wonder what the world would be like with little to no congestion, improved safety and efficiency on all roads? Automated Vehicle Location systems and shortest path algorithms are steps in this direction…Automatic Vehicle Location (AVL) Systems•AVL is an automated vehicle tracking system made possible by navigational technologies such as Global Positioning Systems (GPS)•GPS based systems enable remote tracking of a fleet or vehicle•Modern AVL systems generally include a network of vehicles that are equipped with a mobile radio receiver, a GPS receiver, a GPS modem, and a GPS antenna.History and Development of AVL Systems•Buried Magnetic Strips•Multi-Lateration •An Odometer-Only system can be used as a stand alone system, which counts wheel revolutions by monitoring flying magnets attached to the front wheels of the vehicle •Signpost-Only Systems: use wayside beacons (signposts) to transmit a unique ID within a given area of effect •The Global Positioning System (GPS): relies on a worldwide network of satellites, but as we know, has problemsPotential Applications of AVL Systems•Public Transit Systems•Disaster Recovery•Law Enforcement •Emergency Management Systems•Traffic Management Systems•Fleet Management SystemsPublic Transit Systems•Improve service efficiency–Providing real time information to the travelers regarding the current position of the bus or the transit vehicle at a particular time and the expected arrival and departure time. •Improve information accuracy and availability•Improve radio call management •Improve safety on buses •Improve response times to incidents and emergenciesDisaster Recovery•The GPS-based Automatic Vehicle Location system was used for the first time to manage the debris removal in the disaster recovery setting at the World Trade Center site. •Enabled staff to locate each truck as it loaded materials at the site and transported them to disposal sites•Removing bottlenecks and placing debris removal resources where they were needed at the right time improved efficiency drastically•“Geofence” •Many state and federal agencies have expressed their intent to incorporate this technology into future recovery efforts following such natural disasters as earthquakes, floods, and hurricanes.Law Enforcement and Medical Response Systems•Law enforcement: providing the dispatcher with the location of the vehicles under his control so that the time required to respond to the calls can be reduced•Providing the information regarding an emergency to the emergency response vehicle can reach the scene in reduced time.•Use of shortest path algorithms to reduce the time cost of any particular routeTraffic and Fleet Management Systems•By locating the stalled vehicles or accident and then providing the information to the other users of the same route so that they can use the alternative routes to avoid the possible delays•Knowing the location of each and every vehicle of the fleet, it can provide the same information to the user of the system so that they can use this information to plan their trip and dynamically change their routeBut how do we get there faster, safer, and more efficiently?Shortest Path Algorithms!!!What is a shortest path algorithm?•A shortest path algorithm is a program, or set of directions that can be executed to provide the shortest path between locations given certain conditions and paths•Conditions such as traffic density, speed of travel, and others, as well as geographic obstacles can be factored in to help the algorithm execute and display the shortest path•The latest algorithms being developed adjust to conditions and dynamically execute to give new shortest paths based not only on distance, but also on timeWhy do we need shortest path algorithms?•Shortest path algorithms are essential to improving efficiency and safety in many areas network navigation such as highway systems and disaster clean-up•Algorithms are used for determining time dependent shortest paths in highway systems given variations in traffic density•Algorithms are used in connection with GPS tracking technology to provide shortest paths for trucks to follow to specific dumping areas when cleaning up after a natural or terrorism related disasterTime Dependent Shortest Path Algorithms•Time dependent shortest path algorithms are designed to obtain speed information without integrating GPS into the speedometer•The purpose of the algorithm is to run dynamically with changing traffic conditions and find the shortest time cost path, not necessarily the shortest distance path•In studies done of freeway systems one freeway is assigned as the most congested that way the total traffic load could be distributed among the other routesTime Dependent Shortest Path Algorithms•An interarrival time: the time between the arrival of a moving object and the next moving object. •The average of this interarrival time represents the severity of the congestion•A skew rate is assigned to create more congestion on a specific route than any other route–For example, if the skew rate is 1, then the traffic is distributed equally among the routes, but if it is equal to 2 then this means that the load is twice as heavy on the assigned most congested routeTime Dependent Shortest Path Algorithms•upon entry into the system a moving object must give it start location, destination, start time, and initial speed•two groups were made, winners and losers. Losers would not be


View Full Document

Princeton FRS 142 - Applications of GPS to Shortest Path Algorithms

Download Applications of GPS to Shortest Path Algorithms
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Applications of GPS to Shortest Path Algorithms and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Applications of GPS to Shortest Path Algorithms 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?