zbMATH — the first resource for mathematics

A time bucket formulation for the traveling salesman problem with time windows. (English) Zbl 06599260
Summary: The traveling salesman problem with time windows (TSPTW) is the problem of finding a minimum-cost path visiting a set of cities exactly once, where each city must be visited within a given time window. We present an extended formulation for the problem based on partitioning the time windows into subwindows that we call buckets. We present cutting planes for this formulation that are computationally more effective than the ones known in the literature because they exploit the division of the time windows into buckets. To obtain a good partition of the time windows, we propose an iterative linear programming (LP)-based procedure that may produce buckets of different sizes. The LP relaxation of this formulation yields strong lower bounds for the TSPTW and provides a good starting point for our branch-and-cut algorithm. We also present encouraging computational results on hard test problems from the literature, namely, asymmetric instances arising from a practical scheduling application, as well as randomly generated symmetric instances. In particular, we solve a number of previously unsolved benchmark instances.

90C27 Combinatorial optimization
Full Text: DOI
[1] ABACUS A branch-and-cut system. . http://www.informatik.uni-koeln.de/abacus/ · Zbl 0911.90282
[2] Albiach J., Sanchis J. M., Soler D.An asymmetric TSP with time windows and with time-dependent travel times and costs: An exact solution through a graph transformation. Eur. J. Oper. Res. (2008) 189(3):789-802CrossRef · Zbl 1146.90363
[3] Appelgren L. H.A column generation algorithm for a ship scheduling problem. Transportation Sci. (1969) 3(1):53-68Link
[4] Ascheuer N.Hamiltonian path problems in the on-line optimization of flexible manufacturing systems. (1995) . Ph.D. thesis, Technische Universität Berlin, Berlin · Zbl 0859.90080
[5] Ascheuer N., Fischetti M., Grötschel M.A polyhedral study of the asymmetric travelling salesman problem with time windows. Networks (2000) 36(2):69-79CrossRef · Zbl 0972.90085
[6] Ascheuer N., Fischetti M., Grötschel M.Solving the asymmetric travelling salesman problem with time windows by branch-and-cut. Math. Programming Ser. A (2001) 90(3):475-506 · Zbl 1039.90056
[7] Baker E. K.An exact algorithm for the time-constrained traveling salesman problem. Oper. Res. (1983) 31(5):938-945Link · Zbl 0549.90072
[8] Balas E., Simonetti N.Linear time dynamic programming algorithms for new classes of restricted TSPs: A computational study. INFORMS J. Comput. (2001) 13(1):56-75Link · Zbl 1238.90126
[9] Balas E., Fischetti M., Pulleyblank W. R.The precedence-constrained asymmetric traveling salesman polytope. Math. Programming Ser. A (1995) 68(3):241-265 · Zbl 0835.90109
[10] Christofides N., Mingozzi A., Toth P.State-space relaxation procedures for the computation of bounds to routing problems. Networks (1981) 11(2):145-164CrossRef · Zbl 0458.90071
[11] Cordeau J. F., Desaulniers G., Desrosiers J., Solomon M. M., Soumis F., Toth P., Vigo D.VRP with time windows. The Vehicle Routing Problem (2002) (SIAM, Philadelphia) 157-194CrossRef · Zbl 1076.90543
[12] Desrosiers J., Dumas Y., Solomon M. M., Soumis F., Ball M. O., Magnanti T. L., Monma C. L., Nemhauser G. L.Time constrained routing and scheduling. Network Routing (1995) (Elsevier, Amsterdam) 35-139CrossRef
[13] Dumas Y., Desrosiers J., Gelinas E., Solomon M. M.An optimal algorithm for the travelling salesman problem with time windows. Oper. Res. (1995) 43(2):367-371Link · Zbl 0837.90036
[14] Focacci F., Lodi A., Milano M.A hybrid exact algorithm for the TSPTW. INFORMS J. Comput. (2002) 14(4):403-417Link · Zbl 1238.90054
[15] Langevin A., Desrochers M., Desrosiers J., Soumis F.A two-commodity flow formulation for the traveling salesman and makespan problem with time windows. Networks (1993) 23(7):631-640CrossRef · Zbl 0792.90084
[16] Levin A.Scheduling and fleet routing models for transportation systems. Transportation Sci. (1971) 5(3):232-255Link
[17] Mingozzi A., Bianco L., Ricciardelli S.Dynamic programming strategies for the traveling salesman problem with time windows and precedence constraints. Oper. Res. (1997) 45(3):365-377Link · Zbl 0893.90167
[18] 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 Sci. (1998) 32(1):12-29Link · Zbl 0987.90086
[19] Rochat Y., Taillard E. D.Probabilistic diversification and intensification in local search for vehicle routing. J. Heuristics (1995) 1(1):147-167CrossRef · Zbl 0857.90032
[20] Savelsbergh M. W. P.Local search in routing problems with time windows. Ann. Oper. Res. (1985) 4(1):285-305CrossRef
[21] Solomon M. M.Algorithms for the vehicle routing and scheduling problem with time window constraints. Oper. Res. (1987) 35(2):254-265Link · Zbl 0625.90047
[22] Taillard E. D., Badeau P., Gendreau M., Guertin F., Potvin J.-Y.A new neighborhood structure for the vehicle routing problems with time windows. (1995) . Technical Report CRT-95-66, Centre de Recherche sur les Transports, Université de Montréal, Montréal · Zbl 0886.90070
[23] Tramontani A.Enhanced mixed integer programming techniques and routing problems. (2009) . Ph.D. thesis, DEIS, Università di Bologna, Bologna, Italy · Zbl 1230.90042
[24] Wang X., Regan A. C.Local truckload pickup and delivery with hard time window constraints. Transportation Res. Part B (2002) 36(2):97-112CrossRef
[25] Wang X., Regan A. C.On the convergence of a new time window discretization method for the traveling salesman problem with time window constraints. Comput. Indust. Engrg. (2009) 56(1):161-164CrossRef
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.