En yaygın optimizasyon görevlerinden biri, bir dizi konumu ziyaret eden araç filoları için en iyi rotaları bulmak olan araç yönlendirme işlemidir. "En iyi", genellikle toplam mesafesi veya maliyeti en düşük olan rotaları ifade eder. Yönlendirme sorunlarına ilişkin birkaç örnek aşağıda verilmiştir:
- Bir kargo teslimatı şirketi, sürücülere teslimat yapmak için rota belirlemek istiyor.
- Bir kablo TV şirketi, ev hizmetleri aramaları için teknisyenlere rota atamak istiyor.
- Bir araç paylaşım şirketi, sürücülere yolcu alma ve bırakma için rota belirlemek istiyor.
En bilinen yönlendirme sorunu Seyahat Sorumlusu Sorunu (TSP): Farklı konumlarda bulunan müşterileri ziyaret etmesi ve başlangıç noktasına geri dönmesi gereken bir satış görevlisi için en kısa rotayı bulun. Bir TSP, düğümlerin konumlara karşılık geldiği ve kenarların (veya yayların) konumlar arasındaki doğrudan seyahati gösterdiği bir grafikle temsil edilebilir. Örneğin, aşağıdaki grafikte A, B, C ve D olarak etiketlenmiş yalnızca dört konumu olan bir TSP gösterilmektedir. Herhangi iki konum arasındaki mesafe, bu konumları birleştiren kenarın yanındaki sayıyla verilir.
Olası tüm rotaların mesafelerini hesaplayarak en kısa rotanın ACDBA olduğunu ve toplam mesafenin 35 + 30 + 15 + 10 = 90 olduğunu görebilirsiniz.
Daha fazla konum olduğunda sorun daha da zorlaşır. Yukarıdaki örnekte yalnızca altı rota var. Ancak on konum varsa (başlangıç noktası sayılmıyorsa) rota sayısı 362880 olur. 20 konum için sayı 2432902008176640000'e atlanır. En kısa rotayı bulmak için mümkün olan tüm rotaları ayrıntılı bir şekilde aramanız gerekir. Ancak bu, küçük konum grupları dışındaki tüm konumlar için hesaplama açısından zor bir işlemdir. Daha büyük problemlerde, çözüm alanında akıllı bir arama yapmak ve optimum (veya optimuma yakın) bir çözüm bulmak için optimizasyon teknikleri gerekir.
TSP'nin daha genel bir versiyonu, birden fazla aracın bulunduğu araç yönlendirme sorunudur (VRP). Çoğu durumda VRP'lerin kısıtlamaları vardır: Örneğin, araçlar taşıyabilecekleri maksimum ağırlık veya öğe hacmine uygun kapasitelere sahip olabilir ya da sürücülerin müşterilerin talep ettiği belirli zaman aralıklarında konumları ziyaret etmeleri gerekebilir.
VEYA-Araçları, aşağıdakiler de dahil olmak üzere birçok VRP türünü çözebilir:
- Seyahat Personeli Problemi: Bu, tek bir aracın bulunduğu klasik yönlendirme problemidir.
- Araç rota izleme problemi: TSP'nin birden fazla araç içeren genelleştirilmesi.
- Araçların taşıyabilecekleri öğeler için maksimum kapasiteye sahip olduğu kapasite kısıtlamalarına sahip VRP.
- Araçların belirli zaman aralıklarında konumları ziyaret etmesi gereken zaman aralıklarına sahip VRP.
- Araçları garajda yüklemek ve boşaltmak için alan veya personel (rotaların başlangıç noktası) gibi kaynak kısıtlamalarına sahip VRP.
- Araçların tüm konumları ziyaret etmek zorunda olmadığı, ancak bırakılan her ziyaret için ceza ödemesi gereken ziyaret edilen sanal gerçeklik (VRP).
Araç rota belirleme sorunlarının çözümüyle ilgili sınırlamalar
Araç rota bulma problemleri, doğası gereği inatçı değildir: Bu sorunları çözmek için gereken süre sorunun boyutuyla birlikte katlanarak artar. Yeterince büyük sorunlar için optimum çözümü bulmak VEYA araçlarının (veya başka bir yönlendirme yazılımının) yıllarca geçmesi gerekebilir. Sonuç olarak, VEYA araçları bazen iyi olan ancak optimum olmayan çözümler döndürür. Daha iyi bir çözüm bulmak amacıyla çözücü için arama seçeneklerini değiştirin. Örnek için Arama stratejisini değiştirme bölümüne bakın.