×

zbMATH — the first resource for mathematics

A threshold accepting heuristic with intense local search for the solution of special instances of the traveling salesman problem. (English) Zbl 1102.90025
Summary: In real life scheduling, variations of the standard traveling salesman problem are very often encountered. The aim of this work is to present a new heuristic method for solving three such special instances with a common approach. The proposed algorithm uses a variant of the threshold accepting method, enhanced with intense local search, while the candidate solutions are produced through an insertion heuristic scheme. The main characteristic of the algorithm is that it does not require modifications and parameter tuning in order to cope with the three different problems. Computational results on a variety of real life and artificial problems are presented at the end of this work and prove the efficiency and the ascendancy of the proposed method over other algorithms found in the literature.

MSC:
90B35 Deterministic scheduling theory in operations research
90C27 Combinatorial optimization
90C59 Approximation methods and heuristics in mathematical programming
Software:
TSPTW; JOBSHOP; TSPLIB
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Aarts, E.; Korst, J., Simulated annealing and Boltzmann machines, (1989), John Wiley Chichester, UK · Zbl 0674.90059
[2] Abdel-Hamid, A.; Ascheuer, N.; Grötschel, M., Order picking in an automatic warehouse: solving the on-line asymmetric TSP’s, Mathematical methods of operations research, 49, 501-505, (1999) · Zbl 1009.90037
[3] Althofer, I.; Koschinick, K.U., On the convergence of ‘threshold accepting’, Applied mathematical optimization, 24, 183-195, (1991) · Zbl 0816.90113
[4] Andrews, M.; Bender, M.A.; Zhang, L., New algorithms for the disk scheduling problem, (), 550-559
[5] Applegate, D.; Cook, W., A computational study of the job-shop scheduling problem, ORSA journal on computing, 3, 149-156, (1991) · Zbl 0755.90039
[6] Ascheuer, N.; Fischetti, M.; Grötschel, M., Solving the asymmetric travelling salesman problem with time windows by branch-and-cut, Mathematical programming A, 90, 475-506, (2001) · Zbl 1039.90056
[7] Ascheuer, N.; Escudero, L.; Grötchel, M.; Stoer, M., On identifying in polynomial time violated subtour elimination and precedence forcing constrains for the sequential ordering problem, (), 19-28
[8] Ascheuer, N.; Escudero, L.; Grötchel, M.; Stoer, M., A cutting plane approach to the sequential ordering problem (with applications to the job scheduling problem in manufacturing), SIAM journal on optimization, 3, 25-42, (1993) · Zbl 0794.90039
[9] N. Ascheuer, Hamiltonian path problems in the on-line optimization of flexible manufacturing systems, Ph.D. thesis Technical University Berlin, 1995. · Zbl 0859.90080
[10] N. Ascheuer, M. Junger, G. Reinelt, A branch and cut algorithm for the asymmetric traveling salesman problem with precedence constrains, Report No. 98.323, Angewandte Mathematic und Informatic Universidat Zu Koln, 1998. · Zbl 1017.90095
[11] Balas, E.; Toth, P., Branch and bound methods, (), 361-402 · Zbl 0568.90068
[12] Boland, N.L.; Clarke, L.W.; Nemhauser, G.L., The asymmetric traveling salesman problem with replenishment arcs, European journal of operational research, 123, 408-427, (2000) · Zbl 1054.90058
[13] Buriol, L.; Franca, P.; Moscato, P., A new memetic algorithm for the asymmetric traveling salesman problem, Journal of heuristics, 10, 483-506, (2004) · Zbl 1062.90052
[14] Carpaneto, G.; Dell’Amico, M.; Toth, P., Exact solution of large scale, asymmetric traveling salesman problems, ACM transactions on mathematical software, 21, 4, 394-409, (1995) · Zbl 0887.65058
[15] Chan, D.; Mercier, D., IC insertion: an application of the traveling salesman problem, International journal of production research, 27, 1837-1841, (1989)
[16] Chipman, J.S.; Winker, P., Optimal industrial classification by threshold accepting, Control cybernet, 24, 477-494, (1995) · Zbl 0852.90043
[17] Choi, I.C.; Kim, S.I.; Kim, H.-S., A genetic algorithm with a mixed region search for the asymmetric traveling salesman problem, Computers and operations research, 30, 773-786, (2003) · Zbl 1026.90073
[18] Cirasella, J.; Johnson, D.S.; McGeoch, L.A.; Zhang, W., The asymmetric traveling salesman problem: algorithms, instance generators, and tests, (), 32-59 · Zbl 1010.68848
[19] Dorigo, M.; Gambardella, L.M., Ant colony system: A cooperative learning approach to the traveling salesman problem, IEEE transactions on evolutionary computation, 1, 1, 53-66, (1997)
[20] Dueck, G.; Scheuer, T., Threshold accepting. A general purpose optimization algorithm appearing superior to simulated annealing, Journal of computational physics, 90, 161-175, (1990) · Zbl 0707.65039
[21] Dueck, G., New optimization heuristics: the great deluge algorithm and the record-to-record travel, Journal of computational physics, 104, 86-92, (1993) · Zbl 0773.65042
[22] Dueck, G.; Winker, P., New concepts and algorithms for portfolio choice, Applied stochastic models data anal, 8, 159-178, (1992)
[23] Escudero, L.F., An inexact algorithm for the sequential ordering problem, European journal of operational research, 37, 232-253, (1988) · Zbl 0653.90036
[24] Fagerholta, K.; Christiansen, M., A travelling salesman problem with allocation, time window and precedence constraints—an application to ship scheduling, International transactions in operations research, 7, 231-244, (2000)
[25] Fink, A.; Voi, S., Solving the continuous flow-shop scheduling problem by metaheuristics, European journal of operational research, 151, 400-414, (2003) · Zbl 1052.90030
[26] Fischetti, M.; Toth, P., A polyhedral approach to the asymmetric traveling salesman problem, Management science, 43, 11, 1520-1536, (1997) · Zbl 0902.90159
[27] Focacci, F.; Lodi, A.; Milano, M., A hybrid exact algorithm for the TSPTW, INFORMS journal on computing, 14, 4, 403-417, (2002) · Zbl 1238.90054
[28] Freisleben, B.; Merz, P., A genetic local search algorithm for solving symmetric and asymmetric traveling salesman problems, (), 616-621
[29] Gambardella, L.M.; Dorigo, M., Solving symmetric and asymmetric TSPs by ant colonies, (), 622-627
[30] Gambardella, L.C.; Dorigo, M., An ant colony system hybridized with a new local search for the sequential ordering problem, INFORMS journal on computing, 12, 237-255, (2000) · Zbl 1040.90570
[31] Garey, M.R.; Johnson, D.S., Computers and intractability: A guide to the theory of NP-completeness, (1979), W.H. Freeman New York · Zbl 0411.68039
[32] Glover, F.; Gutin, G.; Yeo, A.; Zverovic, A., Theory and methodology. construction heuristics for the asymmetric TSP, European journal of operational research, 129, 555-568, (2001) · Zbl 1125.90402
[33] Held, M.; Karp, R.M., The traveling salesman problem and minimal spanning trees, Operations research, 18, 1138-1162, (1970) · Zbl 0226.90047
[34] Held, M.; Wolfe, P.; Crowder, H.P., Validation of sub-gradient optimization, Mathematical programming, 6, 62-88, (1974) · Zbl 0284.90057
[35] Helmberg, C., (), 242-258
[36] Helsgaun, K., An effective implementation of the lin – kernighan traveling salesman heuristic, European journal of operations research, 12, 106-130, (2000) · Zbl 0969.90073
[37] Johnson, D.S.; Gutin, G.; McGeoch, L.A.; Yeo, A.; Zang, W.; Zverovitch, A., Experimental analysis of the ATSP, () · Zbl 1113.90355
[38] Johnson, D.S.; McGeoch, L.A., The traveling salesman problem: A case study in local optimization, (), 215-310 · Zbl 0947.90612
[39] Kanellakis, P.C.; Papadimitriou, C.H., Local search for the asymmetric traveling salesman problem, Operations research, 28, 1086-1099, (1980) · Zbl 0447.90082
[40] Karp, R.M., Reducibility among combinatorial problems, (), 85-103 · Zbl 0366.68041
[41] Karp, R.M., A patching algorithm for the non-symmetric traveling salesman problem, SIAM journal on computing, 8, 561-573, (1979) · Zbl 0427.90064
[42] Karp, R.M.; Steele, J.M., Probabilistic analysis of heuristics, (), 181-205 · Zbl 0582.90100
[43] Kirkpatrick, V.; Gelatt, C.D.; Vecchi, M.P., Optimization by simulated annealing, Science, 220, 671-680, (1983) · Zbl 1225.90162
[44] Laarhoven, A.; Aarts, E.H.L., Simulated annealing: theory and applications, (1987), Kluwer Academic Publishers Dordrecht · Zbl 0643.65028
[45] ()
[46] ()
[47] Lee, D.S.; Vassiliadis, V.S.; Park, J.M., A novel threshold meta-heuristic for the job shop scheduling problem, Computers & operations research, 31, 2199-2213, (2004) · Zbl 1071.68016
[48] Lin, C.K.Y.; Haley, K.B.; Sparks, C., A comparative study for both standard and adaptive versions of threshold accepting and simulated annealing algorithms in three scheduling problems, European journal of operations research, 83, 330-346, (1995) · Zbl 0904.90140
[49] Lin, S.; Kernighan, B.W., An effective heuristic algorithm for the traveling salesman problem, Operations research, 21, 972-989, (1973) · Zbl 0256.90038
[50] Little, J.; Murty, K.; Sweeney, D.; Karel, C., An algorithm for the traveling salesman problem, Operations research, 11, 972-989, (1963) · Zbl 0161.39305
[51] Lysgaard, J., Cluster based branching for the asymmetric traveling salesman problem, European journal of operational research, 119, 314-325, (1999) · Zbl 0933.90064
[52] Mak, V.; Boland, N., Heuristic approaches to the asymmetric traveling salesman problem with replenishment arcs, International transactions in operations research, 7, 431-447, (2000)
[53] Martin, O.; Otto, S.W.; Felten, E.W., Large-step Markov chains for the traveling salesman problem, Complex systems, 5, 299-336, (1991) · Zbl 0736.90063
[54] Miller, D.L.; Pekny, J.F., Exact solution of large asymmetric traveling salesman problems, Science, 251, 754-761, (1991)
[55] Moon, C.; Kim, J.; Choi, G.; Seo, Y., An efficient genetic algorithm for the traveling salesman problem with precedence constraints, European journal of operational research, 140, 606-617, (2002) · Zbl 0998.90066
[56] Nissen, V.; Paul, H., A modification of threshold accepting and its application to the quadratic assignment problem, OR spectrum, 17, 205-210, (1995) · Zbl 0842.90092
[57] Paletta, G., The period traveling salesman problem: A new heuristic algorithm, Computers and operations research, 29, 1343-1352, (2002) · Zbl 1038.90067
[58] Papadimitriou, C.H., Computational complexity, (1994), Addiso-Wesley Publishing Company Reading, MA · Zbl 0557.68033
[59] Reinelt, G., The traveling salesman: computational solutions for TSP applications, Lecture notes in computer science, vol. 810, (1994), Springer-Verlag Berlin
[60] Reinelt, G., TSPLIB—A traveling salesman library, ORSA journal on computing, 3, 376-384, (1991) · Zbl 0775.90293
[61] Savelsberg, M.W.P., Local search for routing problems with time windows, Annals of operational research, 4, 285-305, (1985)
[62] Schneider, J., The time-dependent traveling salesman problem, Physica A, 314, 151-155, (2002) · Zbl 1001.90054
[63] Stützle, T.; Dorigo, M., ACO algorithms for the traveling salesman problem, evolutionary algorithms in engineering and computer science: recent advances in genetic algorithms, evolution strategies, evolutionary programming, genetic programming and industrial applications, (1999), John Wiley & Sons New York
[64] Tang, L.; Liu, J.; Rong, A.; Yang, Z., A multiple traveling salesman problem model for hot rolling scheduling in Shanghai baoshan iron & steel complex, European journal of operational research, 124, 267-282, (2000) · Zbl 1025.90523
[65] C.D. Tarantilis, C.T. Kiranoudis, V.S. Vassiliadis, Efficient solutions of the general heterogeneous fleet vehicle routing problem via novel threshold acceptance metaheuristics. Paper presented at the AIChE Annual Meeting, Los Angeles, USA, 2000.
[66] Tarantilis, C.D.; Kiranoudis, C.T., A List based threshold accepting method for job shop scheduling problems, International journal of production economics, 77, 159-171, (2002) · Zbl 1013.90020
[67] M. Timlin, Precedence constrained routing, Master’s thesis, Department of Combinatorics and Optimization, University of Waterloo, 1989.
[68] Timlin Fiala, M.T.; Pulleyblank, W.R., Precedence constrained routing and helicopter scheduling: heuristic design, Interfaces, 22, 3, 100-111, (1992)
[69] Tsitsiklis, J., Special cases of traveling salesman and repairman problems with time windows, Networks, 22, 263-282, (1992) · Zbl 0819.90124
[70] T. White, Routing with Swarm Intelligence, SCE Technical Report SCE-97 15, Systems and Computer Engineering, Carleton University, September 1997.
[71] P.Winker, The Tuning of the Threshold Accepting Heuristic for Traveling Salesman Problems, Paper presented at OR 94, Berlin, 1994.
[72] Winker, P.; Fang, K.T., Application of threshold accepting to the evaluation of the discrepancy of a set of points, SIAM journal on numerical analysis, 34, 5, 2028-2042, (1997) · Zbl 0888.65021
[73] W. Zhang, Truncated branch-and-bound: A case study on the asymmetric tsp, in: Working Note of AAAI 1993 Spring Symposium: AI and NP-Hard Problems, Stanford, CA, 1993, pp. 160-166.
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.