ALGORITHMS FOR EXTERNALLY CONSTRAINED ROUTING QUERY
C. Sudeep Reddy · 2010
Navigational systems play a vital role in transportation services, aviation, ground and maritime operations, tracking and surveillance. Route planning and its application are very important in many domains such as location based services, advanced traveler information systems, and more so in GIS applications. The common applications are shortest path analysis and finding the closest facility. But in the real world, there are many deviations from and constraints to the shortest path between the source and destination, and it is important to consider these while planning the route that has to be traversed. Constraints can be either internal to the road network or external to it. The examples for internal constraints are time dependent one-way streets, road closed for maintenance (though it exists on the road network), etc. External constraints don’t alter the network but affects the route planning or its choice. External constraints are like the fuel (petrol/gas) that can last only till a specified distance and necessitates a visit to another facility (gas station) before proceeding to the destination, or visiting another unplanned facility prior to the closure of the facility (pharmacy or bank). This class of problems is defined as Externally Constrained Routing (ECR) query problems. We present four solutions, other than the naive approach, for finding the optimal route for a road network that is externally constrained. The solutions are examined with parameters affecting the performance, e.g., number of queries, number of edges, constraint distance, network distribution (sparse vs dense networks) and facility density. The algorithms proposed here also minimize the total route length from the source to the destination, with a stop at the facility enroute. All the five approaches are evaluated based on storage space, computational efficiency and query response time. Our experiments on Synthetic and Real world road network datasets show that among the proposed algorithms, Path dependent facility mapping (PDF) is computationally very efficient than the other approaches, assuming storage space is not a constraint. Also, PDF will result in lower power consumption, a vital issue for mobile devices. Comparing the experimental results of Pair path processing (PPP) and Euclidean range query approach (ERQ), it can be said that though PPP performs much better than ERQ for synthetic datasets, it is similar for real world datasets. In addition, the preprocessing time required in ERQ is much less than PPP. Hence the ERQ can be considered efficient and also a good approximate solution in the current real world networks. The current approach of treating all the related features as part of the road network (single layer approach, features as vertices) leads to cumbersome updates and query processing approaches for each feature interaction. So, separation of facilities into layers on the road network, as handles by a Geographic Information System (GIS), is needed to improvise query processing and updates to the features database. This work proposes a generalized framework to handle the features as separate GIS layers above the route network layer.