Eduvest � Journal of Universal Studies Volume 1 Number 8, August 2021 p- ISSN 2775-3735 e-ISSN 2775-3727
TRAVELLING SALESMAN PROBLEM ANALYSIS WITH COMPLETE ENUMERATION METHOD, BRANCH & BOUND AND GREEDY HEURISTIC
Sarah Nur Fatimah, Ifham Azizi Surya Syafiin and Muchammad Fauzi Widyatama University E-mail: [email protected], [email protected], [email protected]
ARTICLE INFO������� ABSTRACT
Received: July, 24^th 2021 Revised: August, 16^th2021 Approved: August, 18^th2021	PT XYZ as the best and largest Bed Sheet Set company in Indonesia with products such as Bed Covers, Bed Sheets, Pillowcases, Bolsters and Blankets. The Traveling Salesman Problem (TSP) is a problem faced in finding the best route to visit shops that sell products from PT BIG. A visit to the shop is carried out on the condition that each city can only be visited once except the city of origin. The algorithms applied in this TSP problem include the Complete Enumeration, Branch & Bound and Greedy Heuristic methods.
KEYWORDS	Travelling Salesman Problem (TSP), Complete Enumeration, Branch & Bound, Greedy Heuristic
	This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License

INTRODUCTION

PT XYZ, a company engaged in garments, especially the largest Bed Sheet Set & Bed Cover in Indonesia with product brands A and B (Faisal, Hardianto, Dwichwanto, & Septiana, 2021). These products are widely used by every community and have been spread in several big cities such as Subang, Sukabumi, Bogor and Bandung (Firman, Herlina, Paturochman, & Sulaeman, 2018). In the process of distributing products in each city, human labor is needed, one of which is through Sales Promotion (Susanto & Sunardi, 2017). Sales Promotion offers products to stores in big cities to sell products to consumers (Larissa, Yuwono, & Mardiono, 2017). The distribution of products in each city has obstacles in delivery with the distance from the city far enough (Chandra & RAHARDJO, 2013) so that the delivery of goods takes quite a long time (Putra, Nyoto, & Pratiwi, 2017). If product delivery takes a long time, it will result in delayed product delivery (Miradji, 2014) and product marketing cannot be done quickly (Toyib, Onsardi, & Muntahanah, 2020). For this reason, the company must be able to develop a plan to be able to create inter-city routes (Zulfikar, Mayvita, & Purboyo, 2019) that can minimize delivery time by arranging product delivery routes (Karundeng, Mandey, & Sumarauw, 2018). So that product marketing can be done effectively (Artaya & Purworusmiardi, 2019). The problem that will be discussed is that there is no optimal delivery route (Tanujaya, Dewi, & Endah, 2013) with the minimum total distance or cost and determining the best route (Muhammad, Bakhtiar, & Rahmi, 2017). Determination of delivery routes using Complete Enumeration, Branch & Bound and Greedy Heuristic methods.

RESEARCH METHODS

Data collection needed for this research, the authors use the following methods: (Pratama, Rahaningsih, Nurhadiansyah, & Purani, 2019)

1. Literature Study. The author collects materials as references from modules, journals, articles, internet on Complete Enumeration, Branch & Bound and Greedy Heuristic Methods.

2. Field Study. The author observes directly in the field based on the required data.

3. Data Collection. The data is taken based on the city that is often visited by sales and based on the distance traveled by the city.

4. Data Processing. The data is processed by analyzing problems in finding the shortest route using the Complete Enumeration, Branch & Bound and Greedy Heuristic methods.

5. Finding the Optimal Solution. Optimal solution is obtained based on the calculation of the shortest route. The shortest route deserves to be the Optimal Solution because it is more efficient.

RESULTS AND DISCUSSION

PT. XYZ will assign Sales Promotion to visit shops that sell products from PT. XYZ (Firmansyah, SE, Anita Roosmawarni, & SE, 2019). These shops are located in the cities of Subang, Sukabumi and Bogor (Taufiq, 2016). Determination of Sales Promotion travel routes in each city is obtained based on the distance of each city (Wijaya, Kristianto, Vanel, & Huwae, 2020). The data retrieval used will later be processed and determine the closest distance that will later be taken Here are the distances between cities: (Amri, Rahman, & Yuniarti, 2014)

Table 1. Distance between Cities

City	Bandung (0)	Subang (1)	Sukabumi (2)	Bogor (3)
Bandung (0)	-	57	96	124
Subang (1)	57	-	144	159
Sukabumi (2)	96	144	-	61
Bogor (3)	124	159	61	-

Based on data collection, the city of origin of the sales promotion is Bandung. Sales Promotion will travel to visit the store. The stores are located in the cities of Subang (1), Sukabumi (2) and Bogor (3). Sales Promotion requires the shortest distance in order to maximize travel and minimize costs. From these problems, the data was processed using the Complete Enumeration, Branch & Bound and Greedy Heuristic methods. Here are the results of Data Processing:

1. Complete Enumeration Method

Figure 1. Results of the Complete Enumeration Method

The results obtained using the Complete Enumeration method with the shortest distance of 373 km.

2. Branch & Bound Method

The results obtained using the Branch & Bound method with the shortest distance of 373 km.

3. Greedy Heuristic Method

Figure 3. Results of Greedy Heuristic Method

The results obtained using the Branch & Bound method with the shortest distance of 386 km.

Table 2 Total Distance

Method	Closest total distance (km)
Complete Enumeration	373
Branch and Bound	373
Greedy Heuristic	386

Based on the Complete Enumeration Method, the results obtained with a distance of 373 km. The Branch & Bound method obtained results with a distance of 373 km. The Greedy Heuristic method obtained 386 km results because it is different from the Complete Enumeration Method and the Branch & Bound Method which can pass through which city first as long as it does not pass through the city of origin. In the Greedy Heuristic Method from the origin of the city the closest distance is chosen then from the city that is being occupied to the next city the closest distance is chosen.

CONCLUSION

Based on the results of the analysis and distance determination, it is found that the Complete Enumeration and Branch & Bound methods are better methods than the Greedy Heuristic method. This is because the distance traveled by determining the Complete Enumeration and Branch & Bound has the same distance of 373 km, while the Greedy Heuristic Methods method has a further distance of 386 km.

REFERENCES

Amri, Mahardika, Rahman, Arif, & Yuniarti, Rahmi. (2014). Penyelesaian Vehicle Routing Problem dengan Menggunakan Metode Nearest Neighbor (Studi Kasus: MTP Nganjuk Distributor PT. Coca Cola). Jurnal Rekayasa Dan Manajemen Sistem Industri, 2(1), p36-45.

Artaya, I. Putu, & Purworusmiardi, Tubagus. (2019). Efektifitas Marketplace Dalam Meningkatkan Konsentrasi Pemasaran Dan Penjualan Produk Bagi Umkm Di Jawa Timur. Ekonomi Dan Bisnis, Universitas Narotama Surabaya, 1�10.

Chandra, Afridel, & RAHARDJO, Susilo Toto. (2013). Analisis kinerja distribusi logistik pada pasokan barang dari pusat distribusi ke gerai indomaret di kota semarang. Fakultas Ekonomika dan Bisnis.

Faisal, Achmad, Hardianto, Doni, Dwichwanto, Dwichwanto, & Septiana, Laila. (2021). Sprei Soulmate (Sutra Organik Super Lembut Anti Alergi) Motivasi Ikarinetti. Journal of Social Responsibility Projects by Higher Education Forum, 2(1), 20�24.

Firman, Achmad, Herlina, Linda, Paturochman, Maman, & Sulaeman, M. Munandar. (2018). Penenentuan Kawasan Unggulan Agribisnis Ternak Domba di Jawa Barat. Mimbar Agribisnis: Jurnal Pemikiran Masyarakat Ilmiah Berwawasan Agribisnis, 4(1), 111�125.

Firmansyah, M. Anang, SE, M. M., Anita Roosmawarni, S. E., & SE, M. (2019). Kewirausahaan (Dasar dan Konsep). Penerbit Qiara Media.

Karundeng, Thessa Natasya, Mandey, Silvya L., & Sumarauw, Jacky S. B. (2018). Analisis Saluran Distribusi Kayu (Studi Kasus di CV. Karya Abadi, Manado). Jurnal EMBA: Jurnal Riset Ekonomi, Manajemen, Bisnis Dan Akuntansi, 6(3).

Larissa, Bellen, Yuwono, Elisabeth Christine, & Mardiono, Bambang. (2017). Perancangan Promosi Produk Kosmetik Salsa. Jurnal DKV Adiwarna, 1(10), 10.

Miradji, Moh Afrizal. (2014). Analisis Supply Chain Management Pada PT. Monier Di Sidoarjo. BALANCE: Economic, Business, Management and Accounting Journal, 11(02).

Muhammad, Muhammad, Bakhtiar, Bakhtiar, & Rahmi, Meliza. (2017). Penentuan rute distribusi sirup untuk meminimalkan biaya transportasi. Industrial Engineering Journal, 6(1).

Pratama, Fidya Arie, Rahaningsih, Nining, Nurhadiansyah, Nurhadiansyah, & Purani, Lili. (2019). Sistem Informasi Akuntansi Kas Kecil Menggunakan Metode Dana Berubah. Journal of Innovation Information Technology and Application (JINITA), 1(01), 42�50.

Putra, Angga Kurnia, Nyoto, Rudy Dwi, & Pratiwi, Helen Sasty. (2017). Rancang Bangun Aplikasi Marketplace Penyedia Jasa Les Private Di Kota Pontianak Berbasis Web. JUSTIN (Jurnal Sistem Dan Teknologi Informasi), 5(1), 22�26.

Susanto, Agus, & Sunardi, Ahmad. (2017). Aktivitas Bauran Komunikasi Pemasaran Di Perusahaan Jamu Ibu Tjipto Kota Tegal. Komunikator, 9(1).

Tanujaya, William, Dewi, Dian Retno Sari, & Endah, Dini. (2013). Penerapan Algoritma Genetik untuk Penyelesaian Masalah Vehicle Routing di PT. MIF. Widya Teknik, 10(1), 92�102.

Taufiq, Muhammad. (2016). Keanekaragaman dan pemanfaatan tanaman buah pekarangan di Desa Cibulakan Kecamatan Cugenang Kabupaten Cianjur Jawa Barat. UIN Sunan Gunung Djati Bandung.

Toyib, Rozali, Onsardi, Onsardi, & Muntahanah, Muntahanah. (2020). Promosi Produk Pertanian Dan Kerajinan Menggunakan Website Serta Pembukuan Sederhanadi Desa Sido Dadi Kecamatan Arma Jaya Kabupaten Bengkulu Utara. Jurnal Pengabdian Masyarakat Bumi Raflesia, 3(1).

Wijaya, Lina Sinatra, Kristianto, Budhi, Vanel, Zon, & Huwae, George Nicholas. (2020). Pengembangan Model Strategi Integrated Marketing Communication (IMC) Dalam Upaya Meningkatkan City Image (Studi Kasus Pemerintah Kota Surakarta-Jawa Tengah). Jurnal Ilmiah Media, Public Relations, Dan Komunikasi (IMPRESI), 1(1).

Zulfikar, Rizka, Mayvita, Prihatini Ade, & Purboyo, Purboyo. (2019). Adopsi Teknik Penyusunan Business Plan Model Canvas Untuk Perencanaan Bisnis Umkm Kuliner Jalanan Di Kawasan Gatot Subroto Banjarmasin. Jurnal Pengabdian Al-Ikhlas Universitas Islam Kalimantan Muhammad Arsyad Al Banjary, 4(2).