Salah satu tugas pengoptimalan yang paling umum adalah pemilihan rute kendaraan, yang tujuannya adalah menemukan rute terbaik untuk armada kendaraan yang mengunjungi kumpulan lokasi. Biasanya, "terbaik" berarti rute dengan total jarak atau biaya terendah. Berikut adalah beberapa contoh masalah perutean:
- Sebuah perusahaan pengiriman paket ingin menetapkan rute bagi pengemudi untuk melakukan pengiriman.
- Sebuah perusahaan TV kabel ingin menetapkan rute bagi teknisi untuk melakukan panggilan layanan rumah.
- Sebuah perusahaan transportasi online ingin menetapkan rute bagi pengemudi untuk mengangkut dan menurunkan penumpang.
Masalah rute yang paling terkenal adalah Masalah Penjual Bepergian (TSP): menemukan rute terpendek untuk staf penjualan yang perlu mengunjungi pelanggan di lokasi berbeda dan kembali ke titik awal. TSP dapat direpresentasikan dengan grafik, dengan node sesuai dengan lokasi, dan tepi (atau lengkungan) menunjukkan perjalanan langsung antarlokasi. Misalnya, grafik di bawah menunjukkan TSP dengan hanya empat lokasi, yang diberi label A, B, C, dan D. Jarak antara dua lokasi diberikan dengan angka di samping tepi yang menggabungkan keduanya.
Dengan menghitung jarak semua kemungkinan rute, Anda dapat melihat bahwa rute terpendek adalah ACDBA, yang total jaraknya adalah 35 + 30 + 15 + 10 = 90.
Masalah akan semakin sulit ketika ada lebih banyak lokasi. Pada contoh di atas, hanya ada enam rute. Namun, jika ada sepuluh lokasi (tidak termasuk titik awal), jumlah rutenya adalah 362880. Untuk 20 lokasi, angka akan melompat ke 2432902008176640000. Penelusuran menyeluruh terhadap semua kemungkinan rute akan dijamin untuk menemukan rute yang terpendek, tetapi cara ini secara komputasi sulit dipahami untuk semua, kecuali kumpulan lokasi yang kecil. Untuk masalah yang lebih besar, teknik pengoptimalan diperlukan untuk menelusuri ruang solusi secara cerdas dan menemukan solusi yang optimal (atau hampir optimal).
Versi TSP yang lebih umum adalah masalah pemilihan rute kendaraan (VRP), yang berisi beberapa kendaraan. Dalam sebagian besar kasus, VRP memiliki batasan: misalnya, kendaraan mungkin memiliki kapasitas untuk berat atau volume maksimum item yang dapat dibawa, atau pengemudi mungkin diharuskan untuk mengunjungi lokasi selama jangka waktu tertentu yang diminta oleh pelanggan.
Alat OR dapat menyelesaikan banyak jenis VRP, termasuk hal berikut:
- Masalah Penjual Keliling, masalah pemilihan rute klasik saat hanya ada satu kendaraan.
- Masalah pemilihan rute kendaraan, generalisasi TSP dengan beberapa kendaraan.
- VRP dengan batasan kapasitas, yaitu kendaraan memiliki kapasitas maksimum untuk item yang dapat dibawa.
- VRP dengan periode waktu, saat kendaraan harus mengunjungi lokasi dalam interval waktu yang ditentukan.
- VRP dengan batasan resource, seperti ruang atau personel untuk memuat dan menurunkan muatan kendaraan di depot (titik awal untuk rute).
- VRP dengan penurunan kunjungan, yang mengharuskan kendaraan tidak diwajibkan mengunjungi semua lokasi, tetapi harus membayar denda untuk setiap kunjungan yang dibatalkan.
Batasan dalam memecahkan masalah pemilihan rute kendaraan
Masalah pemilihan rute kendaraan pada dasarnya sulit dilakukan: lamanya waktu yang diperlukan untuk menyelesaikannya akan bertambah secara eksponensial seiring dengan ukuran masalah. Untuk masalah yang cukup besar, mungkin diperlukan OR-Tools (atau software pemilihan rute lainnya) bertahun-tahun untuk menemukan solusi yang optimal. Akibatnya, OR-Tools terkadang menampilkan solusi yang bagus, tetapi tidak optimal. Untuk menemukan solusi yang lebih baik, ubah opsi pencarian untuk pemecahnya. Lihat artikel Mengubah strategi penelusuran sebagai contohnya.