Shortest path problem wıth dısjunctıve conflıct constraınts

Bu çalışmada oklar arasındaki ayrık çatışma ilişkilerini de dikkate alan birden çoka en kısa yol probleminin bir uzantısı ele alınmaktadır. Ayırıcı çatışma kısıtlı en kısa yol problemi olarak adlandırılan bu problemde, en kısa yol ağacının herhangi bir çatışan ok çifti içermesine izin verilmez. Polinom olarak çözülebilen birçok birleşimsel eniyileme probleminde olduğu gibi, çatışma ilişkilerinin eklenmesi problemi NP-zor yapar. Bu tez kapsamında üç yeni algoritma önerilmektedir. Önerilen ilk algoritma, birden çoka en kısa yol probleminin çözümünden, etkili bir güncelleme yordamından ve dallanmayı budamak için hızlı bir olursuzluk saptama yönteminden yararlanan bir dal ve sınır algoritmasıdır. İkinci olarak, en kısa yol problemine özgü olurluluk gerekli koşullarından yararlanan, derinlik öncelikli bir dalış algoritması geliştirilmiştir. Üçüncü olarak, çatışma çizgesinin bağımsız kümelerini kullanan, verimli bir tur önleyici dizgeden ve yine hızlı bir olursuzluk saptayıcısından yararlanan bir dal ve sınır algoritması geliştirilmiştir. Son olarak, hem rastgele oluşturulmuş hem de gerçekçi test örnekleri üzerinde kapsamlı bir şekilde test edilen yeni algoritmalar, piyasada bulunan en son teknolojiye sahip bir karma tamsayılı doğrusal program çözücü ile karşılaştırılmıştır. Kapsamlı bilgisayısal deneylere göre, yeni algoritmalardan en etkin olanı çözücüden çok daha başarılıdır. Diğerlerinin başarımları ise karşılaştırılabilir düzeydedir.