{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,12]],"date-time":"2026-07-12T03:31:58Z","timestamp":1783827118063,"version":"3.55.0"},"reference-count":128,"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":9263,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Networks"],"published-print":{"date-parts":[[1981,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>As a well\u2010structured and costly activity that pervades industries in both the public and private sector, vehicle fleet management would appear to be a splendid candidate for model\u2010based planning and optimization. And yet, until recently the combinatorial intricacies of vehicle routing and of vehicle scheduling have precluded the widespread use of optimization (exact) methods for this problem class. Our discussion in this paper identifies the extent and nature of these problem complexities and draws contrasts with other applications of combinatorial optimization. It also summarizes a number of successful uses of optimization for vehicle fleet planning and highlights potentially fruitful avenues for algorithmic development. In particular, we describe several alternative models and novel algorithms for the vehicle routing problem, show how various modeling approaches for this problem are intimately related, and illustrate the interplay between model formulations and the algorithms that they suggest. This discussion shows that prospects for applying exact methods, possibly in conjunction with heuristics, are far from fully realized and points to vehicle fleet planning as a tempting target of opportunity for further investigation.<\/jats:p>","DOI":"10.1002\/net.3230110209","type":"journal-article","created":{"date-parts":[[2007,5,11]],"date-time":"2007-05-11T11:57:21Z","timestamp":1178884641000},"page":"179-213","source":"Crossref","is-referenced-by-count":98,"title":["Combinatorial optimization and vehicle fleet planning: Perspectives and prospects"],"prefix":"10.1002","volume":"11","author":[{"given":"T. L.","family":"Magnanti","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"311","published-online":{"date-parts":[[2006,10,11]]},"reference":[{"key":"e_1_2_1_2_2","first-page":"181","article-title":"Model and Calculation Program Relating to the Optimum Formulation of Trunk Haul Freight Trains","volume":"6","author":"Achermann J.","year":"1969","journal-title":"Bull. Int. Railway Cong. Assoc. Cybern. Elec. Railways"},{"key":"e_1_2_1_3_2","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.11.2.124"},{"key":"e_1_2_1_4_2","unstructured":"A.Assad \u201cAnalytic Models in Rail Transportation: An Annotated Bibliography\u201d Working Paper OR 066\u201377 Operations Research Center MIT ( October1977)."},{"key":"e_1_2_1_5_2","doi-asserted-by":"publisher","DOI":"10.1016\/0191-2607(80)90017-5"},{"key":"e_1_2_1_6_2","unstructured":"A.Assad \u201cModeling Rail Freight Management\u201d Ph.D. thesis Sloan School of Management MIT 1978."},{"key":"e_1_2_1_7_2","unstructured":"T. E.Baker \u201cMixed Integer Programming At Exxon\u201d Seminar Operations Research Center MIT 1979."},{"key":"e_1_2_1_8_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.12.2.300"},{"key":"e_1_2_1_9_2","unstructured":"M.Ball L.Bodin andR.Dial \u201cExperimentation With a Computerized System For Scheduling Mass Transit Vehicles and Crew\u201d presented at theInternational Workshop on Urban Passenger Vehicle and Crew Scheduling The University of Leeds England July1980."},{"key":"e_1_2_1_10_2","doi-asserted-by":"publisher","DOI":"10.1002\/nav.3800040205"},{"key":"e_1_2_1_11_2","doi-asserted-by":"publisher","DOI":"10.1002\/nav.3800040308"},{"key":"e_1_2_1_12_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01584338"},{"key":"e_1_2_1_13_2","doi-asserted-by":"publisher","DOI":"10.1017\/S0305004100034095"},{"key":"e_1_2_1_14_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.16.3.538"},{"key":"e_1_2_1_15_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230040106"},{"key":"e_1_2_1_16_2","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.13.2.113"},{"key":"e_1_2_1_17_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230110204"},{"key":"e_1_2_1_18_2","doi-asserted-by":"publisher","DOI":"10.1016\/0191-2615(80)90037-5"},{"key":"e_1_2_1_19_2","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.27.1.19"},{"key":"e_1_2_1_20_2","first-page":"55","article-title":"The Vehicle Routing Problem","volume":"10","author":"Christofides N.","year":"1976","journal-title":"R.A.I.R.O. Recherche Operationelle"},{"key":"e_1_2_1_21_2","unstructured":"N.Christofides \u201cWorst\u2010Case Analysis of a New Heuristic for the Traveling Salesman Problem\u201d Report 388 Graduate School of Industrial Administration Carnegie Mellon University February1976."},{"key":"e_1_2_1_22_2","doi-asserted-by":"publisher","DOI":"10.1057\/jors.1969.75"},{"key":"e_1_2_1_23_2","unstructured":"N.Christofides A.Mingozzi andP.Toth \u201cExact Algorithms for the Vehicle Routing Problem\u201d Math. Prog. to appear."},{"key":"e_1_2_1_24_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.12.4.568"},{"key":"e_1_2_1_25_2","volume-title":"Theory of Scheduling","author":"Conway R. W.","year":"1967"},{"key":"e_1_2_1_26_2","first-page":"151","volume-title":"The Complexity of Theorem\u2010Proving Procedures","author":"Cook S. A.","year":"1971"},{"key":"e_1_2_1_27_2","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.23.8.789"},{"key":"e_1_2_1_28_2","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.26.5.495"},{"key":"e_1_2_1_29_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230110206"},{"key":"e_1_2_1_30_2","first-page":"77","volume-title":"Theory of Graphs","author":"Dantzig G. B.","year":"1967"},{"key":"e_1_2_1_31_2","doi-asserted-by":"publisher","DOI":"10.1002\/nav.3800010309"},{"key":"e_1_2_1_32_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.2.4.393"},{"key":"e_1_2_1_33_2","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.6.1.80"},{"key":"e_1_2_1_34_2","doi-asserted-by":"publisher","DOI":"10.1002\/nav.3800160306"},{"key":"e_1_2_1_35_2","unstructured":"E. V.Denardo G.Huberman andU.Rothblum \u201cOptimal Location on a Line are Interleaved\u201d Technical Report School of Organization and Management Yale University 1980."},{"key":"e_1_2_1_36_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01580113"},{"key":"e_1_2_1_37_2","volume-title":"Distribution Management: Mathematical Modeling and Practical Analysis","author":"Eilon S.","year":"1971"},{"key":"e_1_2_1_38_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.14.3.361"},{"key":"e_1_2_1_39_2","unstructured":"A.FedergruenandP.Zipkin \u201cA Combined Vehicle Routing and Inventory Allocation Problem\u201d Research Working Paper No. 345A Graduate School of Business Columbia University June1980."},{"key":"e_1_2_1_40_2","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.27.1.1"},{"key":"e_1_2_1_41_2","unstructured":"M. L.FisherandR.Jaikumar \u201cA Decomposition Algorithm for Large\u2010Scale Vehicle Routing\u201d Technical Report 78\u201311\u201305 Dept. of Decision Sciences The Wharton School University of Pennsylvania July1978."},{"key":"e_1_2_1_42_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230110205"},{"key":"e_1_2_1_43_2","unstructured":"M. L.FisherandR.Jaikumar private communication."},{"key":"e_1_2_1_44_2","doi-asserted-by":"publisher","DOI":"10.1137\/0127003"},{"key":"e_1_2_1_45_2","first-page":"121","article-title":"The Engine Scheduling Problem in a Railway Network","volume":"14","author":"Florian M. G.","year":"1976","journal-title":"INFOR J."},{"key":"e_1_2_1_46_2","doi-asserted-by":"publisher","DOI":"10.1515\/9781400875184"},{"key":"e_1_2_1_47_2","doi-asserted-by":"publisher","DOI":"10.1057\/jors.1976.63"},{"key":"e_1_2_1_48_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.26.5.686"},{"key":"e_1_2_1_49_2","volume-title":"Computers and Intractibility: A Guide to the Theory of NP\u2010Completeness","author":"Garey M. R.","year":"1979"},{"key":"e_1_2_1_50_2","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.3.4.407"},{"key":"e_1_2_1_51_2","unstructured":"B.Gavish \u201cTopological Design of Centralized Computer Networks\u2010Formulations and Algorithms\u201d Networks to appear."},{"key":"e_1_2_1_52_2","unstructured":"B.GavishandS. C.Graves \u201cThe Traveling Salesman Problem and Related Problems\u201d Working Paper OR 078\u201378 Operations Research Center MIT July1978."},{"key":"e_1_2_1_53_2","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0120690"},{"key":"e_1_2_1_54_2","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.20.5.822"},{"key":"e_1_2_1_55_2","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.11.1.20"},{"key":"e_1_2_1_56_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.22.2.340"},{"key":"e_1_2_1_57_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230070303"},{"key":"e_1_2_1_58_2","doi-asserted-by":"publisher","DOI":"10.1080\/05695557708975144"},{"key":"e_1_2_1_59_2","unstructured":"B.Golden \u201cLarge Scale Vehicle Routing and Related Combinatorial Problems\u201d Ph.D. thesis Operations Research Center MIT 1976."},{"key":"e_1_2_1_60_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230070204"},{"key":"e_1_2_1_61_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230070203"},{"key":"e_1_2_1_62_2","unstructured":"S.Gorenstein S.Poley andW. W.White \u201cOn the Scheduling of Railroad Freight Operations\u201d Technical Report No. 320\u20132999 IBM Philadelphia Scientific Center January1971."},{"key":"e_1_2_1_63_2","article-title":"An Optimization\u2010Based Approach to Vehicle Routing","volume":"10","author":"Graves S. C.","year":"1980","journal-title":"ORSA Bull."},{"key":"e_1_2_1_64_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01585505"},{"key":"e_1_2_1_65_2","doi-asserted-by":"publisher","DOI":"10.1287\/inte.9.2pt2.6"},{"key":"e_1_2_1_66_2","doi-asserted-by":"publisher","DOI":"10.1137\/0110015"},{"key":"e_1_2_1_67_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.18.6.1138"},{"key":"e_1_2_1_68_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01584070"},{"key":"e_1_2_1_69_2","first-page":"25","article-title":"Computer Controlled Empty Wagon Distribution on The SBB","volume":"8","author":"Herren H.","year":"1977","journal-title":"Rail Int."},{"key":"e_1_2_1_70_2","first-page":"1053","article-title":"Locomotive Scheduling By Computer Bashpeck","volume":"4","author":"Holt J.","year":"1973","journal-title":"Rail Int."},{"key":"e_1_2_1_71_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.28.3.623"},{"key":"e_1_2_1_72_2","doi-asserted-by":"publisher","DOI":"10.1137\/0208045"},{"key":"e_1_2_1_73_2","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2.3.209"},{"key":"e_1_2_1_74_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"e_1_2_1_75_2","volume-title":"Algorithms for Network Programming","author":"Kennington J. L.","year":"1980"},{"key":"e_1_2_1_76_2","doi-asserted-by":"publisher","DOI":"10.1287\/moor.5.1.1"},{"key":"e_1_2_1_77_2","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.9.4.643"},{"key":"e_1_2_1_78_2","unstructured":"S.Lakshminarayan R.Lakshmanad R.Pupineau andR.Rochette \u201cOrder Preserving Allocation of Jobs to Two Non\u2010Identical Parallel Machines\u2014A Solvable Case of the Maximum Cut Problem\u201d Dept. d'ingeniere Univ. du Qu\u00e9bec \u00e0 Trois\u2010Rivi\u00e8res (Preprint)."},{"key":"e_1_2_1_79_2","volume-title":"Combinatorial Optimization: Networks and Matroids","author":"Lawler E. L.","year":"1976"},{"key":"e_1_2_1_80_2","doi-asserted-by":"crossref","unstructured":"E. L.Lawler \u201cOptimal Cycles in Graphs and the Minimal Cost\u2010to\u2010Time Ratio Problem\u201d Proceedings of a Conference on Periodic Optimization CISM Udine Italy 1973.","DOI":"10.1007\/978-3-7091-2652-3_3"},{"key":"e_1_2_1_81_2","unstructured":"C. D.LeddonandE.Wrathall \u201cScheduling Empty Freight Car Fleets on the Louisville and Nashville Railroad\u201d Proceedings of the Second International Symposium on the Use of Cybernetics on the Railroads 1967 pp.154\u2013158."},{"key":"e_1_2_1_82_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230110211"},{"key":"e_1_2_1_83_2","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.5.3.232"},{"key":"e_1_2_1_84_2","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1965.tb04146.x"},{"key":"e_1_2_1_85_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.11.6.972"},{"key":"e_1_2_1_86_2","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1016\/B978-0-12-141050-6.50014-3","volume-title":"Sparse Matrix Computations","author":"Magnanti T. L.","year":"1976"},{"key":"e_1_2_1_87_2","volume-title":"Studies in Operations Management","author":"Magnanti T. L.","year":"1978"},{"key":"e_1_2_1_88_2","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.22.11.1195"},{"key":"e_1_2_1_89_2","unstructured":"T.MagnantiandR.Wong \u201cAccelerating Benders Decomposition: Algorithmic Enhancements and Model Selection Criteria\u201d Oper. Res. to appear."},{"key":"e_1_2_1_90_2","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.24.15.1622"},{"key":"e_1_2_1_91_2","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.11.2.213"},{"key":"e_1_2_1_92_2","first-page":"1213","article-title":"Planning Locomotive and Caboose Distribution","volume":"4","author":"McGaughey R. S.","year":"1973","journal-title":"Rail Int."},{"key":"e_1_2_1_93_2","doi-asserted-by":"publisher","DOI":"10.1287\/moor.4.4.414"},{"key":"e_1_2_1_94_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.6.3.329"},{"key":"e_1_2_1_95_2","doi-asserted-by":"publisher","DOI":"10.1057\/jors.1979.46"},{"key":"e_1_2_1_96_2","unstructured":"E. K.Morlok W. P.Pierskalla andW. L.Vandersypen \u201cSchedule Planning and Timetable Construction for Suburban Railways\u201d Proceedings of the International Conference on Transportation Research Bruges Belgium 1974 pp.757\u2013767."},{"key":"e_1_2_1_97_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.25.3.387"},{"key":"e_1_2_1_98_2","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.3.2.164"},{"key":"e_1_2_1_99_2","volume-title":"Traffic Flow","author":"Newell G.","year":"1980"},{"key":"e_1_2_1_100_2","doi-asserted-by":"publisher","DOI":"10.1016\/0305-0548(74)90047-1"},{"key":"e_1_2_1_101_2","unstructured":"J. B.Orlin \u201cMinimizing the Number of Vehicles to Meet a Fixed Periodic Schedule: An Application of Periodic Posets\u201d Working Paper Sloan School of Management MIT July1980."},{"key":"e_1_2_1_102_2","unstructured":"J. B.Orlin \u201cMinimum Convex\u2010Cost Dynamic Network Flows\u201d Technical Report No. 172 Operations Research Center MIT March1980."},{"key":"e_1_2_1_103_2","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0120888"},{"key":"e_1_2_1_104_2","first-page":"1187","article-title":"An Optimizing Network Model for the Canadian Railways","volume":"4","author":"Petersen E. R.","year":"1973","journal-title":"Rail Int."},{"key":"e_1_2_1_105_2","doi-asserted-by":"publisher","DOI":"10.1016\/0041-1647(69)90101-4"},{"key":"e_1_2_1_106_2","doi-asserted-by":"publisher","DOI":"10.1016\/0041-1647(77)90040-5"},{"key":"e_1_2_1_107_2","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.14.2.130"},{"key":"e_1_2_1_108_2","unstructured":"H.PsaraftisandG.Tharakan \u201cA Dynamic Programming Approach to the Dial\u2010a\u2010Ride Problem: An Extension to the Multi\u2010Vehicle Case\u201d Report R79\u201339 Dept. of Civil Engineering MIT August1979."},{"key":"e_1_2_1_109_2","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.10.1.52"},{"key":"e_1_2_1_110_2","doi-asserted-by":"publisher","DOI":"10.1137\/0206041"},{"key":"e_1_2_1_111_2","unstructured":"J. L.Saha \u201cOn Some Problems in Railway Networks\u201d Ph.D. dissertation Dept. of Operations Research Case Western Reserve University 1975."},{"key":"e_1_2_1_112_2","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.4.4.383"},{"key":"e_1_2_1_113_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230110212"},{"key":"e_1_2_1_114_2","unstructured":"T.Sexton \u201cThe Single Vehicle Many to Many Routing and Scheduling Problem\u201d Ph.D. thesis State University of New York at Stony Brook Stony Brook New York 1979."},{"key":"e_1_2_1_115_2","first-page":"113","volume-title":"Annals of Discrete Mathematics\u2014No. 5 Discrete Optimization","author":"Shapiro J. F.","year":"1979"},{"key":"e_1_2_1_116_2","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.26.3.274"},{"key":"e_1_2_1_117_2","unstructured":"R.Simpson \u201cScheduling and Routing Models for Airline Systems\u201d unpublished report Flight Transportation Laboratory MIT 1969."},{"key":"e_1_2_1_118_2","doi-asserted-by":"publisher","DOI":"10.1287\/moor.3.2.89"},{"key":"e_1_2_1_119_2","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.12.3.232"},{"key":"e_1_2_1_120_2","unstructured":"W.StewartandB.Golden \u201cA Vehicle Routing Algorithm Based on Generalized Lagrange Multipliers\u201d Proceedings of the AIDS 1979 Annual Convention L. Moore K. Moore and B. Taylor Eds. New Orleans 1979 Vol. 2 pp.108\u2013110."},{"key":"e_1_2_1_121_2","first-page":"343","volume-title":"Operations Research, 1972","author":"Szpigel B.","year":"1972"},{"key":"e_1_2_1_122_2","unstructured":"J.Tounge \u201cAutomatic Allocation of Locomotives on the SNCF\u201d Proceedings of the Third International Symposium on Rail Cybernetics 1970 pp.179\u2013182."},{"key":"e_1_2_1_123_2","unstructured":"A.TruskolaskiandW.Grabowski \u201cMathematical Model of Empty\u2010Wagon Distribution inn\u2010day Planning Conditions\u201d Proceedings of the Symposium on the Use of Cybernetics on the Railways 1963 pp.104\u2013108."},{"key":"e_1_2_1_124_2","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.2.4.303"},{"key":"e_1_2_1_125_2","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.4.3.243"},{"key":"e_1_2_1_126_2","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.5.1.89"},{"key":"e_1_2_1_127_2","doi-asserted-by":"publisher","DOI":"10.1147\/sj.82.0147"},{"key":"e_1_2_1_128_2","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.11.4.359"},{"key":"e_1_2_1_129_2","unstructured":"R. T.Wong \u201cInteger Programming Formulations of the Traveling Salesman Problem\u201d Proceedings of the IEEE International Conference on Circuits and Computers 1980 pp.149\u2013152."}],"container-title":["Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fnet.3230110209","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/net.3230110209","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,11,12]],"date-time":"2023-11-12T11:41:54Z","timestamp":1699789314000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/net.3230110209"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1981,6]]},"references-count":128,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1981,6]]}},"alternative-id":["10.1002\/net.3230110209"],"URL":"https:\/\/doi.org\/10.1002\/net.3230110209","archive":["Portico"],"relation":{},"ISSN":["0028-3045","1097-0037"],"issn-type":[{"value":"0028-3045","type":"print"},{"value":"1097-0037","type":"electronic"}],"subject":[],"published":{"date-parts":[[1981,6]]}}}