Weitere Kapitel dieses Buchs durch Wischen aufrufen
Route planning in road networks is a basic operation in the area of location-based services. Very often, the knowledge of the optimal route is not the only important information for a driver. Complex services could also present points of interest (e.g. hotels or gas stations) nearby the optimal route as stop-over. Here, ‘nearby’ means: the bypass route from a start to target that passes that point does not exceed certain costs. In this paper, we present an efficient approach to compute all bypasses that are within a given cost limit. We may additionally request only locally optimal bypasses, e.g., that reach an intermediate point without driving U-turns. The set of all bypasses called bypass area can be used for further queries, in e.g. geo databases to find nearby points of interest for a certain application or service. Our approach is fully implemented and evaluated and computes the respective bypass areas very runtime-efficient, whereas it re-uses similar structures as for optimal route planning.
Bitte loggen Sie sich ein, um Zugang zu diesem Inhalt zu erhalten
Sie möchten Zugang zu diesem Inhalt erhalten? Dann informieren Sie sich jetzt über unsere Produkte:
Abraham I., Delling D., Goldberg A. V., Werneck R. F. (2010): Alternative Routes in Road Networks, in Proc. of the 9th Intern. Symposium on Experimental Algorithms (SEA ’10).
Bellman R. and Kalaba R. (1960): On kth best policies, Journal of the Society for Industrial and Applied Mathematics, 582–588.
Dijkstra E. W. (1959): A note on two problems in connexion with graphs, Numerische Mathematik. 1, 1959, 269–271. CrossRef
Duckham M., Kulik L., Worboys M. and Galton A. (2008): Efficient generation of simple polygons for characterizing the shape of a set of points in the plane, Journal Pattern Recognition, Vol. 41, Issue 10, Oct. 2008, 3224–3236. CrossRef
Eppstein D. (1994): Finding the k shortest paths, in Foundations of Computer Science, Proc of the 35th Annual Symposium on. IEEE, 154–165.
Geisberger R., Sanders P., Schultes D. and Delling D. (2008): Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks, WEA 2008, LNCS 5038, 319–333.
Goldberg A. V., Harrelson C. (2005): Computing the Shortest Path: A* Search Meets Graph Theory, in Proc. 16th ACMSIAM, Symposium on Discrete Algorithms, pp. 156–165.
Hart P. E., Nilsson N. J. and Raphael B. (1968): A Formal Basis for the Heuristic Determination of Minimum Cost Paths, IEEE Transactions on Systems Science and Cybernetics SSC4 (2), 1968, 100–107.
Hoffman W. and Pavley R. (1959): A method for the solution of the n th best path problem, Journal of the ACM (JACM), vol. 6, no. 4, 506–514. CrossRef
Luxen D., Schieferdecker D. (2012): Candidate Sets for Alternative Routes in Road Networks, in Proc. of the 11th Intern. Symposium on Experimental Algorithms (SEA ’12).
Paraskevopoulos A., Zaroliagis C. (2013): Improved Alternative Route Planning, 13th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS’13). 108–122.
Roth J. (2009): The Extended Split Index to Efficiently Store and Retrieve Spatial Data With Standard Databases, IADIS International Conference Applied Computing 2009, Rome, Nov. 19–21, 2009, Vol. I, 85-92.
Roth J. (2013): Combining Symbolic and Spatial Exploratory Search – the Homerun Explorer, Innovative Internet Computing Systems (I2CS), Hagen, June 19–21. 2013, VDI, Vol. 10, No. 826, 94–108.
Roth J. (2014): Predicting Route Targets Based on Optimality Considerations, International Conference on Innovations for Community Services (I4CS), Reims (France) June 4–6, 2014, IEEE xplore, 61-68.
Roth J. (2016): Efficient Many-to-Many Path Planning and the Traveling Salesman Problem on Road Networks, KES Journal: Innovation in Knowledge-Based and Intelligent Engineering Systems, 20 (2016), IOS Press, 135–148. CrossRef
Roth J. (2016b): The Offline Map Matching Problem and its Efficient Solution, International Conference on Innovations for Community Services (I4CS), Vienna, under review.
Yen J. Y. (1971): Finding the k shortest loopless paths in a network, Management Science, vol. 17, no. 11, 712–716. CrossRef
- Efficient Computation of Bypass Areas
Neuer Inhalt/© ITandMEDIA, Product Lifecycle Management/© Eisenhans | vege | Fotolia