SCSC2003 Abstract S31354
A Simulation Study for Automated Path Planning in Transportation Systems
A Simulation Study for Automated Path Planning in Transportation Systems
Submitting Author: Dr. Dr. Balqies Sadoun
Abstract:
Summary
Traveling is becoming a part of our daily life. Modern roads and highways are becoming more and more complicated to the degree that it is difficult to find a best path for traveling from one place to another. The use of computer in mapping and route finding and planning has become very important from the pint view of cost, and time. Geographic Information System (GIS) is a computer system, which makes mapping and route planning easy for mankind. GIS packages are based on optimum algorithms that aid in finding the shorted path between two places, among many other features and facilities.
An important aspect in route planning is to find the shortest path between two points efficiently and accurately. An ambulance driver, as an example, cannot afford to be misguided or wait a long period of time to find the best route to his/her patient. The metrics for finding the shortest path can be distance (i.e. to get to a place in shortest distance) or time (i.e. to get to a place in fastest time). In well-known Internet sites that aid in route planning, a user can enter other options, such as, favor or avoid major highways. Efficiency is very important for these Internet sites since cost (such as, capital cost and maintenance cost) is directly correlated to the efficiency of the system.
Route planning is an important component of both computer networks and real world transportation planning. There is a lot of similarity between computer networks and transportation networks to the degree we find that many of the algorithms that are used to find the shortest path between two computer nodes are similar to these used to find the shortest path between two places.
Our simulation results have shown that for rectangular grid type network, that is available in city area, the TWO-Q (Graph Growth with Two Queues - Pallottino) scheme has shown the best performance. The performance of DIKBD (Dijkstra's Buckets - Double buckets ) and DIKH (Dijkstra's Heap -- k-array heap ) schemes is almost similar. Somewhat slower is DIKBA; but performance is closer to that of other two Dijkstra's algorithms. The worst performance of this family is that of BFP (Bellman-Ford-Moore with Parent-checking).
Our results shows that, for square grid network, DIKBA performs best and DIKDB is somewhat worse on smaller problems but catches up with DIKBA on the larger problems. BFP is good on smaller problems but shows poor performance on larger problems, but performance is better than TWO-Q.
Furthermore, the five algorithms have been tested on two sets of real road network. Based on speed and stability corresponding to different arc lengths, a number of algorithms for real road networks with varying size are identified.
The best performing implementations for solving the one to all shortest path problem is TWO Q. Implementation of TWO-Q is extremely fast for large or small networks. Moreover, performance is not a function of arc length magnitude. This algorithm is also proved to be the best for computer generated rectangular grid network data.
For a one to one shortest path or the shortest paths from one to some, it may be worthwhile to consider one of the Dijkstra 's implementations. But Dijkstra implementations depend on the maximum size of the network arc lengths. Dijkstra approximate buckets implementation (DIKBA) is recommended for less arc length. The Finally, the Bellman Ford Moore implementations with parent checking (BFP) have serious difficulties on large networks, therefore, it is not recommended for road network.
Back to SCSC2003 Abstracts