Dolaşım satıcısı problemi ve seçim lojistiğine uygulanması

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.