×

zbMATH — the first resource for mathematics

A variable iterated greedy algorithm for the traveling salesman problem with time windows. (English) Zbl 1354.90110
Summary: This paper presents a variable iterated greedy algorithm for solving the traveling salesman problem with time windows (TSPTW) to identify a tour minimizing the total travel cost or the makespan, separately. The TSPTW has several practical applications in both production scheduling and logistic operations. The proposed algorithm basically relies on a greedy algorithm generating an increasing number of neighboring solutions through the use of the idea of neighborhood change in variable neighborhood search (VNS) algorithms. In other words, neighboring solutions are generated by destructing a solution component and re-constructing the solution again with variable destruction sizes. In addition, the proposed algorithm is hybridized with a VNS algorithm employing backward and forward \(1_{Opt}\) local searches to further enhance the solution quality. The performance of the proposed algorithm was tested on several benchmark suites from the literature. Experimental results confirm that the proposed algorithm is either competitive to or even better than the best performing algorithms from the literature. Ultimately, new best-known solutions are obtained for 38 out of 125 problem instances of the recently proposed benchmark suite, whereas 15 out of 31 problem instances are also further improved for the makespan criterion.

MSC:
90C27 Combinatorial optimization
90C59 Approximation methods and heuristics in mathematical programming
Software:
TSPTW
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Savelsbergh, M. W.P., Local search in routing problems with time windows, Ann. Oper. Res., 4, 1, 285-305, (1985)
[2] Christofides, N.; Mingozzi, A.; Toth, P., State-space relaxation procedures for the computation of bounds to routing problems, Networks, 11, 2, 145-164, (1981) · Zbl 0458.90071
[3] Baker, E. K., An exact algorithm for the time-constrained traveling salesman problem, Oper. Res., 31, 5, 938-945, (1983) · Zbl 0549.90072
[4] Langevin, A.; Desrochers, M.; Desrosiers, J.; Gelinas, S.; Soumis, F., A two-commodity flow formulation for the traveling salesman and makespan problems with time windows, Networks, 23, 7, 631-640, (1993) · Zbl 0792.90084
[5] Dumas, Y.; Desrosiers, J.; Gelinas, E.; Solomon, M. M., An optimal algorithm for the traveling salesman problem with time windows, Oper. Res., 43, 2, 367-371, (1995) · Zbl 0837.90036
[6] Ascheuer, N.; Fischetti, M.; Grotschel, M., Solving asymmetric travelling salesman problem with time windows by branch-and-cut, Math. Program., 90, 475-506, (2001) · Zbl 1039.90056
[7] Balas, E.; Simonetti, N., Linear time dynamic-programming algorithms for new classes of restricted TSPs: a computational study, INFORMS J. Comput., 13, 1, 56-75, (2001) · Zbl 1238.90126
[8] Pesant, G.; Gendreau, M.; Potvin, J.-Y.; Rousseau, J.-M., An exact constraint logic programming algorithm for the traveling salesman problem with time windows, Transp. Sci., 32, 12-29, (1998) · Zbl 0987.90086
[9] Focacci, F.; Lodi, A.; Milano, M., A hybrid exact algorithm for the TSPTW, INFORMS J. Comput., 14, 403-417, (2002) · Zbl 1238.90054
[10] Carlton, W. B.; Barnes, J. W., Solving the traveling-salesman problem with time windows using tabu search, IIE Trans., 28, 617-629, (1996)
[11] Gendreau, M.; Hertz, A.; Laporte, G.; Stan, M., A generalized insertion heuristic for the traveling salesman problem with time windows, Oper. Res., 46, 330-335, (1998) · Zbl 0987.90070
[12] Gendreau, M.; Hertz, A.; Laporte, G., New insertion and post optimization procedures for the traveling salesman problem, Oper. Res., 40, 1086-1094, (1992) · Zbl 0767.90087
[13] Calvo, R. W., A new heuristic for the traveling salesman problem with time windows, Transp. Sci., 34, 1, 113-124, (2000) · Zbl 1041.90524
[14] Ohlmann, J. W.; Thomas, B. W., A compressed-annealing heuristic for the traveling salesman problem with time windows, INFORMS J. Comput., 19, 1, 80-90, (2007) · Zbl 1241.90116
[15] Cheng, C.-B.; Mao, C.-P., A modified ant colony system for solving the travelling salesman problem with time windows, Math. Comput. Model., 46, 1225-1235, (2007) · Zbl 1173.90562
[16] Ibanez, M. L.; Blum, C., Beam-ACO for the travelling salesman problem with time windows, Comput. Oper. Res., 37, 1570-1583, (2010) · Zbl 1190.90165
[17] Da Silva, R. F.; Urrutia, S., A general VNS heuristic for the traveling salesman problem with time windows, Discr. Optim., 7, 203-211, (2010) · Zbl 1241.90130
[18] Ruiz, R.; Stützle, T., A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem, Eur. J. Oper. Res., 177, 3, 2033-2049, (2007) · Zbl 1110.90042
[19] Framinan, J. M.; Leisten, R., Total tardiness minimization in permutation flow shops: a simple approach based on a variable greedy algorithm, Int. J. Prod. Res., 46, 22, 6479-6498, (2008) · Zbl 1154.90361
[20] Gerardo Minella, G.; Ruiz, R.; Ciavotta, M., Restarted iterated Pareto greedy algorithm for multi-objective flowshop scheduling problems, Comput. Oper. Res., 38, 1521-1533, (2011)
[21] Fatih Tasgetiren, M.; Pan, Q.-K.; Suganthan, P. N.; Chen Angela, H.-L., A discrete artificial bee colony algorithm for the total flowtime minimization in permutation flow shops, Inf. Sci., 181, 3459-3475, (2011)
[22] Qinma Kanga, Q.; Heb, H.; Song, H., Task assignment in heterogeneous computing systems using an effective iterated greedy algorithm, J. Syst. Softw., 84, 985-992, (2011)
[23] Ribas, I.; Ramon Companys, R.; Tort-Martorell, X., An iterated greedy algorithm for the flowshop scheduling problem with blocking, Omega, 39, 293-301, (2011)
[24] Fatih Tasgetiren, M.; Pan, Q.-K.; Liang, Y.-C., A discrete differential evolution algorithm for the single machine total weighted tardiness problem with sequence dependent setup times, Comput. Oper. Res., 36, 1900-1915, (2009) · Zbl 1179.90155
[25] Pan, Q.-K.; Fatih Tasgetiren, M.; Liang, Y.-C., A discrete differential evolution algorithm for the permutation flowshop scheduling problem, Comput. Ind. Eng., 55, 795-816, (2008)
[26] Ruiz, R.; Stützle, T., An iterated greedy heuristic for the sequence dependent setup times flowshop problem with makespan and weighted tardiness objectives, Eur. J. Oper. Res., 187, 1143-1159, (2008) · Zbl 1137.90514
[27] Fanjul-Peyro, L.; Ruiz, R., Iterated greedy local search methods for unrelated parallel machine scheduling, Eur. J. Oper. Res., 207, 55-69, (2010) · Zbl 1205.90121
[28] Lozano, M.; Molina, D.; Garcia-Martinez, C., Iterated greedy for the maximum diversity problem, Eur. J. Oper. Res., 214, 31-38, (2011) · Zbl 1218.90175
[29] Kuo-Ching Ying, K.-C.; Lin, S.-W.; Huang, C.-Y., Sequencing single-machine tardiness problems with sequence dependent setup times using an iterated greedy heuristic, Expert Syst. Appl., 36, 7087-7092, (2009)
[30] Ying, K.-C.; Cheng, H.-M., Dynamic parallel machine scheduling with sequence-dependent setup times using an iterated greedy heuristic, Expert Syst. Appl., 37, 2848-2852, (2010)
[31] Kahraman, C.; Engin, O.; Kaya, I.; Ozturk, R. E., Multiprocessor task scheduling in multistage hybrid flow-shops: a parallel greedy algorithm approach, Appl. Soft Comput., 10, 1293-1300, (2010)
[32] Bouamama, S.; Blum, C.; Boukerram, A., A population-based iterated greedy algorithm for the minimum weight vertex cover problem, Appl. Soft Comput. J., (2012)
[33] Mladenovic, N.; Hansen, P., Variable neighborhood search, Comput. Oper. Res., 24, 1097-1100, (1997) · Zbl 0889.90119
[34] Nawaz, M.; Enscore, E. E.; Ham, I. A., Heuristic algorithm for the m-machine, n-node flow shop sequencing problem, Omega, 11, 1, 91-95, (1983)
[35] Coello, Coello Carlos A., Theoretical and numerical constraint-handling techniques used with evolutionary algorithms: a survey of the state of the art, Comput. Methods Appl. Mech. Eng., 191, 11-12, 1245-1287, (2002) · Zbl 1026.74056
[36] Deb, K., An efficient constraint handling method for genetic algorithms, Comput. Methods Appl. Mech. Eng., 186, 311-338, (2000) · Zbl 1028.90533
[37] Coit, D. W.; Smith, A. E., Penalty guided genetic search for reliability design optimization, Comput. Ind. Eng., 30, 4, 895-904, (1996)
[38] Gen, Mitsuo; Cheng, R., Genetic algorithms and engineering optimization, (2000), John Wiley and Sons
[39] Potvin, J.-Y.; Bengio, S., The vehicle routing problem with time windows part II: genetic search, INFORMS J. Comput., 8, 165-172, (1996) · Zbl 0866.90058
[40] Solomon, M. M., Algorithms for the vehicle routing and scheduling problems with time windows constraints, Oper. Res., 35, 2, 254-265, (1987) · Zbl 0625.90047
[41] Xingjuan, Cai; Shujing, Fan; Ying, Tan, Light responsive curve selection for photosynthesis operator of APOA, Int. J. Bio-Inspired Comput., 4, 6, 373-379, (2012)
[42] Liping, Xie; Jianchao, Zeng; Formato, Richard A., Selection strategies for gravitational constant G in artificial physics optimisation based on analysis of convergence properties, Int. J. Bio-Inspired Comput., 4, 6, 380-391, (2012)
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.