The roaming salesman problem and its application to election logistics

Kampanya planlaması, rota belirleme, etkinlik takvimi programlama ve konaklama planlama ile ilgili olarak alınacak önemli kararlardan biridir. Kampanya planlayıcısının, zamanlama ve yönlendirme konusunda uygun bir kararla en iyi şekilde müşteri ziyaretlerini planlaması, zaman kısıtlarını belirlemesi ve faaliyetleri düzenlemesi gerekmektedir. Bu çalışmada, kampanya süresince çeşitli şehirlerden ödüller toplayarak seyahat eden bir gezgin satıcı için günlük turlar belirlemek amaçlı yeni bir problemi araştırıyoruz. Bu yeni probleme, seçim lojistiği, turistik gezi planlaması ve pazarlama kampanyaları dahil olmak üzere çeşitli gerçek hayat uygulamalarının neden olduğu dolaşım satıcı problemi (Roaming Salesman Problem, RSP) diyoruz. RSP, geleneksel periyodik Gezgin Satıcı Problemi (Traveling Salesman Problem, TSP) ile Ödül Toplayan TSP'nin statik ayrıt maliyetleri ve zamana bağlı düğüm ödülleri içeren bir kombinasyonu olarak tanımlanabilir. RSP, kazanılan tüm ödüllerin toplamından seyahat masraflarını çıkararak elde edilen net faydayı enbüyüklemek için, kampanya döneminin her bir günü açık veya kapalı bir tur arar. Satıcının tüm şehirleri ziyaret etmesi veya günlük turlarının aynı şehirde başlaması ve bitmesi gerekmez. Ayrıca satıcı bir sonraki günün turuna başlamak için şehirde bir gece konaklayabilir. Her şehir bir temel ödül ve sabit bir faaliyet süresi ile ilişkilidir. Ek olarak, satıcı belirli sayıda ardışık günden daha uzun bir süre kampanya merkezinin dışında kalamaz. İlaveten aynı gün içindeki etkinliklerin ve şehirler arası seyahatlerin toplam süresi belirli bir maksimum tur süresini aşamaz. Bu problem için mevcut rotalama kısıtlarını kabul ederek, tamamen yeni bir kısıt sınıfı ve ikili değişkenleri içeren bir Karışık Tamsayılı .doğrusal Programlama (Mixed-Integer Linear Programming, MILP) formülasyonu geliştirilmiştir. RSP'nin seçim lojistiği bir uygulaması olarak, çok dönemli seyahat eden politikacı problem tanıtılmaktadır. Problem analitik model ve kapsamlı bir senaryo analizine adapte edilerek verimli bir şekilde çözülmeye çalışılmıştır. Ticari çözücüler, RSP'nin küçük boyutlu örneklerini makul bir zamanda neredeyse optimal çözme yeteneğine sahiptir. Büyük ebattaki örneklerin üstesinden gelmek için, birinci aşamada şehir seçimiyle ilgilenirken, ikinci aşamada rota üretimine odaklanan iki aşamalı bir metasezgisel önerilmiştir. İkincisi, seçilen şehirler arasında en uygun rotayı inşa etmek için bir tamsayılı programlama modeli kullanılmıştır. Önerilen metasezgisel, RSP'yi temel olarak kampanya günlerinin sayısı kadar alt probleme ayrıştırır. Ayrıca bu çalışmada, RSP için granül ve eğriltilmiş değişken komşuluk tabu araması (Granular Skewed Variable Neighborhood Tabu Search, GSVNTS) olarak adlandırılan yeni bir hibrit metasezgisel algoritma sunuyoruz. Bu metasezgisel Eğritilmiş Değişken Komşuluk Arama algoritmasına gömülü bir Granül Tabu Araması'ndan oluşur. Önerilen yöntem, Türkiye'nin 81 ili ve 12 ilçesi dahil olmak üzere gerçek seyahat mesafeleri içeren örnek problemler üzerinde deneysel olarak test edilmiştir. Elde edilen deneysel sonuçlar, GSVNTS'nin az miktarda CPU zamanında optimal veya optimale yakın çözümlerin üretilebileceğini göstermektedir. Sunduğumuz matematiksel model, bu modelin çözümü için geliştirdiğimiz iki farklı metasezgisel ve bu metasezgiseli başlangıç çözümü olarak kullanan çözüm yöntemi GSVNTS sayesinde kampanya planlamacılarına stratejik karar vermelerinde yardımcı olunabilir.