{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,31]],"date-time":"2025-10-31T07:25:12Z","timestamp":1761895512995},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642321467"},{"type":"electronic","value":"9783642321474"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-32147-4_35","type":"book-chapter","created":{"date-parts":[[2012,7,5]],"date-time":"2012-07-05T11:54:50Z","timestamp":1341489290000},"page":"392-403","source":"Crossref","is-referenced-by-count":11,"title":["Hardness Results for the Probabilistic Traveling Salesman Problem with Deadlines"],"prefix":"10.1007","author":[{"given":"Dennis","family":"Weyland","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Roberto","family":"Montemanni","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Luca Maria","family":"Gambardella","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"5","key":"35_CR1","doi-asserted-by":"publisher","first-page":"938","DOI":"10.1287\/opre.31.5.938","volume":"31","author":"E.K. Baker","year":"1983","unstructured":"Baker, E.K.: An exact algorithm for the time-constrained traveling salesman problem. Operations Research\u00a031(5), 938\u2013945 (1983)","journal-title":"Operations Research"},{"issue":"11","key":"35_CR2","doi-asserted-by":"publisher","first-page":"1939","DOI":"10.1016\/j.cor.2009.12.005","volume":"37","author":"P. Balaprakash","year":"2010","unstructured":"Balaprakash, P., Birattari, M., St\u00fctzle, T., Dorigo, M.: Estimation-based metaheuristics for the probabilistic traveling salesman problem. Computers & Operations Research\u00a037(11), 1939\u20131951 (2010)","journal-title":"Computers & Operations Research"},{"issue":"4","key":"35_CR3","doi-asserted-by":"publisher","first-page":"644","DOI":"10.1287\/ijoc.1080.0276","volume":"20","author":"M. Birattari","year":"2008","unstructured":"Birattari, M., Balaprakash, P., St\u00fctzle, T., Dorigo, M.: Estimation-based local search for stochastic combinatorial optimization using delta evaluations: A case study on the probabilistic traveling salesman problem. INFORMS Journal on Computing\u00a020(4), 644\u2013658 (2008)","journal-title":"INFORMS Journal on Computing"},{"key":"35_CR4","unstructured":"Birge, J.R., Louveaux, F.: Introduction to stochastic programming. Springer (1997)"},{"issue":"9","key":"35_CR5","doi-asserted-by":"publisher","first-page":"2703","DOI":"10.1016\/j.cor.2005.02.024","volume":"33","author":"A.M. Campbell","year":"2006","unstructured":"Campbell, A.M.: Aggregation for the probabilistic traveling salesman problem. Computers and Operations Research\u00a033(9), 2703\u20132724 (2006)","journal-title":"Computers and Operations Research"},{"issue":"1","key":"35_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1287\/trsc.1070.0203","volume":"42","author":"A.M. Campbell","year":"2008","unstructured":"Campbell, A.M., Thomas, B.W.: Probabilistic traveling salesman problem with deadlines. Transportation Science\u00a042(1), 1\u201321 (2008)","journal-title":"Transportation Science"},{"issue":"4","key":"35_CR7","doi-asserted-by":"publisher","first-page":"1231","DOI":"10.1016\/j.cor.2008.01.006","volume":"36","author":"A.M. Campbell","year":"2009","unstructured":"Campbell, A.M., Thomas, B.W.: Runtime reduction techniques for the probabilistic traveling salesman problem with deadlines. Computers and Operations Research\u00a036(4), 1231\u20131248 (2009)","journal-title":"Computers and Operations Research"},{"issue":"1","key":"35_CR8","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1007\/s10479-005-5729-7","volume":"134","author":"K. Chepuri","year":"2005","unstructured":"Chepuri, K., Homem-de-Mello, T.: Solving the vehicle routing problem with stochastic demands using the cross-entropy method. Annals of Operations Research\u00a0134(1), 153\u2013181 (2005)","journal-title":"Annals of Operations Research"},{"key":"35_CR9","unstructured":"Desrochers, M., Lenstra, J.K., Savelsbergh, M.W.P., Soumis, F.: Vehicle routing with time windows: optimization and approximation. In: Golden, B.L., Assad, A.A. (eds.) Vehicle Routing: Methods and Studies, pp. 65\u201384. Elsevier Science Publishers (1988)"},{"issue":"8","key":"35_CR10","doi-asserted-by":"publisher","first-page":"1005","DOI":"10.1287\/mnsc.34.8.1005","volume":"34","author":"J. Desrosiers","year":"1988","unstructured":"Desrosiers, J., Sauv\u00e9, M., Soumis, F.: Lagrangian relaxation methods for solving the minimum fleet size multiple traveling salesman problem with time windows. Management Science\u00a034(8), 1005\u20131022 (1988)","journal-title":"Management Science"},{"issue":"3","key":"35_CR11","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1007\/s10107-005-0597-0","volume":"106","author":"M. Dyer","year":"2006","unstructured":"Dyer, M., Stougie, L.: Computational complexity of stochastic programming problems. Mathematical Programming\u00a0106(3), 423\u2013432 (2006)","journal-title":"Mathematical Programming"},{"issue":"2","key":"35_CR12","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1287\/trsc.29.2.143","volume":"29","author":"M. Gendreau","year":"1995","unstructured":"Gendreau, M., Laporte, G., Seguin, R.: An exact algorithm for the vehicle routing problem with stochastic demands and customers. Transportation Science\u00a029(2), 143 (1995)","journal-title":"Transportation Science"},{"key":"35_CR13","doi-asserted-by":"crossref","unstructured":"Gendreau, M., Laporte, G., Seguin, R.: A tabu search heuristic for the vehicle routing problem with stochastic demands and customers. Operations Research, 469\u2013477 (1996)","DOI":"10.1287\/opre.44.3.469"},{"issue":"1","key":"35_CR14","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/0377-2217(95)00050-X","volume":"88","author":"M. Gendreau","year":"1996","unstructured":"Gendreau, M., Laporte, G., Seguin, R.: Stochastic vehicle routing. European Journal of Operational Research\u00a088(1), 3\u201312 (1996)","journal-title":"European Journal of Operational Research"},{"key":"35_CR15","unstructured":"Jaillet, P.: Probabilistic traveling salesman problems. PhD thesis, M. I. T., Dept. of Civil Engineering (1985)"},{"key":"35_CR16","doi-asserted-by":"crossref","unstructured":"Johnson, D.S., McGeoch, L.A.: The traveling salesman problem: A case study in local optimization. Local Search in Combinatorial Optimization, 215\u2013310 (1997)","DOI":"10.2307\/j.ctv346t9c.13"},{"issue":"2","key":"35_CR17","doi-asserted-by":"publisher","first-page":"266","DOI":"10.1287\/opre.35.2.266","volume":"35","author":"A.W.J. Kolen","year":"1987","unstructured":"Kolen, A.W.J., Rinnooy Kan, A.H.G., Trienekens, H.: Vehicle Routing with Time Windows. Operations Research\u00a035(2), 266 (1987)","journal-title":"Operations Research"},{"key":"35_CR18","doi-asserted-by":"crossref","unstructured":"Laporte, G., Louveaux, F.V., Van Hamme, L.: An integer L-shaped algorithm for the capacitated vehicle routing problem with stochastic demands. Operations Research, 415\u2013423 (2002)","DOI":"10.1287\/opre.50.3.415.7751"},{"key":"35_CR19","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1137\/S0097539702411915","volume":"34","author":"B. Morris","year":"2004","unstructured":"Morris, B., Sinclair, A.: Random walks on truncated cubes and sampling 0-1 knapsack solutions. SIAM Journal on Computing\u00a034, 195 (2004)","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"35_CR20","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1002\/nav.3800220110","volume":"22","author":"H.M. Salkin","year":"1975","unstructured":"Salkin, H.M., De Kluyver, C.A.: The knapsack problem: a survey. Naval Research Logistics Quarterly\u00a022(1), 127\u2013144 (1975)","journal-title":"Naval Research Logistics Quarterly"},{"issue":"1","key":"35_CR21","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1007\/BF02022044","volume":"4","author":"M.W.P. Savelsbergh","year":"1985","unstructured":"Savelsbergh, M.W.P.: Local search in routing problems with time windows. Annals of Operations Research\u00a04(1), 285\u2013305 (1985)","journal-title":"Annals of Operations Research"},{"issue":"2","key":"35_CR22","doi-asserted-by":"publisher","first-page":"254","DOI":"10.1287\/opre.35.2.254","volume":"35","author":"M.M. Solomon","year":"1987","unstructured":"Solomon, M.M.: Algorithms for the vehicle routing and scheduling problems with time window constraints. Operations Research\u00a035(2), 254\u2013265 (1987)","journal-title":"Operations Research"},{"key":"35_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"681","DOI":"10.1007\/978-3-642-04772-5_88","volume-title":"Computer Aided Systems Theory - EUROCAST 2009","author":"D. Weyland","year":"2009","unstructured":"Weyland, D., Bianchi, L., Gambardella, L.M.: New Approximation-Based Local Search Algorithms for the Probabilistic Traveling Salesman Problem. In: Moreno-D\u00edaz, R., Pichler, F., Quesada-Arencibia, A. (eds.) EUROCAST 2009. LNCS, vol.\u00a05717, pp. 681\u2013688. Springer, Heidelberg (2009)"},{"key":"35_CR24","doi-asserted-by":"crossref","unstructured":"Weyland, D., Montemanni, R., Gambardella, L.M.: Heuristics for the probabilistic traveling salesman problem with deadlines using monte carlo sampling (2011) (submitted for publication)","DOI":"10.1007\/978-3-642-32147-4_35"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Optimization"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-32147-4_35.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,1,20]],"date-time":"2022-01-20T06:44:10Z","timestamp":1642661050000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-32147-4_35"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642321467","9783642321474"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-32147-4_35","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}