The asymmetric m-travelling salesman problem: A duality based branch-and- bound algorithm. (English) Zbl 0603.90132
An algorithm of Held and Karp for the ordinary TSP is extended to the following situation: Given n cities and m salesmen, find m tours, all starting at the same given city, so that no city is visited twice and total distance travelled is minimum.
The algorithm employs a Lagrangean relaxation, a subgradient procedure to solve the dual and a greedy algorithm to obtain minimal m-trees. For up to \(n=50\) cities, solutions can be routinely obtained; computational experience with \(n=100\) is documented, too. Alternatively, the problem can be transformed into an equivalent ordinary TSP with \(n+m-1\) cities. Whether the approach given here is more efficient than solving the transformed problem remains to be an open question.
The algorithm employs a Lagrangean relaxation, a subgradient procedure to solve the dual and a greedy algorithm to obtain minimal m-trees. For up to \(n=50\) cities, solutions can be routinely obtained; computational experience with \(n=100\) is documented, too. Alternatively, the problem can be transformed into an equivalent ordinary TSP with \(n+m-1\) cities. Whether the approach given here is more efficient than solving the transformed problem remains to be an open question.
Reviewer: K.Mosler
MSC:
| 90C35 | Programming involving graphs or networks |
| 90C10 | Integer programming |
| 65K05 | Numerical mathematical programming methods |
| 90C27 | Combinatorial optimization |
Keywords:
multiple travelling salesman problem; minimum spanning trees; Lagrangean relaxation; subgradient procedure; greedy algorithm; computational experienceReferences:
| [1] | Ali, A. I., Two node-routing problems, ((1980), Operations Research Department, Southern Methodist University: Operations Research Department, Southern Methodist University Dallas, TX), Unpublished dissertation |
| [2] | Ali, A.; Kennington, J., The \(m\)-travelling salesmen problem, (Technical Report OR 80016 (July 1980), Department of Operations Research, Southern Methodist University: Department of Operations Research, Southern Methodist University Dallas, TX) |
| [3] | Bazaraa, M. S.; Goode, J. J., The travelling salesmen problem: A duality approach, Math. Programmings, 13, 221-237 (1977) · Zbl 0377.90092 |
| [4] | Bazaraa, M. S.; Shetty, C. M., Nonlinear Programming: Theory and Algorithms (1979), Wiley: Wiley New York · Zbl 0476.90035 |
| [5] | Bellmore, M.; Hong, S., Transformation of multi-salesmen problem to the standard travelling salesmen problem, J. Assoc. Comput. Mach., 21, 3, 500-504 (1974) · Zbl 0283.90036 |
| [6] | Edmonds, J., Matroids and the greedy algorithm, Math. Programming, 1, 127-136 (1971) · Zbl 0253.90027 |
| [7] | Gavish, B.; Srikanth, K., Optimal and sub-optimal solution methods for the multiple travelling salesman problem, (Presented at the Joint National TIMS/ORSA Meeting. Presented at the Joint National TIMS/ORSA Meeting, Washington DC (1980)) |
| [8] | Geoffrion, A. M., Duality in nonlinear programming: A simplified applications-oriented development, SIAM Review, 13, 1, 1-37 (1971) · Zbl 0232.90049 |
| [9] | Geoffrion, A. M.; Marsten, R. E., Integer programming algorithms: A framework and state-of-the-art survey, Management Sci., 18, 9, 465-491 (1972) · Zbl 0238.90043 |
| [10] | Geoffrion, A. M., Lagrangean relaxation for integer programming, Math. Programming Study, 2, 92-114 (1979) · Zbl 0395.90056 |
| [11] | Glover, F.; Klingman, D., Finding minimum spanning trees with a fixed number of links at a node, (Colloq. Math. Soc. Janos Bolyai, 12 (1974), Progress in Operations Research: Progress in Operations Research Eger, Hungary (North-Holland, Amsterdam), 425-439 · Zbl 0395.90077 |
| [12] | Held, M.; Karp, R. M., The travelling salesman problem and minimum spanning trees, Oper. Res., 18, 1138-1162 (1970) · Zbl 0226.90047 |
| [13] | Held, M.; Karp, R. M., The travelling salesman problem and minimum spanning trees: Part II, Math. Programming, 1, 6-25 (1971) · Zbl 0232.90038 |
| [14] | Held, M.; Wolfe, P.; Crowder, H., Validation of subgradient optimization, Math. Programming, 6, 225-248 (1974) · Zbl 0284.90057 |
| [15] | Helgason, R. V., A Lagrangean relaxation approach to the generalized fixed charge multicommodity network flow problem, ((1979), Department of Operations Research, Southern Methodist University: Department of Operations Research, Southern Methodist University Dallas, TX), Unpublished dissertation |
| [16] | Kennington, J.; Helgason, R., Algorithms for Network Programming (1980), Wiley: Wiley New York · Zbl 0452.90054 |
| [17] | Marsten, R.; Morin, T., Branch-and-bound methods with strogner than optimal bounds, (Presented at Joint National Meeting of TIMS/ORSA. Presented at Joint National Meeting of TIMS/ORSA, Washington, DC (May 1980)) |
| [18] | Miller, C. E.; Tucker, A. W.; Zemlin, R. A., Integer programming formulation of travelling salesman problems, J. Assoc. Comput. Mach., 7, 326-329 (1960) · Zbl 0100.15101 |
| [19] | Svetska, J. A.; Huckfeldt, V. E., Computational experience with an \(m\)-salesman travelling salesman algorithm, Management Sci., 19, 790-799 (1973) · Zbl 0255.90033 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
