STORN: Solution to Traversal of Road Networks
Abstract
The objective of the optimal traversal planning (OTP) is to calculate a route that would provide traversal of all streets in a predefined area. While solving the OTP problem, the total distance of the route should be minimized. This paper presents a solution that provides OTP and the execution of the corresponding plan using a series of loosely coupled web services. A mashup is created based on the provided web services and field tested using a data acquisition case in Riga, Latvia. Other possible application areas are street cleaning, package delivery and evacuation planning.
Keywords: |
Chinese postman problem; cloud computing; travelling salesman problem; web services
|
Full Text: |
References
G. Liu, Y. Ge, T. Z. Qiu, and H. R. Soleymani, “Optimization of snow plowing cost and time in an urban environment: A case study for the city of Edmonton,” Canadian Journal of Civil Engineering, vol. 41, 2014, pp. 667–675. http://dx.doi.org/10.1139/cjce-2013-0409
S. S. Chawathe, “Organizing Hot-Spot Police Patrol Routes,” in Intelligence and Security Informatics, 2007 IEEE, 2007, pp. 79–86.
L. Xintong and P. Feng, “The shortest path and spatial decision support system implementation in the context of parcel delivery,” in Geoinformatics, 2010 18th International Conference, 2010, pp. 1–6.
M. Saadatseresht, A. Mansourian, and M. Taleai, “Evacuation planning using multiobjective evolutionary optimization approach,” European Journal of Operational Research, vol. 198, 2009, pp. 305–314. http://dx.doi.org/10.1016/j.ejor.2008.07.032
S. Marston, Z. Li, S. Bandyopadhyay, J. Zhang, and A. Ghalsasi, “Cloud computing – The business perspective,” Decision Support Systems, vol. 51, Apr. 2011, pp. 176–189. http://dx.doi.org/10.1016/j.dss.2010.12.006
J. Gao, P. Pattabhiraman, X. Bai, and W. T. Tsai, “SaaS performance and scalability evaluation in clouds,” in 6th IEEE International Symposium on Service-Oriented System Engineering, SOSE 2011, Irvine, CA, 2011, pp. 61–71.
C. Yang, M. Goodchild, Q. Huang, D. Nebert, R. Raskin, Y. Xu, et al., “Spatial cloud computing: How can the geospatial sciences use and help shape cloud computing?,” International Journal of Digital Earth, vol. 4, 2011, pp. 305–329. http://dx.doi.org/10.1080/17538947.2011.587547
A. Benlian and T. Hess, “Opportunities and risks of software-as-a- service: Findings from a survey of IT executives,” Decision Support Systems, vol. 52, pp. 232–246, Dec. 2011. http://dx.doi.org/10.1016/j.dss.2011.07.007
S. S. Qureshi, T. Ahmad, K. Rafique, and I. Shuja Ul, “Mobile cloud computingas future for mobile applications – Implementation methods and challenging issues,” in 2011 IEEE International Conference on Cloud Computing and Intelligence Systems, CCIS2011, Beijing, 2011, pp. 467–471.
M. Shiraz, A. Gani, R. H. Khokhar, and R. Buyya, “A review on distributed application processing frameworks in smart mobile devices for mobile cloud computing,” IEEE Communications Surveys and Tutorials, vol. 15, pp. 1294–1313, 2013. http://dx.doi.org/10.1109/SURV.2012.111412.00045
A. Corbeŕn and C. Prins, “Recent results on arc routing problems: An annotated bibliography,” Networks, vol. 56, pp. 50–69, 2010.
H. Thimbleby, “The directed Chinese postman problem,” Software – Practice and Experience, vol. 33, pp. 1081–1096, 2003. http://dx.doi.org/10.1002/spe.540
E. Minieka, “Chinese postman problem for mixed networks”, Management Science, vol. 25, pp. 643–648, 1979. http://dx.doi.org/10.1287/mnsc.25.7.643
L. Kazemi, C. Shahabi, M. Sharifzadeh, and L. Vincent, “Optimal traversal planning in road networks with navigational constraints,” in GIS: Proceedings of the ACM International Symposium on Advances in Geographic Information Systems, 2007, pp. 138–145.
F. Dorn, H. Moser, R. Niedermeier, and M. Weller, “Efficient algorithms for eulerian extension and rural postman,” SIAM Journal on Discrete Mathematics, vol. 27, pp. 75–94, 2013. http://dx.doi.org/10.1137/110834810
D. Soler, E. Martínez, and J. C. Micó, “A transformation for the mixed general routing problem with turn penalties,” Journal of the Operational Research Society, vol. 59, pp. 540–547, 2008. http://dx.doi.org/10.1057/palgrave.jors.2602385
J. Clossey, G. Laporte, and P. Soriano, “Solving arc routing problems with turn penalties,” Journal of the Operational Research Society, vol. 52, pp. 433–439, 2001. http://dx.doi.org/10.1057/palgrave.jors.2601052
S. Almoustafa, S. Hanafi, and N. Mladenović, “New exact method for large asymmetric distance-constrained vehicle routing problem,” European Journal of Operational Research, vol. 226, pp. 386–394, 2013. http://dx.doi.org/10.1016/j.ejor.2012.11.040
G. Jäger and W. Zhang, “A SAT based effective algorithm for the directed Hamiltonian cycle problem,” in 5th International Computer Science Symposium in Russia, CSR 2010 vol. 6072 LNCS, ed. Kazan, 2010, pp. 216–227.
M. Turkensteen, D. Ghosh, B. Goldengorin, and G. Sierksma, “Iterative patching and the asymmetric traveling salesman problem,” Discrete Optimization, vol. 3, pp. 63–77, 2006. http://dx.doi.org/10.1016/j.disopt.2005.10.005
B. Freisleben and P. Merz, “Genetic local search algorithm for solving symmetric and asymmetric traveling salesman problems,” in Proceedings of the IEEE Conference on Evolutionary Computation, 1996, pp. 616–621. http://dx.doi.org/10.1109/ICEC.1996.542671
“Downloading data,” Aug. 9, 2014. [Online]. Available: http://wiki.openstreetmap.org/wiki/Downloading_data [Accessed: Oct. 5, 2014].
J. Varia, “Architecting for the Cloud: Best Practices,” 2001. [Online]. Available: http://media.amazonwebservices.com/AWS_Cloud_Best_Practices.pdf [Accessed: Sept. 20, 2014].
M. Hamdaqa, T. Livogiannis, and L. Tahvildari, “A reference model for developing cloud applications,” in CLOSER 2011 – Proceedings of the 1st International Conference on Cloud Computing and Services Science, 2011, pp. 98–103.
C. Inzinger, S. Nastic, S. Sehic, M. Vogler, F. Li, and S. Dustdar, “MADCAT: A methodology for architecture and deployment of cloud application topologies,” in 8th IEEE International Symposium on Service Oriented System Engineering, SOSE 2014, Oxford, 2014, pp. 13–22.
Y. W. Kwon and E. Tilevich, “Cloud refactoring: Automated transitioning to cloud-based services,” Automated Software Engineering, vol. 21, pp. 345–372, 2014. http://dx.doi.org/10.1007/s10515-013-0136- 9
B. P. Rimal, A. Jukan, D. Katsaros, and Y. Goeleven, “Architectural Requirements for Cloud Computing Systems: An Enterprise Cloud Approach,” Journal of Grid Computing, vol. 9, pp. 3–26, 2011. http://dx.doi.org/10.1007/s10723-010-9171-y
R. Geisberger and C. Vetter, “Efficient routing in road networks with turn costs,” in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) vol. 6630 LNCS, ed, 2011, pp. 100–111.
D. Luxen, “Flexible route guidance through turn instruction graphs,” in MapInteract 2013 – Proceedings of the 1st ACM SIGSPATIAL International Workshop on MapInteraction, 2013, pp. 78–83.
Refbacks
- There are currently no refbacks.
Copyright (c) 2014 Janis Kampars, Elina Shmite
This work is licensed under a Creative Commons Attribution 4.0 International License.