A computational model for the probit‐based dynamic stochastic user optimal traffic assignment problem

This paper focuses on computational model development for the probit‐based dynamic stochastic user optimal (P‐DSUO) traffic assignment problem. We first examine a general fixed‐point formulation for the P‐DSUO traffic assignment problem, and subsequently propose a computational model that can find an approximated solution of the interest problem. The computational model includes four components: a strategy to determine a set of the prevailing routes between each origin–destination pair, a method to estimate the covariance of perceived travel time for any two prevailing routes, a cell transmission model‐based traffic performance model to calculate the actual route travel time used by the probit‐based dynamic stochastic network loading procedure, and an iterative solution algorithm solving the customized fixed‐point model. The Ishikawa algorithm is proposed to solve the computational model. A comparison study is carried out to investigate the efficiency and accuracy of the proposed algorithm with the method of successive averages. Two numerical examples are used to assess the computational model and the algorithm proposed. Results show that Ishikawa algorithm has better accuracy for smaller network despite requiring longer computational time. Nevertheless, it could not converge for larger network. Copyright © 2010 John Wiley & Sons, Ltd.     

Shortest route algorithm with movement prohibitions

This paper presents an algorithm with movement prohibitions which eliminates some problems encountered in network representation used for traffic assignment models, and further allows the representation of the network to be simplified. The paper first presents an appraisal of some proposed methods and reviews the basic concept of existing shortest-route algorithms. The problem of obtaining shortest routes in networks with movement prohibitions is formulated and an algorithm presented. The computational procedure is illustrated by means of a numerical example. The computational efficiency of the algorithm is tested and the test results show that the algorithm is very efficient.     

Traffic assignment by paired alternative segments

The static user-equilibrium (UE) traffic assignment model is widely used in practice. One main computational challenge in this model is to obtain sufficiently precise solutions suitable for scenario comparisons, as quickly as possible. An additional computational challenge stems from the need in practice to perform analyses based on route flows, which are not uniquely determined by the UE condition. Past research focused mainly on the first aspect. The purpose of this paper is to describe an algorithm that addresses both issues. The traffic assignment by paired alternative segments (TAPAS) algorithm, focuses on pairs of alternative segments as the key building block to the UE solution. A condition of proportionality, which is practically equivalent to entropy maximization, is used to choose one stable route flow solution. Numerical results for five publicly available networks, including two large-scale realistic networks, show that the algorithm can identify highly precise solutions that maintain proportionality in relatively short computation times.     

On the dual approach to the traffic assignment problem

This paper attempts to explore the possibility of solving the traffic assignment problem with elastic demands by way of its dual problem. It is shown that the dual problem can be formulated as a nonsmooth convex optimization problem of which the objective function values and subgradients are conveniently calculated by solving shortest path problems associated with the transportation network. A subgradient algorithm to solve the dual problem is presented and limited computational experience is reported. The computational results are encouraging enough to demonstrate the effectiveness of the proposed approach.     

An efficient and exact event-based algorithm for solving simplified first order dynamic network loading problems in continuous time

In this paper a novel solution algorithm is proposed for exactly solving simplified first order dynamic network loading (DNL) problems for any generalised network. This DNL solution algorithm, termed eLTM (event-based Link Transmission Model), is based on the seminal Lighthill–Witham–Richards (LWR) model, adopts a triangular fundamental diagram and includes a generalised first order node model formulation. Unlike virtually all DNL solution algorithms, eLTM does not rely on time discretisation, but instead adopts an event based approach. The main advantage of this approach is the possibility of yielding exact results. Furthermore, an approximate version of the same algorithm is introduced. The user can configure an a-priori threshold that dictates the approximation error (measurable a-posteriori). Using this approximation the computational effort required decreases significantly, making it especially suitable for large scale applications. The computational complexity is investigated and results are demonstrated via theoretical and real world case studies. Fixed periods of stationary demands are included adopting a matrix demand profile to mimic basic departure time demand fluctuations. Finally, the information loss of the approximate solution is assessed under different configurations.     

Approximate algorithms for the discrete network design problem

The discrete network design problem is one of finding a set of feasible actions (projects) from among a collection of possible actions, that when implemented, optimizes some objective function(s). This is a combinatorial optimization problem that is very expensive to solve exactly. This paper proposes two algorithms for obtaining approximate solutions to the discrete network design problem with much less computational effeort. The computational savings are achieved by approximating the original problem with a new formulation which is easier to solve. The first algorithm proposed solves this approximate problem exactly, while the second is even more efficient, but provides only a near-optimal solution to the approximate problem. Experience with test problems indicates that these approximations can reduce the computational effort by a factor of 3–5, with little loss in solution accuracy.     

The dynamic shortest path problem with time-dependent stochastic disruptions

The dynamic shortest path problem with time-dependent stochastic disruptions consists of finding a route with a minimum expected travel time from an origin to a destination using both historical and real-time information. The problem is formulated as a discrete time finite horizon Markov decision process and it is solved by a hybrid Approximate Dynamic Programming (ADP) algorithm with a clustering approach using a deterministic lookahead policy and value function approximation. The algorithm is tested on a number of network configurations which represent different network sizes and disruption levels. Computational results reveal that the proposed hybrid ADP algorithm provides high quality solutions with a reduced computational effort.     

Vehicle sharing system with fleet sizing and multi-transportation modes under allowable shortages: a hybrid metaheuristic approach

In this paper, a vehicle sharing system with multi-transportation modes and allowable shortage is presented. This model aims to minimize the system's total cost by using optimum locations and number of stations, routes, transportation modes, station capacities for different modes and time between stations balancing. Because of the model's complexity, currently available proprietary software is not able to solve the model in a reasonable computational time, so a hybrid algorithm based on a genetic algorithm (GA) and particle swarm optimization is presented. The results confirm its efficiency compared with the classic GA and exact solution methods. Moreover, a sensitivity analysis shows the applicability of the proposed algorithm.     

盾构隧道通用楔形管片排版系统的核心算法研究

盾构隧道通用楔形管片是通过前后两环的相对旋转来拟合线路中的直线和曲线要素,简化了模板设计,通用性强、质量容易保证。通用楔形管片拼装设计的关键是根据线路的平、竖曲线要素和偏差要求确定环宽和楔形量,而每一环衬砌的偏差计算是通过排版来实现的。文章对通用楔形管片排版的主要步骤和核心算法作了介绍,其中包括平、竖曲线上的坐标法定点算法、线路上理想点的二分法求值算法,以及空间任意点绕任意轴旋转的计算机图形学算法。文章最后介绍了一个盾构区间隧道的排版过程及结果。     

A genetic algorithm‐optimized fuzzy logic controller to avoid rear‐end collisions

In this paper, a rear‐end collision control model is proposed using the fuzzy logic control scheme. Through detailed analysis of car‐following cases, our fuzzy control system is established with reasonable control rules. Furthermore, a genetic algorithm is introduced into the fuzzy rules refining process to reduce the computational complexity while maintaining accuracy. Numerical results indicate that our genetic algorithm‐optimized fuzzy logic controller outperforms the traditional fuzzy logic controller in terms of better safety guarantee and higher traffic efficiency. Copyright © 2016 John Wiley & Sons, Ltd.     

A Granular Variable Tabu Neighborhood Search for the capacitated location-routing problem

This paper proposes a new heuristic algorithm for the Capacitated Location-Routing Problem (CLRP), called Granular Variable Tabu Neighborhood Search (GVTNS). This heuristic includes a Granular Tabu Search within a Variable Neighborhood Search algorithm. The proposed algorithm is experimentally compared on the benchmark instances from the literature with several of the most effective heuristics proposed for the solution of the CLRP, by taking into account the CPU time and the quality of the solutions obtained. The computational results show that GVTNS is able to obtain good average solutions in short CPU times, and to improve five best known solutions from the literature. The main contribution of this paper is to show a successful new heuristic for the CLRP, combining two known heuristic approaches to improve the global performance of the proposed algorithm for what concerns both the quality of the solutions and the computing times required to find them.     

A three-stage computational approach to network matching

Network matching is frequently needed for integrating data that come from different sources. Traditional ways of finding correspondences between networks are time-consuming and require considerable manual manipulation. This paper describes a three-stage matching algorithm (node matching, segment matching, and edge matching) that combines bottom-up and top-down procedures to carry out the matching computation. As it uses sensitive matching measures, the proposed algorithm promises good improvement to existing algorithms. An experiment of matching two waterway networks is reported in the paper. The results of this experiment demonstrate that a reasonable matching rate and good computational efficiency can be achieved with this algorithm. The paper also briefly discusses necessary improvements in areas of linear alignment, aspatial matching and higher-level matching.     

A note on using Davidson's function in equilibrium assignment

This paper describes the use of the Davidson congestion function in modelling network flows using equilibrium assignment. A modification to the function is given, which defines the function over all flows values, and consequently removes computational difficulties noted in earlier studies. The modification requires the inclusion of an additional model parameter, and the selection of a suitable value for this parameter is studied for two sets of data. The modified Davidson function is also compared to two alternative functions; a step-wise linear function and a quartic polynomial function, which have both been proposed as congestion functions. Comparisons are made between observed link volumes and the assigned volumes from these models. It is concluded that the modified Davidson function is useful for inclusion in an equilibrium assignment model, given its ability to reflect differences in network link type (e.g. capacity and speed) and environment through its parameters, the conceptual advantage of the function through its derivation from queueing theory, and the previous discovery of reliable methods for estimating its parameters. A value of about 0.8–0.9 is suggested for the parameter (μ, 0 < μ < 1) introduced in the modification.     

A geometry-based algorithm to provide guidance for electric vehicle charging

Electric vehicles (EVs) have been regarded as effective options for solving the environmental and energy problems in the field of transportation. However, given the limited driving range and insufficient charging stations, searching and selecting charging stations is an important issue for EV drivers during trips. A smart charging service should be developed to help address the charging issue of EV drivers, and a practical algorithm for charging guidance is required to realise it. This study aims to design a geometry-based algorithm for charging guidance that can be effectively applied in the smart charging service. Geographic research findings and geometric approaches are applied to design the algorithm. The algorithm is practical because it is based on the information from drivers’ charging requests, and its total number of calculations is significantly less than that of the conventional shortest-first algorithm. The algorithm is effective because it considers the consistency of direction trend between the charging route and the destination in addition to the travel distance, which conforms to the travel demands of EV drivers. Moreover, simulation examples are presented to demonstrate the proposed algorithm. Results of the proposed algorithm are compared with those of the other two algorithms, which show that the proposed algorithm can obtain a better selection of charging stations for EV drivers from the perspective of entire travel chains and take a shorter computational time.     

Forecasting journey time distribution with consideration to abnormal traffic conditions

Travel time is an important index for managers to evaluate the performance of transportation systems and an intuitive measure for travelers to choose routes and departure times. An important part of the literature focuses on predicting instantaneous travel time under recurrent traffic conditions to disseminate traffic information. However, accurate travel time prediction is important for assessing the effects of abnormal traffic conditions and helping travelers make reliable travel decisions under such conditions. This study proposes an online travel time prediction model with emphasis on capturing the effects of anomalies. The model divides a path into short links. A Functional Principal Component Analysis (FPCA) framework is adopted to forecast link travel times based on historical data and real-time measurements. Furthermore, a probabilistic nested delay operator is used to calculate path travel time distributions. To ensure that the algorithm is fast enough for online applications, parallel computation architecture is introduced to overcome the computational burden of the FPCA. Finally, a rolling horizon structure is applied to online travel time prediction. Empirical results for Guangzhou Airport Expressway indicate that the proposed method can capture an abrupt change in traffic state and provide a promising and reliable travel time prediction at both the link and path levels. In the case where the original FPCA is modified for parallelization, accuracy and computational effort are evaluated and compared with those of the sequential algorithm. The proposed algorithm is found to require only a piece rather than a large set of traffic incident records.     

A new approach to time-of-day control based on a dynamic freeway traffic model

This paper presents a new approach to time-of-day control. While time-of-day control strategies presented up-to-now are only optimal under steady-state conditions, the control algorithm derived in this paper takes into account the evolution of traffic flow according to the time delay between a volume change at a ramp and its subsequent disturbance at a freeway point downstream. The new control strategy is based on the solution of a linear programming optimization problem and makes freeway volume hold the capacity constraints for the total time of control operation. In order to reduce the computational effort a simplified version of the new algorithm is also discussed. Simulation results obtained by use of two different traffic flow models show that control derived through the new algorithm can avoid congestion and ensure operation with peak performance even if a steady-state condition is never attained.     

Scheduling of airport runway operations using stochastic branch and bound methods

In this paper we present a solution methodology based on the stochastic branch and bound algorithm to find optimal, or close to optimal, solutions to the stochastic airport runway scheduling problem. The objective of the scheduling problem is to find a sequence of aircraft operations on one or several runways that minimizes the total makespan, given uncertain aircraft availability at the runway. Enhancements to the general stochastic branch and bound algorithm are proposed and we give the specific details pertaining to runway scheduling. We show how the algorithm can be terminated early with solutions that are close to optimal, and investigate the impact of the uncertainty level. The computational experiment indicates that the sequences obtained using the stochastic branch and bound algorithm have, on average, 5–7% shorter makespans than sequences obtained using deterministic sequencing models. In addition, the proposed algorithm is able to solve instances with 14 aircraft using less than 1 min of computation time.     

Development and calibration of a long-distance passenger traffic assignment model

This paper studies the assignment of long-distance passenger traffic on a highway corridor network. First, we propose a traditional model for the long-distance traffic assignment considering interactions with local commuter traffic. It addresses the effect of local networks on highway corridors. An iterative algorithm is developed to solve for the exact solution. Then, to address the potential computational issues that arise therein, a decomposition method is proposed by introducing a new concept of corridor elasticity. An assignment procedure for long-distance passenger traffic is developed accordingly. Numerical tests show that the proposed decomposition method makes significant improvements in computational performance at a small loss of optimality. This decomposition method well approximates the exact assignment from the traditional formulation, especially when the highway corridors are near-saturation. The proposed decomposition method appears practical for application.     

A modification to Kruithof's double-factor method

A modification of Kruithof's double-factor algorithm (sometimes called the Furness iterative method) that takes into account zones which lie outside the boundary of a traffic network is examined analytically. Basically the revised algorithm allows certain rows and columns of the base traffic matrix to be only proportionally scaled while the remaining rows and columns which have pre-specified row and column totals are scaled in the usual biproportional way. This paper shows that all the properties (such as uniqueness, reversibility, existence) which hold for the traditional biproportional transformation also hold for the modified transformation under certain positivity assumptions.     

Optimal feeder bus routes on irregular street networks

The methodology presented here seeks to optimize bus routes feeding a major intermodal transit transfer station while considering intersection delays and realistic street networks. A model is developed for finding the optimal bus route location and its operating headway in a heterogeneous service area. The criterion for optimality is the minimum total cost, including supplier and user costs. Irregular and discrete demand distributions, which realistically represent geographic variations in demand, are considered in the proposed model. The optimal headway is derived analytically for an irregularly shaped service area without demand elasticity, with non‐uniformly distributed demand density, and with a many‐to‐one travel pattern. Computer programs are designed to analyze numerical examples, which show that the combinatory type routing problem can be globally optimized. The improved computational efficiency of the near‐optimal algorithm is demonstrated through numerical comparisons to an optimal solution obtained by the exhaustive search (ES) algorithm. The CPU time spent by each algorithm is also compared to demonstrate that the near‐optimal algorithm converges to an acceptable solution significantly faster than the ES algorithm.