{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,5]],"date-time":"2026-05-05T07:22:22Z","timestamp":1777965742291,"version":"3.51.4"},"reference-count":24,"publisher":"Wiley","issue":"2","license":[{"start":{"date-parts":[[2006,10,11]],"date-time":"2006-10-11T00:00:00Z","timestamp":1160524800000},"content-version":"vor","delay-in-days":4972,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Networks"],"published-print":{"date-parts":[[1993,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We study a specialized version of network design problems that arise in telecommunications, transportation, and other industries. The problem, a generalization of the shortest path problem, is defined on an undirected network consisting of a set of arcs on which we can install (load), at a cost, a choice of up to three types of capacitated facilities. Our objective is to determine the configuration of facilities to load on each arc that will satisfy the demand of a single commodity at the lowest possible cost. Our results (i) demonstrate that the single\u2010facility loading problem and certain \u201ccommon break\u2010even point\u201d versions of the two\u2010facility and three\u2010facility loading problems are polynomially solvable as a shortest path problem; (ii) show that versions of the two\u2010facility loading problem are strongly NP\u2010hard, but that a shortest path solution provides an asymptotically \u201cgood\u201d heuristic; and (iii) characterize the optimal solution (i.e., specify a linear programming formulation with integer solutions) of the common break\u2010even point versions of the two\u2010facility and three\u2010facility loading problems. In this development, we introduce two new families of facets, give geometric interpretations of our results, and demonstrate the usefulness of partitioning the space of the problem parameters to establish polyhedral integrality properties. Generalizations of our results apply to (i) multicommodity applications and (ii) situations with more than three facilities. \u00a9 <jats:italic>1993 by John Wiley &amp; Sons, Inc.<\/jats:italic><\/jats:p>","DOI":"10.1002\/net.3230230205","type":"journal-article","created":{"date-parts":[[2007,5,12]],"date-time":"2007-05-12T13:49:15Z","timestamp":1178977755000},"page":"103-121","source":"Crossref","is-referenced-by-count":64,"title":["Shortest paths, single origin\u2010destination network design, and associated polyhedra"],"prefix":"10.1002","volume":"23","author":[{"given":"Thomas L.","family":"Magnanti","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Prakash","family":"Mirchandani","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","published-online":{"date-parts":[[2006,10,11]]},"reference":[{"key":"e_1_2_1_2_2","volume-title":"Network Flows: Theory, Algorithms, and Applications","author":"Ahuja R.","year":"1993"},{"key":"e_1_2_1_3_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230190202"},{"key":"e_1_2_1_4_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.37.5.716"},{"key":"e_1_2_1_5_2","doi-asserted-by":"publisher","DOI":"10.1002\/nav.3800080104"},{"key":"e_1_2_1_6_2","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0121006"},{"key":"e_1_2_1_7_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01584085"},{"key":"e_1_2_1_8_2","volume-title":"Computers and Intractability: A Guide to the Theory of NP\u2010Completeness","author":"Garey M. R.","year":"1979"},{"key":"e_1_2_1_9_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.19.1.156"},{"key":"e_1_2_1_10_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.19.6.1529"},{"key":"e_1_2_1_11_2","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.1.4.271"},{"key":"e_1_2_1_12_2","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.24.4.245"},{"key":"e_1_2_1_13_2","series-title":"Working Paper No. 709","volume-title":"Modeling and solving the capacitated network loading problem","author":"Magnanti T. L.","year":"1991"},{"key":"e_1_2_1_14_2","article-title":"The convex hull of two core capacitated network loading problems","author":"Magnanti T. L.","journal-title":"Math. Program."},{"key":"e_1_2_1_15_2","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.18.1.1"},{"key":"e_1_2_1_16_2","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1007\/BF02997589","article-title":"Multiflots de c\u01d2ut minimal avec fonctions de c\u01d2ut concaves","volume":"1","author":"Minoux M.","year":"1976","journal-title":"Ann. Telecommun."},{"key":"e_1_2_1_17_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230190305"},{"key":"e_1_2_1_18_2","unstructured":"P.Mirchandani Polyhedral structure of a capacitated network design problem with an application to the telecommunication industry. Unpublished PhD Dissertation MIT Cambridge MA (1989)."},{"key":"e_1_2_1_19_2","doi-asserted-by":"publisher","DOI":"10.1002\/9781118627372"},{"key":"e_1_2_1_20_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.33.4.842"},{"key":"e_1_2_1_21_2","first-page":"471","article-title":"The load planning problem of motor carriers: Problem description and proposed solution approach","volume":"17","author":"Powell W.","year":"1983","journal-title":"Transportation Sci."},{"key":"e_1_2_1_22_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01589102"},{"key":"e_1_2_1_23_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230010205"},{"key":"e_1_2_1_24_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230030404"},{"key":"e_1_2_1_25_2","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.14.7.429"}],"container-title":["Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fnet.3230230205","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/net.3230230205","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,25]],"date-time":"2023-10-25T01:20:34Z","timestamp":1698196834000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/net.3230230205"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993,3]]},"references-count":24,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1993,3]]}},"alternative-id":["10.1002\/net.3230230205"],"URL":"https:\/\/doi.org\/10.1002\/net.3230230205","archive":["Portico"],"relation":{},"ISSN":["0028-3045","1097-0037"],"issn-type":[{"value":"0028-3045","type":"print"},{"value":"1097-0037","type":"electronic"}],"subject":[],"published":{"date-parts":[[1993,3]]}}}