The Comparison of Brute Force, Cheapest-Insertion, and Nearest-Neighbor Heuristics for Determining the Shortest Tour for Visiting Malls in Bandar Lampung

Meli Amelia, Ilma Isyahna Sholeha, Yanda Rico Revangga, Wamiliana Wamiliana

Abstract


A mall is a sizable retail complex made up of numerous stores, as well as restaurants and other commercial spaces, all situated in one huge building or a collection of related or neighboring buildings. In this study we will compare the heuristics which are Brute Force, Cheapest-Insertion, and Nearest-Neighbor heuristics to find the shortest route from one mall to other eight malls in Bandar Lampung exactly once and back to the origin. The problem of finding the shortest route from original location, and go to every location exactly once, and back to original location is known as The Travelling Salesman Problem. Implementing on the data of the locations of those nine malls, the Brute Force Heuristic gives the total length 32,8 km, Cheapest-Insertion Heuristic 33,2 km, and Nearest-Neighbor Heuristic 33,35 km. However, in term of efficiency, the Brute Force is not efficient because we have to search for all possible solutions.

Keywords


Brute Force; Cheapest Insertion; Nearest Neighbor; Heuristics

Full Text:

PDF

References


K. Saleh, Helmi, & B. Prihandono, B. Penentuan Rute Terpendek Dengan Menggunakan Algoritma Cheapest Insertion Heuristic (Studi Kasus: PT. Wicaksana Overseas International Tbk. Cabang Pontianak). Buletin Ilmiah Math. Stat. Dan Terapannya (Bimaster), 04(3), 295–304, 2015.

K. Rosen. Discrete Mathematics and Its Applications, 7thEd. McGraw-Hill, New York, 2012

E. L. Lawler. The Travelling Salesman Problem: A Guided Tour of Combinatorial Optimization John Wiley & sons, 1985.

M. Kurniawan, F. Farida, and S. Agustini,"Rute Terpendek Algoritma Particle Swarm Optimization dan Brute Force untuk Optimasi Travelling Salesman Problem, Jurnal Teknik Infoematika, Vol. 14 No. 2, 191-200, 2021.

S. Violina, "Analysis of Brute Force and Branch & Bound Algorithms to solve the Traveling Salesperson Problem (TSP)", Turkish Journal of Computer and Mathematics Education, 12(8), 1226–1229, 2021.

A. Wilson, Y. Sibaroni, and I. Ummah, "Analisis Penyelesaian Traveling Salesman Problem Dengan Metode Brute Force Menggunakan Graphic Processing Unit", 2(1), 1874-1883, 2015.

Kusrini and J. E., Istiyanto, J.E., “Penyelesain Travelling Salesman Problem dengan Algoritma Cheapest Insertion Heuristic dan Basis Data”, Jurnal Teknik Informatika: 8(2)109-114, 2007.

F., Fargiana, R. Respitawulan, Y. Fajar, D. Suhaedi, and E. Harahap. "Implementation of Cheapest Insertion Heuristic Algorithm in Determining Shortest Delivery Route", International Journal of Global Operations Research, 3(2), 37–45, 2022. https://doi.org/10.47194/ijgor.v3i2.137

M. Hilman, and Y. Sidik. "Penentuan Rute Distribusi Menggunakan Metode Cheapest Insertion Heuristic (Cih) Guna Meminimalkan Pengeluaran Biaya Pada Ukm Aren Creativity Di Kabupaten Ciamis", Jurnal Industrial Galuh, 4(2), 51–61,2023. https://doi.org/10.25157/jig.v4i2.3017

D. T. Wiyanti, D. T. "Algoritma Optimasi Untuk Penyelesaian Travelling Salesman Problem", Jurnal Transformatika",11(1),1-6,2013. https://doi.org/10.26623/transformatika.v11i1.76

E. Yulianto, and A. Setiawan, A. "Optimasi Rute Sales Coverage Menggunakan Algoritma Cheapest Insertion Heuristic Dan Layanan Google Maps Api", INTERNAL (Information System Journal), 1(1), 39–54, 2018. https://doi.org/10.32627/internal.v1i1.326

S.A. Nene, and S. K. Nayar. "A Simple Algorithm for Nearest Neighbor Search in High Dimensions", (Vol. 4, Issue 1, 1995. Department of Computer Science, Columbia University. IEEE Transaction on Pattern Analysis and Machine Intelligence", Vol. 19, 1, 989-1003, 1997.

Sutoyo, I, " Penerapan Algoritma Nearest Neighbour untuk Menyelesaikan Travelling Salesman Problem", Paradigma - Jurnal Komputer Dan Informatika, XX (1), 101–106, 2018




DOI: http://dx.doi.org/10.36448/expert.v14i1.3715

Refbacks

  • There are currently no refbacks.


EXPERT: Jurnal Manajemen Sistem Informasi dan Teknologi

Published by Pusat Studi Teknologi Informasi, Fakultas Ilmu Komputer, Universitas Bandar Lampung
Gedung M Lt.2 Pascasarjana Universitas Bandar Lampung
Jln Zainal Abidin Pagaralam No.89 Gedong Meneng, Rajabasa, Bandar Lampung,
LAMPUNG, INDONESIA

Indexed by:



Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.