Tabu Search – Ruang Pencarian & Struktur Neighborhood

Ruang pencarian bagi TS sama dengan ruang pencarian local search (LS). Semua transformasi lokal yang dapat diterapkan pada solusi saat ini (S) didefinisikan sebagai sekumpulan solusi dalam suatu ruang pencarian dan dinyatakan sebagai N(S) atau neighborhood dari solusi S (Gendreau, 2002). Secara formal, N(S) adalah sebuah bagian dari ruang pencarian yang didefinisikan oleh:

Kusumadewi dan Purnomo (2005) menyatakan bahwa kandidat solusi (Neighborhood) adalah suatu fungsi yang memetakan setiap solusi layak (feasible) S ke solusi-solusi yang lainnya. Jumlah solusi layak dalam neighborhood biasanya dibatasi dengan menggunakan berbagai kriteria untuk mengurangi waktu proses pencarian solusi.

Cordeau dan Laporte (2002) menyatakan ada dua cara membentuk neighborhood bagi TS untuk permasalahan penentuan rute kendaraan. Cara pertama, neighborhood dibentuk oleh perpindahan pelanggan antara dua rute sampai maksimal l-perpindahan (l–interchanges). Nilai l biasanya maksimal 2 pelanggan. Perpindahan tersebut dinyatakan oleh (l₁, l₂) (dengan l₁ £
l dan l₂ £
l) yang artinya dilakukan operasi pemindahan pelanggan sebanyak l₁ dari rute 1 ke rute 2, dan pemindahan pelanggan sebanyak l₂ dari rute 2 ke rute 1.

Cara kedua dikenal sebagai ejection chains yakni neighborhood dibentuk melalui perpindahan terhadap lebih dari dua rute pada saat bersamaan. Cara ini dilakukan dengan lebih dahulu mengidentifikasi sejumlah rute dan kemudian memindahkan vertek-vertek pelanggan dalam pola siklik dari rute 1 ke rute 2, rute 2 ke rute 3 dan seterusnya sehingga cara ini menghasilkan l perpindahan pada lebih dari satu rute.

Perancangan TS yang efisien sangat terkait dengan adanya keseimbangan yang baik antara kualitas neighborhood dengan waktu komputasi. Jumlah neighborhood yang banyak memberikan kemungkinan lebih banyak solusi yang dipertimbangkan pada tiap iterasi. Di saat yang sama, jumlah neighborhood yang banyak memerlukan waktu evaluasi kandidat yang lebih lama.

Isu lain terkait dengan neighborhood adalah dibolehkannya penerimaan suatu solusi yang tidak layak selama proses pencarian. Keuntungan mekanisme itu adalah kemungkinan munculnya solusi layak pada iterasi ke-t dan t+2 namun diantara kedua iterasi itu yakni iterasi t+1 berupa solusi tidak layak.

Sumber: Gendreau (2002), Kusumadewi dan Purnomo (2005), Cordeau dan Laporte (2002)