Traveling Salesman Problem: Definisi dan Implementasi

Traveling Salesman Problem: Definisi dan Implementasi

Traveling Salesman Problem (TSP) – Menentukan rute penjualan terbaik masih menjadi tantangan yang dihadapi oleh para sales hingga saat ini. 

Keberadaan beberapa platform peta masih dirasa kurang membantu para sales dalam memetakan rute mana yang bisa mereka lalui sekali jalan hingga sampai di titik awal kembali.

Sebab, beberapa platform hanya memberikan informasi mengenai cara pergi dari lokasi A ke lokasi B, tetapi tidak mengoptimalkan rute ketika kita menemui lebih dari satu persimpangan dan juga tidak membantu dalam proses sales lainnya.

Apakah perusahaan Anda mengalami permasalahan tersebut?

Salah satu solusi yang bisa digunakan oleh para pelaku usaha untuk mengatasi masalah diatas adalah dengan memanfaatkan Travelling Salesman Problem

Mengenal Travelling Salesman Problem (TSP)

Traveling Salesman Problem
image via wikipedia
 

Travelling salesman problem atau TSP adalah tantangan untuk menemukan rute terpendek dan efisien bagi seseorang sesuai daftar tujuan tertentu. 

TSP pertama kali diperkenalkan pada tahun 1930-an oleh Karl Menger seorang ahli matematika dan ekonomi. Menger menyebutnya sebagai “Messenger Problem” yakni masalah yang dihadapi oleh pengirim surat dan banyak pengelana.

Untuk lebih mudah memahami TSP, perhatikan contoh dibawah ini.

Seorang sales  ingin mengunjungi beberapa lokasi untuk menawarkan produk mereka. Dia mengetahui nama dari area tersebut dan jarak antar masing-masing rumah.

TSP berusaha menjawab pertanyaan tentang rute terpendek mana yang harus dilalui oleh sales tersebut  sehingga dia hanya mengunjungi setiap lokasi sekali saja sebelum kembali ke titik awal.

Tantangan yang Dihadapi Oleh Sales

Tentu di luar sana terdapat puluhan hingga belasan rute berbeda yang bisa dipilih, namun menemukan rute terbaik yang hanya bisa ditempuh dengan jarak yang pendek dan sedikit memakan biaya merupakan pekerjaan yang tidak mudah. 

Dikutip dari Roitific, jika kita memiliki 10 tempat tujuan, maka akan ada lebih dari 300,000 permutasi dan kobinasi rute berangkat dan pergi, sedangkan dengan 15 tujuan, jumlah rute bisa melebihi 87 miliar.

Tanpa menggunakan rute terpendek, sales akan memakan banyak waktu untuk sampai ke tempat tujuan, belum lagi jika menemui berbagai pilihan rute jika gagal memilih rute yang efisien akibatnya akan menaikkan biaya operasional perusahaan.

Solusi Travelling Salesman Problem Bagi Bisnis

Biasanya, setiap sales sudah memiliki jadwal dan tak jarang mereka juga menerima janji pertemuan yang tiba-tiba dibuat dengan klien mereka.  

Oleh sebab itu, tim sales jarang memiliki waktu kerja yang tetap dan terkadang harus menempuh rute yang jauh untuk menemui klien tersebut. Sayangnya, dengan melewati rute yang lebih panjang, mereka terkadang melewatkan janji penting  dan peluang  bisnis yang berharga. 

Disinilah peran penting dari Travelling Sales Person yakni untuk menghindari hal-hal diatas. Seperti yang sudah sempat dijelaskan diatas, TSP berguna untuk menemukan rute terpendek ke beberapa kota atau tujuan dan kembali ke tempat asal.

Berikut beberapa solusi yang sering digunakan untuk Travelling Salesman Problem;

Pendekatan The Brute-Force 

Pendekatan The Brute-Force atau juga dikenal dengan pendekatan Naive adalah mengkalkulasi dan membandingkan semua kemungkinan permutasi dari rute untuk menentukan solusi rute terpendek.

Jika menggunakan pendekatan ini, pelaku usaha perlu menghitung jumlah rute dan gambar serta membuat daftar semua rute yang memungkinkan. Menghitung jarak dari setiap rute dan kemudian memilih yang terpendek.

Metode The Branch dan Bound 

Metode ini membagi permasalahan untuk diselesaikan kedalam beberapa sub masalah.  Jika menggunakan metode ini, pelaku usaha perlu untuk memilih titik atau node keberangkatan kemudian buatlah pilihan ke berbagai tujuan.

Pilih lengkungan termudah antara titik yang belum dikunjungi dan saat ini dan kemudian tambahkan jarak ke jarak saat ini.

Ulangi proses hingga  jarak saat ini kurang dari batas. Jika jarak saat ini kurang dari batas, maka hasilnya akan terlihat.

Metode The Nearest Neighbor

Metode terakhir adalah the Nearest Neighbor. Kunci dari metode ini adalah selalu mengunjungi tujuan terdekat terlebih dahulu dan kemudian kembali ke kota awal saat semua kota sudah dikunjungi.

Cara menggunakan metode ini adalah, pilih sebua kota secara rondom kemudian lihat dan cari kota terdekat yang belum dikunjungi dan pergi kesana. Setelah sales mengunjungi semua kota, sales harus kembali ke kota keberangkatan.

Implementasi Travelling Salesman Problem

Salah satu contoh penerapan dari TSP adalah penggunaanya untuk last mile delivery yakni pengiriman barang dari pusat transportasi seperti depot atau warehouse ke tempat pelanggan.

Last mile delivery ini memakan banyak biaya pengiriman yakni hingga 28%, biasanya perusahaan menanggung biaya tersebut agar bisa berkompetisi di pasaran.

Namun, faktanya biaya pengiriman last mile perusahaan rata-rata $10, atau Rp. 150,432  tetapi pelanggan hanya membayar rata-rata $8 atau Rp. 120,346.

Inilah sebabnya mengapa bisnis ingin meminimalisir biaya dari pengiriman last mile. Pengurangan biaya tersebut pada dasarnya adalah menggunakan Vehicle Routing Problem. VRP sendiri merupakan versi umum dari TSP.

Fungsi utamanya adalah menemukan serangkaian rute untuk mengurangi biaya pengiriman. Permasalahannya  biasanya melibatkan satu set lokasi depot, ratusan lokasi pengiriman, dan beberapa kendaraan.

Route Planning untuk Sales Lapangan dengan LOKASI Enterprise

Melakukan perencanaan rute menjadi salah satu kunci sukses untuk perusahaan. Semakin efisien rute yang dimiliki maka akan semakin cepat pula sales lapangan tiba di tempat tujuan. 

Sehingga akan mengurangi waktu mengendarai kendaraan dan lebih banyak waktu untuk bekerja. 

Platform kami, LOKASI Enterprise dapat membantu pelaku usaha untuk menganalisis dan menemukan rute terbaik dan efisien untuk sales lapangan. Dengan melakukan hal tersebut, pelaku usaha dapat menghemat biaya pengiriman, meningkatkan kepuasan pelanggan, dan menghemat biaya operasional. 

Pelajari lebih lanjut dengan menghubungi [email protected] atau WhatsApp di 087779077750.

Related Posts