Methods for the solution of a-priori travelling salesman problems

A probabilistic traveling salesman problem (PTSP) is a variation of the traveling salesman problem where each customer has a given probability of requiring a visit. In this paper, the probabilities are allowed to be different from one customer to another (nonhomogeneous customers). An a-priori tour approach to PTSP; i.e., finding the optimal basic sequence, is adopted in this research. A basic sequence is a tour through all the customers such that any subset of customers will be visited in the same order that they appeared. The optimal basic sequence is the one with the minimum expected tour length. The objective of this paper is to develop a heuristic method for finding a good, if not optimal, basic sequence. Heuristics for generating a basic sequence were developed, evaluated, and compared. The main result of this research is an inserting heuristic which produces a good basic sequence with a relatively small computational effort.