ISTANBUL KÜLTÜR UNIVERSITY
DEPARTMENT OF INDUSTRIAL ENGINEERING 

SEMINAR SERIES

"A Granular Skewed Variable Neighborhood Tabu Search for the Roaming Salesman Problem "
by
Masoud Shahmanzari

PhD Candidate 
Koç University – Dept. of Business Administration  
E-mail: Mshahmanzari14 @ku.edu.tr

Abstract: 

We present a Granular Skewed Variable Neighborhood Tabu Search (GSVNTS) for the Roaming Salesman Problem (RSP). RSP is a multi-period and selective version of the traveling salesman problem involving a set of cities with time-dependent rewards. It is defined over a fixed planning horizon referred to as the campaign period. Each city can be visited on any day for reward collection while a subset of cities can be visited multiple times, though with diminishing rewards after the first visit. The goal is to determine an optimal campaign schedule consisting of either open or closed daily tours that maximize the total net benefit while respecting the maximum tour duration and the necessity to return to the campaign base frequently. Here the term ‘net benefit’ implies the total rewards collected minus the total traveling costs incurred. RSP arises in several applications including touristic trip planning, planning of client visits by company representatives, and election logistics. A differentiating feature of the RSP is that there exist no fixed depots and daily tours do not have to start and end at the same city. 

We formulate RSP as a mixed integer linear programming problem in which we capture as many real-world aspects as possible. We also present a hybrid metaheuristic algorithm which can be classified as a Variable Neighborhood Search (VNS) with Tabu Search conditions. The initial feasible solution is constructed via a novel two-phase matheuristic approach which decomposes the original problem into as many subproblems as the number of days. Next, this initial solution is improved using the proposed local search procedure. The concept of granularity is incorporated into the developed algorithm to prevent non-promising moves and thereby reduce the computing time of the neighborhood search. On the other hand, the concept of skewedness modifies the basic VNS so as to explore deeper neighborhoods of the current solution by accepting nonimproving moves which lead to far enough neighboring solutions. We consider a set of 95 cities in Turkey and a campaign period of 40 days as our largest problem instance. Computational results on actual distance and travel time data show that the developed algorithm GSVNTS can find near-optimal solutions in reasonable CPU times.

All interested are cordially invited.  
Date    : October 10, 2018
Time   : 13:30 – 14:30
Room    : 4C-03-05