{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,2]],"date-time":"2026-06-02T23:12:26Z","timestamp":1780441946777,"version":"3.54.1"},"reference-count":54,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2016,2,12]],"date-time":"2016-02-12T00:00:00Z","timestamp":1455235200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Ann Oper Res"],"published-print":{"date-parts":[[2016,9]]},"DOI":"10.1007\/s10479-016-2116-5","type":"journal-article","created":{"date-parts":[[2016,2,12]],"date-time":"2016-02-12T05:28:02Z","timestamp":1455254882000},"page":"313-348","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["Exact methods for solving the elementary shortest and longest path problems"],"prefix":"10.1007","volume":"244","author":[{"given":"Quoc Trung","family":"Bui","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yves","family":"Deville","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Quang Dung","family":"Pham","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2016,2,12]]},"reference":[{"key":"2116_CR1","doi-asserted-by":"crossref","unstructured":"Achterberg, T., & Berthold, T. (2009). Hybrid branching. In Proceeding of the 6th international conference on integration of AI and OR techniques in constraint programming for combinatorial optimization problems (pp. 309\u2013311).","DOI":"10.1007\/978-3-642-01929-6_23"},{"issue":"1","key":"2116_CR2","doi-asserted-by":"crossref","first-page":"42","DOI":"10.1016\/j.orl.2004.04.002","volume":"33","author":"T Achterberg","year":"2005","unstructured":"Achterberg, T., Koch, T., & Martin, A. (2005). Branching rules revisited. Operations Research Letters, 33(1), 42\u201354.","journal-title":"Operations Research Letters"},{"key":"2116_CR3","unstructured":"Ar\u00e1oz, J., Fern\u00e1ndez, E., & Meza, O. (2007) A simple exact separation algorithm for 2-matching inequalities. Research Report DR-2007\/13, EIO Departement, Technical University of Catalonia (Spain). http:\/\/www.optimization-online.org\/DBHTML\/2007\/11\/1827.html ."},{"issue":"1","key":"2116_CR4","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1023\/A:1008779125567","volume":"17","author":"N Ascheuer","year":"2000","unstructured":"Ascheuer, N., J\u00fcnger, M., & Reinelt, G. (2000). A branch & cut algorithm for the asymmetric traveling salesman problem with precedence constraints. Computational Optimization and Applications, 17(1), 61\u201384.","journal-title":"Computational Optimization and Applications"},{"issue":"9","key":"2116_CR5","doi-asserted-by":"crossref","first-page":"1229","DOI":"10.1287\/mnsc.42.9.1229","volume":"42","author":"E Balas","year":"1996","unstructured":"Balas, E., Ceria, S., & Cornu\u00e9jols, G. (1996). Mixed 0\u20131 programming by lift-and-project in a branch-and-cut framework. Management Science, 42(9), 1229\u20131246.","journal-title":"Management Science"},{"key":"2116_CR6","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1007\/BF01581274","volume":"58","author":"E Balas","year":"1993","unstructured":"Balas, E., & Fischetti, M. (1993). A lifting procedure for the asymmetric traveling salesman polytope and a large new class of facets. Mathematical Programming, 58, 325\u2013352.","journal-title":"Mathematical Programming"},{"issue":"1","key":"2116_CR7","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.ejor.2011.07.037","volume":"218","author":"R Baldacci","year":"2012","unstructured":"Baldacci, R., Mingozzi, A., & Roberti, R. (2012). Recent exact algorithms for solving the vehicle routing problem under capacity and time window constraints. European Journal of Operational Research, 218(1), 1\u20136.","journal-title":"European Journal of Operational Research"},{"key":"2116_CR8","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1002\/net.3230190402","volume":"19","author":"JE Beasley","year":"1989","unstructured":"Beasley, J. E., & Christofides, N. (1989). An algorithm for the resource constrained shortest path problem. Network, 19, 379\u2013394.","journal-title":"Network"},{"key":"2116_CR9","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1017\/S0962492913000032","volume":"22","author":"P Belotti","year":"2013","unstructured":"Belotti, P., et al. (2013). Mixed-integer nonlinear optimization. Acta Numerica, 22, 1\u2013131.","journal-title":"Acta Numerica"},{"key":"2116_CR10","doi-asserted-by":"crossref","first-page":"413","DOI":"10.1007\/BF01581256","volume":"59","author":"D Bienstock","year":"1993","unstructured":"Bienstock, D., et al. (1993). A note on the prize collecting traveling salesman problem. Mathematical Programming, 59, 413\u2013420.","journal-title":"Mathematical Programming"},{"issue":"1","key":"2116_CR11","doi-asserted-by":"crossref","first-page":"58","DOI":"10.1016\/j.orl.2004.11.011","volume":"34","author":"N Boland","year":"2006","unstructured":"Boland, N., Dethridge, J., & Dumitrescu, I. (2006). Accelerated label setting algorithms for the elementary resource constrained shortest path problem. Operations Research Letters, 34(1), 58\u201368.","journal-title":"Operations Research Letters"},{"key":"2116_CR12","unstructured":"Comet Tutorial. Dynamic Decision Technologies, Inc, 2010."},{"key":"2116_CR13","volume-title":"Introduction to algorithms, third edition","author":"TH Cormen","year":"2009","unstructured":"Cormen, T. H., et al. (2009). Introduction to algorithms, third edition (3rd ed.). Cambridge: The MIT Press.","edition":"3"},{"key":"2116_CR14","first-page":"99","volume":"44","author":"AM Costa","year":"2006","unstructured":"Costa, A. M., Cordeau, J. F., & Laporte, G. (2006). Steiner tree problems with profits. INFOR: Information Systems and Operational Research, 44, 99\u2013116.","journal-title":"INFOR: Information Systems and Operational Research"},{"key":"2116_CR15","first-page":"1073","volume":"38","author":"M Dell\u2019Amico","year":"1995","unstructured":"Dell\u2019Amico, M., Maffioli, F., & V\u00e4rbrand, P. (1995). On prize-collecting tours and the asymmetric travelling salesman problem. International Transactions in Operational Research, 38, 1073\u20131079.","journal-title":"International Transactions in Operational Research"},{"key":"2116_CR16","doi-asserted-by":"crossref","unstructured":"Drexl, M., & Irnich, S. (2012). Solving elementary shortest-path problems as mixed-integer programs. OR Spectrum, 36(2), 281\u2013296.","DOI":"10.1007\/s00291-012-0302-7"},{"issue":"5","key":"2116_CR17","doi-asserted-by":"crossref","first-page":"977","DOI":"10.1287\/opre.42.5.977","volume":"42","author":"M Dror","year":"1994","unstructured":"Dror, M. (1994). Note on the complexity of the shortest path models for column generation in WRPTW. Operations Research, 42(5), 977\u2013978.","journal-title":"Operations Research"},{"key":"2116_CR18","doi-asserted-by":"crossref","first-page":"125","DOI":"10.6028\/jres.069B.013","volume":"69","author":"J Edmonds","year":"1965","unstructured":"Edmonds, J. (1965). Maximum matching and a polyhedron with 0, 1-vertices. Journal of Research of the National Bureau of Standards B, 69, 125\u2013130.","journal-title":"Journal of Research of the National Bureau of Standards B"},{"key":"2116_CR19","doi-asserted-by":"crossref","first-page":"188","DOI":"10.1287\/trsc.1030.0079","volume":"39","author":"D Feillet","year":"2005","unstructured":"Feillet, D., Dejax, P., & Gendreau, M. (2005). Traveling salesman problems with profits. Transportation Science, 39, 188\u2013205.","journal-title":"Transportation Science"},{"key":"2116_CR20","doi-asserted-by":"crossref","unstructured":"Feillet, D., et al. (2004). An exact algorithm for the elementary shortest path problem with resource constraints: Application to some vehicle routing problems. Networks, 44(3), 216\u2013229.","DOI":"10.1002\/net.20033"},{"issue":"1","key":"2116_CR21","doi-asserted-by":"crossref","first-page":"42","DOI":"10.1287\/moor.16.1.42","volume":"16","author":"M Fischetti","year":"1991","unstructured":"Fischetti, M. (1991). Facets of the asymmetric traveling salesman polytope. Mathematics of Operations Research, 16(1), 42\u201356.","journal-title":"Mathematics of Operations Research"},{"key":"2116_CR22","unstructured":"Fischetti, M., Lodi, A., & Toth, P. (2004). Exact methods for the asymmetric traveling salesman problem. In G. Gutin & A. P. Punnen (Eds.), The traveling salesman problem and its variations (pp. 169\u2013205). US: Springer."},{"key":"2116_CR23","unstructured":"Goemans, M. X., & Williamson, D. P. (1992). A general approximation technique for constrained forest problems. In Proceedings of the third annual ACM-SIAM symposium on discrete algorithms (pp. 307\u2013316)."},{"key":"2116_CR24","volume-title":"Graphes et algorithmes, 3e \u00e9dition revue et augment\u00e9e","author":"M Gondran","year":"1995","unstructured":"Gondran, M., & Minoux, M. (1995). Graphes et algorithmes, 3e \u00e9dition revue et augment\u00e9e. Paris: Eyrolles."},{"key":"2116_CR25","unstructured":"Gr\u00f6tschel, M., & Padberg, M. (1985). Polyhedral theory. In E. L. Lawler, J. K. Lenstra & A. H. G. Rinnooy Kan (Eds.), The traveling salesman problem: A guided tour of combinatorial optimization (pp. 251\u2013305). Wiley."},{"key":"2116_CR26","doi-asserted-by":"crossref","first-page":"361","DOI":"10.1111\/j.1475-3995.2008.00681.x","volume":"16","author":"MS Ibrahim","year":"2009","unstructured":"Ibrahim, M. S., Maculan, N., & Minoux, M. (2009). A strong flow-based formulation for the shortest path problem in digraphs with negative cycles. International Transactions in Operational Research, 16, 361\u2013369.","journal-title":"International Transactions in Operational Research"},{"key":"2116_CR27","doi-asserted-by":"crossref","unstructured":"Irnich, S., & Desaulniers, G. (2005). Shortest path problems with resource constraints. In G. Desaulniers, J. Desrosiers & M. M. Solomon (Eds.), Column generation (pp. 33\u201365). US: Springer.","DOI":"10.1007\/0-387-25486-2_2"},{"key":"2116_CR28","unstructured":"Jepsen, M. K., Petersen, B., & Spoorendonk, S. (2008). A branch-and-cut algorithm for the elementary shortest path problem with a capacity constraint. Technical Report, Department of Computer Science, University of Copenhagen."},{"key":"2116_CR29","doi-asserted-by":"crossref","first-page":"82","DOI":"10.1007\/BF02523689","volume":"18","author":"D Karger","year":"1997","unstructured":"Karger, D., Motwani, R., & Ramkumar, G. (1997). On approximating the longest path in a graph. Algorithmica, 18, 82\u201398.","journal-title":"Algorithmica"},{"key":"2116_CR30","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1002\/(SICI)1097-0037(199810)32:3<207::AID-NET5>3.0.CO;2-O","volume":"32","author":"T Koch","year":"1998","unstructured":"Koch, T., & Martin, A. (1998). Solving Steiner tree problems in graphs to optimality. Networks, 32, 207\u2013232.","journal-title":"Networks"},{"issue":"1","key":"2116_CR31","doi-asserted-by":"crossref","first-page":"58","DOI":"10.1016\/0377-2217(85)90284-X","volume":"20","author":"RV Kulkarni","year":"1985","unstructured":"Kulkarni, R. V., & Bhave, P. R. (1985). Integer programming formulations of vehicle routing problems. European Journal of Operational Research, 20(1), 58\u201367.","journal-title":"European Journal of Operational Research"},{"key":"2116_CR32","doi-asserted-by":"crossref","first-page":"972","DOI":"10.1287\/opre.11.6.972","volume":"11","author":"JDC Little","year":"1963","unstructured":"Little, J. D. C., et al. (1963). An algorithm for the traveling salesman problem. Operations Research, 11, 972\u2013989.","journal-title":"Operations Research"},{"key":"2116_CR33","doi-asserted-by":"crossref","unstructured":"Ljubi\u0107, I., et al. (2006). An algorithmic framework for the exact solution of the prize-collecting Steiner tree problem. Mathematical Programming, 105(2), 427\u2013449.","DOI":"10.1007\/s10107-005-0660-x"},{"key":"2116_CR34","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1002\/(SICI)1097-0037(199801)31:1<39::AID-NET5>3.0.CO;2-L","volume":"31","author":"A Lucena","year":"1998","unstructured":"Lucena, A., & Beasley, J. E. (1998). A branch and cut algorithm for the Steiner problem in graphs. Networks, 31, 39\u201359.","journal-title":"Networks"},{"issue":"4","key":"2116_CR35","doi-asserted-by":"crossref","first-page":"326","DOI":"10.1145\/321043.321046","volume":"7","author":"CE Miller","year":"1960","unstructured":"Miller, C. E., Tucker, A. W., & Zemlin, R. A. (1960). Integer programming formulation of traveling salesman problems. Journal of the ACM (JACM), 7(4), 326\u2013329.","journal-title":"Journal of the ACM (JACM)"},{"key":"2116_CR36","doi-asserted-by":"crossref","first-page":"907","DOI":"10.1016\/j.endm.2010.05.115","volume":"36","author":"VH Nguyen","year":"2010","unstructured":"Nguyen, V. H., & Nguyen, T. T. T. (2010). Approximating the asymmetric profitable tour. Electronic Notes in Discrete Mathematics, 36, 907\u2013914.","journal-title":"Electronic Notes in Discrete Mathematics"},{"issue":"1","key":"2116_CR37","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0167-6377(87)90002-2","volume":"6","author":"M Padberg","year":"1987","unstructured":"Padberg, M., & Rinaldi, G. (1987). Optimization of a 532-city symmetric traveling salesman problem by branch and cut. Operations Research Letters, 6(1), 1\u20137.","journal-title":"Operations Research Letters"},{"key":"2116_CR38","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1007\/BF01580861","volume":"47","author":"M Padberg","year":"1990","unstructured":"Padberg, M., & Rinaldi, G. (1990). Facet identification for the symmetric traveling salesman polytope. Mathematical Programming, 47, 219\u2013257.","journal-title":"Mathematical Programming"},{"key":"2116_CR39","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1287\/moor.7.1.67","volume":"7","author":"MW Padberg","year":"1982","unstructured":"Padberg, M. W., & Rao, M. R. (1982). Odd minimum cut-sets and b-matchings. Mathematics of Operations Research, 7, 67\u201380.","journal-title":"Mathematics of Operations Research"},{"key":"2116_CR40","unstructured":"Padberg, M. W., & Gr\u00f6tschel, M. (1985). Polyhedral computation. In E. L. Lawler, J. K. Lenstra, & A. H. G. Rinnooy Kan (Eds.), The traveling salesman problem: A guided tour of combinatorial optimization (pp. 251\u2013305). Wiley."},{"key":"2116_CR41","doi-asserted-by":"crossref","unstructured":"Pham, Q. D & Deville, Y. (2012) Solving the longest simple path problem with constrains-based techniques. In Proceedings of the 9th international conference on integration of AI and OR techniques in constraint programming for combinatorial optimization problems (pp. 292\u2013306).","DOI":"10.1007\/978-3-642-29828-8_19"},{"key":"2116_CR42","doi-asserted-by":"crossref","unstructured":"Portugal, D., Antunes, C. H., & Rocha, R. P. (2010). A study of genetic algorithms for approximating the longest path in generic graphs. In Systems man and cybernetics (SMC), 2010 IEEE international conference on (pp. 2539\u20132544).","DOI":"10.1109\/ICSMC.2010.5641920"},{"key":"2116_CR43","doi-asserted-by":"crossref","unstructured":"Portugal, D., & Rocha, R. P. (2010) Msp algorithm: Multi-robot patrolling based on territory allocation using balanced graph partitioning. In Proceedings of the 2010 ACM symposium on applied computing (pp. 1271\u20131276).","DOI":"10.1145\/1774088.1774360"},{"key":"2116_CR44","doi-asserted-by":"crossref","unstructured":"Punnen, A. P. (2004) The traveling salesman problem: Applications, formulations and variations. In G. Gutin, & A. P. Punnen (Eds.), The Traveling salesman problem and its variations (pp. 1\u201328).","DOI":"10.1007\/0-306-48213-4_1"},{"key":"2116_CR45","unstructured":"Radulescu, A., L\u00f3pez-Ib\u00e1\u00f1ez, M., & St\u00fctzle, T. (2012). Automatically improving the anytime behaviour of multiobjective evolutionary algorithms. Technical Report TR\/IRIDIA\/2012-019, IRIDIA, Universit\u00e9 Libre de Bruxelles, Belgium."},{"key":"2116_CR46","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1016\/j.disopt.2006.05.007","volume":"3","author":"G Righini","year":"2006","unstructured":"Righini, G., & Salani, M. (2006). Symmetry helps: Bounded bi-directional dynamic programming for the elementary shortest path problem with resource constraints. Discrete Optimization, 3, 255\u2013273.","journal-title":"Discrete Optimization"},{"key":"2116_CR47","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1002\/net.20212","volume":"51","author":"G Righini","year":"2008","unstructured":"Righini, G., & Salani, M. (2008). New dynamic programming algorithms for the resource constrained elementary shortest path problem. Network, 51, 155\u2013170.","journal-title":"Network"},{"key":"2116_CR48","doi-asserted-by":"crossref","unstructured":"Schmidt, K., & Schmidt, E. G. (2010). A longest-path problem for evaluating the worst-case packet delay of switched ethernet. In Industrial embedded systems (SIES), 2010 international symposium on (pp. 205\u2013208)","DOI":"10.1109\/SIES.2010.5551398"},{"key":"2116_CR49","doi-asserted-by":"crossref","unstructured":"Tarjan, R. (1972). Depth-first search and linear graph algorithm. SIAM Journal on Computing, 1(2), 146\u2013160.","DOI":"10.1137\/0201010"},{"key":"2116_CR50","doi-asserted-by":"crossref","unstructured":"Toth, P., & Vigo, D. (Eds.). (2002). The vehicle routing problem. SIAM monographs on discrete mathematics and applications. Philadelphia: SIAM.","DOI":"10.1137\/1.9780898718515"},{"key":"2116_CR51","unstructured":"Tseng, I. L., Chen, H. W. & Lee, C. I. (2010) Obstacle-aware longest-path routing with parallel MILP solvers. In Proceedings of the world congress on engineering and computer science (pp. 827\u2013831)."},{"issue":"4","key":"2116_CR52","doi-asserted-by":"crossref","first-page":"437","DOI":"10.1016\/j.orl.2005.02.007","volume":"34","author":"E Uchoa","year":"2006","unstructured":"Uchoa, E. (2006). Reduction tests for the prize-collecting Steiner problem. Operations Research Letters, 34(4), 437\u2013444.","journal-title":"Operations Research Letters"},{"key":"2116_CR53","first-page":"297","volume":"3","author":"T Volgenant","year":"1987","unstructured":"Volgenant, T., & Jonker, R. (1987). On some generalizations of the travelling-salesman problem. Journal of the Operational Research Society, 3, 297\u2013308.","journal-title":"Journal of the Operational Research Society"},{"key":"2116_CR54","doi-asserted-by":"crossref","unstructured":"Wong, W. Y. (2005). Information retrieval in p2p networks using genetic algorithm. In Proceedings of the 14th international world wide web conference (pp. 922\u2013923).","DOI":"10.1145\/1062745.1062799"}],"container-title":["Annals of Operations Research"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10479-016-2116-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10479-016-2116-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10479-016-2116-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10479-016-2116-5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,4]],"date-time":"2019-09-04T13:37:58Z","timestamp":1567604278000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10479-016-2116-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,2,12]]},"references-count":54,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2016,9]]}},"alternative-id":["2116"],"URL":"https:\/\/doi.org\/10.1007\/s10479-016-2116-5","relation":{},"ISSN":["0254-5330","1572-9338"],"issn-type":[{"value":"0254-5330","type":"print"},{"value":"1572-9338","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,2,12]]}}}