Synthesis of Spatial Network Visualization with Quantitative Metrics for Prioritizing Highway
Synthesis of Spatial Network Level Metrics with Local Quantitative Metrics for Prioritizing Transportation Projects
Abstract
Prioritizing and selectingfew critical projects from several competing transportation projects is a multiobjective combinatorial optimization problem (MOCO). In such problems, transportation planners and managers are interested in visualizing and analyzing the trade-offs involved. This paper develops methodology for synthesis of spatial network level metrics with local quantitative metrics for planning and prioritizing of a large and diverse portfolio of transportationinvestment projects. The methodology serves as an aid to planners, managers and engineers to visualize and compare cost-benefit trade-offs. The methodology is based on incorporating network level metrics along with local metrics in formulatinggeneric MOCO algorithm and visualizing multiobjective trade-offs on a spatial network.A district level case study demonstrates the use of methodology in trade-offs analysis for short- and long-range transportation plans. The methodology is adaptable to other areas like water supply management, manufacturing and service industry where spatial consideration is important.
Key Words: MOCO problem; network visualization; Entropy; transportation planning; risk analysis.
1. Introduction
Transportation professionals at district and state transportation agencies in the United States are increasingly pressed with the task of allocating limited public funds among potential highway improvement projects and the subsequent determination of the order in which selected projects should be undertaken. There are several projects competing for these limited funds. Prioritizing highway projects is basically a Multiobjective combinatorial optimization (MOCO) problem. Over the last decade, many algorithms have been developed to solve such types of problems. But these mathematical models have been rarely used by managers and professionals in actual decision making. The major problem is lack of visualizing and understanding these models and trade-offs involved. We believe that models should be represented in a clear and informative way.
This paper aims at integrating network level metrics with local quantitative metrics to better understand the impact of selecting certain projects on the specified geographical region. The scope of the paper includes: developing a generic MOCO model for prioritizing and planning transportation projects, developing a spatial network and network level metrics, identifying useful quantitative metrics for the comparison of diverse projects, developing an interface for visualizing project portfolio information and relative trade-offson the spatial network and presenting a case study with short and long-range plans from the Culpeper district in the state of Virginia.
The organization of this paper is as follows. Section 2 provides background for generic MOCO formulation of projects planning and prioritizations problem. Section 3 describes the methodology for integrating network level metrics with quantitativemetrics. Section 4 presents the case study and discusses the scalability of the developed methodology.The last section provides a summary.
2. Background
The purpose of this section is to formulate the projects planning and prioritization problem as a multiple objective combinatorial optimization problem. Projects planning and prioritization problem is combinatorial in nature and it involves multiple and conflicting objectives.In other words, we are interested in studying finite set of competing projects and combinations and arrangements of these projects that satisfy specified criteria. Our MOCO formulation is based on the general model as per Ehrgott and Gandibleaux (2002).
The finite action set A = {a1,…, an} representsn competing transportation projects, where ai represents a unique project. The power set of A is the set of all subsets of A and is denoted by P(A). The feasible set of the MOCO problem can be defined as a subsetX such that,
XP(A)
The problem can be formulated in terms of binary decision variables. A binary decision variable xi is introduced for every element aiA. Then, a basic feasible solution SXcan be represented by a binary vector {x1,…, xn} where
xi = 1 ai S
0 otherwise
In other words xi =1 indicates that ith project is selected in the final solution and xi=0 suggests that ith projecthas not been selected in the final solution. A typical multiobjective problem can have Q objectives or criteria, zjwhere j = 1,…, Q.Then the overall problem takes the form of maximizing a set of objective functions:
Maximize
Examples can be easily constructed toclarify this MOCO formulation. For example, assume that there are 3 competing projects in a specified region and the decision makers are considering two criteria for projects prioritization: first, to select a portfolio of projects that will address higher average daily traffic (ADT) problem is high and second, to select a portfolio ofprojects that will address higher crash ratesconcerns. ADT and crash rate are two important measures in transportation planning. These two objectives are not necessarily in conflict, but definitely they will not yield the same portfolio of projects. The action set, A = {a1, a2, a3} for this particular problem is of order n = 3. Then, the power set of A will be of order 23= 8 as follows:
P(A) = {, {a1}, {a2}, {a3}, {a1, al2}, {a1, a3}, {a2, a3}, {a1, a2, a3}}
The basic feasible set for this problem will be any subset X of the power set P(A). There are three binary decision variables x1, x2 and x3 and a basic solution S can be represented by a binary vector {x1, x2, x3}. One particular solution can be {1, 0, 1}, i.e., in final portfolio, project a1 and project a3 have been selected and project a2 has not been included.The two objective functions will be z1(S) and z2(S)representing two different criteria as mentioned above.
Thus, the overall combinatorial model is:
Maximize
S X
XP(A)
A = {a1, a2, a3}
xi = 1 ai S
0 otherwise
3. Methodology
The purpose of this section is to develop the spatial network level metrics, to identify useful local quantitative metrics for the comparison of diverse projects and toimplement generic MOCO algorithm and represent multiobjective trade-offs on the spatial network.The synthesis of spatial network level metrics with quantitative metrics willgreatly enhance understanding and analysis of complex models for transportation planners and managers.The first step in proposed methodology is to develop a spatial network,G (N, E) of cities and highways for a geographical region under study where N is the collection of nodes and subset E of N X N is the collection of arcs. The network is undirected. The nodes in this specific network represent major cities in the specified region and arcs represent the highways connecting these major cities. The network can be a short one consisting of only a few cities or it can be a very detailed one consisting of large number of cities depending on the nature of analysis a decision maker is interested in. The second step is to locate the competing projects on the network, so that plannerscan have a comprehensive look at the distribution of projects throughout the specified region.
The next step is to gather quantitative evidences for each candidate project from a given set of projects being considered for funding. There can be many local quantitative metrics based on the criteria to be satisfied while selecting a portfolio. Few good quantitative metrics are level of service, ADT, crash rate, volume to capacity ratio and flow rate on each arc in the network. Unemployment rates and environmental issues in different portions of the network are also important measures. Cost effectiveness of individual project is another important metric. Then there are some specialized measures developed by transportation agencies like bridge sufficiency rating, etc. The significance of each quantitative metric varies according to the criteria selected by planners and decision makers. For example, if safety is one of the main criteria, then crash rate is the most important metric. If economic development is a major criterion, then unemployment rate is a highly significant measure.
Among several measures, we believe that ADT and crash rates on each individual arc and cost of the project are three meaningful and typical measures for transportation projects planning and prioritization. The paper mainly uses these three measures for the case study. But, it is not binding. Similar analysis can be performed using any of the other local quantitative metrics.
We can apply generic MOCO formulation to the developed spatial network in which different arcs have different values of quantitative measures. For one criterion, individual arc crash rates might be more important and for another criterion, arc ADT might be more significant. Consideration of arc ADTs will give one portfolio of projects and consideration of arc crash rates will give another. The problem is essentially of which combination of projects will be satisfy these two criteria. It is generally observed that the decision makers will try to choose a portfolio that maximizes these local quantitative measures. With many different local criteria under consideration, there is one more important criterion, i.e. topology of the network, which is generally neglected by the decision makers. Fair distribution of the resources among all arcs (highways) is as important as maximizing the local criteria. The advantage of the methodology is that decision makers can easily visualize the distribution of the projects throughout the network. They get good understanding of whether the resources are all concentrated in a specific portion of the network or whether they are equally distributed. But mere visualization of the distribution is not sufficient. It can be subjective. One decision maker might interpret it differently than the other. To solve this problem, we propose other network level quantitative metrics which can be added as separate criteria along with local level criteria to be satisfied.
We use a special network complexity index to see how uniformly the resources are distributed throughout the network. Different indices can be developed for different network level quantitative metrics. One of such network complexity index can analyze the distribution of the projects throughout the network. This index is denoted by,
where,
Here N denotes the total number of projects in the selected portfolio and Nidenotes the number of projects from the portfolio that are on the ith arc. Higher value of the indicates more uniform distribution of projects throughout the spatial network and lower value of index indicates that the distribution of projects is not uniform throughout the network or the projects are concentrated among few cities or only a few highways in the network. In general, heavy concentration in any particular area of the network is not advisable unless there is a good justification for it.
Similarly, another network complexity index can be developed to analyze the distribution of the funds throughout the network by modifying Pi in the previous equation as:
Where C denotes the cumulative cost for all the projects in the selected portfolio and Cidenotes the total cost of the projects from the portfolio that are on the ith arc. Thus our goal is to maximize these network level indices along with other local objectives in the MOCO formulation.
Many solution methods have been developed to solve MOCO problems. These methods are mainly classified into three categories based on the role of the decision maker in the portfolio selection process: priori mode, posteriori mode and interactive mode (Ehrgott and Gandibleaux, 2002). We prefer interactive mode because in this mode, managers and planners are actively involved in the solution process.
The last step in the methodology is to show the trade-offs graphically. A key aspect of the methodology is the interface used to present project information on the network. Graphing and visualizing two objectives trade-off problem in the decision space or functional space is relatively easier. But when a typical multiobjective problem consists of three or more objectives, suddenly visualizing and understanding the trade-offs involved becomes difficult. The problem essentially turns into visualizing multivariate data involving several variables simultaneously. Many techniques have been discusseed to represent trivariate or multivariate data effectively (Cleveland, 1994, Gower & Digby, 1981, Tufte, 1997). Trivariate data canbe represented by bubble plots, in which values of two variables are indicated by the location of the bubble on a two-dimensional scatter plot and value of third variable is represented by the size on the bubble. One important technique to represent multivariate data is scatter plot matrix. A scatterplot matrix is defined as a square, symmetric table or “matrix” of bivariate scatterplots (Cleveland, 1994).
We propose a matrix of trivariate bubble plots to visualize and understand the trade-offs involved in projects planning and prioritization. Our symmetric matrix has m rows and m columns. Number of rows and columns are equal to the number of nodes (cities) in the spatial network developed earlier. The intersection of row i and column j contains a bubble plot showing the total number of projects on a typical arc between two specific cities. Three criteria can be shown simultaneously on this bubble plot. For example, a typical matrix will have bubble plots showing average daily traffic on x-axis, crash rate on y-axis and cost of the project will be indicated by the size of the bubble. One can develop similar matrix different quantitative metrics and criteria. This matrix presents a large amount of information to the decision maker in a very efficient manner.
4. Case Study
Followingdistrict level case studyshows the application of the methodology. Culpeper district in the state of Virginia is selected for the case study. Table I shows sample project information collected for this case.Project data include the project ID, route, starting and end points, ADT, crash rate and cost, of the project.
Table 1>
Specified region consists of 42 competing projects. Thus, the initial action set for the problem, A = {a1, …, a42} is of order n = 42. The developed spatial network is shown in Figure 1. The network consists of 14 nodes (cities) and 21 arcs. The number on each arc represents actual highway number. The network consists of mainly primary highways in the Culpeper district. Interstate highways are not included in the network since interstate highway projects come under a different state level interstate highway projects prioritization program. The methodology is scalable. A similar state-level interstate highways network can be developed for interstate highway projects prioritization plan.
< Figure 1>
Projects are grouped together according to their location in the network and can be described with corresponding quantitative information such as number of projects, costs, average cost, ADT, ADT per dollar, etc. As an example, Figure 2 shows the total number of projects on each arc in the network. Such aggregate statistics can suggest the network complexity and the potential gross efficiencies of investments in projects on each individual arc. Another good example of quantitative evidence can be the ratio of cumulative accident rate and the total project cost.
< Figure2
After projects are grouped based on their location in the network, analysis can be done to compare projects within a group. Figure 3 shows an example of such an analysis for projects planning and prioritization. Shown are the projects on a particular arc. Coordinate axes are used with average daily traffic and crash rates as measures of crash exposure and crash intensity. Each of the projects is then represented by a bubble icon, centered on coordinate values of the project and whose size represents the project cost. The variations among project costs and the contribution of each project in terms of crash exposure and crash intensity is shown in the figure.
< Figure3
The power set of the initial action set is of the order 242. Implementing the methodology on every element of power set is both unnecessary and impossible. Some of the solutions in the power set are obviously inferior. It is important to remove such obvious inferior solutions at this stage to simplify the application methodology. For example, empty set, and sets of only one project can not be efficient. Similarly set of all the projects is also meaningless. As mentioned previously, using interactive mode with the decision maker, many such inferior solutions can be identified to develop a small set of meaningful solutions. It is also helpful to know the approximate number of projects the decision maker is interested in undertaking simultaneously.
After initial analysis, the final set of efficient solutions consists of combinations of only 20 projects from initial action set of 42 competing projects. These 20 projects along with other relevant information are shown in Table II.
5. Summary
The developed methodology for synthesis of network level metrics with quantitative metrics for projects prioritization can serve as a decision aid among the transportation planners.
6. Acknowledgment
The authors are grateful to the members of the steering committee from Virginia Transportation Research Council and Virginia Department of Transportation: Chad Tucker.
References
Cleveland W.S., (1994). The Elements of Graphing Data (Rev. ed.). Summit, NJ: Hobart Press.
Ehrgott M., Gandibleux X., (2002). Multiobjetive Combinatorial Optimization – Theory, Methodology, and Applications. Multiple Criteria Optimization: State of the Art Annotated Bibliographic Surveys.
Gower J.C., Digby P.G.N. (1981). Expressing complex relationships in two dimensions. In V. Barnett (Ed.), Interpreting Multivariate Data. Chichester, UK: John Wiley and Sons.
Jones C.V., (1996). Visualization and Optimization.
Shannon C.E.,(1948). A Mathematical Theory of Communication. Bell System Technical Journal, Vol. 27, PP. 379-423 and 623-656.
Tufte E.R., (1997). Visual Explanations. Cheshire, CT: Graphics Press.
Baker J.A., Lambert J.H., (2001). Information systems for risks, costs, and benefits of infrastructure improvement projects. Public Works Management and Policy, 5(3):198-208.
Capital Improvement Program (2000). Delaware Department of Transportation, Dover.(
Charlottesville-Albemarle Regional Transportation (CHART) 2021 Plan Update. (2001). Thomas Jefferson Planning District Commission. (