Scientific Program > Talks by Speaker > Shahmanzari Masoud

We introduce the Roaming Salesman Problem (RSP) as a multi-period variant of the Prize-Collecting Traveling Salesman Problem (PCTSP). On a directed graph with static arc costs and time-dependent node rewards, RSP finds the best closed or open tour for each day of a planning horizon. The objective is to maximize the net benefit defined as the sum of rewards collected from the visited cities minus the normalized traveling costs. The salesman is not required to visit all cities, which makes the problem selective. He can also visit the same city more than once. Moreover, he can stay overnight in any city and resume his tour there the next day. This means there is no unique central node as is the case in the PCTSP. Several applications ranging from the trip planning of marketing associates to the scheduling of wholesaler purchases can be modeled as such. In our study, RSP is adapted to seek the most impactful rally schedule for a politician during a 30-day campaign before elections. The problem involves 81 cities in Turkey each associated with a base reward. The reward collected from a visited city is linearly depreciated with the meeting date and the recency of the preceding meeting in that city. We propose a comprehensive MILP formulation which captures many real-world aspects of this election logistics problem. Different scenarios are analyzed that may arise during the rally planning. We also develop a greedy heuristic for constructing the initial solution, and implement it on our data sets.