Premium
A New Multiperiod Multiple Traveling Salesman Problem with Heuristic and Application to a Scheduling Problem
Author(s) -
Gilbert Kenneth C.,
Hofstra Ruth B.
Publication year - 1992
Publication title -
decision sciences
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.238
H-Index - 108
eISSN - 1540-5915
pISSN - 0011-7315
DOI - 10.1111/j.1540-5915.1992.tb00387.x
Subject(s) - travelling salesman problem , traveling purchaser problem , 2 opt , lin–kernighan heuristic , bottleneck traveling salesman problem , mathematical optimization , computer science , scheduling (production processes) , heuristic , job shop scheduling , operations research , mathematics , schedule , operating system
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.