Simulation‐based dynamic traffic assignment: Meta‐heuristic solution methods with parallel computing

The aim of this study is to solve the large‐scale dynamic traffic assignment (DTA) model using a simulation‐based framework, which is computationally a challenging problem. Many studies have been performed on developing an efficient algorithm to solve DTA. Most of the existing algorithms are based on path‐swapping descent direction methods. From the computational standpoint, the main drawback of these methods is that they cannot be parallelized. This is because the existing algorithms need to know the results of the last iteration to determine the next best path flow for the next iteration. Thus, their performance depends on the single initial or intermediate solution, which means they exploit a solution that satisfies the equilibrium conditions more than explore the solution space for the optimal solution. More specifically, the goal of this study is to overcome the drawbacks of serial algorithms by using meta‐heuristic algorithms known to be parallelizable and that have never been applied to the simulation‐based DTA problem. This study proposes two new solution methods: a new extension of the simulated annealing and an adapted genetic algorithm. With parallel simulation, the algorithm runs more simulations in comparison with existing methods, but the algorithm explores the solution space better and therefore obtains better solutions in terms of closeness to the optimal solution and computation time compared to classical methods.     

B‐Dynamic: An Efficient Algorithm for Dynamic User Equilibrium Assignment in Activity‐Travel Networks1

Abstract: Multi‐dimensional choice in dynamic traffic assignment (DTA)—for example, a combined model of activity location, time of participation, duration, and route choice decisions—results in exponentially increasing choice alternatives. Any efficient algorithm for solving the multi‐dimensional DTA problem must avoid enumeration of alternatives. In this article an algorithm that does not enumerate paths is presented. The algorithm is a novel extension of Algorithm B ( Dial, 2006 ) to dynamic networks and hence referred to as Algorithm B‐Dynamic. The DTA model proposed here uses a point queue model for traffic propagation that reduces computational complexity. The activity participation decision dimensions are incorporated through utility functions, which are a linear function of duration and schedule delay (early or late arrival penalty). Numerical examples are then presented to illustrate both the steps of the algorithm and its capabilities. Overall, the algorithm performed well for up to medium‐sized networks. Further, the algorithm scales fairly well with increasing demand levels.     

A Dual Variable Approximation‐Based Descent Method for a Bi‐level Continuous Dynamic Network Design Problem

Abstract: The transportation network design problem (NDP) considers modifying network topology or parameters, such as capacity, to optimize system performance by taking into account the selfish routing behavior of road users. The nature of the problem naturally lends itself to a bi‐level formulation of a problem that represents a static case of a Stackelberg game. The NDP is complex because users’ individual objectives do not necessarily align with system‐wide objectives; thus, it is difficult to determine the optimal allocation of limited resources. To solve the bi‐level dynamic NDP, this study develops a dual variable approximation‐based heuristic, which identifies the system‐wide gradient as a descent direction, and designs an iterative solution framework. Descent direction‐based approaches designed to solve bi‐level programming problems typically suffer from non‐differentiability, which can hamper the solution process. The proposed method addresses this issue by approximating the descent direction with dual variables that correspond to cell transmission model constraints and using the constructed rational direction to iteratively decrease the upper‐level objective while maintaining the feasibility of the lower‐level program. The proposed method was empirically applied to three networks of various sizes. The results obtained from this empirical solution were compared with the results from an exact Kth‐best algorithm and a genetic algorithm. The promising results demonstrate the efficacy and efficiency of the proposed descent method.     

Time‐Varying Lane‐Based Capacity Reversibility for Traffic Management

Abstract: This article presents a new bi‐level formulation for time‐varying lane‐based capacity reversibility problem for traffic management. The problem is formulated as a bi‐level program where the lower level is the cell‐transmission‐based user‐optimal dynamic traffic assignment (UODTA). Due to its Non‐deterministic Polynomial‐time hard (NP‐hard) complexity, the genetic algorithm (GA) with the simulation‐based UODTA is adopted to solve multiorigin multidestination problems. Four GA variations are proposed. GA1 is a simple GA. GA2, GA3, and GA4 with a jam‐density factor parameter (JDF) employ time‐dependent congestion measures in their decoding procedures. The four algorithms are empirically tested on a grid network and compared based on solution quality, convergence speed, and central processing unit (CPU) time. GA3 with JDF of 0.6 appears best on the three criteria. On the Sioux Falls network, GA3 with JDF of 0.7 performs best. The GA with the appropriate inclusion of problem‐specific knowledge and parameter calibration indeed provides excellent results when compared with the simple GA.     

Relay Requirement and Traffic Assignment of Electric Vehicles

This article defines, formulates, and solves a new equilibrium traffic assignment problem with side constraints—the traffic assignment problem with relays. The relay requirement arises from the driving situation that the onboard fuel capacity of vehicles is lower than what is needed for accomplishing their trips and the number and distribution of refueling infrastructures over the network are under the expected level. We proposed this problem as a modeling platform for evaluating congested regional transportation networks that serve plug‐in electric vehicles (in addition to internal combustion engine vehicles), where battery‐recharging or battery‐swapping stations are scarce. Specifically, we presented a novel nonlinear integer programming formulation, analyzed its mathematical properties and paradoxical phenomena, and suggested a generalized Benders decomposition framework for its solutions. In the algorithmic framework, a gradient projection algorithm and a labeling algorithm are adopted for, respectively, solving the primal problem and the relaxed master problem—the shortest path problem with relays. The modeling and solution methods are implemented for solving a set of example network problems. The numerical analysis results obtained from the implementation clearly show how the driving range limit and relay station location reshape equilibrium network flows.     

Solving Detour‐Based Fuel Stations Location Problems

This article studies the problem of locating fuel stations to minimize the extra cost spent in refueling detours, which belongs to a class of discretionary service facility location problems. Unlike many studies of similar problems in the literature, the proposed model considers capacity constraints and compares different ways to incorporate them in the formulation. Note that ignoring the capacity constraint results in nonoptimal and unrealistic solutions. The proposed models are solved using both an off‐the‐shelf solver (CPLEX) and a specialized meta‐heuristic method (Simulated Annealing) developed in this study. The solution methods are tested and compared in two case studies; a test benchmark network and a large‐scale network. An effort to overcome the memory limitation of CPLEX through more compact formulation was partially successful: it results in a model that is less tightly bounded by its linear relaxation and hence is much more difficult to solve. In contrast, the Simulated Annealing algorithm scales better and is able to consistently yield high‐quality solutions with a reasonable amount of computation time.     

Surrogate‐based toll optimization in a large‐scale heterogeneously congested network

Toll optimization in a large‐scale dynamic traffic network is typically characterized by an expensive‐to‐evaluate objective function. In this paper, we propose two toll‐level problems (TLPs) integrated with a large‐scale simulation‐based dynamic traffic assignment model of Melbourne, Australia. The first TLP aims to control the pricing zone (PZ) through a time‐varying joint distance and delay toll such that the network fundamental diagram (NFD) of the PZ does not enter the congested regime. The second TLP is built upon the first TLP by further considering the minimization of the heterogeneity of congestion distribution in the PZ. To solve the two TLPs, a computationally efficient surrogate‐based optimization method, that is, regressing kriging with expected improvement sampling, is applied to approximate the simulation input–output mapping, which can balance well between local exploitation and global exploration. Results show that the two optimal TLP solutions reduce the average travel time in the PZ (entire network) by 29.5% (1.4%) and 21.6% (2.5%), respectively. Reducing the heterogeneity of congestion distribution achieves higher network flows in the PZ and a lower average travel time or a larger total travel time saving in the entire network.     

A Cell‐Based Model for Multi‐class Doubly Stochastic Dynamic Traffic Assignment

Abstract: This article proposes a cell‐based multi‐class dynamic traffic assignment problem that considers the random evolution of traffic states. Travelers are assumed to select routes based on perceived effective travel time, where effective travel time is the sum of mean travel time and safety margin. The proposed problem is formulated as a fixed point problem, which includes a Monte–Carlo‐based stochastic cell transmission model to capture the effect of physical queues and the random evolution of traffic states during flow propagation. The fixed point problem is solved by the self‐regulated averaging method. The results illustrate the properties of the problem and the effectiveness of the solution method. The key findings include the following: (1) Reducing perception errors on traffic conditions may not be able to reduce the uncertainty of estimating system performance, (2) Using the self‐regulated averaging method can give a much faster rate of convergence in most test cases compared with using the method of successive averages, (3) The combination of the values of the step size parameters highly affects the speed of convergence, (4) A higher demand, a better information quality, or a higher degree of the risk aversion of drivers can lead to a higher computation time, (5) More driver classes do not necessarily result in a longer computation time, and (6) Computation time can be significantly reduced by using small sample sizes in the early stage of solution processes.     

Surrogate‐Based Optimization of Expensive‐to‐Evaluate Objective for Optimal Highway Toll Charges in Transportation Network

This article adopts a family of surrogate‐based optimization approaches to approximate the response surface for the transportation simulation input–output mapping and search for the optimal toll charges in a transportation network. The computational effort can thus be significantly reduced for the expensive‐to‐evaluate optimization problem. Meanwhile, the random noise that always occurs through simulations can be addressed by this family of approaches. Both one‐stage and two‐stage surrogate models are tested and compared. A suboptimal exploration strategy and a global exploration strategy are incorporated and validated. A simulation‐based dynamic traffic assignment model DynusT (Dynamic Urban Systems in Transportation) is utilized to evaluate the system performance in response to different link‐additive toll schemes implemented on a highway in a real road transportation network. With the objective of minimizing the network‐wide average travel time, the simulation results show that implementing the optimal toll predicted by the surrogate model can benefit society in multiple ways. The travelers gain from the 2.5% reduction (0.45 minutes) of the average travel time. The total reduction in the time cost during the extended peak hours would be around US$65,000 for all the 570,000 network users assuming a US$15 per hour value of time. Meanwhile, the government benefits from the 20% increase of toll revenue compared to the current situation. Thus, applying the optimized pricing scheme in real world can be an encouraging policy option to enhance the performance of the transportation system in the study region.     

A decomposition scheme for parallelization of system optimal dynamic traffic assignment on urban networks with multiple origins and destinations

This paper presents a decomposition scheme to find near‐optimal solutions to a cell transmission model‐based system optimal dynamic traffic assignment problem with multiple origin‐destination pairs. A linear and convex formulation is used to define the problem characteristics. The decomposition is designed based on the Dantzig–Wolfe technique that splits the set of decision variables into subsets through the construction of a master problem and subproblems. Each subproblem includes only a single origin‐destination pair with significantly less computational burden compared to the original problem. The master problem represents the coordination between subproblems through the design of interactive flows between the pairs. The proposed methodology is implemented in two case study networks of 20 and 40 intersections with up to 25 origin‐destination pairs. The numerical results show that the decomposition scheme converges to the optimal solution, within 2.0% gap, in substantially less time compared to a benchmark solution, which confirms the computational efficiency of the proposed algorithm. Various network performance measures have been assessed based on different traffic state scenarios to draw managerial insights.     

A Hybrid Branch‐and‐Bound and Benders Decomposition Algorithm for the Network Design Problem

Given a set of candidate road projects associated with costs, finding the best subset with respect to a limited budget is known as the network design problem (NDP). The NDP is often cast in a bilevel programming problem which is known to be NP‐hard. In this study, we tackle a special case of the NDP where the decision variables are integers. A variety of exact solutions has been proposed for the discrete NDP, but due to the combinatorial complexity, the literature has yet to address the problem for large‐size networks, and accounting for the multimodal and multiclass traffic flows. To this end, the bilevel problem is solved by branch‐and‐bound. At each node of the search tree, a valid lower bound based on system optimal (SO) traffic flow is calculated. The SO traffic flow is formulated as a mixed integer, non‐linear programming (MINLP) problem for which the Benders decomposition method is used. The algorithm is coded on a hybrid and synchronized platform consisting of MATLAB (optimization engine), EMME 3 (transport planning module), MS Access (database), and MS Excel (user interface). The proposed methodology is applied to three examples including Gao's network, the Sioux‐Falls network, and a real size network representing the city of Winnipeg, Canada. Numerical tests on the network of Winnipeg at various budget levels have shown promising results.     

Column Generation‐Based Approach for Solving Large‐Scale Ready Mixed Concrete Delivery Dispatching Problems

Ready mix concrete (RMC) dispatching forms a critical component of the construction supply chain. However, optimization approaches within the RMC dispatching continue to evolve due to the specific size, constraints, and objectives required of the application domain. In this article, we develop a column generation algorithm for vehicle routing problems (VRPs) with time window constraints as applied to RMC dispatching problems and examine the performance of the approach for this specific application domain. The objective of the problem is to find the minimum cost routes for a fleet of capacitated vehicles serving concrete to customers with known demand from depots within the allowable time window. The VRP is specified to cover the concrete delivery problem by adding additional constraints that reflect real situations. The introduced model is amenable to the Dantzig–Wolfe reformulation for solving pricing problems using a two‐staged methodology as proposed in this article. Further, under the mild assumption of homogeneity of the vehicles, the pricing sub‐problem can be viewed as a minimum‐cost multi‐commodity flow problem and solved in polynomial time using efficient network simplex method implementations. A large‐scale field collect data set is used for evaluating the model and the proposed solution method, with and without time window constraints. In addition, the method is compared with the exact solution found via enumeration. The results show that on average the proposed methodology attains near optimal solutions for many of the large sized models but is 10 times faster than branch‐and‐cut.     

A Linear Model for the Continuous Network Design Problem

Abstract:   This article is concerned with the continuous network design problem on traffic networks, assuming system optimum traffic flow conditions and time-dependent demand. A linear programming formulation is introduced based on a dynamic traffic assignment (DTA) model that propagates traffic according to the cell transmission model. The introduced approach is limited to continuous link improvements and does not provide for new link additions. The main contribution of the article is to provide an analytical formulation for network design that accounts for DTA conditions that can be used for further analysis and extensions. The model is tested on a single destination example network, resembling a freeway corridor, for various congestion levels, loading patterns and budget sizes, to demonstrate the simplicity and effectiveness of the approach.     

Multi‐Objective Mathematical Programming Approach to Construction Laborer Assignment with Equity Consideration

Construction laborer assignment is the assignment of laborers in a team to the tasks for a daily work in a construction project. This study proposes a mathematical programming approach to examine the optimal construction laborer assignment problem with the objectives of productivity and occupational health and safety while considering equity between laborers. Several linearization techniques are presented to transform the mathematical programming model into a mixed‐integer linear program, which can be solved by off‐the‐shelf mixed‐integer linear solvers. The proposed model is applied to extensive numerical experiments and the results show that the mathematical programming approach outperforms a conventional heuristic by over 10% in terms of job completion time. This implies considerable overhead, equipment, and manpower savings for the construction industry.     

A Mixed User‐Equilibrium and System‐Optimal Traffic Flow for Connected Vehicles Stated as a Complementarity Problem

Connected vehicles (CVs), be they autonomous vehicles or a fleet of cargo carriers or Uber, are a matter of when they become a reality and not if. It is not unreasonable to think that CV technology may have a far‐reaching impact, even to the genesis of a completely new traffic pattern. To this end, the literature has yet to address the routing behavior of the CVs, namely traffic assignment problem (TAP) (perhaps it is assumed, they ought to follow the traditional shortest possible paths, known as user equilibrium [UE]). It is possible that real‐time data could be derived from the vehicles’ communications that in turn could be used to achieve a better traffic circulation. In this article, we propose a mathematical formulation to ensure the CVs are seeking the system optimal (SO) principles, while the remainder continue to pursue the old‐fashioned UE pattern. The model is formulated as a nonlinear complementarity problem (NCP). This article contributes to the literature in three distinct ways: (i) mathematical formulation for the CVs’ routing, stated as a mixed UE‐SO traffic pattern, is proposed; (ii) a variety of realistic features are explicitly considered in the solution to the TAP including road capacity, elastic demand, multiclass and asymmetric travel time; and (iii) formal proof of the existence and uniqueness of the solutions are also presented. The proposed methodology is applied to the networks of Sioux‐Falls and Melbourne.     

Applying Projection‐Based Methods to the Asymmetric Traffic Assignment Problem

This article examines the application of a path‐based algorithm to the static and fixed demand asymmetric traffic assignment problem. The algorithm is of the simplicial decomposition type and it solves the equilibration or master problem step by means of five existing projection methods for variational inequality problems to evaluate their performance on real traffic networks. The projection methods evaluated are: (1) a cost approximation‐based method for minimizing the Fukushima's gap function, (2) the modified descent method of Zhu and Marcotte ( 1988 ), (3) the double projection method of Khobotov ( 1987 ) and three of its recently developed variants (Nadezhkina and Takahashi, 2006 ; Wang et al., 2010 ; and He et al., 2012); (4) the method of Solodov and Svaiter ( 1999 ); and (5) the method of Solodov and Tseng ( 1996 ). These projection methods do not require evaluation of the Jacobians of the path cost functions. The source for asymmetries are link costs with interactions, as in the case of priority ruled junctions. The path‐based algorithm has been computationally tested using the previous projection methods on three medium to large networks under different levels of congestion and the computational results are presented and discussed. Comparisons are also made with the basic projection algorithm for the fixed demand asymmetric traffic assignment problem. Despite the lack of monotonicity properties of the test problems, the only method that failed to converge under heavy congestion levels was the basic projection algorithm. The fastest convergence was obtained in all cases solving the master problem step using the method of He et al. (2012), which is a variant of Khobotov's method.     

Reliability‐Based Transit Assignment for Congested Stochastic Transit Networks

Abstract: This article proposes a nonlinear complementarity problem (NCP) formulation for the risk‐aversive stochastic transit assignment problem in which in‐vehicle travel time, waiting time, capacity, and the effect of congestion are considered as stochastic variables simultaneously and both their means and variances are incorporated into the formulation. A new congestion model is developed and captured in the proposed NCP formulation to account for different effects of on‐board passengers and passengers waiting at stops. A reliability‐based user equilibrium condition is also defined based on the proposed generalized concept of travel time budget referred to as effective travel cost, and is captured in the formulation. A column generation based algorithm is proposed to solve the NCP formulation. A survey was conducted to validate that the degree of risk aversion of transit passengers affects their route choices. Numerical studies were performed to demonstrate the problem and the effectiveness of the proposed algorithm. The results obtained show that underestimating the congestion effect and ignoring the risk aversion behavior can overestimate the patronage of transit service, which have profound implications on the profit of the operators involved and the development of transit network design models.     

Cross‐comparison of convergence algorithms to solve trip‐based dynamic traffic assignment problems

Solving a dynamic traffic assignment problem in a transportation network is a computational challenge. This study first reviews the different algorithms in the literature used to numerically calculate the user equilibrium (UE) related to dynamic network loading. Most of them are based on iterative methods to solve a fixed‐point problem. Two elements must be computed: the path set and the optimal path flow distribution between all origin–destination pairs. In a generic framework, these two steps are referred to as the outer and the inner loops, respectively. The goal of this study is to assess the computational performance of the inner loop methods that calculate the path flow distribution for different network settings (mainly network size and demand levels). Several improvements are also proposed to speed up convergence: four new swapping algorithms and two new methods for the step size initialization used in each descent iteration. All these extensions significantly reduce the number of iterations to obtain a good convergence rate and drastically speed up the overall simulations. The results show that the performance of different components of the solution algorithm is sensitive to the network size and saturation. Finally, the best algorithms and settings are identified for all network sizes with particular attention being given to the largest scale.     

Case-Based Reasoning for Real-Time Traffic Flow Management

Real-time traffic management is a promising approach for alleviating congestion. This approach uses real-time and predicted traffic information to develop routing strategies that optimize the performance of highway networks. This article explores the potential for using case-based reasoning (CBR), an emerging artificial intelligence (AI) paradigm, to overcome the limitations of existing traffic-management decision support systems. To illustrate the feasibility of the approach, the article develops and evaluates a prototype CBR routing system for a real-world network in Hampton Roads, Virginia. Cases for building the system's case base are generated using a heuristic dynamic traffic assignment (DTA) model specifically designed for the region. Using a set of 25 new independent cases, the performance of the prototype system is evaluated by comparing its solutions with those of the DTA model. The evaluation results demonstrate the feasibility of the CBR approach. The prototype system was capable of running in real time and produced high-quality solutions using case bases of reasonable size.     

环境污染限制及最优信号控制条件下的综合离散网络设计问题

现代城市综合交通网络设计问题研究的主要内容就是通过新建或改善道路网络,用以减少现代交通带来的环境污染、合理设置交通信号等诸方面的问题。将道路环境能力限制、最优交通信号设置问题与城市交通离散网络设计问题结合起来研究,一方面通过修建新的路段使交通需求量达到最大从而满足城市中不断增长的交通需求;另一方面通过道路环境能力限制使交通网络的最大需求量能符合现代城市环境保护的要求。给出了描述上述问题的一个双层规划模型及其启发式求解算法。最后,通过一个简单的算例,说明该算法是可行并且有效的。