Show simple item record

dc.creatorPerng, Chyuan
dc.date.available2011-02-18T19:24:44Z
dc.date.issued1989-12
dc.identifier.urihttp://hdl.handle.net/2346/10674en_US
dc.description.abstractA Bicriterion Traveling Salesman Problem (BCTSP) is introduced. The problems considered include both a cost matrix and a time matrix, and the objective is to minimize both cost and time. A set of undominated solutions will be found by solving the BCTSP. Several exact solution approaches: Best-k-Optimal algorithm (KB^3), Double-Bound Branch-and-Bound (DB^3) algorithm and Double-Optimal-Bound Branch-and-Bound (DOB^3) algorithm are introduced to solve the two-objective traveling salesman problem exactly. The DB^3 algorithm is based on Little's branch-and-bound algorithm (Little et al. 1963). Little's algorithm is one of the efficient exact solution approaches for the single objective TSP. In this study, we are dealing with the bicriterion TSP in which there are two objectives (bounds) to be considered. Therefore, Little's algorithm has to be modified to carry two bounds in every branch and node. The KB^3 algorithm is extended from solving the standard TSP. Instead of stopping when the optimal solution has been found, this algorithm finds an ordered list of the best k optimal solutions to the cost problem with the associated time values and the best k optimal solutions to the time problem with the associated cost values. The decision maker then can make his decision and choose the best alternative from these two sets of solutions. The exact solution methods can solve the BCTSP exactly and efficiently for problem size n < 14. In the case of n > 14, it appeared that all exact methods become prohibitive because of excessive computer memory and computational time. Therefore, a statistical Monte Carlo simulation which uses the maximum saving 3-opt. tour improvement method to solve the BCTSP approximately has been developed. A performance evaluation scheme for the approximate solutions is discussed. The approximate solution method assumes the possible sequences follow the bivariate normal distribution, and uses the first-order statistics and autocorrelation to determine termination rules which produce results close to optimal. This algorithm is very efficient compared to the exact solution methods.
dc.format.mimetypeapplication/pdf
dc.language.isoeng
dc.publisherTexas Tech Universityen_US
dc.subjectTraveling-salesman problemen_US
dc.titleA bicriterion traveling salesman problem
dc.typeDissertation
thesis.degree.namePh.D.
thesis.degree.levelDoctoral
thesis.degree.disciplineIndustrial and Systems Engineering
thesis.degree.grantorTexas Tech University
thesis.degree.departmentIndustrial and Systems Engineering
thesis.degree.departmentIndustrial Engineering
dc.degree.departmentIndustrial and Systems Engineeringen_US
dc.rights.availabilityUnrestricted.


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record