Methods for the solution of a-priori travelling salesman problems

Siwate Rojanasoonthon, Rafael G. Moras, Milton L. Smith

Research output: Contribution to conferencePaper

Abstract

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.

Original languageEnglish
Pages1124-1131
Number of pages8
StatePublished - 1995
EventProceedings of the 1995 4th Industrial Engineering Research Conference - Nashville, TN, USA
Duration: May 24 1995May 25 1995

Conference

ConferenceProceedings of the 1995 4th Industrial Engineering Research Conference
CityNashville, TN, USA
Period05/24/9505/25/95

Fingerprint Dive into the research topics of 'Methods for the solution of a-priori travelling salesman problems'. Together they form a unique fingerprint.

  • Cite this

    Rojanasoonthon, S., Moras, R. G., & Smith, M. L. (1995). Methods for the solution of a-priori travelling salesman problems. 1124-1131. Paper presented at Proceedings of the 1995 4th Industrial Engineering Research Conference, Nashville, TN, USA, .