## References

[BEAR 59]BEARDWOOD, J., J. H. HALTON, AND J. M. HAMMERSLEY, "The Shortest Path Through Many Points,"Proceedings of the Cambridge Philosophical Society, 55, 299-327(1959).[BELL 74]BELLMORE, M., AND S. HONG, "Transformation of Multi- Salesmen Problem to the Standard Traveling Salesman Problem,"Journal of ACM, 21, 500-504 (1974).[BELT 743]BELTRAMI, E., AND L. BODIN, "Networks and Vehicle Routing for Municipal Waste Collection,"Networks, 4 (1), 65-94 (1974).[BERM 78]BERMAN, O.,Dynamic Positioning of Mobile Servers on Net- works, Technical Report 144, MIT Operations Research Center, Cambridge, Mass., January 1978.[BODI 75]BODIN, L., "A Taxonomic Structure for Vehicle Routing and Scheduling Problems,"Computers and Urban Society, 1, 11-29 (1975).[CHRI 74]CHRISTOFIDES, M., "The Vehicle Routing Problem," NATO Conference on Combinatorial OptirnizatioD, Paris, July 1974.[CHRI 75]CHRISTOFIDES, N.,Graph Theory--An Algorithmic Approach, Academic Press, London, 1975.[CHRI 76]CHRISTOFIDES, N.,Worst-Case Analysis of a New Heuristic for the Travelling Salesman Problem, Carnegie-Mellon Uni- versity Management Sciences Research Report 388, Pitts- burgh, Pa., February 1976.[CHUR 78]CHURCH, R. L., AND R. S. GARPINKEL, "Locating an Obnox- ious Facility on a Network,"Transportation Science, 12, 107-118 (1978).[CORN 77]CORNUEJOLS, G., M. L. FISHER, AND G. L. NEMHAUSER, "Location of Bank Accounts to Optimize Float: An Analytic Study of Exact and Approximate Algorithms,"Management Science, 23, 789-810 (1977).[CROE 58]CROES, A., "A Method of Solving Travelling Salesman Prob- lems,"Operations Research, 6, 791-812 (1958).[DTJK 59]DIJKSTRA, E. W., "A Note on Two Problems in Connection with Graphs,"Numerische Mathematik, 1, 269 (1959).[EDMO 73]EDMONDS, J., AND E. JOHNSON, "Matching, Euler Tours and the Chinese Postman Problem,"Mathematical Programming5, 88-124 (1973).[EILO 71]EILON, S., C. D. T. WATsoN-GANDY, AND N. CHRISTOFIDES,Distribution Management: Mathematical Modelling and Practical Analysis, Hafner, New York, 1971.[FLOR 76}FLORIAN, M., ed.,Traffic Equilibrium Methods, Lecture Notes in Economics and Mathematical Systems, Springer-Verlag, lg76.[FLOY 62]FLOYD, R. W., "Algorithm 97--Shortest Path,"Communica- tions of ACM, 5, 345 (1962).[FRAN 69]FRANK, H., "Shortest Paths in Probabilistic Graphs,"Opera- tions Research, 17, 583-599 (1969).[FRAN 71]FRANK, H. AND I. T. FRISCH,Communication, Transmission, and Transportation Networks, Addison-Wesley, Reading, Mass., 1971.[GARF 72]GARRNKEL, R. S., AND G. L. NEMHAUSER,Integer Program- ming, Wiley, New York, 1972.[GARF 74]GARPINKEL, R. S., A. W. NEEBE, AND M. R. RAO, "An Algorithm for the M-Median Plant Location Problem,"Transportation Science, 8, 217-231 (1974).[GILL 74a]GILLETT, B., AND J. JOHNSON, "Sweep Algorithm for the Mul- tiple Depot Vehicle Dispatch Problem," presented at the ORSA/TIMS Meeting, San Juan, Puerto Rico, October 1974.[GILL 74b]GILLETT, B., AND L. MILLER, "A Heuristic Algorithm for the Vehicle Dispatch Problem,"Operations Research, 22, 340 (1974).[GOLD 76]GOLDEN, B. L., "Large-Scale Vehide Routing and Related Combinatorial Problems," Ph.D. dissertation (unpublished), MIT Operations Research Center, Cambridge, Mass., June 1976.[GOLD 77]GOLDEN, B. L., T. L. MAGNANTI, AND H. Q. NGUYEN, Im- plementing Vehicle Routing Algorithms,"Networks, 7,113- 148 (1977).[GOLD 79]GOLDEN, B. L., L. BODIN, T. DOYLE AND W. STEWART, JR., "Approximate Traveling Salesman Algorithms," presented at the San Francisco ORSA/TIMS Meeting, May 1977. Revised March 1979. (To appear inOperations Research.)[HAKI 64]HAKIMI, S. L., "Optimum Locations of Switching Centers and the Absolute Centers and Medians of a Graph,"Opera- tions Research, 12, 450 459 (1964).[HALP 78]HALPERN, J., "Finding Minimal Center-Median Convex Combination (Cent-Dian) of a Graph,"Management Science, 24 (5), 535-544 (1978).[HAND 73]HANDLER, G. Y., "Minimax Location of a Facility in an Undirected Tree Graph,"Transportation Science, 7, 287-293 (1973).[HAND 79]HANDLER, G. Y. AND P. B. MIRCHANDANI,Location on Net- works: Theory and Algorithms, The MIT Press, Cambridge, MA, 1979.[HELD 62]HELD, M., AND R. M. KARP, "A Dynamic Programming Approach to Sequencing Problems,"SIAM Review, 10, 196- 210 (1962).[HELD 71]HELD, M., AND R. M. KARP, "The Traveling Salesman Prob- lem and Minimum Spanning Trees: Part II,"Mathematical Programming, 1(1), 6-25 (1971).[JARV 75a]JARVIS, J. P., K. A. STEVENSON, AND T. R. WILLEMAIN,A Simple Procedure for the Allocation of Ambulances in Semi- rural Areas, Technical Report TR-13-75, MIT Operations Research Center, Cambridge, Mass., March 1975.[JARV 75b]JARVIS, J. P.,Optimization in Stochastic Service Systems with Distinguishable Servers, Report TR-19-75, MIT Operations Research Center, Cambridge, Mass., June 1975.[KARP 77]KARP, R. M., "Probabilistic Analysis of Partitioning Algo- rithms for the Traveling Salesman Problem,"Mathematics of Operations Research, 2, 209-224 (1977).[KNUT 76]KNUTH, D. E., "Mathematics and Computer Science: Cop- ing with Finiteness,"Science, 194 (4271), 1235-1242 (1976).[KROL 72]KROLAK, P., W. FELTS, AND J. NELSON, "A Man-Machine Approach Toward Solving the Generalized Truck-Dispatch- ing Problem,"Transportation Science, 6, 149-170 (1972).[LIN 73]LIN, S., AND B. W. KERNIGHAN, "An Effective Heuristic for the Traveling Salesman Problem,"Operations Research, 21, 498-516 (1973).[MEI 52]MEt-Ko, K. "Graphic Programming Using Odd or Even Points,"Chinese Mathematics, I (3), 237-277 (1962).[MIRC 79a]MIRCHANDANI, P. B. AND A. R. ODONI, "Locating New Pas- senger Facilities on a Transportation Network,"Transporta- tion Research, SIB, 113-122 (1979).[MIRC 79b]MIRCHANDANI, P. B. AND A. R. ODONI, "Locations of Medians on Stochastic Networks,"Transportation Science, 13, 85-97 (1979).[ODON 74]ODONI, A. R.,Location of Facilities on a Network: A Survey of Results, Technical Report TR-03-74, MIT Operations Research Center, Cambridge, Mass., 1974.[ORLO 74]ORLOFF, C., "Routing a Fleet of M Vehicles to/from a Central Facility,"Networks, 4, 147-162 (1974).[PAPA 76]PAPADIMITRIOU, C. H., "On the Complexity of Edge Travers- ing,"Journal of ACM, 23, (3), 544-554 (1976).[PAPA 77]PAPADIMITRIOU, C. H., "The Euclidean Traveling Salesman Problem Is NP-Complete,"Theoretical Computer Science,4, 237-244 (1977).[PSAR 78]PSARAFTIS, H. N., ADynamic Programming Approach to the Dial-a-Ride Problem, Report R78-34, MIT Department of Civil Engineering, Cambridge, Mass., September 1978.[REVE 70]REVELLB, C., AND R. W. SWAIN, "Central Facilities Loca- tion,"Geographical Analysis, 2 (1), 30 42 (1970).[STEI 78]STEIN, D. M., "An Asymptotic, Probabilistic Analysis of a Routing Problem,"Mathematics of Operations Research, 3 (2), 89-101 (1978).[STRI 70]STRICKER, R., "Public Sector Vehicle Routing„The Chinese Postman Problem," Ph.D. thesis (unpublished), MIT Elec- trical Engineering Department, Cambridge, Mass., 1970.[SVES 73]SVESTKA, J., AND V. HUCKFELDT, ' Computational Experience with an M-Salesmen Traveling Salesman Algorithm,"Man- agement Science, 19, 79>799 (1973).[TEIT 68]TEITZ, M. B., AND P. BART, "Heuristic Methods for Estimat- ing the Generalized Vertex Median of a Weighted Graph,"Operations Research, 16, 955-961 (1968).[IILL 72]PULLMAN, F., AND T. CAIN, "An Upper Bound Algorithm for Single and Multiple Terminal Delivery Problems,"Manage- ment Science, 18, 664-682 (1972).[TORE 71]TOREGAS, C., R. SWAIN, C. REVELLE, AND L. BERGMAN, "The Location of Emergency Service Facilities,"Operations Research, 19, 1363-1373 (1971).[WIOR 75]WIORKOWSKI, J. J., AND K. McELvAtN, "A Rapid Heuristic Algorithm for the Approximate Solution of the Traveling Salesman Problem,"Transportation Research, 9, 181-185 (1976).