×

The selective travelling salesman problem. (English) Zbl 0695.90098

This paper deals with exact solutions for the Selective Traveling Salesman Problem - a TSP with profit at the nodes - by branch-and bound. The contribution is in the form of a new upper bound calculation as well as two node partitioning rules. The upper bound is a knapsack problem while the partitioning rules are (1) a single descendant node corresponding to the inclusion of each vertex that does not yield a dominated solution and (2) a two-descendant rule that has some vertices for which a decision is delayed until later on. Numerical results indicate that the first rule is generally best and that the upper bound calculation permits the resolution of problems with a few tens of nodes up to about 10 depending on the network and cost structure.
Reviewer: A.Girard

MSC:

90C35 Programming involving graphs or networks
90C10 Integer programming
65K05 Numerical mathematical programming methods
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Carpaneto, G.; Martello, S.; Toth, P., Algorithms and codes for the assignment problem, (Simeone, B.; Toth, P.; Gallo, G.; Maffioli, F.; Pallottino, S., Fortran Codes for Network Optimization. Fortran Codes for Network Optimization, Annals of Operations Research, 13 (1988), Baltzer: Baltzer Basel)
[2] Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Complete Problems (1979), Freeman: Freeman New York · Zbl 0411.68039
[3] Golden, B. L.; Levy, L.; Vohra, R., Some heuristics for the generalized traveling salesman problem, (Working Paper MS/S 85-036 (1985), College of Business and Management, University of Maryland)
[4] Golden, B. L.; Levy, L.; Vohra, R., The orienteering problem, Naval Res. Logist., 34, 307-318 (1987) · Zbl 0647.90099
[5] Golden, B. L.; Wang, Q.; Liu, L., A multi-faceted heuristic for the orienteering problem, Naval Res. Logist., 35, 359-366 (1988) · Zbl 0649.90089
[6] Hayes, M.; Norman, J. M., Dynamic programming in orienteering: route choice and siting of controls, J. Oper. Res. Soc., 35, 791-796 (1984)
[7] Laporte, G., Generalized subtour elimination constraints and connectivity constraints, J. Oper. Res. Soc., 37, 509-514 (1986) · Zbl 0594.90064
[8] Martello, S.; Toth, P., An upper bound for the zero-one knapsack problem and a branch and bound algorithm, European J. Oper. Res., 1, 169-175 (1977) · Zbl 0374.90050
[9] Martello, S.; Toth, P., Algorithms for knapsack problems, (Martello, S.; Laporte, G.; Minoux, M.; Ribeiro, C., Surveys in Combinatorial Optimization. Surveys in Combinatorial Optimization, Annals of Discrete Mathematics, 31 (1987), North-Holland: North-Holland Amsterdam), 213-257
[10] Rosenkrantz, D. J.; Stearns, R. E.; Lewis, P. M., An analysis of several heuristics for the traveling salesman problem, SIAM J. Comput., 6, 563-581 (1977) · Zbl 0364.90104
[11] Tsiligirides, T., Heuristic methods applied to orienteering, J. Oper. Res. Soc., 35, 797-809 (1984)
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.