{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,4]],"date-time":"2026-08-04T15:31:53Z","timestamp":1785857513097,"version":"3.56.0"},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2012,9,13]],"date-time":"2012-09-13T00:00:00Z","timestamp":1347494400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Prog. Comp."],"published-print":{"date-parts":[[2013,3]]},"DOI":"10.1007\/s12532-012-0047-y","type":"journal-article","created":{"date-parts":[[2012,9,12]],"date-time":"2012-09-12T11:57:05Z","timestamp":1347451025000},"page":"27-55","source":"Crossref","is-referenced-by-count":66,"title":["The time dependent traveling salesman problem: polyhedra and algorithm"],"prefix":"10.1007","volume":"5","author":[{"given":"Hern\u00e1n","family":"Abeledo","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ricardo","family":"Fukasawa","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Artur","family":"Pessoa","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Eduardo","family":"Uchoa","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2012,9,13]]},"reference":[{"key":"47_CR1","first-page":"645","volume":"3","author":"D Applegate","year":"1998","unstructured":"Applegate, D., Bixby, R., Chv\u00e1tal, V., Cook, W.: On the solution of traveling salesman problems. Documenta Mathematica. Extra Volume ICM 3, 645\u2013646 (1998)","journal-title":"Documenta Mathematica. Extra Volume ICM"},{"key":"47_CR2","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/j.disopt.2005.10.001","volume":"3","author":"E Balas","year":"2006","unstructured":"Balas, E., Carr, R., Fischetti, M., Simonetti, N.: New facets of the STS polytope generated from known facets of the ATS polytope. Discrete Optim. 3, 3\u201319 (2006)","journal-title":"Discrete Optim."},{"key":"47_CR3","unstructured":"Balas, E., Fischetti, M.: Polyhedral theory for the ATSP. In: Gutin, G., Punnen, A. (eds.) The Traveling Salesman Problem and Its Variations, pp. 117\u2013168. Kluwer, Dordrecht (2002)"},{"key":"47_CR4","doi-asserted-by":"crossref","unstructured":"Bigras, L.-Ph., Gamache, M., Savard, G.: The time-dependent traveling salesman problem and single machine scheduling problems with sequence dependent setup time. Discrete Optim. 5, 685\u2013699 (2008)","DOI":"10.1016\/j.disopt.2008.04.001"},{"key":"47_CR5","doi-asserted-by":"crossref","first-page":"393","DOI":"10.1287\/opre.2.4.393","volume":"2","author":"GB Dantzig","year":"1954","unstructured":"Dantzig, G.B., Fulkerson, D.R., Johnson, S.M.: Solution of a large-scale traveling salesman problem. Oper. Res. 2, 393\u2013410 (1954)","journal-title":"Oper. Res."},{"key":"47_CR6","doi-asserted-by":"crossref","first-page":"1055","DOI":"10.1287\/opre.41.6.1055","volume":"41","author":"M Fischetti","year":"1993","unstructured":"Fischetti, M., Laporte, G., Martello, S.: The delivery man problem and cumulative matroids. Oper. Res. 41, 1055\u20131064 (1993)","journal-title":"Oper. Res."},{"key":"47_CR7","first-page":"101","volume":"28","author":"K Fox","year":"1980","unstructured":"Fox, K., Gavish, B., Graves, S.: An n-constraint formulation of the (time dependent) traveling salesman problem. Oper. Res. 28, 101\u2013102 (1980)","journal-title":"Oper. Res."},{"key":"47_CR8","doi-asserted-by":"crossref","first-page":"1073","DOI":"10.2140\/pjm.1957.7.1073","volume":"7","author":"D Gale","year":"1957","unstructured":"Gale, D.: A theorem of flows in networks. Pacif. J. Math. 7, 1073\u20131082 (1957)","journal-title":"Pacif. J. Math."},{"key":"47_CR9","doi-asserted-by":"crossref","unstructured":"Godinho, M.T., Gouveia, L., Pesneau, P.: Natural and extended formulations for the time- dependent travelling salesman problem, CIO Report8\/2010, Lisbon (2010)","DOI":"10.1016\/j.endm.2010.05.133"},{"key":"47_CR10","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1016\/0377-2217(93)E0238-S","volume":"83","author":"L Gouveia","year":"1995","unstructured":"Gouveia, L., Voss, S.: A classification of formulations for the (time-dependent) traveling salesman problem. Eur. J. Oper. Res. 83, 69\u201382 (1995)","journal-title":"Eur. J. Oper. Res."},{"key":"47_CR11","doi-asserted-by":"crossref","unstructured":"Gouveia, L., Simonetti, L., Uchoa, E.: Modeling hop-constrained and diameter-constrained minimum spanning tree problems as Steiner tree problems over layered graphs. Math. Program. Online first (2009)","DOI":"10.1007\/s10107-009-0297-2"},{"key":"47_CR12","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1007\/BF01582117","volume":"16","author":"M Groetschel","year":"1979","unstructured":"Groetschel, M., Padberg, M.: On the symmetric traveling salesman problem II: lifing theorems and facets. Math. Program. 16, 281\u2013302 (1979)","journal-title":"Math. Program."},{"key":"47_CR13","unstructured":"Groetschel, M., Padberg, M.: Polyhedral theory. In: Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G. (eds.) The Traveling Salesman Problem, pp. 251\u2013305. Wiley, New York (1985)"},{"key":"47_CR14","doi-asserted-by":"crossref","first-page":"26","DOI":"10.1112\/jlms\/s1-10.37.26","volume":"10","author":"P Hall","year":"1935","unstructured":"Hall, P.: On representatives of subsets. J. Lond. Math. Soc. 10, 26\u201330 (1935)","journal-title":"J. Lond. Math. Soc."},{"key":"47_CR15","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1090\/psapm\/010\/0114759","volume":"10","author":"A Hoffman","year":"1960","unstructured":"Hoffman, A.: Some recent applications of the theory of linear inequalities to extremal combinatorial analysis. Proc. Symp. Appl. Math. 10, 113\u2013128 (1960)","journal-title":"Proc. Symp. Appl. Math."},{"key":"47_CR16","doi-asserted-by":"crossref","first-page":"391","DOI":"10.1287\/ijoc.1040.0117","volume":"18","author":"S Irnich","year":"2006","unstructured":"Irnich, S., Villeneuve, D.: The shortest path problem with resource constraints and $$k$$ -cycle elimination for $$k\\ge 3$$ . INFORMS J. Comput. 18, 391\u2013406 (2006)","journal-title":"INFORMS J. Comput."},{"key":"47_CR17","doi-asserted-by":"crossref","first-page":"753","DOI":"10.1002\/net.3230200605","volume":"20","author":"A Lucena","year":"1990","unstructured":"Lucena, A.: Time-dependent traveling salesman problem\u2014the deliveryman case. Networks 20, 753\u2013763 (1990)","journal-title":"Networks"},{"key":"47_CR18","first-page":"3233","volume":"156","author":"I M\u00e9ndez-D\u00edaz","year":"2008","unstructured":"M\u00e9ndez-D\u00edaz, I., Zabala, P., Lucena, A.: A new formulation for the traveling deliveryman problem. Discrete Appl. Math. 156, 3233\u20133237 (2008)","journal-title":"Discrete Appl. Math."},{"key":"47_CR19","unstructured":"Melo, M., Subramanian, A.: Personal communication (2010)"},{"key":"47_CR20","doi-asserted-by":"crossref","first-page":"351","DOI":"10.1016\/j.endm.2010.05.045","volume":"36","author":"JJ Miranda Bront","year":"2010","unstructured":"Miranda Bront, J.J., M\u00e9ndez-D\u00edaz, I., Zabala, P.: An integer programming approach for the time dependent traveling saleman problem. Electron. Notes Discrete Math. 36, 351\u2013358 (2010)","journal-title":"Electron. Notes Discrete Math."},{"key":"47_CR21","unstructured":"Niskanen, S., Ostergard, P.R.J.: Cliquer users guide. Helsinki University of Technology. Communications Laboratory, Technical report 48 (2003)"},{"key":"47_CR22","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1007\/BF01580121","volume":"5","author":"M Padberg","year":"1973","unstructured":"Padberg, M.: On the facial structure of set packing polyhedra. Math. Program. 5, 199\u2013215 (1973)","journal-title":"Math. Program."},{"key":"47_CR23","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1287\/opre.26.1.86","volume":"26","author":"J Picard","year":"1978","unstructured":"Picard, J., Queyranne, M.: The time-dependent traveling salesman problem and its application to the tardiness problem in one-machine scheduling. Oper. Res. 26, 86\u2013110 (1978)","journal-title":"Oper. Res."},{"key":"47_CR24","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1007\/978-0-387-77778-8_14","volume-title":"The Vehicle Routing Problem: Latest Advances and New Challenges","author":"A Pessoa","year":"2008","unstructured":"Pessoa, A., Poggi de Arag\u00e3o, M.: Robust branch-cut-and-price algorithms for vehicle routing problems. In: Golden, B., Raghavan, S., Wasil, E. (eds.) The Vehicle Routing Problem: Latest Advances and New Challenges, pp. 297\u2013326. Springer, New York (2008)"},{"key":"47_CR25","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1002\/net.20330","volume":"54","author":"A Pessoa","year":"2009","unstructured":"Pessoa, A., Uchoa, E., Poggi de Arag\u00e3o, M.: A robust branch-cut-and-price algorithm for the heterogeneous fleet vehicle routing problem. Networks 54, 167\u2013177 (2009)","journal-title":"Networks"},{"key":"47_CR26","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1007\/s12532-010-0019-z","volume":"2","author":"A Pessoa","year":"2010","unstructured":"Pessoa, A., Uchoa, E., Freitas, R.: Exact algorithm over an arc-time indexed formulations for parallel machine scheduling problems. Math. Program. Comput. 2, 259\u2013290 (2010)","journal-title":"Math. Program. Comput."},{"key":"47_CR27","unstructured":"Ralphs, T.K., Lad\u00e1nyi, L.: COIN\/BCP User\u2019s Manual. http:\/\/www.coin-or.org\/Presentations\/bcp-man.pdf (2001)"},{"key":"47_CR28","volume-title":"Mathematical Programming","author":"S Vajda","year":"1961","unstructured":"Vajda, S.: Mathematical Programming. Addison-Wesley, New York (1961)"},{"key":"47_CR29","doi-asserted-by":"crossref","first-page":"797","DOI":"10.1002\/(SICI)1520-6750(199609)43:6<797::AID-NAV2>3.0.CO;2-#","volume":"43","author":"RJ Vander Wiel","year":"1996","unstructured":"Vander Wiel, R.J., Sahinidis, N.V.: An exact solution approach for the time-dependent traveling salesman problem. Naval Res. Logist. 43, 797\u2013820 (1996)","journal-title":"Naval Res. Logist."}],"container-title":["Mathematical Programming Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s12532-012-0047-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s12532-012-0047-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s12532-012-0047-y","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,1,28]],"date-time":"2022-01-28T19:37:41Z","timestamp":1643398661000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s12532-012-0047-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,9,13]]},"references-count":29,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2013,3]]}},"alternative-id":["47"],"URL":"https:\/\/doi.org\/10.1007\/s12532-012-0047-y","relation":{},"ISSN":["1867-2949","1867-2957"],"issn-type":[{"value":"1867-2949","type":"print"},{"value":"1867-2957","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,9,13]]}}}