CEVAP:

Rotalama problemleri genellikle bir serim (network) üzerinde gösterilir. Serim, düğümler ve ayrıtlardan oluşan bir yapıdır. Çoğu zaman düğümler kentleri veya kavşakları, ayrıtlar ise yolları gösterir. Ayrıtlarda yön olması, yolun tek yönlü olduğu anlamına gelir. Rotalama problemindeki temel ayrım, müşterilerin düğümlerde veya ayrıtlarda olduğu varsayımıyla oluşur. Örneğin; müşterileriniz kent merkezlerinde ise ve siz kentleri birbirine bağlayan yollardan oluşmuş bir serim çizdiyseniz, aracınızın rotası düğümlerden geçeceği için bu bir düğüm rotalama problemi olur. Genellikle şehirlerarası taşımalarda bu yapı söz konusu olur. Öte yandan müşterileriniz bir şehirdeki bakkallar ise ve araç bir yoldan geçtiğinde o yol üstünde bütün bakkallara uğruyorsa aracınızın ayrıtlardan geçmesi gerekiyor demektir. Bu da ayrıt rotalama adıyla anılır. Genellikle şehir içi taşımalar ayrıt rotalama grubuna girer. Örneğin; çöp kamyonlarının evlerin önünden çöp toplaması, bir postacının posta dağıtması, kargo şirketinin şehir için adreslerine kargoları dağıtması birer ayrıt rotalama problemidir. Düğüm rotalama probleminde çok sayıda araç olması ve araçların da taşıma kapasitelerinin olması hâlinde ortaya çıkan probleme, araç rotalama problemi (Vehicle routing problem) denmektedir. Ama ayrıt rotalama probleminde aynı koşullar altındaki probleme kapasiteli ayrıt rotalama problemi (Capacitated arc routing problem) denmektedir. Rotalama problemleri NP sınıfındadır. Bu nedenle de eniyi çözümlerini bulmak zordur. İyi bir çözüm bulmak için genellikle sezgisel algoritmalar kullanılmaktadır.