The Traveling Salesman Problem with Job-times (TSPJ)

摘要

This paper explores a problem related to both the Traveling Salesman Problem and Scheduling Problem where a traveler moves through n locations (nodes), visits all locations and each location exactly once to assign and initiate one of n jobs, and then returns to the first location. After initiation of a job, the traveler moves to the next location immediately and the job continues autonomously. This is representative of many practical scenarios including autonomous robotics, equipment maintenance, highly automated manufacturing, agricultural harvesting, and disaster recovery. The goal is to minimize the time of completion of the last job, i.e. makespan. Although the makespan objective typically is used in scheduling problems, the transportation times can be significant relative to the processing time, and this changes the optimization considerations. We refer to this problem as the Traveling Salesman Problem with Job-times (TSPJ) and present a mathematical formulation and local search improvement heuristics for it. Computational experience in solving the TSPJ using both commercial solvers and heuristics is reported. (C) 2021 Elsevier Ltd. All rights reserved.