Aplikasi teori Graph untuk mendapatkan keuntungan optimum: Studi kasus pada CV Mitra Tour Dan Travel Jl. Hamid Rusdi No. K٠70 Malang

ABSTRAK

Teori graph merupakan bagian yang penting dalam matematika. Terdapat banyak aplikasi yang berkaitan dengan graph dan aplikasi teori graph dapat dimanfaatkan berbagai bidang. Didalam aplikasi tersebut graph digunakan sebagai alat untuk merepresentasikan atau memodelkan persoalan. Berdasarkan graph yang dibentuk, barulah persoalan tersebut dapat diselesaikan.

Salah satu aplikasi dari teori graph adalah menentukan sirkuit terpendek dalam graph pada persoalan pedagang keliling (Traveling Salesperson Problem- TSP). Nama persoalan ini diilhami oleh masalah seorang pedagang yang akan mengunjungi sejumlah kota dan menyinggahi setiap kota tepat satu kali dan kembali lagi ke kota asal keberangkatan. Persoalan perjalanan pedagang ini tidak lain adalah untuk menentukan sirkuit Hamilton yang memiliki bobot minimum pada sebuah graph terhubung.

Walaupun persoalan ini bernama perjalanan pedagang, namun penerapannya tidak hanya pada kasus yang berhubungan dengan pedagang. Aplikasi dari teori TSP diantaranya adalah untuk menentukan keuntungan yang optimum pada CV. Mitra Tour dan Travel. Tujuan aplikasi dari teori ini adalah untuk meminimumkan pengeluaran dan mengoptimumkan keuntungan, dengan cara mencari jalur terdekat, karena dengan melewati jalan yang lebih dekat tentunya akan meminimkan pengeluaran untuk bahan bakar (solar).

Jalur atau rute terpendek dari Malang menuju tempat pariwisata ke Yogyakarta dengan menggunakan teori TSP yang berjarak 872,14 km, dan menghabiskan solar sebanyak 379,2 liter, dengan harga total Rp 663.600,00, jalur tersebut dimulai dari Malang (ML) - Pare (PE) - Kediri (KI) - Nganjuk (NJ) - Mejayan (ME) — Ngawi (NW) — Surakarta (SR) - Bawen (BW) — Magelang (MG) - Candi Borobudur (BB) - Semanu (SM) - Mayudan (MY) - Tempel (TL) - Monjali (MJ) - Malioboro (MB) - Catur Tunggal (CT) - Yogyakarta (YK) — Nogotirto (NG) - Kasihan (SH) - Kasongan (KG) - Pendowo Haijo (PD) - Palbapang (PB) - Barongan (BN) - Parang Tritis (PT) - Pundung (PN) - Singosaren (SS) - Sewon (SW) - Panggung Haijo (PH) - Keraton Yogyakarta (KY) - Kerajinan Perak (KP) - Kutho Gedhe (KD) - Bangun Tapan (BT) - Depok (DP) - Marguwo Harjo (MH) - Prambanan (PR) - Piyungan (PY) - Gading (GD) - Playen (PL) - Logandeng (LG) - Semanu (SU) - Bedoyo (BD) - Giritontro (GI) - Pacitan (PA) - Ponorogo (PO) - Trenggalek (TR) - Tulungagung (TA) - Blitar (BL) - Malang (ML).

Adapun jalur yang diambil CV Mitra Tour dan Travel JI. Hamid Rusdi No. K-70 Malang adalah berjarak 916,88 km dan menghabiskan bahan bakar (solar) sebanyak 400 liter dengan total harga Rp 700.000,00. Jadi jalur yang diambil CV Mitra Tour dan Travel lebih jauh dengan selisih 44,74 km.