An improved assignment lower bound for the euclidean traveling salesman problem |
| |
Authors: | William R Stewart |
| |
Institution: | School of Business Administration, College of William and Mary, Williamsburg, VA 23185, USA |
| |
Abstract: | A simple transformation of the distance matrix for the Euclidean traveling salesman problem is presented that produces a tighter lower bound on the length of the optimal tour than has previously been attainable using the assignment relaxation. The improved lower bound is obtained by exploiting geometric properties of the problem to produce fewer and larger subtours on the first solution of the assignment problem. This research should improve the performance of assignment based exact procedures and may lead to improved heuristics for the traveling salesman problem. |
| |
Keywords: | traveling salesman flow algorithms integer programming lower bounds |
本文献已被 ScienceDirect 等数据库收录! |