×

zbMATH — the first resource for mathematics

A general VNS heuristic for the traveling salesman problem with time windows. (English) Zbl 1241.90130
Summary: This paper presents a General Variable Neighborhood Search (GVNS) heuristic for the Traveling Salesman Problem with Time Windows (TSPTW). The heuristic is composed by both constructive and optimization stages. In the first stage, the heuristic constructs a feasible solution using VNS, and in the optimization stage the heuristic improves the feasible solution with a General VNS heuristic. Both constructive and optimization stages take advantage of elimination tests, partial neighbor evaluation and neighborhood partitioning techniques. Experimental results show that this approach is efficient, reducing significantly the computation time and improving some best known results from the literature.

MSC:
90C27 Combinatorial optimization
90C59 Approximation methods and heuristics in mathematical programming
Software:
PERL; TSPTW; TTTPLOTS
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Aiex, R.M.; Resende, M.G.C.; Ribeiro, C.C., Tttplots: a perl program to create time-to-target plots, Optimization letters, 1, 4, 355-366, (2006) · Zbl 1220.90102
[2] Calvo, R.W., A new heuristic for the traveling salesman problem with time windows, Transportation science, 34, 1, 113-124, (2000) · Zbl 1041.90524
[3] Carlton, W.B.; Barnes, J.W., Solving the travelling salesman problem with time windows using tabu search, IEE transactions, 28, 617-629, (1996)
[4] Dumas, Y.; Desrosiers, J.; Gelinas, E.; Solomon, M., An optimal algorithm for the travelling salesman problem with time windows, Operations research, 43, 2, 367-371, (1995) · Zbl 0837.90036
[5] 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
[6] Gendreau, M.; Hertz, A.; Laporte, G., New insertion and postoptimization procedures for the travelling salesman problem, Operations research, 40, 1086-1094, (1992) · Zbl 0767.90087
[7] Gendreau, M.; Hertz, A.; Laporte, G.; Stan, M., A generalized insertion heuristic for the traveling salesman problem with time windows, Operations research, 46, 3, 330-335, (1998) · Zbl 0987.90070
[8] Hansen, P.; Brimberg, J.; Urošević, D.; Mladenović, N., Primal-dual variable neighborhood search for the simple plant-location problem, INFORMS journal on computing, 19, 4, 552-564, (2007) · Zbl 1241.90072
[9] Hansen, P.; Mladenović, N.; Pérez, J.A.M., Variable neighbourhood search: methods and applications, 4or, 6, 4, 319-360, (2008) · Zbl 1179.90332
[10] Johnson, D.S.; McGeoch, L.A., The traveling salesman problem: a case study in local optimization, (), 215-310 · Zbl 0947.90612
[11] Kirkpatrick, S.; Gelatt, C.D.; Vecchi, M.P., Optimization by simulated annealing, Science, 220, 671-680, (1983) · Zbl 1225.90162
[12] Langevin, A.; Desrochers, M.; Desrosiers, J.; Gélinas, S.; Soumis, F., A two-commodity flow formulation for the traveling salesman and the makespan problems with time windows, Networks, 23, 7, 631-640, (1993) · Zbl 0792.90084
[13] Mladenović, N.; Hansen, P., Variable neighborhood search, Computations & operations research, 24, 11, 1097-1100, (1997) · Zbl 0889.90119
[14] Ohlmann, J.W.; Thomas, B.W., A compressed-annealing heuristic for the traveling salesman problem with time windows, INFORMS journal on computing, 19, 1, 80-90, (2007) · Zbl 1241.90116
[15] Pesant, G.; Gendreau, M.; Potvin, J.-Y.; Rousseau, J.-M., An exact constraint logic programming algorithm for the travelling salesman problem with time windows, Transportation science, 32, 12-29, (1998) · Zbl 0987.90086
[16] Ribeiro, C.C.; Aloise, D.; Noronha, T.F.; Rocha, C.; Urrutia, S., An efficient implementation of a VNS/ILS heuristic for a real-life car sequencing problem, European journal of operational research, 191, 3, 596-611, (2008) · Zbl 1156.90377
[17] Salvesbergh, M.W., Local search in routing problems with time windows, Annals of operations research, 4, 285-305, (1985)
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.