The roaming salesman problem and its application to election logistics

Abstract

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.

Campaign planning is one of the important decisions to make while dealing with determining routes, schedule of the activities, and accommodation planning. The campaign planner is required to plan the schedule of the visits to the customers, to satisfy time constraints, and to organize activities at its best with a proper decision on the scheduling and routing. In this study, we investigate a new problem the goal of which is to determine daily tours for a traveling salesman (referred to as the campaigner) who collects rewards from various cities during a campaign period. We call this new problem the roaming salesman problem (RSP) motivated by various real-world applications including election logistics, touristic trip planning, and marketing campaigns. RSP can be characterized as a combination of the traditional periodic TSP and the prize-collecting TSP with static edge costs and time-dependent vertex rewards. RSP seeks a closed or open tour for each day of a campaign period with the objective of maximizing the net benefit which is defined as the sum of all collected rewards minus the traveling costs. The campaigner is not required to visit all cities, and the daily tours do not have to start and end at the same city. Moreover, he/she can stay overnight in any city to start the tour of the next day. In particular, each city is associated with a base reward and a fixed activity duration. In addition, he/she cannot stay outside the campaign center for more than a given number of consecutive days and the total length of the activities and travel times between cities on the same day cannot exceed a certain maximum tour duration. We develop a MILP formulation for this problem in which we adopt existing routing constraints and introduce an entirely new class of constraints and binary variables. As an application of RSP in election logistics, we introduce the multi-period traveling politician problem (MPTPP). The problem is tackled efficiently by adapting analytical model and an extensive scenario analysis. Commercial solvers are capable of solving small-size instances of the RSP to near optimality in a reasonable time. To tackle large-size instances we propose a two-phase matheuristic where the first phase deals with the city selection while the second phase focuses on the route generation. The latter capitalizes on an integer program to construct an optimal route among selected cities. The proposed matheuristic decomposes the RSP basically into as many subproblems as the number of campaign days. We also introduce a new hybrid metaheuristic algorithm for the RSP, called granular skewed variable neighborhood tabu search (GSVNTS). It consists of a Granular Tabu Search which is embedded in a Skewed Variable Neighborhood Search algorithm. The suggested method is experimentally tested on the real-life instances including 81 cities and 12 towns in Turkey with actual travel distances. The computational results show that GSVNTS can generate optimal or near-optimal solutions in a small amount of CPU time. Using effective analytical models, the two-phase matheuristic, and GSVNTS, we show that promising results can be obtained to hopefully assist campaign planners in their strategic decision making.