——_‘ ' .\..7 IL ;, KIIIIIIIII IJW'IIIIMI I II III “mm-III!!! Iéh:'h'|'qu [WUTJI!”£I IIN IWII '. .. IIi 'Il ‘I.!!! ' ‘ IIIIIIII'IIl I “I I I. IIIIIIIIII“! ”'I'“ II! I! II III!!! ' .III II. IIIIIIIIIII I II- 'I If IIIIII IIIIII I I. I III! I!!! IIIIIIII'IIIIIII ‘2'”— :— III' M” w “—- ‘—_;—‘A—_~ “L. - .. :d .q—— ._ - .II IIIIIIIIII‘ “I”!!! II!” IIIIII $h I!” II ’I' II III!!! . I I... III. I - w A—."‘. ...w__ s 4\_w I .— ‘ - 4 q .4. - ‘_ ‘ . 'WAAM —--—.—.~. I!III III I! IIIIII'II!! III I!!!" III III II“ I I‘III! IIIII III'II IIIIIIII ’I': “I!!! H!!! !! I!!!II!!I!II I' ”I! III!!! III IIIIII II’I'I'IIJfi II II {'Itth . u o . ‘ . ‘. l I u.. N H...‘ _ - . 3.5.612..- w :5 u -4. ‘ ' O I . "’ I!!! I I. .. III IIIIII I IIIIIIIIIII IIIII' H II I I1“! ' I!!! III, “I! I"! I! III. III II "I.“ "I" " III I! III II. . IN!!!“ I ' III, In”!!! !! I II!! !'!'II ‘IIIIIJ ”I!!! '1": I!” . 3!!!” III!!! II! !IIIIIIII.IIII II.I !IIIII ( I!!!“ HM!!! III“! "2!”!!! , I IWE! I‘! I“.“'.. I hI! I I] ‘ tif;:I f “F“!!! IIIliIII 'II'II:I III! !!III!!_I!I.!III.!I " I" It!!' l. I M!!!“ (I Egg . ' J" I I‘ "‘ ”“I'N!IW I III“!!! I!!!“ II. IIIIIIIIII'I ”HI!!!“ I’IIII'III' I III II II!!! -I’III!I H l ' I! = “97-1.3.7, ~= II II .II I I I III :== III. lII'IIIII "’ 31-. 'I I!” '3!!! ’I'-'I. u. 12"!!!”‘ngIg $11.3 'I-‘I'IIII'I’ I I I“ III I3;.I“,":‘I ": III :. I}! , . .HII. » I I.! J'. gI‘w! I19. =::n;_: ZIII:?!I!.I!I'IIIII'IIIIII. ‘WII'.!I'.I'I . III: . 7;;I_.;I.,:"{‘: MIMI Ifi‘fiI IN HII"H:h 'H TIII . IIIIII I" I I ~ I‘I' IIIIf‘ . .I I I'I{:;: ‘ I III}. I. ‘ III . "' III ;~ . I I I!!! I '.: I II" . '“fII‘fI” I"I“I ‘I ' I..*rIII“II'.’I.‘.;II IIT'. .. I“.'I':“II":III;I' It . .I .’ - "'1"; I" III " .."I-.I-' “I; :~ ”III" . 1 ' II III‘I‘I‘I' I... 'I'“ . II? III . ...rI' ' IIIIIIL-II 5"I' 1" H‘MII!I H IIFIIH IH “II'! Ifiunu!WWHq! I” !‘JI I RWJWUINIVrafiv' I I""III ‘. III 'III”! III'I‘I III”. I‘l'l'I IIIIHI .I 5.! III “III" " IIIIIIU “IIIII: III/III'I :‘I.I".. IIIIII.IIIII IIJIIIIIIIII I. . ~ -..':' II. I. 8' I. '| I. .l . I I VIII. * . (III: I .-. III-n! II .IIIIII IIIII II!:IIIII I!!!“ !!-‘J.! II’!!'!I I'II II I!!! a!” A II. r Mm“: .III I, .. “I .II‘IIl‘III!!Iw. ‘I.:IIIgIIIII! '- | . .0! “FAQ '. III}! IIMIIM! ! IIIIIIIIIII.III!I-!a 35‘ "W! This is to certify that the thesis entitled DEVELOPMENT OF A MODEL FOR THE DETERMINATION OF OPTIMAL BUS GARAGE SITE SELECTION presented by THOMAS H. MAZE has been accepted towards fulfillment of the requirements for PH. D. degreein Civil Engineering I? /__:(l/L~’___1 C . "fl! (CL Major professor / /// 5119/ Date / / 0-7639 MSU RETURNING MATERIALS: Place in book drop to LIBRARIES remove this checkout from ”- your record. FINES will be charged if book is returned after the date stamped below. DEVELOPMENT OF A MODEL FOR.THE DETERMINATION OF OPTIMAL BUS GARAGE SITE SELECTION By Thomas Harold Maze A DISSERTATION Submitted to Michigan State University in partial fulfillment of the requirements for the degree of DOCTOR OF PHILOSOPHY Department of Civil Engineering 1982 ABSTRACT DEVELOPMENT OI" A MODEL FOR THE DETERMINATION OF OPTIMAL BUS GARAGE SITE SELECTION By Thomas Harold Maze A model is developed. and demonstrated for determining both the optimal bus garage locations and optimal assignment of buses to those garages. The model uses a list of candidate garage sites, the transit system's service and operational characteristics and the characteristics of the regional highway system as input. As output it produces the optimal number, sizes and locations of bus garage additions or changes. The model considers garage operating and garage construction costs and the costs of deadheading and driver relief under separate operating schedules for morning, all-day, and evening assignments on weekdays, Sundays , and Saturdays . The model devloped is computationally feasible. Initially the problem is formulated as a discrete solution-space fixed-charge facility location problem. The fixed charge problem is formulated as a mixed integer program. However, because of the difficulty involved in solving a large-scale problem with a general purpose mixed-integer program, the problem is solved by a special purpose branch-and-bound process. This process utilizes an efficient sequence of classical transportation problems plus a number of easy-to-use side calculations which rule out a wide variety of potential computations. Consequently the model may be applied to a relatively complex system at the cost of a relatively modest amount of computer use. The model is demonstrated in the context of a Detroit metropolitan area case study. The manner in which the model may be used to include judgemental inputs and perform sensitivity analyses is also described. ACKNOWLEDGEMENTS I would like to thank my comittee chairman, Dr. William Taylor, Professor and Chairman of Civil Engineering, for his understanding and help during the completion of my doctoral work. I am also quite grate- ful for Dr. Taylor's advice and excellent guidance in the preparation of this dissertation. The constant support of my committee member, Dr. Tapan Datta, through the completion of my doctoral work and his guidance in preparation of this dissertation, is also gratefully acknowledged. The timely support of my other other committee members, Dr. James Brogan and Dr. Robert Bushnell, was very instrumental in the completion of my dissertation and I am indebted to both for their help and guidance. I would also like to give recognition to the financial support made available to me through a grant to Wayne State University, Department of Civil Engineering, from the Urban Mass Transportation Administration, United States Department of Transportation (UMTA Grant No. MPH-0004). These funds aided greatly in the completion of this dissertation. Also, the work of others, Dr. Snehamay Khasnabis, Mr. Mehmet Kutsal, Ms. Pamela Cummings, and Ms. Jennifer Thomas, involved in the research con- ducted for the Urban Mass Transportation Administration, has aided in the swift completion of this dissertation. Lastly, but by no means least, I would like to thank my friends for their support during my progress on this dissertation. Special thanks go to my wife, Leslie, who may not have always understood why anyone would want to go through the trials and tribulations of a doctoral program, but who supported my endeavor completely. ii TABLE OF CONTENTS LIST OF TABLES LIST OF FIGURES CHAPTER 1, INTRODUCTION 1-1 Importance of Problem 1-2 Research Objectives 1-3 Dissertation Organization CHAPTER 2, LITERATURE REVIEW 2-1 Locational Models 2-2 Bus Garage Planning 2-3 Literature Review Conclusions CHAPTER 3, PROBLEM STATEMENT CHAPTER 4, METHODOLOGY 4-1 Theoretical Model Formulation 4-2 Practical Implications of Theoretical Model Formulation . 4-3 Summary CHAPTER 5, CASE STUDY 5-1 Site Identification 5-2 Cost Parameter Generation 5-3 System Characterization iii 10 12 13 31 56 S8 61 62 83 95 96 97 101 111 TABLE OF CONTENTS (continued) Page 5-4 Model Application 113 5-5 Sensitivity Analysis 131 5-6 Summary 141 CHAPTER 6, FINDINGS, CONCLUSIONS AND RECOMMENDATIONS 143 6-1 Findings 143 6-2 Conclusions 146 6-3 Recommendations 149 REFERENCES 152 APPENDIX A, AUTOMATED DATA CODING FOR DETROIT CASE STUDY 157 APPENDIX B, GLOSSARY OF TERMS 162 iv Table 2-1 2-2 LIST OF TABLES MTC Total Annualized Cost MTC Total Annualized Cost Example Non-Productive Transportation Cost Example Optimal Mixed Integer Programming Solution Example Assignment Solved as a Transportation Problem Application of Delta Rule to the Sample Problem Application of Omega Rule to the Sample Problem Examples of Pullout and Pullin Assignments Examples of Deadhead Time and Distance Costs Examples of Non-Productive Transportation Costs Existing Detroit Garages Transportation Problem Including All Sites Results of Omega Decision Rule Detroit Bus Garage Location-Allocation Options Page 50 52 81 82 87 91 91 106 106 107 111 117 124-125 133 Figgre 4-1 4-3 4-4 4.5 LIST OF FIGURES Metropolitan Transit Commission’s Garage Operating Cost Versus Garage Size AC Transit's Garage Operating Cost Versus Garage Size Metropolitan Transit Commission's Garage Construction Cost Versus Garage Size AC Transit's Garage Construction Cost Versus Garage Size Branch and Bound Tree of Sample Problem Detroit Site Map Example Garage Layout Flow Chart of Methodology Branch and Bound Tree of Case Study Total Cost Versus Non-Productive Transportation Cost Total Cost Versus Number of Site Flowchart of Data Coding Methodology vi 69 70 92 98 105 114 127 134 140 159 CHAPTER 1 INTRODUCTION The location and sizing of bus garage additions is a common problem for operators of expanding transit systems or systems modern- izing their capital facilities. Because of the significant costs of constructing and operating garages and the costs of bus travel between the garage and bus routes, garage location and size decisions have important implications on the efficiency of the transit system. Methods currently used to analyze the implications of these decisions are quite elementary. Solution techniques developed for similar problems in other fields use sophisticated models that account for the complex relationships between facility location and size and previous study has shown that significant savings can be realized if more sophisticated solution techniques are used to aid in locating and sizing bus garage additions or changes (1). Hence, the need to devel- op a state-of-the-art approach is evident. The problem of locating and sizing garages within a transit system requires the simultaneous consideration of both the location of garages and the allocation of buses to garages located. For each combination of potential garage sites, buses must be optimally-allo- cated to each individual site while still meeting system constraints and garage capacity limits. At the same time, all potential com- binations of garage sites must be compared to find a minimum cost garage system. Typically, large scale transit agencies operate 1,000 or more buses (each of which may have more than one route assignment) and there may exist several existing and potential garage sites (for example, between 10 and 30 sites). Hence, the problem of optimally locating and sizing bus garages is a complex problem because 1) garage locations and bus allocations must be treated simultaneously, and 2) there usually are a large number of potential combinations that must be considered. The objective of this research is to develop and demonstrate a methodology which can be used to select the minimum cost garage con- figuration and. test the cost implications of other garage options. The methodology is developed as a two step process. First, the rela- tionships between costs related to garage location and size are struc- tured into one mathematic model. Second, the structure of the given model is exploited to efficiently reach a minimum cost solution as well as test the cost implications of other options. The model devel- oped uses the regional transit system's service and operational char- acteristics and the characteristics of the regional highway transpor- tation system as input. As output, the model determines the optimal locations and sizes of garage additions as well as the cost implica- tion of other garage options, under the conditions characterized in the problem structure. The model is tested and its ability to provide concise and accurate answers demonstrated on a Detroit metropolitan area case study. 1-1 Importance of the Research Although determining the locations and sizes of new bus garage 3 additions or garage changes is a problem faced by expanding transit agencies, little independent research has been devoted to this (1, p. 1). The importance of research on this topic and in the development of accurate techniques to aid in sizing and locating garages lies in; 1) the costs attributable to bus garages, and 2) the controversy that often surrounds garage location decisions. Garage-Related Costs Costs related to the components of the garaging system are quite significant. These costs can be divided into three categories: 1) non-productive transportation costs, 2) garage operating costs, and 3) garage construction costs. Each of these costs is described in the following pages, with examples of their magnitude and variance with alternative garage system parameters. Non-Productive Transportation Costs. The costs of deadheading buses to and from their work assignments and of providing relief for drivers are dependent on the locations of garages with respect to the bus routes each garage services, and on the characteristics of the highway network surrounding the garage. Non-productive transportation costs per vehicle housed at a garage have been shown to increase as garages increase in size and draw vehicles from more distant routes (diseconomies of scale)(2). Also, studies of non-productive transpor- tation costs have shown that these costs can vary significantly as a function of the location of a garage in relation to the transit net- work and with respect to other garages(1,3,4). Thus, non-productive transportation costs are a function of the capacity allocated to the garages and the location of garages with respect to routes. The magnitude of non-productive transportation costs can be quite consequential. For instance, Bi-State Development Agency (the St. Louis metropolitan area operator) projected its 1985 non-productive transportation costs to average almost $9,000 per year per bus (4, p. 9). Considering that Bi-State operates approximately 1,200 vehicles, its 1985 annual non-productive transportation costs will be approxi- mately $10 million. A study of the Washington, D.C. metropolitan area operator estimated that approximately ten percent of annual operating costs are consumed by non-productive transportation (5, p. 39). Presumably, non-productive transportation costs account for even greater shares of operating costs in more sparse transit networks than that of Washington, D.C. GaraEOperating Costs. The cost per vehicle of servicing and maintaining buses in a garage has been shown to be sensitive to the number of buses stored in a garage (3, pp. 142-143; 6, pp. 13-15). When more vehicles are stored in a facility, labor and equipment can be more efficiently utilized (economies of scale). For example, a study of A.C. Transit (the East San Francisco Bay Area operator) found that their costs for operating a garage dropped from $14,570 to $13,530 per bus per year when the size of a garage increased from 150 vehicles to 300 (3, p. 142). Although A.C. Transit operates only 760 -buses and 4 garages, its total cost of operating its garages is ap- proximately $10.5 million per year. Operating costs can be much more for operators like the Philadelphia or Chicago systems, which have 10 and 12 garages respectively (6, p. 3). The magnitude of the annual costs of garage operation indicates the importance of this cost com- ponent. Garage Construction Costs. Unlike the other costs related to 5 garages, the costs of building the garage and of equipment installa- tion for a garage are fixed costs. Once a decision is made to con- struct a facility, construction costs are expended for the life of the structure. With larger facilities more efficient utilization can be made of storage and repair space, and the total cost per vehicle decreases as size increases (economies of scale). For example, the A.C. Transit study estimated that construction cost per bus dropped from $38,570 to $30,460 when garage size was increased from 150 vehi- cles to 300 vehicles (3, p. 142). Because a typical size garage for ' 250 vehicles has an initial cost of approximately $10 million, con- struction costs of garage additions are quite important. Relationship between Costs. Non-productive transportation costs, garage operating costs, and garage construction costs are all depend- ent on garage planning decisions. Although they can be estimated separately, their interdependence locks these three cost components together in determining the cost implications of bus garage changes or additions. Because each represents an important cost component by itself, the aggregate cost implication is even more important. In all but one known garage planning study, each of these costs is considered separately.* Often, the investigators select a desir- able size for a garage addition, thus fixing the allocation of vehi- cles to all the facilities in the system, and later look for an ef- ficient location. By solving the problem in two steps, the analyst has really solved two discrete suboptimization problems which when combined may not lead to a global optimization. The reason for not *A description of the process used by many operators is described in the state-of-the-practice review. 6 considering the total optimizations of all costs simultaneously is that this presents a very complex problem. There is evidence that a comprehensive effort which considers all related costs simultaneously could permit significant cost savings (1,7). In a 1976 study by the Metropolitan Transit Commission (the Minneapolis-St. Paul operator), a simplified but comprehensive study of the costs related to a limited number of combinations of locations and capacity allocations managed to trim $1.5 million dollars per year (1976 dollars) from the previously planned 1985 system (1, p. 22; 7, pp. 34-36). The results of the MetrOpolitan Transit Conission's limited study in 1976 demonstrate the need to develop more comprehen- sive, accurate and exhaustive methods of finding optimal garage loca- tions and capacity allocations. The Public Sensitivity of Gagge Flaming Decisions Locating and sizing bus garage additions or changes is often one of the more controversial aspects of transit planning. Bus garages often occupy prime industrial sites but, because bus operators are public agencies, they do not enhance the local tax base. Further, the movement of buses into and out of a garage often has a disruptive effect on the flow of adjacent arterials. For these reasons and others, the public or local municipalities have often stopped bus garage additions slated to be built in their comunities. When dealing with controversial and sensitive issues it is a difficult task to make trade-offs between the concerns of one comun- ity and the regional interests of the transit operator even when accurate cost information on both sides is available. However, be- cause transit planners have no accurate means of measuring the cost 7 penalty of not locating at a desirable site, it is impossible to make these kinds of trade-offs. This makes it difficult for operators to justify locating a garage at any site that might be publically chal- lenged. A An example of the potential problems of trying to build on a con- troversial site is the action taken by the Metropolitan Transit Com- mission in 1974-75 (prior to its 1976 study) (7, pp. 6-8). After conducting a state-of-the-art garage site selection analysis, the Me- tropolitan Transit Comission bought a $1.35 million property previ- ously occupied by a drive-in movie. After the operator had invested approximately $580,000 in architectural and engineering plans and environmental impact statements, the local municipality began legal action to stop construction. Without accurate evidence of an oper- ating cost penalty of not occupying the planned site, the operator had no choice but to look for a (site elsewhere and forfeit the metal- ready sunk into its plans. Although the experience of the Metro- politan Transit Commission is uncommon, attempts to locate garages are frequently thwarted by local opposition; hence the need for accurate information on the penalty of changing a garage location. 1-2 Research Objectives The objective of this research is to develop a model which can select optimal bus garage locations and garage capacity allocations from an array of feasible garage sites. Problems like the one ad- dressed here are known as location-allocation problems (8, p. 233). This general class of problems is different from other types of loca- tional problems because location cannot be treated independently of 8 other considerations. This type of problem recognizes that capacity, allocation and locations of all facilities are interdependent, and that the determination of the locations and capacities of all facili- ties must be considered simultaneously in the system optimization model. However, the various costs related to the decision variables must be estimated before the optimization process can be developed. Therefore, the methodology developed uses two sequential steps: first, estimation of costs, and, next, the optimization. Once the method- ology is developed, a case study is performed using Detroit metropol- itan area transit system data to test the model and provide an example of its use. Cost Estimations In representing the system, it is important to accurately esti- mate the related costs. This does not present a problem when con- sidering garage operating and construction costs. Historical infor- mation on these costs can be used to prepare a standard engineering economy model across realistic ranges of garage capacities. However, non-productive transportation costs have unique values for each com- bination of locations and allocation of buses to garages. Thus, non-productive transportation costs for non-existent garage systems cannot be obtained directly from hdstorical information. Each possi- ble combination of locations and bus allocations will have a unique non-productive transportation cost. To create a realistic representation of non-productive transpor- tation costs, the cost model must symbolically represent actual time and distance costs through the highway network. Thus, a specific objective of the cost model is to estimate non-productive travel costs 9 through a highway system simulation rather than use approximations such as straight-line distance cost functions or rectilinear distance cost functions. The results of the non-productive transportation cost model and the operating and construction cost models will be used as cost parameter values in the optimization. Optimization The criteria used to select the optimization methodology will include: 1. Applicability of the optimization methodology to the nature and shape of the cost functions (i.e., linear or nonlinear costs). 4 2. The efficiency with which the analysis can be performed. 3. The adaptability of the model to different types of garage system constraints and planning criteria. Examples of these include the constraining of garage additions to a maximum and/or a minimum capacity, or the assessment of a penalty for occupying a feasible but controversial garage site. The specific objective of this portion of the research is the identification of an optimization technique that is best suited to the problem, and a description of the mathematical program to be used in the case study. Special care is taken to ensure that the mathematical program is efficient. Case Study To demonstrate the methodology and to provide an example of the results that can be expected from its use requires the application of the model to an actual transit system. The results of the application of the model to a specific regional transit system results in specific 10 information (for example, locations and capacities) related to the subject area. The case study considers the transit networks of the two Detroit metropolitan transit operators, the Southeastern Michigan Transporta- tion Authority (SEMTA) and the Detroit Department of Transportation (D-DOT) (9). The network includes service additions scheduled through 1985. By including future service, more buses are assigned to the network than there are currently garage spaces; hence, requiring the location and sizing of at least one addition and/or expansion of an existing facility. Further, by merging both operators and including planned service, the resulting number of buses considered is of suf- ficient magnitude to demonstrate the capability of the model even when used by'a large-scale operator. The specific objectives of the case study are to test the applic- ability of the model to an actual transit network, to provide an example of the model’s use, and to demonstrate the capability of the model to deal with a large-scale transit system. The results will be compared with existing and planned Detroit area transit system im- provements . 1-3 Dissertation Organization The remainder of this dissertation is divided into five chapters. Chapter 2 is a literature review divided into two sections that cover 1) generalized location models used to solve facility location-allo- cation problems and, 2) methodologies used in the past to plan the locations of garage additions or changes. Chapter 3 is the problem statement, and Chapter 4 covers the methodology. Chapter 5 presents 11 the case study. Chapter 6 presents a summary of the findings of the research, conclusions and recommendations. CHAPTER 2 LITERATURE REVIEW There are two bodies of literature relevant to this research. The first is the methodological literature related to location-alloca- tion modeling. The second is the bus garage planning literature. The reason for studying the literature is to obtain an understanding of how this research can build on past work done in related areas, how it relates to current. needs for flmproved garage location-allocation methodologies, and how this research contributes to the state-of-the- art. The first section of the literature review is a survey of the state-of-the-art of location models relevant to this research. Such a review allows an acknowledgement of the insights contributed by others studying similar problems and yields an understanding of the evolution of location modeling. The second section of the literature review is a survey of the state-of-the-practice for planning bus garages. The purposes of this . review are twofold. The first purpose is to describe the practical problems faced by local transit operators when planning garage facili- ties. Knowledge of their concerns and constraints helps in construct- ing the model such that it is generally suited to operators' needs. The second purpose is to demonstrate that there is a deficiency in the state-of-the-practice and to establish that the development of a model 12 13 to determine optimal garage location-allocations will be useful to op- erators faced with garage planning decisions. 2-1 Location Models The study of location models has focused on determining a loca- tion for a facility that will minimize the cost of distributing to customers whatever is produced or stored at that facility. The facil- ity may be a warehouse supplying materials to industrial customers, or a service center such as a hospital providing health care to the surrounding community. Regardless of the exact nature of the goods or service, the objective of the location model is to minimize operation and distribution costs. Thus, because the exact type of distribution center is unimportant to generalized location models, all distribution centers will be considered "facilities," whether they are bus garages, hospitals, warehouses or other installations. The cost of the distribution can be broken into two portions: 1) the cost of operating the facility, and 2) the cost of delivery to customers. These costs are discussed in the following subsections. Facility Costs. The cost of operating facilities can be divided into fixed and variable costs. Fixed costs include the costs that remain constant regardless of the output of the facility, such as the cost of the building, equipment, property tax, administration, etc. Variable costs are those that increase with the output of the facil- ity, such as the cost of electricity and other services, labor to handle output, inventories, maintenance, etc. The combination of fixed and variable costs defines the total cost of a facility, as expressed in Equation (2-1). The costs for all facilities in the 14 system are expressed in Equation (2-2). Fi = a1 + fi(Wi) (2-1) where: ai fixed costs for facility i (i = l,2,...,m) f(Wi) variable costs which depend on the output Vi m F = 2 Pi (2-2) i=1 If all facilities in the system have the same fixed costs, then the system-wide cost is expressed in Equation (2-3). n F = ms + 2 f.(W.) (2-3) 1 1 i=1 The output may be a function of inventory, material processed, storage space required, or other measures of production, plus the carrying charges of stock levels. The measure of output used should be that measure which is most highly correlated with cost (10, p. 5). Delivery Costs. A general expression of the costs of delivery to the customer from the facility is shown in Equation (2-4). Hi = O}: a wij dij (2-4) Where: a * delivery cost per unit amount of space distance and/or time distance wij = amount delivered from facility i to customer j(j=1,2,...,n) dij = the distance from facility i to customer j(j = l,2,...,n) The total system delivery cost is expressed in Equation (2-5). To ensure that all demand is satisfied, the problem is constrained to the conditions expressed in Equations (2-6) and (2-7). H = B. (2-5) 1 "Ma 1 l 15 n w. = z w.. -6 1 i=1 ‘1 (2 ) m w = z wi (2-6) i=1 Where: W’8 the total output of all facilities in the system Thus, the object of location models is to minimize the total cost of distribution, that is, to find the minimum of the total cost, C, as expressed in Equation (2-8). Minimize c = r + a (2-8) The facilities location problem is not just a single problem. As Eilon et al. note, "The number of depots in the system, their respec- tive size, their locations, the allocations of customers to depots -- all these are interrelated problems which need to be examined closely" (10, p. 7). In the following state-of-the-art review, the many ap- proaches taken to account for all these interrelated system parameters by other researchers when studying problems similar to the bus garage location problem are described and critiqued. Location models can be divided into single facility location models and multiple facility location models. These two groups can be further divided into models that consider all points to be potential facility locations (continuous solution sets) and models that consider only specific points to be potential locations for facilities (dis- crete solution sets). Although many of these different kinds of models provide interesting solutions to complicated problems, only multifacility location models with discrete solution sets are relevant to the problem of locating and sizing bus garages.* *For a discussion of other types of location models see Maze et al.(11). 16 The problem addressed here involves multifacility location models because many transit operators maintain multiple garages. For exam- ple, the operators in Chicago, Philidelphia, Detroit, St. Louis, Oakland, Milwaukee and Minneapolis-St. Paul maintain 12, 10, 7, 6, S, S, 4 and 5 bus storage garages, respectively (6,7,4,3,12,7). Further, the single facility location problem is a special case of the more difficult multifacility location problem. The reason for restricting the review to discrete solution set models is because there are normally only a few points in an urban area that are available for locating bus garages. Bus garages require 5-14 acres of land, they must be located in an area of similar land use, and they should not be located at points that are great distances from some portion of the transit network. These characteristics greatly constrain the number of available location for a garage. For example, garage studies that used a discrete location approach in Louisville, Oakland, St. Louis and Minneapolis were only able to identify 8, 16, 11 and 7 possible sites, respectively (13,3,4,7). Further, continuous solution sets can only treat transportation costs as a monotonic function of distance (10, p. 13-14). Transportation cost through an urban area varies with the expressways, highways, arterials, and streets along the path of travel, and may vary greatly from one path to the next and between points along the path. Thus it is not realistic to assume that transportation cost is a monotonic function of distance. Hence, the multifacility discrete solution set approach is more appropriate. Multifacility Discrete Solution Set Models Researchers studying multifacility discrete solution set models have developed models that exclude and include facility costs. Those models that exclude facility costs are known as covering problems. Since facility costs (garage operating and construction costs) are an important part of the garage location problem; these models are not relevant to the garage location problem and only total cost models are described. Methods to solve multifacility locational problems with discrete solution sets that consider facility costs and delivery costs were first researched in the late 1950's. In a-1958 paper, Baumol and Wolfe describe a heuristic approach used to locate warehouses given flows of goods from factories to warehouses to retailers, as shown below ( l4) . C 1*“:qu Warehouse Retailer i J j k The authors start their analysis of the problem of locating ware- houses by noting that if they were only concerned with delivery costs between the factories and warehouses and between the warehouses and the retailers, the problem could be solved as a basic transportation problem using a linear programming solution technique.* However, because of fixed costs, facility costs (warehouse costs) are discon- tinuous at zero capacity, and hence the problem cannot be solved as a basic transportation problem if facility costs are included. Thus, the authors were faced with the following non-linear problem: , 'I'For examples of the formulation of a transportation problem see Wag- ner or Hillier and Lieberman (15, pp. 166-170; 16, pp. 119-129). 17 18 m n n Minimize f(xijk) 8 1:1 1:1 51 cijk(xijk) 'I' jil szj n + 1:1 V.1 6(21) 3 ‘1 Subject to jil til xijk = Q1 m n 1:1 3:1 311k ' 3k Where: x1th = the quantity shipped from factory i(i=1,2, . . . ,m), through warehouse j(j=1,2,. .. ,n), to retailer loca- tion k(k=1,2, . . . ,q) cijk(xijk) = the cost of this shipment 1' q 2. = I I X. 11: = the quantity shipped through warehouse j 3 i=1 k=1 (j=1,2,...,n) wj = the warehouse variable cost per unit shipped through warehouse j(j=1,2,...,n) 0; if Zj = O 5(Zj)= 1; if Zj > 0 V1 = the fixed costs of warehouse j (j=1,2,...,n) Q1 = the quantity shipped from factory i (i=1,2,...,n) Sk = The quantity demanded by retailer k (k=1,2,...,q) Baumol and Wolfe's method searches for a solution to the non- linear problem in a two-stage iterative heuristic process. In the initial stage values are calculated for the minimum total cost path along the link between the factory and warehouse cij’ and between the warehouse and the retailer, djk' The initial cost along the minimum cost path, Cit, is expressed in Equation (2-9), where j ik denotes the 19 minimum cost path from factory i to retailer k through warehouse j (the warehouse routing criterion) and superscripts indicate the stage of the solution process. 0 _ . _ o C. - Min.(cij + djk) - (cij + (1. 1k J k) , (2-9) ik Jik The initial stage (stage 0) uses the initial minimum cost path costs, ignoring the warehouse costs, to solve the basic transportation problem min 2:“ 23:1 cgk Xik' This solution is used as the start- ing point for the second stage. From the warehouse loadings computed in any stage n-l, (2':==1 2:” 22:), the marginal warehouse costs are computed with Equation (2-10). The new costs to be used in the transportation problem are calculated for stage n using Equation (2-11). This process iterates until the loadings at the warehouses converge to a constant value. I q _ aw ( z z xgkl) J -. .. An} = ;‘1 :‘1 all ikejgkl (2-10) 3( z z xgil) i=1 k=1 n _ ‘ _ cik - minj (ci j + dik) + ij (2 11) Balinski and Mills developed a heuristic approach similar to Baumol and Wolfe's approach, to solve warehouse location problems (17). They also formulate their problem so that it can be solved as a basic transportation problem. However, Balinski and Mills only consider single factory cases. Stated in the same notation as the Baumol and Wolfe's approach, the problem Balinski and Mills attempted to solve is as follows:* *Notice that the factory subscript i has been deleted. This is be- cause Balinski and Mills characterize their problem with one only factory. n q Minimizeflx )=Z ZCH(X)+2W..Z Jk jgl F1 jk jk j_1 JJ‘ +2V.6(Zj) Fl“ ‘1 Subject to Z X.k 5 G for all j(j=1,2,...,n) 1=k J j Z X 2 8k for all k(k=1, 2, .,q) i=1 3" Where: Gj = the capacity of warehouse In theory, an optimal solution to this problem can be found by using an integer program. However, as Balinski and Mills point out, given the capacity of computers at the time. of their work (the late 1950's), even a small problem could not be handled (17, p. 6). Be- cause of computing limitations at the time, they developed an approx- imation technique. Their method substitutes the average cost of operating a facility at high levels of utilization. This is formu- lated in the following way: 2. = 14.2. + V. 5 2. f 11 ' °=1,2,..., Hj( J) J J J (J) or a JCJ m) I L t . = ' G. 2 2. e eJ m1.n(J,j=:1 J) R l H. 2. ’th H. . ep ace J( J) m. J(eJ)/ej This means that the warehouse cost function (fixed and variable costs) for each warehouse is approximated by the average facility cost when it is operating at a high utilization level: either the capacity of the warehouse, Gj’ or the total flow of comodities passing through the system . 21 With the use of this approximation, the problem becomes linear. Thus, the problem can now be solved as a basic transportation problem. The objective of the transportation problem is stated in Equation (2-12), which is still subject to the constraints stated in the orig- inal problem. . n q Minimize f(xjk) = jil til (Cjk + Hj(ej)/ej)Xjk (2-12) The optimal solution to the linear problem represents the lower bound of the total system cost. The allocation of flows to warehouses determined by solving Equation (2-11) is then.placed back in the orig- inal integer programing problem, and the authors prove that given that allocation, the resulting system cost represents the upper bound of the optimal solution. Kuehn and Hamburger critiqued both Baumol and Wolfe's and Balin- ski and Mills' heuristics approaches (19). In their critique of Baumol and Wolfe's algorithm, Kuehn and Hamburger point out that this heuristic approach may be appropriate for certain types of problems but does not take into account the fixed portion of warehouse operat- ing costs (19, p. 661). To prove the inappropriateness of the model when used on fixed cost problems, Kuehn and Hamburger solved the problem Baumol and Wolfe had used as an example of their technique, and found a lower cost solution than had Baumol and Wolfe (19, p. 661). Kuehn and Humburger also apply Balinski and Mills' method to the same problem and find that Balinski and Mills' lower bound of the total cost is 19 percent below the optimal value, and their upper bound 22 percent above (19, p. 663). Kuehn and Hamburger developed a heuristic of their own to solve 22 the same problem addressed by Baumol and Wolfe and by Balinski and Mills (19). The algorithm developed by Kuehn and Hamburger is divided into two portions: a main program which locates warehouses at avail- able sites one at a time until no additional warehouses can be added without increasing cost, and a bump-and-shift routine which attempts to improve the initial solution by removing and interchanging ware- house locations. Kuehn and Hamburger postulate three principles of optimal locations which they use to set up their algorithm (19, pp. 665-646): 1. Good locations for regional warehouses will be at or near concentrations of demand. Therefore, only the largest de- mand points need to be considered as potential warehouse lo- cations. 2. A sub-optimal warehouse system can be developed by adding one warehouse at a time. Thus, at each stage of the algor- ithm, the warehouse that offers the biggest improvement should be chosen. The process is to be terminated when no improvement can be made. 3. At each stage, only a subset of the potential locations need be considered for detailed evaluation. Choose as members of this subset those locations which offer the greatest local improvement. The bump-and-shift routine is designed to check the current solu- tion and search for an improved solution in two ways: 1) any warehouse which is no longer economical, because some of its customers have been shifted to a recently assigned warehouse, is eliminated (bumped) and the remaining customers reassigned, and 2) attempts are made to shift 23 each remaining site with other sites in the territory it serves. The speed with which this approach works is dependent on the closeness of the initial sub-optimal solution to the approximate optimal solution. When the bump-and-shift routine takes over the sub-optimal solution, it is merely an enumeration process of likely improvements. Although the last stage of Kuehn and Hamburger's algorithm uses a brute force enumeration approach, the means that they take to get to their enum- eration stage has proven to be efficient and, thus, they have been able to approximate optimal solutions efficiently. The kind of problem addressed by Kuehn and Hamburger has been labeled the "fixed-charge problem." In the early to mid 1960's, others worked on approximations of optimal solutions to fixed-charge problems. Some examples are the work of Balinski, Cooper and Drebes, Manne, and Feldman, Lehren, and Ray (20)(21)(22)(23). A pure optimi-' zation was developed by Murty in the mid 1960's (24). Murty's ap- proach was to solve the problem without fixed charges as a linear program. The solution would serve as a lower bound to the fixed- charge problem, and then Murty's algorithm would systematically search among extreme points adjacent to the lower bound for an optimal solu- tion to the fixed charge problem. But, as Gray indicates, Murty's algorithm has never been tested on an actual problem (18, p.3). Finally, when developing a method to check' the heuristic of Feldman, et al., Efroymson and Ray developed more than just a method to verify the results of the other paper, they developed an applicable pure optimization to solve the fixed charge problem (25). I Before Efroymson and Ray published their work, basic integer programs used branch-and-bound techniques that were time consuming. 24 Because of the state of the art of integer programming at that time, large problems were impossible to solve. To overcome this problem they formulated the fixed charge problem with care and introduced sim- plifications so they could make use of the structure of the problem. Efroymson and Ray's objective was to locate facilities (plants) with respect to customers and without the intermediate concern of warehouse locations. Using Efroymson and Ray's notation, the problem that was solved is the following: I! Minimizez= 2 z c. x..+ 21‘. Y. i=1 j=1 ‘1 ‘3 i=1 1 1 Subject to I X.. 1 for all j j = 1, 2, ..., n all isnj lJ 0 S 2 X . S n1 Yi for all i i = 1, 2, ..., m all jePi . 0 Y. ={:or for all i = 1, 2, ..., m i 1 Where: * n.j = the set of indices of those plants that can supply customer j(j = 1, 2, ..., n) P. = the set of indices of those customers that can be supplied from plants i (i = 1, 2, ..., m) n. = the number of elements in P1 * Note that variables are defined as those that can rather than those that do or will. This means that the variable relates to the maximum quantity possible that still remains unassigned. 25 the fraction of customer j's total demand quantity shipped X.. 1J from.plant i (i = 1, 2, ..., m) Cij xij = the cost of the shipments from plant i to customer j F. 1 the fixed costs associated with plant i (i = 1, 2,..., m)*. The three constraints cause: 1. All demands to be met, 2. All plants to supply zero customers if Y = 0 and as many as i n customers, 1 3. A plant to either be open Y = 1, or closed, Y1 = 0. i If this problem is solved as a mixed integer program, the solu- tion process will first start by solving the problem without integer requirements. Then, a branch-and-bound process begins which assigns each variable that is required to be an integer the value of the nearest larger integer and solves the linear program again. Picking the solution with the lower cost, it branches from that node and the other node becomes a terminal node. Efroymson and Ray assert that, at any state of the branch-and-bound process, denoting {x0} {K1} the set of indices of Y1 fixed at 1 the set of indices of Y1 fixed at 0 {Xi} = the set of indices of the remaining Yi’ the optimal solution of the linear programming problem is: x = { 1 if cij + gi/ni = min(CkJ. + gk/nk) k 8 {K1 U K2} i1 0 otherwise Y. = I X ./n. 1 jePi iJ 1 *The problem is stated such that only fixed facility costs are included. Variable facility costs could be included by adding them to the trans- portation costs. 26 8 ={Fk;ifke{K2} k 0 ; if k 8 {II} To show that this is the optimal solution to the linear program note that for isK , 2 1!.an 2 Y. which implies that in the optimal solu- Jfipi 1 1 i n.Y. or 2 Xu/ni = Yi‘ i' 11 . J 389, tion the equality will hold; that is Z X 181:, Efroymson and Ray’s method makes each node easy to evaluate, at least by computer. However, because the number of customers served by any plant is much smaller than the potential number of customers (n1), the amount of fixed charges absorbed by the plant at any iteration (gi/ni) will be small and the program will tend to run long. Efroym- son and Ray designed three simplifications to streamline the process: 1. Find the least net savings of opening a new plant. If the savings is positive, then the plant should be opened. 2. If it is cheapest to ship to a given customer from a plant that is already open, then ship to the customer from that plant. 3. Find the greatest net savings that could be made from open- ing a plant. If this value is negative, the plant should not be opened. These three physical principles (simplifications) are followed over and over until no improvement can be found. Then the branch-and- bound process is performed one last time and the solution is run through the three simplications as a check. Efroymson and Ray go on to adapt their methodology to three special cases of fixed charge problems, and conclude by indicating that they have been able to solve a 50-plant, ZOO-customer problem with a modest amount of computing 27 time.* However, the approach does have the flaw that with its use it is impossible to treat problems with an upper bound on the capacity of any or all plants. Efroymson and Ray’s simplifications were an ingenious way of ex- ploiting the structure of the problem so that it could be solved by the weak mathematical programing codes that were available at the time. It was simply a matter of time, however, until more powerful codes became available that could handle large mixed integer programs and allow a direct solution to the problem. But in the meantime a great many shortcuts were devised to fortify Efroymson and Ray's approach. For instance, after pointing out that Efroymson and Ray's method was unable to cope with facility capacity limits, Gray devel- oped a technique that could treat capacitated facilities (18). Gray realized that if be solved the minimization problem address- ed by Efroymson and Ray without integer restrictions, he would get a solution, 2, which had a lower value than the solution with integer restrictions, Z. Further, for any problem the lower bound of the delivery cost portion (21:1 X. n where Item1 U 1(2)) will be j=1cij Xij equal to the basic transportation problem solution (T[{I(1 U K2}] = min 22:1 Z§e1 cijxij k (where Yk = 1 or Yk = O), the value of the solution satisfies Equation where ke{K1 U K2}).** Thus, given the optimal Y (2-13). Because 222, the inequality in Equation (2-14) results when the two are combined and provides a constraint on the optimal Yk' * Ten minutes on an IBM 7094 computer. **The notation for the sets {K}, {K1} and {K2} are the same as those used in the presentation of E roymsoln and Ray 3 approach. 28 m Z 2 1:1 Fi Yi + T[{K1 U K2” k 8 {K1 U K2} (2-13) I - 1:1 Pi Y1 S 2 - T[{K1 U K2}] 1: 8 {K1 U K2} (2-14) If Equation (2-14) will be violated by setting Yk clearly Yk must be set to zero for the integer solution, 2, to im- = 1, k 6 {K2}, then prove. At approximately the same time as Gray, Khumawala developed simple decision rules to aid in quickly evaluating whether to include or exclude sites as candidate facility locations (27). These rules are quite similar in nature to Grey's approach but more simplistic in application. The decision rules are: 1. If the least possible increase in transportation cost due to not opening a facility is greater than its fixed charge, then it should remain open (delta rule). The least trans- portation cost decrease of opening a site can be estimated by running a transportation problem including all facilities (T[{K1 U K2“) and then running a transporation problem without the facility (T{K1 U K2}-k]). 2. If the largest possible decrease in transportation cost due to opening a facility is less than its fixed charge, then it should remain closed (omega rule). The greatest transporta- tion cost decrease can be estimated by running a transporta- tion problem with only those facilities that have been fixed open (T[{K1}]) and then adding the one site and running a transportation problem again (T[{K1} U k]). 29 These rules are mathematically stated as: Ak = T[{K1 U K2}-k] - T[{K1 U K2}] - Fk’ k 8 {K2} ifAkZOthenY =1 k at = 1'[{xl}] -'1'[{x1} u k] - F k 8 {K2} k’ if 0k S then Yk = 0, “{KO} These two decision rules are tested in two steps. Step one is to determine which locations meet the delta rule and should remain open (Yk=1)‘ A transportation problem is solved with all locations opened (T[{K1 U K2“). Then sequentially each member of {K2} is individually removed, the transportation problem is re-solved T[{I(1 U K2}-k], and then the location is replaced in {K2}. Those members of {K2} that caused the total transportation to increase by an amount greater than or equal to their fixed charge are placed in the set {K1}. Step two is to fix locations closed (Yk=O). through the omega rule. This is done by adding one location at time from {K2} to locations in {K1} and solving the transportation problem T[{K1} U k]. If the transportation costs do not decrease by a sum at least equal to the fixed charge, the site is fixed closed and becomes a member of {K0}. By fixing open and closed facilities in this manner, typically, a large portion of the candidate locations can either be fixed open or closed. The locations that remain in {K2} after the two decision rules have been tested can then be tested through a typical branch and bound process to determine whether they should be included or exclud- ed. Generally, because the two decision rules have fixed a majority of the candidate sites either open or closed, the number of branches that must be evaluated has greatly diminished. One of the problems of an approach like Khumawala's is that it 30 requires the solving of a great many transportation problems. Specif- ically, the delta rule requires solving one transportation problem for every element in K2 (at that time) plus one and the omega rule re- quires solving one‘ transportation problem for every element in K2 (at that time) plus one. In a problem with a large number of potential sites, this process becomes unwieldly. To relieve the problem of having to solve a large number of transportation problems, Akinc, and Khumawala and Akinc chose to develop approximations so that it was possible to apply Efroymson and Ray's method and treat capacitated facilities (28,29). Many others have chosen to utilize Benders' inequality which states that if u = (ui) is a feasible solution to the dual of just the optimization of n i=1 cij solution to the problem without integer restrictions, then the optimal the delivery costs (2 1:1 I X13.) for a set Yk and E is the solution must satisfy the following inequality: 0 n 1; [F1 - Gi(ui - u8)]Yk s 2 - 1:1 Dj*uj - us) It 8 {x1 11 K2} Where Gi = the capacity of facility 1 Dj = the quantity shipped to customer j 118 = a dummy destination to absorb excess capacity Benders' inequality is used in the algorithm developed by Ellwein and Gray (31). Bulfin and Unger employ a surrogate constraint techni- que to fortify Benders' inequality (32). Still others have found in- genious means to shortcut the computational difficulty of solving a facility location problem with mixed integer programs (33,34,35,36,37, 38). However, many of these special purpose methods used to solve 31 unique problems are no longer necessary because of the current exist- ence of powerful general-purpose mixed integer programing packages (34). 2-2 Bus Garagg Flaming The development of bus garage planning in the last 40 to 50 years parallels the availability of funds for mass transit capital improve- ments. When there were no funds available to build garages, there was no need to plan bus garage additions. In the 1950's most United State cities experienced rapid subur- banization. The movement to less densely populated suburbs shifted increasingly larger portions of the urban population beyond the ef- fective, economic reach of existing mass transportation systems. Sub- urbanization, coupled with the post-war thrust to build more and better highways, led to a relative shift in the dependence on travel modes away from transit and towards automobile transportation. An ebbing in ridership and increasing costs left local operators small margins between their fare revenues and operating costs. When ad- dressing the austere conditions of the transit industry in the 1950’s, Smerk wrote: For its part, urban mass transit had its own crisis. There had been no end to the generally deteriorating condi- tions of mass transportation that had set in at the end of the Second World War. The companies which had accrued sur- pluses as a result of heavy wartime traffic had used up their resources, and by the late 1950's they were generally living a hand-to-mouth existence. Many public transit concerns went out of business, especially in small cities. The situation was hardly better in larger metropolitan areas. Even where transit companies managed to keep their heads above water, earnings were slim and it was difficult to secure funds for new facilities, for improvement of facilities and for the re-placement of equipment (42, p. 250). 32 Prior to the fifties were the war years, and before that the Depression. Thus, before the 1950's, the last time the transit in- dustry had experienced stable and normal economic conditions was prior to the Depression years of the 1930’s. Garages constructed in the 1920’s or before were built to store vehicles for transit systems that had changed dramatically 30, 40 or 50 years later. In fact, many transit operators still use converted street car barns to store buses” (7,12,9). Because there was little need to plan bus garages between the pre-Depression years and the end of the fifties, there was no need to update bus garage planning practices. The Housing Act of 1961 initiated the first federal funding for local mass transit. However, this legislation allotted only $25 million for mass transportation demonstration projects, to be matched one-third by local funds (43, p. 273). The Urban Mass Transportation Act of 1964 first permitted federal funds to be used for new equipment and facilities. Financial grants were to be matched one-third by local funds. The 1964 act and a 1966amendment made $150 million per year available for grants through fiscal year 1969 (43, pp. 310-319). The 1964 act resulted in approximately $375 million being allocated for loans and grants to local operators (44, p. 3). Although the federal funds made available to transit operators from 1961 to 1969 helped to slow the downward spiral of local transit service, they provided primarily stop-gap help to operators, and the main result was to refurbish existing Ffacilities and replace vehicles. The resources necessary to permit operators to make substantial capital improvements did not become available until the Urban Mass Transportation Act of 1970. The 1970 legislation increased funding 33 levels to $10 billion over the following 12 years, or a permissible average of $830 million.per year (44, p. 3). Later, the National Mass Transportation Act of 1974 decreased the local matching requirement from one-third to one-fifth of the financial grant (44, p. 1). The 1974 legislation also increased funding limits to $7.8 billion for capital grants over the next six years or a permissible average of $1.3 billion per year. Since the Urban Mass Transportation Act of 1964, grants for local transit service increased free $52 million to $826 million in fiscal year 1974 (44, p. 1). The most recent funding legislation, the Federal Public Transportation Act passed in late 1978, increased the federal funding level for mass transportation to $3.175 billion in 1979 alone (45, p. 318). This sum is approximately equal to half of 1979’s federal authorization for highway funding. In contrast to the importance placed on transit through its share of federal funds, transit provides a modest 4 percent of United State person-miles, while trucks and cars provide 91 percent (46, p. 48). Nevertheless, the emphasis placed on transit funding indicates its importance to federal transportation policy. It was not until the 1970's that funding levels increased to a level sufficient to. provide more than stop-gap help and operators could begin to plan capital improvements (e.g., bus garage additions); At that time operators could again fund new facilities and the transit industry begun planning new facilities. Hence, the modern phase of bus garage planning did not begin until the early to mid 1970's. In the early 1970's, because operators and transit technical con- sultants had not previously had to deal with the expansion of fixed facilities, or at least not recently enough to be of any significance, 34 the expertise and experience necessary to approach garage planning with any technically rigorous methodologies did not exist. For this and other reasons, garage planning started at a very elementary level. Early garage studies approached the problem of locating and sizing garages in a stepwise fashion. Because transit planners were sensi- tive to managing and operating facilities, they first set out to determine the most manageable and efficient size for a garage, and what kinds of equipment should be located in the garage. In 1975, the Urban Mass Transportation Administration (UMTA) published a report entitled "Bus Maintenance Facilities: A Transit Management Handbook," which was intended to answer many of the questions relative to in- ternal planning of bus garages (6). The authors of the UMTA handbook surveyed 54 operators on their experiences and perceptions about bus garage planning. With the response and the researchers' own interpretations of the results, they attempted to document industry-wide practice. However, the survey only collected past and current planning practices and personal per- ceptions of local operators, and published the results as standard industry practice. Thus, the handbook directed garage planners to continue to do as they had in the past, regardless of whether past practice was the most efficient possible.‘ The survey portion of the handbook attempted to specify an effi- cient garage capacity by asking maintenance managers what maximum capacity they would recon-lend for a bus garage. The largest number of responses (89 percent) specified 250 buses or less (6, p. 13). Al- though the handbook does point out that a garage sizing plan should include considerations of the local transit network (i.e., spatial 35 configuration of the bus route structure) it does state that "an optimum garage size exists and is somewhere in the range of 250 to 300 buses." Later, operators' bus garage studies have used this size range as a fixed parameter for the capacity of all new garages (3,4, 7,12). By fixing the capacity, the planner need only search for a garage location and allocate approximately 250 vehicles to the facil- ity. This narrows the problem of planning a new facility from a locationeallocation problem to a multifacility location problem. The UMTA handbook points out that location preference is depend- ent on the route structure, and that the most desirable site is one that minimizes desdhead mileage (6, p. 12). It also points out that desdhead mileage may range from 10 percent to 50 percent of total vehicle mileage, thus indicating the significance of minimizing desdheading (6, p. 12). Garage Plannigg Studies To indicate the status of current transit industry practice, garage studies of five metropolitan operators, Milwaukee, Louisville, Detroit, Oakland, and St. Louis, will be described and critiqued in the following subsections (12,13,9,3,4). Four of the five studies were completed as recently as 1979 and, with the exception of the Oakland and St. Louis studies, all use a different approach to locate garages. An approach used to locate garages for the Minneapolis-St. Paul operator will also be described (7). The reason for the special emphasis placed on the Minneapolis-St. Paul study is that it is the only known study to treat the garage location problem as a location- allocation problem. Further, it presents an indication of the cost savings that could be gained by planning garage additions using more 36 accurate planning techniques. Milwaukee. In 1975, UMTA granted Milwaukee County funds to pur- chase the private operator that provided transit services to the Mil- waukee metropolitan area (12). A stipulation of the grant was that a facility utilization study he conducted to determine if existing facilities were efficiently matched to existing and future bus storage needs, and, if not, to recommend facility improvements. After having identified a need to redevelop existing facilities and build additional ones, the study defined a simple two step method to determine the number and locations of garage changes. In the first step, the ideal ("optimal") locations and size of garages were deter- mined without considering existing facility locations or the avail- ability of property at a selected site. That is, ideal garage sites and sizes are determined as if there were no existing facilities and no constraints placed on where a garage could be located. The second step estimates the increase in costs of locating at various combination of existing sites and available sites when com- pared to the ideal garage locations and sizes. The most desirable combination of existing and available sites is judged to be the one that causes the least increase in cost over the ideal garage system's 'cost.- An optimal location for a bus garage was deemed to be that point which is at the distance center-of-gravity from all route assignment beginnings (pullout points) and ends (pullin points) that are serviced from the garage. To find centers of gravity, the pullout and pullin points would have to be clustered into groups, and each group assigned to a garage. The assigning of pullout and pullin points to various 37 groups is based on the number of buses which may be assigned to a garage (garage size) and natural boundaries between clusters of pull- out and pullin points. Once the center of gravity of each group is found, the rectilinear distance between the garage and its pullout and pullin points (desdhead) is totaled and multiplied by a factor to convert rectilinear desdhead distance to estimated desdhead cost. Next, the locational properties of existing garages and optimal sites are compared. The rectilinear distance of all pullout and pullin points served from the existing garage was first computed. Then the differential between the desdhead of serving the same points from the ideal location and the existing garage is calculated. The differential is converted to an estimated cost which is assumed to be the penalty of not having the existing garage at the ideal location. To determine a standard ideal ("optimal") size, the Milwaukee study investigated industry practice and arrived at a garage size of 250 buses. This result was based on 1) observations and judgement of the consultant, 2) conversations with industry experts, 3) a survey of the garage sizes of other operators, 4) recommendations made in UMTA's handbook, "Bus Maintenance Facilities: A Transit Management Hand- book," and 5) the recommendation made in a garage cost analysis study, "Optimal Garage Size Analysis," prepared for the Metropolitan Transit Commission (this study is discussed in detail later). The Milwaukee bus fleet was planned to reach 1,000 vehicles by the year 2000. Hence, the study set out to find the least cost, feasible combination of four 250-vehicle bus garages. Realizing that desdhead costs could be reduced by locating more and smaller garages closer to pullout-pullin points, the authors tried to justify their 38 firm stand on 250 vehicle bus garages by stating that, in their opin- ion, "The balance in size of the operating location is more desirable than reducing desdhead time to a minimum" (12, p. 34). After dividing the planned 1,000-bus network into four sectors, each having service requirements of 250 buses, they found the distance center of gravity for all four sectors. Then they checked to make sure all pullout- pullin points were closest to the center of gravity of the sector they were assigned to. If all pullout-pullin points met this condition, the authors claimed to have found the "optimal" site. The study considered combinations of the four "optimal” and the three existing sites, until it found the combination with the minimum sum of desdhead cost differential and other costs related to the garage system (i.e., garage construction costs, property costs, site preparation, etc.). The study finally recommended its seventh least- cost alternative (out of 24 alternatives). The first six were infeas- ible because land was unavailable at one or more of the sites included in the combination. Ironically, even though the study had earlier claimed that all garages should be sized at 250 buses each, the recom- mended alternative included five garages with capacities ranging from 144 to 255 vehicles. Louisville. The Transit Authority of River City (TARC), the Lou- isville metropolitan area operator, is the smallest operator reviewed. TARC expected to expand from 234 buses in 1975 to 343 in 1980 (13). Because the only existing garage could efficiently store only 130 buses, there existed a pressing need to build an additional garage. unlike studies of larger systems, the TARC study was only interested in locating one facility. That is, 130 buses would be stored in the 39 existing garage and the remainder would be stored in the new facility. The TARC study took a highly subjective, but interesting, recur- sive approach to selecting the new site. Bach.step refined the prob- lem and the number of sites remaining as candidates was reduced at each step. The last step in the process was to have six professionals rank the remaining potential sites according to weighted criteria. The recursive steps were: 1. Objective definitions. 2. Area-wide search. 3. Identification of potential sites. 4. Elimination of sites that did not fit the objectives. 5. Ranking of remaining sites and-site selection. After defining the objectives, the area-wide search began identi- fying the total deadhead travel times associated with locating an ad- ditional garage in various sectors. This was done by dividing the area into zones and calculating the deadhead travel to bus assignments from each zone and frmm the existing facility. To simplify the prob- lem, all bus assignments were aggregated by routes, to reduce the number of potential combinations of travel times and zones. Next, for each combination of the existing garage and one poten- tial garage location zone, the total deadhead travel time for the planned 1980 transit network was calculated. The existing garage was assigned 130 vehicles, and in each combination the potential zone was assigned the remainder. One zone was identified as being the minimum deadhead travel time zone. The remaining zones were ranked according to how much greater the total deadhead travel time would be in rela- tion to the minimum cost zone. 40 After investigating only the zones that had deadhead travel times of less than 1.5 times the minimum zone, identifying all potential sites, and eliminating those that did not fit the objectives only eight sites remained. These eight sites were ranked on a weighted scale by six professionals. The weighted scale include three cate- gories: 1) Considerations of compatibility of the candidate site with adjacent land use, 2) considerations of the engineering characteris- tics of the site (i.e., drainage, soil conditions, street access, etc.), and 3) the operational costs of occupying the site (i.e., deadhead costs, property purchase, garage operations, etc.). The first category was weighted by 431 points (out of one thousand), the second received 237 points, and operational costs were weighted with 332 points. Note that compatibility with adjacent land used (category one) was ranked most highly. This points to the particular importance placed on the sensitivity of locating a bus garage where it is not a desirable addition to the surrounding community. Detroit. The Detroit system study is unique, because it is con- cerned with the garage needs of two operators (9). Suburban transit services are operated by the Southeast Michigan Transportation Author- ity (SEMTA), while transit services within the city of Detroit are operated by the Detroit Department of Transportation (D-DOT). Al- though the two systems operate separately, they will soon merge. The study treats the merger by maintaining the independence of both sys- tems' route structure while treating the garage storage needs of both operators jointly. That is, the existing routes were maintained in their existing form, but buses from either operator could be stored in any garage. 41 SEMTA operated 281 buses in 1979 and expects to have a fleet of 525 buses by 1983 and 710 buses by 2000. D-DOT is currently the larger operator, operating 884 buses. The number of buses dedicated to the area D-DOT serves is not expected to increase. D-DOT operates three large storage garages (280-320 buses), while SEMTA operates three moderate-size suburban storage garages of approximately 100 vehicles each and another extremely small facility that holds only 15 buses. One of SEM'l'A's moderate-sized garages is located northeast of - Detroit, another north, and another to the west. As a result of a judgemental decision of the SEMTA staff in con- currence with an earlier (1975) garage study, the northwest and south- west portions of the SEMTA service area were earmarked as the two can- didate areas for new garage locations. However, the addition of new garages was not the only solution considered for resolving SEMTA's garage space problems. Also considered was expansion of existing SEMTA and/or D-DOT facilities in conjuction with combinations of building or not building a northwest and/or a southwest garage. The different possibilities considered resulted in eight different pro- spective combinations. The method used to evaluate the possible candidate garage com- binations was based on a rectilinear distance minimization objective. The method first cordoned off a portion of the service area and as- signed all buses that served routes within the area to a garage to be located in that area. The next step of the process finds the minimum rectilinear deadhead distance location to all pullout-pullin points in the area by stepping around the area and evaluating each point until a relative minimum is found. 42 Once the minimum rectilinear deadhead distance location is found for garages assigned to new sites, rectilinear distances are calculat- ed for buses assigned to existing garages. All rectilinear distances are multiplied by a factor to convert miles travelled to transporta- tion cost. Transportation costs are totaled across all garages and added to the capital costs of all garage construction called for in the combination and the increased cost of maintaining the building and the grounds at a new facility. These same costs are calculated for future transit networks up to 2000. At each point in the future, costs per unit (i.e., the cost of miles traveled, facility mainten- ance, and construction) are increased to equal their projected in- flated value. This future estimation allows a dynamic staging of facilities. In conclusion, the SEMTA study recommends that its exist- 2 ing northeast and north facilities be increased in size and that later a northwest facility be built, followed by the construction of a southwest facility. Reviewing SEMTA's location model, it is evident that the method used takes a brute force approach by stepping around the cordoned area and enumerating the rectilinear distance at each point. Once buses are assigned to a particular area, the minimum distance location could be found by simply identifying the median location (8, p. 176). Also, by inflating future costs, the method places more emphasis on future values than they deserve. That is, assuming that receipts (federal and local fund and farebox receipts) increase at a rate equal to inflation, inflation should have no impact on the total cash flow. Oakland. The study of the Oakland area transit system (A.C. Transit) was much more than a garage location study (3). It also 43 critically looked at all existing facilities and projected future needs based on four scenarios: 1) service continues at its existing level, 2) 33% reduction from existing service levels, 3) 33%.expansion from existing service levels, and 4) 100% expansion from existing service levels. Based on the sufficiency of existing facilities to 'accommodate bus storage needs under each of the four scenarios, the study located new facilities (if necessary under the scenario con- sidered). The study began its search for new locations by specifying cri- teria for a new site. Although most of the criteria focussed on internal characteristics of garages, for instance, the space required per storage bay, the quantity of space needed for parking, and others, the study also specified a capacity of 250 vehicles for all new ga- rages and based this size on "past and ongoing transit industry prac- tice" (3, p. 108). The next step was to select candidate sites for garages and evaluate the costs associated with occupying different combinations of sites under the four scenarios. For each combination of sites, buses were allocated to individual sites by first estimating deadhead costs and then allocating buses to the minimum-cost site while observing capacity constraints. Dead- heading costs were estimated by using the UTPS computerized highway network and determining the time and distance cost along the minimum cost paths. Based on the estimated travel cost, buses were allocated to the existing and candidate sites included in the combination. The study enumerated the deadheading cost implications of locat- ing at combinations of the 20 different sites (16 new locations and 4 existing ones). Having estimated the deadheading costs under the four 44 scenarios, the study made recomendations on future additions. Since the study had already determined a specific size for garage additions, other garage size-sensitive costs (i.e., garage operating and con- struction) did not enter into the recommendation decision. The A.C. Transit report is a well-documented study of the exist- ing garaging system, and does a good job of pointing out garage layout concerns. It does not, however, give much emphasis to garage loca- tion-allocation considerations, and the approach taken collapses the problem to a simple location model by fixing garage capacities. St. Louis. The study conducted by the St. Louis operator (Bi- State Development Agency) was very much like the Oakland study, except that future bus storage needs were set at one level (4). The St. Louis study also did not critique the existing facilities, but started with a search for new sites. The fact that existing garages were antiquated and needed to be replaced was determined before the study started. Like the Oakland study, the St. Louis study started by specifying that all new garages would have a capacity of 250 buses, justifying 250 by stating that "This figure is an industry wide ac- cepted number, reflecting tested economics and efficiencies in bus maintenance operations" (4, p. 3-7). The study also goes on to make the heroic assumption that "The basis for achieving adequate system- wide capacity and optimal deadhead (travel) is the 250 bus limit" (4, p. 2-3). After making these strong statements on garage size, the study proceeds to find locations for new garages. Because Bi-State has a planned fleet size of 1,324 buses by 1986 and 1,748 buses by 2000, the study predicts a need for 6 garages by 1985 and 8 by 2000. The next step was to find candidate sites. This 45 was accomplished with the use of general howledge of the direction the transit network is expanding and contrasted with knowledge of suitable locations for bus garages. After identifying 16 sites (5 existing garage locations and 11 candidate locations), the deadhead transportation costs were estimated for servicing all routes from all sites. Travel costs were estimated by using the UTPS highway network and finding the time and distance costs from all. pullout/pullin points, aggregated by routes, to all candidate sites. Then combina- tions of sites were tested for their associated deadhead costs by allocating buses assigned to each route to the minimum-cost garage site, while observing capacity constraints. A minimum-cost combina- tion of six sites was recommended for 1985 and a minimum-cost combina- tion of eight sites was recommended for 2000. As can be seen, there is a great deal of similarity between the St. Louis and the Oakland studies. Both reduce the problem of locat- ing garages and allocating capacity to those garages to a simple location problem. This is done by making the assumption that, because garages have been built in the past at a capacity of 250, the same practice should be continued into the future. The problems with such an approach will be demonstrated in the following discussion of a garage study conducted for the Minneapolis-St. Paul operator. Minneapolis-St. Paul. The' Minneapolis-St. Paul operator (the Metropolitan Transit Commission) purchased the area's private Operator in 1967 (7). The Metropolitan Transit Commission (MTC) had purchased 650 aging buses, the youngest bought in the early 1950's, and three garages, all which were constructed before 1910. By the spring of 1976 the fleet consisted of 1,050 buses, all less than five years old. 46 Although the fleet had been increased by 60%, only one new small (150 buses) garage had been added in the summer of 1975 when the MTC real- ized it could not make it through the 1975-76 winter without a new facility. This most recent facility, the Shingle Creek garage, was only leased, and it was built such that it could be converted to industrial use if the MTC did not accept its option to buy the facility when the lease expired. The Shingle Creek garage presented a quick and simple solution to space problems-and permitted the MIC to weather the winter of 1975-76. However, this was only a stopgap solution. One of the old garages just to the north of downtown Minneapolis (the Northside Garage) was fast approaching retirement, and even with the Shingle Creek garage, buses were still stored outside. Further, because the Shingle Creek garage is located in a northern Minneapolis suburb, it bolstered the northwestern end of the service area's relative propor- tion of garage space but left the service area to the southwest and east (St. Paul) relatively deficient in garage space. This distribu- tion of facilities resulted in large deadhead costs, because route assignments were misallocated to garages where space was available instead of to garages where the routes could be serviced at a minimum cost. The need to correct the unequal dispersion of facilities and to find additional garaging space lead to a search for additional garage sites, primarily to the south and secondly to the east. In 1974' (before the addition of the Shingle Creek garage) the staff began to search in the south Minneapolis suburban area for a garage site that would minimize deadhead costs. Because the most extensive growth in the metropolitan area was concentrated towards the 47 south and west of Minneapolis, the transit network had been funneled towards this area. Because of these reasons it was evident that this area was most deserving of a new facility. The 1974 study cordoned off the south and southwest metropolitan area and performed a center of gravity-like location analysis of all the routes in the area.* Once a center of gravity was found, a site would later be sought in the general area. The next step in the garage study was to determine the size of the facility to be located at the selected site. The MTC next conducted a study to determine the optimum garage size. This study modeled the garage operating costs of existing fa- cilities and extrapolated the results to derive estimated operating costs for garages varying in size from 100 to 400 buses. Garage con- struction costs were derived in a similar fashion. To estimate non- productive transportation costs, the study looked to an existing core city garage (the Nicollet garage). The deadheading costs of the 100 buses assigned to the Nicollet garage with the fewest deadheading miles were estimated; mileage was multiplied by a factor to convert miles to costs. Costs were then estimated for the 50 buses with the next fewest deadhead miles. Increments of 50 buses were so assigned until the last estimate encompassed 400 buses. This resulted in estimates of the deadhead cost for the Nicollet garage, in increments of 50, from 100 buses to 400 buses. The least average cost (cost per bus) when all three costs were totaled fell at a garage size of 300 vehicles, and hence the decision was made to size the new facility at *The study used a center of gravity approach, except that travel through zones with freeway access had their distances weighted differently than those without freeway access. 48 300 buses. What was really determined was that the lowest average cost for the Nicollet garage, located in a dense portion of the trans- it network, would be at a capacity of 300 buses, but the MTC assumed that this value held true at any location. The next step in the process was to find a piece of vacant prop- erty that would accomodate a garage near the center of gravity loca- tion. A piece of property was found on the Bloomington strip. The property was previously occupied by the Bloomington Drive-In. The land is 12.5 acres acres in area and was priced at approximately $1.35 million. The weakness in this garage study's analysis was in its piecemeal nature. It is easy to see why the whole process developed in discrete small steps; the path through the separate studies followed the logi- cal route through the separate decisions that have to be made to arrive at a cost-minimizing garaging scheme. But no comprehensive ef- fort was made to determine the cost relationships between capacity-re- lated cost and spatial parameters. During the summer of 1976, after the MTC had invested approxi- mately $580,000 on architectural and engineering plans and environ- mental impact statements, the City of Bloomington reneged on its previous position of goodwill towards garage construction in the City of Bloomington, and.the city began taking action to stop the garage's construction at the drive-in site. Out of respect for its public image, and because the MTC had no concrete evidence of the cost penale ty of not locating at the drive-in site, the MTC decided to retrench and re-evaluate its decision to build at that particular site. This led to a second study conducted in the summer and fall of 1976. 49 The 1976 study first estimated the non-productive transportation costs (the sum of relief and deadhead costs) for all block assignments to all proposed sites, including the existing facility locations, the drive-in site, and a number of other candidate sites. The costs were estimated with the use of the UTPS highway network and the MTC's esti- mated distance and time costs. Then, by assigning blocks to garages with the minimum transportation cost, while observing capacity con- straints, and using the garage operating costs and the construction costs estimated in the optimum capacity study, the costs were esti- mated for the existing and planned system. The planned 1980 garage system included the following changes: 1. Building a garage at the drive-in site of 200 bus capacity (in 1985 to be increased to 300 buses). 2. , Buying the Shingle Creek garage and increasing its capacity to 300 buses. 3. Phasing out the North Side garage. The costs for the existing system including all existing sites (Snelling, Nicollet, North Side and Shingle Creek), are shown in Table 2-1A. The costs for the planned system are shown in Table 2-lB. Next, the costs of all logical combinations of candidates were cal- culated with respect to the capacity coastraints only of existing garages, assigning all other garages a capacity equal to the number of buses closest to that site. The total cost of the least-cost combina- tion is shown in Table 2-IC. Notice that the drive-in site is not included in the least-cost system, and that the Shingle Creek garage remains at its 1976 capacity (150 buses). Also, a new site just to the southwest of downtown St. Paul (Riverview) is included. Table 2-1 50 Table 2-1 MTC Total Annual Costs (1976 Dollars) Table 2-1A MTC's Existing Garage System Peak Garages Garage Construction Operating Transportation (Existing1f Demand Capacity Cost Costs Costs Snelling 229 250 $ 0 $1,045,933. $1,480,740. Nicollet 243 270 0 1,103,834. 1,626,900. North Side 261 300 0 1,190,653. 1,260,630. Shingle Creek 146 150 __0 801,509. $1,160,870. 879 $'0 $4,141,951. $5,529,140. Total $9.67 million/year Table 2-lB MTC's Planned Garage System (as of 1976) Garages (Existing and Peak Construction Operating Transportation Proposed) Demand Capacity Cost Costs Costs Bloomington(new) 165 200 $283,824. $ 899,245. $1,472,620. Nicollet 243 270 0 1,103,834. 1,421,580. Shingle Creek (expanded) 242 300 213,955. 1,103,834. 1,824,680. Snelling 229 250 0 1,045,955. $1,480,740. 879 $497,779. $4,152,877. $6,199,620. Operating and transportation costs $10.35 million/year; Total $10.85 million/year Table 2-10 Recommended Garage System Garages (Existing and Peak Construction Operating Transportation Proposed) Demand Capacity Cost Costs Costs Nicollet 243 270 0 $1,103,834. $1,626,900. North Side 261 300 0 1,190,653 1,243,230. Shingle Creek 116 150 0 703,774. 986,870. Snelling 113 150 0 703,744 355,830. Riverview (new) 146 200 $283,824. 703,774. 672,800. 879 $283,824. $4,405,809. $4,885,630. Operating and transportation costs $9.29 million/year; Total $9.58 million/year 51 indicates that the planned system would cost approximately $1.18 million more per year than the existing system, and approximately $1.27 million more per year than the recomended system. Next, the same process was conducted on the planned 1985 system. The changes to the planned 1980 system included: 1. Increasing the drive-in site to a capacity of 300 buses. 2. Constructing a facility in the east (the Riverview site) of a capacity that had not at the time (1976) been decided. The results of the cost estimates for the planned system are shown in Table 2-2A and, for the least-cost combination of candidate sites, in Table 2-28. Note that, based on the planned 1985 network, the planned system would cost approximately $1.48 million per year more than the recommended system. Also, the drive-in and Shingle Creek garages have a recomended capacity of 150 buses. The MTC study's approach is not a pure optimization. It merely assigns buses to the least non-productive transportation cost site. Lower costs than the planned system were found, demonstrating the problems that can be encountered by preselecting a garage size and locating facilities of that size regardless of other considerations. Conclusions of the State-of-the-Practice Review Six garage location studies were reviewed. The highlights of each are described in the following pages: 1. Milwaukee Study. This study used a center of gravity ap- proach to locate new garages. The first step in the. ap- proach was to specify a fixed size for all garages (250 buses). Then the service areas were divided into sectors Table 2-2 MTC Total Annualized Costs (1976 Dollars) Table 2-2A MTC's Planned Garage System (as of 1976) Garages (Existing and Peak Proposed) Demand Bloomington(new) 270 Nicollet 243 Shingle Creek 242 Snelling 144 Riverview (new) 293 1101 Operating and transportation costs $13.43 million/year; Capacity 300 270 270 175 225 Total $14.32 million/year. Construction Operating Transportation Cost Costs Costs $372,716. $1,190,653. $2,855,920. 0 1,103,834. 1,531,490. 213,955. 1,103,834. 2,027,970. 0 801,509. 604,650. 304,766. 972,600. $1,233,080. $891,437. $5,172,430. $8,253,110. Table 2-2B Recommended Garage System Garages (Existing and Peak Proposed) Demand Northside , 261 Bloomington(new) 243 Nicollet 243 Shingle Creek 129 Snelling 144 ,Riverview(new) 292 1101 Capacity 300 150 270 150 175 225 Construction Operating Transportation Cost Costs Costs 0 $1,190,653. $1,350,750. $283,824. 703,774. 1,075,320. 0 1,103,834. 1,456,090. 0 703,774. 1,052,110. 0 801,504. 609,950. 304,766. 972,600. 1,233,080. $588,590. $5,476,144. $6,777,300. Operating and transportation costs $12.25 million/year; Total $12.84 million/year 53 containing 250 buses and the center of gravity of each sector was deemed the optimal location for garages. Lastly, alternative combinations of sites were ranked by the cost implications of each combination. Because less costly combinations contained unavailable sites, the seventh least- cost combination. was recomended. In contrast to the ini- tial criterion of a fixed 250-bus garage, the recommended combination contained garages with capacities ranging from 144 to 255 vehicles. Louisville Study. The objective of this study was to find one site in addition to the existing garage. First, the ap- proach divided the service area into zones. The total dead- head travel time when a garage was located in each zone and at the existing location was calculated and a minimum total deadhead travel time zone was identified. A search was then initiated for acceptable sites within zones of 1.5 times or less the total deadhead travel time of the minimum zone. Eight sites were found and all were ranked by a panel of six professionals with respect to: 1) compatibility with adja- cent land use, 2) engineering characteristics, and 3) opera- tional costs. The most interesting facet of the ranking was that compati- bility with adjacent land use was weighted more highly than operational costs. Detroit Study. The approach used in this study located garages based on a rectilinear distance minimization.objec- tive. Certain portions of the service areas were cordoned 54 off, and a minimum rectilinear distance site to all pullout] pullin points within the cordoned area was deemed the opti- mal location for a garage. The costs of operating garages were estimated for the present and the future (planned) transit system, and a staging through time for building garage additions was recomended. Oakland Study. This study starts by evaluating each of the existing garages. The authors thoroughly critique each fa- cility with respect to its functional design. Then the study defines future garage needs under four growth scenar- ios. After fixing a garage size of 250 vehicles and identi- fying 16 candidate sites for new garages, the study esti- mates the deadheading cost of all reasonable combinations of garages. Deadhead costs are calculated by using the region- al UTPS highway network and calculating the impedances (time and distance costs) to and from pullout/pullin points to each site. Buses are assigned to the least-cost garage and the deadheading costs are totalled. Finally, the least-cost alternative under each scenario is recommended. St. Louis Study. This study takes the same approach as the Oakland study, but it does not evaluate existing garages and only seeks new facilities under one scenario. Minneapolis-St. Paul. The study reviewed was the second ga- rage study conducted for the Minneapolis-St. Paul operator. Like the Milwaukee, Oakland and St. Louis studies, the first study had fixed garage sizes (300 buses) and later searched for a location. After purchasing the site recomended in 55 the first study and develOping plans to build on that site, the operator was stopped by the municipality. The second study sought proof that the operator would be penalized by not locating at the purchased site, but in fact showed that locating a 300-bus garage at the site would penalize the operator in annual operating costs. Nonrproductive trans- portation costs were estimated by using the UTPS highway network and bus assignments are allocated by permitting garages to seek a capacity equal to the number of pullout/ pullin points closest to the site. The garage system recom- mended by the second study had a much lower cost than that of the first study, hence showing the possible penalities of sizing garages at a fixed capacity regardless of location. In conclusion, most of the studies reviewed, and especially the Oakland study, covered the internal garage layout and facility needs well. However, only the Minneapolis-St. Paul study dealt with the locating of garages as a location-allocation problem. The Detroit study implicitly selected the size of the facility by allocating only buses assigned to pullout/pullin points within a cordoned area to a new facility. The Louisville study explicitly fixed the capacity of a new garage to be equal to the number of buses in the system that was greater than the capacity of the existing garage. The Milwaukee, Oakland and St. Louis studies all fixed bus garage capacities at 250 buses, thus collapsing the problem of selecting sites to a simple location problem. The Minneapolis-St. Paul study treated the site selection problem as a location-allocation problem and showed that studies based on the questionable assumption that one garage size is 56 optimal regardless of the location could be penalizing operators with millions of dollars of additional, unnecessary expenses. However, the approach used in the Minneapolis-St. Paul study only located garages with respect to non-productive transportation costs, and therefore could not claim to optimally select sites. 2-3 Literature Review Conclusions From the review of the literature it is quite evident that there exists a number of analytically rigorous techniques that can be used to locate facilities. Further, the state of computer capabilities and the existence of powerful mathematical codes make it possible to solve locational problems with robust optimizations. However, the current state of garage planning practice has only begun to develop a few rudimentary approaches to the special needs of garage location prob- lems. Further, many studies have chosen first to fix garage capaci- ties at a specific size and then reduce the garage location-allocation problem to a simple location problem, which results in a non-optimal solution. This may be due to the relative complexity of solving location-allocation problems. Past garage planning studies have tended to focus on functional layouts of garages and other internal considerations. These studies have developed an excellent body of information with regard to facil- ity layout and design and to the cost of operating and building garages. Also, many studies have been able to identify the non- productive transportation costs associated with assigning buses to garages. But, none of the known garage planning studies have been able to tie facility and non-productive transportation costs together 57 in a total-cost location-allocation optimization. The Minneapolis-St. Paul study points out the savings that can be achieved through the treatment of site selection as a location-alloca- tion problem. Although this study used only a manual approximation solution technique, its results indicate the possibility of even greater savings through the use of a comprehensive optimization tech- nique. Therefore, there is a clear need to develop a state-of-the-art location model that may be need to solve garage location problems for regional transit operators. However, before the development of a garage location-allocation.model there remains a number of issues that must be addressed. They include: 1. The nature of garage facility cost functions; i.e., the way in which the unit costs change with changes in garage capac- ity. 2. A realistic representation of the non-productive transporta- tidn costs that result from deadheading and driver relief. 3. A realistic mathematical representation of feasible schedul- ing of buses to work assignments and facility capacity constraints. 4. The identification of a location modeling technique or tech- niques that may be restructured and adapted to garage loca- tion problems. 5. The structuring of the techniques into a computer model that accurately represents all necessary quantitative inputs and has sufficient capabilities to permit subjective and judge- mental inputs. CHAPTER 3 PROBLEM STATEMENT As indicated in the literature review, current methods used to aid in locating and sizing bus garages do not fully utilize state-of- the-art location models. The objective of this research is to develop a model that can be used to optimally locate and size bus garages. Following the design of the model, it will be applied to a Detroit metropolitan area case study to demonstrate the feasibility of the model. Although the bus garage location problem has similarities to other facility location problems that have been studied in the past, there are unique features of the bus garage location problem that require development of a specific model: 1. The nature of the facility costs related to bus garage sizes has not been identified in the literature. 2. A bus garage planning model must be capable of including subjectively weighted inputs, such as a variable accounting for the penalty of intruding on a politically sensitive neighborhood or for locating a garage on a prime industrial site. . 3. A bus assignment can not be partially assigned to more than one facility. 4. Each bus assignment may or may not be equivalent to one bus 58 59 stored in a garage. For instance, the same bus may be used on two assignments, one in the morning and one in the after- noon, or it may be used on one all day assignment. This is quite unlike other facilities where the facility capacity generally is proportional to the number of customers. These facets of the garage location problem make it necessary to develop a model which can be used to solve garage location problems. The specific objectives in the design and tailoring of a general purpose model for bus garage planning within a regional transit net- work are to: 1. Identify the nature and magnitude of cost parameters related to bus garage facilities. Develop a mathematical structure that accurately depicts feasible scheduling of buses to work assignments subject to facility capacity constraints. Develop a solution technique or techniques from the current location modeling literature and adapt the selected approach to garage location problems. Structure a computer model which can be used to solve bus garage location problems. Estimate the cost parameters that are necessary for use of the approach on a case study. Demonstrate the model by locating garages using the Detroit metropolitan area's transit system and the Detroit transpor- tation system's characteristics. Demonstrate, with the case study, the potential savings and costs of using the developed model. 6O 8. Perform a sensitivity analysis on the Detroit case study by varying availability of garage sites. The mmdel that is constructed in the research optimally locates bus garages and provide a mechanism for estimating the cost implica- tions of locating at sites other than the optimal sites. The model considers all costs related to the distribution of buses to service assignments. Specifically, the costs considered are: 1) nonproduc- tive transportation costs, 2) facility operating costs, and. 3) facility construction costs. CHAPTER 4 METHODOLOGY The location problm has been described by Eilon, et al. as one of minimizing distribution costs (10). In the case of bus garages, the distribution costs are the costs of: 1. Driving buses to and from block assignments (deadheading) and providing driver relief to those blocks that require it. 2. Operating the garages that store the buses. 3. Construction, if a new garage is required. In this chapter, two optimization models are formulated that will minimize distribution costs. The first model is a theoretical one which is impractical to use on a large-scale problem, although it could reach an optimal solution. The second model uses the theore- tical model as a basis to derive a practical approach, which also results in an optimal solution. After each model is formulated, it is applied to a small-scale example problem. The example is hypothetical, but it illustrates the use of both models and their differences. The practical model developed represents the structuring of a general optimization model that considers all costs relevant to. the garage location problem. When used by a transit operator, cost and transit system data must be obtained for the specific case being con- sidered. The structuring of the relationships among these costs is 61 62 fundamental . 4-1 Theoretical Model Formulation The objective of the model is to minimize the costs related to garages located and to the allocation of buses to garages located. Since the objective is to minimize costs subject to physical and transit system constraints, the problem is structured as a mathemati- cal program. Once the program has been formulated, it is examined to determine which mathematical programing solution technique (i.e., linear programing, integer programing, etc.) is applicable to its structure. In the following subsection cost inputs and data sources are defined. In the next subsection a formal structure relating the cost inputs to one another is formulated and a cost minimization mathamatical model is developed. Once a mathematical programing solution technique is selected, a small-scale sample problem is solved. Cost Inputs There are three costs related to the location of the garages and the allocation of buses to garages located. They are: 1. Non-productive Transportation Costs. These are the costs of the buses traveling to pullout points at the beginning of route assignments, of returning from pullin points to the garage at the end of the route assignment, and of providing driver relief to route assignments. 2. Garag570peratiug‘Cost. These are the costs of garage main- tenance labor, bus maintenance labor, and driver scheduling labor. 63 3. Garage Construction Costs. These are the costs of purchas- ing the garage and garage equipment. Each of these costs is discussed individually in the following para- graphs. Non-productive Transportation Costs. Route assignments of buses are known as blocks. Each block begins when a bus leaves the garage and ends when the bus returns . One driver may stay with the bus throughout the block, or a block may have more than one driver if the block is longer in time than one workshift. In the latter case, the initial driver is relieved at some intermediate point in the block. Because each block defines one individual trip, non-productive trans- portation costs are examined on a block-by-block level. Non-productive transportation costs for each block will be unique for each potential block-garage assignment. Non-productive transpor- tation costs may be estimated through a number of travel cost approxi- mation (i.e., Euclidean distance, rectilinear distance, or squared Euclidean distance); however, in this effort non-productive transpor- tation costs will be estimated using the UTPS computerized simulation of the highway network.* If a block is assigned to a particular garage or potential garage site, the non-productive transportation cost of the assignment is added to the costs included in that particular garage combination. However, the number of blocks assigned to a garage will probably not equal the number of buses necessary to service the blocks. Therefore, *The estimation of non-productive transportation costs with a UTPS computerized highway network is demonstrated in Chapter 5. 64 blocks have to be converted to bus equivalents to allocate capacity to garages. Blocks can be categorized by the period of the day the block spans. There are generally four types of blocks: all-day blocks, midday blocks, AM blocks, and PM blocks. All-day blocks are bus as- signments that, at least partially, overlap both the morning and afternoon peak. Midday blocks are bus assignments that overlap nei- ther peak. AM and PM blocks are assignments that cover their respec- tive peaks. Thus, the number of active buses assigned to a garage site has to be greater than or equal to the sum of the AM blocks plus all-day blocks assigned, and it must be greater than or equal to the sum of the PM blocks plus the number of all-day blocks. Similarly, the number of midday blocks plus the number of all-day blocks assigned to a garage must be less than or equal to the number of active buses assigned to a garage. These types of blocks occur during weekdays, Saturdays and Sundays, all .of which may have different schedules. Garage Operating Costs. These costs are an increasing function of the number of buses assigned to a garage. Cost estimates of garage operating costs over a range of garage capacities are available through studies conducted by two operators. Garage operating cost es- timates of the Metropolitan Transit Commission (the Minneapolis-St. Paul operator) and AC Transit (the Oakland operator) are plotted in Figures 4-1 and 4-2 (2,3). Both operators used the same methodology to arrive at their cost estimates. First, benchmark garage capacities were selected and costs were estimated at each capacity. The Metropolitan Transit Commission (MTC) selected benChmark capacities between 100 and 400 vehicle 65 swam.owosmu momuo> umoo wcwumummo ammumo m.:0wmmfiesoo awesome cmufiaoeouumz .Huq ouswwm mwmumo new woman mo monssz m m m m m m w. m _ . _ _ . F . _ fl _ _ _ _ . . _ 1r m6 0 11.... 41%. 1r9~ III-Iran." (193A lad SJBIIOP SL61 ;0 uorttrm ur) $3903 Burnsiado 982199 66 exam owmumo momum> umoo wcwumuono oweumo m.uwmcmuk o< .Nte muswwm owmumu mom women we monamz m m m m m m w. m — — p — — p — L a q _ a a . q a 11o; ..T: 1roa Ire; [lo-w 0.0 (193i 18d SJBIIOP 086T §O suorttrm ur) 3303 Suraeiado 989199 67 garages at increments of 50 buses and AC Transit selected benchmark capacities of 30, 60, 90, 150, 250 and 300 buses. Next, the opera- tors' professional staff estimated the number of employees and quan- tity of materials that would be required to operate a garage at each of the benchmark capacities. For example, AC Transit's professional staff estimated that bus garages of 30, 60, 90, 150, 250 and 300 buses would require 7, 7, 7, 11, 16 and 21 scheduling employees and 9, 17, 24, 39, 63 and 78 shop employees, respectively (3, p. 142). Each of the individual components is multiplied by its cost and a total cost developed for each benchmark capacity. As garage capacity is increased, most cost components increase in discrete additions. waever, even though operating costs may be dis- continuous when examining small incremental increases in capacity, the cost curves in Figures 4-1 and 4-2 are nearly linear. They do not run through the origin (non-proportion), as there is a fixed charge to operate a garage of any size. The fixed charge reflects the cost of carrying a minimum number of personnel to perform maintenance and scheduling activities and to operate the physical facilities. Thus, no matter how small a garage, the facility will sustain the labor costs of the minimum number of employees. Although the specific garage operating cost functions of the two transit operators differ in slope and fixed charge, they both behave in the same manner. Therefore, it is assumed that in the general case, garage operating cost functions will have a fixed charge and a linear variable cost portion even though both the fixed and variable portions may vary between transit systems or even between garages in the same systems . 68 Garage Construction Costs. Like garage operating costs, garage construction costs are a function of the size of the garage. Con- struction cost estimates are available through studies made by the Metropolitan Transit Commission and AC Transit (2,3). Their estimates are plotted in Figures 4-3 and 4-4. The construction cost estimates were made in the same manner as the garage operating cost estimates. Like the operating cost estimates, there are fixed and variable portions of construction cost. The fixed portion is largely due to the fact that, under normal circumstances, no matter how small the garage it requires certain pieces of equipment and facilities. For example, AC Transit's construction cost estimates for both a 30-bus garage and a 250-bus garage included the purchase of one bus washing rack. The specific garage construction cost functions of the two oper- ators vary in slope and fixed charge. However, both cost functions behave similarly. Therefore, it is assumed that in the general case garage construction costs will have a fixed charge and linear variable cost portion. Cost Relationshipg Having defined the cost inputs, the formal relationships between coats are structured. First, each of the individual costs is express- ed in separate mathematical models. Next, the block assignments are related to the number of active buses assigned to a garage and then active bus assignments are related to total garage capacities. Last- ly, all are combined in a comprehensive model. I Non-Productive Transportation Cost. The non-productive transpor- tation cost of allocating a block to any site can be represented by a 69 swam owmumo momuo> umoo newuospumcoo omoumo m.co«mmwasoo samcmue :muHHonouqu .muc seamen mmmumo mom women we monezz m m m w. m w. w. m. — p p b p p — n — q u q u q q M 18— L... 1‘3 [v.5 lites (199K 19d s19ttop SL6I ;o spuesnoqn up) 3903 u0113n1nsuog 989193 7O mufim mumsmo mmmuo> unou :owuuzsumcou owenmc m.nwm:msh u< .ecq ms2wwm mwmumu Hem woman no monasz m m m w. m w. m m. p p — . _ a cash —_ «.o Ll... (199A 19d s19110p 086T go suorIIIm up) 3909 u0119n1asu09 989199 71 set of integer assignment variables, bounded by zero and one. For in- stance, if there exist m candidate sites, and block i has nonrpro- ductive transportation costs, Tij’ for assignment to garage j (j = 1,2,.. .,m), then the non-productive transportation costs can be re- presented by Equation (4-1). Equation (4-1) is subject to the con- straint that the assignment variables xij must sum to one (assignment constraint) and Xij is an integer bounded by zero and one. Block's non-revenue transportation " 11 X11 + T12 x12 + + Tim xim (4 1) cost m subject to Z X.. = 1 ._ ij j-l Xij = O or 1, for all j (j=1,1,...,m) Where: i = Block number (i=1,2,...,n) j = Garage number (j=1,2,...,m) Xij = The assignment variable for block i to garage j. GaragngperatingiCosts. Operating costs have a fixed portion and a linearly increasing variable portion. This can be approximated with Equation (4-2). The fixed portion, F0, is included if the garage is to be built (Z=l) and the variable portion, 5, is proportional to the number of buses assigned to the garage site. Garage Operating Cost = FO(Z;) + 5(Ng (4-2) where: F0 = Fixed portion of operating costs ~ 0 = Variable operating cost per bus 72 N? = The number of buses assigned to the garage site for the pur- pose of assessing operating costs to garage site j 1; if N‘? > o z‘.’ = J J o; if N? = o J Garage Construction Cost. Construction costs have a fixed por- tion and a linearly increasing variable portion. Construction cost can be approximated with an expression identical to the approximation of garage operating costs. In Equation (4-3), the fixed portion, PC, is included if the garage is to be built (Z=1) and the variable por- tion, C, is proportional to the number of buses assigned to the garage site that require the construction of garage spaces. Garage Construction Cost = FC(Z§) + C(N§) (4-3) where FC = Fixed portion of construction costs 5 Variable garage construction costs 2 -n N The number of buses assigned to the garage site that require construction of spaces at garage site j 1; if N? > o 2? J o; if N; = o Relatinnglock Assignments to Capacity. The non-productive transportation costs are a function of block assignments; however, garage costs are a function of buses assigned to a facility. To make these costs comparable, some constraints must be structured regarding the relationship between blocks and buses. To balance the number of blocks assigned to a garage with the active buses assigned, a set of constraints is generated for each 73 garage (garage capacity constraint) like those shown below. For example, the capacity constraint in Equation (4-4) sets the sum of the weekday AM blocks plus the weekday all-day blocks assigned to the garage at less than or equal to the facilities' capacity (Nj). The capacity constraints in Equation (4-5) do the same for weekday PM and weekday all-day blocks and Equation (4-6) constrains weekday midday and weekday all-day block assignments. Equations (4-7), (4-8) and (4-9) similarly constrain Saturday block assignments, while Equations (4-10),(4-11) and (4-12) constrain Sunday block assignments. n n a c X X . Z X .. S N., for all j (j=1,2,...,m) (4-4) i=1 ‘13 i=1 C13 3 n. n. 2 xbi' + i Xcij S Nj, for all j (j=1,2,...,m) (4-5) i=1 J i=1 nd nc Z X .. + Z .. S N., for all j (j=1,2,...,m) (4-6) i=1 le i=1 °13 3 n n e g ) I X .. + 2 X .. 5 N., for all j (j=1,2,...,m) (4-7 i=1 ’13 i=1 313 J nf n8 2 X .. + Z X .. S N., for all j (j=1,2,...,m) (4-8) i=1 £13 i=1 3‘3 J uh n8 ( ) 2 .. + 2 X .. S N., for all j (j=1,2,...,m) 4-9 i=1 xhlJ i=1 ‘IJ 3 n2 up 2 X .. + 2 X .. S N., for all j (j=1,2,...,m) (4-10) i: 213 1:1 911 J 74 n X .. + Z X . S Nj’ for all j (j=1,2,...,m) 013 i=1 P1J n X .. + I X . S Nj’ for all j (j=1,2,...,m) qlJ i=1 plj weekday AM blocks weekday PM blocks weekday All-day blocks weekday Midday blocks Saturday AM blocks Saturday PM blocks Saturday All-day blocks Saturday Midday blocks Sunday AM blocks Sunday PM blocks Sunday All-day blocks Sunday Midday blocks the block number (i = 1, 2, ..., n) the garage site number (j = 1, 2, ..., m) block assignment (X = 0 or 1) (4-11) (4-12) the number of active buses assigned to a garage site. RelationshipiBetween Active and Total Vehicle Assignment. this point, only active buses assigned to garage sites have been dealt with. Since some spare vehicles must be stored in a facility in case of breakdowns, that the actual capacity of a site will be equal to the 75 number of active buses assigned to a garage, plus a spare factor (a). Also, the variable costs of garage operating cost must be equal to the number of active buses assigned the site plus the spares multi- plied by the variable operating cost per bus. Therefore, the variable operating cost per bus, 5, is re-expressed in terms of variable oper- ating cost per active bus, 0, where O = 5(1+a). Further, to force the operating fixed charge variable (2;) to switch on when active buses are assigned to a garage, a constraint is added to force 2; = 1 when N; > O and 2; = 0 when N; = 0. These relationships are stated below: (GOG) = 90(zg) + ocng) for all j (j = 1, 2, ..., m) (4-13) 1 subject to: N§(1+a) 5 K; for all j (j = 1, 2, ..., m) N; - B(Z§) s o, for all j (j=1,2,...,m) N; Z O, for all j (j = 1, 2, ..., m) where: (GOC)j = total garage operating cost for garage site j o = 5(1+o) spare factor maximum (m) capactiy of garage site j which may be greater :2 “'3' than the capacity of an existing garage if the facility can be expanded Z? = 0 or 1 J B = large number 2 max K for all j (j=1,2,...,m) 3 Garage construction costs must also be related to the total num- ber of buses (active plus spare buses) assigned to a garage. There- fore, the variable construction cost per bus, C, is re-expressed in terms of variable construction cost per active bus, C, where CfiC(1+a). 76 However, for a garage that is already built, fixed costs and variable costs were already expended in the original construction. When addi- tional buses are assigned to an existing garage beyond its existing capacity, additional spaces must be built only for the total number of buses assigned beyond the existing capacity. Since the fixed charge has already been sunk into the facility, it does not need to be assessed again when the garage is increased in capacity. This is stated below: (ace)j = FC(Z;) + C(Ng) for :11 j (j = 1, 2, ..., m) (4-14) subject to: N; z N; - x§/(1+a), for all j (j=1,2,...,m) N; - B z§ s o, for j s {x§=o} a; z o, for all j (j=1,2,...,m) where: ‘ (GCC)j = garage construction costs at garage site j c = '5(1+a) K; = existing capactiy (e) of garage site j (for sites not built, x; = 0) 2; = O or 1 Total Cost Minimization Model All three cost components have been related to a common indepen- dent variable, active buses assigned to a site. This common dimension allows the summing of all three in a total cost function. Minimizing the total cost function subject to the related constraints results in the determination of the minimum cost garage system. 77 The specification of the total model is shown on the two follow- ing pages. The total cost function (objective function) in Equation (4-15) sums all three variable cost components and the fixed charges. The functional constraint in Equation (4-16) forces every block to be assigned to a garage. The functional constraints in Equations (4-17) through (4-25) are the capacity constraints from Equations (4-4) through (4-12), but the capacity has been moved to the left hand side of the inequality. Equation (4-26) constrains the relationship be- tween the number of buses asssigned to a garage for the purpose of assessing operating and construction variable costs. The constraints in Equations (4-27) and (4-28) switch off and on the variable for operating and construction fixed charges, respectively. Equations (4-29) through (4'34) define the lower bound and/or upper bounds of decision variables. Sample Problem The following pages describe a small-scale problem that is solved through the application of the theoretical model. All costs are line- ar. However, the 0-1variables make the cost non-proportional. Thus, a linear program is not applicable, and a mixed integer program must be used. Mixed integer programing computer packages exist, and should be available through most large computer installations. The package used to solve the example problem is the IBM package MPSX- MIP/370.* The example problem contains four candidate garage sites. One site already contains a garage (site 1) with a capacity of six active *The MPSX-MIP/370 package uses Dakin's branch and bound algorithm to solve mixed integer programs (40,47). 78 nm {221' ..+Zj;.’F0(Z) all k i=1 j=1 kij xli =1 (k=a,b,...,q) min 2 = + I 0(N; ) + Z FC(Z§ ) + E C(N; ) j= -1 i=1 1= 1 m jil‘xkij = 1 for all i (i = 1, 2, ..., n) and for all k (k = a, b, c, ..., q) na nc o 2. X + Z X .. - N S O for all j (j=1 2,... i=1 Sij 1:]. Cl.) 1 ’ "b n. o E. xbij + E. xcij - N3 5 O for all j (j=1,2,... 1-1 1-1 nd nc o : X611 + 1:1 xcij - Nj s O for all j (j=1,2,... :5 x :8'x H° s o f 11 ( 1 2 , ‘I’ . . " . . .= 9 ' ‘ i=1 °1j i=1 3‘3 J or a J J ’ nh n o . .- .5 xhij + E xgij - Nj S O for all j (j-1,2,... l-l i 1 ng np o 2 X . + I X - N. S 0 for all j (j=1,2,... s o for all j (j=1,2,... z. x .. - N? s o for all j (j=1,2,... .m) .M) .M) .,m) an) .m) .m) :m) (4-15) (4-16) (4-17) (4-18) (4-19) (4-20) (4-21) (4-22) (4—23) (4-24) 79 n n p 2 x .. + 2, x .. - N? s 0 £0 all ' '=1 2 ... m 1:] (11,] 1:1 le J r J (J 9 a a ) N; - N; - K;/(1+a) s o for all j (j=1,2,...,m) u; - 3(2;) 5 o for all j (j = 1, 2, ..., m) N; - 3(zg) s o for all j s {1; = 0} NO 1 s K?/(l+a) for all j (j = 1, 2, ..., m) Restrictions 0 S inj i 1 for all k (k = a, b, ..., q); for all i (i=1,2,...,n) and for all j (j=1,2,...,m) o s z; s 1 for all j (j = 1, 2, ..., m) o s z; s 1 for all j (j = 1, 2, ..., m) 1, 2, ..., m) N; Z O for all j (j N; z o for all j (j 1, 2, ..., m) inj = 0 or 1 O or 1 N II N ll 0 or 1 (4-25) (4-26) (4-27) (4-28) (4-29) (4-30) (4-31) (4-32) (4-33) (4-34) 80 buses, which is also its maximum capacity. The spare factor is set at zero for the sake of simplicity. The non-productive transportation costs for all blocks to all candidate sites are shown in Table 4-1. The number shown in Table 4-1 were randomly selected from non-pro- ductive transportation cost estimates made during a study conducted for the Metropolitan Transit Commission (7). For the sake of brevity, there are no allsday and midday Saturday and Sunday blocks. The annual fixed garage operating charge and annual fixed garage construc- tion charge per garage are $2,000 and $1,000, respectively. The variable annual garage operating cost and annual garage construction cost per active bus are $10,000 and $3,000, respectively. To keep site 1 from exceeding its maximum capacity, it is upper bounded at six active buses. The procedure used to calculate the integer solution is a branch and bound search method. This entails first solving the problem without integer restrictions. Next, the program selectively fixes 0-1 variables to 0 or 1 and re-solves the linear program and then selec- tively resets 0-1 variables and re-solves the problem. The process continues to evaluate combinations of 0-1 variables (nodes) until an optimal solution is found. In the case of the sample problem, 28 nodes were evaluated. The optimal solution to the sample problem is $294,730, as shown in Table 4-2. Using the first value in the first column as an example of how to interpret the solution in Table 4-2, the AH weekday assign- ment variable of block one to garage one is equal to one and all other assignment variables for that block are equal to zero. This means that AH block one is assigned to garage one. All remaining assignment 81 Table 4-1 Example Non-Productive Transportation Costs (Annual) Block Type Site 1 Site 2 Site 3 Site 4 weekday AM (in dollars) al 3,577 3,462 4,939 4,301 a2 4,536 4,044 4,939 5,061 a3 3,348 3,672 4,128 7,560 a4 5,541 9,019 8,035 7,634 a5 9,552 4,449 4,442 6,122 a6 4,941 5,087 4,663 5,558 a7 5,676 4,304 4,365 6,234 a8 5,153 4,403 7,632 9,044 a9 8,817 10,732 4,748 4,179 a10 6,420 4,916 5,059 4,538 weekday PH b1 5,446 6,505 6,359 5,862 b2 5,207 6,262 5,230 4,959 b3 6,724 6,956 10,245 10,001 b4 9,751 7,162 2,300 4,972 b5 7,185 5,301 5,296 6,782 b6 5,469 5,168 5,386 5,640 b7 5,757 5,255 5,268 7,234 b8 5,428 5,428 7,540 8,907 b9 8,963 11,311 6,617 5,446 weekday.Allday c1 2,478 3,098 4,184 2,583 c2 2,361 2,978 2,718 2,593 c3 3,154 3,162 5,673 7,099 c4 6,260 7,076 5,867 6,020 weekday Hidday . d1 1,764 4,406 2,014 1,167 d2 1,167 1,443 2,284 2,478 d3 1,642 1,351 5,365 6,170 Saturday PM e1 458 581 853 424 e2 304 634 496 471 e3 611 642 1,391 1,353 e4 1,355 1,327 998 1,050 Saturday AM f1 1,331 1,572 945 1,780 f2 1,705 1,852 1,844 1,789 f3 1,624 1,687 2,317 2,749 Sunday PM 21 1,188 1,412 1,277 1,499 22 1,419 1,638 1,600 1,577 23 1,417 1,535 2,068 2,457 Sunday AM 01 1,105 867 1,468 1,001 02 1,145 817 1,047 1,086 03 754 822 977 954 82 Table 4-2 Example Optimal Mixed Integer Programming Solution* Variable Optimal Value Variable Optimal Value xall 1 xd23 1 xa22 1 xe11 1 X:13 1 X212 1 xa14 1 X'e13 1 xass 1 Xe34 1 xa36 1 x£31 1 Xa27 1 x£12 1 xa28 1 x£13 1 xa39 1 x2114 1 xazlo 1 x212 1 xbll 1 x213 1 xb12 1 x021 1 xb13 1 x022 1 xb34 1 x013 1 x1:35 1 N1 6 xb26 1 N; 4 xb27 1 N; 4 xb28 1 N; 4 x1:39 1 N; 4 x€11 1 z: 1 xc2 1 z; 1 xc13 1 z; 1 11:34 1 z; 1 deI 1 z; 1 Xc112 1 iVilues not shown are zero. 33 ' variables can be interpreted similarly. The variables N; (j=1,2,3,4) are equal to the number of active buses assigned to garage j for variable operating cost purposes. Notice that zero buses are assigned to garage four. The variable N; (j=1,2,3,4) is equal to the number of bus spaces that must be constructed at each site. The variables 2; and 2; (j=1,2,3,4) switch on the operating and construction fixed charges, respectively. Notice that 22 and z: are both zero, meaning that a garage has not been opened at site four. 4-2 Practical Implications of Theoretical Model Formulation The theoretical model was developed with the objective of formu- lating a model that accurately represented the problem and will derive an optimal solution. However, the practical implications of the model's use must also be tested. . In the theoretical formulation there is one integer restriction for each possible block assignment. Consider a realistic problem where the operator has 1,000 active buses, each averaging two block assignments per week. If there are 18 candidate sites (existing and potential garage sites) then there are 36,000 possible assignments. Since there may be as many as two 0-1 integer restricted variables per site, there are a grand total of 36,036 .integer restrictions. Al- though it is theoretically possible to solve a problem with this many integer restrictions, it is infeasible. For example, when Hairs et al. tried to solve a smaller fixed charge with 2,294 integer assign- ments and 20,815 variables, they permitted MPSX-HIP to run for 20 hours on an 1811 370/158 before interrupting the program (48, p. 1626). At that time, the program had not reached the first integer 84 node. Although it is impossible to predict how long one problem will run from the results of another problem, it is possible to see that run times of this relative magnitude make it infeasible to solve a realistic problem with the theoretical model. There are two problems with the theoretical formulation. These are: 1. Preserving the integer restrictions of 0-1 variables. 2. Developing an approach that is within the practical limits of normal computing resources. These two problems are dealt with and resolved separately in the following subsection. The two facets are then merged and the result- ing approach applied to a small-scale example to find an optimal solution. Integer Restrictions It is generally costly, in terms of computing time, to force an integer solution. However, there are naturally-occurring integer solutions to linear programs. One type of problem that results in a naturally-occurring integer solution is known as a classical transpor- tation problem. A transportation problem can be characterized as a flow from a number of sources (supply) to a number of sinks (demand). The reason that this kind of problem results in an integer solution is due to unimodularity of the matrix of functional constraints (49). To prove that a linear program is unimodular, the determinant of every basis must equal +1, 0, or -1. This is nearly impossible to prove, but, in general, a linear program is unimodular if it meets the fol- lowing necessary but not sufficient conditions (50, p. 126): 85 1. Every column contains at most one non-zero entry in every section of supply or demand constraints. 2. Every entry is 0 or :1 and the matrix of functional con- straints and the matrix can be partitioned into disjoint sets of rows such that: a. Two non-zero entries in a column with the same sign are not contained in the same set of rows. b. Two non-zero entries in a column with different signs are contained in the same set of rows. In the theoretical garage location model, the demand portion is the demand of block assignments for spaces in a garage. The supply portion is the storage spaces available for blocks in individual garages. However, i there are several different kinds of blocks, and thus there are different independent portions of the supply functional constraint matrix. Each block assignment variable appears once in the demand portion (assignment constraints) with a coefficient of one and only once in one group of constraints in the supply portion (the garage capacity constraints). For instance, a variable symbolizing an assignment of AM block i to garage j will appear once in an assignment constraint to insure that the block is assigned to one garage and in one AH capacity constraint, which insures that garage j can supply a space for block i. Although the portion of the function constraint matrix which includes the assignment and capacity constraints appears unimodular, the two types of constraints that switch off and on the fixed charge 0 variables (2 j and 2;) do not fit the two unimodularity necessary con- ditions. They fit into neither the demand nor supply portions of the 86 functional constraint matrix. Also, because the arbitrary large value B in these constraints is not +1, 0 or -1, its inclusion destroys uni- modularity. Therefore, to derive a naturally occurring integer solu- tion from the current model, the fixed charge functional constraints must be dropped. Without the fixed charge constraints, the assignment variables will naturally seek 0-1 integer values. The example problem is re- solved using a linear program without the fixed charges and the re- sults are shown in Table 4-3. Note that all variables are in fact integers. However, although the integer restriction of the assignment variables has been preserved, the integer values of the fixed charge switches (23’ and 2;) have not been preserved. Note that this can be overcome by constraining the capacity of garages to zero and thus im- plicitly setting its fixed charge to zero, or, alternatively, opening a garage by upper bounding its capacity at its maximum, and thus in- plicitly turning its fixed charge on. Practical Approach In the literature review, decision rules developed by Khumawala were discussed that can be used to efficiently eliminate nodes of fixed charge problems (27).* Khumawala's objective for development of his decision rules was to eliminate potential nodes of warehouse loca- tion problems through exploiting general properties of fixed charge problems. Although he uses a transportation problem to determine the optimal values of his assignment variables, his reasons for using a transportation problem was to be able to exploit its fast solving *See pages 25-27 of Chapter 2. 87 Table 4-3 Example Assignment Solved as a Transportation Problem* Variable Optimal Value Variable Optimal Value xall 1 Xd21 1 xa22 1 xc112 1 1‘a13 1 Xc123 1 xa14 1 xe41 1 xa35 1 xe12 1 xa36 1 xe13 1 xa27 1 xe34 1 xazs 1 x£31 1 xa49 1 X£12 1 xa410 1 X£13 1 x1:41 1 x211 1 xb42 1 X212 1 xb13 1 X213 1 xb34 1 x021 1 xb35 1 X013 1 sza 1 x022 1 1‘1:27 1 "1 6 Xb18 1 N3 3 X1149 1 N; 3 xcll 1 NZ 2 x€12 1 N; 3 xc13 1 N; 3 xc34 1 NZ 2 ;Values not shown are zero. 88 properties and not necessarily to cause an all integer assignment. Khumawala's decision rules have not been widely used because they re- quire that a minimum of 2x({K2}+1) transportation problems be solved, where {K2} is the number of sites that have not been fixed open or fixed closed. This presents a problem when there is a large number of candidate sites in the set {K2}. However, in the typical bus garage location problem there are relatively few feasible sites in comparison to the number of customers (blocks). This suggests that because the bus garage location problem is structured differently, the weakness of these decision rules may not present a problem. In fact, the example problem will be used to demnstrate that the use of these decision rules can be quite efficient. Example of the Practical Approach In the practical approach, the candidate sites are divided into three sets: set {K0}L where all members are fixed closed, set {K1} where all numbers are fixed open, and set {K2} where the sites have not been fixed open or closed. At the beginning of the process the sets {K01 and {K1} will be empty and the object is to place as many numbers of {K2} into either {Hg} or {K1} as possible through the two decision rules (delta and omega rules). The first step is to apply the delta rule which evaluates members of {K2} as candidates for {K1}. The delta rule is mathematically stated below: A1‘ = T[{K2}-k] - T[{Kz}] - Fk’ for k 8 {K2} where: T[] = The transportation problem including the members in brackets. Fk = Fixed charge of site k. 89 Decision: If Ak P. 0 then k 8 {XI}. The above delta rule means that when all sites that have not yet been fixed closed ({EZD are included in a transportation problem, the result will be the minimum possible (lower bound) variable cost (transportation plus facility variable costs) assignment. If k is removed and the variable cost increases by a sum greater than or equal to the fixed charge of leaving k open, then site k should be left open and becomes a member of {K1}. However, if the delta rule does not justify shifting k to {El}, it remains in {K2}. Once each site in {K2} is evaluated by the delta rule, then sites remaining in {K2} can be evaluated as candidates for {KO} through the omega rule. The omega rule is mathematically stated below: “k = T[{K1}] - T[{K1} U k] - Pk for k 8 {K2} Decision: If 0k S 0 then k 8 {Ho}. The omega rule means that if only sites fixed open {K1} are in- cluded in a transportation problem, the result will be the maximum (upper bound) of the minimum variable cost assignment to that point. If by opening site k the variable costs do not decrease by a sum greater than or equal to the fixed charge for having site k open, then k should be left closed and becomes a member of {K0}. The two decision rules can be run through until the sites re- maining in {K2} cannot be Opened or closed by the delta or omega decision rules. At this point, the remaining sites can be evaluated through a branch and bound process. However, the number of nodes to be evaluated (members of {K2}) are typically few. Further, because all assignment variables are naturally restricted to 0-1 by unimodu- larity, the need to branch and bound on integer assignment variable 90 nodes is removed. To illustrate this approach, the small-scale sample problem is solved using the delta and omega rules. First the delta rule is applied. This requires solving five linear programs, one including all fbur sites, and one when each site is removed (four more runs). The resulting delta values and the number of active buses assigned to each garage are shown in.Tab1e 4-4. Through the delta rule, sites 1 and 3 enter {K1} because their delta values are positive. Sites 2 and 4 remain in {Hz}. wa the omega rule is applied. This entails solving one linear program that includes sites 1 and 3. Then the solution to the first linear program is compared to two other linear programs solved with sites 1, 2, and 3 and with sites 1, 3, and 4. Note, however, that the two later combinations of three sites have already been solved during the testing of the delta decision rule. The resulting omega values are shown in Table 4-5. Because both omega values are greater than zero, neither site 2 nor 4 can be placed in set 1Ko1’ Therefore, to find an optimal solution, a branch and bound process is used. At the start of the branch and bound process, sites 1 and 3 are fixed open (2131,23=1). As illustrated in Figure 4-5, at that point there remain only three nodes to be evaluated. A linear program is used to evaluate each node and the fixed charges are added manually. Notice, however, all nodes had been previously evaluated during the delta rule testing and that no further linear programs were run. The optimal node includes opening sites 1, 2 and 3 (21:1,22=l and 23=1) and has a total cost of $294,730. This can be compared to the optimal solution found in the earlier application of the mixed integer program 91 Table 4-4 Application of the Delta Rule to the Sample Problem Delta Value Active Bus Assignments A1 = $20,295 N1 = 0, N2 = 6, N3 = 3, N4 = 5 A2 = $-141 N1 = 6, N2 = 0, N3 = 4, N4 = 4 A3=$691 N1=6, N2=5, N3=0, N4=3 A4 = $-600 N1 = 6, N2 = 4, N3 = 4, N4 = 0 Table 4-5 Application of the Omega Rule to the Sample Problem Omega Value Active Bus Assignments (22 = $818 N1 = 6, N2 = 4, N3 = 4, N4 = 0 04 = $359 N1 = 6, N2 = 0, N3 = 4, N4 = 4 92 C $295,184) ($294,730) C $295,330) Optimal Node Figure 4-5 Branch and Bound Tree of Sample Problem 93 to verify that, in fact, both arrive at the same solution. However, the mixed integer. program evaluated 26 nodes, while, through the use of the delta and omega rules, only six nodes were evaluated. Although no attempt has been made to solve a realistic problem with the theor- etical model (for example, 18 sites and 36,000 assignment combina- tions), it is believed that the difference in computational effort between the two would be even more striking. Applicability of the Practical Optimization Technique To judge the applicability of the selected optimization tech- nique, three questions relative to the selected approach need to be answered:* 1. Is the selected methodology applicable to the structure of the cost functions? 2. Is the selected methodology efficient? 3. Is the model adaptable to different types of garage system constraints and planning criteria? Each of these questions is dealt with individually in the follow- ing paragraphs. Mlicability to the Structure of Cost Functions. There are three costs considered in the model: garage operating costs, garage construction costs, and non-productive transportation costs. The garage operating and construction costs for two operators were exam- ined, and both contain a fixed charge and an approximately linear variable charge. In the model, garage operating and construction fibese questions were originally stated as criteria for methodology selection in page 9 of Chapter 1. 94 costs are represented with a fixed charge and a linear variable por- tion. Non-productive transportation costs are a unique cost for the assignment of each block to each garage. A block can be assigned to one and only one garage, and the corresponding non-productive trans- portation costs are assessed to the assigned garage. The model ac- counts for non-productive transportation costs by multiplying the actual block assignment's non-productive transportation cost by one and all others by zero. Hence, all three costs are symbolized in the model with the exact structure of the respective cost function. Methodology Efficiency. The methodology developed makes use of two attributes to make it efficient. First, the model structures the problem as a transportation. problem. The transportation problem structure permits the solution to be derived much more quickly than a similar linear program without this structure (16, p. 118). Second, the model exploits Khumawala‘s decision rules to eliminate possible nodes efficiently. These two attributes together permit the method- ology to converge quickly on an integer solution. Adaptability of the Model. The methodology developed is only a generalized model. The model may be tailored to fit the special needs of a transit agency by defining any of the cost parameters and con- straints to suit its special needs. For example, suppose a candidate site is at a controversial location and that locating a garage at that site will penalize the operator with respect to community relations. If the penalty can be equated to a dollar value, this amount can be added to the fixed charge of occupying the site. Another adaptation of the model might include increasing the variable portion of the con- struction costs for one site because of some particular difficulty in 95 building at the site. Still another adaptation might occur where ex- isting sites are assumed to have a salvage value. To account for this, the fixed charge for keeping an existing facility open should include the annualized opportunity cost of not selling the site. Another might include increasing the variable operating cost parameter of an older garage relative to newer garages to account for the de- crease in efficiency when operating an older structure. As these examples demonstrate, it is possible to adapt the model to almost any condition. 4-3 3mg In this chapter, two garage site selection models were developed. The first is considered to be a theoretical model and is used as a basis for developing a second model. Thetecond model reaches an op- timal solution to the site selection problem by using two efficient shortcuts. First, the problem is formatted such that, given a set of garages and a set of capacities for each, 'the optimal assignment of buses to the given set of garages can be determined by running a transportation problem. Then, by selectively opening and closing sites according to two decision rules and running successive transpor- tation problems, an optimal solution is reached. The method is adaptable to almost any condition and uses software that should be available through most computer installations. The next chapter demonstrates the use of the model on a real-world Detroit case study. CHAPTER 5 CASE STUDY The sample problem in the preceeding chapter provided a simple example of the garage site selection methodology. This chapter demon- strates the model's use on a Detroit case study. Detroit is chosen because the data is readily available, and because the Detroit system is currently in desperate need of an additional garage. The total regional system is made up of two transit operators, the Southeastern Michigan Transportation Authority (SEMTA) and the Detroit Department of Transportation (D-DOT). The application of the model to the com- bined system of SEMTA and D-DOT should prove the model’s capability to solve even large-scale problems. In the case study, every reasonable attempt is made to use the actual characteristics of the Detroit transit and highway systems. However, the case study is only intended to demonstrate and test the methodology; it is not intended to be a plan or a critique of the Detroit area’s transit facilities. Therefore, where actual infor- mation from the Detroit system is unavailable, realistic assumptions are made and justification for these assumptions is given along with instructions on what should be done in the case of an actual site selection study. The first section of the case study describes the site identifi- cation process. This is followed by a section describing how the 96 97 Detroit system is characterized for the model. The third section explains how the cost parameters are generated. The fourth section describes the model's application. and results. The last, section examines the sensitivity of the case study's solution to the avail- ability of different sites and of various attributes of the sites selected. 5-1 Site Identification Process Because the objective of the case study is to demonstrate the model and not to demonstrate how to identify candidate sites, a leng- thy site identification process is not necessary. However, two steps were used to identify new sites in an effort to identify reasonable candidate sites and thus make the case study realistic. First, the advice of the Southeastern Michigan Transportation Authority (SEMTA) staff was sought on reasonable candidate sites. Second, criteria were developed for the identification of additional candidate sites. Those criteria are: 1. The candidate site should be relatively near (i.e., one mile or less) a major arterial or freeway. 2. The site should not be occupied by a structure that is cur- rently in use and the adjacent area should be of a similar land use (i.e., industrial, warehousing, or light comer- cial). The candidate and existing sites are shown on the map in Figure 5-1. There are seven existing sites, each labeled with a solid cir- cle. There are ten candidate sites, each labeled with a solid tri- angle. A total of seventeen sites (seven existing and ten candidates) 98 "'7‘!- 53 / mu: son ”“1. .080 eons 9. mt! --— 1)! new“ “1> ' . see; l. 1"" D 010 ! 5 l- 75 Figure 5-1. Legend Existing Garages 0 Candidate Sites A Detroit Site Map 99 is a fairly typical number for a garage location study. For example, recent studies conducted for the transit operators of Minneapolis-St. Paul, Oakland, Louisville and St. Louis considered a total of eleven, twenty, nine and sixteen sites, respectively (7,3,13,14). The candidate sites labeled 1, 5, 8, 9 and 10 are sites suggested by SEMTA staff. Site 1 is located in a light comercial-industrial area and is in close proximity to a garage SEMTA abandoned in 1979. It is also adjacent to 1-94 and the major arterials Michigan Avenue and Ford Road. Site 5 is currently used as a parking lot fOr Detroit Public Works garbage trucks. It is adjacent to I-96 and the South- field Freeway. Site 8 is located at the fringe of the urban area, and vacant land is still available in this “area. It is close to the outer ring freeway (I-275). SEMTA is currently attempting to purchase site 9, but has met with resistance from the local municipality. It is near both I-696 and I-275. Site 10 is located in an industrial-comercial strip area. There is vacant property in the area and the site has access to 1-696. 1 The remaining candidate sites were identified through field trips aimed at searching out vacant properties that meet the two locational criterion. The resulting concentration of candidate sites to the south and west of Detroit is intentional. The reasons for this are: 1. The availability of sites in close proximity to major travel corridors. 2. Previous SEMTA studies had indicated that the Coolidge Garage (existing Facility 1) should be increased in size if the only consideration were to minimize deadhead travel. However, it was deemed impossible to enlarge the existing lOO facility because of abutting land use, and previous studies opted to recomend distant suburban locations. Nonetheless, the findings of previous studies imply that locations in nearby areas could be desirable. 3. SEMTA already has two facilities to the north and northeast (existing sites 6 and 7). It is unlikely that another ga- rage should be located to the north of Detroit. On the other hand, SEMTA plans to abandon its only southwest site (existing facility 4), and hence there soon will be a void in garage space to the south and west of Detroit. Candidate site 2 is currently used as a storage lot for construc- tion equipment and its only structure is a small pole barn. It is located in the industrial area abutting I-96. Candidate site 3 is a large piece of vacant property, and is near a major arterial, Ford Road, and the Southfield Freeway. Candidate site 4 is currently a field owned by the Detroit Public School system. Although it abuts a residential area on two sides, a number of the surrounding houses are vacant. On the other sides, the property abuts I-96 and light in- dustrial facilities. Candidate site 6 is located in an industrial area with scattered vacant sites. It has access to I-75 and a major arterial, Fort Street. Candidate site 7 is a large vacant lot and is adjacent to the Southfield Freeway and close to a major arterial, Michigan Avenue. ' Admittedly, some of these sites may in fact be unavailable for use as garage locations, and if this study were being conducted for the Detroit area transit operators, investigations would need to be conducted to determine ownership, zoning, political feasibility and 101 other characteristics of the site. Because the sites are identified only for the purposes of demonstrating the model, this is unnecessary. 5-2 Cost Parameter Generation Parameters for all three types of costs (garage operating costs, garage construction costs and non-productive transportation costs) are estimated for the Detroit operators. Specific cost functions are estimated for the Detroit transit systems operating and construction costs. However, non-productive transportation costs are unique for every block-garage site combination. Hence, a Detroit specific cost function is not estimated and instead a generalized approach to esti- mate unique costs for each combination is described. Garage Operating_Costs Although SEMTA made its cost records available, it only operates four of the seven existing garages and the facilities it operates are all less than 100 vehicles in capacity.* Since it is beyond the scope of this study to conduct an in-depth engineering analysis of operating costs, an existing garage operating cost funCtion of another operator is used by adjusting it to match past Detroit area costs. The garage operating cost estimates made for AC Transit are the most recent available (1980)(3). They divided their operating costs into four portions: transportation staff (bus and driver scheduling), extra boards,” maintenance and stores staff, and shop employees. * All SEMTA information was made available to the researcher during numerous meetings and phone conversations during 1980 and 1981. **For an explanation of extra boards, see glossary. 102 SEHTA, unlike AC Transit and most other operators, does not maintain extra boards. This is mainly due to the difference in labor relations between SEMTA and its drivers. Nonetheless, if the costs of extra boards are subtracted from the AC Transit estimates, SEMTA costs for their three moderately sized garages (Oakland, Wayne and Macomb ga- rages) tend to be approximately 15%.above AC Transit‘s estimates for a similar size garage. For example, the Macomb facility houses ap- proximately 87 buses and the total cost to operate this facility (in- cluding maintenance, stores, shop and schedule labor) during the 1980 fiscal year was $911,796. The AC Transit operating cost estimates, excluding extra boards, for a garage of 87 buses is approximately $805,000 (estimated). For the purposes of this study, garage operat- ing costs are estimated to be equal to AC Transit’s operating costs, minus extra boards, factored up 1.15. The resulting equation is: Total Annual _ (Number of Buses Garage Operating Cost - 192’412 + 9403 Assigned to a Garage) Because values of garage capacity range from only 30 to 300 buses in AC Transit's cost estimates, little is known about the cost function beyond this range . Garggg Construction Costs The only construction cost information available through SEMTA is the actual costs incurred when it built the Wayne garage. Again, because of the paucity of locally-generated cost information, the approach taken is to rely heavily on AC Transit cost estimates (3). Their estimates are contrasted with those costs actually sustained by SEMTA to correct for differences. 103' In comparing the AC Transit cost estimates with the costs for constructing the Wayne facility, the two are seen to be quite similar, with the exception that SEMTA's property costs are much less. AC Transit used a value of $160,000 per acre to purchase the land while SEMTA costs for the Wayne garage are $60,000 per acre. Using the actual costs of the loo-vehicle capacity Wayne garage for comparison, if AC Transit's property costs are reduced to $60,000 per acre, then extrapolating their cost estimates to a loo-vehicle garage results in a estimated cost of $3,186,000. The cost of the Wayne facility is $3,284,680. Hence, once the adjustment is made in property costs, the two appear close enough for practical purposes. To arrive at an an- nual cost, a 25-year life discount rate of 9 percent is assumed.* The resulting equation is: Total Annual Garage Construction Cost (Number of Buses Assigned to a Garage) = 68,933 + 2,899 Non-Productive Transportation Costs To estimate the costs of various facilities, the non-productive transportation costs must be determined for operating all blocks out of all sites. In this way, the cost of any garage at any capacity and any possible combination of sites may be assessed with respect to its non-productive transportation costs. A simplified two-garage example is presented here to demonstrate the use of the technique. The solid line in Figure 5-2 is the path of route 1 and the dashed lines are the deadheading paths to the two garages, A and B. This example considers only the first three blocks on the route, which *A discount rate of 9 percent is used by both SEMTA and AC Transit. 104 have the pullout and pullin assignments shown in Table 5-1. In devel- oping the cost estimates, only the total costs of the times and dis- tances along the minimum-cost paths between the garages and the pull- outs and pullins, respectively, are of concern. Thus, instead of dealing with miles or minutes of distance, the costing operation deals with dollars of distance, along the minimum-cost paths. For example, the costs in Table 5-2 were generated as examples of costs of the deadheading legs. The non-productive transportation costs of blocks 1, 2, and 3 are shown in Table 5-3. The costs of blocks 1 and 2 are the sums of their deadheading cost paths; however, the cost of block 3 is a little more difficult to calculate. Block 3 has 3 reliefs and, because a relief can be made directly from Garage A, relief from Garage A has no cost. There is no transit link between Garage B and route 1. If block 3 were to come from Garage B, relief would have to be made by making 3 round trips to point E at a cost of $2 per one-way trip, or $12 for all 3 round trips. Therefore, a cost of $12 is assigned to block 3 coming from Garage B, making it less costly to assign the block to Garage A. To estimate the non-productive transportation costs for the De- troit case study, the metropolitan area (UTPS) computerized highway network is used (51). The network contains average speed and length of highway links. The mileage cost (the cost to operate a bus per mile) and the time cost (the driver's wage per minute) are applied to the UTPS highway network and the UTPS module UROAD will determine the minimum cost paths and accumulate the costs from every centroid to every other centroid. The result of the UROAD module is recorded in card images through another UTPS module UMCON. 105. ..-""' I\ -“‘ l\ Garage A l \ I .\ 5‘ ~ 3 D Route 1 Deadhead path 7Figure 5-2. Example Garage layout 106 Table 5-1 Examples of Pullout and Pullin Assignments Route “slack Pullout “Pullin Rem“ Time Number Number Point Point 1 Period 1 1 E C 0 AM 1 2 D C 0 AM 1 3 E C 3 All Day Table 5-2 Examples of Deadhead Time and Distance Costs Li Garage A Garage B Travel to Travel to Point Cost Point Cost C $ 4 C $17 D $ 8 D $10 E $16 E $ 2 107 Table 5-3 Examples of Non-Productive Transportation Costs Table 5-3A Garage A fioute Block Pullout Pullin Reliefs Total Number Number Cost Cost Cost Cost 1 1 $16 $ 4 $ 0 $20 1 2 s 8 $ 4 $ 0 $12 1 3 $16 $ 4 $ 0 $20 Table 5-3B Garage B Houte (Block Pullout Pullin Reliefs Total Number Number Cost Cost Cost Cost 1 1' s 2 $17 3 0 $19 1 2 $10 $17 s o $27 1 3 $ 2 $17 $12 $31 10.8 Centroids can be moved or created so that they are located ap- proximately at every pullout and pullin point and at every garage lo- cation. In this way the costs of traveling from every pullout and pullin point along the minimum-cost path to every existing or pro- spective garage site may be ascertained. The advantage of this meth- odology is that the transportation costs are not estimated through a monotonic function (i.e., Euclidian, squared Euclidean or rectalinear distance), but rather are estimated with a simulation of the highway system.wbdch more closely approximates the actual costs between.every pair of points of interest within the system. Using the distance and time costs derived from the computerized highway network, the total actual non-productive transportation costs to serve all blocks from all garages are estimated. SEMTA and D-DOT run guides (block descriptions) are used to lo- cate the centroids corresponding to the block pullout, pullin and relief points. If centroid locations deviate greatly from a specific point, the centroid should be moved to the approximate location of the point in interest. After ensuring that all centroids are approximate- ly at these points and approximately at site locations, the UTPS modules can be run.* SEMTA records show that during fiscal year 1980 bus operating costs were 39¢ per mile and average driver wages, in- cluding all benefits, were 22¢ per minute. These values are used as parameters in the UROAD module to determine the cost of the minimum cost path from all centroids to all centroids. These values are then *Minor deviations from the exact location should be of little conse- quence because the computer network itself is only an approximation of travel times and distances and is not an exact measure. 109 manipulated in a manner similar to the example given in Figure 5-2 and Tables 5-1, 5-2 and 5-3. The resulting values are multiplied by a factor to equate block costs to annual costs. Weekday blocks are mul- tiplied by 255 (approximately the number of weekdays per year minus the number of national holidays) and Saturday and Sunday blocks are multiplied by 52 (the number of weekends per year). Once the non-productive transportation costs are calculated, all model parameters are known. However, before the model can be struc- tured, the system characteristics must be determined so that the model accurately symbolizes the transit system. 5-3 System Characterization In this section, the Detroit system is characterized. This re- presents the way in which the modeler perceives the possible options for expanding existing and candidate facilities. For instance, one existing facility may be constrained to its current capacity because adjacent land is unavailable for expansion. It is quite likely that each alternative characterization would result in a different optimal solution. It is possible to consider different characterizations of the transit system to answer "what if" questions. For instance, in the event that adjacent land were available, what would be the minimal total system cost? The model is equipped to answer this type of question, but in the case study a single system characterization will be used. Case Study Characterization One of the problems faced by both Detroit operators is that 110 neither can store all its buses inside. D-DOT has three facilities (see Table 5-4). Although it stores approximately 185 buses outside, almost all of its active buses are stored inside. From D-DOT's fall 1980 run guides, it is estimated that the maximum number of blocks D-DOT must service at any one period requires 630 buses. Thus, be- tween the three D-DOT garages there must be a combined capacity for 630 active buses. The Coolidge and Gilbert garages are assigned capacities equal to their current number of indoor storage bays. There then remain 160 active buses to be assigned to the Shoemaker garage. This is slightly more than its number of existing indoor storage bays. It is unlikely that the D-DOT garages could be expanded to store more buses. A previous SEHTA study ruled out the possibility of expanding the Coolidge garage and it is unlikely that the Gilbert garage could be expanded because it abuts residential property. The Shoemaker facility is planned to be enlarged, but the result will be that more of the inactive buses will be stored indoors. Therefore, each of these facilities is fixed at approximately its current cap- acity. SEMTA's plans for its existing and proposed facilities are cur- rently in a state of change. Therefore, the decision is made to fix its garages' capacities approximately equal to the current (1980) indoor storage capacity. Further, since both the Oakland and wayne facilities can be expanded, they are both assigned maximum active bus capacities of approximately double their existing capacity. The Wyandotte facility has indoor space to store only five buses and SEMTA currently plans to phase it out of service when this becomes 111 Table 5-4 Existing Detroit Garages* Table S-AA D-DOT Storage Facilities Facility Description Gilbert Shoemaker Coolidge (Site 1) (Site 2) (Site 3) Buses Assigned 279 287 318 Service Days 25 33 25 Storage Bays 225 146 245 Total Indoor Bays 250 179 270 Buses Stored Outside 29 108 48 Table 5-43 SEMTA Storage Facilities Facility Description wyandotte Wayne Oakland Macomb (Site 4) (Site 5) (Site 6) (Site 7) Buses Assigned 19 1 82 93 87 Service Bays 0 12 11 7 Storage Bays 5 90 85 70 Total Indoor Bays 5 112 96 77 Buses Stored Outside 14 0 0 10 *Taken from (9). 112 possible (see Table S-b). If the model is to consider a do-nothing option (maintain and expand only existing sites) there have to be enough spaces for active buses to make a do-nothing option feasible. The existing and proposed SEHTA service through 1985 requires that there be enough active buses in the SEHTA system to service approxi- mately 434 blocks at one time. If the Wayne and Oakland facilities are expanded to double their existing capacity (to approximately 180 active buses each) and the wyandotte facility is phased out there must be ample space for 74 active buses stored in the Macomb facility. This is slightly greater than its existing indoor capacity of 70 bus bays, and makes the do-nothing alternative infeasible. Therefore, the Macomb capacity facility is increased to a maximum capacity of 77 active buses, which is equal to its current number of storage and service bus bays. Currently, most inactive 'buses (spares) are stored. outside, except at the wayne garage. Presumably, at least in the future, new garages and expanded facilities will store all buses inside. If the current policy of storing inactive buses outside at existing facili- ties is maintained and expanded facilities are assumed to have ample capacity for all assigned buses, construction variable cost for new bus bays must be multiplied by an expected spare factor. SEHTA staff recommended a ten percent spare factor, and thus construction variable costs as well as garage operating variable costs are increased by ten percent. Using this system characterization, the model is applied to the combined Detroit systems. This characterization only represents the way in which the transit systems are constrained for the case study. 113 The next step is to apply this characterization to the model and select sites and estimate costs. The results of the model application are described in the following section. 5-4 HOdel Application The solution approach is the same as the practical methodology developed and applied to a sample problem in the previous chapter. Figure 5-3 shows a flow chart which summarizes the approach. First, the initial list of sites is developed. Then the model enters the delta rule phase and all sites are tested to become either fixed Open (set {K1}) or remain undecided (set {K2}). Then the model enters the omega phase and all sites remaining in {K2} are tested to become ei- ther fixed closed (set {Ko}) or remain in set {K2}. Sites remaining in {32} enter a branch and bound phase and the result is an optimal solution. In the case study, there are 17 garage sites (seven existing and ten candidates) and approximately 2,300 blocks.* This creates approx- imately 39,000 possible block assignments. A problem created by the magnitude of the case study is the amount of computing time necessary to solve a 39,000-variable problem starting from the original data. Because the planned approach neces- sitates running the problem several times, for the sake of efficiency, rather than to start from the original data at every iteration another approach is taken. *Blocks are determined from Fall 1980 SEMTA and D-DOT run guides and from SEMTA's projected 1985 runs. 114 moan mason was museum muowuum momoz unfinwsmum unannouon 3: hwoaovonuuz mo guano scam mum ouswmm ”one one as a tease ”an“ new as a moron a «new amok mass amuse he common on on Amwxweav a mafia uuoaum a «new sees «Ham wagon he aw unwnfismum Aevoumm been umsnm mason can museum commas on o» a scam uuoaum as» umwfl ream steam UV sesame“ no» woman yawn omsnm sumac unamm sauna 115 The changes made at every iteration of the modeling sequence re- present only local changes in the assignment variables. At every iteration garages are selectively opened or closed. Physically, this means that the buses assigned to the facility affected are reassigned either to or from neighboring facilities. This suggests that it would be efficient to start at the previous optimal basis (the solution of the last linear program) and revise the constraints and solve the new problem. Further, it would be more efficient to start from a basis which is already feasible (a basis that does not violate any con- straints) for, the revised problem. Therefore, the raw data are used only once, and from that point on future iterations are solved with an already optimal and, if possible, a feasible basis from a previous iteration. Another change made from the original problem .is to drop the variable garage operating costs from the objective function. As des- cribed earlier, operating variable costs per bus are a. constant ($9,400 x (ll-101.) per year) times the number of active buses assigned to the garage site. Since all active buses must be assigned to one and only one site, the total system variable garage operating costs ‘will be equal to the total number of active buses in the system (1064) times the variable garage operating cost. Variable garage operating costs will be a constant of approximately $11,000,000 for all possible combinations of sites. Therefore, it can be dropped from the ob- jective function with no impact on the results. However, to obtain the total system-wide garage-related costs (total cost) for any combi- nation of sites, this constant has to be added to the other costs that are included in the objective function. 116 Delta Decision Rule. The first step in the decision rule is to run the transportation problem with all variable costs (garage construction variable costs and non-productive transportation costs) and all garage site capaci- ties upper bounded at their maximum. The second step is to set the upper bound of the capacity of one garage equal to zero, rerun the transportation problem, and calculate the difference in total variable cost from the first to the second run. If the variable costs increas- ed by a sum greater than the removed site's fixed charge, the site is to be fixed open. The third step is to select another garage and iterate back to step two until the list of sites is exhausted. The running of the problem with all upper bounds set equal to the site's maximum capacity is the only time the problem is to be run with * the raw data. From that point onward, the basis of a previous run is revised. The initial solution took approximately thirteen minutes to solve.* The solution is listed in Table 5-5. Note that all existing garages were filled to their existing capacity. This is primarily because the variable cost of constructing a space for each active bus at a new site is $3,190 ($2900x(1+10%) per year, and although the an- nual non-productive transportation costs vary from site to site, they seldom vary by as much as the construction cost. Therefore, even though a candidate site may have the least non-productive transporta- tion cost assignment of a block, the non-productive transportation cost differential between the candidate and the existing sites is typically less than the construction cost of building a space at a new site. *On an Amdahl 470V/6. 116 Delta Decision Rule. The first step in the decision rule is to run the transportation problem with all variable costs (garage construction variable costs and non-productive transportation costs) and all garage site capaci— ties upper bounded at their maximum. The second step is to set the upper bound of the capacity of one garage equal to zero, rerun the transportation problem, and calculate the difference in total variable cost from the first to the second run. If the variable costs increas- ed by a sum greater than the removed site's fixed charge, the site is to be fixed open. The third step is to select another garage and iterate back to step two until the list of sites is exhausted. The running of the problem with all upper bounds set equal to the site’s maximum capacity is the only time the problem is to be run with “ the raw data. From that point onward, the basis of a previous run is revised. The initial solution took approximately thirteen minutes to solve.* The solution is listed in Table 5-5. Note that all existing garages were filled to their existing capacity. This is primarily because the variable cost of constructing a space for each active bus at a new site is $3,190 ($2900x(1+10%) per year, and although the an— nual non-productive transportation costs vary from site to site, they seldom vary by as much as the construction cost. Therefore, even though a candidate site may have the least non-productive transporta- tion cost assignment of a block, the non-productive transportation cost differential between the candidate and the existing sites is typically less than the construction cost of building a space at a new site. *On an Amdahl 470V/6. 117 Table 5-5 Transportation Problem Including All Sites Sites Existing Expanded Tatal Capacity Capacity Capacity Existing Sites (Gilbert) El 225 0 225 (Shoemaker) Hz 160 0 160 (Coolidge) 33 245 0 245 (Wyandotte) E4 5 0 5 (Hayne) E5 90 0 90 (Oakland) E6 90 23 113 (Macomb) E7 77 0 77 Candidate Sites C1 0 27 27 C2 0 3 3 C3 0 7 7 C4 0 4 4 CS 0 58 58 C6 0 4 4 C7 0 4 4 C8 0 5 5 C9 0 18 18 C10 0 19 19 Total Variable Cost = $6,006,576 Total Cost Including Fixed Charges = $20,972,181 118 The delta decision rule dictates that an additional 17 transpor- tation problems he run. However, experimentation proved that for sites with only a few active buses assigned, for instance candidate site 3 (with only 7 active buses assigned), the problem would take a minimum of one and one-half minutes of computing time to solve. For sites with a large number of active buses assigned, for instance the Coolidge garage with 245 active buses, the problem would take as much as nine minutes of computing time to solve. Even though each run would start from the previous basis, these lengthy run times are incurred because whenever a site is switched off, the previous solu- tion becomes infeasible, which greatly increases the time necessary to solve the problem. To alleviate this problem, an alternative method is developed. Intuitively, it can be seen that by switching off one candidate site, the maximum increase in total variable costs will be the differ- ential in non-productive transportation cost between the blocks as- signed to the site turned off and the next least non-productive trans- portation cost site. The delta rule dictates that a site will be fixed open if the increase in variable costs due to excluding a site is greater than its fixed charge. Therefore, the sum of this differ- ential for all blocks assigned to a candidate site would then have to be greater than the operating fixed charge plus the construction fixed charge ($261,345). Since none of the candidate sites are great dis- tances from one another, the differential from one candidate site to the next in non-productive transportation cost per block should not be very great. Therefore, it is highly unlikely that any of the candi- date sites could be fixed open based on the delta decision rule and 119 therefore application of the delta rule is omitted for all candidate sites in the case study. Thus all candidate sites remain an element of the undecided set ({KZD. Later, all candidate sites will be evaluated by the omega rule to determine if they can be shifted to the set of closed sites ({X°}). Now that all candidate sites have been left in set {K2}, only the existing sites remain to be evaluated. However, with seven existing sites to evaluate, the prospect of using as much as nine minutes of computing time per site is not very satisfactory. Therefore, an alternative approach is again offered. For each existing site that is removed from the problem, an equal number of garage spaces for active buses will have to be built at a candidate site or added at an existing site. For instance, if the Coolidge garage is removed, 245 active buses spaces will have to be built at other sites within the system at a cost of $3,190 per space. In addition, at the very minimum, the total non-productive transpor- tation cost will change by the differential in cost of blocks current- ly assigned to the Coolidge and the least non-productive transporta- tion cost of assigning that block to any candidate site or an expand- able existing site. This is stated mathematically in Equation (5-1) for existing garage j. The value Vj in Equation (5-1) is the minimum increase in cost of eliminating existing garage j. The first portion of Equation (5-1) is CH} which is the variable construction cost, C, times the number of spaces for active buses available at garage j, Kg. The other portion is the differential in non-productive transpor- tation cost between a block assigned to existing garage j and the min- imum non-productive transportation cost of all candidate and expand- 120 able existing garages summed over all blocks assigned to garage j. min V3 = CK. + Z 2 [T . - min(T )] (5-1) allk v=1 “1‘ Wk where: k = the block type (k=a,b,....q) v : the block number, vs{i} where for all Xij = 1, v = i, with nk blocks per block type k w = an index of all candidate sites and existing site that can be expanded V. = the change in total variable costs due to switching off existing garage site j . C = the variable construction cost per active bus N -n u the existing number of active buses that can be assigned to site j Xij = the block assignment variable, if xij = 1 then block i is assigned to garage j. The minimum possible value for delta is then: min Aj = min V3 - Fj (5-2) where: F = the fixed charge of site j It is also true that, at a minimum, the differential in non-pro- ductive transportation costs between a block assignment to an exist- ing garage and the least non-productive transportation cost candidate or expandable existing site assignment for every block plus the garage construction cost per bus must be greater than or equal to zero. For purposes of illustration, suppose this were not true. For example, assume that the annual non-productive transportation cost for a block 121 assignment to candidate site 10 is $3,000, while the same block as- signment to the Macomb garage (E7) is $6,500. Assigning the block to candidate site 10 means that the maximum variable cost for that block is the sum of the non-productive transportation cost ($3,000) plus the cost of constructing a space ($3,190) at candidate site 10 to house the active bus to service the block. The maximum total variable cost attributable to the block being assigned to candidate site 10 is $6,190. If the same block is assigned to the Macomb garage, the vari- able cost attributable to the block is $6,500, which is greater than the cost of assigning the block to candidate site 10. Therefore, the block would never be assigned to the Macomb garage and blocks will only be assigned to an existing facility if the variable costs attrib- utable to their assignment to an existing facility are less than or equal to the variable costs of assigning the block to an expandable existing site or a candidate site. This condition is mathematically stated as: 0 § C + [ijk - min(vak)], for all k, (k=a,b,...,q) and for all i (i=1,2,...na,nb,...nq) Thus, the maximum non-productive transportation cost differential between a block assigned to an existing garage and its assignment to a candidate or an expandable existing site is -$3,190. Now, assume that AM blocks, PM blocks and allday blocks that are assigned to existing garages are divided into two groups, those with non-productive trans- portation costs differentials when compared to the minimum cost candi- date site or an expandable existing garage that are greater than or equal to zero (lower non-productive transportation cost at an existing garage), and those that are less than zero. If the group that is 122 greater than zero is arranged into active bus equivalents (an AM block plus a PM block or an all-day block), it can be seen that, for every active bus space not available because an existing garage is removed, the total variable costs will increase by a minimum of the construc- tion cost. For the blocks in the group that are less than zero, for every active bus equivalent that is no longer available because an ex- isting garage is removed, total variable costs will increase by a maximum of zero for every all-day block and a maximum of $3,190 for every pair of AH and PH blocks. By going through the result of the transportation problem with all sites Opened and counting the number of blocks assigned to a garage that fall into each of these two groups and calculating the minimum possible cost differential for removing an existing facility, the minimum delta value can be calculated without rerunning the prob- lem. For example, the Gilbert garage has 225 active buses assigned to it (see Table 5-5) and, through a comparison of costs for each block assigned to Gilbert, 167 block equivalents to active buses were found to have non-productive transportation cost differentials greater than or equal to zero. Of the remaining 58 active bus equivalents, 11 are all-day blocks and 47 are combinations of Ali and PM blocks. ' Therefore, the minimum possible delta value is 167 times $3,190, minus 11 times zero, minus 47 times $3,190, and minus its fixed charge of $192,412. The total is equal to $190,388, which is greater than zero, and thus, by the delta rule, the Gilbert site should be fixed open (set {K1}). All the other existing garages were evaluated in a simi- lar manner, and only the Wayne and Wyandotte garage could not be fixed open. Both Wayne and Wyandotte facilities had their delta values 123 manually calculated (to conserve computer cost) through Equations 5-1 and 5-2. The Wayne facility had a positive delta value ($141,573), while the Wyandotte facility had negative delta (-$145,294), which is reasonable considering that Wyandotte has a capacity of only five buses. After applying the delta decision rule, all existing garages ex- cept the Wyandotte facility are fixed open and become members of set {K1}. Wyandotte and all the candidate sites remained members of the undecided set {K2}. Next the omega decision rule will be applied to justify fixing sites closed and make them members of the set {K0}. MLDecision Rule. The first step in the omega decision rule is to run a transporta- tion problem with the capacity of all sites not included in set {K1} fixed at zero. This meant revising the basis from the first run and rerunning the linear program. This took approximately ten minutes of computing time. The result is shown in the first column of Table 5-6, where $6,624,101 is the minimum total variable cost for the problem T[{K1}]. The next step is to open one facility from {Hz} at a time and rerun the transportation problem. Each of the runs of the linear programing package took between one and one-half to four minutes of computing time. The reason for the relatively short runs is because the basis that is revised is the solution to the problem including members of only {K1}. This means that each run started from a feasi- ble basis. Existing site 4 (Wyandotte) and candidate sites 1, 2, 3, 6, 7, 8, 9 and 10 are eliminated because their omega values are less than zero. 124 mne.enaueue am_.me-mumuc aae.ee-au~ua eem.e-au_ua eee.~mw-nemc eese> emcee e c e e e e We e e e e e e no e e e e e e no e e e e e e on e e o e e e no e e e e e e so ems e e e e e no e em a e e e «u e e nee e e e nu e e c has e e o madam oumthflmu he he he he as as we Aeeeuenv ~m~ no. «he cm" can ems mu Aenearaov ca am em as «as has an fleesezv c o a e m a mu Aoaaeeeesze ecu new mam new mea man «u Aememseeoe ems ees ees cos ee_ cos _n Areseeeeeme mum nun nuu nun mam n- a Aneuafiaoe momma umfiumwmm vuemwua< woman u>wuo< mee.eem.ee hee.~me.eo ee~.eme.ea nee.-m.ee nae.nem.ew ~e_.e~e.e» seen eaeasee> Haney teases: Ivan—cum :J are: magnate. as =5: :5 are: :5. :5: sea: L 83.2385 mesa sowawoun music no nauseom mun mamas 125 ee~.oe-auesuc eem.ea-a»euc rea.mea-auaec em~.em-aueoc em~.em-aueoe eeu.oeannoc heme» geese as e e e e e emu e an o e e e no e e as e o e ea c e o am e o so a e e a «ea e no a e e e e was so a e e e e e no o e e e o e mg a e e c e e so a e e e e e u muuwm uumvwvflmo as he as he he he “a Aeeeeeze «he can ee~ ems mes was mm neeesseov has «as «ea ea ea ea em fleeseze a a e e e a mu Aeeneeeeszv ea“ me~ men new meN hem «m Aeueeseeov era es. are con are con em Aeoseeeeemv was mam mum was mum mwa m Anthemauv uuumm mnwumfixm eunwfimum amusm o>wuu< ene.eme.e» emm.eee.ea eee.~em.ea eee.mee.ea eee.nee.e» hee.-~.ew eaeu oeeeaea> Hence teases: as a e a a a a a e a m H sadness .m, u =_u~_a _~ u a mums _nxu almW_a .e o a m~_a Hm u a mw_a _m o a germ, eesaeeeeeaeeea eeeeaeeeu e-n omens 126 However, both candidate sites 4 and 5 have positive omega values, which requires that a three-node branch and bound tree be evaluated to determine the optimal solution. This necessitates running one more transportation problem which includes switching on both sites 4 and 5. Starting with the basis saved from T[{K1U C5}], this required slightly more than one minute of computing time. The resulting branch and bound tree is shown in Figure 5-3. The costs shown in the tree are the total annual costs including all fa- cility variable costs and fixed charges. The optimal node (minimum cost) includes all the sites already placed in {K2} plus candidate site 5. This combination includes maintaining the Gilbert, Shoemaker, Coolidge, Wayne and Macomb garages at their current capacity, elimi- nating the Wyandotte garage and increasing the Oakland garage to a capacity of 167 buses (152 active buses plus 15 spares). Also, a garage is built at candidate site 5 for approximately 127 buses (115 active and 12 spares). Because all garages have lower capacities than the upper limit of the known portion of the facility cost functions (300 buses per garage), the assumptions used in constructing the cost curves have not been violated. What If Questions. It is possible that, after arriving at an optimal solution for a system characterization, the modeler may want to recharacterize the system to answer "what if" questions. For instance, the modeler may be interested in assessing the consequences of expanding the Gilbert garage. 127 c 3 All Members 0f K1 Open I All Members . All Members of K1 Open of K1 Open Plus C4 c: I In . N . Q18,737,29 618,695,206 ) ($18,950,253 Optimal Node Figure 5-4 Branch and Bound Tree of Case Study 128 To demonstrate how the model can be used to resolve such a ques- tion, suppose that enlarging the Gilbert garage means that adjacent structures have to be demolished, which will increase the construction variable cost by a fixed amount, and that a fixed penalty is assessed for disrupting the adjacent neighborhood. To determine whether it is efficient to enlarge the Gilbert garage and by how much, the cost parameters are revised and the problem is re-solved starting from the existing solution (the current set of {K0}, {K1}, and {Kz}). The Gilbert garage becomes a member of the set {K2}, its construction variable cost is increased for all added increments of capacity beyond the existing capacity, and a fixed charge is imposed that equals the penalty of disrupting the neighborhood. Another example of a what if question is: Suppose that SEHTA desires to know the cost penalty of increasing the Wayne garage to its planned capacity of 200 buses (180 active and 20 spares). This will increase costs because this capacity is not assigned to the Wayne garage in the optimal solution, in which the Wayne garage has an upper capacity limit of 180 active buses. The answer to this question T[{K1U 65)] is solved with the lower bound of the active capacity of the Wayne facility fixed at 180 active buses. Judgemental inputs can be similarly treated. For example, an operator may have specific criteria relative to the capacity of new facilities. A garage greater in size than 250 buses may be too large to be manageable and a garage of less than 50 buses may be too small to be practical. These judgemental inputs can be characterized in the model by lower and upper bounding capacities at their appropriate levels . 129 Another likely question might be: What is the most desirable garage system and staging of construction if the transit system's bus fleet is projected to expand gradually over a long-range planning horizon (e.g, 20 years)? For example, the number of active buses pro- jected to be in the Detroit transit system in 1985, is 1,064. Suppose that the number of active buses is projected to increase by 10 percent every five years until 2000. That is, in 1990, 1995 and 2000 there are expected to be 1,170, 1,287 and 1,416 active buses, respectively, in the Detroit transit system. Although the model can determine which combination of garage locations and bus allocations is optimal given the transit system at each five-year increment, there is no assurance that any of the optimal garage systems at five-year increments will include the same sites. For example, suppose the model selects only one site when considering the 1985 system and two sites when consider- ing the 2000 system. Further, suppose that the site selected given the 1985 system is not the same as either site selected when the year 2000 system is considered. To resolve this problem, two tasks must first be performed: 1. Different possible garage systems should be organized into feasible construction staging streams through time. These streams are created so that physically feasible construction staging alternatives are compared. For instance, in the Detroit fleet expansion example, one stream would be to determine the optimal 1985 site addition and fix that site open for all other years, and allow the model to select other optimal additions given the planned future transit systems. Another example would be to fix open one of the 130 optimal 2000 additions in all years prior to 2000. Once streams. have been formed that can be feasibly linked from one period to the next, the various streams generated can be compared. 2. To compare cost streams that occur at different times, all costs of each stream need to be reduces to a cannon value with respect to time. This means that all costs in a stream should either be equated to their present worth or their equivalent uniform annual value. Once these two tasks have been performed, the streams can be com- pared and the least-cost stream selected. However, this approach is based on the assumption that the transit planners are certain of fu- ture system expansion. This gives rise to the question of what the impacts are of uncertainty of future demands. To provide an example of the impact of uncertainty in expansion estimates, suppose that there is a range of uncertainty for the De- troit system expansion of 20 percent above or below the projected 2000 level. Even though a 10 percent expansion every five years is an ambitious improvement plan, it entails only a 33 percent increase over 1985 service. The uncertainty of the projection than represent 20. percent of the 33 percent increase, or 6.6 percent. Therefore, the percent uncertainty when compared to the remainder of the system is small. Further, future costs must be depreciated to equate them to present costs, which further diminishes the impact of future uncer- tainty. For example, suppose that the base year for comparison of different streams is 1985. Given a 10 percent discount rate, every dollar of cost accrued in the year 2000 has a present worth of 131 approximately 24 cents (53, p. 584). Assuming that uncertainty can be discounted, uncertainty of future bus fleet expansions will have only slight impacts on planned garage additions. If uncertainty is not assumed discountable, the least-cost garage staging streams can be determined for different service projections within the range of uncertainty. If all service projections locate garages at the same points, then the uncertainty will impact only the size of future garages or the extent of expansion of existing garages. If two or more of the service projections result in different Optimal garage locations, then the problem is more complex. In this case, the dif- ferent staging plans should have their costs estimated under each service projection. With these cost estimates the decision-maker will have enough information to determine the potential penalties of each staging plan and to adopt one staging plan based on the risk he is willing to assume.* Next, the discussion will investigate the sensitivity of the total annual garage-related costs to change in the availability of sites and change in the attributes of sites selected. 5-5 Sensitivity Analysis The question could be asked: Why is it necessary to examine changes in total cost from one feasible combination of sites (site option) to the next? The answer is that the optimal combination of sites (option) may include one or more sites that are controversial in some respect and the Operator may face public opposition to occupying *Example decision-making criteria (i.e., maximin or maximax decision rules), used to deal with uncertainty in decision-making, are des- cribed by Wohl and Martin (54, pp. 222-226). 132 the site. In such a situation, the operator should wish to know what kinds of tradeoffs can be made between costs and system attributes to occupy a less controversial site. This suggests two questions: 1. What are the changes in total cost from one option to the next? 2. How do the attributes change from option to Option in rela- tion to total cost? . When searching through the delta and omega decision rules, four- teen different combinations of sites (options) were evaluated. Each of these options is used as an example of a data point to evaluate the trade-offs between coats and system attributes and to evaluate the costs of site options relative to one another. First, the relative costs of various options are examined and this is followed by a com- parison of option attributes and total cost. Relative Total Costs The total cost (all fixed charges plus all variable costs) and system description for each option are listed in Table 5-6. All four- teen options are listed in increasing order of total cost, with option one being the optimal system and option ten the existing system. Also listed are the increases in total cost relative to option one. Note that with the exception of option 14 the greatest deviation in total cost from the Optimal option is only a little over a quarter of a million dollars per year. These deviations are small in comparison to the magnitude of the remaining costs. However, it should be remember- ed that each option includes optimally assigned blocks to garages. This means that each option is internally optimal. Further, at the 133 Table 5-6 Detroit Bus Garage Location-Allocation Options Busses Assigned Option Sites Total Cost Total Cost Increase To Candidate Number Included Per Year Over Option 1 Sites 1 {KID Cs} $18,695,206 ----- 115 2 {KID Ch} $18,731,262 $ 36,056 110 3 {K1} $18,790,015 $ 94,809 --- 4 {K10 Cl} $18,794,404 $ 99,198 116 5 {KIU C7} $18,826,245 $ 131,034 97 6 {K10 CG} $18,828,245 $ 133,039 104 7 {K10 C3} $18,855,166 $ 159,960 99 8 {K10 C2} $18,856,503 $ 161,297 105 9 {KID Clo} $18,880,313 $ 185,107 71 10 {KIU E4} $18,882,863 $ 187,657 --- 11 {K10 C9} $18,886,595 $ 191,389 58 12 {HID C40 Cs}$18,950,253 $ 255,047 118 13 {KlU CB} $18,963,863 268,657 69 14 {KID K2} $20,972,181 $2,276,975 149 134 most, none of the options could be more costly than the additional fixed charges over option 3 (the intial members of set {K1} after application of the delta decision rule). Thus, the increase in total cost is upper bounded by the total of the fixed charges of opened sites and the deviations in total cost may not be dramatic because each option is internally optimal. An excellent illustration of the relative insensitivity of total cost to location of a new garage is provided by a comparison of option 1 to option 9. The candidate site included in option 1 is on the west side of Detroit (see Figure 5-1) while the candidate site included in option 9 is on the northeast side of Detroit. The candidate site on the northeast side is located furthest from the optimal candidate site but the two options differ in total cost by, only $185,107 annually. Thus, internally optimal options tend to differ little in relative total costs even when some of the locations are at extremely different points within the urban area. From this comparison, a conclusion might be reached that location is relatively unimportant, and hence the question arises: Why is a model necessary to select sites? However, this ignores the fact that the model performs two sinultaneous functions: It optimally locates garages and at the same time it optimally assigns buses to garages located. The Metropolitan Transit Commission’s garage study points out that the potential penalty of forcing a nonoptimal allocation of buses to candidate sites can be many times greater than the differ- ences in costs between internally optimal options.* In fact, what the *For a discussion of the results of the Metropolitan Transit Camis- sion's study, see the literature review. 135 results of the Detroit case study show is that when a few selected options are compared the total cost differential between internally optimal options is not dramatic. This does not mean that any location can be allocated any capacity and the resulting cost penalty will not be great. What this does mean is that the cost penalty of even a poor location will not be great if route assignments are Optimally allo- cated. Further, since in the Detroit case study the do-nothing alter- native (option 3) is the third least cost option, garages are current- ly in relatively efficient locations which makes it difficult to show a dramatic cost improvement through the model's selection of locations and allocations. Another factor that can be noted from a comparison of the total costs is that the options that include the most distant candidate sites from downtown Detroit are generally more costly. Both candidate sites 8 and 9 are on the urban fringe of Detroit, and these options are ranked thirteenth and eleventh in total cost, respectively.* Al- though this result tends to agree with the findings of the study of the Metropolitan Transit Comission's garage locations, more sites should be evaluated before a claim can be made of concrete evidence of a general trend. Cmarison of Option Attributes to Total Cost The results of each option evaluated can be divided into three types of information, 1) bus (or block) assignments to sites, 2) cost estimates (facility and non-productive transportation costs), and 3) *Candidate site 9 is a site SEMTA is or was trying to occupy. 136 the number of new garages built and existing garages removed. The relationships between these three kinds of information and total cost are examined individually in the following paragraphs. Assignments of Buses to Sites. All of the sites that are fixed open after the application of the delta rule (all existing sites except Wyandotte) in all options are assigned a number of buses at least equal to their existing capacities. This is because the con- struction cost of assigning a bus to a candidate site for all buses assigned an existing garage is greater than the nonrproductive trans- portation cost savings of assigning the bus to a candidate site. If construction costs were reduced, at some point buses assigned to existing garages would be moved to candidate sites. On the other hand, since in all options existing garages are filled to capacity, increases in construction costs will have no impact on bus assignment and will only increase total cost. In fact, given the construction costs estimated for the case study or even greater construction costs, the model assigns buses to a candidate site based on the non-produc- tive transportation cost tradeoffs between expanding the Oakland and Whyne sites and assigning buses to the candidate site included in the option. - Total Cost versus Transportation and Facility Costs. Facility costs are more or less fixed for the case study. The variable operat- ing costs are a constant cost times the numbers of buses. The variable construction costs are a constant times the number of buses in the system that exceeds the number of existing spaces for buses. The fixed charge portion is a multiple of the number of open garages included in an option. Therefore, the facility costs of all options with the same 137 number of candidate and existing sites have the same facility costs and those that have more or less sites differ by their fixed charges. If garage operating cost varied, it would have little impact on the resulting allocation of buses to sites but it would impact total cost. For example, if variable operating cost per bus were increased or decreased the impact on total cost would be the change in variable operating cost times the number of vehicles in the system. This total cost change would be the same regardless of the option consider. Changes in fixed charges would have an impact on total cost equal to the number of effected facilities times the change. For instance, if the construction cost fixed charge were increased, all options with one candidate site would increase in total cost by the change in the fixed charge. A large increase in fixed charges will affect which op- tion is optimal. For example, if the construction cost fixed charge for candidate site Cs were increased by more than $36,056, option 2 would become optimal rather than option 1 (see Table 5-6). If the ga- rage operating cost fixed charge were changed, it would not effect the relative desirability of options with the same number of sites, but option with fewer garages would increase in desirability relative to options with more garages. For example, if garage operating cost fixed charge increase by more than $94,804, option 3 with 6 sites would become more desirable than option 1 with 7 sites. Because in the case study facility costs are constant for all op- tions that have the same number of existing and candidate sites, the change in total cost from one option to the next is the change in non- productive transportation cost. The relationship between the two can be seen in the plot of total cost versus non-productive transportation 138 cost in Figure 5-5. The options with six existing sites and one can- didate site (Options 1, 2, 4, 5, 6, 7, 8, 9, 11,13) form a 45-degree line between the vertical and horizontal axis. Because all sites are open in Option 14, it has the least non-productive transportation cost and it also has the greatest total cost. Option 12 has two candidate sites open and has the second least non-productive transportation cost. Option 3 has the greatest non-productive transportation cost and includes the fewest open sites (six). Total Cost Versus the Number of Garag5_. When comparing options including the smme number candidate options, facility costs are constant. Therefore, the Option with the minimum non-productive transportation cost when compared to Options with the same number of . sites will have the minimum total cost. ' If options are classified by the number of sites included, as in Figure 5-6, the dominate op- tions (least cost options) of each classification form a convex envelope. The dominate option in the classification, where one new garage is built and one existing garage is removed, is the overall minima. To the left of the minima, where fewer garages are included, facility costs are less than that of the overall minima but the great- er increase in non-productive transportation cost makes the total cost of Options to the left greater. To the right, non-productive trans- portation costs decrease less than the increase in facility costs. Note also that if the wrong facility were built, even though it in- cluded the minimum cost number of facilities (i.e., options 4,.5, 6, 7, 8, 9, and 11), the result would be less desirable than the existing system . 139 umoo mofiumuuommnmua O>Huo=ooumlnoz momuo> umoo Hence Aummm mom mmmaaoo mo maoaaawa may umoo moaumuuommmmua O>Huosooumlmoz .mlm mmswfim 9 s s s s s s .0 "a r. .t r. ”a .t _ _ _ _ m m m m _ 3 a S 41. .... a 8:8 0 ...... \ .... \ a 8:8xe. \ \ \ a 8:8 e . 8:8rex LT . x A m 3 a . . 8:8 \e o a a 8:8 \m, z a e 3.8 e. a 8:8 e . x x x ..l .... \ \ \ x 2 8:8 e 2 8:8 e , “w. es a 8:8 e ..l ...: A sad SJBIIOP go suorttpm up) 3803 paistau 338189 {2301 (183 Total Garage Related Cost (in millions of dollars per year) 21 20.9 19 18.9 18.8 18.7 18.6 18.5 140 1‘ . OPT1ON 13 0mm 12 omens 9. 10. u 0 00971005788 OPTION 1. L e mnuwssse omos 3 e omou a e um: ' mums: 1 k 1 1 J I j 1 1 1 1—11/ I 1 5 5 7 a 9 16 17 Number of Sites in Each Option Figure 5-6. Total Cost Verses Number of Sites 141 5-6 Summagy This chapter describes the application of the garage site selec- tion methodology to the combined systems of the two Detroit transit operators. In some instances, general information specifically devel- oped for the Detroit transit Operators was unavailable and information had to be extracted from other transit operatora’ garage studies. HOwever, because the intention of the case study is only to illustrate the model and not to actually locate garages for the Detroit opera- tors, not having complete information specifically for the Detroit operators should not detract from the example provided by the case study. NOnetheless, whenever possible every attempt was made to re- present the Detroit systems realistically. The methodology, as described in the previous chapter, was a1- tered such that fewer computer runs would have to be made while test-. ing sites against the delta decision rule. However, these alterations had no impact on the result. When the omega rule was tested, sites were eliminated from candidacy quickly in terms of computing time per run and in terms of the number of runs made. Nine of the eleven sites that were not fixed open during the delta rule were eliminated by the omega rule in nine computer runs which each took between one and one- half minutes and four minutes of computing time. The remaining candi- date sites were reduced to the optimal combination in three more short runs. The reason for the relatively short computer runs is the way in which the omega decision rule is structured. The omega rule test is to run a transportation problem with all sites that had been fixed open and then add one site and rerun the transportation problem. Then 142 the difference between the two runs is calculated, and if the decrease in the variable costs from one run to the next is less than the fixed charge of opening a site, the additional site is fixed closed. Note that the optimal basis of the first transporation problem is a feasi- ble basis for the second regardless of the site opened. Because the transportation problems that started from a feasible basis tended to take short computing times to solve, the omega rule testing ran rela- tively quickly. Because of the relative speed of the approach, it does not appear that increasing the number of candidate sites (the number of vari- ables) would create an unmanageable problem. Although the number of candidate sites should not be expanded beyond reason, it is probable that the number of candidate sites considered in the case study (ten) could have been doubled or tripled before the problem would have been unmanageable. CHAPTER6 FINDINGS , CONCLUSIONS AND RECOMMENDATIONS In this research a mathematical model was developed which will aid transit planners in determining optimal bus garage locations and bus allocations to garages located. After the model was developed it was demonstrated using a Detroit case study. This chapter summarizes the finding of the research, presents conclusions and makes recomend- ations for future study in this area. Each of these topics is includ- ed in one of the following sections. 6-1 Findings The model developed and demonstrated in this research represent a significant advance over past methods used to aid in bus garage planning. Methods comonly used by transit planners to locate bus garages do not fully utilize state-of-the-art location modeling tech- niques. None of the known past methods consider all cost related to garage location and bus allocation in a comprehensive cost minimi- zation model. The model developed in this research provides transit planners with a comprehensive cost minimization methodology and a demonstration of its use. Methodology The three types of costs related to the garage location problem 143 144 are: non-productive transportation, garage operating and garage con- struction costs. Operating and construction costs are both facility costs, and because of the way their cost functions behave, both fa- cility costs can be divided into two portions: a fixed charge and variable portion which increases linearly with capacity. This means that if a site is opened it is assessed the appropriate fixed charges and a constant variable cost times its capacity. These costs can be represented by a variable equal to the capacity assigned to a site times the variable cost plus O-l variable that switches on (equal to 1) if any capacity is assigned a site, times the fixed charges. The non-productive transportation costs can be represented by the unique cost of servicing a block from a site times an assignment variable (0-1) which switches on (equal to 1) if the block is assigned to the site. In the model, all variables except the variable set equal to a site's capacity are 0-1‘. Such problems could theoretically be solved with a mixed integer program, but the computing time necessary to solve a realistic large-scale problem using a mixed integer program makes it impractical. To simplify the problem, it is divided into two portions and the problems of each portion are resolved separately. The first portion deals with the problem of integer (0-1) block assignments. If the problem is restructured and the fixed charge switches are dropped, then the problem becomes a classical transporta- tion problem. Because of its special structure, a transportation problem, when solved, naturally yields integer values. Although for- matting the model as a transportation problem solves the issue of preserving the integer values of the block assignments, it does not 145 resolve the problem of preserving the integer values of the fixed charge switches. If the transportation problem is solved without including a site, then implicity its fixed charge is switched off. Using this approach, all combinations of sites could be evaluated by including and exclud- ing sites in separate transportation problems. But even with a few sites there will be a large number of combinations, which makes evalu- ating all possibilities impractical. Therefore, an approach is em- ployed that efficiently eliminates possible nodes. Nodes are elimi- nated by applying two decision rules to iterate towards a small set of remaining nodes;* The few remaining nodes can be evaluated quickly through a branch and bound approach. Case Study The case study applied the methodology to the combined systems of the two Detroit metropolitan transit operators. The case study considered existing transit service plus planned service increases through 1985. The increases outstripped existing garage capacity, which would force the methodology to locate a new facility and/or expand existing garages. There are currently seven bus garages in the Detroit area; how- ever, one contains only five indoor storage bays and is slated to be removed from service when it becomes possible to replace it with a larger facility. An additional ten candidate sites were identified. Thus, there were 17 sites (existing and candidates) over 2,300 blocks causing over 39,000 potential block assignments. This meant that the transportation problmm, when all garages were considered, would have *The decision rules are described in Chapters h and 5. 146 over 39,000 variables. Although transportation problems tend to solve more quickly than other linear programs, it still requires large amount of computing time to solve from the initial raw data. An alternative approach was developed to alleviate the need to make a number of runs, and an optimal result was reached by solving only 14 transportation problems, most of which required between one and one-half to four minutes of computing time.* The optimal solution included building one new garage at a site on the west side of Detroit and expanding a north suburban bus garage. Because the optimal solution was found without using a large amomnt of computing time, it is likely that the number of candidate sites included in the problem could be doubled or tripled before the problem becomes unmanageable. Further, with more sites included in a problem, the modeler will evaluate more combinations of sites spread over a greater portion of the urban area, which would permit a greater understanding of the changes in cost with respect to different loca- tions. This information should aid in making tradeoffs between coats and other attributes of particular sites (i.e. neighboring land use, institutional problems, land development, etc.). 6-2 Conclusions The research has achieved its initial objectives. To demonstrate this the objectives listed in the problem statement in Chapter 3 are compared to the results. 1. Identify Nature of Cost Parameters. The shapes of construc- tion and operating cost functions were identified in Chapter 4 through *On an Amdahl 470V/6. 147 the use of estimates made in two garage studies conducted for two different transit operators. It was concluded that both garage construction and operating cost functions could be satisfactorily represented by a fixed charge and a variable portion linear with garage capacity. 2. Develop a Structure that Symbolizes Bus Assignment. In Chapter 4 a mathematical structure was developed that assigned buses to garages on a block-by-block basis. The structure represents the relationship 'between garage capacity and block assignments at the most disaggregate level possible. 3. Develop a Solution Technique. In Chapter 4, two models were developed. The first method theoretically could reach a solution when applied to an actual problem, but would require an impractical amount of computing time. The second approach used the theoretical model as a basis and adapted it into a feasible and efficient approach. 4. Structure a Computer Model. In Chapter 4 the practical ap- proach (as well as the theoretical approach) is used to locate and size garages optimally in a sample problem. The practical approach requires only that the problem be modeled as a linear program, and the solution is found by solving a specific sequence of linear programs each having different capacity limits for garage sites. 5. Estimate Cost Parameters for the Case Study. In Chapter 5 garage construction and garage operating cost functions were estimated for the Detroit case study by using the estimates of a recent AC Transit study and factoring their estimates upward to equal past De- troit costs (3). After the appropriate factors were applied to the AC Transit estimates, a curve relating garage capacity to annualized 148 costs was fit to the data points. Non-productive transportation costs were estimated for every block-garage site combination through the Detroit area computerized highway network. 6. Demonstrate the Model through a Detroit Example. In Chapter 5 the Detroit system was characterized and, based on the characteriza- tion, the model was applied to the combined system of both Detroit operators (D-DOT and SEMTA). The optimal combination of garages in- cludes the addition of one facility on the west side of Detroit. 7. Demonstrate the Savings and Costs of the Model Use. In Chapter 5 the total costs of 14 different garage location-capacity options were estimated for the Detroit system. One of these options included a site that SEMTA has attempted to purchase for a northwes- tern garage. The decision to build at a site in this area was reached through the results of two previous garage location studies. In com- parison to the option selected with the model, occupying this site would cause the combined Detroit operators to incur an additional cost, at the very minimum, of $191,389 per year. This figure assumes that all buses are optimally assigned to garages and that the result- ing assignment represents the minimum lower bound of actual costs. 8. Perform a Sensitivity Analysis. In Chapter 5 the relation- ship between total cost and buses assigned to candidate sites and between total cost and nonrproductive transportation costs was exam- ined for the 14 garage location-capacity options. It was found that total cost tends to decrease as the number of buses assigned to candi- date sites increases. The change of total cost was found to be pro- portional to the change of non-productive transportation costs for all options that included the same number of existing and candidate sites. 149 All eight specific objectives have been met by the research. The importance of this research to the state-of-the-art is that it pro- vides an efficient method to find an optimal solution considering all costs related to garages in one comprehensive model. In application of the model, the user has a great deal of flex- ibility to characterize the transit system and the garage-related costs, and to provide judgemental inputs of the modeler, given the special attributes of the specific system. This flexibility should permit the user to represent accurately the specific problem being considered. Further, the flexibility of the model should allow him to test the sensitivity of the solution to various possibilities. The case study using the Detroit metropolitan area transit op- erators data demonstrates that the model can be used to solve a large- scale garage location problem. Approximately 2,300 blocks were con- sidered, and 17 candidate and existing sites. Because all blocks can potentially be assigned to each site, the model had over 39,000 as- signment variables (17 x 2,300 = 39,100). However, because the solu- tion technique proceeds efficiently, future users could expand the number of sites considered. 6-3 Recommendations If the methodology is to be improved it is recomended that a computer program be used that solves transportation problems as trans- portation problems rather than using a general-purpose linear program- ming computer package. An example of an efficient transportation problem code is one developed by Barr (55). 150 It is recommended that future research increase the scape of study. For example, the methodology developed in this research treats pullout, pullin and relief points as being independent of the loca- tions of garages. Because a bus transit system is not fixed to any one location, pullout, pullin, and relief points need not be fixed. Further, the doubling of buses into other runs may also be possible, depending on the location of a garage.* These potential changes in the network increase the difficulty of the garage location problem but, because such system changes are possible, future research should attempt to treat the transit system as being dynamic. The treatment of a dynamic transit system will mean that transit system costs related to productive service will change. For example, suppose that the garage location problem treates pullout and pullin points as being moveable. Also, suppose that a pullout and/or pullin point is moved to diminish the amount of deadheading necessary to serve a block from a garage site. Note that by decreasing deadhead- ing, the amount of revenue service travel is changed. Therefore, both non-productive transportation costs and productive transportation costs of the block have been changed, and a total cost optimization must consider both costs. This means that both halves of the transit system, the non-productive half (e.g., garage costs and non-productive transportation costs) and the revenue service half have to be consid- ered in a total system optimization. Although at this point it is uncertain how to minimize total costs while locating and sizing *Doubling means that after a driver has completed his run on a spe- cific route, he drives his bus to another run on another route rather than returning to the garage. 151 facilities, it appears to be a much more complex problem that needs further investigation. 10. 11. REFERENCES Maze, T.H., Khasnabis, 8., Kapur, K. and Pools, M.S., "A Proposed Approach to Determine the Optimal Number, Size and Location of Bus Garage Additions," Transportation Research Record, No. 798, 1981, pp. 11-18. Collins, T.P., "Optimum Garage Size Analysis," prepared by ATE Management and Service Corporation, for the Metropolitan Transit Comission, St. Paul, Minnesota, 1975. "A Master Plan of Bus Maintenance Service, Garages and Other Facil- ities," prepared by Wilber Smith and Associates and Leo A. Daly Co., for A.C. Transit, Oakland, California, 1979. ”Selection Criteria and Process for Garage Locations: Bi-State Development Agency's Garage Expansion Plan," prepared by Daniel, Mann, Johnson, and Mendenhall for Bi-State Development Agency, St. Louis, Missouri, 1979. Spielberg, F. and Golenberg, M., "Systematic Procedure for Analysis of Bus Garage Locations," Transportation Research Record No. 746, 1980, p. 39-42. Thurlow, V.S., Backman, J.A. and Lovett, C.D., "Bus Maintenance Facilities: A Transit Management Handbook," prepared by the Mitre Corporation for the Urban Mass Transportation Administration, United States Department of Transportation, Washington, D.C. , 197$. Maze, T.H., "A Methodology for Locating and Sizing Transportation Dependent Facilities: As Applied to Locating and Sizing Bus Ga- rages," Masters' paper, Institute for Transportation Studies, Uni- versity of California, Berkeley, California, 1977. Francis, R.L. and White, J .A. , Facility Layout and Location: An Analytic Approach, Prentice-Hall, Inc. , Englewood Cliffs, New Jersey, 1974. ‘ - "Fixed Facility Improvement Recommendations: Final Report," pre- pared by the Market and Research Planning Staff of the Southeastern Michigan Transportation Authority, Detroit, Michigan, 1979. Eilon, S., Watson-Gundy, C.D.T. and Christofides, N., Distribution Management: Mathematical ModellinLand Practical Analysis, Hafner Publishing Company, New York, New York, 1971. Maze, T.II., Khasnabis, S., Kapur, K. and Kutsal, M.D., "A Metho- dology for Locating and Sizing Transit Fixed Facilities and A De- troit Case Study," prepared for the Urban Mass Transportation Authority, United States Department of Transportation, Washington, D.C. (draft). 152 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 153 "Milwaukee Transit Facility Requirements," prepared by W.C. Gilman and Co. for Milwaukee County, Milwaukee, Wisconsin, 1979. "TARC Garage-Office Facility Location and Integration Analysis," Prepared by Luckett and Farley, Inc. for the Transit Authority of River City, Louisville, Kentucky, 1976. Baumol, W.J. and Wolfe, P., "Warehouse Location," Operations Re- search, Vol. 6, No. 2, 1958, pp. 252-263. Wagner, H.M., Principles of Operations Research: With Applications to Managerial Decisions, Prentice-Hall, Inc., Englewood Cliffs, New Jersey, 1969. Hillier, F.S. and Lieberman, G.J., Introducgion to Operations Re- search, third edition, Holden-Day, Inc., San Francisco, California, 1980. Balinski, M.L. and Mills, 11., "A Warehouse Problem," Mathematica, Princeton, New Jersey, 1960. Gary, P. , "Mixed Interger Programing Algorithms for Site Selection and Other Fixed Charge Problems Having Capacity Constraints," Ph.D. Dissertation, Stanford University, Stanford, California, 1968. Kuehn, A.A. and Hamberger, J .J . , "A Heuristic Program for Locating Warehouses," Management Science, Vol. 9, No. 4, 1963, pp. 643-667. Balinski, M.L. , "Fixed Cost Transportation Problems," Naval Re- search Logistics Quarterly, Vol. 8, No. l, 1961, pp. 41-54. Manme, A.S., "Plant Location Under Economics of Scale-Decentraliza- tion and Computation," ManaLment Science, Vol. 11, No. 2, 1964, pp. 213-235. Copper, L. and Drebes, C., "An Approximate Solution Method for the Fixed Charge Problem," Naval Research Logistics Quarterly, Vol. 14, No. 1, 1967, pp. 101-113. Feldman, E., Lehrer, F.A. and Ray, T.L., "Warehouse Location Under Continuous Economics of Scale," Management Science, Vol. 12, No. 9, 1966, pp. 670-684. Murty, K.G. , "Solving the Fixed Charge Problem by Ranking Extreme Points," Operations Research Center Report 66-7, University of California at Berkeley, Operations Research Center, Berkeley, California, 1966. Efromson, M.A. and Ray, T.L., "A Branch-Bound Algorithm for Plant Location," Operations Research, Vol. 14, No. 3, 1966, pp. 361-368. Spielburg, K., "Plant Location with Generalized Search Origin," ManaLement Science, Vol. 17, 1969, pp. 165-177. 27. 28. 29. 30. 31. 32. 33. 34. 35. 36. 37. 38. 39. 40. 154 Khumawala, B.M., "An Efficient Branch and Bound Algorithm for the Warehouse Location Problem," Management Science, Vol. 18, 1972, pp. 718-731. Akinc, U. , "A Branch and Bound Procedure for Solving Warehouse Location Problems with Capacity-Constraints," Ph.D. dissertation, University of North Carolina, Chapel Hill, 1973. Khumawala, B.W. and Akinc, U., "An Efficient Branch and Bound Al- gorithm for the Capacitated Warehouse Location Problems," Paper No. 415., Krannert Graduate School of Industrial Administration, Purdue University, Lafayette, Indiana, 1974. Benders, J .F. , "Partitioning Procedures for Solving Mixed Variable Programing Problems," Numerische Mathematik, Vol. 4, 1962, pp. 238-252. Ellwein, L.B. and Gray, P.L., "Solving Fixed Charge Location-Allo- cation Problems with Capacity and Configuration Constraints," AIIE Transactions, Vol. 3, 1971, pp. 290-299. Bulfin, R.L. and Unger, V.E., "Comutational Experience with an Algorithm for the Lock Box Problem," Proceedings of ACM, 1973, pp. 16-19. Geoffrion, A.M. and McBride, "The Capacity Facility Location Prob- lem with Additional Constraints," AIIE, ORSA/TIMS Joint National Meeting, 1973. McGinnis, L.F., "Approximate and Exact Solution Procedures for a Class of Facilities Location Problems," Ph.D. dissertation, North Carolina State University, Raleigh, North Carolina,p1975. Geoffrion, A.M. and Graves, G., "Multicomodity Distribution System Design by Benders' Decomposition," Manpgement Science, Vol. 20, 1974, pp. 822-844. Soland, R.M., "Optimal Plant Location with Concave Costs," Opera- tions Research, Vol. 22, 1974, pp. 373-382. Rardin, R.L., "Group Theoretic and Related Approaches to Fixed Charge Problems," Ph.D. dissertation, School of Industrial and systems Engineering, Georgia Institute of Technology, 1973. Remington, J .L. and Unger, V.E. , "The Group-Theoretic Structure in the Fixed-Charge Transportation Problem," Operations Research, vol. 21, No. 5, 1973, pp. 1142-1152. Remington, J .L. , "The Fixed-Charge Transportation Problem: A Computational Study with a Branch-and-Bound Code," AIIE Transac- tions, vol. 8, No. 2, 1976, pp. 241-247. "IBM Mathematical Programing System; Extended 370 (MPSX/370), Mixed Integer Programing/370 (MP/370)," International Business Machines, White Plains, New York, 1975. a1. 42. 43. 45. 47. 48. 49. 50. 51. '52. 53. 54. 55. 155 Wesolowsky, G.0. , "Location in Continuous Space," Geographic Analy- s_i_s_, Vol. 5, 1973, pp. 95-112. Smerk, G., Readings in Urban Transportation, Indiana University Press, Bloomington, Indiana, 1968. Dickey, J .W., Metromlitan Transportation Plannipg, ed. Dickey, J.W., Scripts Book Company, Washington, DC, 1975. I-Gomez, J.A., "Assessing the Argument for Urban Transit Operating Subsidizes," Transportation Research Record No. 573, 1970, pp. 1- 11. Briggs, R., ”The Impact of Federal Local Public Transportation Assistance Upon Travel Behavior," Professional Ge_ographer, Vol. 32, No. 3, 1980, pp. 316-325. "Motor Vehicle Facts and Figures ‘79," Motor Vehicle Manufacturers Association, Detroit, Michigan, 1980. Dakin, R.J. , "A Tree-Search Algorithm for Mixed Integer Programing Problems," The Comppter Journal, Vol. 8, No. 3, pp. 250-255, 1965. Mairs, T.C., Wakefield, G.W., Johnson, E.L. and Spielberg, K., "On a Production Allocation and Distribution Problem," Manggment Sci- ence, Vol. 24, No. 15, 1978, pp. 1622-1630. Hoffman, A.J. and Kruskal, J.B., "Integer Boundary Points of Convex Polyhedra,” in "Linear Inequalities and Related Systems," eds. Kuhn, W.H. and Tucker, H.W., Annals of mathematics Studys No. 38, Princeton University Press, Princeton, New Jersey, 1956, pp. 233- 246. Hu, T.C. , Integer Programing and Network Flows, Addison-Wesley Publishing Company, Reading, Massachusetts, 1969. "Guidelines for Preparing Environmental Assessments ," UMTA Circu- lar No. 5620.1, Urban Mass Transportation Administration, United States Department of Transportation, Washington, D.C., 1979. "UMTA UTPS Manuals," Urban Mass Transportation Administration, United States Department of Transportation, Washington, D.C. Grant, E.L., Ireson, W.G. and Leavenworth, R.S., Principles of Engi- neerinflconomy, John Wiley and Sons, New York, NY, 1976. Wohl, M. and Martin, Traffic Systems Analysis for Engineers and Planners, McGraw-Hill Book Company, New York, NY, 1967. Barr, R.S., Streamlining Primal Simplex Transportation Codes," Research Report, Southern Methodist University, Cox School of Business, Dallas, Texas, 1981. 156 56. Greig, M. and Tenisci, T., UBC TSPl Time Series Processor, Univer- sity of British Columbia Computing Centre Publication, Vancouver, British Columbia, 1978. APPENDIX A AUTOMATED DATA CODING FOR THE DETROIT CASE STUDY The original data for the non-productive transportation costs are generated through the application of the UTPS module UROAD to the De- troit metropolitan area computerized highway network to arrive at travel costs from garage sites to pullout, pullin and relief points. These data are then recorded on card images through another UTPS module, UMCON. The resulting data are non-productive transportation costs for each possible pullout, pullin or relief. These must be totalled for each block to derive the non-productive transportation cost per block and multiplied by the number of times a block is serviced by a bus per year. The manipulating of the non-productive cost data was done through the data formatter of a standard statistical package (Time Series Pro- cessor) (56). The reason for using a standard package to total the non- productive transportation costs is primarily convenience. However, it would have been more efficient, in terms of computing time, to write a program to perform this function, and it is suggested that future users write their own programs to perform this function. Once the non-productive transportation costs were reduced to annual values, the cost parameters had to be formatted for entry into the mathematic programing package (MPSX/370). Because of the large volume of data and because the mathematic programing package requires that all data be formatted in a specific manner, programs were written to prepare the cost parameters for entry to the package. 157 158 The mathematical programing package divides the portions of the model into five sections: 1. ;RO_W_S_: The ROWS section identifies the constraints. That is, for the objective function and each functional constraint there is one record (card) in the ROWS section of the package data input. Included in the record are a constraint label and the sense of the constraint (i.e., an equality constraint, a less than constraint, etc.). COLUMNS: The COLUMNS section identifies each of the vari- ables. In the mathematical program there is one column for each variable. The COLUMNS section contains a record identi- fying the variable and one record for each row in which the variable appears, which includes the name of the row (identi- fied in the ROWS section) and the parameter value (coeffi- cient) of the variable in each row. R_HS_: The RHS section defines the values of the right-hand side of the mathematical programing. There is one record in this section for each row. RANGE: The RANGE section is optional, and permits the user to specify a range for the values in the right-hand side (this section was not used in the garage location model). m: The BOUNDS section is also optional and permits the user to define an upper and lower bound on each variable. The program utilized to format the data is flowcharted in Figure A-l. It uses five random access working files, four of which are used as scratch files. The initial formatting program is designed to set up the theoretical model (see Chapter 3 for a description of the theoreti- 159 Figure A—l Flowchart of Data Coding Methodology 160 cal model) and later the mathematical program was edited to derive the practical model. File-1 is used to store the ROWS section, as well as information and labels to be utilized by the system during later stages. File-2 is similarly used for the COLUMNS section. However, since the names for the variables obtained from the name generator (see flowchart in Figure Arl) are treated in an array and the problem calls for five different types of functional constraints, the generation of this sec- tion is treated in a sequential manner according to constraint types. The whole file was later sorted into an order where all variables are defined individually in their own segment of the COLUMNS section. One of the mathematical programing package requirements is that there be no imbedded blanks in variable names or in constraint labels. On the other hand, to assure accuracy, the name generator used is de- signed to treat these names and labels in two parts. The first part contained an identifying alphabetic string, and the second a two-part sequential numeric code as shown below. AB...123...123 Max. length = 8 characters To satisfy the requirements of the mathematical programming package, a modular program is developed that fills the imbedded blanks by under- scoring them, thereby making the length of each variable name or con- straint label consistent, as shown below. Original Label Filled Label A1 1 A_1__l 3237 B__23___7 This option also provided for easier identification and comparison of all variable names and constraint labels. 161 File-3 and File-4 are used to generate the RHS and BOUNDS sections respectively, in a similar manner. However, since the RHS section calls for the names and other information about the constraints, File-1 is used again. (This condition applies to the BOUNDS section as well and therefore File-4 and File-2 are similarly utilized.) Notice that MPSX/370 (the mathematical programing package) re- quires that all problem data be contained in a stream and that it con- tain prescribed labels on pre-positioned control cards. To achieve this and as further precautionary editing of the data, a modular LINK and EDIT program is developed. This module finalizes the data preparation as well as providing error-scanning for proper format. APPENDIX B GLOSSARY OF TERMS M: A route is a general category for one or more vehicle op- erating paths. Routes are often fragmented, branching into separ- ate paths, that is, subroutes. Routes are only a pathway for serv- ice and vehicles, and on a daily or partial-day basis, buses will be rotated through different route assignments. B1335: A block is the assignment of a driver or drivers to a piece of labor. A block is started when a route is started by a particu- lar bus and driver that have either just come from the garage or was doubled in from another block ("doubled” means that a bus and driver shift from one block to another). The block ends once the bus returns to the garage or is doubled into another block. During the duration of the block, the bus always remains on the same route; also, during the. block, the bus will remain the same but the driver may be relieved several times. Pullins and pullouts: A pullout is the action of taking (deadhead- ing) the bus to the beginning of a block (the in-revenue point) from the garage. A pullin is just the opposite, taking the bus back to the garage. Each block does not necessarily have either or both a pullout and a pullin; a block may have one or two doubles at either terminus of the block. The points to and from. the block pullouts and pullins is a function of the specific block, although many blocks on the same route may have the same pullout and pullin 162 163 points. Also, a block may have the same pullout and pullin points, but usually it does not. AML PM, midday and all-day blocks: The demand for vehicles to be used in the network is the greatest in the two peaks and particu- larly greatest in the morning peak (AM peak). Therefore, garage capacity can be focused around the supply of space needed to store the buses required to satisfy the AM peak service demand. An AM block is one that takes place during the morning peak only, PMs are out only during the PM peak, middays are out only between the peaks, and all-days are out during both peaks and the midday period. There are relatively few middays since there is little demand for midday-only service, and most middays are for some specific purpose, such as downtown shuttles, service to senior citizens homes, service to the zoo, and so on. Spare factors: The fleet of vehicles must have some number of spare vehicles beyond the number needed to meet the demand during the AM peak. This is to provide spare vehicles to replace bad- order vehicles, vehicles being serviced for periodic maintenance, and street breakdowns. Assignment of blocks to garages: All vehicles must start and end at the same garage. This means that a block cannot pullout from garage X because it possesses the cheapest pullout cost and pullin to garage Y because it possesses the cheapest pullin cost. Gener- ally, drivers' unions will not allow this procedure, not to mention the confusion it would cause with the dispatchers, maintenance people, vault tenders, etc. But buses assighed to the same route but on different blocks may originate from different garages.