Formulation and Model Solution of the Roaming Salesman Problem: Application to Election Logistics
College of Administrative Sciences and Economics, Koç University
In this paper we investigate a new problem the goal of which is to determine daily routes for a traveling salesman 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. In fact, the 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. The 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 salesman is not required to visit all cities, and his daily tours do not have to start and end at the same city. Moreover, he 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 meeting duration. The salesman cannot stay outside the campaign center for more than a given number of consecutive days. In addition, the total length of the talks and travel times between cities on the same day cannot exceed a certain maximum tour duration. We develop a new mixed integer linear programming formulation for the RSP. The proposed formulation is tested on a real case study involving 81 cities (provinces) in Turkey inclusive of the capital Ankara which constitutes the campaign center. Promising results are achieved.
This study is a joint work with Masoud Shahmanzari from Koç University and Said Salhi from Kent Business School, University of Kent, Canterbury.
Deniz Aksen is Associate Professor of of Management Information Systems (MIS) at Koç University College of Administrative Sciences and Economics (CASE). He holds his BS (Jun 1994) and MS degrees (Sep 1996) from Boğaziçi University Department of Industrial Engineering in İstanbul, Turkey. He received his PhD in MIS from Krannert School of Management at Purdue University, USA (Jan 2003). The same year he joined Koç University.
Deniz Aksen teaches in the areas of MIS, e-commerce, Internet security, business spreadsheet applications, and mathamatical modeling in Excel. From 2011 through 2017 he also supervised KU student teams participating at the Google Online Marketing Challenge. His research interests include distribution and collection logistics, vehicle routing, facility location and interdiction problems, heuristic optimization, and political apportionment systems. His papers have been published in the European Journal of Operational Research, Computers & Operations Research, International Journal of Production Economics, and Transportation Research Part C, among others.
Friday, April 20, 2018 at 4.00 pm in IE03