{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,9]],"date-time":"2026-05-09T06:51:32Z","timestamp":1778309492589,"version":"3.51.4"},"reference-count":34,"publisher":"Wiley","issue":"2","license":[{"start":{"date-parts":[[2021,6,21]],"date-time":"2021-06-21T00:00:00Z","timestamp":1624233600000},"content-version":"am","delay-in-days":365,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#am"},{"start":{"date-parts":[[2020,6,21]],"date-time":"2020-06-21T00:00:00Z","timestamp":1592697600000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"funder":[{"DOI":"10.13039\/100007297","name":"Office of Naval Research Global","doi-asserted-by":"publisher","award":["N00014\u201019\u20101\u20102329"],"award-info":[{"award-number":["N00014\u201019\u20101\u20102329"]}],"id":[{"id":"10.13039\/100007297","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100006070","name":"Universidad de los Andes","doi-asserted-by":"publisher","award":["Office of Research \/ 2019\u20102020"],"award-info":[{"award-number":["Office of Research \/ 2019\u20102020"]}],"id":[{"id":"10.13039\/501100006070","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["onlinelibrary.wiley.com"],"crossmark-restriction":true},"short-container-title":["Networks"],"published-print":{"date-parts":[[2020,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>A constrained shortest path is a minimum\u2010cost sequence of arcs on a directed network that satisfies knapsack\u2010type constraints on the resource consumption over the arcs. We propose an exact method based on a recursive depth\u2010first search procedure known as the pulse algorithm (PA). One of the key contributions of the proposal lies in a bidirectional search strategy leveraged on parallelism. In addition, we developed a pulse\u2010based heuristic that quickly finds near\u2010optimal solutions and shows great potential for column generation (CG) schemes. We present computational experiments over large real\u2010road networks with up to 6 million nodes and 15 million arcs. We illustrate the use of the bidirectional PA in a CG scheme to solve a multi\u2010activity shift scheduling problem, where the pricing problem is modeled as a constrained\u2010shortest path with multiple resource constraints.<\/jats:p>","DOI":"10.1002\/net.21960","type":"journal-article","created":{"date-parts":[[2020,6,21]],"date-time":"2020-06-21T12:50:53Z","timestamp":1592743853000},"page":"128-146","update-policy":"https:\/\/doi.org\/10.1002\/crossmark_policy","source":"Crossref","is-referenced-by-count":37,"title":["An exact bidirectional pulse algorithm for the constrained shortest path"],"prefix":"10.1002","volume":"76","author":[{"given":"Nicol\u00e1s","family":"Cabrera","sequence":"first","affiliation":[{"name":"Industrial Engineering Department Universidad de los Andes  Bogot\u00e1 Colombia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1529-0322","authenticated-orcid":false,"given":"Andr\u00e9s L.","family":"Medaglia","sequence":"additional","affiliation":[{"name":"Industrial Engineering Department Universidad de los Andes  Bogot\u00e1 Colombia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Leonardo","family":"Lozano","sequence":"additional","affiliation":[{"name":"Operations, Business Analytics and Information Systems University of Cincinnati  Cincinnati Ohio USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3364-9597","authenticated-orcid":false,"given":"Daniel","family":"Duque","sequence":"additional","affiliation":[{"name":"Industrial Engineering and Management Sciences Northwestern University  Evanston Illinois USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","published-online":{"date-parts":[[2020,6,21]]},"reference":[{"key":"e_1_2_9_2_1","unstructured":"9th DIMACSImplementation Challenge\u2014Shortest Paths.http:\/\/users.diag.uniroma1.it\/challenge9\/. Accessed: July 8 2019."},{"key":"e_1_2_9_3_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.2018.1756"},{"key":"e_1_2_9_4_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.50.1.3.17780"},{"key":"e_1_2_9_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11590-014-0742-x"},{"key":"e_1_2_9_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2006.04.030"},{"key":"e_1_2_9_7_1","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.1090.0282"},{"key":"e_1_2_9_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/b135457"},{"key":"e_1_2_9_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/141868.141871"},{"key":"e_1_2_9_10_1","doi-asserted-by":"publisher","DOI":"10.1111\/1475-3995.00003"},{"key":"e_1_2_9_11_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.10090"},{"key":"e_1_2_9_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2014.08.019"},{"key":"e_1_2_9_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2014.11.003"},{"key":"e_1_2_9_14_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.21909"},{"key":"e_1_2_9_15_1","volume-title":"Computers and Intractability: A Guide to the Theory of NP\u2010Completeness","author":"Garey M.R.","year":"1979"},{"key":"e_1_2_9_16_1","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.39.6.736"},{"key":"e_1_2_9_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2005.01.017"},{"key":"e_1_2_9_18_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230100403"},{"key":"e_1_2_9_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/0377-2217(88)90377-3"},{"key":"e_1_2_9_20_1","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.2014.0582"},{"key":"e_1_2_9_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2012.07.008"},{"key":"e_1_2_9_22_1","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.2016.0721"},{"key":"e_1_2_9_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.trc.2015.09.009"},{"key":"e_1_2_9_24_1","doi-asserted-by":"publisher","DOI":"10.2172\/4785039"},{"key":"e_1_2_9_25_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.21511"},{"key":"e_1_2_9_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10732-009-9106-6"},{"key":"e_1_2_9_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ijpe.2012.06.030"},{"key":"e_1_2_9_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.trb.2006.12.001"},{"key":"e_1_2_9_29_1","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.2018.0880"},{"key":"e_1_2_9_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.amc.2015.05.109"},{"key":"e_1_2_9_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02216932"},{"key":"e_1_2_9_32_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.21856"},{"key":"e_1_2_9_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/0-306-47536-7_13"},{"key":"e_1_2_9_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.trd.2017.10.001"},{"key":"e_1_2_9_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2011.03.008"}],"container-title":["Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/net.21960","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/full-xml\/10.1002\/net.21960","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/am-pdf\/10.1002\/net.21960","content-type":"application\/pdf","content-version":"am","intended-application":"syndication"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/net.21960","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,2]],"date-time":"2023-09-02T15:56:42Z","timestamp":1693670202000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/net.21960"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,21]]},"references-count":34,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2020,9]]}},"alternative-id":["10.1002\/net.21960"],"URL":"https:\/\/doi.org\/10.1002\/net.21960","archive":["Portico"],"relation":{},"ISSN":["0028-3045","1097-0037"],"issn-type":[{"value":"0028-3045","type":"print"},{"value":"1097-0037","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,6,21]]},"assertion":[{"value":"2020-05-22","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-05-23","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-06-21","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}