Penentuan lokasi awal optimal bagi traveling salesman

Abstract

Salah satu model network yang terkenal adalah Traveling salesman problem (TSP). Modifikasi dari model ini adalah minisum traveling salesman location problem (masalah MSTSL). Berbeda dengan TSP, masalah MSTSL ini bertujuan menentukan lokasi (node) awal optimal bagi pedagang keliling sehingga diharapkan dapat diperoleh rute yang meminimalkan jarak perjalanan pedagang. Masalah MSTSL ini dilatarbelakangi oleh ide membangun cabang perusahaan baru pada suatu lokasi tertentu. Cabang perusahaan ini nantinya akan dilengkapi dengan armada kendaraan (unit servis) yang akan digunakan untuk memenuhi panggilan servis dari pelanggan yang sudah tercatat di dalam daftar. Masing- masing pelanggan hanya dapat memberikan sebuah panggilan dengan peluang memberikan panggilan akan diberikan. Sehingga jika terdapat pelanggan yang potensial maka akan ada 2" - 1 tur yang mungkin dijalani oleh unit servis. Sedangkan daftar hanya akan berisi paling banyak b panggilan pertama dari pelanggan dengan b ≤n. Penentuan lokasi bagi pembangunan cabang perusahaan ini diharapkan dapat meminimalkan jarak perjalanan bagi unit servis. Pada awalnya penentuan lokasi awal optimal ini dilakukan dengan mencari jarak perjalanan harapan unit servis yang terpendek dari semua kemungkinan rute yang ada. Dengan menggunakan metode ini diperlukan nilai peluang masing-masing pelanggan memerlukan servis (h,) dan jarak antar lokasi dimana pelanggan tinggal. Karena metode ini menghitung jarak perjalanan harapan untuk semua kemungkinan maka cara ini tidak praktis. Lalu dikembangkan suatu algoritma, yaitu Algoritma 1, yang menyederhanakan proses pencarian lokasi awal optimal. Algoritma I ini tidak memerlukan jarak antar lokasi, melainkan hanya h, yang digunakan untuk mencari lokasi awal optimal. Apabila h; bernilai sama untuk semua pelanggan, Algoritma 1 dapat lebih disederhanakan menjadi Algoritma 2 yang tidak lagi memerlukan h,, tetapi hanya memerlukan banyaknya node pada salah satu partisi di network. Kedua algoritma tersebut berorde O(n).