Minimization of time distribution of ballots with Greedy algorithms in Jombang Regency

Erina Seviyanti Dewi*  -  Universitas Negeri Surabaya, Indonesia
Latifah Asmaul Fauzia  -  Universitas Negeri Surabaya, Indonesia

(*) Corresponding Author
DOI: 10.21580/jnsmr.2021.7.1.3687

Supp. File(s): common.other

Travelling Salesman Problem is a problem faced by salesmen in distributing goods by passing all points exactly once. This problem is often encountered in life, not least in the distribution of election ballots from the Komisi Pemilihan Umum Daerah (KPUD) Jombang office to the sub-district office in Jombang Regency. Proper route determination can help to minimize the travelling time between places so that the risk of delaying ballot distribution can be avoided. In determining the solution of Traveling Salesman Problem, a Hamiltonian cycle is required. The Hamiltonian cycle is a closed trail that passes every point exactly one time. The Hamilton cycle can be formed by the Greedy Algorithm. The Greedy Algorithm can quickly determine the next point based on the smallest weight in the form of distance between points. From the problem of ballot distribution in Jombang, the starting point of the route is the office of Komisi Pemilihan Umum Daerah (KPUD) Jombang then through 21 sub-district offices and back to the Komisi Pemilihan Umum Daerah (KPUD) office Jombang. Based on the searching for solutions to minimize the distribution time of ballots in Jombang Regency with Greedy Algorithm, the total distance to pass all existing sub-district offices is 253.1 km with a travel time of 427 minutes or 7 hours 7 minutes.

©2021 JNSMR UIN Walisongo. All rights reserved.

Supplement Files

Keywords: time minimization; distribution of ballots; greedy algorithms; ballots; KPU

  1. N. Agatz, P. Bouman, and M. Schmidt, “Optimization approaches for the traveling salesman problem with drone,” Transp. Sci., vol. 52, no. 4, pp. 965–981, 2018.
  2. D. Davendra, Traveling Salesman Problem: Theory and Applications. BoD–Books on Demand, 2010.
  3. B. P. Fatmawati and E. Noviani, “Penyelesaian Travelling Salesman Problem Dengan Metode Tabu Search,” BIMASTER, vol. 4, no. 01, 2015.
  4. A. A. A. Fatma A. Karkory, “Implementation of Heuristics for Solving Travelling Salesman Problem Using Nearest Neighbour and Minimum Spanning Tree Algorithms,” vol. 7, no. 10, pp. 1524–1534, 2013.
  5. F. S. P. ,Awang Harizka, “Implementasi Metode Ant Colony Untuk Traveling Salesman Problem Menggunakan Google Maps Pada Kota-Kota Di Jawa,” vol. 1, no. 2, pp. 12–20, 2014.
  6. W. M. Hameed, A. Baker Kanbar, and A. Lecturer, “A Comparative Study of Crossover Operators for Genetic Algorithms to Solve Travelling Salesman Problem,” Int. J. Res., vol. 5, no. 2, pp. 284–291, 2017, doi: 10.5281/zenodo.345734.
  7. M. Yousefikhoshbakht, N. Malekzadeh, and M. Sedighpour, “Solving the Traveling Salesman Problem Based on The Genetic Reactive Bone Route Algorithm with Ant Colony System,” Int. J. Prod. Manag. Eng., vol. 4, no. 2, p. 65, 2016, doi: 10.4995/ijpme.2016.4618.
  8. D. Wicaksana and A. Alamsyah, “Solusi Travelling Salesman Problem Menggunakan Algoritma Fuzzy Evolusi,” Unnes J., vol. 3, 2014.
  9. W. Zulkarnaen, I. D. Fitriani, B. Sadarman, and N. Yuningsih, “Evaluasi Kinerja Distribusi Logistik KPU Jawa Barat Sebagai Parameter Sukses Pilkada Serentak 2018,” JIMEA J. Ilm. MEA (Manajemen, Ekon. dan Akuntansi), pp. 251–252, 2020.
  10. I. Tristanti, “Surat Suara Tertukar Pada Pemilu Legislatif Tahun 2014 Di Jawa Timur: Studi Tentang Distribusi Surat Suara Dari Perspektif Manajemen Logistik.” Universitas Airlangga, 2018.
  11. Y. Safitri, “Rancang bangun aplikasi
  12. pencarian lokasi wisata Kota Bogor Menggunakan algoritma Greedy Berbasis Android,” J. Techno Nusa Mandiri, vol. XI, no. 2, pp. 169–175, 2014.
  13. M. V. S. (Guide) Annu Malik, Anju Sharma, “Greedy Algorithms,” Int. J. Sci. Res., vol. 3, no. 8, pp. 29–42, 2013, doi: 10.1142/9789814271424_0002.
  14. N. H. Sardini, Restorasi penyelenggaraan pemilu di Indonesia. Fajar Media Press, 2011.
  15. D. T. Wiyanti, “Algoritma Optimasi Untuk Penyelesaian Travelling Salesman Problem,” J. Transform., vol. 11, no. 1, p. 1, 2018, doi: 10.26623/transformatika.v11i1.76.
  16. A. Levitin, Introduction to The Design and Analysis of Algorithms, vol. 6, no. 2. 2012.
  17. F. S. Efendi, M. Pinto, and H. Steven, “Implementasi Algoritma Greedy Untuk Melakukan Graph Coloring : Studi Kasus Peta Propinsi Jawa,” J. Inform., vol. 4, no. 1, pp. 440–448, 2010.
  18. G. Aristi, “Perbandingan algoritma greedy, algoritma cheapest insertion heuristics dan dynamic programming dalam penyelesaian travelling salesman problem,” Paradig. Komput. dan Inform., vol. 16, no. 2, pp. 52–58, 2014.
  19. S. Mondal, N. De, and A. Pal, “The M-polynomial of line graph of subdivision graphs,” Commun. Fac. Sci. Univ. Ankara Ser. A1 Math. Stat., vol. 68, no. 2, pp. 2104–2116, 2019.
  20. C. Vasudev, Graph theory with applications. New Age International, 2006.
  21. J. A. Bondy and U. S. R. Murty, Graph theory with applications, vol. 290. Macmillan London, 1976.

Open Access Copyright (c) 2021 Journal of Natural Sciences and Mathematics Research
Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

Journal of Natural Sciences and Mathematics Research
Published by Faculty of Science and Technology
Universitas Islam Negeri Walisongo Semarang

Jl Prof. Dr. Hamka Kampus III Ngaliyan Semarang 50185
Website: https://journal.walisongo.ac.id/index.php/JNSMR
Email:jnsmr@walisongo.ac.id

ISSN: 2614-6487 (Print)
ISSN: 2460-4453 (Online)

View My Stats

Lisensi Creative Commons

This work is licensed under a Creative Commons Lisensi Creative Commons .

apps