A New Multiperiod Multiple Traveling Salesman Problem with Heuristic and Application to a Scheduling Problem

Abstract

ABSTRACT A new multiperiod variation of the M ‐traveling salesman problem is introduced. The problem arises in efficient scheduling of optimal interviews among tour brokers and vendors at conventions of the tourism and travel industry. In classical traveling salesman problem vocabulary, a salesman is a tour broker at the convention and a city is a vendor's booth. In this problem, more than one salesman may be required to visit a city, but at most one salesman per time period can visit each city. The heuristic solution method presented is polynomial and is guaranteed to produce a nonconflicting set of salesmen's tours. The results of an implementation of the method for a recent convention are also reported.