Implementation of Traveling Salesman Problem (TSP) based on Dijkstra's Algorithm in the Information System of Delivery Service

M. Firman Aji Syahputra, Riri Nada Devita, Sherly Allsa Siregar, Kartika Candra Kirana

Abstract

Traveling Salesman Problem (TSP) was defined as a task for finding of the shortest route. The finding  of  the  shortest  route influences a price of delivery service and profit of company.  Therefore, we proposed an implementation of Traveling Salesman Problem (TSP) based on Dijkstra’s Algorithm in a information systems of delivery services" for optimizing the finding of shortest route. This algorithm using distance which is extracted from Google Maps. There are 60 routes which are tested. The results show the accuracy of TSP based on Dijkstra’s algorithm is 100%. The results can be concluded that the implementation of Dijkstra’s algorithm is accurate for finding the shortest route.

Full Text:

PDF

References

Y.Y. Sheng, “The Role of Transportation in Logistics Chain”, Proceedings of the Eastern Asia Society for Transportation Studies, Vol. 5, pp. 1657 - 1672, 2005

M.I.C., Tunon and M.R. Lopez.”Design and Use of the CPAN Branch and Bound for The Solution of the Travelling Salesman Problem (TSP)” International Conference on Electronics, Communication and Computers, Conielecomp, 1 August 2005.

Pragya, M.Dutta, and Pratyush, “TSP Solution Using Dimentional Ant Colony Optimization”, International Conference on Advanced Computing & Communication Technologies, 6 April 2015.

M.M. Mena, R.H. Ucan, V.C. Vetina, and F.M. Ramirez, “Web Services Compotition using the Bidirectional Dijktra Algorithm” IEEE Latin America Transaction, vol 14, issue 5, May 2016

A. Ratnasari, F. Ardiani, F. Nurvita. “Penentuan Jarak Terpendek dan Jarak Terpendek Alternatif menggunakan Algoritma Dijkstra serta Estimasi Waktu Tempuh”. Universitas Islam Indonesia. ISBN: 979-26-0266-6. Yogyakarta 2013

E. Kasturi and S. Lakshmi Narayanan, “A Novel Approach to Hybrid Genetic Algorithms to Solve Symmetric TSP”, Volume 2, Issue 2, February 2014, ISSN: 2321-7782.

Mohd. Junedul Haque and Khalid. W. Magld. “Improving the Solution of Traveling Salesman Problem Using Genetic, Memetic Algorithm and Edge assembly Crossover”, (IJACSA) International Journal of Advanced Computer Science and Applications, Vol. 3, No. 7, 2012.

Adewole Philip, Akinwale Adio Taofiki and Otunbanowo Kehinde, “A Genetic Algorithm for Solving Travelling Salesman Problem” (IJACSA) International Journal of Advanced Computer Science and Applications, Vol. 2, No.1, January 2011.

Dweepna Garg and Saurabh Shah, “Ant Colony Optimization For Solving Traveling Salesman Problem”, International Journal of Computer Science and System Analysis Vol. 5, No. 1, January-June 2011, pp. 23-29, ISSN 0973-7448.

Vaibhavi Patel and Prof. ChitraBaggar, “A Survey Paper of Bellman-Ford Algorithm and Dijkstra Algorithm For Finding Shortest Path in GIS Application”, International Journal of P2P Network Trends Technology(IJPTT), Vol. 5 february 2014

Ni Kai, Zhang Yaoting, Ma Yuepeng, "Shortest Path Analysis Based on Dijkstra's Algorithm in Emergency Response System" Indonesian Journal of Electrical Engineering and COmputer Science, vol. 12, no. 5, pp 133-139, 2015

S.S. Biswas, B. Alam and M.N. Doja, "Generalization of Dijkstra’s Algorithm for Extraction ff Shortest Paths In Directed Multigraphs " Journal of Computer Science, vol. 9, no.3, pp. 377-382, 2013

Muhamad Ibrahim, Hadi Muhammad Diar and Gandi Suryanto, “Perancangan Sistem Rute Terpendek Menggunakan Algoritma Greedy”. Universitas Komputer Indonesia, January 2014.

Hendy Setiady and Yulistia. “Sistem Informasi Pemesanan dan Penjualan Berbasis Web pada Dewi Florist”. STMIK GI MDP, August 2012.

Andri Kristanto, “Perancangan Sistem Informasi dan Aplikasinya”.

Yogyakarta: Gava Media, 2008.

G.G Gable; D. Sedera, T. Chan,"Re-conceptualizing Information System Success: The IS-Impact Measurement Model" Journal of the Association for Information Systems, vol. 9, no. 7, pp. 377-408. 2008

Rahayu Ningati, “Aplikasi Pencarian Rute Terpendek Daerah Wisata Kota Kediri menggunakan Algoritma Dijkstra”. Universitas Nusantara PGRI Kediri, 2014.

Refbacks

  • There are currently no refbacks.