{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,11]],"date-time":"2026-07-11T17:21:23Z","timestamp":1783790483763,"version":"3.55.0"},"reference-count":57,"publisher":"Wiley","issue":"4","license":[{"start":{"date-parts":[[2006,10,11]],"date-time":"2006-10-11T00:00:00Z","timestamp":1160524800000},"content-version":"vor","delay-in-days":6311,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Networks"],"published-print":{"date-parts":[[1989,7]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In this paper we examine an integer programming formulation of the resource constrained shortest path problem. This is the problem of a traveller with a budget of various resources who has to reach a given destination as quickly as possible within the resource constraints imposed by his budget. A lagrangean relaxation of the integer programming formulation of the problem into a minimum cost network flow problem (which in certain circumstances reduces to an unconstrained shortest path problem) is developed which provides a lower bound for use in a tree search procedure. Problem reduction tests based on both the original problem and this lagrangean relaxation are given. Computational results are presented for the solution of problems involving up to 500 vertices, 5000 arcs, and 10 resources.<\/jats:p>","DOI":"10.1002\/net.3230190402","type":"journal-article","created":{"date-parts":[[2007,5,12]],"date-time":"2007-05-12T03:19:10Z","timestamp":1178939950000},"page":"379-394","source":"Crossref","is-referenced-by-count":237,"title":["An algorithm for the resource constrained shortest path problem"],"prefix":"10.1002","volume":"19","author":[{"given":"J. E.","family":"Beasley","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"N.","family":"Christofides","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"311","published-online":{"date-parts":[[2006,10,11]]},"reference":[{"key":"e_1_2_1_2_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230130212"},{"key":"e_1_2_1_3_2","doi-asserted-by":"publisher","DOI":"10.1002\/nav.3800250314"},{"key":"e_1_2_1_4_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01939836"},{"key":"e_1_2_1_5_2","unstructured":"J. E.Beasley The application of mathematical programming and graph theory in distribution problems. PhD thesis University of London (1979)."},{"key":"e_1_2_1_6_2","doi-asserted-by":"publisher","DOI":"10.1137\/0108044"},{"key":"e_1_2_1_7_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01589353"},{"key":"e_1_2_1_8_2","unstructured":"T. S.Chuah Constrained shortes path. MSc thesis Department of Management Science Imperial college London (1978)."},{"key":"e_1_2_1_9_2","doi-asserted-by":"publisher","DOI":"10.1016\/0377-2217(82)90205-3"},{"key":"e_1_2_1_10_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-247X(66)90009-6"},{"key":"e_1_2_1_11_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230140208"},{"key":"e_1_2_1_12_2","series-title":"Publication number 394A","volume-title":"A generalized permanent labelling algorithm for the shortest path problem with time windows","author":"Desrochers M.","year":"1985"},{"key":"e_1_2_1_13_2","series-title":"Publication number 421A","volume-title":"An algorithm for the sortest path problem with resource constraints","author":"Desrochers M."},{"key":"e_1_2_1_14_2","doi-asserted-by":"crossref","first-page":"357","DOI":"10.1051\/ro\/1983170403571","article-title":"Plus court chemin avec contraintes d'horaires","volume":"17","author":"Desrosiers J.","year":"1983","journal-title":"RAIRO"},{"key":"e_1_2_1_15_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230140406"},{"key":"e_1_2_1_16_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01386390"},{"key":"e_1_2_1_17_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.17.3.395"},{"key":"e_1_2_1_18_2","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.27.1.1"},{"key":"e_1_2_1_19_2","doi-asserted-by":"publisher","DOI":"10.1287\/inte.15.2.10"},{"key":"e_1_2_1_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/367766.368168"},{"key":"e_1_2_1_21_2","unstructured":"L. R.Ford Network flow theory. Report number P\u2010923 The Rand Corporation Santa Monica CA (1956)."},{"key":"e_1_2_1_22_2","first-page":"214","volume-title":"Computers and Intractability: A Guide to the Theory of NP\u2010Completeness","author":"Garey M. R.","year":"1979"},{"key":"e_1_2_1_23_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230040304"},{"key":"e_1_2_1_24_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230100403"},{"key":"e_1_2_1_25_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-48782-8_9"},{"key":"e_1_2_1_26_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01580223"},{"key":"e_1_2_1_27_2","doi-asserted-by":"publisher","DOI":"10.1016\/0377-2217(86)90092-5"},{"key":"e_1_2_1_28_2","doi-asserted-by":"publisher","DOI":"10.1145\/320998.321004"},{"key":"e_1_2_1_29_2","first-page":"93","article-title":"The travelling salesman problem as a constrained shortest path problem: theory and computational experience","volume":"17","author":"Houck D. J.","year":"1980","journal-title":"Opsearch"},{"key":"e_1_2_1_30_2","doi-asserted-by":"publisher","DOI":"10.1137\/1015031"},{"key":"e_1_2_1_31_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230140109"},{"key":"e_1_2_1_32_2","unstructured":"P. A.JensenandR. C.Berry A constrained shortest path algorithm. Paper presented at the 39th National ORSA Meeting Dallas Texas USA. Abstract given inORSA Bulletin19 (1971)B\u2010139."},{"key":"e_1_2_1_33_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-247X(66)90020-5"},{"key":"e_1_2_1_34_2","doi-asserted-by":"publisher","DOI":"10.1090\/psapm\/010\/0122573"},{"key":"e_1_2_1_35_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230120406"},{"key":"e_1_2_1_36_2","unstructured":"A.Kershenbaum W.Hsieh andB. L.Golden Constrained routing in large sparse networks. InConference record of the IEEE International Conference on Communications pp.38.14\u201338.18(1976)."},{"key":"e_1_2_1_37_2","first-page":"92","volume-title":"Combinatorial Optimization: Networks and Matroids","author":"Lawler E. L.","year":"1976"},{"key":"e_1_2_1_38_2","volume-title":"The Travelling Salesman Problem: A Guided Tour of Combinatorial Optimization","author":"Lawler E. L.","year":"1985"},{"key":"e_1_2_1_39_2","doi-asserted-by":"publisher","DOI":"10.1145\/358172.358406"},{"key":"e_1_2_1_40_2","doi-asserted-by":"publisher","DOI":"10.1016\/0377-2217(84)90077-8"},{"key":"e_1_2_1_41_2","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(84)90028-2"},{"key":"e_1_2_1_42_2","doi-asserted-by":"publisher","DOI":"10.1016\/0041-1647(67)90170-0"},{"key":"e_1_2_1_43_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230160204"},{"key":"e_1_2_1_44_2","doi-asserted-by":"publisher","DOI":"10.1002\/nav.3800310110"},{"key":"e_1_2_1_45_2","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(85)90007-1"},{"key":"e_1_2_1_46_2","volume-title":"Methods of Operations Research","author":"Ribeiro C."},{"key":"e_1_2_1_47_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.16.6.1232"},{"key":"e_1_2_1_48_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.16.1.205"},{"key":"e_1_2_1_49_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.14.5.909"},{"key":"e_1_2_1_50_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230060303"},{"key":"e_1_2_1_51_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230090303"},{"key":"e_1_2_1_52_2","first-page":"425","article-title":"Probl\u00e8mes multicrit\u00e8res","volume":"16","author":"Vincke P.","year":"1974","journal-title":"Cahiers du Centre d'Etudes de Recherche Op\u00e9rationnellle"},{"key":"e_1_2_1_53_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.35.1.70"},{"key":"e_1_2_1_54_2","doi-asserted-by":"publisher","DOI":"10.1016\/0305-0548(82)90008-9"},{"key":"e_1_2_1_55_2","first-page":"158","volume-title":"Optimality and Efficiency","author":"White D. J.","year":"1982"},{"key":"e_1_2_1_56_2","unstructured":"C.WitzgallandA. J.Goldman Most profitable routing before maintenance. Paper presented at the 27th National ORSA Meeting Boston Massachusetts USA. Abstract given inORSA Bulletin13 (1965)B\u201082."},{"key":"e_1_2_1_57_2","doi-asserted-by":"publisher","DOI":"10.1090\/qam\/253822"},{"key":"e_1_2_1_58_2","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.17.11.712"}],"container-title":["Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fnet.3230190402","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/net.3230190402","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,22]],"date-time":"2023-10-22T08:44:24Z","timestamp":1697964264000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/net.3230190402"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1989,7]]},"references-count":57,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1989,7]]}},"alternative-id":["10.1002\/net.3230190402"],"URL":"https:\/\/doi.org\/10.1002\/net.3230190402","archive":["Portico"],"relation":{},"ISSN":["0028-3045","1097-0037"],"issn-type":[{"value":"0028-3045","type":"print"},{"value":"1097-0037","type":"electronic"}],"subject":[],"published":{"date-parts":[[1989,7]]}}}