Feasible Route Search on Road Networks by Using Clues
Keywords:
Social Routing, Social Metrics, Road network, spatial databases, events, geo streaming, mustier solution, traffic analytics.Abstract
The booming industry of location based services is accumulated many collection of users location trajectories of driving, cycling, hiking. We find the problem of discovering the Most Popular Route (MPR) between two locations by taking the traveling behaviors of many backend users. To determining the waiting time every parking vertex to achieve the minimal on-road time becomes a big challenge which further breaks FIFO property. We propose two efficient algorithms using minimum on-road travel cost function to answer the query. This paper focuses on the highly developed solution is using ACO algorithm. It also applied the method considering flow, distance, cost, and emergency. Given a query location and a set of candidate objects in a road network the kNN search finds the k nearest objects to the query location. We propose balanced search tree index, called G tree. The G tree is road network and constructed by recursively partitioning the road network into sub-networks and each G-tree node corresponds to a sub-network. Propose a class of routing schemes is finding the nodes of highest utility for routing improving the delay and delivery ratio. Additionally proposed an analytical framework based on fluid models is used to analyze the performance of many opportunistic routing strategies, in heterogeneous settings.
References
- I. Abraham, D. Delling, A. V. Goldberg, and R. F. Werneck. Hierarchical hub labelings for shortest paths. In ESA, pages 24-35. Springer, 2012.
- H. Gonzalez, J. Han, X. Li, M. Myslinska, and J. P. Sondag, "Adaptive fastest path computation on a road network: a traffic mining approach," in VLDB, 2007, pp. 794-805.
- F. Giannotti, M. Nanni, F. Pinelli, and D. Pedreschi, "Trajectory pattern mining," in SIGKDD, 2007, pp. 330-339.
- A. Monreale, F. Pinelli, R. Trasarti, and F. Giannotti, "Wherenext: a location predictor on trajectory pattern mining," in SIGKDD, 2009, pp. 637-646
- J. Dong and J. Wu, "Urban traffic networks equilibrium status recognition with neural network," Proceedings Intelligent Transportation Systems, 2003 IEEE, vol. 2, pp. 1049-1053 vol.2, Oct. 2003.
- F. H. Knight, "Some fallacies in the interpretation of social cost," The Quarterly Journal of Economics, vol. 38, pp. 582-606, 1924.
- B. Guo, Z. Wang, Z. Yu, Y. Wang, N. Yen, R. Huang, and X. Zhou, Mobile crowd sensing and computing: The review of an emerging human-powered sensing paradigm, ACM Computing Surveys, vol. 48, no. 1, p. 7, 2015.
- Y. Li, M. Qian, D. Jin, P. Hui, Z. Wang, and S. Chen, Multiple mobile data offloading through disruption tolerant networks, IEEE Trans. on Mobile Computing, vol. 13, no.7, pp. 1579-1596, 2014.
- H. Jeung, Q. Liu, H. T. Shen, and X. Zhou, "A hybrid prediction model for moving objects," in ICDE, 2008, pp. 70-79.
- C. M. Grinstead and J. L. Snell, Introduction to Probability, 2nd ed. American Mathematical Society, 1997
- Y. Zhu, C. Zhang, and Y. Wang, Mobile data delivery through opportunistic communications among cellular users: A case study for the D4D challenge, in Proc. Of NetMob, 2013.
- L. Wang, D. Zhang, and H. Xiong, Effsense: Energyefficient and cost-effective data uploading in mobile crowdsensing, in Proc. of ACM UbiComp, 2013.
- P. Hui, J. Crowcroft, and E. Yoneki, Bubble rap: Social-based forwarding in delay-tolerant networks, IEEE Transactions on Mobile Computing, vol. 10, no. 11, pp. 1576-1589, 2011.
- T. Spyropoulos, K. Psounis, and C. S. Raghavendra, Spray and wait: An efficient routing scheme
- S. Brakatsoulas, D. Pfoser, R. Salas, and C. Wenk. On Map-Matching Vehicle Tracking Data. In VLDB, pp. 853-864, 2005.
- H. Cao and O. Wolfson. Nonmaterialized Motion Information in Transport Networks. In ICDT, pp. 173-188, 2005.
- A. Civilis, C.S. Jensen, and S. Pakalnis. Techniques for Efficient Road-networkbased Tracking of Moving Objects. IEEE TKDE, 17(5):698-712, 2005.
- C. de Fabritiis, R. Ragona, and G. Valenti. Traffic Estimation and Prediction Based on Real Time Floating Car Data. In IEEE ITSC, pp. 197-203, 2008
- J. G. Wardrop, "Some theoretical aspects of road traffic research," Proceedings, Institute of Civil Engineers, Part II, vol. 1, pp. 325-378, 1952.
- Ichoua, S., M. Gendreau, and J. Potvin. 2003. Vehicle dispatching with time-dependent travel times. European Journal of Operational Research (144): 379-396.
- M. Middendorf, F. Reischle and H. Schmeck (2002) Multi colony ant algorithms.Journal of Heuristics, (in press). Journal of Heuristics, (in press).
- S. E. Dreyfus, "An appraisal of some shortest-path algorithms," Operations research, vol. 17, no. 3, pp. 395-412, 1969.
- E. Kanoulas, Y. Du, T. Xia, and D. Zhang, "Finding fastest paths on a road network with speed patterns," in Data Engineering, 2006. ICDE’06. Proceedings of the 22nd International Conference on. IEEE, 2006, pp. 10-10.
- B. Ding, J. X. Yu, and L. Qin, "Finding time-dependent shortest paths over large graphs," in Proceedings of the 11th international conference on Extending database technology: Advances in database technology. ACM, 2008, pp. 205-216.
- M. Middendorf, F. Reischle and H. Schmeck (2002) Multi colony ant algorithms.Journal of Heuristics, (in press). Journal of Heuristics, (in press).
- M. Dorigo, Online website
- Di Caro, G., F. Ducatelle, and L. M. Gambardella. 2005. Anthocnet: An adaptive nature-inspired algorithm for routing in mobile ad hoc networks.
- J. B. Rocha-Junior and K. Nørv?ag. Top-k spatial keyword queries on road networks. In EDBT, pages 168-179, 2012.
- L. Roditty and U. Zwick. On dynamic shortest paths problems. Algorithmica, 61(2):389-401, 2011.
Downloads
Published
Issue
Section
License
Copyright (c) IJSRST
This work is licensed under a Creative Commons Attribution 4.0 International License.