Multidimensional assignment and scheduling with application to a tourism convention scheduling problem

The dissertation makes four major contributions: (1) An applied problem has been formulated, solved, and implemented along with computational tests. (2) An in-depth literature review has been done for the multidimensional assignment problem, with special results derived for one, and a summary of others. (3) A solvable case of the NP-hard three-dimensional planar assignment problem has been solved with a polynomial-time solution, (4) A new multiple traveling salesman problem has been introduced, and a heuristic developed and analyzed for a class of random problems.

The source problem is a tourism industry convention scheduling problem in which interviews among buyers and sellers are to be scheduled on a one-to-one basis during available time periods. Preference lists provided by both sellers and buyers are to be used to get mutual preference coefficients for optimization. A secondary goal is overall distance minimization for buyers moving between meetings. The dissertation contains an exposition of several different types of model formulations of higher dimensional assignment problems and related problems which appear in the literature. The focus is on the three-dimensional planar assignment problem, which is the basic model of the tourism convention application. The general problem is shown to be NP-hard in computational complexity.

The primary tourism convention problem is shown to belong to a polynomial bounded special class of the three-dimensional planar assignment problem. A two phase optimization solution is presented which consists of a two-dimensional capacitated transportation problem and a succession of two-dimensional classical assignment problems. In the first phase, optimal interviews overall are found for buyers and sellers, and in the second phase, nonconflicting time schedules are made for those optimal meetings. An application of the "marriage theorem" is used to derive the nonconflicting schedules.

A new multiple traveling salesman problem is defined which is a simultaneous, overlapping, nonconflicting problem. It appears in consideration of the secondary objective of the tourism problem, and is referred to as the "musical chairs traveling salesman problem" (MCTSP). An heuristic method of solution is presented which is a succession of distance minimizing two-dimensional classical assignment problems, after a judicious starting assignment is found by the first one. When the secondary objective is included in the tourism convention problem, the second phase of the three-dimensional planar assignment solution is modified to include the MCTSP heuristic.

A probabilistic analysis is done for the general MCTSP heuristic, using for weights independent random variables from a gamma g(1/n,β) distribution, where n is the number of time periods, salesmen, and cities (assumed equal for the analysis). The ratio of the expected objective function value of the heuristic solution to that of a randomly chosen solution is shown to be less than (1 + ln(n-1))/(n-1).

The solution method is computer implemented using four mutual preference objective coefficients with data from a recent tourism convention. A logarithmic cost is found to give the largest percentages of high preferences to both buyers and sellers. Computational tests are reported for problems of varying size using random independent preferences and random competitive preferences. The algorithm demonstrates the ability to resolve the conflicts and give almost as good solutions for data with strong competition and similar preferences as for random preferences, as indicated by ranks of preferences for resulting assignments. The average distance traveled when the MCTSP heuristic is not used in Phase II is greater than when it is used by a factor of 2.5 or more in all random problems, based on a sample grid supplied for the problems. With the number of time periods held constant, and numbers of buyers and sellers proportional, the CPU time is almost linear with problem size as depicted by the number of sellers.

Several potentially fruitful research areas are presented with some conjectures.