A bicriterion traveling salesman problem



Journal Title

Journal ISSN

Volume Title


Texas Tech University


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.