NASA Logo

NTRS

NTRS - NASA Technical Reports Server

Back to Results
WHAMII - An enumeration and insertion procedure with binomial bounds for the stochastic time-constrained traveling salesman problemThis paper presents an algorithm (WHAMII) designed to solve the Artificial Intelligence Design Challenge at the 1987 AIAA Guidance, Navigation and Control Conference. The problem under consideration is a stochastic generalization of the traveling salesman problem in which travel costs can incur a penalty with a given probability. The variability in travel costs leads to a probability constraint with respect to violating the budget allocation. Given the small size of the problem (eleven cities), an approach is considered that combines partial tour enumeration with a heuristic city insertion procedure. For computational efficiency during both the enumeration and insertion procedures, precalculated binomial probabilities are used to determine an upper bound on the actual probability of violating the budget constraint for each tour. The actual probability is calculated for the final best tour, and additional insertions are attempted until the actual probability exceeds the bound.
Document ID
19870063179
Acquisition Source
Legacy CDMS
Document Type
Conference Paper
Authors
Dahl, Roy W.
(Maryland Univ. College Park, MD, United States)
Keating, Karen
(Maryland Univ. College Park, MD, United States)
Salamone, Daryl J.
(Distict Management Consultants Columbia, MD, United States)
Levy, Laurence
(Maryland, University College Park, United States)
Nag, Barindra
(Towson State University MD, United States)
Sanborn, Joan A.
(NASA Goddard Space Flight Center Greenbelt, MD, United States)
Date Acquired
August 13, 2013
Publication Date
January 1, 1987
Subject Category
Computer Programming And Software
Report/Patent Number
AIAA PAPER 87-2333
Accession Number
87A50453
Distribution Limits
Public
Copyright
Other

Available Downloads

There are no available downloads for this record.
No Preview Available