Integrative Freight Market Simulation
Jose Holguin-Veras, Ph.D., P.E. Office room: JEC 4030, Telephone: 276-6221
Disclaimer: This material is based upon work supported by the National Science Foundation under Grant No. #NSF-CMS 0085705. Any opinions, findings and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation ( NSF ).
This project is concerned with the development of a comprehensive model of freight movements intended to: a) estimate freight origin destination matrices on the basis of secondary information, such as traffic data from Intelligent Transportation Systems (ITS); b) consider the flow of both commodities and commercial vehicles; c) consider commercial vehicle trip chaining, or alternatively Trip Length Distributions (TLDs); d) use logistic information in freight demand modeling; e) enable the study of the impact of real-time traffic control upon commercial vehicle traffic. The concept discussed here entails a bi-level approach in which the top level corresponds to the estimation of the provision of service consistent with a Cournot equilibrium, while the bottom level focuses on the construction of tours that satisfy the Cournot solution and the remaining system constraints, in a context of a large scale stochastic simulation. These methodologies will enhance transportation modeling by adding another layer of realism to the freight demand modeling process; and will improve the efficiency of traffic management by ensuring proper consideration of freight movements, significant contributors to urban congestion. Furthermore, enhanced consideration of freight transportation will benefit the transportation planning process as a whole, making it truly multimodal in its scope.
The transportation planning process usually entails the use of demand models to forecast, in combination with network models to analyze supply. For the most part, the evolving transportation modeling paradigms have focused on the analysis of passenger transportation, while paying little or no attention to freight. This is a consequence of the fact that passenger issues have traditionally been perceived as having the highest priority, effectively reducing the amount of resources allocated to freight transportation research and education. Generations of transportation planners have been trained, and provided with the tools, to deal with passenger transportation. Unfortunately, the same cannot be said about freight transportation.
A constellation of factors are increasing the already important role played by the freight transportation system in the vitality of the Nation's economy. Economic globalization, Just-In-Time production systems and electronic commerce (e-commerce) deserve specific mention. In a context of increasing economic globalization, in the interest of minimizing the total costs of producing and delivering goods, production systems are reaching out to global markets of supply and demand. The net effect of economic globalization is to extend the geographic realm of the freight transportation systems. Once confined by national boundaries, the transportation systems of today and tomorrow will have to operate across multiple nations at a global scale.
The expectations of performance are changing as well. More and more, businesses and consumers are relying on the freight transportation industry for the delivery of goods on demand, thus reducing the need for inventory stocks. Just-In-Time (JIT) production systems are the business expression of this trend. On the consumer side, e-commerce is providing consumers with the opportunity of purchasing goods way beyond the traditional geographic boundaries, and with unparalleled ease. Although not yet fully developed, e-commerce and JIT are expected to be increase the standard of performance expected from the freight industry. In other words, the freight system not only has to be able to transport the cargoes, it will be expected to do it at a reasonable price, with high reliability, and within the narrow time windows the customers want.
On the other hand, freight activity do produce externalities in terms of congestion, pollution, street blockage, noise (Small et al. 1989). In addition, an increasing body of literature is highlighting the need to study the health impacts produced by truck traffic. The human health effects of airborne particulate matter (PM) have been examined in numerous epidemiologic studies (e.g., Ostro, 1987), which have highlighted the health significance of particles less than 2.5 m in aerodynamic diameter (PM2.5), potentially more harmful than others because they can reach deeper into the lower respiratory tract. Given that nearly all diesel particles fall within the PM2.5 range, with median diameters ranging from 0.05 to 0.3 m (Godlee, 1993) health considerations demand the implementation of policies aimed at mitigating the negative impacts of truck traffic (e.g., Holguín-Veras et al. 2000d).
However, in spite of the negative externalities that
freight activity produce, there is no doubt that freight transportation makes
significant contributions to the Nation's economy. In 1994, business and
industry spent $421 billion to move 3.5 trillion tons of freight over the
transportation network (USDOT, 1996). Trucking, the dominant mode, accounts for
$331 billion or 79% of the total freight bill. Using 1994 Gross National
Product numbers, freight transportation made up 6.3% of total expenditures.
When revenues spent on inventory, warehousing, and logistics services are
included, these numbers go up to 10-11% of total expenditures. The impact of
freight on the
The above situation, in turn, adds pressure to transportation planning agencies that have to balance conflicting objectives (e.g., economic development, environmental protection and preservation, environmental justice, equity) in an environment in which the private industry has a major stake. As seen in this proposal the challenge is compounded by the complexity of freight movements and the lack of appropriate freight modeling methodologies.
This proposal formulates a comprehensive model of freight movements by framing the problem as a market in Cournot-Nash equilibrium, in the context of a large scale stochastic simulation. It is expected that the formulation and approach presented here will be able to provide a more meaningful depiction of freight movements able to: a) estimate freight origin destination matrices on the basis of secondary information, such as traffic data from Intelligent Transportation Systems (ITS); b) consider the flow of both commodities and commercial vehicles; c) consider commercial vehicle trip chaining, or alternatively Trip Length Distributions (TLDs); d) use logistic information in freight demand modeling; e) enable the study of the impact of real-time traffic control upon commercial vehicle traffic.
Metropolitan Planning Organizations, transportation planners and researchers have attempted to address freight issues by: (a) using advanced technologies to enhance system productivity and efficiency (e.g., Holguín-Veras and Walton, 1996a; and Regan et al., 1995); (b) implementing traffic control strategies aimed at reducing the negative impacts of freight activity traffic upon local communities (as in Holguín-Veras et al., 2000d); and/or (c) forecasting future freight supply and demand to estimate future needs (e.g., NYC EDC 1998). The successful implementation of the latter type of analysis is hampered by: lack of appropriate transportation modeling methodologies; and, lack of the specialized staff required to deal with freight issues.
From the methodological standpoint, the most significant hurdle to the inclusion of freight transportation into the transportation modeling process is related to the prevailing lack of knowledge on the fundamental mechanisms conditioning freight demand and supply. This situation is the result of the inherent complexity of freight processes, and of the fact that most modeling methodologies have been developed for passenger trips, not freight trips. This methodological void has necessitated the use of models originally developed for passenger demand, and, in the most questionable cases, the use of simplistic models such as estimating freight traffic as a function of the passenger car traffic. The use of such simplistic approaches may be an acceptable solution for small urban areas, where the amount of commercial vehicle traffic is of no major significance, but it is completely inadequate for major metropolitan areas, e.g., New York City (NYC), where the amount of truck traffic is of considerable importance. In such a situation, policy-sensitive freight demand models are required to examine the impact of freight specific policies upon commercial vehicle traffic. However, the development of policy-sensitive freight demand models faces significant hurdles which are a consequence of the inherent complexity of the mechanisms driving freight demand.
A number of factors add complexity to freight demand: a) there are multiple dimensions (i.e., value, weight, volume, trips) to be considered (Ogden, 1992); b) there are multiple decision makers (e.g., drivers, dispatchers) that interact dynamically and take decisions that affect freight demand (Holguín-Veras and Thorson, 2000a); c) these interactions takes place in a private context, for the most part not accessible to transportation planners; d) freight demand data is for the most part considered to be commercially sensitive; and, e) the opportunity costs of the cargoes exhibit a wide range (Cambridge Systematics, 1997), resulting in multiple user classes ranging from products such as gypsum with a market value of $9/ton; to products such as computer chips that cost in excess of $500,000/ton (Holguín-Veras and Walton, 1997).
Although the above factors been
discussed elsewhere (see Holguín-Veras and Thorson, 2000a), it is important to
discuss here the multi-dimensionality of freight movements. Contrary to passenger
transportation, in which there is only one unit of demand, (i.e., the passenger
that is also the decision maker) in freight transportation there are multiple
dimensions (e.g., volume, weight, and vehicle-trips) to be taken into account
when modeling freight movements. The multiple variables that could be used to
measure and define freight demand, have given rise to two major modeling
platforms: commodity-based and trip-based modeling. These platforms are unable
to provide a full depiction of freight movements. These limitations are related
to the inability to model empty trips, in commodity based modeling; and the
inability to consider the cargoes’ economic characteristics, in the case
of vehicle trip-based modeling (Holguín-Veras and Thorson, 2000a). Figure 1
shows the trip length distributions (TLDs) corresponding to a major modeling
Figure 1: Tonnage TLD and Trip TLDs
The role of the cargoes' economic characteristics is demonstrated theoretically in Holguín-Veras and Jara-Díaz (1999) in the context of optimal pricing. Empirically, the role of the commodities can be appreciated in the shipment size equation, obtained from the data used to create Figure 1 (Holguín-Veras and Thorson, 2000). Equation (1) is the assumed functional form, while equation (2) is the one obtained after estimation (t-statistics in parentheses).
(12.45) (-2.22) (3.99) (-6.01) (5.80) (6.94) (7.54) (9.82)
(13.25) (-2.31) (1.93) (2.37) (19.38) (1.68)
R2= 0.46 F= 209.19
As seen, the commodity types have a distinctive impact upon the shipment size function. Since the coefficient of ln(D) captures the rate of increase of shipment size for the “average” commodity, the ratios of the parameters of the interaction terms with respect to the coefficient of ln(D) can be interpreted as the marginal rates that could be positive or negative.
The analyses of the coefficients of the commodity variables indicate that four commodity groups exhibit positive marginal rates: Prepared foods (07); Monumental or building stone (10); Natural sands (12); Group 1A (a super group comprised of minerals); Group 1B (a super group of fuel and oils); and Non-metallic minerals (31). The common features among these groups are: (a) that they are usually transported in bulk; and (b) that they have relative high unit weight. These results indicate that, in order to take advantage of scale economies, shippers tend to transport these commodity groups in relatively large shipments (with respect to other commodity groups). The commodity groups with negative marginal rates are: Agricultural products (03); and group 0A (a super groups of agriculture and meat products). For the most part, these groups are comprised of commodities that, in developing countries, are usually transported in relatively small shipments.
An important element in equation (2) is the set of the binary variables that represent the intersectorial flows, where a subscript RR refers to Retail-to-Retail flows, RW refers to Retail-to-Wholesale, OW represents Other-to-Wholesale, etc. The slope of the shipment size functions is smaller when the flows involve Retail activities, with the smallest corresponding to Retail-to-Retail flows. Flows involving Other have the second largest slopes; while the absolute largest corresponds to Wholesale-to-Wholesale flows. As shown in equation (2), the slope of the shipment size function depends upon the commodity. The cargoes' economic characteristics also play a role in subsequent stages of mode choice and traffic assignment/routing.
The estimation of future freight transportation supply and demand is undertaken with the help of network and freight demand models. When modeling freight demand, basic data is sought to enable the analyst to appropriately model the decision processes associated with freight demand. In this context, freight origin-destination (OD) matrices are one of the most important pieces of information. OD matrices can be estimated from: a) direct samples, and, b) secondary data sources such as traffic counts, i.e., OD synthesis. OD synthesis tries to overcome the limitations of direct sampling methods by using traffic counts –linear combinations of the OD flows–to estimate the OD matrices. Selected publications on OD synthesis are shown in Table 1.
Table 1: Selected references on OD synthesis and related problems
Although there is a vast body literature on the subject of OD synthesis, covering a variety of different problems, the estimation of freight OD matrices, in general, have received relatively little attention from researchers and transportation professionals. After a comprehensive search, only three publications were found: Tamin and Willumsen (1988); List and Turnquist (1994); and, Nozick, Turnquist and List (1996). Tamin and Willumsen (1988, reprinted in 1992), developed a formulation to obtain the parameters of the gravity-opportunity model that best reproduce a given set of traffic counts. Their approach requires link volumes and estimates of total tons produced and attracted at each zone. List and Turnquist (1994) developed a formulation of OD synthesis as a large-scale linear programming problem in which the decision variables are the OD flows, and the objective function is a weighted combination of the deviations of the estimated volumes with respect to the target values.
The amount of freight being transported is of significant
importance. In 1998, more than 475 million tons of freight were
moved to, through or out of the Region. The inter-county freight movements
estimated from a waybill sample, amount to close to 200 million tons. The majority of these goods arrive, or depart from, terminals in
The economic costs of such congestion are of undeniable
importance. Federal Express claims that it costs 40% more to deliver in NYC
than other comparable locations. United Parcel Service states that it costs
them $0.40 more to deliver a package in NYC than in
Recognizing the importance of incorporating freight
transportation into the planning process, the local MPO (i.e., the New York
Metropolitan Transportation Council, or NYMTC) created the Freight
Transportation Working Group, to provide a forum for the discussion of freight
policy; and, more relevant to this research it decided to develop a Regional
Freight Model (a research project, intended to study the state of the
practice of freight modeling techniques for use in the Regional Freight
Model is under way, Holguín-Veras, 2000d). In addition, a number of
transportation agencies are undertaking, or have recently finished, a dozen
different freight transportation studies. Methodologically, the modeling
approaches implemented in these studies are based on relatively simplistic
assumptions. This situation is recognized by the authors of these studies and
correctly explained as the result of lack of research on the area of freight
demand modeling. Taken together, these studies provide an
unique picture of the freight transportation system in the
One of the guiding principles of this research project is to take advantage of a synergetic relationship between theory and practice. In this context, special attention is being paid to ensure a meaningful collaboration with key representatives of the freight transportation industry and transportation agencies. This is of the utmost importance because: a) most of the freight data is of proprietary nature; b) the expertise of the freight transportation operators is needed to ensure the conceptual validity of the methodologies developed as part of this project; c) there is an urgent need to establish bridges of communication between the research community and the freight private industry. As seen in the attachments, key transportation companies have expressed their support to this investigation. The same spirit of collaboration needs to be established with the relevant transportation agencies. In this context, the research team has requested the collaboration of the New York Metropolitan Transportation Council (NYMTC), which together with the Transportation Coordinating Committee (TRANSCOM) and the New York State Department of Transportation have expressed their support to this project.
As it shall be seen when describing the analytical formulations and work program, the proposed research spans across a number of different areas. This offers an unique opportunity to produce contributions on a number of different fields and disciplines. Among them, one must highlight: transportation planning, transportation economics, large scale simulation, stochastic optimization. Achieving the long term objectives of the proposed research ultimately will:
v lead to an enhanced understanding of the nature and characteristics of freight transportation demand by considering the flow of both commodities and commercial vehicles;
v improve the assumptions on which the planning of crucial components of the infrastructure of the Nation (e.g., intermodal terminals, highways, ports) is conducted;
v provide the foundation for an effective integration of freight considerations into the transportation planning process;
v provide the tools for the incorporation of freight intermodal planning into the metropolitan planning organization process;
v significantly reduce data collection costs associated with gathering freight demand data;
v benefit other application areas, such as estimation of origin-destination matrices for passenger trips (or vehicle trips), advanced traffic management and the like;
v consider commercial vehicle trip chaining, or alternatively Trip Length Distributions (TLDs);
v use logistic information in freight demand modeling;
v enable the inclusion of freight movements as part of the traffic management process;
v lead to the development of methodologies aimed at integrating real-time information into the demand estimation process;
v enable the study of the impact of real-time traffic control upon commercial vehicle traffic;
v lead to the development of large scale freight specific stochastic simulation techniques;
v enable the testing and implementation of stochastic optimization techniques;
v lead to a better understanding of the role of key economic parameters such as marginal cost functions, and market elasticity upon the behavior of commercial vehicle traffic.
The freight transportation system has an impact on a relatively large number of stakeholders: private industry, transportation agencies, local communities, environmental groups, researchers and the like. This situation requires the implementation of a two-way feedback process as to ensure the research team takes advantage of the considerable expertise, and unique perspective offered by each of the aforementioned stakeholders. This would enable the research team: a) to contribute to the creation of bridges of communication between the planning community and the freight industry; b) to help these stakeholders understand the value of freight transportation research; c) to communicate/disseminate research results directly to the stakeholders. In addition to the above process, this research will disseminate results in the traditional ways by means of journal papers, professional presentations and consultations with other researchers and practitioners.
The objectives of this proposal are associated with the algorithmic implementation of the concept of Integrative Freight Market Simulation (Holguín-Veras, 2000b) and the corresponding testing in a small case study. In more specific terms, the objectives for this period of the research are:
v To develop the algorithms needed for implementation of the Integrative Freight Market Simulation in the context of a simplified version of the problem (i.e., single commodity and one type of commercial vehicle);
v To produce estimates of the key economic parameters needed to implement the proposed concept;
v To design a set of meaningful test cases to be used as a benchmarks;
v To test the efficiency and accuracy of the algorithms.
Jose Holguin-Veras’ long term research goals are associated with enhancing the state of the art of transportation modeling and transportation economics, so that a complete picture can be developed on the broad impacts of transportation activity, and the most appropriate ways to model transportation phenomena. Professor Holguín-Veras’ main area of work focuses on the integration of transportation economics principles into transportation modeling. Work Plan, Schedule, Tasks
The Integrative Freight Market Simulation is intended to provide an approximation to the processes that take place in real life, in which: producers create or transform the commodities that are demanded elsewhere; consumers utilize products and raw materials created by the producers, for either personal use or as input to production processes; shippers arrange for carriers to transport the commodities from places of origin to their destinations; while the government puts together regulations and the basic infrastructure (as in Harker and Friesz, 1986). As a simplifying assumption, the proposed approach focuses on producers, consumers, carriers (shippers are not explicitly modeled), while the government is divided into a regulatory body and a traffic management center (TMC) that provides real time traffic information and exercises traffic control.
A second simplifying assumption is related to the spatial price equilibrium. As indicated by Samuelson (1952), the flow of goods into and out of any given area is determined by the economics of production and transportation. In this context, producers send products to the market if, and only if, the corresponding production plus transportation costs are lower than those of their competitors; otherwise no flow of goods is generated. In the strictest sense, the production levels are determined by the outflow of goods resulting from the spatial price equilibrium. This process, which explains the economics of the generation of cargoes is not explicitly considered. It is assumed here that the quantities of goods produced and consumed are constant and estimated exogenously. In other words, the amount of the cargoes produced and consumed in the different transportation analysis zones (TAZs) are known, a routine assumption in transportation studies.
The location and the number of vehicles owned and operated by the different carriers are assumed to be known. The proposed framework allows the consideration of Trip Length Distributions (TLDs), or alternatively trip chain data. These assumptions are reasonable because: a) the location and number of commercial vehicles owned by the different carriers are usually collected by periodic surveys, e.g., Truck Inventory and Use Survey (U.S. Census Bureau), or could readily be estimated from employment databases such as Dun and Bradstreet's; b) the TLDs, or trip chains, could readily be estimated by direct interviews or travel diaries.
The role of the government is reflected through the actions of the Traffic Management Center (TMC) which provides real time traffic information and exercises traffic control. Since the proposed approach focuses on the short term, for which infrastructure and regulations are reasonably, the actions of the regulatory body are of limited scope and could be disregarded.
In essence, the proposed framework would attempt the estimation of the trips made by freight transportation providers in the study area, such that:
II. the user requirements are met, i.e., the commodities produced by and attracted to each TAZ are transported;
III. the resulting trip chains are consistent with trip chain patterns captured in travel diaries, or alternatively, known Trip Length Distributions (TLDs);
IV. the resulting commercial vehicle traffic is consistent with secondary data sources, e.g., ITS traffic data.
Conditions I and II are termed primary constraints, i.e., constraints that must be met. Conditions III to IV, referred to as secondary constraints, are those that could be relaxed under certain circumstances. Condition I ensures proper consideration of the interactions among freight providers in the supply market. Condition II ensures consideration of user requirements. Conditions III and IV are information constraints expected to bound the solution.
In real life, freight transportation carriers maximize profits by participating in market competition. As a result of this process, carriers implement tours that maximize their profits and collectively meet the user requirements in terms of the goods to be transported. The transportation service provided (referred to as provision of service, measured, for instance, in ton*km or veh*km) is comprised of a certain number of loaded trips, yk, and empty trips, zk. For a given company k, the provision of service is:
where xijk is equal to one, if node i precedes j in the tour for company k and zero otherwise; and cij is the cost (or distance) matrix (i and j are nodes representing TAZs).
In the strictest sense, the mathematical optimization of the process described above would require the maximization of the profit functions of the different carriers, subject to the systems constraints outlined in conditions II to IV. Conceptually, this problem could be represented as maximizing the following profit functions:
where: p(y1+y2+… yn) is the market price, i.e., the inverse demand function; and ck is the cost function.
Since both yk and zk depend upon the routing patterns, it is evident that equation (4) is a rather elaborate form of a vehicle routing problem, in itself a NP-hard problem. As a way of simplification, it is assumed that the objective function outlined in equation (4) can be decomposed in two separate problems. The first problem is the determination of the provision of service (yk + zk) consistent with profit maximization in market equilibrium conditions; while the second problem is related to the determination of the tours consistent with the provision of service estimated above for the different carriers. Schematically:
Figure 2: Solution approach (Conditions I and II)
Problem 1 is solved assuming a Cournot-Nash market equilibrium model (Varian, 1992), which is discussed next. Problem 2 is solved with heuristics that ensure satisfaction of the Cournot condition and the other system constraints. Under the assumption of Cournot-Nash equilibrium, a firm k contributes to the market the amount yk that maximizes profit, assuming that the competitor’s decisions are held constant. However, in doing so it produces a given number of empty trips zk, reflected in its cost function, that may be assumed to be an implicit function of yk. The profit function for carrier k is:
Since the total supply equals Y= y1+y2+… yn, equation (5) could be written as:
The optimality conditions are:
which results in:
Designating the market share for company k as:
equation (7) becomes:
where e represents the market elasticity. Alternatively:
where is the marginal cost
As indicated by Varian (1992), the Cournot solution is an intermediate solution between a monopoly, sk =1, and a perfectly competitive market, where the number of suppliers tend to infinity and sk =0. This represents the freight industry in urban areas, characterized for a high number of competing companies, with no single company having a dominant position in the market. For that reason, the assumption of Cournot equilibrium is reasonable.
Equation (12) provides key insights into the nature of the solution of the problem defined by conditions I and II. As seen, the marginal cost includes the empty trips made when providing yk. Since at equilibrium the market price equals the marginal cost divided by (1- sk/e) and, at a given moment, the market price, p(Y), the market shares, sk , and the market elasticity, e, are reasonably constant, the problem reduces to finding the quantities (yk+ zk) that for a given company, ensures satisfaction of equation (12). The quantities (yk+ zk) represent the total amount of transportation service contributed to the market by company k, in terms of loaded trips, yk, and empty trips, zk, (e.g., in ton*km or veh*km). These amounts are determined by the routing patterns implemented by firm k in the area.
This support the idea of framing the problem as one in which the objective is to obtain the set of tours, for the different companies, that are consistent with equation (12) and condition II. This ensures satisfaction of Cournot equilibrium and user requirements, i.e., the primary constraints of the problem. Conceptually, this is equivalent to a bi-level formulation with the Cournot solution at the top level and a routing problem as the secondary problem.
The solution approach depicted in Figure 2 implies that the market competition takes place at an aggregate level, above specific market segments such as individual OD pairs, which is appropriate for urban areas, where freight carriers may compete in all OD markets. The assumption of competition at the aggregate level is of less general applicability to intercity freight transportation. In such cases, there may be situations in which the freight carriers compete in all markets (which seems to be the case of long-haul trucking, where companies compete at a national scale) and the assumption of aggregate competition may be appropriate; but there are other cases in which the market competition takes place at specific market segments, i.e., in specific OD corridors. In the latter case, the approach outlined here would not apply.
Figures 3 shows the network used in the example, as well as the requirements in terms of productions and attractions at each of the transportation analysis zones (TAZs). Figure 4 shows the true routing patterns, i.e., the solution, used as a benchmark to test the proposed approach. The first part of the analysis consists of the estimation of the relevant parameters. The example itself focuses on estimating the routing patterns consistent with Cournot equilibrium, as it would be done in a real life application. It is expected that by using error-free parameters (not available in real life) insights could be gained into the potential of the approach.
As shown in Figure 3, there are four TAZs (nodes 1 to 4).
One carrier is located in node 1 and the other in node 3. The capacity of the
vehicles is 3 units. Travel costs are shown next to each arc. The user
requirements (production, P, and attraction, A) are shown in the table.
Internal trips, e.g., from 1 to 1, are not allowed. Actual routing patterns are
shown in Figure 5, where solid lines represent deliveries and dashed lines
represent empty trips. In this example, the average cost, used as a proxy for
the market price equals 45 units divided by 8 trips, i.e., 5.625. The market
shares for company 1 (located in node 1) and company 2 (located in node 3) are
respectively equal to 19/45 and 26/45, i.e., the ratio of the total
transportation service provided (measured by the total trip costs) with respect
to the market total. It is assumed, for illustration purposes, that the market
elasticity, e, equals 2. Assuming marginal cost functions equal to ck = ak (
Figure 3: Example of network Figure 4: Actual routing patterns
The first step in the process is to estimate the service provided by each company. On the basis of the (perfect) parameters estimated before, the Cournot solution is:
solving for the unknowns, the following values are found: y1+ z1 = 19; and y2+ z2 = 26 (which should not come as a surprise because, in this example, the key economic parameters have been perfectly estimated). The second step is to construct the tours consistent with the Cournot solution (above) and the other system constraints, most notably the user requirements (productions and attractions of commodities).
Figure 5 shows the different trials required to reach the solution d). Case a) is an example of a non-feasible solution. Cases b), c) and d) are feasible solutions that were screened out on their ability to replicate the Cournot solution. As shown, the use of the Cournot condition and user requirements leads to the solution of the problem.
Figure 5: Different trials
The framework discussed in the previous section is able to deal with market equilibrium conditions and the definition of the corresponding tours. In the remainder of this section, conditions III and IV are discussed. Condition III is particularly important because it provides a mechanism for the consideration of commercial vehicle trip-chains; and, more importantly in the long term, it provides a natural way to include logistic information as part of the freight demand modeling process. Condition III also introduces randomness in the process. This is because, although the trip length distributions for typical freight carriers may be reasonably constant, individual trips represent different realizations of the random variable captured in the TLD. This leads to the idea of extending the framework of Figure 2 as a large scale stochastic optimization problem, using simulation as the tool to generate solutions (including the generation of trips according to TLDs or trip chain data), checking at each step the feasibility of the generated solutions.
Condition IV could readily be considered as part of the tour construction algorithms, by incorporating as the objective function a weighted function of the target values and the traffic estimated by the model (as in List and Turnquist, 1994). The incorporation of an objective function, such as equation (14), in the optimization process would enable the estimation of freight OD matrices consistent with: a) market equilibrium assumptions; b) known commercial vehicle trip chain patterns; and c) secondary traffic data, such as traffic data collected by ITS.
where F is the sum of squared differences between target and estimated values at a given iteration.
The joint consideration of conditions I, II, III and IV would require an implementation framework such as the one depicted in Figure 6. The solution resulting from the framework of Figure 6 should be interpreted as an equilibrium, i.e., steady state, solution. On the basis of such solution, and the resulting tours, the impact of real time traffic control techniques upon commercial vehicle traffic could be analyzed, for instance, by perturbation techniques. This would ensure a more realistic representation of freight movements.
In addition to the consideration of the conditions discussed before, the proposed framework lends itself (because of the flexibility offered by simulation) to considering hierarchy systems with Truck Load (TL) and Less than Truck Load (LTL) interactions. TL and LTL interfaces (i.e., warehousing and distribution centers) could be readily considered as particular cases of TAZs.
Although the proposal has focused on individual carriers, for description purposes, it is important to highlight that, because of practical considerations, it may be advisable to cluster the freight carriers located in the same TAZs in the same group. Among other things, clustering freight carriers significantly reduces data collection needs because zonal estimates of economic parameters could be used instead of estimates for individual carriers. However, given that very little is known about the implications in terms of computational performance, data costs, and accuracy, more research is warranted before conclusive guidelines are established.
Figure 6: Solution approach (Conditions I, II, III and IV)
Complex systems similar to the one described in this proposal, are being modeled now due to the requirements of modern society. Today, it is not sufficient to model isolated and highly simplified systems. The interactions among different systems are needed to develop useful solution that will respond to the needs of our highly efficient society. However, unlike very simple systems, these complex systems are difficult to model a closed form function. Thus, simulation appears to be the most feasible approach for modeling complex systems. Assuming that, the simulation models can be efficiently run using a performance computer, the problem becomes how to develop solutions using simulation. Traditionally, optimization is the approach used to determine “best” (optimal) solutions to a given problem that in general can be expressed in the form of an objective function to be optimized and a set of contraints. In its most general form, this problem (P) can be shown as:
(P) Min (Max) c(x) (15)
Subject to A x b (16)
x 0 (17)
Where: c(x) is the objective function with a known analytical form; A is a constraint matrix; b is vector of capacities; and x is vector of decision variables.
However, when simulation is used the functional form of c(x) is not known to the analyst. Thus, the above approach that attempts to minimize (maximize) a given function is not valid anymore. In the case of simulation, the output of each simulation run can be used as one evaluation of a function. Thus, simulation becomes a function evaluator of some sense. This is shown in Figure 7.
Figure 7: Functional Relationship Between the Input and Output
In the simulation case, the system’s response to the input is evaluated and an output is obtained. In the most effective simulation optimization approaches proposed in the literature, the system is treated as black box (Glover et al., 1996). This mainly due to the desire for separating simulation from the optimization in order to allow both components to evolve separately. This type of simulation / optimization approach proposed by Glover et al., 1996) is shown in Figure 8.
Figure 8: Continuous
In this approach optimization procedure uses the output from the simulation model obtained as a result of the inputs fed into the simulation model. Historically, iterative algorithms have been used for simulation / optimization problems. Among those, Hook and Jeeves Pattern Search is the most widely used one (1961). This technique is well applicable to simulation optimization problems since it does not us the derivative of the objective function. Thus, we do not have to have express our objective function in terms of a differentiable function of the decision variables. Hooke-Jeeves technique alternates between sequences of exploratory search and pattern moves. The exploratory searches serve to establish a direction of improvement whereas the pattern moves project the solution vector o a new point in the solution space to restart the exploratory searches.
Most recently, artificial intelligence techniques have been developed to conduct smarter searches in the case of highly non-linear and stochastic systems. Here, some of the important techniques / algorithms that can be employed to develop a smart “optimization” procedure that can find the best solutions given the highly complex and non-linear nature of the simulation include:
Evolutionary algorithms (
2. Simulated Annealing (Kirkpatrick et al., 1983): A detailed anology with annealing in solids provides a framework for organization of the properties of very large and complex systems. This framework is especially useful in solving combinatorial optimization problems.
3. Tabu Search (Glocer and Laguna, 1997): Tabu search is meta-heuristic that has important links to evolutionary and genetic computing. Tabu search based is based on the understanding that problem solving must incorporate adaptive memory and responsive exploration. Tabu Search differs from memoryless search techniques that rely on semi-random processes in that it is guided by information collected during the search.
Among all these techniques, Tabu Search (TS) is the one that has provided analysts and researchers with the most promising results for solving large scale combinatorial problems. To intelligently guide the search process, TS uses recency and frequency memories. Recency memory is a short tem memory which discourages the moves that lead to solutions with attributes shared by other solutions recently shared. A standard form of frequency memory encourages moves leading to solutions whose attributes have been rarely seen before.
In addition to these AI based techniques, other well-known AI approaches such as, neural networks, can be used in conjunction with TS. Neural Networks can be employed to map out different values of the objective function, in this case “simulation.” The neural network is used as predictor that helps us avoid inferior results. This in turn reduces the number of simulation evaluations and accelerates the TS process. In our research project, we will test the feasibility of these simulation / optimization procedures and determine the most suitable combination for the specific problem we will have in hand.