2013 Session: 844

• Joint Optimization of Supply Chain Network Design and Highway Pavement Rehabilitation Plan Under Traffic Equilibrium
  Abstract: Expansion of industries often leads to construction of new facilities, and these facilities often induce additional traffic demand in a transportation network to or from these facility locations. This imposes pressure on the existing highway transportation infrastructure especially due to the heavy freight vehicles, which has a major impact on the traffic congestion and highway pavement deterioration. Hence, it is important to design facility locations in a holistic manner, taking into account the routing of vehicles as well as planning of pavement rehabilitation. This paper presents an integrated modeling framework for a capacitated facility location problem which incorporates traffic routing under congestion and pavement rehabilitation under deterioration. The objective is to minimize the total facility investment, transportation delay, along with life cycle costs of the pavement facilities. A bi-level mixed integer non-linear program (NLP) is developed to simultaneously determine the optimal number and location of facilities, optimal routing of shipments, and optimal pavement rehabilitation frequency and intensity. A Lagrangian relaxation (LR) solution framework is developed to solve the problem and get optimal solutions. A numerical case study on a hypothetical transportation network is conducted, and the computational results show that the proposed algorithm is able to solve the problem effectively. Managerial insights are also drawn.
  Authors: Hajibabai, Leila; Bai, Yun; Ouyang, Yanfeng
  Authors: Hajibabai, Leila; Bai, Yun; Ouyang, Yanfeng
  Year: 2013
  Document Type: Paper
  Subject: Planning and Forecasting
  Session: 844
  Paper Number: 13-0796
• Online Stochastic Routing Incorporating Real-Time Traffic Information
  Abstract: This study develops on-line stochastic routing policies which identify the optimal next (path choice) action at the current decision node (intersection) for travelers, based on their preferring future paths with the shortest travel time, the lowest travel time variability, or a combination thereof, given the current network conditions. A modified label-correcting algorithm is provided to solve for the shortest path resulting from the proposed routing policies. Its running time is bounded by O(mn^2 ), where m and n are the number of arcs and nodes, respectively, in the network. Considering that real-time traffic information is usually available with a certain level of accuracy, the proposed on-line routing policy integrates an existing information fusion model by the authors (1), which provides real-time short-term arc travel time distributions by considering information accuracy. Numerical experiments are used to demonstrate the performance of the proposed routing policies/algorithms as well as the impacts of real-time information accuracy on the online stochastic routing.
  Authors: Du, Lili; Peeta, Srinivas; Kim, Yong Hoon
  Authors: Du, Lili; Peeta, Srinivas; Kim, Yong Hoon
  Year: 2013
  Document Type: Paper
  Subject: Planning and Forecasting
  Session: 844
  Paper Number: 13-1477
• Greedy Genetic Algorithm for Improving Capacity Reliability in Large-Scale Networks Considering the Effect of Low-Frequency Events: Application to Expressway Network in Tehran, Iran
  Abstract: One of the most important problems in the area of transportation network analysis is Network Design Problem (NDP). The main issue of NDP refers to its high computational effort. This study has been conducted to promote the computational efficiency of NDP under supply uncertainty, where a reliability measure -network capacity reliability- defines the performance of network, through two steps. At the first step, a fast method is presented for the measurement of the capacity reliability for urban transport networks. The method is based on link performance reliabilities, which are computed with regard to traffic volume and the Probability Density Function (PDF) of capacity, caused by low-frequency events (e.g., accident and vehicle breakdown). Under the occurrence of a low-frequency event it might be assumed that the travelers are not well informed about the consequence of the event in such a way that they can change their previous paths which were selected under the absence of the event (‘non-adaptive users’ is assumed). Thus, a User Equilibrium model with the assumption of maximum link capacities has been considered to assign demand volumes on links and to compute the performance reliability of each link. Furthermore, this paper adopts Genetic Algorithm (GA) with a modification on initial population generation sub-procedure (using a greedy algorithm) to expedite the GA used for optimization of capacity reliability. The proposed greedy GA is applied on a simple test network to calibrate GA’s requirements as well as to experiment the convergence of the proposed GA. Results of this application show that the computational efforts required by the proposed greedy GA is very less than that of the standard GA (e.g. 1:26 in terms of the number of iterations needed). The proposed method has also been applied on a real case study, the expressway network of Tehran City, Iran, and results indicate that the proposed GA can successfully be implemented even in very large networks.
  Authors: Babaei, Mohsen; Shariat-Mohaymany, Afshin
  Authors: Babaei, Mohsen; Shariat-Mohaymany, Afshin
  Year: 2013
  Document Type: Paper
  Subject: Planning and Forecasting
  Session: 844
  Paper Number: 13-1817
• Bicriterion Shortest-Path Problem with a General Nonadditive Cost
  Abstract: A bicriterion shortest path problem with a general nonadditive cost seeks to optimize a combination oftwo path attributes, one of which is evaluated by a nonlinear function. The paper identifies a number ofemerging transportation applications for which such a shortest path problem might be considered a coresubproblem. We propose to first approximate the general nonlinear attribute function with a piecewise linearcounterpart, and then solve each linear subproblem sequentially. A specialized method is developed tosolve subproblems, which makes use of the efficient path set (or the convex hull) to update upper and lowerbounds of the original problem. Conditions under which the solution to a subproblem must belong to theefficient path set are specified. Accordingly, we verify an established result in the piecewise linear case,that the optimal path must be efficient if the nonlinear attribute function is concave. If the optimal path to asubproblem is not efficient, partial path enumeration, implemented using a simple K-shortest path rankingprocedure, is conducted to close the duality gap. The proposed algorithm includes strategies aiming to minimizethe efforts for such path enumeration by making use of upper bounds available from the efficient pathset. Numerical experiments are conducted to demonstrate the correctness and effectiveness of the proposedalgorithm.
  Authors: Chen, Peng; Nie, Yu
  Authors: Chen, Peng; Nie, Yu
  Year: 2013
  Document Type: Paper
  Subject: Planning and Forecasting
  Session: 844
  Paper Number: 13-2771
• Sequential Bayesian Model for Network Design Problem with Uncertainties
  Abstract: Formulations for the Network Design Problem with Uncertainty (NDPU) usually characterize uncertainty by a discrete scenario set and tend not to fully explore the inherent correlations between different alternatives. As a result, solving the NDPU problem typically requires simulating an unnecessarily large number of candidate solutions. To facilitate more efficient use of the simulation runs, in this paper we formulate the NDPU problem as a constrained Bayesian Ranking and Selection (R&S) problem with correlated beliefs. In this formulation, each solution to the NDPU problem represents an "alternative" and the corresponding objective value represents a "reward" we want to maximize. We adaptively update our belief about the mean and covariance of the rewards of all alternatives through sequential simulation decisions. Constraints of the NDPU problem in the Bayesian R&S formulation are handled by penalizing the rewards of infeasible solutions while uncertainties are modeled by continuous probability distributions on the rewards. The constrained Bayesian R&S problem can then be solved by a Knowledge-Gradient-based method called the KGCB algorithm, which we modify to account for unknown variances of the alternatives. We apply our methodology to the Sioux Fall network as a case study. Results showed that the Bayesian R&S formulation, solved with the KGCB algorithm, converges faster than a fine-tuned Genetic Algorithm solver in the deterministic case and in addition saves as much as 80% of the simulation samples on average in the stochastic case. The methodologies developed can also be applied more broadly to a larger class of transportation problems with similar structures.
  Authors: Wang, Xun; Gao, H. Oliver
  Authors: Wang, Xun; Gao, H. Oliver
  Year: 2013
  Document Type: Paper
  Subject: Planning and Forecasting
  Session: 844
  Paper Number: 13-3168
• Finding Reliable Shortest Paths in Dynamic Stochastic Networks
  Abstract: A reliable a priori shortest path (RASP) offers the least time budget which ensures that a traveler can arrive at the destination on-time with the desired probability. RASP is equivalent to enumeratingall non-dominated paths under the first order stochastic dominance (FSD) rule. Compared with the problem in static networks, the RASP problem becomes more complex in dynamic networks because it is more difficult to compute path travel time distributions. Two modules of process are the keys to solve the RASP problem. One is the convolution scheme (how to compute a path travel time distribution from its member links' travel time distributions), and another one is the stochastic dominance scheme (how to determine non-dominated paths). This paper aims to find an efficient solution algorithm to this problem. Firstly, we develop an alternative convolution method based on adaptive discretization approach which was originally proposed to solve the RASP problem in static networks. On the other hand, we show that the higher order stochastic dominance rule can reduce the number of non-dominated paths, which promises to improve the computational efficiency. Numerical experiments show that the second-order stochastic dominance (SSD) rule offer good approximations, while the CPU time is reduced by at least 50%.
  Authors: Wu, Xing
  Authors: Wu, Xing
  Year: 2013
  Document Type: Paper
  Subject: Planning and Forecasting
  Session: 844
  Paper Number: 13-3260
• Evaluation of Shape Grammar Rules for Urban Transport Network Design
  Abstract: Shape grammar rules are increasingly applied in urban simulation. Even though many network design standards propose shape grammar rules, little is known of the measurable impact of these rules on the performance of transport networks. This paper provides a general definition of shape grammar rules for transport network design. Different rules are evaluated regarding a comprehensive objective function. Networks are designed and simulated on featureless planes to avoid a bias due to history. Findings are compared with real-world case studies. Different network characteristics are evaluated in this paper.The densities of network loops are high in all generated networks, and comparable with real-world grids and medieval fabrics. The average length of network loops decreases as an inverse function of road density, which is in line with graph theory. Intersection density is proportional to the network length. The average number or arms of an intersection depends on road density. A denser network has a disproportionately higher density of 4 arm intersections, compared to less denser networks.Additionally, different road types are assigned to each road segment. Hierarchical road type distribution has a significant but low influence on network user costs. Terrain boundaries, as well as predefined roads (e.g. boulevards) increase average user costs. However, the average increase strongly depends on the number of bridges and on the boulevard capacity. The results show that shape grammar rules for transport network design can be evaluated to increase the understanding of their impacts, which supports future design standards.
  Authors: Vitins, Basil Janis; Garcia-Dorado, Ignacio; Vanegas, Carlos; Aliaga, Daniel; Axhausen, Kay W.
  Authors: Vitins, Basil Janis; Garcia-Dorado, Ignacio; Vanegas, Carlos; Aliaga, Daniel; Axhausen, Kay W.
  Year: 2013
  Document Type: Paper
  Subject: Planning and Forecasting
  Session: 844
  Paper Number: 13-3834
• Traffic Performance Impacts of Link Removal on a Grid Urban Pattern
  Abstract: In this paper we explore how the traffic performance of a grid street network changes when links are removed. Our objectives are: to better understand the behavior of grid-like patterns when dealing with traffic; to evaluate the effects of link removal in the overall traffic performance; and, to explore how far from the full grid pattern, an urban structure can be still considered one. We create an abstract grid network composed of 100 nodes and bidirectional streets. A simple demand model is applied to load the network effectively. The objective is to emulate a dense urban environment. We develop a static traffic assignment model using the Frank-Wolfe algorithm. The accuracy of this model has been increased by a more detailed intersection modeling scheme. The link removal strategies seek representing both: operational eventualities (blockage of streets), and, city planning policies aiming at recovering space for other activities. Links are removed in different ways: in a total random manner, focusing on the center of the grid, and, focusing on the perimeter of the grid. Up to 30 % of the total links are removed.As it will be seen, we analyze the critical points of a grid system when accommodating traffic. We show that it is possible to remove a certain percentage of links without worsening traffic conditions excessively. This magnitude is very dependent on the link removal strategy. We believe that these results can be very useful for city and traffic planners.
  Authors: Ortigosa, Javier; Menendez, Monica
  Authors: Ortigosa, Javier; Menendez, Monica
  Year: 2013
  Document Type: Paper
  Subject: Planning and Forecasting
  Session: 844
  Paper Number: 13-3851
• Impacts of Correlations on Reliable Shortest-Path Finding: Simulation-Based Study
  Abstract: The focus of this paper is to examine how correlations in link travel times affect reliable path finding in a stochastic network. The most reliable path is defined in this paper as the path that requires the lowest travel time budget to ensure a given probability of on-time arrival. Such path can be found by solving the shortest path problem considering on-time arrival reliability, or SPOTAR. We propose to approximately solve SPOTAR using an approach based on Monte Carlo simulation. A major advantage of the simulation-based algorithm is its ability to deal with correlated link travel times. Using a real-world network, the study first validates the simulation-based algorithm by comparing it to a label-correcting algorithm, and then uses it to examine the impacts of the correlations in link travel times. The results of numerical experiments indicate that correlations affect the optimal SPOTAR solutions significantly. Yet, larger correlations do not always imply that larger errors would occur if they are ignored. Due to the difficulty to specify a large-scale covariance matrix that is physically meaningful, the study does not observe any robust relationship between the structural properties in correlations and their impacts on the SPOTAR solutions.
  Authors: Zockaie Kheiraie, Ali; Nie, Yu; Wu, Xing; Mahmassani, Hani S.
  Authors: Zockaie Kheiraie, Ali; Nie, Yu; Wu, Xing; Mahmassani, Hani S.
  Year: 2013
  Document Type: Paper
  Subject: Planning and Forecasting
  Session: 844
  Paper Number: 13-4425
• Algorithms for One-to-One Time-Dependent Shortest Pathon Real Networks
  Abstract: In this research, we propose one-to-one time dependent shortest path(TDSP) algorithms, where the link flow speeds depend on time intervals. For this work, first three general shortest path algorithms which have proven to be fast and efficient algorithms in real networks are selected. These are Dijkstra¡¯s algorithm with approximate buckets, Dijkstra¡¯s algorithm with double buckets and Graph growth algorithm with two queues, and all three algorithms are to compute shortest paths from one node to all nodes in a network. These algorithms are extended to compute a shortest path from an origin node to a destination node in time dependent networks. Also, instead of travel time models, flow speed models and arrival time functions are used in the three algorithms to hold the First-In First-Out property.Three extended algorithms are tested and evaluated on 3 data sets from real networks. Data set 1 consists of 10 low-detail state road networks and data set 2 consists of 10 high-detail state road networks in the United States. Data set 3 consists of 4 urban street networks for Anaheim, CA, Baltimore, MD, Chicago, IL, and Philadelphia, PA. Based on the computational results, among the three algorithms for TDSP, the best performing algorithms for solving one-to-one time dependent shortest path for urban street networks and for state wide networks, are extended Dijkstra¡¯s algorithm with double buckets and extended Graph growth algorithm with two queues, respectively.
  Authors: Kim, Taehyeong; Haghani, Ali; Kim, Hyoungsoo
  Authors: Kim, Taehyeong; Haghani, Ali; Kim, Hyoungsoo
  Year: 2013
  Document Type: Paper
  Subject: Planning and Forecasting
  Session: 844
  Paper Number: 13-1169
  Practice-Ready: Yes
• Parallel Label-Correcting Algorithms for Large-Scale Static and Dynamic Transportation Networks on Laptop Personal Computers
  Abstract: A parallel implementation of the Label Correcting Algorithm (LCA) for finding shortest paths on static networks is first presented. The parallel static LCA is then extended to include time-dependent link costs. For both the static and time-dependent cases, an efficient sparse matrix storage scheme that has been frequently employed by “sparse equations solver researchers” is adopted. It can be shown that the proposed sparse storage scheme is equivalent (in terms of computer memory requirement) to the forward or reverse star representation that is often used by transportation researchers.The proposed parallel (time-dependent) LCA simply assigns each processor to handle a number of source (or destination) nodes within a network. Both real (and randomly generated), static and time-dependent transportation networks (including a network with 100,000 nodes and 349,850 links) are extensively used to evaluate the numerical efficiency (in terms of accuracy, and wall-time) of the proposed parallel LCA, using inexpensive desktop/laptop Personal Computers (PCs), and under the C#, C++, and MATLAB programming languages.Numerical results demonstrate that the proposed parallel LCA is simple and very efficient. While implementing the proposed parallel LCA in the MATLAB / C++ environments offer the reasonable / very good efficiency of around 65% / 87%, its efficiency increased to be in the remarkable range of 95.11 % (which is very close to the 100% ideal/ perfectly linear efficiency) through 167.12% (which is considered as “super-linear” performance) when implementing in the C # environment.
  Authors: Nguyen, Duc Thai; Ng, ManWo
  Authors: Nguyen, Duc Thai; Ng, ManWo
  Year: 2013
  Document Type: Paper
  Subject: Planning and Forecasting
  Session: 844
  Paper Number: 13-2103
  Practice-Ready: Yes
• Variable Time-Discretization Strategy-Based, Time-Dependent Shortest-Path Algorithm for Dynamic Traffic Assignment
  Abstract: Within the Simulation-Based Dynamic Traffic Assignment (SBDTA) model, the Time-Dependent Shortest Path (TDSP) algorithm plays a crucial role in the path-set update procedure by solving for the current optimal auxiliary solution (shortest path). Common types of TDSP algorithms require temporal discretization of link/node time/cost data, and the discretization could affect the solution quality of TDSP and of the overall SBDTA as well. This paper introduces two variable time-discretization strategies applicable to TDSP algorithms. The strategies are aimed at determining the optimal time-discretization for time-dependent links/nodes travel time data. The first proposed strategy produces a specific discretization interval for each link. The second proposed strategy generates time-varying intervals for the same link over the analysis period. The proposed strategies are implemented in a link-based time-dependent A* algorithm and tested with two numerical experiments on two traffic networks. The results show that, with the same amount of computer memory usage, the proposed variable time-discretization strategies achieve considerably higher accuracy than that of uniform time discretization. Further, this study incorporates the modified TDSP into a SBDTA model. A numerical analysis on two separate networks evaluates the sensitivity and properties of SBDTA outputs with respect to the time-discretization strategy of TDSP. The analysis shows that the enhanced SBDTA model uses less memory, achieving better convergence at moderate computational tradeoff.
  Authors: Tian, Ye; Chiu, Yi-Chang
  Authors: Tian, Ye; Chiu, Yi-Chang
  Year: 2013
  Document Type: Paper
  Subject: Planning and Forecasting
  Session: 844
  Paper Number: 13-5279
  Practice-Ready: Yes
• Stochastic Shortest-Path Problem Considering Traffic Signals
  Abstract:

  The shortest path problem is very important in transportation field, but limited researches have considered intersection delays caused by traffic signals and queuing vehicles when seeking shortest path. When considered, the traffic signal was mostly modeled as fixed timing. Delays caused by queuing vehicles were seldom considered. Consequently, shortest path problem considering traffic signals is usually deterministic. In the case of actuated traffic signal control, however, the intersection delays are stochastic in nature. In addition, the delays experienced by a vehicle at a downstream intersection may depend on the delays it experiences at upstream intersections. In this paper the shortest path problem considering traffic signals is modeled based on the theory of Markov decision problem (MDP). The delays caused by actuated traffic signals as well as by queuing vehicles are included in the formulation. The problem is first formulated as an infinite horizon and countable state space MDP with absorbing state set. This formulation allows the intersection delays to be considered as stochastic and delays experienced by a vehicle at downstream intersection will depend on those at upstream intersections. As the MDP with countable state space cannot be solved directly in practice, a corresponding finite state space MDP is formulated taking advantage of the cyclic property of traffic signals such that the optimal policy can be solved for using value iteration algorithm. The output of the algorithm will be an optimal policy instead of a single optimal path. We show that the required input information for the model can be estimated from high resolution traffic data obtainable from field and numerical tests are carried out at the end.

  Authors: Sun, Jie; Liu, Henry X.
  Authors: Sun, Jie; Liu, Henry X.
  Year: 2013
  Document Type: Paper
  Subject: Planning and Forecasting
  Session: 844
  Paper Number: 13-4988
• Algorithms for One-to-One Time-Dependent Shortest Path on Real Networks
  Authors: Kim, Taehyeong
  Authors: Kim, Taehyeong
  Year: 2013
  Document Type: Presentation
  Subject: Planning and Forecasting
  Session: 844
  Paper Number: 13-1169
• Joint Optimization of Supply Chain Network Design and Highway Pavement Rehabilitation Plan Under Traffic Equilibrium
  Authors: Bai, Yun
  Authors: Bai, Yun
  Year: 2013
  Document Type: Presentation
  Subject: Planning and Forecasting
  Session: 844
  Paper Number: 13-0796
• Online Stochastic Routing Incorporating Real-Time Traffic Information
  Authors: Du, Lili
  Authors: Du, Lili
  Year: 2013
  Document Type: Presentation
  Subject: Planning and Forecasting
  Session: 844
  Paper Number: 13-1477
• Parallel Label-Correcting Algorithms for Large-Scale Static and Dynamic Transportation Networks on Laptop Personal Computers
  Authors: Nguyen, Duc
  Authors: Nguyen, Duc
  Year: 2013
  Document Type: Presentation
  Subject: Planning and Forecasting
  Session: 844
  Paper Number: 13-2103
• Finding Reliable Shortest Paths in Dynamic Stochastic Networks
  Authors: Wu, Xing
  Authors: Wu, Xing
  Year: 2013
  Document Type: Presentation
  Subject: Planning and Forecasting
  Session: 844
  Paper Number: 13-3260
• Traffic Performance Impacts of Link Removal on a Grid Urban Pattern
  Authors: Ortigosa, Javier
  Authors: Ortigosa, Javier
  Year: 2013
  Document Type: Presentation
  Subject: Planning and Forecasting
  Session: 844
  Paper Number: 13-3851
• Evaluation of Shape Grammar Rules for Urban Transport Network Design
  Authors: Vitins, Basil
  Authors: Vitins, Basil
  Year: 2013
  Document Type: Presentation
  Subject: Planning and Forecasting
  Session: 844
  Paper Number: 13-3834
• Impacts of Correlations on Reliable Shortest-Path Finding: Simulation-Based Study
  Authors: Nie, Yu
  Authors: Nie, Yu
  Year: 2013
  Document Type: Presentation
  Subject: Planning and Forecasting
  Session: 844
  Paper Number: 13-4425
• Stochastic Shortest-Path Problem Considering Traffic Signals
  Authors: Sun, Jie
  Authors: Sun, Jie
  Year: 2013
  Document Type: Presentation
  Subject: Planning and Forecasting
  Session: 844
  Paper Number: 13-4988
• Variable Time-Discretization Strategy-Based, Time-Dependent Shortest-Path Algorithm for Dynamic Traffic Assignment
  Authors: Tian, Ye
  Authors: Tian, Ye
  Year: 2013
  Document Type: Presentation
  Subject: Planning and Forecasting
  Session: 844
  Paper Number: 13-5279