Endüstri Mühendisliği Seminerler Serisi - Deniz Aksen

Title: The Traveling Politician Problem: An Application of the Roaming Salesman Problem to Election Logistics

Abstract: 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. The well-known traveling salesman problem (TSP) encapsulates the core of the RSP.  In fact, the RSP can be characterized as a combination of the traditional Periodic TSP and the Prize-Collecting TSP. On a graph 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 making the problem selective. Moreover, he can stay overnight in any city to start the tour of the next day. There is no fixed central node, i.e. no depot which means that tours do not have to start and end at the same city. As an application of this problem in election logistics, we introduce the Multi-Period Traveling Politician Problem. We consider 81 cities (provinces) in Turkey inclusive of the capital Ankara which constitutes the campaign center. Each city is associated with a base reward and a fixed meeting duration. The party leader 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 mixed integer linear programming formulation for the RSP in which we capture as many real-world aspects as possible. In our computational experiments we test arc-based and node-based subtour elimination constraints for this problem. We evaluate several scenarios which may likely occur during the campaign and try different solver configurations in an effort to improve the solution speed and accuracy.

Bio: Deniz Aksen is Associate Professor of Associate Professor 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. Academic Website:  http://home.ku.edu.tr/~daksen/resume.html