Çok gezginli en küçük gecikme problemi için yeni karar modelleri

En küçük Gecikme Problemi (EGP) rotalama problemlerinin temelini oluşturan Gezgin Satıcı Probleminin (GSP) bir türü olmaktadır. EGP, bir başlangıç düğümünden başlayarak, tüm düğümlere uğradıktan sonra başlangıç noktasında veya verilen bir düğümde sona eren Hamilton turunu veya yolunu araştırmaktadır. GSP bütün müşterilere uğramak için gerekli olan toplam zamanı en küçük yapmayı amaçlamakta, EGP ise tüm müşterilerin toplam gecikme zamanını en küçük yapmayı amaçlamaktadır. EGP'nin en önemli özel durumu olarak görülen çok gezginli uzantısı için kaynaklardaki yapılan çalışmalar incelendiğinde polinom sayıda ve üstel sayıda kısıta sahip iki farklı matematiksel model olduğu ancak bu modellere bakıldığında kısa sürede çözüme ulaşma açısından verimli olmadığı belirlenmiştir. Bu nedenle yeni karar modellerine ihtiyaç olduğu görülmüştür. Bu çalışma kapsamında ise, temel konu olarak ele alınan çok gezginli EGP için yapılacak çalışmanın altyapısını oluşturması amacıyla öncelikle EGP modelleri kaynaklarda bulunan kıyaslama problemi verileri kullanılarak sayısal analizlere tabi tutulmuştur. İşlem süresi (CPU) ve doğrusal programlama (LP) gevşetme değerleri yönüyle en iyi performans gösteren model belirlenmiştir. Çok gezginli EGP için üç tanesi yeni model bir tanesi kaynaklarda yer alan bir model olmak üzere toplam dört model ele alınıp kaynaklardaki farklı düğüm sayısına sahip kıyaslama problemleri ve gezgin sayıları için çözdürülerek en iyi performans gösteren model önerilmiştir. Yapılan bu karşılaştırmalı analizler sonucunda problem boyutu ve CPU süresi arasındaki ilişki ve gezgin sayısı ile CPU süresi arasındaki ilişki ile ilgili çıkarımlar da elde edilmiştir. Bu çalışmanın en önemli sonucu çok gezginli EGP için yeni bir modelin bilime katkı olarak sunulmasıdır.