The Selective Traveling Salesman Problem with Regular Working Time Windows

摘要

Most literature on variations of traveling salesman problem (TSP) assumes that the worker is continuously available. However, this assumption may not be valid in some real applications due to the human's natural needs. In this work, we study a selective TSP with regular working time windows in which a set of jobs at dispersed locations requires a specific length of time for completion from the worker. In the whole working time horizon, the worker can only travel or process jobs during the working time windows and the rest of time is used for taking breaks. The objective is to maximize the sum of the job processing time. By conducting extensive experiments, we show that our devised tabu search is a good approach to solve this problem.