Google Map API service for VRP Solving Application

Main Article Content

Darmawan Satyananda

Abstract

Computer program application was widely used to solve VRP (Vehicle Routing Problem) cases. In general, the graph used was mainly to model the problem, instead of depicted actual geographic condition. This modeling was inadequate to give comprehensive information to the users, particulary information related to real distance and real route. Google Map provided geographic data in the form of API (Application Programming Interface) that could be accessed by a computer program. Some of services provided were to display map, to access geographical data, distance of some places in distance matrix form, route from selected source to selected destination, and some more.


This article studied developing web-based application for solving VRP using Google Map service. VRP variant implemented in the application is CVRP, and routing strategy used was Sequential Insertion method. Distance among customers was obtained from Google Map service, based on user input on the displayed map, as well as route drawing that used Google Map service.


The application provided better visualization to the users, and route produced was more appropriate to the real circumstances. Test showed that length of the route is slightly longer than calculation from CVRP in general, which considered that route between two nodes is symmetrical.

Article Details

How to Cite
SATYANANDA, Darmawan. Google Map API service for VRP Solving Application. Prosiding SI MaNIs (Seminar Nasional Integrasi Matematika dan Nilai-Nilai Islami), [S.l.], v. 1, n. 1, p. 240-246, july 2017. Available at: <http://conferences.uin-malang.ac.id/index.php/SIMANIS/article/view/76>. Date accessed: 01 apr. 2023.
Section
Mathematics

References

[1] Laporte G. The vehicle routing problem: An overview of exact and approximate algorithms. European Journal of Operational Research [Internet]. 1992 [cited 10 May 2017]; 59(3):345-358. Available from: http://www.sciencedirect.com/science/article/pii/037722179290192C
[2] Sandhya VK. Issues in Solving Vehicle Routing Problem with Time Window and its Variants using Meta heuristics-A Survey. International Journal of Engineering and Technology. 2013 Jun;3(6):668-72
[3] Rosen KH, editor. Handbook of discrete and combinatorial mathematics. CRC press; 1999 Sep 28.
[4] Satyananda D. Developing MST, TSP, and VRP Application. In Proceeding of International Seminar on Mathematics Education and Graph Theory. Malang: Universitas Islam Malang; 2014; pp. 499-508
[5] Wahyuningsih S, Satyananda D. The Characteristics Study of Solving Variants of Vehicle Routing Problem and Its Application on Distribution Problem. International Conference on Research, Implementation and Education of Mathematics and Science [Internet]. Yogyakarta: Faculty of Mathematics and Sciences Yogyakarta State University; 2015 [cited 18 May 2017]. p. 101-108. Available from: http://eprints.uny.ac.id/23319/
[6] Wahyuningsih S, Satyananda D. Implementations of TSP-VRP Variants for Distribution Problem. Global Journal of Pure and Applied Mathematics [Internet]. 2016 [cited 18 May 2017];12(1):723-732. Available from: https://www.ripublication.com/gjpam16/gjpamv12n1_64.pdf
[7] Svennerberg G. Beginning Google Maps API 3. 1st ed. [New York]: Apress; 2010.
[8] Lin J, Chou T. A Geo-Aware and VRP-Based Public Bicycle Redistribution System. International Journal of Vehicular Technology [Internet]. 2012 [cited 1 May 2017];2012:1-14. Available from: https://www.hindawi.com/journals/ijvt/2012/963427/abs/
[9] Salles R, Neto G, Cruz M. An Application of Vehicle Routing Problem in Chartered Buses to Transport Employees Using Geographic Information System. 13th World Conference on Transport Research [Internet]. Rio De Janeiro: WCTR; 2013 [cited 1 May 2017]. Available from: http://www.wctrs-society.com/wp/wp-content/uploads/abstracts/rio/selected/3507.pdf
[10] Urquhart N, Scott C, Hart E. Using Graphical Information Systems to improve vehicle routing problem instances. 15th annual conference companion on Genetic and evolutionary computation [Internet]. Amsterdam: Gecco; 2013 [cited 18 May 2017]. p. 1097-1101. Available from: http://dl.acm.org/ft_gateway.cfm?id=2466802&ftid=1384399&dwn=1&CFID=764439493&CFTOKEN=27175352
[11] Google Maps APIs [Internet]. Google Developers. 2017 [cited 19 May 2017]. Available from: https://developers.google.com/maps/documentation/
[12] Subramanian A, Drummond L, Bentes C, Ochi L, Farias R. A parallel heuristic for the Vehicle Routing Problem with Simultaneous Pickup and Delivery. Computers & Operations Research. 2010;37(11):1899-1911.
[13] Penna P, Subramanian A, Ochi L. An Iterated Local Search heuristic for the Heterogeneous Fleet Vehicle Routing Problem. Journal of Heuristics. 2011;19(2):201-232.
[14] Silva M, Subramanian A, Ochi L. An iterated local search heuristic for the split delivery vehicle routing problem. Computers & Operations Research. 2015;53:234-249.