# A bicriterion traveling salesman problem

 Title: A bicriterion traveling salesman problem Author: Perng, Chyuan Abstract: A 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 . URI: http : / /hdl .handle .net /2346 /10674 Date: 1989-12

## Citation

A bicriterion traveling salesman problem. Doctoral dissertation, Texas Tech University. Available electronically from .

## Files in this item

Files Size Format View

There are no files associated with this item.