Mathematical Programming Formulations Of Transportation .

39TRANSPORTATION RESEARCH RECORD 1125Mathematical Programming Formulations ofTransportation and Land Use Models:Practical Implications of Recent ResearchSTEPHENH.PUTMANThe next generation of transportation, location, and land usemodels will most probably emerge from mathematical programming formulations. Presented are simple numerical examples of trip assignment and population location, both described as optimization problems, In mathematicalprogramming formulations. A trip assignment model withconstant link costs ls described first, and then the same modelis modified to show the consequences of a How-dependent linkcost formulation. In similar fashion, a linear model of least costpopulation location is transformed into a nonlinear model thatincorporates dispersion of location due to differences in locators' preferences or perceptions. It ls then shown how the tripassignment model and the location model can be combined intoa single nonlinear programming formulation that solves bothproblems simultaneously. In the final section of the paper, thetheoretical advantages and practical disadvantages of this approach are brlefty enumerated. This is followed by suggestionsabout the likely resolution of practical problems to allow use ofthese techniques in applied planning situations.There has been considerable refinement of practical methods offorecasting urban location and transportation patterns duringthe past 10 to 15 years. Although there is continuing discussionand development, and even the best of forecasts are far fromperfect, there appears to be a greater consensus on whatmethods are clearly outmoded and in what directions futureefforts should move. This author's views on general progress inthe field have already been published (1). Among the mostsophisticated practical methods of transportation and land useforecasting are the extended spatial interaction models, especially when they are included in comprehensive integratedmodel systems [see paper by Bly and Webster in this Recordand Putman (2)].In addition to these practical developments there have alsobeen important theoretical developments. On the transportationside these include the development of discrete choice models,especially for travel demand and mode choice (3 ), and thedevelopment of mathematical programming formulations ofthe traffic assignment problem (4). On the location side thedevelopment of utility theory as a basis for location models (5)and the general discussion of mathematical programming models as alternate or underlying structures for spatial interactionmodels (6) were major developments. Some of these developments are important principally because they provide an improved underpinning of existing practical methods; some haveUrban Simulation Laboratory, Department of City and Regional Planning, University of Pennsylvania, Philadelphia, Pa. 19104.shown the existence of clear errors in prior practice; and othersmay offer substantial improvements for future applications.Past experience suggests that there is a lag of 10 years,sometimes more, between the initial development and subsequent practical application of new techniques in transportationand land use forecasting. Thus, although there have been someattempted applications of these methods (7, 8), they are farfrom being the accepted norm. The purpose of this paper is topresent some illustrations of the mathematical programmingformulations along with some simple numerical examples. Theintent is to show some of the benefits, both practical andtheoretical, of these formulations and to provide the practicalplanner with an introduction to this promising new area.NETWORKS AND TRIP ASSIGNMENTIn the discussion that follows, extensive use will be made of thedata describing Archerville, a simple five-zone numerical example. Table 1 give the land use and socioeconomic data forArcherville. Figure 1 shows the Archerville highway system.Shortest Path ProblemA frequently encountered problem in transportation and location analyses is that of finding the shortest path from one nodeto another over the links of a network. This is a problem thatcan be considered as a linear programming problem. The equation form is(1)subject toI: 1xk' -Xii IkI:xk' I0 (Vi,;)1 if i{ origin- 1 if i;;;: destination0 otherwise(2)(3)where Cij is cost of traversing link i, j and Xij is flow (trips) onlink i, j.The objective function is straightforward: simply to minimize the sum of the link cost times the trips incurring that cost.The principal constraint equations (Equations 2) are a set offlow-balance relationships that ensure that the flows, at each

TABLE 1 ARCHERVILLE-LAND USE AND SOCIOECONOMIC DATASocioeconomic DataLand Use DataResiZone dentialCommercialIndustrialVacant ousehold Cross TabulationCommercialIndustrialNorn: loymentLl HouseholdsHl 03001506508601,0505855505153,560Employee-Household Conversion cialIndustrialLIHlTotal.533.571.467.4291.001.00 low-income and Hl high-income.-·- --/10/I.'I -'FIGURE 1 Archerville highway system.11

Putman41network node, balance. Thus for each node the total flow oftrips into the node minus the total flow of trips out of the nodemust equal the net trips supplied (or demanded) at the node.The last constraint equation (Equation 3) is simply the nonnegativity requirements that prohibit negative flows. It canreadily be seen that writing the shortest path problem in thisform yields a rather good sized problem. In the objectivefunction the number of terms equals the number of links in thenetwork. There must be a constraint equation (Equation 2) foreach network node and a constraint equation (Equation 3) foreach network link.For practical applications there are many fast algorithms forsolving this problem. However, it is worth noting here that,because this is just a simple linear program, it can be solv bythe well-known simplex method. If it were done that way, itwould be necessary to solve the problem once for each origindestination path that was wanted. Further note that this problemonly addresses the situation for fixed link costs and flow volumes, which must, of course, be known in advance of anyattempt to solve for the minimum path or paths.Minimum-Cost Flow Problem E jEe . x .jIJIJ(4)subject toEx. - kEXk.I ·IJ1O; if i origin- D.I if i destination{0 otherwise(7)Note that the objective function here is the same as that for theshortest path problem given in Equation 1. The constraints,Equations 5, are a set of flow-balance relationships similar tothose of Equations 2.Because the intrazonal travel costs are 1.0 for each zone,clearly the first consideration is that all employees residing inany zone first be assigned to jobs in that zone. Given theArcherville data, Zone 1 requires 4 workers and Zone 3 requires 302. Zones 2, 4, and 5 have 23, 188, and 95 surplusworkers, respectively. The link flows produced by the simplexalgorithm to solve this problem are shown in Figure 2. Notethat if it were desired that some of the network links have amaximum allowable flow, then some constraints of the form ofEquation 7 would have to be added.Nonlinear Minimum-Cost Flow ProblemAnother type of linear programming problem is that known asthe minimum-cost flow problem. The Archerville data may beused as an example. Assume that there are a known number ofhouseholds of each income group in each zone and a knownnumber of employees of each type working in each zone.Implicitly there is a zone-to-zone matrix of home-to-work tripsthat can be estimated by standard techniques. Suppose now thatthe location of households in Table 1 and the location ofindustrial employment in the same table are taken as given. Byfirst assuming that there will be one employee per householdand then applying the Employee-Household Conversion Matrixgiven in Table 1, the number of industrial employees residingin each zone may be calculated. These were 146, 173, 98, 188,and 95, respectively. Note that the number of industrial employees working in each zone is 150, 150, 400, 0, and 0,respectively.It is possible to consider the proposal that each employee isto choose a place of work such that the total travel cost for allemployees is minimized. If network link capacities, and theconsequent congestion, are ignored for this illustration, thisproblem may be stated as a linear programMin: Zproblem. If there were specified link capacities (V;j) for eachlink, which could not be exceeded, then another set of constraints would be substituted for Equation 6. This new set ofconstraints would be of the form(5)(6)where O; is net trips leaving node i and D; is net trips arriving atnode i.Equations 4, 5, and 6 are the general minimum-cost flowThe minimum-cost flow problem described here can be reconsidered as a nonlinear programming formulation. In the previous formulation the linear objective function, Equation 4,was simply the sum of the trips (flows) on each network linktimes the travel cost of the link. The link costs were fixed,remaining constant regardless of link flows (though it wasshown how the link flows could themselves be restricted by useof additional constraint equations). Suppose the more realisticview was taken that link costs depend on link flows. For thesake of illustration consider the following function, where linkcost varies with link flowC;i c (LO ox\)(8)whereCiCuxij'O "congested" or flow-related link travel cost,free-flow link travel cost,link flow volume (trips), anda parameter.With this function the link travel cost is equal to the free-flowcost when the link flow volume is zero. As link flow volumeincreases, link travel cost increases too.In the linear version of this problem the solution involvedonly the finding of the minimum paths and the subsequentrouting of trips along those paths. If there were specific linkflow volume constraints, then the excess trips would be rerouted to the second shortest path. When link flows determinelink costs the essential nature of the problem changes. Thesolution becomes a matter of adjusting volumes, observing theresulting costs, and then adjusting the volumes again. Thus, ina very real sense, even for the small problem size of theArcherville data the complexity of the problem begins to defy